25-Comp-A3 Computer Architecture, December 2017, Q4

Question 4 (15 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) a single ten-line listing I0–I4 then I0a–I4a on registers $0/$2/$3/$5 — a dynamic trace of two passes through one loop body (I4's always-taken branch targets label L, which is I0a; I3a's branch targets label E, which is I4a), the a suffix marking the second pass. (b) L1: 3-cycle latency, 96% hit rate; main memory: 80-cycle latency; proposed L2: 12-cycle latency, accessed serially on every L1 miss before main memory.

Find. (a) every RAW/WAR/WAW register dependency across the whole ten-instruction trace. (b) the minimum L2 hit rate that makes the two-level hierarchy beat the L1-only average memory access time (AMAT).

Approach. (a) walk the trace in program order keeping, per register, its last writer and the list of readers since that write: each read yields RAW(last writer, reader), and each write yields WAW(last writer, writer) plus a WAR from every reader accumulated since that write. (b) write the AMAT formula for L1-only and for L1+L2 (serial access on miss) and solve the inequality for the L2 hit rate.

Part (a) — dependency analysis. The ten lines are one listing, not two independent programs. I4 is beq $0, $0, L — an always-taken branch to label L — and the very next line, I0a, carries that label; likewise I3a's beq $3, $5, E targets label E, which is I4a. The paper is therefore printing a dynamic trace of two passes through one loop body, the a suffix marking the second pass. That reading is what makes the question answerable as asked: within a single pass each of $2 and $3 is written exactly once, so one pass on its own carries no WAR and no WAW whatsoever — the anti- and output dependencies the question explicitly asks for exist only across the pass boundary, which is precisely why the second pass is printed.
  Walk the trace in program order, tracking for each register its last writer and every reader since that write. $0 is the hard-wired zero register and is never written; $5 is read by I3 and I3a but never written anywhere in the trace — neither contributes a dependency.
  Register $2 is written by I0 and rewritten by I0a. I0's value is read by I1, by I2, and by I0a itself (lw $2, 0($2) reads $2 to form its address before writing it) → RAW(I0, I1, $2), RAW(I0, I2, $2), RAW(I0, I0a, $2). I0a's write then lands after those reads and after I0's own write → WAR(I1, I0a, $2), WAR(I2, I0a, $2), WAW(I0, I0a, $2). I0a's new value is read by I1a, I2a and I4a (the store's data operand) → RAW(I0a, I1a, $2), RAW(I0a, I2a, $2), RAW(I0a, I4a, $2).
  Register $3 is written by I2 and rewritten by I2a. I2's value is read by I3 → RAW(I2, I3, $3). I2a's write follows that read and I2's write → WAR(I3, I2a, $3), WAW(I2, I2a, $3). I2a's new value is read by I3a and by I4a (the store's base-address operand) → RAW(I2a, I3a, $3), RAW(I2a, I4a, $3).
  A store never writes a register, so I4a can only ever be the target of a RAW, never its source. The complete answer is nine RAW, three WAR and two WAW — fourteen dependencies in total:

All register dependencies in the printed I0–I4a trace
Type	Dependencies, given as (x, y, rz)
RAW — 9	(I0, I1, `$2`); (I0, I2, `$2`); (I0, I0a, `$2`); (I2, I3, `$3`); (I0a, I1a, `$2`); (I0a, I2a, `$2`); (I0a, I4a, `$2`); (I2a, I3a, `$3`); (I2a, I4a, `$3`)
WAR — 3	(I1, I0a, `$2`); (I2, I0a, `$2`); (I3, I2a, `$3`)
WAW — 2	(I0, I0a, `$2`); (I2, I2a, `$3`)

The three WAR and two WAW dependencies all cross the pass boundary; a single pass through the loop body contains none of either.

This set is derived instruction by instruction: each line is encoded as the registers it reads and writes, and a last-writer / readers-since-write walk is run over it.

Check: three readings settled against the printed page. (1) The ten instructions are printed as one uninterrupted column at a single indentation, with no blank line between I4 and I0a, and the repeated L: label is exactly the branch target of I4 — so this is one trace, not two programs. Reading it as two independent blocks would report no WAR and no WAW at all, contradicting what the question asks for. (2) The paper prints I2's comment as # $3 = MEM[$4+4] while the instruction itself is lw $3, 4($2); the instruction governs — the comment's $4 is a typo in the exam paper, and $4 appears nowhere else in the listing — so I2 reads $2, which is what creates RAW(I0, I2, $2) and WAR(I2, I0a, $2). (3) I0 itself also reads $2 before I0a writes it, but that anti-dependence is subsumed by WAW(I0, I0a, $2) because I0 overwrites $2 itself, so it is not listed separately.

Part (b) — required L2 hit rate. The average memory access time (AMAT) with only L1 is the L1 hit latency plus the L1 miss rate times the main-memory penalty: $$\text{AMAT}_{L1}=L1+(1-H_1)\times\text{Mem}=3+(1-0.96)\times80=3+0.04\times80=\boxed{6.2\ \text{cycles}}$$ Adding an L2 that is accessed on every L1 miss, serially, before main memory (per the question's stated assumption — the L2 access is never overlapped with the L1 access or the main-memory access), the AMAT becomes: $$\text{AMAT}_{L1+L2}=L1+(1-H_1)\times\Big(L2+(1-H_2)\times\text{Mem}\Big)$$ Setting $\text{AMAT}_{L1+L2}<\text{AMAT}_{L1}$ and solving for $H_2$: $$3+0.04\times\big(12+(1-H_2)\times80\big) < 6.2$$ $$0.04\times\big(12+(1-H_2)\times80\big) < 3.2\ \Rightarrow\ 12+(1-H_2)\times80 < 80$$ $$(1-H_2)\times80 < 68\ \Rightarrow\ 1-H_2 < 0.85\ \Rightarrow\ \boxed{H_2 > 0.15}$$ So the L2 must be right more than 15% of the time it is consulted. This makes physical sense: even an L2 that never hits at all only costs an extra 12 cycles on every L1 miss (worse than L1-only by $0.04\times12=0.48$ cycles), so a fairly low hit rate is enough to recover that fixed overhead and start saving the far larger 80-cycle main-memory penalty on the fraction of L1 misses the L2 now absorbs.
Check: assumes (i) the L2 access is strictly serial after an L1 miss (never overlapped with L1's own access, as the question states), and (ii) main memory is reached only after an L2 miss, i.e. the L2's own miss penalty is exactly the main-memory latency with no further level.

Final results — Question 4
Part	Result
(a) RAW — 9	(I0,I1,`$2`); (I0,I2,`$2`); (I0,I0a,`$2`); (I2,I3,`$3`); (I0a,I1a,`$2`); (I0a,I2a,`$2`); (I0a,I4a,`$2`); (I2a,I3a,`$3`); (I2a,I4a,`$3`)
(a) WAR — 3	(I1,I0a,`$2`); (I2,I0a,`$2`); (I3,I2a,`$3`)
(a) WAW — 2	(I0,I0a,`$2`); (I2,I2a,`$3`)
(b)	AMAT$_{L1}=6.2$ cycles; need $\boxed{H_2 > 0.15}$ (L2 hit rate above 15%)

Topic: RAW/WAR/WAW dependency classification in straight-line and looping code, and multi-level cache average memory access time (AMAT).

Key relations: RAW(x,y,r): $x$ writes $r$, $y$ (later) reads it; WAR(x,y,r): $x$ reads $r$, $y$ (later) writes it; WAW(x,y,r): $x$ writes $r$, $y$ (later) writes it again; $\text{AMAT}=\text{Hit time}+\text{Miss rate}\times\text{Miss penalty}$, extended per level as $\text{AMAT}_{n}=L_n+(1-H_n)\times\text{AMAT}_{n+1}$.

Why this works: RAW is the only dependency that is fundamental to the DATAFLOW of the program (the value literally does not exist until the write completes); WAR and WAW are artifacts of reusing the same register name and can be removed by renaming, which is precisely why they don't appear when a register is written only once per pass through straight-line code. AMAT decomposes recursively because each cache level is only ever consulted after every faster level above it has already missed, so its access time is unconditionally paid but its penalty is only paid a fraction of the time (its own miss rate).

Common pitfall: reading a printed execution TRACE as two unrelated code blocks — a repeated label is a branch target, not a second program, and splitting the trace there discards every WAR and WAW the question asks for, because those arise only where the second pass rewrites a register the first pass read; mislabeling a store's register reads as a "write" dependency (a store never writes a register, so it can only ever be the target of RAW, never its source); forgetting that adding a cache level costs a small FIXED overhead on every miss from the level above, so its hit rate must clear that overhead before it is worth anything.

Source: Patterson & Hennessy, Computer Organization and Design, 6th ed., Ch.4 (pipeline hazards, dependency types) & Ch.5 (multi-level cache AMAT).

Question 4 of 6

Question 4 (15 marks)