Midterm — Spring 2024

Midterm — Spring 2024

EECS 4340 · Spring 2024

Historically numbered as EECS 4824.

Question 1 12 pts

In-Order Pipelines. A processor has expected CPI = 1 for programs with no hazards. Caches remove the structural memory hazard. Branches are converted to predication, removing the control hazard. For each program, measure expected CPI.

Load (%)	Store (%)	ALU (%)	% of all instructions dependent on the instruction in front of them	Expected CPI
15	15	70	10	?
25	25	50	20	?
40	40	20	30	?

Only a load followed immediately by a dependent instruction causes the remaining one-cycle load-use stall (a RAW hazard not coverable by forwarding). Therefore:

Expected CPI = 1 + LoadFraction * DependentFraction * 1-cycle stall

Load fraction	Dependent fraction	CPI calculation	Expected CPI
0.15	0.10	1 + 0.15 * 0.10	1.015
0.25	0.20	1 + 0.25 * 0.20	1.05
0.40	0.30	1 + 0.40 * 0.30	1.12

Verified correct

Correct. With caches eliminating the structural memory hazard and predication eliminating control hazards, the only remaining stall source on a classic 5-stage in-order pipeline is the load-use slot: a load’s value is not available until the end of MEM, so a dependent consumer in the immediately following slot must stall exactly one cycle (forwarding from MEM/WB → EX covers everything beyond the next-cycle case). The probability of this event per instruction is LoadFraction × DependentFraction, yielding the additive penalty Load × Dep × 1 over the no-hazard baseline of CPI = 1. The three results 1.015, 1.05, and 1.12 follow directly.

L03 · p.5L03 · p.43

Question 2(a) 4 pts

Instruction-Level Parallelism. Given the instruction sequence:

I1: R2 = R6 + R3
I2: R1 = R7 + R3
I3: R2 = R5 * R4
I4: R1 = R4 + R6
I5: R2 = R2 + 1
I6: R5 = R7 + R2
I7: R1 = R3 * R2

List all RAW, WAW, and WAR hazards.

Hazard type	Hazards
RAW	I3 -> I5, I5 -> I6, I5 -> I7
WAW	I1 -> I3, I2 -> I4, I3 -> I5, I4 -> I7
WAR	I3 -> I6

Verified correct

Correct minimal set. RAW edges are exactly the producer → first consumer pairs for live values: I3 writes R2 read by I5; I5 writes R2 read by I6 and I7. WAW edges connect consecutive writers of the same architectural register (R2: I1→I3→I5; R1: I2→I4→I7). WAR is I3 (write R2) after I6 reads R2 — wait, actually the listed direction I3 -> I6 reflects the program-order anti-dependence on R5: I3 reads R5 and I6 later writes R5, so the edge from I3 to I6 enforces “I3’s read of R5 must complete before I6’s write of R5.” That is the standard WAR ordering edge. (Some textbooks would also list R3 reads, but those registers are never overwritten, so no further WAW or WAR edges arise.)

Question 2(b) 4 pts

For scoreboard scheduling, draw the control-flow graph: explicit checks/stalls are needed for RAW, WAW, and WAR hazards.

Edge list:

I1 -> I3
I3 -> I5
I5 -> I6
I5 -> I7
I2 -> I4
I4 -> I7
I3 -> I6

One way to view the graph:

I1 -> I3 -> I5 -> I6
            \
             -> I7
I2 -> I4 --------^
I3 -> I6   (WAR edge)

Verified correct

Correct. Scoreboarding does not perform register renaming, so it must enforce all three hazard classes with explicit interlocks: RAW (issue waits for the producing functional unit to write the operand back), WAW (issue waits if any earlier in-flight instruction will write the same destination), and WAR (write-back waits if an earlier instruction has not yet read its source). The seven edges listed are exactly the union of the three hazard sets from 2(a), so the graph is consistent with that part.

Question 2(c) 3 pts

What is the ILP for scoreboard scheduling with infinite resources?

Longest dependence chain length is 4 instructions, e.g.:

I1 -> I3 -> I5 -> I6

So:

ILP = total instructions / critical path length = 7 / 4 = 1.75

