FS22

1. Boolean Logic

c)

We are allowed to use 3-input NOR gates here → then it becomes pretty easy

2. FSM

→ no need to handle the illegal transitions (i.e. non-existant passengers leaving)

3. ISA vs uarch

Number of instructions fetched per cycles → ISA

Instruction “issue width” (number of instrs issued by the pipeline, not the actual
instruction width) → uarch

Size of addressable memory → ISA

Number of read/write ports on physical register file → uarch

4. Verilog

a)

Each hex character is 4 bits, so +: 8 takes the two next chars from the hex values.

in1[base +: width] gives in1[7:0] for base = 0.

Notice that in the code var1 is only two bits wide.

• So on overflow in loop 8, it loops back around → is sent back to 0
• Since en is not activated anymore, it’s just stuck and repeatedly outputs 16

b)

The |in operator gives or reduction. what we want here!

5. Memory Potpourri

A main memory access typically consumes less energy than a register file access
→ TRUE

Building a larger memory array by increasing the length of the array’s wordlines and bitlines increases the cost$, but does not increase the access time
→ FALSE, increases critical path

Activating a DRAM cell temporarily destroys the value stored in the cell
→ TRUE

• DRAM reads are destructive
• Precharge > bitline drive to $V_{DD}/2$ then left floating
• Access → raising wordline turns on the access transistors, connecting the capacitor to the bitline → the two now share charge
  • Charge sharing → cell capacitance is much smaller than bitline cap so bitline get’s perturbed slightly. Cell capacitor is now also V_DD / 2
• Amplification → detects $\Delta V$ and drives bitline all the way to V_DD or 0
• Restor → because wordline is still arsserted, fully driven bitline recharges the cell to original value.

A cache that has block size equal to word size of memory access instructions cannot exploit spatial locality.
→ TRUE

The entire page table is stored in physical memory.
→ FALSE, some parts are stored on disk
Physical memory = RAM here.

7. Pipelining

b)

So only MEM/WB -> EX forwarding.

WHY did I even think there was E3 → D forwarding ???? THat doesn’t even exist, the D stage needs no data.

e)

Note that instruction 3 can “overtake” instruction 2 and also be in E1 because it’s an ADD, while 2 is a MUL → different hardware!!!!!

Then with the correct instruction execute lengths and stuff it gives us 16/13 in speedup.

f)

We can run it faster by forwarding from EX/MEM → EX.
this gets us down to 15 cycles, by saving one wait.

8

8.2.2

Be careful when filling out the instructions from Tomasulos!
They have to be in the order the reservation stations are filled in.

10. Branch Prediction

Pipeline Equation

The Formula for cycles taken is $C=P+I-1+BD$ where

• $C$ means number of cycles
• $P$ means number of pipeline stages
• $I$ means number of (dynamic) instructions
• $B$ means number of conditional branches taken/number of conditional branch instructions executed
• $D$ means number of cycles stalled for each conditional branch

11.

b)

We issue 2K acesses for N = 2. Out of those 1/4 are actually valid.
$\frac{\frac{1}{4}2k}{k}=\frac{1}{2}$ total coverage! Don’t duck up the arithmetics.

c)

We do not count duplicate memory requests going to DRAM.

Thus we issue 2K + K requests, but of those 2K, every second is duplicate.
So A → A+1, A+2, A+1 → A+2, A+3, so out of 2 requests, 3 were issued.
$\frac{\frac{1}{2}K+K}{K}=\frac{3}{2}$.

d)

From A → A+9, A+10 → A+19 we always fetch +8 before it “loops around”.
Do not count the original base address itself → it’s not 9

e)

$\frac{8k+k}{K}=9$ overhead.

12.

a)

Draw out the different cache end-states for each of the ways/sets combinations.
Here with $0\to 9\to 16$ we find the different results.
THen reduce to lowest addresses and find $0\to 8\to 16$.

Make sure to convert from address to block!!!.