Question 4 of 6

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) The 6-instruction sequence above with its register reads/writes. (b) PC (4mm², 100ms/phase = 20ms sequential + 80ms parallelizable), SC (1mm², half PC's speed), AC (1.5mm², 1.5× PC's speed, parallel-only), area budget 4mm², at least one PC or SC required.

Find. (a) every RAW/WAR/WAW hazard, labelled by instruction pair and register. (b) the fastest valid core configuration and its execution time, with all valid configurations' times shown.

Approach. (a) track, for every register, the most recent write and the set of reads since that write, then classify each new access against that history. (b) treat the sequential 20ms as running on exactly one PC-or-SC core alone, and the parallelizable 80ms as running on the combined throughput of every core present (Amdahl-style), then enumerate every area-feasible core combination.

1. Part (a) — dependency analysis. Tracking each register's write/read history instruction-by-instruction:

   Register	Written by	Read by	Dependencies
   r9	L0	L5	RAW(L0,L5,r9)
   r8	L1, L4	L2, L3, L4, L5	RAW(L1,L2,r8); RAW(L1,L3,r8); RAW(L1,L4,r8); WAR(L2,L4,r8); WAR(L3,L4,r8); WAW(L1,L4,r8); RAW(L4,L5,r8)
   r7	L2	L3	RAW(L2,L3,r7)

   Reading this out: L1 writes r8 and L2/L3/L4 all subsequently read or rewrite it before it changes again — three RAWs on r8. L2 and L3 both read r8 before L4 overwrites it, so L4's write must not complete ahead of those reads — two WARs on r8. L1 and L4 both write r8 with nothing else writing it in between — one WAW. L2 writes r7, consumed once by L3 — one RAW on r7. L0 writes r9, consumed only at the loop-exit test L5 — one RAW on r9. Nine hazards total: six RAW, two WAR, one WAW (see table) — all reusing r8, r7, or r9, the only three registers this snippet touches. (Since L5 branches back to L2, the same RAW(L4,L2,r8) pattern also recurs across loop iterations, but the table above lists every hazard within one static pass, which is what the question asks for.)
2. Part (b) — snowplow core configuration. Model each phase as a mandatory sequential slice (20ms of PC-equivalent work) that must run on a single PC-or-SC core, followed by a parallelizable slice (80ms of PC-equivalent work) that all present cores tackle together at their combined rate (no overhead, per the question). Throughput per core, in PC-equivalents: PC $=1.0$, SC $=0.5$, AC $=1.5$. Since 1 PC alone already consumes the entire 4mm² budget, a PC can never be combined with anything else; every other configuration needs exactly one SC to do the sequential part (an AC cannot run it), with any remaining SCs/ACs added to the parallel-phase throughput once the sequential slice finishes: $$t(n_{SC},n_{AC})=\underbrace{\frac{20\text{ms}}{0.5}}_{\text{sequential, on 1 SC}}+\underbrace{\frac{80\text{ms}}{0.5n_{SC}+1.5n_{AC}}}_{\text{parallel, all cores combined}}=40\text{ms}+\frac{80\text{ms}}{0.5n_{SC}+1.5n_{AC}}$$ Enumerating every combination with area $n_{SC}(1)+n_{AC}(1.5)\le4$mm² and $n_{SC}\ge1$, plus the standalone-PC case:

   Configuration	Area (mm²)	Time
   1 PC	4.0	100.0 ms
   1 SC	1.0	200.0 ms
   2 SC	2.0	120.0 ms
   3 SC	3.0	93.3 ms
   4 SC	4.0	80.0 ms
   1 SC + 1 AC	2.5	80.0 ms
   2 SC + 1 AC	3.5	72.0 ms
   1 SC + 2 AC	4.0	$\boxed{62.9\text{ ms}}$

   The winner uses the full 4mm² budget as 1 SC + 2 AC: $t=40+80/3.5=40+22.857\approx\boxed{62.9\text{ ms}}$, over 37% faster than a lone PC. This is the fastest because AC delivers the most parallel throughput per mm² (1.5 speed / 1.5 mm² $=1.0$/mm²) of any option, so once the one mandatory SC is placed, every remaining mm² of budget should buy AC throughput rather than more SC or a PC.