Equations

Question 1

hamming rule

Answer 1

d + p + 1 <= 2^p
d = data bits
p = parity bits

Question 2

measuring performance: cycles per instructions

Answer 2

CPI = (sum(CPI . Ii)/Ic
- Ii = executed instructions (type i)
- Ic = executed instructions (total)

Question 3

measuring performance: time to execute a program (2 equations)

Answer 3

T = (Ic x CPI)/f
OR
T = (Ic(p + m.k)/f
- Ic = executed instructions
- f = frequency
- p = cycles to decode instructions
- m = number of memory references needed
- k = memory cycle time

Question 4

measuring performance: instructions per second (2 equations)

Answer 4

IPSr = Ic/T
OR
IPSr= f/CPI
- IPSr = rate of instructions per second
- Ic = executed instructions (total)
- T = total execution time
- f = frequency
- CPI = cycles per instructions

Question 5

measuring performance: floating-point operations per second

Answer 5

FLOPSr = If/T
- FLOPSr = rate of floating-point operations per second
- If = executed floating-point operations (total)
- T = total execution time

Question 6

speedup general equation

Answer 6

Sp = T1/Tp
- Tp = execution time with p processors

Question 7

bounds of speedup

Answer 7

1 <= Sp <= p

Question 8

parallel efficiency

Answer 8

Ep = Sp/p
- p = number of processors

Question 9

parallel efficiency bounds

Answer 9

1/p <= Ep <= 1

Question 10

strong scaling

Answer 10

Amdahl’s law -
Tp = s.T1 + (1 - s).T1/p
- Tp = execution time with p processors
- p = number of processors
- s = fraction of code that must run sequentially

Question 11

speed up in strong scaling

Answer 11

Sp = T1/Tp = p/(s.p + 1 - s)
- p = number of processors
- s = fraction of code that must run sequentially

Question 12

weak scaling

Answer 12

Gustafson’s law -
T1 = s.Tp + (1 - s).Tp.p
- s = fraction of code that must be run sequentially
- p = number of processors
- Tp = execution time with p processors

Question 13

speedup in weak scaling

Answer 13

Sp = T1/Tp = s + (1 - s).p

Question 14

waiting time in queue systems

Answer 14

Little’s law -
L = lambda x W
- L = items waiting in the system
- lambda - average arrival time (items per unit time)
- W = average waiting time in the system

Question 15

pipeline performance: cycle time

Answer 15

t = max1<=i<=k( ti )+ d = tm + d
- ti = time delay of ith pipeline stage
- k = number of pipeline stages
- d = delay of latch
- tm = maximum stage delay

Question 16

pipeline performance: total pipeline time

Answer 16

Tk,n = (k + n - 1).t
- Tk,n = execution time of n instructions in k-stages
- t = cycle time
- k = number of pipeline stages
- n = number of instructions

Question 17

pipeline: speedup

Answer 17

Sk = T1,n/Tk,n = (n.k)/(k + n - 1)
- Sk = speedup of k-stage over 1-stage pipeline
- Tk,n = execution time of n instructions in k-stage pipeline
- t = cycle time
- k = number of pipeline stages
- n = number of instructions

Question 18

pipeline: limit of speedup

Answer 18

k

Question 19

memory hierarchy performance modelling: expected access time

Answer 19

ts = h.t1 + (1 - h).(t1 + t2)
= t1 + (1 - h).t2
- ts = average system access time
- h = M1 hit ratio
- t1 = access time of M1
- t2 = access time of M2

Question 20

memory hierarchy performance modelling: average cost per bit

Answer 20

Cs = (C1.S1 + C2.S2)/(S1 + S2)
- Cs = average system cost per bit
- C1 = average cost per bit of M1
- C2 = average cost per bit of M2
- S1 = size of M1
- S2 = size of M2

Question 21

memory hierarchy performance modelling: access efficiency

Answer 21

T1/Ts = T1/(T1 + (1 - H).T2)
- T1 = access time of M1
- Ts = average system access time
- H = M1 hit ratio
- T2 = access time of M2

Question 22

performance modelling memory hierarchy: average access time

Answer 22

Ts = sum(harmonic((1 - hj).hi.ti))
-Ts = average system access time
- h = Mi hit ratio
- ti = access time of Mi

Question 23

non RAM transfer formula

Answer 23

Tn = Ta + n/R
- Ta = access time
- n = number of bits
- r = transfer rate in bps

Question 24

main memory formula

Answer 24

M = 2^n/K
- k = blocks
- 2^n = addressable words

Question 25

cache line size

Answer 25

tag + control bits

Question 26

direct mapping formula

Answer 26

i = j mod m - i = cache line - j = main memory block - m = number of cache lines

Question 27

direct mapping: word

Answer 27

w bits

Question 28

direct mapping: cache line

Answer 28

r

Question 29

direct mapping: tag bits

Answer 29

s - r

Question 30

direct mapping: address length

Answer 30

s + w

Question 31

direct mapping: block size

Answer 31

2^w

Question 32

direct mapping: number of blocks in main memory

Answer 32

2^s

Question 33

direct mapping: number of lines in cache

Answer 33

m = 2^r

Question 34

set-associative mapping: relationship

Answer 34

m = v.k, i = j mod v - m = number lines of cache - v = number of sets - k = number of lines per set - i = cache set number - j = main memory block memory

Question 35

k-way set associative mapping: number of sets

Answer 35

v = 2^d

Question 36

k-way set associative mapping: number of lines in set

Answer 36

k

Question 37

k-way set associative mapping: total lines in cache

Answer 37

m = k.v = k.2^d

Question 38

k-way set associative mapping: tag size

Answer 38

s - d

Question 39

write back cache & write through cache equation

Answer 39

N x Twt >= Twb - N = how many writes must occur for a write-back (WB) cache to outperform a write-through (WT) cache

Question 40

external memory: transfer time

Answer 40

T = b/rN - b = number of bytes to be transferred - N = number of bytes per track - r = revolutions per second

Question 41

external memory: one full rotation

Answer 41

1/r

Question 42

external memory: average rotational delay

Answer 42

1/2r

Question 43

external memory: total read/write time

Answer 43

Ttotal = Ts + 1/2r + b/rN - Ts = seek time - 1/2r = average rotational delay - b/rN = transfer time

Question 44

MIPSe

Answer 44

MIPSr = f x IPC - f = clock frequency - IPC = instructions per cycle

Question 45

speedup in multicore

Answer 45

speedup(N) = 1/((1-f) + f/N) - f = fraction of the program that is parallelisable - N = number of cores