Verified correct

Correct. With infinite functional units, the steady-state throughput is bounded by the longest path in the dependence graph from 2(b). The chain I1 → I3 → I5 → I6 has length 4 (four instructions on the critical path); the equally long alternate chain I1 → I3 → I5 → I7 also has length 4. Ideal ILP = N / critical path = 7 / 4 = 1.75 instructions per cycle.

Question 2(d) 4 pts

Draw the dependence graph for Tomasulo scheduling. With Tomasulo / register renaming, WAW and WAR false dependences are removed; only RAW dependences remain.

Edge list:

I3 -> I5
I5 -> I6
I5 -> I7

Graph:

I1    I2    I4    independent
I3 -> I5 -> I6
       \
        -> I7

Verified correct

Correct. Tomasulo’s algorithm uses reservation stations and the common data bus to implement implicit register renaming, which removes WAW and WAR (name) dependences entirely. Only true RAW (data-flow) dependences remain. The three RAW edges from 2(a) are exactly the edges shown; I1, I2, and I4 become roots with no outgoing edges into a longer chain because their writes are renamed away.

Question 2(e) 3 pts

What is the ILP for Tomasulo scheduling with infinite resources?

Longest RAW chain length is 3 instructions:

I3 -> I5 -> I6

or:

I3 -> I5 -> I7

So:

ILP = 7 / 3 ~= 2.333

Verified correct

Correct. Once name dependences are renamed away, only the RAW chains in 2(d) constrain the schedule. Both I3 → I5 → I6 and I3 → I5 → I7 have length 3; I1, I2, I4 are independent and can issue in cycle 1. Ideal Tomasulo ILP = 7 / 3 ≈ 2.333 IPC, a clear improvement over scoreboarding (1.75) precisely because the WAW/WAR edges that lengthened the critical path in 2(b) no longer exist.

Question 3(i) 5 pts

Finite State Machines. The provided SystemVerilog module implements a 2-bit saturating-counter branch predictor. The states are:

STRONGLY_NOT_TAKEN = 2'b00
WEAKLY_NOT_TAKEN   = 2'b01
WEAKLY_TAKEN       = 2'b10
STRONGLY_TAKEN     = 2'b11

predict_taken is 1 in the weakly-taken or strongly-taken states. Draw the FSM diagram.

States and outputs:

State	Encoding	Output predict_taken
Strongly not taken	00	0
Weakly not taken	01	0
Weakly taken	10	1
Strongly taken	11	1

Transitions:

Current state	If branch_taken = 0	If branch_taken = 1
Strongly not taken	Strongly not taken	Weakly not taken
Weakly not taken	Strongly not taken	Weakly taken
Weakly taken	Weakly not taken	Strongly taken
Strongly taken	Weakly taken	Strongly taken

Reset goes to strongly not taken.

Mermaid diagram equivalent:

stateDiagram-v2
    [*] --> SNT: reset
    SNT: Strongly Not Taken / output 0
    WNT: Weakly Not Taken / output 0
    WT: Weakly Taken / output 1
    ST: Strongly Taken / output 1

    SNT --> SNT: 0
    SNT --> WNT: 1
    WNT --> SNT: 0
    WNT --> WT: 1
    WT --> WNT: 0
    WT --> ST: 1
    ST --> WT: 0
    ST --> ST: 1

Verified correct

Correct. This is the textbook 2-bit saturating counter used as a per-PC entry in a BHT: increment toward 11 on branch_taken=1, decrement toward 00 on branch_taken=0, saturating at the endpoints. The output is the high bit of the counter — predict_taken = state[1] — which is 0 for 00/01 and 1 for 10/11. The hysteresis is the whole point: a single misprediction from STRONGLY_TAKEN only drops to WEAKLY_TAKEN (still predicting taken), so a one-off not-taken outcome inside a mostly-taken loop does not flip the prediction polarity. Reset to STRONGLY_NOT_TAKEN (00) is a conservative initialization.

Question 3(ii) 5 pts ⚠ OCR

Complete the timing diagram for the 2-bit saturating counter branch predictor given the supplied reset and branch_taken waveform.

The handwritten counter-state sequence is:

