FS23

2

2 Designing an FSM

→ Arrow from state C is wrong, I need to be careful to correctly consider the NS after a 0 from C.

State C is “seen 00”, thus another 0 puts us in C again.

5 Memory Potpourri

Note: Memory Stuff:

• SRAM = 6T cross coupled
• DRAM = 1 transistor + capacitor
• PCM (phase change memory) = stores a bit in the resistance of a “chalcogenide alloy”, used in Optane
  • material has two stable phases: amorphous and crystalline
  • non-volatile as stable at room-temp
  • writing is done by heating element
    • SET: short pulse → melts material (600 deg) then quenched so it freezes amorphous
    • RESET: longer low amplitude pulse melts → anneals → crystallizes
  • reading uses small current that senses resistance
  • → writing takes much longer than reading

SHORT: SRAM trades area for speed, DRAM trades speed for density, PCM trades write cost and endurance for density and non-volatility.

SRAM is commonly used as a main memory is modern computers
→ FALSE, that’s DRAM

A DRAM cells requires larger power to store data compared to an SRAM cell.
→ FALSE, DRAM uses less power because the cross-coupled inverters leak continously.

Reads are faster than writes in DRAM:
→ FALSE, both require row activation, sensing and precharge.

Reads are faster than writes in PCM
→ TRUE

A bitline in a DRAM array connects all cells in a DRAM to the row decoder
→ FALSE, a wordline connects all cells in a row, a bitline all cells in a column

Using Virtual Memory reduces memory access latency
→ FALSE, it’s for abstraction, it would only increase due to translation overhead

PCM non volatile
→ TRUE

If a hypothetical system is not constrained by chip area, memory cost and energy consumption, PCM would be the best memory technology to use
→ FALSE, PCM wins on chip area, cost and energy consumption. It loses on latency, writer endurance and write energy per bit.

Program with streaming memory access pattern leads to very high temporal locality in the last level cache
→ FALSE, it would be spatial locality, not temporal!

In DRAM, access to different rows in one bank can be serviced faster compared to accesses to different rows in different banks.
→ FALSE, same row would be faster.

A page fault happens when the TLB does not contain the entry needed by an instruction.
→ FALSE, it would only be a TLB miss. Only if the page is on disk, not in memory is it a page fault → major latency
TLB miss = sufficient, but not necessary for page fault

A fully associative cache that only stores 4KB virtual-to-physical mappings has 1024 entries can cover up to 4MB of memory.
→ TRUE

6 Performance Evaluation

d)

I made a mistake while reading, the real CPI of LSU is higher. Thus ALU wins.

7 Pipelining

a)

E3 → E1 forwarding and M → E1 forwarding.
We can see this in cycle 6:

• R1 is forwarded from MEM/WB register to E1 of instruction 4
• R2 is forwarded from EX/MEM register to E1 of instruction 4

b)

R1 = 1024 after 8 iterations of the loop. The first time MUL R4, R1, R1 is fetched we have clock cycle = 3.

• Then at clock cycle 12 it’s fetched the second time. Thus the first loop takes 9 cycles.

We can now fill out the pipeline for the instructions in the second loop. After 10 cycles, the next MUL starts

• note, we could start it’s F stage earlier, but then we’d stall 4 NOPs. So we delay it by another 2 to get a repeating pattern with 2 NOPs
  Thus it takes 10 iterations to complete the loop once.

So the first iteration takes 12 cycles and the next 7 take 10.
$T=12+7\cdot 10=82$.

c)

Calculate the value of $N$, the total number of dynamic instructions fetched by the clock cycle $T$.

Each iteration takes 6 instructions. So $N=2+8\ast 6+1=51$.

e)

It takes 100 cycles to complete the code (final JNZ).

It iterates 9 times in total and we know:

• first iteration = 12
• 8 next ones take 10 each
• no branch prediction penalty
• then there is a final MUL R1, R1, R1 instruction, which stalls twice + 7 stages
  • it’s fetched at cycle 92, so it needs 8 more cycles to complete ( 6 stages + 2 NOPs)

$T=12+8\cdot 10+8=92+8=100$.

8 Vector Processing

a)

Minimum number of banks to avoid stalls while executing a VLD or VST instruction.
Calculate for every stride from 1 to 10.

