FS19

2. Verilog

a)

• a “two-bit” flip-flop does not exist. It’s just two flip-flops.
• do not forget to state “active-low as the code resets if the reset signal is low”

b)

Sequential circuit “as all the left-hand side signals are not assigned in every possible condition”. For ex, data_out[0] not assigned foor mask = 0.

c)

State “NOT syntactically correct”

• if something has multtiple assigns, it has multiple drivers, which is wrong.

3. FSMs

b), c)

DO NOT forget to give an equation for O[0] = ... the output!!!!

→ make sure to clearly state what NS, S are, etc…

ISA vs. uArch

physical page size not in ISA! only the layout of the entries, for the page table walkers…

5. Performance Eval

b)

MIPS = million instructions per second.

$$\text{MIPS}=\frac{\text{freq}}{\text{CPI}}$$

so for 600MHz with CPI = 3 $\text{MIPS}=\frac{600MHz}{3\cdot 10^6}=200$.

c)

Make sure to properly account for the +50% of instrs needed to encode it into processor B code.

Then $T=N_{\text{instrs}}\ast CPI\ast \frac{1}{freq}$.

6. Pipeline Rev. Eng.

c)

No, we cannot reduce exec. time with more ports → more ports does not mean that we can have multiple instrs. in W or M at the same time.
→ no stall cycle reduction.

d)

say “any other forwarding is unkown”.

e)

Possible to run using more forwarding paths?

State → “No. All instructions that stall due to data dependency already use the best possible forwarding.”

f)

Internal register forwarding?

Yes W→ ID (or W → EX for delay 2).
“Instruction 6 can finish decode by reading R4 in the second half of the cycle in the same cycle that it’s written.”

g)

→ Make sure to explain the changes in the box, not only put the new instructions in!

7. Tomasulo’s

Latency of ALU and memory unit:

• This refers to the Execution time, so how many cycles EX takes!
  • 2 not 5, 10 not 13 (without the F, D, W)

Numbers of entries in each RS:

• the decode is only executed (before it stalls) once the second instruction goes into W → two entries per RS
• make sure to count this separately for each instruction type

Data forwarding?

• NO!

8. Systolic Arrays

Notice the shape 3x4

• Each element of the convolution kernel is multiplied with 4 of the matrix
  ⇒ Matrix is fed block-wise into the top
  ⇒ convolution kernels each get one row

We have to stagger them, so all data is available when they arrive.

9. GPUs and SIMD

for (i = 0; i < 1026; i++) {
	if (A[i] < 33) // instr 1
		B[i] = A[i] << 1; // instr 2
	if (A[i] > 33) // instr 3
		B[i] = A[i] >> 1; // instr 4
}

a)

Warps = $\lceil \frac{\#\text{threads}}{\text{warp size}}\rceil$

33 warps = 32 with 32 threads, 1 with 2 threads.

b)

Maximum possible → we want the fraction “threads doing shit”/“threads * warps * instructions” to be maximal.

so we want to have the

• 32 full warps to do as much as possible
• 1 warp with 2 to do as little as possible

$$\text{util}=\frac{1026+32\ast 32+1026}{1056+1024+1056}$$

this is split by instruction, counting threads:

• isntr 1:
  • 1026 = 32*32+2 → all 1026 threads execute the first
• instr 2 / 4:
  • 1024 = 32*32 → only the 32 first warps to 2 or 4
• instr 3:
  • 1026 = 32*32 + 2 → all 1026 do the last instr
    and this is out of a maximum of:
• instr 1, 3:
  • 1056 = 32*33 i.e. 33 full warps
• instr 2 or 4:
  • 1024 = 32*32 as only the first 32 warps actually get there
    • so no cycles wasted for the last warp

the 32 warps execute 1, 3 and either 2 or 4 as a block (so for each warp choose either 2 or 4, i.e. A[i] < / > 33, but no mix).
The final warp should do as little as possible, so only execute 1 and 4 → A[i] = 33.

c)

What needs to be true about A for this to happen: (3 cases)

• for the first 1024, every consecutive 32 elements of A
  • every element either < 33 OR > 33 (not mixed)
• for the last two:
  • A[i] = 33

d)

Minimum utilisation:

• each warp executes all 4
  • so mix of < 33, > 33.
• last warp executes all 4:
  • exactly 1 < 33 and 1 > 33

this gives $\text{util}=\frac{1026+1\ast 33+1026+1\ast 33}{32\ast 33+32\ast 33+32\ast 33}$

e)

for every consecutive 32 elements of A for the first 1024:

• A[i] < 33 for one, > 33 for another, the rest should be = 33.
  last 2 elements:
• A[1024] > 33, A[1025] < 33 so exactly a mix.

10. Rev. Eng. Caches

Note: the 1 means 1.0 cache hit rate, so 8/8.

a) Block Size

(8. 16,32, 64 or 128B)

Notice that seq. 1 has 3/8.

Compute the hit rate for all different block sizes, then see which matches.

b) Cache Associativity

(1,2,3,4 or 8 way assoc.)

Block number = bytes address / block size.

Notice that regardless of cache-size or assoc. 0, 8192 16384 and 32768 map to set 0. Let $S=\#\text{ of sets}$.

• $0/64B\mathrm{mod}S=0$

• $8192/64B\mathrm{mod}S=0$

• $16384/64B\mathrm{mod}S=0$

• $32768/64B\mathrm{mod}S=0$.

• 64 does not map to set 0 (set 1)

• 4096 maps to either 0 or 1 depending on # sets.

  • for cache-size 8192B and 1-way, it maps to set 64
  • for all other configs, it’s set 0.

>= 3:

• 16384 is a hit at end of seq. 1 so it must contain {0, 8192, 16384} at least (4096 is open)
  ⇐ 4:
• Because 8192 is not a hit at the end of seq. 2, 4096 must have been set 0 and it’s associativity has to be >= 3, so it’s 4 but ⇐ 4.

c)

(4KB or 8KB)

We now know block size = 64B and 4-way assoc.

Look at Seq. 3.

• 4096 is a hit, so 3072 and 1024 could not have been mapped to → set 0.

for 4-way and 64B block size, we would have

• 4KB cache size →
  • $4096/64B/4-way=16$ sets
  • $8192/64B/4-way=32$ sets

So 3072 and 1024 would map to →

• $1024/64\mathrm{mod}16=0$, mod 32 = 16
• $3072/64\mathrm{mod}16=0$, mod 32 = 16.
  As 4096 is a hit, they must have mapped to set 16 → thus size = 8192KB.

d)

(LRU or FIFO)

8192 is a miss in seq. 2, so let’s look at FIFO vs. LRU:

FIFO for set 0

• seq. 1 end $\{0,8192,16384,4096\}$
• then seq. 2 :
  • on insertion of 32768: $\{8192,16384,4096,32768\}$
  • 0 is inserted back $\{16384,4096,32768,0\}$
• thus it’s consistent with 8192 miss

LRU for set 0:

• seq 1. end from LRU, MRU $\{0,4096,8192,16384\}$
• seq 2.
  • $\{4096,8192,16384,32768\}$
  • $\{8192,16384,32768,0\}$
• but then 8192 would not have been a miss!

Thus the cache must be FIFO.

Branch Prediction

a)

Lead-In

There is always a NN lead-in to take into account.
This makes sure we have something to index the first branch with.

We have TTT…NT, so prepend the NN lead in. Then we have NN → T, NT → T, etc…

b)

We don’t have to give a value for all entries of the PHT → only those actually taken in the steady state branch history.