XX -> 00 -> 00 -> 01 -> 10 -> 11 -> 10 -> 01

predict_taken is 1 when the counter state is 10 or 11, and 0 otherwise.

Best interpretation

Reading the handwritten waveform: before reset deasserts, the counter is unknown (XX). Reset clamps it to STRONGLY_NOT_TAKEN (00). Each subsequent rising edge of the clock advances the state per the FSM in 3(i) using that cycle’s branch_taken:

Cycle	branch_taken	Next state	predict_taken
reset	—	00	0
1	0	00	0
2	1	01	0
3	1	10	1
4	1	11	1
5	0	10	1
6	0	01	0

So the state trace is XX → 00 → 00 → 01 → 10 → 11 → 10 → 01, and predict_taken is high only while the state is 10 or 11, matching the 2-bit counter semantics.

Verified correct

Correct for the inferred branch_taken pattern 0,1,1,1,0,0. The trace exhibits the saturating behavior: the counter climbs 00 → 01 → 10 → 11 on three consecutive taken outcomes, then walks back 11 → 10 → 01 on two not-taken outcomes. predict_taken flips high one cycle after entering 10 and stays high through 11 until the counter falls back to 01.

Question 4(a) 5 pts

Performance. A program has 20% sequential and 80% parallel work. An accelerator speeds up the parallel part by 4x. Compute the overall speedup.

Using Amdahl’s law:

Speedup = 1 / (sequential_fraction + parallel_fraction / accelerator_speedup)
        = 1 / (0.2 + 0.8 / 4)
        = 1 / 0.4
        = 2.5x

As percent improvement over baseline:

(2.5 - 1) * 100% = 150% faster

Verified with caveat

The arithmetic is correct: $S = 1 / ((1-f) + f/k) = 1/(0.2 + 0.8/4) = 2.5\times$. The wording “150% faster” is correct only as percent improvement over baseline (i.e., new throughput is $1 + 1.5 = 2.5\times$ the old). It is not the same as a speedup factor of 1.5x, which is a common misreading. Per the source’s own verification summary, prefer reporting the speedup factor 2.5x and only switch to 150% when explicitly asked for percent improvement.

L03 · p.5

Question 4(b) 5 pts

A program has 40% sequential and 60% parallel work. An accelerator speeds up the parallel part by 6x. Compute the overall speedup.

Speedup = 1 / (0.4 + 0.6 / 6)
        = 1 / 0.5
        = 2.0x

As percent improvement over baseline:

(2.0 - 1) * 100% = 100% faster

Verified with caveat

Correct arithmetic: $S = 1/(0.4 + 0.6/6) = 1/0.5 = 2.0\times$. Same wording caveat as 4(a): “100% faster” means “twice as fast” (a 2x speedup), not a 1x speedup. The right way to report this is 2.0x speedup or 100% improvement over baseline, never “100% speedup” with no qualifier.

L03 · p.5

Question 4(c) 5 pts

Which program has better area computing efficiency? Assumptions:

• Both programs have the same baseline area without accelerators.
• Accelerator A gives 2.5x speedup with 150% area increase, so total area is 2.5x baseline.
• Accelerator B gives 2.0x speedup with 100% area increase, so total area is 2.0x baseline.

Area computing efficiency can be compared as:

ACE = speedup / area_factor

For program A:

ACE_A = 2.5 / 2.5 = 1

For program B:

ACE_B = 2.0 / 2.0 = 1

Answer: Programs A and B have the same area computing efficiency.

Verified correct

Correct given the stated area model. Defining area-computing-efficiency as speedup ÷ (total area / baseline area) cancels the numerator and denominator in both cases — A: 2.5/2.5 = 1, B: 2.0/2.0 = 1 — so the two designs are tied on this specific metric. Caveat: if the baseline core itself were excluded from “area” (i.e., dividing by just the accelerator’s added area of 1.5x and 1.0x respectively), A would yield 2.5/1.5 ≈ 1.67 and B would yield 2.0/1.0 = 2.0, making B better. The conclusion is therefore sensitive to whether the baseline core is included in the area denominator; the answer above adopts the inclusive definition stated in the problem.

L03 · p.5