Latency = 100 for row miss, 50 for row hit.

Worst case we access new elements, so the row is not loaded in yet. Thus we have to be able to carry out 100 memory accesses at least, without reading twice from the same bank.

• each bank has 64 bits row buffer → 2 x 4 byte vector element (64 bits = 8 bytes).
• even we have some hits, due to the miss latency we need to compensate.

So we need $N/\gcd (N,s)$ the number of accesses after which we get a repeat to be $\ge 100$!

• $b_k=(B_0+kS)\mathrm{mod}N$ gives us the bank of access $k$.
• What is the smallest gap in the cycles between two accesses that hit the same bank → reuse distance
• If reuse distance $d\ge 100$, bank is always free, otherwise we stall

So access $k$ and $k^{\prime }$ collide when $b_k=b_k^{\prime }⟹kS\equiv k^{\prime }S\mathrm{mod}N$. Then $(k-k^{\prime })S\equiv 0\mathrm{mod}N$ and thus we are asking for the smallest $d>0$ with $dS\equiv 0\mathrm{mod}N$ → we need $d\ge 100$.
→ we need to find $N$ s.t. $d\ge 100$

• $N|dS$ with $g=\gcd (S,N)$
• We factor out $g$ and get $S=g{s}^{\prime }$ and $N=g{n}^{\prime }$
• thus $g{n}^{\prime }|dg{s}^{\prime }⟹n^{\prime }|d{s}^{\prime }$ with $\gcd (n^{\prime }s,s^{\prime })=1$
• thus $n^{\prime }|d$ and the smallest positive such $d$ is $n^{\prime }$ itself:

$$d=\frac{N}{g}=\frac{N}{\gcd (S,N)}\ge 100$$

So we need to chose $N$!
Ex: stride = 2. $\gcd (N,2)$, for $N/\gcd (N,2)\ge 100$. So we choose an odd value 101 (which is also prime), then $\gcd (101,2)=1$ and $101/1=100\ge 100$.

Even stride: we need 101 banks For ex: stride 2 gives us memory banks 0, 2, 4, …, 96, 98, 100, (as 100 + 1 = 0, 100 + 2 = 1) 1, 3, … 97, 99,

• so after 100 we cycle around for even numbers

Odd stride: we need 100 banks. For ex: stride 1 gives us 0, 1, 2, 3, …, 99, so we loop around after exactly 100 loads.

b)

Assembly to vector instructions.

Note: we can load whole vectors and set the $V_{ln}$ like it’s nothing. Then we just process all the elements at once, using VCOMPZ for branching.

We then invert the mask with VNOT and do the other opterations.

c)

$V_{st}=1$, so we get MISS, HIT, MISS, HIT for the row banks (first one loads the row, second in the row, loop).
We load $46$ elements from a total of $8$ banks.

Thus it takes $3\cdot 100+3\cdot 50=450$ cycles per bank to finish.
→ the final two banks have less accesses, thus finish early

• then it takes $450+5$ cycles until we’re done (5 because that’s when we first access bank 5).

Thus we get 1822 in total from the actual instructions.

9. VLIW

Do not put the store in the load bank lol!

10. Cache

I correctly reverse engineered, but I choose $0\to 4$ instead of $0\to 2$.
both work:

• sets = 1, ways = 4:
  • both 0 and 2 are hits, as the set is just $\{0,2,4\}$ and is kept that way
• sets = 2, ways = 2
  • after $0\to 2\to 4$ we have $\{2,4\}$ in set 1 and $\varnothing$ for the other
  • $0$ is a miss, then that displaces $2$.
  • $2$ is thus also a miss.
• sets = 4, ways = 1
  • after $0\to 2\to 4$ we have $\{4\},\varnothing ,\{2\},\varnothing$
    • as $0$ is evicted by $4$
  • then $0$ is a miss, and evicts the 4 again
  • $2$ is a hit.

11. Systolic Array

b)

For a 4x4 matrix, we cannot just compute 4 2x2 tiles, since they interact!

Instead we reuse the systolic array and do 4 times 2x2 tiles, but we need to shift through the entire 4x1 column of A and 1x4 row of B.

Thus one tile takes 6 until C11 is complete and then we can start again after 4. So $4\cdot 4+2$ in the end $=18$.