Exam trainer

1. Pipelining is an implementation technique that overlaps the execution of consecutive instructions: the execution is divided into stages and each stage works on a different instruction in the same clock cycle. The latency of one instruction does not change (k cycles), but once the pipeline is full one instruction completes per cycle, so the throughput grows by up to k times; n instructions take k + n − 1 cycles instead of nk, and the clock period becomes the time of one stage instead of a whole instruction. Costs: a fill of k − 1 cycles, pipeline-register overhead, and hazards (structural, data, control) that insert stalls.

2. The five stages correspond to five resources used once by every instruction: IF fetches from the instruction memory and computes PC + 4; ID decodes and reads the two source registers (two read ports); EX uses the ALU for the operation, the address or the branch comparison; MEM accesses the data memory (loads and stores only); WB writes the destination register (one write port). Because each stage uses a different resource, five instructions can be in flight without conflicts; every instruction traverses all five stages (idle stages are not skipped), so completion is in order and at most one instruction writes per cycle.

3. The pipeline registers IF/ID, ID/EX, EX/MEM and MEM/WB sit between the stages and are written on every clock edge. They hold everything an in-flight instruction still needs: the instruction and PC + 4 (IF/ID); the operand values, the immediate, the destination register number and the control signals for EX, MEM and WB (ID/EX); the ALU result or address, the store data, the branch target, rd and the MEM/WB control (EX/MEM); the loaded data or ALU result, rd and the WB control (MEM/WB). Benefits: they isolate the stages so that the clock period equals one stage; the control is decoded once and carried along; and they are the source of the values used by forwarding.

4. With a single memory, the instruction fetch of one instruction and the data access of another (IF and MEM of two different instructions in the same cycle) would compete for the memory port: a structural hazard with a stall every time. Separate instruction and data memories (in practice separate L1 caches) give the two stages their own port, so the hazard is designed away. It is a property of the implementation, not of the instruction set.

Total clock cycles = k + n − 1 = 5 + 5 − 1 = 9 (equivalently IC + 4 = 5 + 4 with no stalls); execution time = 9 × 2 ns = 18 ns. Non-pipelined: 5 × 5 = 25 cycles = 50 ns. Speedup of the pipeline = 50 / 18 = 2.78.

Against 1000 ns without the pipeline: a speedup of 1000 / 208 = 4.81.

Stage time = 10 / 10 = 1 ns; clock period = 1 + 0.5 = 1.5 ns. For n → ∞ the pipeline completes one instruction per clock period, so the speedup tends to 10 / 1.5 = 6.67 — not 10.

Answer 2. The pipeline overlaps instructions: the time of one instruction is still k cycles, but a new one completes every cycle once the pipeline is full, so n instructions take k + n − 1 cycles.

Answers 1, 3 and 5.

1. The register file is written in the first half of a clock cycle and read in the second half, so an instruction in WB and an instruction in ID exchange a value within the same cycle. Benefit: a consumer three instructions after its producer needs no stall and no extra datapath; without it a consumer at distance 1, 2 or 3 would pay one more stall. It is the "read and write at the same address in the same cycle" assumption of the exercises.

2. Forwarding (bypassing) feeds a result to a dependent instruction from the pipeline register where it already sits, instead of waiting for WB and a register-file read. EX/EX takes the ALU result from EX/MEM into the ALU input (ALU producer at distance 1); MEM/EX takes a value from MEM/WB into the ALU input (ALU producer at distance 2, or a loaded value); MEM/MEM takes a loaded value from MEM/WB into the data-memory write input (load followed by a store). The forwarding unit compares the destination register numbers in EX/MEM and MEM/WB with the source numbers in ID/EX, gives priority to the newest result and ignores R0. Benefit: all ALU-to-ALU stalls disappear; cost: multiplexers and comparators.

3. A load's value exists only at the end of its MEM stage, so an instruction that uses it immediately would need it in the same cycle: one stall is unavoidable even with forwarding, after which the MEM/EX path delivers the value. The hazard detection unit, in ID, detects the case (the instruction in EX is a load whose destination equals a source the instruction in ID needs in EX; the data register of a store is exempt, since the MEM/MEM path serves it in MEM) and inserts the bubble: it holds the PC and the IF/ID register and zeroes the control signals entering ID/EX. Benefit: correctness with the minimum delay; the compiler can fill the slot with an independent instruction.

4. Static solutions are applied by the compiler: nop insertion (simple, wastes the same cycles as a stall and inflates code and instruction count) and instruction scheduling (fills the gap with independent instructions, free when they exist). Dynamic solutions are applied by the hardware at run time: stalling through interlocks (bubbles, no code growth) and forwarding (the preferred one). Benefit of dynamic solutions: the code is independent of the pipeline depth; benefit of static ones: no detection hardware and the ability to fill slots forwarding cannot remove.

(a) Without forwarding. RAW on R2 (I0 to I1), R3 (I1 to I2) and R5 (I2 to I3), all at distance 1: 2 stalls each. I4 reads R2 and R5 in cycle 12, both already written: 0 stalls.

Stalls = 6; clock cycles = 5 + 4 + 6 = 15 (the cycle of the last WB); CPI = 15 / 5 = 3.0.

(b) With forwarding. I0 to I1 is a load-use pair: 1 stall, then R2 through the MEM/EX path in cycle 5. I1 to I2: EX/EX path in cycle 6, 0 stalls. I2 to I3: R5 forwarded to the store through the EX/EX path in cycle 7, 0 stalls. I4: R5 through the MEM/EX path in cycle 8, R2 from the register file, 0 stalls.

Stalls = 1; clock cycles = 5 + 4 + 1 = 10; CPI = 10 / 5 = 2.0.

(c) Speed-up = 15 / 10 = 1.5 (the CPI drops from 3.0 to 2.0).

Only AND stalls (distance 1 from SUB: 2 stalls); OR is held in IF behind it and reads R2 in cycle 6, after the write in cycle 5; ADD and SD are later still. Clock cycles = IC + 4 + stalls = 5 + 4 + 2 = 11.

Answer 2: 1 stall. The loaded value exists only at the end of the load's MEM stage; the add's EX is delayed one cycle and then takes the value through the MEM/EX path.

Answers 1 and 4. Reads in ID precede any later write in WB and all writes are in order through one WB stage, so WAR and WAW are impossible; split memories remove the IF/MEM conflict; RAW and control hazards remain.

Answer 3: 2 NOPs. Motivation: SUB writes R2 in WB in cycle 5. The consumer at distance \(d\) reads in cycle \(d + 2\); the read must be in cycle 5 or later, so \(d = 3\): two instructions in between. Stalls = max(0, 3 − d) = 0.

CPI1 = 0.3 × 2 + 0.1 × 8 + 0.2 × 2 + 0.3 × 2 + 0.1 × 3 = 0.6 + 0.8 + 0.4 + 0.6 + 0.3 = 2.7

CPI2 = 0.3 × 1 + 0.1 × 6 + 0.2 × 3 + 0.3 × 2 + 0.1 × 3 = 0.3 + 0.6 + 0.6 + 0.6 + 0.3 = 2.4

T_CLK1 = 1 / 500 MHz = 2 ns; T_CLK2 = 1 / 200 MHz = 5 ns.

CPUtime1 = IC × CPI1 × T_CLK1 = 100 × 2.7 × 2 ns = 540 ns; CPUtime2 = 100 × 2.4 × 5 ns = 1200 ns.

CPU1 is faster by the ratio of the execution times: 1200 / 540 = 2.22 times faster, i.e. 122% faster (Perf(CPU1) = (1 + 122/100) × Perf(CPU2)), although its CPI is higher: the clock factor 2.5 outweighs the CPI factor 2.7 / 2.4 = 1.125.

(a) Single iteration: cycles = m + k + 4 = 6 + 2 + 4 = 12; CPI_iter = 12 / 6 = 2.0.

(b) Whole loop: IC = m × n = 1200; clock cycles = n × (m + k) + 4 = 200 × 8 + 4 = 1604 (the fill is paid once).

(c) CPI = 1604 / 1200 = 1.337; CPI_AS = (m + k) / m = 8 / 6 = 1.333.

(d) MIPS_AS = f_CLK / (CPI_AS × 10⁶) = 2000 MHz / 1.333 = 1500 MIPS.

(e) T_CLK = 1 / 2 GHz = 0.5 ns; CPU time = 1604 × 0.5 ns = 802 ns.

Speedup = 1 / ((1 − F) + F / S) = 4 ⇒ (1 − F) + F / 10 = 0.25 ⇒ 1 − 0.9 F = 0.25 ⇒ F = 0.75 / 0.9 = 0.833 (83% of the execution time).

1. CPU time = IC × CPI × T_CLK = IC × CPI / f_CLK: the instructions executed, times the average clock cycles per instruction, times the cycle time. Each factor is set by a different level (compiler and ISA for IC; organisation for CPI; technology and pipeline depth for T_CLK) and they interact (a deeper pipeline shortens the cycle but adds stalls). Benefit: it predicts the effect of a design change and makes execution time, the only reliable metric, computable from measurable factors.

2. Total cycles = Σ CPI_i × I_i; dividing by IC gives CPI = Σ CPI_i × F_i with F_i = I_i / IC the frequency of class i. Benefit: the CPI of a program on a machine from a mix table (e.g. 2.7 vs 2.4), without executing it; it shows which class dominates the time.

3. MIPS = f_CLK / (CPI × 10⁶) = IC / (CPU time × 10⁶): millions of instructions per second. Limits: it depends on the instruction set and on the program, and it ignores the work per instruction, so it can vary inversely with performance (software FP: more instructions, higher MIPS, longer time). It is valid only to compare the same program with the same IC; otherwise compare CPU times.

4. If a fraction F of the original execution time is made S times faster, the new time is ((1 − F) + F / S) × old time and the speedup is 1 / ((1 − F) + F / S), bounded by 1 / (1 − F) as S → ∞. Benefit: it tells where to invest ("make the common case fast") and bounds the return of any single enhancement; e.g. F = 0.4, S = 10 gives 1.56, at most 1.67.

5. In a 5-stage pipeline the first instruction completes in cycle 5 and each following one a cycle later, so IC instructions complete in IC + 4 cycles (the 4 fill cycles are the depth minus one, paid once); each stall cycle delays everything behind it by one cycle: Clock cycles = IC + Stall cycles + 4, CPI = cycles / IC, MIPS = f_CLK / (CPI × 10⁶). It gives the throughput of pipelined code from a cycle table (e.g. 5 instructions, 2 stalls: 11 cycles, CPI 2.2).

6. For a loop of m instructions and k stall cycles per iteration run n times, cycles = n(m + k) + 4 and CPI(n) = 1 + k/m + 4/(mn) → CPI_AS = (m + k)/m = 1 + k/m as n → ∞: the fill becomes negligible and the performance is governed by the stall cycles per instruction, so minimising k (or spreading it over a longer body) is what matters. The ideal CPI 1 is reached only with k = 0.

Answer 2: Perf(A)/Perf(B) = Time(B)/Time(A) = 15/10 = 1.5 = 1 + 50/100.

Answer 2: Clock cycles = IC + Stall cycles + 4 with Stall cycles = 0.

Answers 1, 2 and 4.

1. Branch always not taken. Fetch continues at PC + 4 as if the branch were an ordinary instruction; no hardware and no target address are needed. When the branch is not taken the cost is zero; when it is taken the one instruction fetched after the branch is flushed (turned into a NOP) and fetch restarts at the target: a 1-cycle penalty with the branch solved in ID. Good for if-then-else with a rare else path, bad for loop-closing branches, which are taken almost always.

2. Branch always taken with a BTB. Fetch continues at the target. The target is needed while the branch is still in IF, before decoding, so a Branch Target Buffer — a cache indexed by the address of the branch instruction whose entry holds the predicted target address — supplies it; on a hit the target is fetched in the next cycle. When the branch is not taken the instruction fetched from the target is flushed and fetch resumes at PC + 4 (1 cycle). On a BTB miss the processor falls back to PC + 4 or waits for the target. Good for backward loop branches; without a BTB the scheme has no benefit in a 5-stage pipeline because the target is not known before the outcome.

3. BTFNT. Use the direction of the branch, i.e. the sign of the offset: backward branches (loops) are predicted taken, forward branches (if-then-else, rarely entered paths) not taken. Needs only one bit of the instruction and no learning hardware; better accuracy than either uniform rule on mixed code. Not adaptive: a forward branch that is usually taken is mispredicted most of the time; and the direction is only known after decoding, so the guess is stored in the BTB entry to be usable in IF.

4. Delayed branch. The instruction in the slot after the branch is always executed, whatever the outcome; the branch takes effect after it. The compiler fills the slot with an instruction from before the branch (independent of it: always useful), from the target (useful when taken; must be harmless when not; usually duplicated at the label) or from the fall-through (useful when not taken; harmless when taken). A filled slot hides the 1-cycle bubble of the ID-resolved pipeline; a NOP in the slot is a stall. Benefit: no guessing and no flush logic; drawbacks: the slot ties the ISA to one pipeline depth, deeper or multiple-issue pipelines cannot be covered by one slot, and about half of the slots are not usefully filled — which is why RISC-V has no delay slot.

The BNE executes with R1 = 4, 8, 12, 16, 20 against R2 = 20: five executions, outcomes T T T T NT.

(a) 4 mispredictions of 5 = 80 %, 4 stall cycles. (b) 1 of 5 = 20 %, 1 stall cycle. (c) LOOP is above the BNE, the offset is negative, the branch is predicted taken: identical to (b), 20 %, 1 stall cycle.

Always not taken mispredicts exactly the taken branches, so \(p_{\text{mis}} = 0.6\). For comparison: stalling gives 1.20, always taken with a perfect BTB 1.08; with the PC written in ME (penalty 3) the three become 1.60, 1.36, 1.24.

      LD    F0, 0(R1)      # copy of the target, runs once
LOOP: ADDUI R1, R1, 8      # new target
      FADD  F2, F2, F0
      FMUL  F4, F4, F0
      BNE   R1, R2, LOOP
      LD    F0, 0(R1)      # delay slot: next iteration's load

Before: 5 instructions + 1 NOP = 6 cycles per iteration (m = 5, k = 1, CPI_∞ = 1.2). After: 5 cycles per iteration (k = 0, CPI_∞ = 1), because the slot now holds the next iteration's load. Legal because: the moved LD does not produce an operand of the branch (R1, R2); the slot LD writes F0, which the next FADD reads with the ADDUI in between, so no load-use stall appears; the ADDUI stays at least one instruction before the BNE that tests R1 (2-cycle ALU-to-branch latency); and on the exit path the extra load past the end of the array must be harmless — the address readable and F0 dead after the loop. The copy before the loop is the duplication cost of the strategy.

1 cycle: penalty = resolution stage − 1 = 2 − 1.

It is always executed, regardless of the branch outcome.

True: indexed by the branch PC; stores the predicted target; on a hit the target is fetched in the next cycle. False: it does not decide the direction, and always not taken does not need it.

(a) The hardware predicts each branch at run time from its past behaviour, so the pipeline keeps fetching instead of stalling. Benefits: fewer mispredictions and hence a lower CPI (in \(\text{CPI} = \text{CPI}_{\text{ideal}} + f_b (1 - a) P\) the predictor raises the accuracy \(a\), the penalty \(P\) is fixed by the pipeline); adaptation to the actual input data and program phases, which a static compile-time rule cannot see; it is essential in deep and wide pipelines, where every misprediction wastes depth × width instructions; it enables speculative execution past unresolved branches, with results committed only when the branch resolves; it needs no compiler support, delay slots or profiling, so existing binaries benefit.

(b) A Branch History Table is a table indexed by the low-order bits of the branch PC, without tags (so two branches may share an entry: aliasing). Each entry is a small finite-state machine: 1 bit storing the last outcome, or a 2-bit machine with the states Strongly Taken, Weakly Taken, Weakly Not Taken, Strongly Not Taken, predicting Taken in the first two. The table is read in IF with the fetch PC and the prediction decides whether to fetch PC + 4 or the target; when the branch resolves the entry is updated with the outcome. With 2 bits a single anomaly, such as a loop exit, moves a strong state to the weak state of the same direction without changing the prediction, so a loop branch is mispredicted once per execution of the loop instead of twice.

The branch target address is computed in the ID stage, so even a correct Taken prediction in IF leaves the fetch unit without an address: one bubble on every taken branch. The Branch Target Buffer removes this control hazard. It is a small cache indexed by the branch PC, with tags, whose data is the predicted target address of taken branches (often together with the T/NT prediction bits). On a hit with a Taken prediction the next PC is set to the stored target in the same IF cycle, so a correctly predicted taken branch costs zero cycles. An entry is written when a taken branch resolves and its target is known; on a miss, fetch defaults to PC + 4 and the branch pays the normal penalty if taken. The tags are necessary because a false hit would redirect the fetch of a non-branch instruction — unlike the BHT, which only predicts the direction and can be untagged.

The BNE is executed with R1 = 4, 8, 12, 16, 20: five times, Taken four times and Not Taken at the exit.

Mispredictions at the 1st, 2nd and 5th execution: misprediction rate = 3 / 5 = 60 % (Answer 1). With the FSM of the lecture figure the 3rd state is Strongly Taken (WNT → ST on a Taken); the predictions and the rate are the same.

Before the 5th execution the state is Strongly Taken (after four Taken). The outcome is Not Taken, so the state moves one step: Strongly Taken → Weakly Taken (Answer 2). The question asks for the state after the last update, one transition beyond the last column of the table.

The BEQ is executed with R1 = 0, 1, …, 100: 101 accesses to the BHT. Outcomes: Not Taken 100 times, then Taken at R1 = 100. The entry starts as Taken: 1st access, predict Taken, outcome Not Taken → misprediction, bit ← NT; accesses 2 to 100 predict Not Taken correctly; 101st access, predict Not Taken, outcome Taken → misprediction. Total: 101 accesses, 2 mispredictions (rate 2/101 ≈ 2 %).

(a) 3 × 8 = 24 accesses; outcomes T T T T T T T NT, three times. The 1-bit entry mispredicts at access 1 (NT predicted, T), at 8 (exit), at 9 (re-entry: the entry holds NT), at 16, 17 and 24: 6 mispredictions, 6/24 = 25 %, final state Not Taken (the last outcome).

(b) From Strongly Not Taken: access 1 predicts NT (miss, → WNT), access 2 predicts NT (miss, → WT with a saturating counter, → ST with the lecture figure), accesses 3–7 predict T correctly (the state is ST from access 4 at the latest), access 8 predicts T but the branch exits (miss, ST → WT); access 9 predicts T from WT correctly (→ ST), accesses 10–15 hit, 16 misses (→ WT), 17 hits, 18–23 hit, 24 misses (→ WT). Mispredictions at 1, 2, 8, 16, 24: 5, rate 5/24 ≈ 21 %, final state Weakly Taken.

(c) Steady state: 2 per inner-loop execution with 1 bit (exit and re-entry), 1 with 2 bits (exit only). The 2-bit predictor also paid one extra warm-up miss from Strongly Not Taken.

True. (1) Initialization: the initial state of the entry decides whether the first executions of a branch are predicted correctly — a loop branch whose entry starts Strongly Not Taken costs two warm-up mispredictions, one that starts Weakly Not Taken costs one, one that starts Taken costs none. (2) Size: the BHT is indexed by k low-order bits of the PC without tags, so with 2^k entries all branches sharing those bits share the entry and interfere (aliasing); a larger table spreads the branches over more entries and reduces the interference. (The number of mispredictions also depends on the predictor's FSM, 1-bit or 2-bit, and on the program's branch patterns.)

A standard BHT predicts each branch from its own past only. A correlating (two-level) predictor also uses the outcomes of the branches executed just before it: an m-bit Global History Register, a shift register holding the last m outcomes (1 = Taken), selects one of 2^m tables of n-bit entries (1-bit, or the 2-bit states Strongly/Weakly Taken, Weakly/Strongly Not Taken), and the k low-order bits of the branch PC select the entry inside the selected table. Equivalently the GHR concatenated with the PC bits forms one index of m + k bits into a single table; gshare XORs the history with the PC bits instead, to spread the branches over the whole table and reduce aliasing. After the branch resolves, the entry is updated and the outcome is shifted into the GHR. The benefit: each (branch, recent context) pair has its own counter, so a branch whose outcome depends on previous branches — or on its own recent pattern, such as a loop exit — is predicted correctly after warm-up, where a per-branch counter flip-flops; H&P show a (2,2) predictor of 8 Kbit mispredicting less than a 2-bit BHT with unlimited entries. The cost is one shift register, 2^m × n × 2^k bits of tables, a longer warm-up (every context must be trained) and aliasing in the pattern table.

(a) 1-bit per branch (prediction = bit before, bit after = outcome):

(b) (1,1) predictor, entries written "if last NT / if last T":

(c) 8 of 8 mispredicted against 2 of 8. The 1-bit entry always holds the previous outcome, and the outcomes alternate, so it is always one step behind. In the (1,1) predictor the global history bit selects a different entry for "after a taken branch" and "after a not-taken branch": in this code b1 not taken implies b2 not taken and b1 taken implies b2 taken, so each context converges after one miss; b1 is predicted from the previous b2, whose outcome encodes the previous value of d. Only the two cold entries miss.

that is 1 KB; a plain 2-bit BHT with the same budget would have 4096 entries.

Answer 1. Executions of BEQ: R1 = 0, 1, …, 100 → 101 accesses. Predict Taken at R1 = 0: outcome Not Taken, miss, bit → NT. R1 = 1 … 99: predict NT, outcome NT, 99 hits. R1 = 100: predict NT, outcome Taken, miss. Two mispredictions.

True. (1) Initialisation: the initial state of the entries decides whether the first executions of each branch are predicted right — a 2-bit entry initialised Strongly Not Taken mispredicts the first two taken executions of a loop branch, initialised Strongly Taken it mispredicts none; these start-up misses count in the misprediction rate. (2) Size: the BHT is indexed by the low-order PC bits without tags, so with a small table different branches map to the same entry (aliasing) and interfere, each spoiling the other's state; a larger table reduces the collisions.

Answer 3. The exit is predictable because it comes at a fixed position; only a history long enough to distinguish "nine taken in a row" from the earlier positions can represent it, which is what a local (or, with no other branch in the body, global) history of at least 9 bits does. Counters of any size and static rules cannot.

Dynamic instruction scheduling. The hardware, not the compiler, decides at run time when each instruction executes. Instructions are issued in program order to reservation stations and start executing as soon as their operands and a functional unit are available, so an instruction stalled on a long-latency producer (a divide, a cache miss) does not block the independent instructions behind it. Benefits: higher ILP and unit utilisation, latency hiding, handling of dependences unknown at compile time (memory, control flow), and binary compatibility — the same code runs efficiently on different pipelines; it is also the base for hardware speculation.

Dynamic register renaming. At issue, each destination register is mapped to a new name — a physical register, a reservation-station tag or a reorder-buffer entry — and later readers are redirected to it, so two instructions that re-use the same architectural register no longer conflict. Benefits: it eliminates WAR and WAW hazards (name dependences), leaving only true RAW dependences, which lets instructions execute out of order and loop iterations overlap without running out of registers.

Out-of-order execution. Instructions execute in the order in which their operands become ready rather than in program order, while issue and commit remain in program order; results are broadcast on the common data bus to the waiting consumers. Benefits: independent instructions fill the cycles that dependent ones would waste, long latencies are overlapped, more ILP is extracted from the instruction window. Cost: renaming, reservation stations and a reorder buffer to keep exceptions precise.

New problems: (1) a structural hazard on the unpipelined divider; (2) several instructions may reach write-back in the same cycle, so the register-file write port must be arbitrated or reserved at issue; (3) WAW hazards, because a short operation issued after a long one to the same register completes first — WAR hazards cannot occur, since operands are still read in order in ID; (4) imprecise exceptions, because a younger instruction may have written its result before an older one faults; (5) more and longer RAW stalls, since forwarding cannot hide a multi-cycle computation.

A single commit point delays every result so that all operations reach the W stage after the same number of cycles: write-back is then in issue order, one per cycle (no WAW, no write-port conflict), and an exception is taken at commit, after all earlier instructions and before any later one (precise). Cost: independent fast instructions wait behind slow ones, and an unpipelined divide or a cache miss stalls the whole pipeline — low ILP, which is what motivates out-of-order execution with a reorder buffer that keeps commit in order while execution reorders.

Answer 2. S1 reads X[i-1], produced by S1 in iteration i-1: loop-carried. S2's dependence on X[i] is within the iteration, and Y[i-1] is read only.

RAW, structural and control. WAR and WAW cannot occur: reads precede writes in order (no WAR) and all writes happen in WB in order (no WAW). Register renaming therefore buys nothing on this pipeline; it matters only once multi-cycle units (WAW) and out-of-order execution (WAR) appear.

The second option. An exception is precise when all older instructions have completed and no younger one has changed the state; here younger, independent instructions completed and wrote their registers before the older FDIV faulted, so the state corresponds to no point of the sequential program. In-order commit (a reorder buffer) fixes it by holding their results until the FDIV has committed.

1. Dynamic instruction scheduling. The hardware, not the compiler, decides at run time when each instruction executes: instructions are issued in program order to reservation stations and start as soon as their operands and a functional unit are available, so execution and completion are out of order while issue and commit stay in order. Benefits: an instruction stalled on a long-latency producer (FP divide, cache miss) no longer blocks the independent instructions behind it; higher ILP and unit utilisation; latency hiding; dependences unknown at compile time (memory, misses) are handled; the same binary runs efficiently on different pipelines; it is the base for hardware speculation.

2. Dynamic branch prediction and speculative execution. A branch history table (with a branch target buffer) predicts the outcome and the target at fetch time from the past behaviour of the branch; the processor fetches, issues and executes the predicted path before the branch is resolved, keeping the results in the reorder buffer, and squashes them if the prediction was wrong. Benefits: removes most control stalls, keeps the issue slots of a wide machine full and exposes ILP across branches; the cost is the flush on a misprediction, which grows with pipeline depth and issue width.

3. Multiple-issue pipeline. The front end fetches, decodes and issues up to w instructions per cycle (the issue width) into several functional units, so IPC can exceed 1 and the ideal CPI is 1/w. It needs wider fetch and decode, a multi-ported register file, more functional units and hazard checks across the instructions issued together. Benefit: throughput multiplied by the width when enough independent instructions are available; the ideal is a maximum, rarely sustained because of dependences, branches and misses.

4. Reservation stations. Buffers in front of each functional unit that hold the operation, the operand values already available (Vj, Vk) or the tags of the instructions that will produce them (Qj, Qk); an instruction waits in its station and fires when the last operand arrives on the common data bus. Benefits: hazard detection is distributed (no central bottleneck), operands are fetched once at issue, so WAR hazards vanish, the station's tag renames the destination, so WAW hazards vanish, and issue continues past a waiting instruction.

5. Dynamic register renaming. At issue, every destination register is mapped to a new name — a reservation-station tag, a ROB entry or a physical register — and later readers are redirected to that name, so two instructions that reuse the same architectural register no longer conflict. Benefits: WAR and WAW hazards, which are name dependences, are eliminated; only true RAW dependences remain; more instructions can be in flight and loop iterations overlap without unrolling.

6. Out-of-order execution. Instructions execute in the order in which their operands become ready rather than in program order; issue and commit remain in order and results are broadcast on the common data bus to the waiting consumers. Benefits: independent instructions fill the cycles that dependent ones would waste, long latencies (loads, FP operations) are overlapped and more ILP is extracted from the instruction window; the cost is renaming, reservation stations and a reorder buffer to keep exceptions precise.

7. Reorder buffer. A FIFO in program order that holds each result from write-result to commit; the entry at the head commits to the register file (or to memory, for a store) only when it is complete and no longer speculative. Benefits: precise exceptions and an architectural state updated in program order; speculation can be undone by discarding the entries after a mispredicted branch; the register file is written only at commit.

8. Simultaneous multithreading. Several hardware threads issue in the same cycle into the functional units of one out-of-order core, each with its own PC and rename table, sharing the units and the caches. Benefits: thread-level parallelism fills the issue slots that the ILP of one thread leaves empty (both horizontal and vertical waste), so throughput rises at a small hardware cost; the ideal CPI of the core stays 1/w and the ideal per-thread CPI is threads/w; threads contend for caches and units, so single-thread performance can drop.

Static (VLIW). The compiler, at compile time, packs independent operations into long instruction words, scheduling around the known latencies and inserting NOPs where no operation fits. Advantages: simple hardware (no dependence checks, no renaming, no out-of-order logic), predictable timing, low energy per instruction. Drawbacks: performance depends entirely on the compiler and on the visible ILP; the binary is tied to one machine configuration (units, latencies), so it must be recompiled for a new one; the schedule cannot adapt to run-time events such as cache misses or mispredictions; unused slots become NOPs, lowering the code efficiency IC/(cycles × issues). Domains: embedded, real-time, DSP and domain-specific processors.

Dynamic (superscalar). The hardware, at run time, detects the parallelism with reservation stations, register renaming and a reorder buffer, and issues whatever is ready. Advantages: adapts to unpredictable latencies, keeps binary portability (no recompilation), exploits the hidden parallelism of general-purpose code. Drawbacks: complexity, area and power; the scheduling logic becomes the bottleneck at wide issue widths; timing is hard to verify. Domains: general-purpose x86 and ARM cores. Both aim at IPC above 1; the trade-off between hardware complexity and compiler sophistication decides where each wins.

Answer 3: ideal CPI = 1/issue width = 1/2 = 0.5; ideal per-thread CPI = threads/issue width = 4/2 = 2.

Statements 1, 2 and 3 are true (1 only for the ideal CPI, 1/issue width); statement 4 is false, because dependences, branches and memory stalls do not shrink with the width and Amdahl's law bounds the gain at 1/f.

Serial fraction \(f = 0.2\), \(p = 4\):

In the formula sheet's form, \(F = 0.8\) and \(S = 4\): \(1/(0.2 + 0.8/4) = 2.5\). The ceiling for this program is \(1/0.2 = 5\).

(i) Single-issue, in-order issue; out-of-order read of operands, execution and write-back; no forwarding (a result is visible only after it is written in the register file); several independent functional units ("multiple pipelined FUs" in the notes) with different latencies, each holding one instruction from issue to write result in the tables; no register renaming, so WAW and WAR hazards must be handled by stalls; exceptions are imprecise.

(ii) Issue (in order): structural hazard — the functional unit must be free — and WAW — no pending write to the destination in the register result status. Read Operands (out of order): RAW — both source operands written to the register file (and read ports available). Execute: no hazard, latency of the unit. Write Result (out of order): WAR — no earlier instruction still waiting to read the destination (and a write port free).

(iii) Instruction status: the stage reached by each instruction (the I / RR / E / WB table). Functional-unit status, one row per unit: Busy, Op, Fi (destination), Fj, Fk (sources), Qj, Qk (the units that will produce Fj, Fk; blank if the value is in the register file), Rj, Rk (source ready and not yet read; set to No when the operands are read). Register result status: for each register, the unit that will write it. Qj/Qk say who produces an operand, Rj/Rk say whether it may be read now; Rj = No after the read is what the WAR test of Write Result uses. Benefits: independent instructions overlap, long latencies are hidden, functional units are better used, no compiler support is needed.

(iv) Limits: the parallelism available in the window, the number of scoreboard entries, the number and types of functional units, WAR/WAW stalls because there is no renaming, one extra cycle per RAW dependence because there is no forwarding, centralized control, imprecise exceptions. Tomasulo adds register renaming through reservation stations (WAR and WAW disappear), the Common Data Bus (results forwarded to every waiting station, distributed hazard detection) and, with a reorder buffer, speculation and precise exceptions.

I1 issues at 5 because the Integer unit is Busy until I0's write at 4. I2 reads at 9 = WB(I1) + 1. I3 cannot issue while the register result status says F2 = Integer (cycles 7–8); it issues at 9 and writes at 13, allowed because I2 has read F2 at 9. I4 issues at 10 and reads at 15 = WB(I2) + 1; it holds the Integer unit until its write at 17, so I5 issues at 18. Total 21 cycles; CPI = 21 / 6 = 3.5.

I3 completes execution at cycle 7 but I2 (FADD F6, F4, F8) still has to read F8; I2 reads only at cycle 11 (= WB of I1 + 1). WAR on F8: WB(I3) = max(7 + 1, 11 + 1) = 12.

Answer 2: the later writer waits at Write Result until the earlier reader has read its operands (Rj/Rk back to No).

Answer 3: Rj, Rk are "ready and not yet read"; No covers both "waiting for the producer" and "already read", and a writer may proceed in both cases.

False: Busy is cleared at Write Result, not at the end of execution. Example: in the fragment of this lesson I0 completes execution at cycle 3 and writes at 4; I3, which needs the same Integer unit, issues at 5, not at 4.

Without renaming the two writes to the same register must land in program order. Checking at Issue is the simplest guarantee: issue is in order, so the instruction being issued is always the later writer, and one lookup in the register result status (a non-blank entry for its destination) settles it. It also keeps the Write Result test simple: because two pending writes to one register can never coexist, a source flag Rj = No can only mean "already read" or "waiting for this very writer", so the WAR test may let the writer through on a No.

If the check is postponed to write-back, the later writer issues and executes early (it no longer blocks the instructions behind it), but the Write Result stage must additionally enforce WB(second) > WB(first) for every earlier pending writer of the same register — i.e. the hardware must track, per register, more than one pending writer and order the writes explicitly.

(a) 62 cycles; CPI = 62 / 6 ≈ 10.3. I1 issues at 5 because the Integer unit is Busy through I0's WB at 4; I2 and I3 read at 9 = WB(I1) + 1; I4 reads at 21 = WB(I2) + 1; I5 issues at 13, the cycle after I3's WB.

(b) A WAR hazard on F6 with I4: I4 reads F6 only at 21, because it waits for F0 (written at 20); I5 completes at 16 and writes at RR(I4) + 1 = 22.

(c) No. With a second adder I5 issues at 9 and completes at 15, but it still cannot write before I4 has read F6, so WB(I5) = 22; the total is fixed by the chain LD F2 → FMUL → FDIV, which ends at 62 whatever happens to the adds.

23 cycles; CPI = 23 / 7 ≈ 3.29; speedup = 25 / 23 ≈ 1.09. Forwarding takes one cycle out of each RAW wait (I1, I2, I4); the WAW on F4 still holds I3 at Issue, so the queue behind it moves only with I1's earlier write.

I1 2–7–10–11 and I2 3–12–15–16 as in the basic scheme (no forwarding). I3 issues at 7 (LDU1 free, no WAW check at Issue), reads at 8, completes at 11 — but may write only after I2 has read F4, at 12 (WAR), and after I1's write at 11 (WAW at write-back): WB = 13. I4 issues at 14 on LDU1, reads F4 at 15 = WB(I3) + 1, E 18, WB 19. I5 15–16–17–18. I6 issues at 19 (ALU1 free after 18), 20, 21, WB = 22. CPI = 22 / 7 ≈ 3.14.

Answer 2: RR = WB of the producer (one cycle earlier than without forwarding).

Answer 2: postponing the WAW check (22) beats forwarding (23); together they give 21.

False. In the notes' example FADD F6 reads at 14 and completes at 16 although FDIV, an earlier reader of F6, reads only at 21; the WAR delays FADD's write to 22, not its execution.

1. Issue decodes and checks the resources (a free unit, no pending write to the destination: structural and WAW hazards), in order; Read Operands waits for the sources to be in the register file (RAW), separately for every issued instruction. Benefit: an instruction waits in the row of its own unit while independent later instructions issue behind it and may read before it (in the notes' example FADD, issued at 13, reads at 14 while FDIV, issued at 8, reads at 21). Cannot fix: a stall at Issue still blocks every later instruction.

2. The register result table is not consulted at Issue, so a later writer of a busy register issues as soon as a unit is free; Write Result then enforces the order of the two writes (WB of the second after WB of the first) in addition to the WAR test. Benefit: the in-order issue queue is not blocked by an output dependence (January 2026: I3 issues at 7 instead of 12 and the three instructions behind it issue 3 cycles earlier: 25 → 22). Cannot fix: the dependence itself — the two writes are still serialised, and the WAR test can still delay the second write; only renaming removes it.

3. A result is bypassed from the unit to a waiting consumer in the cycle it is written instead of after the register-file write: each RAW wait is one cycle shorter (RR = WB of the producer). Benefit: one cycle per link of every true-dependence chain (January 2026: 25 → 23). Cannot fix: the latency itself, and nothing about structural, WAW or WAR waits.

4. Instructions enter in program order, which keeps the hardware simple (the instruction being issued is always the later writer, so one lookup settles a WAW), and leave as soon as they are done, which lets independent instructions overlap long latencies (in the notes' example the subtract and the add complete inside the load–multiply–divide chain, which alone sets the 62 cycles). Cannot fix: WAR and WAW stalls (no renaming), imprecise exceptions (no reorder buffer), and the stalls of the issue queue behind a blocked instruction.

Reservation stations. Buffers in front of each functional unit. An issued instruction waits there with its operation, its operand values (Vj, Vk) or the tags of the producers it waits for (Qj, Qk), and a busy bit. They decouple issue from execution: an instruction waits locally for its operands instead of blocking the pipeline, the station’s name is the temporary name of its result (renaming), and the control is distributed — each unit schedules itself. Benefit: no central scoreboard, no stall of the instructions behind a waiting one, more instructions in flight than there are registers.

Dynamic register renaming. At issue the destination register’s status field Qi is set to the station’s tag, and every later consumer records that tag instead of the register name. Results are broadcast with the tag; a register is written only if its Qi still holds that tag (the newest writer owns the register). Benefit: WAR and WAW hazards — name dependences — can never stall or corrupt; only true RAW dependences remain; the renaming is done by hardware, invisible to the ISA, so the register count of the ISA no longer limits scheduling.

Out-of-order execution. An instruction leaves its station for the functional unit as soon as Qj = Qk = 0 and the unit is free, independently of program order; results return out of order over the common data bus. Benefit: independent instructions proceed while a long-latency one (a load, a divide) waits, so stalls are filled and the CPI falls. Cost: completion out of order gives imprecise exceptions unless a reorder buffer restores in-order commit.

In the scoreboard an instruction reads its operands from the register file in the Read Operands stage. A later instruction that writes one of those registers must therefore wait at Write Result until the read has happened, otherwise the reader would get the new value: the WAR hazard costs a stall of the writer. In Tomasulo’s algorithm the reader takes a copy of the operand at Issue (into Vj/Vk) if it is available, or records the producer’s tag (Qj/Qk) and receives the value from the CDB; it never reads the register file later. The later writer cannot overwrite anything the reader still needs; it only sets the register’s Qi to its own station. The WAR hazard is dissolved at Issue — copy or tag — and no stage ever stalls for it.

Answer 3: the station is busy from Issue through Write Result and reusable from the next cycle.

Answers 2, 4 and 5. Data hazards never stall issue in Tomasulo’s algorithm: RAW waits in the station, WAR and WAW are dissolved by the tags.

False: the store buffer monitors the CDB for its data and writes memory; it broadcasts nothing. In the exam table its WRITE RESULT entry is the cycle the memory write completes.

Reservation stations. Buffers in front of each functional unit, each holding one issued instruction: its operation, its operand values (Vj, Vk) if they were available at issue, otherwise the tags (Qj, Qk) of the stations that will produce them, and a busy bit; the station's name is the tag under which its result will be broadcast. Benefits: the instruction leaves the in-order front end at once (a RAW dependence never stalls issue), waits locally and fires as soon as both operands arrive (data-driven execution); hazard detection is distributed, there is no central scoreboard; the stations give pending results more names than the ISA has registers. Cost: when all stations of a class are busy, issue stalls (structural hazard).

Dynamic register renaming. At issue the destination register's status field Qi is set to the station's tag, so the register always names its youngest writer; a consumer copies the value or the producer's tag at issue and never reads the register later. A result is broadcast with its tag, captured by every waiting station, and written into the register only if Qi still holds that tag. Benefits: WAR and WAW hazards (name dependences created by register reuse in loops and by the compiler's allocation) can neither stall nor corrupt — only true RAW dependences remain; the ISA's register count no longer limits scheduling; it is invisible to the program.

Out-of-order execution. An instruction starts in its unit as soon as Qj = Qk = 0 and the unit is free, independently of program order; results return out of order on the common data bus, one per cycle. Benefits: independent instructions proceed while a long-latency one (a load miss, a divide) waits, so stalls are hidden and throughput rises (lower CPI); latencies unknown at compile time are tolerated. Cost: completion out of order makes exceptions imprecise — a reorder buffer with in-order commit restores them.

Dependences: I1 true with I0 for F2, output with I0 for F2; I2 true with I1 for F2, anti with I1 for F2, output with I0 and I1 for F2; I3 true with I2 for F2; I4 anti with I0 and I3 for R1; I5 true with I4 for R1.

Writes on the CDB at 6, 8, 10, 11, 14 and the memory write at 19: no tie. CPI = 19 / 6 ≈ 3.17.

Dependences: I3 true with I0 for F2 and I1 for F4, output with I1 for F4; I4 true with I3 for F4 and I2 for F6, output with I2 for F6; I5 true with I4 for F6; I6 anti with I0, I1, I2 and I5 for R1; I7 true with I6 for R1.

CPI = 22 / 8 = 2.75.

The store now finds a free station at cycle 5 (ISSUE 5 instead of 7), ADDUI issues at 6 (6 / 7 / 9) and BNE at 7 (7 / 10 / 12, no tie on the CDB any more). But the store still needs F2 from I3, written at 14: START EXEC 15, WRITE RESULT 15 + 4 = 19. CPI = 19 / 7 ≈ 2.71, unchanged.

Answer 3: a station is busy from ISSUE through WRITE RESULT and reusable from the cycle after the write.

Answers 2, 4 and 5. Data hazards never stall issue: RAW waits in the station, WAW and WAR are dissolved by renaming.

False. A store waits in its load/store station for the address and the data (the data may arrive by tag over the CDB), then writes memory; it broadcasts nothing because no later instruction reads a register from it. In the June 2026 table the store's WRITE RESULT = 15 + 4 = 19 is its memory write, and it never competes for the bus.

Reservation stations. Buffers in front of each functional unit. An issued instruction waits there with its opcode, its operand values (Vj, Vk) if they were available at issue, otherwise the tags (Qj, Qk) of the stations that will produce them; the station is itself the tag under which the result will be broadcast. Benefits: the instruction leaves the in-order front end at once (no issue stall on a RAW hazard), waits locally and fires as soon as both operands arrive, results reach every waiting station and the register file in one cycle through the common data bus (forwarding), and hazard detection is distributed instead of centralized in a scoreboard.

Dynamic register renaming. At issue the destination register's status field Qi is set to the station's tag, so the register names its youngest producer; consumers take a value or a tag at issue and never consult the register name again. Benefits: WAR hazards disappear (a reader owns its copy or its producer's tag), WAW hazards disappear (only the broadcast whose tag matches Qi is written; an older writer's result is dropped), so the false dependences created by register reuse no longer serialize execution; more instructions in flight; loop iterations overlap without unrolling.

Out-of-order execution. An instruction executes as soon as its operands and a unit are available, whatever older instructions are doing: issue stays in order, execution and completion do not. Benefits: a long-latency instruction (a cache miss, a 40-cycle divide) no longer blocks independent work behind it — in the classic example FADD, issued after FDIV, writes its result at cycle 13 while FDIV finishes at 59 — giving higher unit utilization and IPC. Cost: results written out of order make exceptions imprecise and speculation hard to undo; the reorder buffer restores in-order commit.

Checks: I2 starts at 8 = write of I1 + 1; I3 at 8 = max(6 + 1, 7 + 1); I4 at 15 = write of I2 + 1, FPU2 free (I2 executed 8–13); I5 at 12 = write of I3 + 1, FPU1 free since 11. CDB at 6, 7, 11, 14, 15, 27: no collision. CPI = 27 / 6 = 4.5.

LD F2: issue 2, start 3, write 5. FMUL: start 6, write 16. FDIV: start 17 (F0 written at 16, the multiplier free), write 17 + 40 = 57. With one load unit held through its write cycle the chain starts two cycles later and the answer is 59.

Answer 2. If Qi[F6] = RS4, a younger writer owns the name and the broadcast is dropped by the register file (the stations waiting for RS3 still take it).

Answer 2. In the example the scoreboard held FADD's write from 16 to 22 for a WAR with FDIV; Tomasulo wrote it at 13.

Answers 1, 3 and 4.

Results are written into the register file at write result, in completion order, which is not program order: in the classic example FADD writes F6 at cycle 13 while the older FDIV finishes at 59. If FDIV raised an exception, F6 would already hold a value produced by a younger instruction and no earlier instruction could be guaranteed complete — the architectural state is inconsistent and in-place writes cannot be undone. The fix is a reorder buffer: results go to the ROB at write result and are committed to the register file in program order, so at an exception everything older has committed and everything younger is discarded. The scoreboard has the same problem, since it too writes registers in place and out of order.

(1) A reservation station is a buffer in front of a class of functional units that holds an issued instruction together with its operand values (Vj, Vk) if they are already available, or the tags (Qj, Qk) of the stations that will produce them. Benefits: the instruction leaves the issue stage without waiting for its operands, so later independent instructions can issue; the station is also the renamed destination, which removes WAR and WAW stalls (the February 2025 ADDI overwrites R0 while two stores still hold their copies of the old R0). Cost: the number of stations bounds what can be issued; when every station of a class is busy, issue stalls (RS1 and RS2 busy at cycles 5–8 of the February paper).

(2) When a unit finishes, the result is broadcast on the Common Data Bus as the pair (tag, value), the tag being the station of the producer. Every station and register whose Qj, Qk or tag field matches captures the value in the same cycle, so a consumer can start the next cycle without a trip through the register file and without a stall on name dependences. Cost: one bus delivers one result per cycle; when two are ready the older goes first and the younger waits, keeping its station (midterm 2025, cycles 12–16: five results, I7 writes at 15 instead of 12).

(3) Instructions issue strictly in program order, one per cycle, but start executing as soon as their own operands and a unit are available, and finish out of order: long-latency instructions no longer block independent ones (I6 ADDI executes at 12 while the FP work is pending), the hardware tolerates unpredictable latencies such as cache misses, and the compiler needs no knowledge of the pipeline. Cost: in-order issue means one blocked instruction blocks everything behind it; out-of-order completion makes exceptions imprecise, and nothing can pass an unresolved branch until a reorder buffer (lesson 17) adds speculation.

Dependences: I0, I1, I2: none. I3: true with I0 for F2 and with I1 for F4; output with I1 for F4. I4: true with I3 for F4 and with I2 for F6; output with I2 for F6. I5: true with I4 for F6. I6: anti with I0, I1, I2 and I5 for R1. I7: true with I6 for R1.

CPI = 22 / 8 = 2.75.

I1 1 / 2 / 6 RS1 LDU1; I2 2 / 3 / 7 RS2 LDU2; I3 3 / 4 / 8 RS3 FPU1; I4 4 / 5 / 9 RS4 FPU2 (no unit wait); I5 7 / 8 / 12 RS1 LDU1 (structural: RS1, RS2 busy at 5–6); I6 8 / 9 / 13 RS2 LDU2; I7 9 / 10 / 14 RS5 ALU1 (ready at 12: CDB taken by I5 at 12 and I6 at 13); I8 10 / 11 / 15 RS6 ALU2 (ready at 13: behind I6 and I7); I9 15 / 16 / 18 RS5 ALU1 (RS5 free after 14; R2 arrives at 15); I10 16 / 19 / 21 RS6 ALU2 (R3 at 18). CPI = 21 / 10 = 2.1.

I2 starts 10, writes 14; I3 starts 15, writes 19; I4 starts 15 (F4 at 14), writes 21; I6 11 / 12 / 13 and I7 14 / 15 / 16 unchanged; I5 starts 20 (F6 at 19), writes 26. Write cycles 8, 9, 13, 14, 16, 19, 21, 26: no bus collision. Last WRITE RESULT = 26, CPI = 26 / 8 = 3.25.

Answer 3: STRUCTURAL on RS5, the single integer station, busy with I6 through cycle 13.

Answer 3. This is why a result that waits for the bus delays the issue of later instructions.

True. Motivation: stations are released at WRITE RESULT; a write delayed by bus arbitration keeps the station busy, and in-order issue stalls on the missing station.

(a) WAR and WAW are name dependences, caused only by reusing the few ISA register names. At issue, the reservation station that will produce a result becomes its name (tag): the register status records the tag, consumers keep either the value (Vj, Vk) or the producer's tag (Qj, Qk), and results are broadcast on the CDB as (tag, value). Benefits: WAR/WAW never stall, more instructions in flight, loop iterations overlap on unchanged code. Costs: tag comparators in every station, CDB bandwidth, limited by the number of stations. RAW remains.

(b) The compiler copies the loop body u times, folds the addresses into the displacements, keeps one index update and one branch, and gives each copy fresh ISA registers ((u − 1)ρ more), so the copies share no names. Benefits: the overhead is paid once per u elements (w + o/u instructions per element instead of w + o) and a large block of independent instructions can be scheduled — loads first, FP operations next, stores last. Costs: code size, register pressure, a remainder loop when the trip count is not a multiple of u; the latencies must be known at compile time. RAW inside each copy remains.

Original loop: R1 goes 0, 4, …, 396 before the branch falls through at 400, so 400/4 = 100 iterations; 7 instructions per iteration; 3 of them overhead (ADDUI R1, ADDUI R2, BNE), 4 useful; 700 instructions and 100 branches executed.

Unrolling factor 2 — the body with the second copy renamed:

LOOP: LD    F2, 0(R1)
      LD    F4, 0(R2)
      FADD  F6, F2, F4
      SD    F6, 0(R1)
      LD    F8, 4(R1)
      LD    F10, 4(R2)
      FADD  F12, F8, F10
      SD    F12, 4(R1)
      ADDUI R1, R1, 8
      ADDUI R2, R2, 8
      BNE   R1, R3, LOOP

50 iterations (100 is a multiple of 2, no remainder loop); 11 instructions per iteration; overhead still 3; 550 instructions and 50 branches executed. Registers: with the same names, the second copy could not write F2, F4, F6 before the first copy had read them (WAR/WAW), so the copies would stay serialised; F2, F4, F6 are renamed to F8, F10, F12: 3 more registers, (u − 1) × 3. Decrease: (700 − 550)/700 = 21.43 %.

Unrolling factor 4: copies 3 and 4 use F14/F16/F18 and F20/F22/F24 with displacements 8 and 12; ADDUI R1, R1, 16 and ADDUI R2, R2, 16. 25 iterations; 19 instructions per iteration; overhead 3; 475 instructions and 25 branches executed; (4 − 1) × 3 = 9 more registers, F8 … F24 — the same three registers F2, F4, F6 renamed three times. Decrease: (700 − 475)/700 = 32.14 %.

Best factor: 4. Iterations and branches halve again (50 → 25) and the overhead per useful add falls from 1.5 to 0.75 instructions. The price is 12 live FP registers instead of 6 and a 19-instruction body; factor 4 is preferable if the architectural register file holds the 12 live values without spilling and the code size is acceptable, otherwise factor 2 is the safer choice.

(a) R1 takes the values 80, 72, …, 8 at the top of the body: 80/8 = 10 iterations; 5 instructions per iteration, 2 of them overhead (SUBI, BNE); 50 instructions and 10 branches executed.

(b)

LOOP: LD    F0, 0(R1)
      FMUL  F4, F0, F2
      SD    F4, 0(R1)
      LD    F6, -8(R1)
      FMUL  F8, F6, F2
      SD    F8, -8(R1)
      SUBI  R1, R1, 16
      BNE   R1, R2, LOOP

(c) 5 iterations; 8 instructions per iteration; overhead still 2; 40 instructions and 5 branches executed. 2 more registers, (2 − 1) × 2: F0 → F6 and F4 → F8 in the second copy; F2 is only read and is not renamed. Decrease: (50 − 40)/50 = 20 %.

10 = 2 × 4 + 2: two iterations of the unrolled body (3 × 4 + 2 = 14 instructions each) and two iterations of the original body (5 each): 2 × 14 + 2 × 5 = 38 instructions, with 2 + 2 = 4 branches; the decrease is (50 − 38)/50 = 24 %, less than the 30 % the formula o(1 − 1/u)/(w + o) promises for u = 4, because the remainder pays full overhead.

SD F16, 8(R1): displacement = old displacement − (change of R1) = −24 − (−32) = 8.

Answer 2. The loop-carried dependence is S1 → S1 through X: iteration i reads X[i−1], produced by iteration i − 1. S2 depends on S1 within the iteration, and Y is read only.

False. Loop unrolling is a compiler transformation of the program text. Tomasulo issues the instructions of each iteration as they arrive, in order, each into its own reservation station with its own tag; because operands are tracked by tag and not by register name, the LD/FMUL/SD of iteration i + 1 can execute while those of iteration i are still waiting — the "dynamic loop unrolling effect" — but the code is never modified or replicated.

Dynamic instruction scheduling. The hardware decides at run time when each instruction executes, preserving the data flow: instructions issue in program order and wait in reservation stations until their operands are available, instead of stalling the pipeline behind the first one that must wait. Benefit: it adapts to latencies known only at run time, such as a cache miss. In the loop the second iteration's LD, FMUL and SD issue at cycles 6, 7 and 8 while the first LD is still missing; the same code runs well on different implementations. Cost: stations, tag-compare logic and a common data bus.

Reservation stations. Buffers in front of the functional units (Load1–3, Mult1–2, Store1–3 in the example) holding the operation, the operand values (Vj, Vk) or the tags of the stations that will produce them (Qj, Qk). An instruction enters a free station even when its operands are missing (the first FMUL at cycle 2 with Qj = Load1) and fires when they arrive on the CDB. Benefits: distributed hazard detection, operands read once, and the station names serve as tags for renaming. Limit: a station is held from issue to write result, so their number bounds the overlap; with two multiply stations the third FMUL cannot issue until cycle 15.

Dynamic register renaming. At issue, the station or buffer that will produce a result becomes the name of that result; the register result status maps each register to its youngest producer (F0: Load1, then Load2 from cycle 6; F4: Mult1, then Mult2). Readers record the tag, not the register, and the register file accepts a broadcast only from the youngest producer: at cycle 10 M[80] goes to Mult1 but not to F0. Benefit: WAR and WAW hazards disappear without stalls, so two iterations using the same F0 and F4 are in flight together (dynamic loop unrolling); only RAW dependences remain.

Out-of-order execution. Instructions execute and complete when their operands are ready, not in program order; issue stays in order. The second LD completes at cycle 10, before the first FMUL starts at 11. Benefit: long latencies (misses, FP operations) are overlapped with independent work, functional units stay busy and CPI drops. Requirements and limits: renaming against WAR and WAW; without a reorder buffer results reach the registers out of order, so exceptions are imprecise and nothing may execute past an unresolved branch.

Dependences: I0 — None. I1 — true data dependence with I0 for F0; output dependence with I0 for F0. I2 — true data dependence with I1 for F0. I3 — anti-dependence with I0 and I2 for R1. I4 — true data dependence with I3 for R1.

CPI = 15 / 5 = 3.0.

Iterations 1 and 2 do not change: no station is reused before cycle 15. Mult1 writes at 15 and is free at 16, so the third FMUL issues at 16 with both operands ready (F0 = M[64] since cycle 13), executes from 17 to 20 and writes at 21. The third SD issues at 17 into Store3, receives the product at 21, executes at 22 and writes memory at 23.

Answer 2. Only Mult1, whose Qj = Load1, captures M[80]; the register file writes F0 only if F0's status equals the broadcast tag, and since cycle 6 it equals Load2.

Answer 2: a structural hazard on the reservation stations. A station stays busy from issue to write result; Mult1 holds the first FMUL from cycle 2 to 15 because its load missed, Mult2 holds the second until 16. The third FMUL issues at 15, when Mult1 is freed, and in-order issue keeps the third SD behind it until 16.

False. The addresses differ and loads do not conflict with loads; the delay is structural — one memory unit, occupied by the miss from cycle 2 to 9. Memory disambiguation concerns a load and an earlier store to the same address.

Dynamic branch prediction and speculative execution. The outcome and target of a branch are predicted at fetch from run-time history (BHT, BTB). The instructions after the branch are fetched, issued and executed before the branch resolves; their results are forwarded among them through the CDB and the ROB but kept out of the architectural state until the branch is resolved and the instruction commits. On a misprediction the younger entries of the ROB are flushed and fetch restarts at the correct target. Benefit: branches no longer drain the pipeline, and the window of exploitable ILP spans several basic blocks. Cost: wasted work and recovery time on mispredictions, so accuracy matters.

Dynamic register renaming. Each issued instruction that writes a register gets a fresh name for its result — a reservation station in classic Tomasulo, a ROB entry in the speculative version; the rename table maps the architectural register to its newest producer, and a consumer issuing later takes that producer's value or its tag. Benefit: WAR and WAW (name) hazards disappear, so instructions and loop iterations can be overlapped freely and only true (RAW) dependences remain. Cost: a rename table to keep, to restore after a misprediction, and the copy of each value into the architectural register at commit.

Out-of-order execution. Instructions wait in reservation stations and start as soon as their own operands are ready, independently of program order; results are broadcast on the CDB. Issue and commit remain in order. Benefit: a stalled instruction — a cache miss, a long-latency FP operation — does not block independent later ones; functional units stay busy and CPI drops. It requires renaming against WAR/WAW hazards and in-order commit to keep exceptions precise.

Reorder buffer. A circular FIFO: an entry is allocated at issue in program order, written out of order at Write Result (value, ready bit) and drained in order at Commit from the head (head, ready, not speculative). It supplies operands between completion and commit, provides the names for renaming (the ROB number is the tag) and replaces the store buffers, keeping a store's address and data until commit. Benefits: precise exceptions, since nothing younger than a faulting instruction has touched the state; cheap misprediction recovery by discarding the entries after the branch; speculation made safe. Cost: a finite window — a stalled head stops issue when the buffer fills.

An exception is precise if (1) the processor can stop at a well-defined point corresponding to a specific instruction, (2) all previous instructions are fully committed, and (3) no subsequent instruction has modified the architectural state. With a reorder buffer, results are written to the ROB entry at Write Result, never directly to the register file or memory; only the head commits, in program order. An exception is recorded in the entry of the faulting instruction and taken when that instruction reaches the head: at that moment every older instruction has committed and every younger one is still in the buffer, so the younger entries are discarded and fetch restarts at the handler — the three conditions hold by construction. An exception raised on a mispredicted path never reaches the head: when the branch resolves, the entries after it are flushed together with the recorded exception, so it is never taken.

The third option: at Commit. The register file must reflect only instructions that are certainly part of the program's path; at Write Result the value goes to the ROB entry and to the waiting reservation stations.

True: 1, 3, 5, 6. False: 2 (the station is freed at Write Result, the ROB entry at Commit) and 4 (the tail points to the next free entry).

The Reorder Buffer. A speculative instruction's result is held only in its ROB entry (and in copies inside reservation stations), never in the register file or memory, and the entry is marked speculative. When the branch resolves as mispredicted: all ROB entries younger than the branch are invalidated and the tail is moved back to the entry after the branch; the reservation stations and load buffers working for them are squashed; the rename table is restored to the mapping valid at the branch, so that each register points to its older in-flight producer or to nothing; fetch is redirected to the correct target; the branch itself commits normally. Nothing has to be undone in the architectural state, because nothing speculative ever reached it.

(a) The ROB is full after four issues: head = tail = ROB0 and the entry is busy. In+3 is speculative because the BNE in ROB2 is unresolved; the BNE itself is not.

(b) In completes (Ready = Yes, value 10 in ROB0, Load1 released) and commits from the head: F0 = 10 in the register file, ROB0 freed, head ROB1, tail ROB0, and the mapping of F0 cleared. In+1 has captured F0 from the CDB and is executing.

(c) In+4 has meanwhile issued into ROB0 (FP3, speculative) and In+1 has committed (F2 = 20, head ROB2, tail ROB1). The BNE resolves as mispredicted: ROB3 and ROB0 are flushed, FP2 and FP3 released, the tail moves to ROB3, the mappings of F6 and F8 are cleared (no older producer is in flight), fetch restarts at the fall-through instruction. The branch is Ready at the head and commits next; the register file holds F0 = 10, F2 = 20 and was never touched by the flushed instructions.

(a) The outcome and target of a branch are predicted at fetch from run-time history (BHT, BTB); the instructions after the branch are fetched, issued and executed before the branch resolves, their results forwarded among themselves but kept out of the architectural state until the branch is validated; on a misprediction the younger instructions are flushed and fetch restarts. Benefit: branches no longer drain the pipeline, the window of exploitable ILP spans several basic blocks. Cost: wasted work and recovery time on a misprediction, so accuracy matters.

(b) Each issued instruction that writes a register gets a fresh name for its result — a reservation station in classic Tomasulo, a ROB entry in the speculative version; the rename (register status) table maps the architectural register to its newest producer, and consumers receive the value or its tag. Benefit: WAR and WAW (name) hazards disappear, instructions and loop iterations can be overlapped freely; only true RAW dependences remain.

(c) Instructions wait in reservation stations and start as soon as their own operands are ready, regardless of program order (data-flow execution), results being broadcast on the CDB. Benefit: a stalled instruction (cache miss, long FP latency) does not block independent later ones; functional units stay busy; CPI falls. It requires in-order commit to keep exceptions precise.

(d) A circular FIFO allocated at issue in program order, written out of order at write result (value, ready bit) and drained in order at commit from the head; it supplies operands between completion and commit, provides the names for renaming and replaces the store buffer (address and data kept until commit). Benefits: precise exceptions (nothing after the faulting instruction has touched the state), cheap misprediction recovery (discard the entries after the branch), safe speculation. Cost: a finite window — a blocked head stalls issue when the buffer fills.

Iterations: 40/4 = 10. Instructions per iteration: 5. Control vs datapath: 2 (ADDI, BNE) vs 3 (LD, FADD, SD). Unrolled by 2 with renaming (second copy on F6, F8 with offset +4; one ADDI of 8; one BNE): L0 LD F2, 0(R1); L1 FADD F4, F2, F2; L2 SD F4, 0(R1); L3 LD F6, 4(R1); L4 FADD F8, F6, F6; L5 SD F8, 4(R1); L6 ADDI R1, R1, 8; L7 BNE R1, R2, L0. Iterations 40/8 = 5; 8 instructions per iteration; 2 control vs 6 datapath.

Head = ROB0, tail = ROB0 (busy): full. Rename Table: F0 –; F2 ROB0 ROB8; F4 ROB1 ROB9; F6 ROB3; F8 ROB4 (and R1 → ROB6 if integer registers are listed). Load4 and FP4 remain free.

(a) ROB0 LD F0, 0(R1) · F0 · Load1 · No, exec.(*) · No; ROB1 FMUL F4, F0, F2 · F4 · Mult1 · No, issued · No; ROB2 SD F4, 0(R1) · Mem [0+R1] · – · No, issued · No; ROB3 SUBI R1, R1, 8 · R1 · Int1 · No, issued · No; ROB4 BNEZ R1, Loop · – · Int2 · No, issued · No; ROB5 LD F0, 0(R1) · F0 · Load2 · No, issued · Yes; ROB6 FMUL F4, F0, F2 · F4 · Mult2 · No, issued · Yes; ROB7 SD F4, 0(R1) · Mem [0+R1] · – · No, issued · Yes. Head = ROB0, tail = ROB0 (busy): full. Rename table: F0 ROB0 ROB5, F4 ROB1 ROB6, R1 ROB3.

(b) ROB5, ROB6, ROB7 are flushed (Busy = No); Load2 and Mult2 are released; head still ROB0 (the load has not committed), tail = ROB5; Rename table: F0 → ROB0, F4 → ROB1 (the older producers are still in flight), R1 → ROB3; fetch restarts at the instruction after BNEZ, which will take ROB5 with Spec = No; the BNEZ in ROB4 commits normally when it reaches the head.

Original: 96/4 = 24 iterations of 5 instructions. Unrolled by 4: 24/4 = 6 iterations of 4 · 3 + 2 = 14 instructions. Dynamic count: 6 × 14 = 84 (down from 120).

Answer 3: at commit. The register file must reflect only instructions that are certainly part of the program's path; at write result the value lives in the ROB entry and in the stations that captured it.

Answer 1, the Reorder Buffer. Every speculative result is held only in its ROB entry (and in station copies), marked speculative, never in the register file or memory. When the branch resolves wrong: the entries younger than the branch are invalidated and the tail goes back to the entry after the branch; their reservation stations and load buffers are squashed; the rename table is restored to the mapping valid at the branch; fetch is redirected to the correct path; the branch itself commits normally. Nothing has to be undone in the architectural state.

True: 1, 3, 5, 6. False: 2 (station freed at write result, entry at commit) and 4 (the tail is the next free entry).

1. The compiler analyses data dependences and resource constraints at compile time and decides which operations execute together and in which cycle; the hardware executes the schedule without checking it. Benefit: no dynamic scheduling hardware (no scoreboard, reservation stations or run-time dependence checks), hence less area and power; the compiler sees a much larger instruction window than any hardware. Cost: it must know all latencies and cannot see run-time events.

2. Independent operations are grouped into one very long instruction word; each slot corresponds to one functional unit (e.g. Memory, FP, Integer). Benefit: one fetch delivers k operations, decode is trivial (slot i goes to unit i, no arbitration), and scaling means adding slots.

3. When no independent operation is available for a slot, or a latency must elapse, the compiler fills the slot with a NOP. Benefit: the fixed format and the timing stay explicit, so no stall logic is needed. Cost: wasted slots and larger code; code efficiency = IC / (#cycles × #issues).

4. One PC fetches one bundle per cycle, and a bundle contains at most one branch. Benefit: a single next-PC decision per cycle keeps branch handling simple (in the exam's model the branch is solved in ID with one delay slot).

5. All the operations of a bundle read their operands in the same cycle, and every unit can write a result in every cycle: two read ports and one write port per operation, 8 + 4 for a 4-issue machine. Benefit: every unit gets its operands and writes its result without a bottleneck. Cost: area and power grow quickly with the number of ports, which leads to clustered VLIWs (several smaller register files, each serving a subset of the units).

6. Every unit accepts a new operation each cycle, and its result is available after a fixed latency (e.g. Memory 3, FP 3, Integer 1, 2 to a branch); the compiler places each consumer at least one latency after its producer and fills the gap with independent operations. Benefit: one operation per unit per cycle with no interlocks. Cost: the schedule, hence the binary, depends on the latencies of one implementation.

7. To remove WAR and WAW dependences the compiler writes results into different architectural registers. Benefit: more freedom to reorder and overlap operations, more ILP. Cost: register pressure — every result in flight needs an architectural register; when the register file saturates, values are spilled to memory.

8. The compiler cannot know whether a load will miss in the data cache or whether a static branch hint is wrong. On a miss the processor stalls; on a misprediction the hardware flushes the wrongly fetched bundles. Benefit: correct execution despite unpredictable events, while the regular flow stays free of checks. Cost: a stall freezes the whole schedule, which assumed the hit latency.

FADD at C1 + 3 = C4 (F2 from the memory unit); SD at C4 + 4 = C8 (F6 from the FP ALU); ADDUI in C8 with the SD, its last reader of R1 (read and write in the same cycle); BNE at C8 + 2 = C10; delay slot C11.

Critical path = 11 cycles. CPI = 11 / 5 = 2.2. FP ops per cycle = 1 / 11 = 0.09. Code efficiency = 5 / (11 × 3) = 0.15.

Old binary: SD F6, 0(R1) in C7 reads F6 one cycle before the 4-cycle FADD (issued in C4) writes it, so it stores the F6 of the previous iteration. A VLIW has no hardware that detects the RAW hazard.

False. One PC fetches one bundle per cycle; the bundle carries up to 4 operations in its 4 slots, one per functional unit, and at most one of them is a branch.

False. A basic block (straight-line code with one entry and one exit) holds only about 4 to 7 instructions, and its RAW chains limit the parallelism further. VLIW compilers therefore schedule larger regions: loop unrolling and software pipelining overlap loop iterations, trace scheduling schedules the most likely path through several basic blocks.

Answers 1, 2 and 3. Data hazards (RAW, WAR, WAW) and structural hazards are solved statically with known latencies and resources; cache misses and branch mispredictions are dynamic events handled by the hardware (stall, flush).

1. A straight-line sequence of instructions with one entry and one exit (only the last instruction may branch). All its instructions execute together, so the compiler can reorder them freely as long as the data dependences hold. It is the unit of local scheduling; its limit is its size — a few instructions between branches.
2. A DAG with one node per instruction and one edge per dependence: RAW (true), WAR and WAW (name dependences). RAW edges carry the producer's latency. It shows what may run in parallel (unconnected nodes) and what must wait, and it is the input of every scheduler.
3. The longest latency-weighted path from a source to a sink, LP(i) = max LP(p) + Lat(i). It is the minimum execution time of the block even with unlimited resources: no schedule can beat it. In the exam's VLIW exercise, "critical path for a single iteration" is answered with the length of the scheduled iteration, delay slot included.
4. Each operation is scheduled in the first cycle in which its operands are available, ignoring resources. It gives the lower bound (= the critical path) and the earliest cycle of every operation; it is not a valid schedule on a real machine, because it can use more units than exist.
5. ASAP plus resource constraints: in every cycle the ready instructions (operands available) are sorted by priority and the highest ones take the free units. It is greedy and fast, close to optimal on small graphs, and it is what a VLIW compiler — and the exam table — uses.
6. The priority of an instruction is the longest path from it to the end of the block, computed backwards from the sinks. Instructions with a long chain still ahead go first; instructions with slack fill the holes; ties are broken in program order.
7. A table of cycles × functional units recording which unit is busy in which cycle. The scheduler checks it before placing an instruction, so no unit is oversubscribed (with fully pipelined units: one new instruction per unit per cycle). Read row by row, it gives the bundles.
8. Local scheduling works inside one basic block (ASAP, list scheduling; unrolling and software pipelining reshape a loop body); it is simple but limited by the block. Global scheduling moves instructions across branches (trace and superblock scheduling): more ILP, at the cost of compensation code and a more complex compiler.

Dependences: LD F2 → FADD F6 (RAW F2, 3) → SD F6 (RAW F6, 3); LD F4 → FADD F4 (RAW F4, 3); FADD F8 → SD F8 (RAW F8, 3); ADDUI R1 after LD F2 and SD F6 (WAR R1, same cycle allowed); ADDUI R2 after LD F4 and SD F8 (WAR R2); BNE at least 2 cycles after ADDUI R1.

Critical path for a single iteration: 10 cycles (LD F2 → FADD F6 → SD F6 / ADDUI R1 → BNE → delay slot). Code efficiency = 10 / (10 × 3) = 0.33. (CPI = 10/10 = 1; FP ops per cycle = 3/10 = 0.3.)

Inside the body there is no RAW chain except ADDUI R1 → BNE: each SD stores a value computed in the previous iteration, each FADD reads a value loaded in the previous iteration. Only WAR edges remain (SD F6 before FADD F6, FADD F6 before LD F0, the SD and LD of each pointer before its ADDUI), and the same cycle is allowed for all of them.

Critical path for a single iteration: 5 cycles. CPI = 5/13 ≈ 0.38. FP ops per cycle = 3/5 = 0.6. Code efficiency = 13 / (5 × 4) = 0.65.

Answer 2. The critical path is a resource-independent lower bound; resources and priorities can only make the schedule equal to it or longer.

Answers 1, 4 and 5: they give 13, 12 and 13 cycles. Answers 2 and 3 leave 14: the units they add are never waited for.

False. LP(i) = max LP(p) + Lat(i) contains latencies and edges only; the number of functional units changes the list schedule, not the critical path.

(1) Loop unrolling replicates the loop body u times in one block, adjusts the displacements of the copies (0, 8, 16, …) and keeps a single index update and a single branch. The compiler renames the registers of each copy, removing the WAR and WAW dependences between copies, so the scheduler can interleave u independent chains and hide latencies. Benefits: fewer branches and index updates per element, fewer stalls, more operations per bundle (x[i] = x[i] + s: 10 cycles per element → 3.5 on a single-issue pipeline with a delay slot). Costs: code size, (u − 1) times the registers a copy writes, a remainder loop when the trip count is not a multiple of u.

(2) Software pipelining reorganises the loop so that each execution of the body contains stages of different iterations — store of i, compute of i + 1, load of i + 2 — in reverse order. The true dependences of an iteration no longer lie inside one body; only anti-dependences and the loop control do. A prologue fills and an epilogue drains the pipeline. Benefits: one iteration completes per execution of the body, with the body's original size and the same registers (June 2026: LOOP1 10 cycles, LOOP2 5 cycles, CPI speed-up 2). Costs: prologue and epilogue code, extra registers when a value must live longer than one pass, at least as many iterations as stages, compiler complexity.

(3) Trace scheduling is global scheduling across basic blocks: profiling selects the most likely path (the trace, acyclic), which is list-scheduled as one block; instructions move across branches (above them speculatively) and across joins. Compensation code — copies of moved instructions on the off-trace exit and entry paths — keeps the other paths correct. Benefits: fills wide instructions beyond the 4 to 7 instructions of a basic block and starts long-latency loads early. Costs: code growth from compensation code, slower off-trace paths, dependence on predictable branches, a complex compiler; stores and instructions that may raise exceptions cannot be speculated freely.

(4) Superblock scheduling restricts the region to a single entry and multiple exits, obtained by tail duplication: the part of the trace below a side entrance is copied for the entering path. Moves then need compensation only at the exits, outside the superblock, so speculation is simpler and safer. Cost: the duplicated code.

(5) Predication removes a branch instead of scheduling around it: a compare sets a predicate register and its complement, and the instructions of each arm are guarded by one of them — always issued, but writing their result only when their predicate is true. The control dependence becomes a data dependence on the predicate, so both arms form one larger basic block that the scheduler can fill, with nothing to mispredict and no compensation code. Cost: both arms take issue slots on every pass, so it pays only for short, balanced, hard-to-predict branches; it needs predicate registers in the ISA (IA-64).

There is no true dependence among the SDs, FADDs and LDs: each SD reads the value its FADD rewrites (WAR), each FADD reads the value its LD rewrites (WAR), and every ADDUI may share the cycle of the last instruction that reads its register. The integer unit has four instructions to issue (three ADDUI and BNE), so each stream's SD and LD are placed together to free its ADDUI as early as possible.

Critical path = 5 cycles. CPI = 5/13 ≈ 0.38. FP ops per cycle = 3/5 = 0.6. Code efficiency = 13/(5 × 4) = 0.65.

(a) With R3 = initial R1 + 8n:

LOOP: LD    F0, 0(R1)
      FADD  F4, F0, F2
      SD    F4, 0(R1)
      ADDUI R1, R1, 8
      BNE   R1, R3, LOOP

(b) SD F4, 0(R1): iteration i, whose sum was computed in the previous pass. FADD F4, F0, F2: iteration i + 1, whose operand was loaded in the previous pass. LD F0, 16(R1): iteration i + 2 — two strides ahead, 16 = 2 × 8.

(c) FINISH_UP: SD F4, 0(R1) (element n − 2); FADD F4, F0, F2 (element n − 1); SD F4, 8(R1) (element n − 1).

(d) The body handles i = 0 … n − 3: it runs n − 2 = 98 times. R5 = initial R1 + 8 × 98 = R1 + 784, the address of element 98.

LOOP1 does not change: its chain LD (C1) → FADD (C4) → SD with ADDUI (C7) → BNE (C9) → delay slot (C10) uses one memory unit at a time. 10 cycles, CPI = 10/5 = 2.

LOOP2: SD F6, 0(R2) and LD F2, 8(R2) both fit in C1 (two memory units, two different addresses), with FADD F6 (WAR on F6 and F2) and ADDUI R2 (WAR on R2) in the same cycle; BNE in C3, delay slot in C4. 4 cycles, CPI = 4/5 = 0.8.

Strip mining. The loop has 260 elements and a vector register holds 32: 260 = 8 × 32 + 4, so a first strip of 4 elements and then eight strips of 32, setting VLR for each strip.

False. Each execution of the body finishes one iteration, so the throughput is one iteration per initiation interval — 5 cycles for LOOP2 on the 3-issue VLIW of June 2026, 8 cycles for the midterm's SP_LOOP.

Answers 1, 2 and 4.

1. A layered memory system: small, fast, expensive levels close to the processor (registers; L1, L2, L3 caches in SRAM) and large, slow, cheap levels further away (main memory in DRAM, disk). Each upper level holds a subset of the level below. Benefit: the processor sees one large memory with an average access time close to that of the fastest level, at a cost per bit close to that of the cheapest (the illusion of a large, fast memory). It works only because programs have locality. Registers are managed by the compiler, caches by hardware, main memory and disk by the operating system.

2. A location accessed now is likely to be accessed again soon (an accumulator in a loop, the instructions of a loop body). Exploited by keeping recently used blocks in the cache and, when space is needed, replacing the least recently used one (LRU), so that the repeated accesses hit. Benefit: after the first access the reused word costs only the hit time; the cache needs enough capacity to keep the block until the reuse comes.

3. After a location, nearby locations are likely to be accessed soon (array elements a[i], a[i+1]; sequential instructions). Exploited by transferring whole multi-word blocks: one miss brings the neighbours, whose accesses then hit (8 doubles in a 64-byte block: 1 miss, 7 hits). Benefit: one miss penalty is shared by several accesses; if the neighbours are never used, a larger block only makes each miss longer.

4. The smallest unit transferred between memory and cache, typically 32 to 128 bytes; number of blocks = cache size / block size (64 KB / 16 B = 4096). Benefit: one transfer serves several accesses (spatial locality). Cost: a larger block makes each miss longer.

5. Hit time: time to access the cache, determine whether it is a hit and return the data (1 to 3 cycles for L1). Miss penalty: extra time to fetch the block from the lower level, write it into the cache and resume the CPU (tens to hundreds of cycles). On a miss the CPU stalls, the block is fetched and written, and the access is retried; miss time = hit time + miss penalty.

6. AMAT = Hit Rate × Hit Time + Miss Rate × (Hit Time + Miss Penalty) = Hit Time + Miss Rate × Miss Penalty, because Hit Rate + Miss Rate = 1: every access pays the hit time, the misses add the penalty. The miss rate is a fraction (5% = 0.05): 1 + 0.05 × 100 = 6 cycles. Benefit: one number that combines the three parameters and shows the three ways to improve a cache: reduce the hit time, the miss rate or the miss penalty.

7. Split L1: separate I-cache and D-cache, so the pipeline can fetch an instruction and access data in the same cycle (no structural hazard). AMAT = %Instr × (HT + MR_I × MP) + %Data × (HT + MR_D × MP), with %Instr = 1/(1 + d) and %Data = d/(1 + d), d = loads/stores per instruction. Unified: one cache shared flexibly between code and data, usually a lower miss rate for the same total size, but with one port every data access stalls one cycle. Example: unified 1.99% against split 2.10% miss rate, yet AMAT 2.245 against 2.05 cycles: the split cache is better there because of the port, and the comparison must be made on AMAT.

8. SRAM: six transistors per bit, fast but large and expensive per bit, used for the caches. DRAM: one transistor and a capacitor per bit, dense and cheap but slower, and it must be refreshed; used for main memory (SDRAM and DDR are DRAM). No single technology is both fast and big, which is why the hierarchy combines them.

1. Per instruction: 1 fetch + 0.25 data accesses = 1.25 accesses. %Instr = 1 / 1.25 = 0.80 (80%); %Data = 0.25 / 1.25 = 0.20 (20%).

2. MR_Harvard = 0.8 × 0.01 + 0.2 × 0.06 = 0.008 + 0.012 = 0.020 (2.0%), higher than the unified 1.8%.

3. AMAT_Harvard = 0.8 × (1 + 0.01 × 50) + 0.2 × (1 + 0.06 × 50) = 0.8 × 1.5 + 0.2 × 4 = 1.2 + 0.8 = 2.0 cycles. AMAT_unified = 0.8 × (1 + 0.018 × 50) + 0.2 × (1 + 1 + 0.018 × 50) = 0.8 × 1.9 + 0.2 × 2.9 = 1.52 + 0.58 = 2.1 cycles.

4. The Harvard organisation is better, 2.0 against 2.1 cycles, although its miss rate is higher (2.0% against 1.8%). The unified cache saves (0.020 − 0.018) × 50 = 0.1 cycles per access on misses but loses 0.2 × 1 = 0.2 cycles per access in structural-hazard stalls on its single port. The comparison is decided by AMAT, not by the miss rate.

AMAT = Hit Time + Miss Rate × Miss Penalty ⇒ 3 = 1 + Miss Rate × 100 ⇒ Miss Rate = 2 / 100 = 0.02 (2%).

Answer 2: AMAT = 1 + 0.05 × 100 = 6 clock cycles.

Answers 1, 2 and 4.

False. A unified cache usually has the lower miss rate for the same size; it loses only when the structural-hazard stalls on its single port cost more than its miss-rate advantage saves (Example 6: 0.25 cycles against about 0.05 per access). With two ports, or a large enough miss penalty (above about 233 cycles with the numbers of Example 6), it wins.

(a) Each memory block can be placed in exactly one cache line, line = block address mod #blocks: the index bits select the line and a single tag comparison decides hit or miss. Benefit: the simplest and fastest organisation — one comparator, no replacement decision, and the data can be read while the tag is being checked. Cost: conflict misses — two blocks with the same index evict each other at every access (blocks 12 and 20 in an 8-line cache), even while other lines are empty.

(b) A block may be placed in any line: there is no index, the whole block address is the tag, and the address tag is compared with the tags of all lines in parallel. Benefit: no conflict misses, and full freedom for the replacement policy. Cost: one comparator per line plus the logic that selects the matching line — expensive in area and energy, and slower, so it is used only for small caches and buffers.

(c) The cache is divided into sets of n lines (ways); a memory block maps to exactly one set, set = block address mod #sets, and may occupy any of its n ways. Benefit: far fewer conflict misses than direct-mapped (two blocks with the same index can coexist) at a much lower cost than fully associative, since only the n tags of one set are compared. Cost: n comparators and an n-way multiplexer, so a slightly longer hit time and more energy.

(d) The address is split into tag | index | offset: offset = log2(block size), index = log2(#sets), tag = the remaining high-order bits. The index selects the set, the n stored tags of that set are compared with the address tag in parallel, and a way hits if its tag is equal and its valid bit is 1; the offset then selects the word. Benefit: one parallel lookup; only the tag is stored, since index and offset are implied by the position; the valid bit prevents false hits at cold start.

(e) On a miss into a full set, the block whose last use (read or write, hit or fill) is oldest is evicted; the order of use is updated on every access. Benefit: it exploits temporal locality — recently used blocks are likely to be used again — so it usually misses less than FIFO or random. Cost: state per set grows as log2(n!) bits and must be updated on every hit, so highly associative caches use pseudo-LRU or random.

(f) A write updates only the cache line and sets its dirty bit; main memory is updated with the whole block only when a dirty block is evicted. Benefit: many writes to the same block cost one memory write, less memory traffic and writes at cache speed. Cost: a dirty bit per line, memory stale until eviction, and a miss that evicts a dirty block must write it back as well.

(g) Every write updates the cache (on a hit) and main memory; a small FIFO write buffer holds the pending writes so the processor continues while they drain to memory, stalling only if the buffer is full. Benefit: memory is always up to date, simple control, no write-back on eviction. Cost: one memory transaction per store, so high traffic; without the buffer every store would stall for a memory write.

(h) On a write miss, write allocate fetches the block into the cache and then writes it (as a read miss would); no write allocate writes the word directly to memory and leaves the cache unchanged. Write allocate is paired with write-back: once allocated, further writes to the block hit and generate no traffic. No write allocate is paired with write-through: every write goes to memory anyway, so fetching the block would only add traffic; it also keeps data that is written once and not read soon from evicting useful blocks.

Answer 3. Offset = log2(256) = 8 bits; number of blocks = 2^20 / 2^8 = 2^12; number of sets = 2^12 / 4 = 2^10, so index = 10 bits; tag = 32 − 10 − 8 = 14 bits.

Sets = 8 / 4 = 2 (Answer 1). The 5-bit block address = 4-bit tag | 1-bit set: set = address mod 2, tag = address div 2. Set 0 = lines a–d, set 1 = lines e–h; a free line is taken in alphabetical order, otherwise the LRU line of the set. "Yes (14)" means: the evicted block 14 is dirty and is written back to memory. The last column is scratch work, not a column of the paper.

Miss rate = 8 / 10 = 80 % (two hits: accesses 4 and 5). Final cache: a = 4 (dirty), b = 6, c = 30 (dirty), d = 18 (dirty), e = 7 (dirty), f–h empty.

Sets = 8 / 2 = 4: set = address mod 4 (the two last bits), tag = address div 4 (3 bits). Set 0 = a, b; set 1 = c, d; set 2 = e, f; set 3 = g, h.

Miss rate = 8 / 10 = 80 %. Written back: blocks 14, 16 and 18.

Offset = log2(64) = 6 bits; blocks = 65 536 / 64 = 1024; sets = 1024 / 4 = 256, so index = 8 bits; tag = 32 − 8 − 6 = 18 bits. Check: 32 − log2(64 KB / 4) = 32 − 14 = 18.

Answers 2, 3 and 5. Answers 1 and 4 describe write-through.

False. LRU evicts the least recently used block; the block that arrived first is the FIFO victim. Before access 8 of the July 2024 sequence, set 0 holds 16 (in at 1, last used 5) and 14 (in at 2, last used 4): FIFO evicts 16, LRU evicts 14.

CPI = CPI_exec + memory accesses per instruction × miss rate × miss penalty, with CPI_exec = 8 clock cycles.

1. CPI3_ideal_cache = 8 + 3 × 0 × 3 = 8.

2. Stall cycles per instruction = 3 × 0.5 × 3 = 4.5; CPI3_real_cache = 8 + 4.5 = 12.5. Same IC and same clock, so the ratio of the CPU times is the ratio of the CPIs: 12.5 / 8 = 1.5625. With the real cache CPU3 takes 56.25% more time; the ideal cache would be 1.56 times (56.25%) faster.

3. Stall cycles per instruction = 3 × 1 × 3 = 9; CPI3_no_cache = 8 + 9 = 17. 17 / 12.5 = 1.36: without a cache CPU3 takes 36% more time than with the real cache (the real cache is 1.36 times faster); against the ideal cache, 17 / 8 = 2.125.

1. Miss Rate L1 = 40 / 1000 = 0.04 (4%); local Miss Rate L2 = 20 / 40 = 0.5 (50%); global Miss Rate L2 = 0.04 × 0.5 = 20 / 1000 = 0.02 (2%).

2. AMAT = 1 + 0.04 × (10 + 0.5 × 200) = 1 + 0.04 × 110 = 5.4 clock cycles.

3. Stall cycles per instruction = 1.5 × (0.04 × 10 + 0.02 × 200) = 1.5 × (0.4 + 4) = 6.6 (check: 1.5 × (5.4 − 1) = 6.6). CPI = 1.0 + 6.6 = 7.6.

4. Without L2: stall cycles per instruction = 1.5 × 0.04 × 200 = 12; CPI = 13 (AMAT = 1 + 0.04 × 200 = 9). Speed-up due to L2 = 13 / 7.6 = 1.71.

Answer 2. Miss Rate L1 = 1 − 0.95 = 0.05. The L2 hit rate of 90% is local, so the L2 misses 0.10 of the accesses that reach it. Global miss rate of the last-level cache (L2) = 0.05 × 0.10 = 0.005 = 0.5%: one access in 200 goes to main memory. The clock and the hit times are not needed.

AMAT = Hit Time L1 + Miss Rate L1 × (Hit Time L2 + Miss Rate L2 × Miss Penalty L2) = 1 + 0.05 × (5 + 0.10 × 15) = 1 + 0.05 × 6.5 = 1.325 clock cycles (1.325 ns at 1 GHz).

Answers 3 and 4. Answer 1 reduces the miss rate (fewer conflict misses). Answer 2 reduces the hit time: the cache is indexed while the TLB translates. Answer 3 makes an L1 miss cost an L2 access instead of a memory access. Answer 4 serves a read miss before the pending writes complete (after checking the write buffer for the same address), so the read waits less.

Answers 1, 2 and 5.

1. A larger, slower cache between L1 and main memory (hundreds of KB to MBs, SRAM, usually unified, on chip). It catches L1 misses before they reach DRAM, so the L1 miss penalty becomes Hit Time L2 + Miss Rate L2 × Miss Penalty L2 instead of the memory latency. Benefit: L1 stays small and fast while its misses become cheap (Example 8: AMAT 6 → 2.5 cycles). It does not change the L1 miss rate; it pays off only if its hit time plus its own misses cost less than the trip to memory.

2. Local miss rate = misses of a level / accesses to that level; global miss rate = misses of a level / all CPU accesses; for L2, local = L2 misses / L1 misses and global = Miss Rate L1 × local Miss Rate L2. Example: 1000 accesses, 40 L1 misses, 20 L2 misses → 4%, 50% local, 2% global. The global rate measures the accesses that reach memory and is comparable across hierarchies; the local L2 rate is high because L1 has already served the easy accesses.

3. Nest the one-level formula: AMAT = Hit Time L1 + Miss Rate L1 × Miss Penalty L1, with Miss Penalty L1 = Hit Time L2 + Miss Rate L2 × Miss Penalty L2 (local rate). Expanded: every access pays Hit Time L1, the L1 misses pay Hit Time L2, the misses in both pay Miss Penalty L2. Example: 1 + 0.04 × (10 + 0.5 × 200) = 5.4 cycles, against 9 without L2.

4. CPU time = IC × (CPI_exec + memory stall cycles per instruction) × T_CLK; stall cycles per instruction = memory accesses per instruction × miss rate × miss penalty (misses per instruction × penalty). With L1 and L2: MAPI × (Miss Rate L1 × Hit Time L2 + Miss Rate L1 × Miss Rate L2 × Miss Penalty L2) = MAPI × (AMAT − Hit Time L1). Example: CPU3, 8 + 3 × 0.5 × 3 = 12.5. Benefit: it predicts the effect of the memory system on execution time, and shows that a faster core loses a larger share of its time to the same misses.

5. The first access to a block (cold start); they occur even in an infinite cache. Reduced by larger blocks (one miss brings the neighbours) and by prefetching; larger blocks raise the miss penalty.

6. The working set does not fit, so blocks are evicted and needed again: the misses of a fully associative cache of the same size, minus the compulsory ones. Reduced by a larger cache, at the cost of hit time, area and power.

7. Blocks that map to the same set evict each other although other lines are free: the misses of the real cache minus those of a fully associative cache of the same size. Reduced by higher associativity (more comparators, longer hit time) or a victim cache. Example: blocks 12 and 20 in a direct-mapped cache of 8 blocks, 100% miss rate, against 33% fully associative.

8. From AMAT = Hit Time + Miss Rate × Miss Penalty: reduce the miss rate (larger caches and blocks, higher associativity, prefetching, compiler optimizations), reduce the miss penalty (multilevel caches, priority to read misses over writes, early restart and critical word first, non-blocking caches), reduce the hit time (small and simple L1, avoiding address translation with virtually indexed, physically tagged caches, pipelined writes). Most techniques move two terms (bigger cache: miss rate down, hit time up; bigger block: miss rate down, miss penalty up), so each choice is a trade-off judged on AMAT.

1. Larger block size: a miss brings in the neighbouring words too, exploiting spatial locality, so compulsory misses decrease. For a fixed cache size there are fewer blocks, so beyond an optimum conflict and capacity misses grow (U-shaped miss rate), and the miss penalty grows with the block (latency + transfer). The AMAT-optimal block is at or below the miss-rate-optimal one; common sizes are 16–64 bytes.

2. Higher associativity: a block can be placed in any of the n ways of its set, so blocks with the same index can coexist: conflict misses decrease, compulsory and capacity misses do not change. Rules of thumb: a direct-mapped cache of size N misses about as often as a 2-way cache of size N/2; 8-way is practically fully associative. Cost: the way-select multiplexer must wait for the n tag comparisons, so the hit time (clock cycle) and the power grow; for large caches AMAT can increase.

3. Victim cache: a small (4–16 entries) fully associative buffer between the cache and the next level, holding the blocks recently evicted. On a miss it is checked; on a hit there the block is swapped back into the cache. It removes many conflict misses of a direct-mapped cache (a few blocks that keep evicting each other) without changing the hit time of the main cache; low cost. Seen from the main cache, it makes those misses cheap (miss-penalty view).

4. Way prediction: a small table indexed by the set index stores, for each set, the way that hit last (log2 n bits). Only the predicted way is read and its data is sent out at once, as in a direct-mapped cache; one tag comparison confirms it. On a mismatch the other ways are checked (+1–2 cycles); the table is updated on every wrong prediction, misses included. Benefit: hit time and energy close to direct-mapped with the miss rate of a set-associative cache (accuracy 80–95 %). It does not reduce the miss rate.

5. Pseudo-associativity: a direct-mapped cache where each block has a second possible line (e.g. the index with its MSB flipped). Check the primary line (1-cycle hit), then the secondary (slow hit, +1 cycle), then miss. Two blocks with the same index can now both stay, one in each line (the pair of lines acts as one 2-way set), so it removes many conflict misses with little hardware; cost: two different hit times, harder to pipeline; blocks are swapped so that the most recently used one is in the primary line.

6. Hardware prefetching: on a miss on block X the hardware fetches X into the cache and X+1, X+2, … into a stream buffer next to it (instruction stream buffer for sequential code, data stream buffers for sequential or strided accesses). If the next access finds the block in the buffer, it is moved into the cache and the following one is prefetched. It removes compulsory (and some capacity) misses by overlapping memory accesses with execution; the separate buffer avoids polluting the cache with wrong guesses. Cost: memory bandwidth, useless prefetches.

7. Software prefetching: the compiler inserts prefetch instructions ahead of the use (e.g. prefetch A[i+8] while using A[i]), at a distance of about miss latency / cycles per iteration. Cache prefetch (into the cache, not a register) is the common form; the prefetch must be non-faulting and the cache non-blocking, so that execution continues while the block arrives. Benefits: removes compulsory/capacity misses of predictable patterns the hardware may not detect, tunable by profiling. Costs: extra instructions (issue slots), bandwidth; too close is useless, too far may be evicted.

8. Loop interchange swaps nested loops so that the inner loop walks memory sequentially (row-major C arrays: inner loop on the last index), so each block fetched serves all its words before eviction (e.g. 16 times fewer misses with 4-byte words and 64-byte blocks). Loop blocking (tiling) splits a computation that reuses data, such as matrix multiplication, into B × B tiles that fit in the cache, so that each tile is reused before eviction: words moved go from 2N³ + N² to 2N³/B + N². Both reduce capacity (and conflict) misses at no hardware cost; they must respect the data dependences.

Miss penalty = 80 + 2 × (B/16) clock cycles; AMAT = 1 + Miss rate × Miss penalty.

The minimum AMAT is 1.93 clock cycles with 64-byte blocks, although the lowest miss rate is at 128 bytes: from 64 to 128 bytes the miss rate drops only from 1.06 % to 1.02 % while the miss penalty grows from 88 to 96 cycles.

(a) Direct-mapped: 8 sets, Set = address mod 8, Tag = address div 8 (2 bits); set k is cache address a + k (set 3 = d, set 5 = f).

Miss rate = 8/8 = 100 %.

(b) 2-way: 4 sets, Set = address mod 4, Tag = address div 4 (3 bits); set 0 = a, b; set 1 = c, d; set 2 = e, f; set 3 = g, h.

Miss rate = 4/8 = 50 %.

(c) The four conflict misses of (a), rows 3, 4, 6 and 8, become hits. Blocks 3 and 11 share a set in both caches (and so do 5 and 13), but the 2-way set holds both, while the direct-mapped line holds one at a time. The four cold-start misses remain: associativity does not remove compulsory misses. The two write-backs of (a) disappear too, because no dirty block is evicted.

(d) 4: only the cold-start misses (accesses 1, 2, 5, 7). Each conflict miss of (a) finds its block in the victim cache, where the previous access to the same line put it (access 6 finds block 3, evicted by access 4), and swaps it back into the line.

Number of sets = 32 768 / (64 × 8) = 64. Each entry names one of 8 ways: log2 8 = 3 bits. Table size = 64 × 3 = 192 bits (24 bytes).

Answers 1, 2 and 3.

Answer 2.

False. A compulsory miss is the first access to a block. These transformations change only the order of the accesses (and the loop structure), not the set of blocks the program touches, so the number of first accesses is unchanged. They reduce capacity (and conflict) misses: a block is used completely (interchange) or reused (fusion, blocking) before it is evicted.

1. A read miss soon stalls the processor, because the following instructions need the data; a write can wait in the write buffer. So when a read miss competes with pending writes, the read is served first. In a write-through cache the read miss first compares its address with those in the write buffer: on a match it takes the data from the buffer, because memory still holds the old value (a RAW hazard through memory); with no match it goes to memory ahead of the buffered writes. In a write-back cache a dirty victim is copied into the write buffer, the new block is fetched at once and the victim is written back afterwards. Benefit: the read-miss penalty no longer includes writes nobody waits for. Cost: comparators on the buffer; a full buffer still stalls.

2. Each block is divided into sub-blocks, each with its own valid bit, under a single tag. On a miss only the requested sub-block is fetched; the others stay invalid until needed, and a hit requires both the tag match and the sub-block's valid bit. Benefit: the tag storage of a large block with the transfer time of a small one, so a lower miss penalty and less bandwidth, useful with large blocks or weak spatial locality. Cost: extra valid bits and control; less spatial locality exploited, so neighbouring words may miss later.

3. The block is fetched in normal order, but the requested word is sent to the processor as soon as it arrives and the processor resumes while the rest of the block is filled in the background. With a latency L before the first word, one word per cycle, n words per block and the requested word at position k (from 0), the stall falls from L + n to L + k + 1 cycles. Benefit: no change to the memory; the gain is larger when the word is early in the block.

4. Critical word first (wrapped fetch) asks the memory for the requested word first and then for the rest of the block, wrapping around (W2, W3, W0, W1). The stall is L + 1 cycles whatever the position of the word. Benefit: the largest gain when the word is late in the block. Cost: wrap-around fetch logic and a memory that supports it. Both 3 and 4 pay mainly with large blocks, where the transfer is a large part of the penalty, and both gain less when the processor soon needs another word of the block.

5. A blocking cache stalls the processor on a miss even if the next accesses would hit. A non-blocking (lockup-free) cache keeps serving accesses while misses are outstanding, each tracked in a Miss Status Holding Register (MSHR). Hit under miss: hits proceed while one miss is pending. Miss under miss: several misses are serviced in parallel (memory-level parallelism), with several MSHRs and a memory that accepts several requests. Benefit: the miss penalty is overlapped with useful work and with other misses, so the effective miss penalty drops; each miss itself is not shorter. It needs a processor with independent work, such as an out-of-order core. Cost: MSHRs, complexity, memory ordering.

6. An L2, larger and slower than L1 but much faster than main memory, catches most L1 misses: AMAT = L1 Hit Time + L1 Miss Rate × (L2 Hit Time + L2 Miss Rate × L2 Miss Penalty), with the local L2 miss rate; the bracket is the new L1 miss penalty. Example: 0.05 × (10 + 0.10 × 100) adds 1 cycle per access instead of 0.05 × 100 = 5. Design: much larger (hundreds of KB to MBs), more associative (8 to 16 ways), usually write-back, its slower hit time acceptable because it is not on the processor's critical cycle. Cost: every L1 miss pays the L2 lookup; area and power.

7. Inclusive: L2 holds a copy of every block in L1, so a coherence check in a multiprocessor can rely on L2 alone; the price is duplicated capacity. Exclusive: a block is either in L1 or in L2, never in both, so the total capacity is the sum of the two. Non-inclusive non-exclusive (NINE): no strict relation. In multicores a private L2 per core reduces contention and a shared L3 helps sharing and coherence.

8. In a write-through cache every store goes to memory through the write buffer; without merging, stores to adjacent addresses each become a memory transaction. A merging write buffer keeps block-sized entries with the aligned block address, a data field and a byte-valid mask; a store to a block already in the buffer is written into its entry instead of taking a new one. Benefit: fewer and larger transactions, less bus contention, so read misses wait less for the bus and the buffer fills less often. Cost: matching logic and masks; a partial entry needs a byte-enabled write or a read-merge-write; a full buffer still stalls.

Answers 3 and 4. Answer 1 reduces the miss rate (conflict misses); Answer 2 reduces the hit time; Answer 3 replaces most trips to main memory with an L2 access; Answer 4 lets a read miss start its fetch without waiting for pending writes.

Answer 1. Full block: L + n = 30 + 8 = 38. Early restart: L + k + 1 = 30 + 5 + 1 = 36. Critical word first: L + 1 = 31.

False. A non-blocking cache keeps serving hits and starts further misses while one is outstanding (tracked in MSHRs). Each miss takes as long as before; the processor simply does other work, so the stall it sees, the effective miss penalty, is smaller.

For comparison: full-block fetch 40 + 16 = 56, critical word first 40 + 1 = 41.

Miss Rate L1 = 1 − 0.95 = 0.05; Miss Rate L2 (local) = 1 − 0.90 = 0.10.

1. The L1 miss penalty, in clock cycles:

2. The AMAT, in clock cycles:

3. The global miss rate of L2, the last-level cache:

4. Without L2, in clock cycles:

5. Speed-up of the average access: 6 / 2 = 3.

With merging: 2 entries and 2 transactions, one full 32-byte write for E0 and one partial 16-byte write for E1 (with byte enables, or a read-merge-write if the bus has none). Without merging: 6 transactions, one per store; the 4-entry buffer is full after the fourth store, so the fifth and the sixth store stall the CPU until an entry has been written to memory.

1. The virtual and the physical address spaces are divided into pages of one fixed size (for example 4 KB). Each process sees a large, private, contiguous virtual space; the OS maps its pages onto physical frames anywhere in RAM. A virtual address is VPN | page offset; translation replaces the VPN with the PFN and leaves the offset unchanged. Benefits: programs larger than RAM (main memory acts as a cache for the disk), protection and isolation between processes, relocation, sharing of frames; fixed-size pages avoid external fragmentation. Cost: a translation on every access.

2. Each process has a page table in memory, indexed by the VPN; each entry holds the PFN, a valid bit, a dirty bit, a use bit and protection bits. The same virtual address in two processes maps to different frames (isolation), two VPNs may point to one frame (sharing), and the hardware enforces the permissions. Because a page fault costs millions of cycles, placement is fully associative (any frame), replacement approximates LRU with the use bit, and the write policy is always write-back with the dirty bit. Cost: memory for the tables, hence multi-level tables.

3. A small, fast, fully or highly associative cache of recent translations: tag = VPN, data = PFN and the flags. It is looked up on every access; on a hit the physical address is available in about one cycle, with the protection check. Benefit: without it every access would need an extra memory access to read the page table. Cost: it must stay tiny (tens of entries) to answer within the cycle.

4. On a TLB miss the page table is walked in memory, by a hardware walker or a software handler, in tens of cycles; if the entry is valid it is inserted into the TLB and the access completes, with no OS involvement for a hardware walker. If the entry is invalid, the page is not in RAM: a page-fault exception transfers control to the OS, which chooses a frame (writing back a dirty victim), reads the page from the disk, updates the entry and restarts the faulting instruction; this costs millions of cycles and requires precise exceptions. A TLB miss is not a page fault.

5. The cache index is taken from the virtual address and the tag from the physical address. The set is read while the TLB translates the VPN; the PFN is then compared with the tags of the set. Benefit: the TLB latency leaves the hit time, max(TLB, set read) + compare instead of TLB + cache, for example 1 cycle instead of 2 (notes, p. 360); since most accesses are hits, the AMAT drops. The TLB is still read on every access, for the tag and the permissions. Cost: the size restriction of point 7.

6. Translation never changes the page offset, so index and block-offset bits taken from it are the same in the virtual and the physical address and can be used before the TLB answers (the page offset trick). It also solves synonyms, two virtual addresses mapped to one physical address (shared memory, mapped files): all aliases select the same set and, with physical tags, match the same line, so only one copy exists and no stale value can be read. A VIVT cache could keep two copies with different virtual tags.

7. All index bits must lie in the page offset: index bits + block-offset bits ≤ page-offset bits, that is cache size / associativity ≤ page size. With 4 KB pages and 64-byte blocks a 32 KB 4-way cache (8 KB per way, 7 index bits) takes one index bit from the VPN; 8 ways make it safe (4 KB per way), and 48 KB needs 12 ways. A larger VIPT L1 therefore needs more ways. Cost: more comparators, a wider way multiplexer, more energy and a longer hit time, which way prediction mitigates. Alternatives: page colouring, hardware alias detection, larger pages.

8. L2 and L3 use the physical address for both index and tag. They are accessed only after an L1 miss, when the TLB has already translated the address, so translation adds nothing to their access and they have no synonym problem and no page-size limit: they can be large (MBs) and highly associative. Their longer hit time is acceptable because it is paid only on L1 misses.

Page offset = log₂ 4096 = 12 bits, [11:0]. Block offset = log₂ 32 = 5 bits, [4:0].

1. Sets = 8 KB / (32 B × 2) = 128, so the index has 7 bits, [11:5], and the tag 32 − 7 − 5 = 20 bits, [31:12]: |20-bit tag | 7-bit index | 5-bit offset|. Index + offset = 7 + 5 = 12 bits = the page offset; equivalently 8 KB / 2 = 4 KB ≤ 4 KB. The cache can be VIPT, and its tag is exactly the PFN.

2. Sets = 64 KB / (32 B × 2) = 1024, so the index has 10 bits, [14:5]. Bits 14, 13 and 12 lie above the page offset: k = 10 + 5 − 12 = 3 bits come from the VPN, and an alias may be in any of 2³ = 8 sets.

3. Minimum associativity = 64 KB / 4 KB = 16 ways: 128 sets, index [11:5] again.

4. Pages of 32 KB (15 offset bits contain index [14:5]); page colouring by the OS, so that all aliases of a frame agree on virtual-address bits 14 to 12; hardware that checks the 8 candidate sets on a miss and removes a duplicate (as the AMD Opteron did).

64 sets: index = bits [11:6] of the page offset 0x234 = 001000 = set 8 for all three addresses. Virtual tags: 0x40001 (VA1) and 0x80001 (VA2); physical tag: 0x10001.

VIVT:

VIPT:

In the VIVT table, "Yes (7)" means that the dirty line of VA1, holding 7, is written back to PA 0x1000_1234 before VA2's block is fetched; that fetch then reads the 7.

Neither design returns a wrong value. The aliases share set 8, and a direct-mapped set holds one block: the VIVT cache never has two copies, it pays 3 misses out of 4 and 2 write-backs instead (ping-pong). The VIPT cache has 1 miss and 3 hits. With a second way (8 KB 2-way) the VIVT cache would keep both copies and both reads would return stale values.

Speed-up = 3 / 2 = 1.5.

Answer 3. Minimum associativity = cache size / page size = 64 KB / 4 KB = 16. The block size does not enter: it moves bits between index and block offset, not out of the page offset.

Answer 2. The index comes from the page-offset bits of the virtual address, the tag from the physical address: the PFN delivered by the TLB is compared with the tags of the selected set.

False. On a TLB miss the page table in memory is walked and the translation inserted into the TLB, in tens of cycles. Only if the page-table entry is invalid does a page fault occur, and the OS loads the page from the disk, in millions of cycles.

1. Hit time. The L1 is accessed on every cycle, so its access time bounds the clock period or adds pipeline stages. A small array has short wires, a simple index decoder and a small tag array; low associativity needs few comparators and, when direct-mapped, no way-select multiplexer, so the data can be sent on while the tag is compared. Benefit: minimum hit time and lower energy per access. Cost: a higher miss rate, worth it only if (MR_small − MR_big) × MP < HT_big − HT_small, i.e. when a fast L2 keeps the miss penalty small.
2. Hit time. A small table remembers, for each set, the way that hit last; only that way is read and its data is sent at once, as in a direct-mapped cache, while one tag comparison confirms the hit. A wrong guess costs an extra cycle to check the other ways, and the table is updated. Benefit: the hit time and energy of a direct-mapped cache with the miss rate of a set-associative one. It does not reduce the miss rate.
3. Hit time. The cache is indexed with bits of the virtual address that lie in the page offset, identical in the physical address, while the TLB translates in parallel; the physical tag is compared at the end (virtually indexed, physically tagged). Benefit: the TLB leaves the critical path of every hit. Constraint: index and block-offset bits must fit in the page offset, so cache size / associativity ≤ page size (for example 32 KB, 8-way, with 4 KB pages).
4. Hit time. A write hit is slower than a read hit, because the tag must be checked before the data array is written: a wrong read can be discarded, a wrong write cannot. The write is split into stages (address decode, tag check, data write) and a new write enters every cycle; the data write of one store overlaps the tag check of the next, the data waiting in a delayed-write buffer. Benefit: one write per cycle instead of one every k cycles; the latency of a write does not change. Loads must check the buffer for a pending write to the same address.
5. Hit time. Each one-word sub-block has its own valid bit, so the cache writes the word and the tag in parallel with the tag check. Match: the write was right (set the word's valid bit if needed). Mismatch: the overwritten word belonged to another block that memory already holds (write-through), so the line keeps the new tag with only this word valid. Benefit: writes never wait for the tag check, and a write miss fetches nothing. Usable only with write-through: with write-back a dirty block could be destroyed.
6. Miss rate. A small fully associative buffer (4–16 entries) between the cache and the next level keeps the blocks recently evicted; on a miss it is searched, and a hit there swaps the block back into the cache. It removes many conflict misses of a direct-mapped cache without changing its hit time. Seen from the L1 alone, a victim-cache hit is a cheap miss.
7. Miss penalty. A read miss stalls the processor, a buffered write does not; so read misses are served before the writes waiting in the write buffer, after checking the buffer for the same address (otherwise a RAW hazard through memory). In a write-back cache a dirty victim is moved to the write buffer and written after the new block has been fetched. Benefit: the read-miss penalty no longer includes pending writes.
8. Miss penalty. An L2, larger and slower than the L1 but much faster than main memory, serves most L1 misses: AMAT = L1 Hit Time + L1 Miss Rate × (L2 Hit Time + L2 Miss Rate × L2 Miss Penalty), with the local L2 miss rate. The L1 miss rate is unchanged; the L1 miss penalty falls, and the global miss rate (L1 Miss Rate × L2 Miss Rate) is the fraction of accesses that reaches memory. It also makes a small, fast L1 affordable.

1. Miss Penalty L1 = Hit Time L2 + Miss Rate L2 × Miss Penalty L2, in clock cycles:

2. AMAT = Hit Time + Miss Rate × Miss Penalty, in clock cycles:

Design S is faster by 0.1 clock cycles per access.

3. Equal AMAT when the extra misses of S cost exactly the cycle it saves on every hit:

S is faster for an L1 miss penalty below about 33 clock cycles.

4. Without the L2 the miss penalty is 100 clock cycles:

With the L2 choose S (2.8 against 2.9); without it choose B (5.0 against 7.0).

Without pipelining \(kN\) = 40 clock cycles. The throughput becomes one store per cycle instead of one every 4; each store still takes 4 cycles.

Answers 2, 3 and 5. Answer 1 reduces the miss rate (and increases the hit time); Answer 4 reduces the miss penalty.

Answers 2 and 3. A larger block raises the miss penalty, a victim cache and an L2 act only after an L1 miss.

False. With pipelined writes a new write can start every cycle, so the throughput rises (to one write per cycle in Example 22 of the notes), but each write still needs its address decode, tag check and data write: "latency still 3, but overlapped". Its data may even wait longer in the delayed-write buffer when loads are using the data array.

Concepts. Fine-grained MT: the core holds the context (PC, registers) of several threads and switches thread every clock cycle, round robin, skipping a thread that is stalled; in each cycle all the issue slots belong to one thread. SMT: on a dynamically scheduled (out-of-order, renamed) superscalar, the issue slots of one cycle are filled with ready instructions of several threads; each thread has its own PC and renaming table, instructions carry a thread tag in the reservation stations and the ROB, and functional units and caches are shared.

Example, fine-grained (one thread per cycle; T4 is stalled at C7 and skipped):

Example, SMT (several threads per cycle; T4 is stalled from C3 to C6 and the others take its slots):

Ideal CPI = 1 / issue width = 1/4 = 0.25. Ideal per-thread CPI = threads / issue width = 4/4 = 1: the four slots are shared by four threads, one instruction per cycle each.

Benefits. Fine-grained: hides short and long stalls (RAW, mispredictions, misses), because a stalled thread just loses its turn; no switch cost; simple fair rotation. SMT: the highest throughput, because it fills both the empty cycles (vertical waste) and the empty slots inside a cycle (horizontal waste); it combines ILP and TLP at a small hardware cost on an out-of-order core.

Drawbacks. Fine-grained: each thread runs slower when the others are ready (one cycle in N); the slots a thread cannot fill in its cycle stay empty; a thread selection every cycle. SMT: the threads compete for caches, functional units and branch predictors, so per-thread performance is lower and unpredictable; complex fetch, issue and commit logic; a larger register file.

Threads in each core: simultaneous multithreading (Intel Hyper-Threading style). Both hardware threads of a core are active at once and, in the same cycle, their ready instructions fill the two issue slots of the shared out-of-order engine; per thread a PC and a renaming table, thread tags in the reservation stations and the ROB; caches and functional units shared.

Ideal CPIs: per core = 1/2 = 0.5; dual-core = 1/(2 × 2) = 0.25, since the chip completes four instructions per cycle; per thread = 2/2 = 1, since each thread shares its core's two slots with one other thread.

Scheduling inside each thread: dynamic scheduling — Tomasulo's algorithm with reservation stations and register renaming, out-of-order execution, and a reorder buffer for speculation with in-order commit, together with dynamic branch prediction.

Coherence: each core has private caches holding copies of shared blocks; a snooping write-invalidate, write-back protocol (MESI) on the shared bus keeps them coherent: a write to a shared block first invalidates the other copies.

ILP executes independent instructions of one instruction stream in parallel: pipelining, multiple issue (superscalar or VLIW), dynamic scheduling with out-of-order execution, register renaming against WAR and WAW hazards, branch prediction and speculation. It is limited by true dependences, control dependences and memory latency, is extracted mostly by the hardware (by the compiler in a VLIW) and speeds up one thread. TLP executes independent instruction streams — threads or processes provided by the programmer or the OS — in parallel: multithreading in one core (coarse-grained, fine-grained, SMT), multicores and shared-memory multiprocessors (coherent caches, synchronisation with locks and barriers), and clusters with private memories and message passing. It raises the throughput of a multithreaded workload.

Combining both: simultaneous multithreading, which fills the issue slots of a superscalar in the same cycle with instructions of several threads.

Scheduling: dynamic scheduling — the hardware reorders the instructions at run time (Tomasulo with renaming and a reorder buffer), instead of static scheduling by the compiler as in simple in-order superscalars and VLIWs. One instruction window holds the instructions of all active threads; every cycle the ready instructions, from whichever thread, are issued to the free functional units. Renaming gives each in-flight instruction a unique physical destination, so threads cannot collide on register names.

Hardware: a PC per thread; a renaming table per thread over a larger shared physical register file that holds every thread's architectural registers; a thread tag on every instruction in the reservation stations, the ROB and the load/store queues; per-thread commit and exception squash; a fetch policy that selects the thread each cycle (round robin, ICOUNT); issue logic that picks ready instructions across threads; buffers shared or partitioned between threads; caches, functional units and predictors shared.

8. Simultaneous multi-threading. Several hardware threads are active at once in one out-of-order superscalar core: each keeps its own PC and renaming table over the shared physical registers, and a thread tag in the reservation stations and the ROB keeps results and commits apart. Every cycle the issue logic sends the ready instructions of any thread to the free functional units, so one cycle mixes threads. Benefit: the other threads fill the slots that one thread's ILP leaves empty (vertical and horizontal waste) — higher throughput and unit utilisation for little hardware (Hyper-Threading: under 5 % of the die, up to 30 % more throughput). Cost: shared caches and units, so single threads run slower and less predictably.

Answer 3. Ideal CPI = 1 / issue width = 1/4 = 0.25; ideal per-thread CPI = threads / issue width = 8/4 = 2.

Answer 3: ideal CPI = 1/2 = 0.5; ideal per-thread CPI = 4/2 = 2.

In every cycle the two slots hold instructions of two threads issued together. From C7 on T4 waits for a miss and the other threads take its slots.

False. Fine-grained multithreading switches thread every clock cycle, so consecutive cycles may belong to different threads, but within one cycle only one thread issues; issuing from several threads in the same cycle is simultaneous multithreading.

1. Data-level parallelism. The same operation applied independently to many data items, as in Z[i] = X[i] + Y[i]: no element waits for another. It is a property of the program, exploited by SIMD and vector hardware with one instruction per data operation instead of one per element; the fetch, decode and issue cost per element is divided by the vector length, so it costs far less energy than extracting the same parallelism as ILP.

2. Flynn's taxonomy and the superscalar. Flynn classifies machines by the number of instruction streams and data streams. A superscalar fetches several different instructions per cycle from one program counter: one instruction stream, each instruction on its own operands, so it is SISD and exploits ILP. The benefit of the classification is to separate ILP (more instructions per cycle from one stream), DLP (one instruction on many data, SIMD) and TLP (many streams, MIMD): Flynn counts streams, not width.

3. SIMD with a single PC. One control unit fetches each instruction once and broadcasts it to many processing elements, which execute it in lockstep on their own data. Benefits: one fetch and decode per operation instead of per PE (energy), compact code, no synchronisation between PEs. Drawback: divergent control flow must be handled by masking off elements.

4. Array vs vector processors. An array processor has N processing elements working side by side; an operation with latency L keeps them frozen, so it takes L × ⌈n/N⌉ cycles and the latency is exposed on every round, and the programmer thinks in PEs and local memories. A vector processor pipelines its units: the latency is paid once and then one result per cycle, L + n cycles (6 + 64 = 70), and the programmer thinks in vector registers. On long vectors one L-stage pipelined unit does the work of about L unpipelined ones.

5. Vector register file. Registers holding whole vectors (VMIPS: 8 registers of 64 × 64-bit elements, 16 read and 8 write ports through a crossbar), used register-to-register: each element is loaded once and reused by several instructions, and the pipelines are fed from registers without stalling on memory. It is compiler-controlled, unlike a cache: no tags, no misses.

6. Deeply pipelined functional units. Each unit accepts a new element every cycle. Element independence means no hazard checks between elements, so the pipelines can be deep and fast, and the start-up latency is amortised over the whole vector: about one result per cycle per unit. Cost: every instruction pays its start-up, so short vectors are inefficient.

7. Interleaved memory banks. Consecutive words are placed in consecutive banks; each bank is busy for several cycles after an access, but together they deliver one word per cycle to the vector load/store unit (Cray-1: 16 banks, 4-cycle bank busy time). Benefit: the bandwidth needed by streaming loads and stores; cost: many banks, and conflicts when a stride keeps hitting the same bank.

8. Little or no data cache. Vector accesses are predictable — the instruction states which words it needs — and streaming kernels use each element once, so a cache would add latency and area for little reuse. Bandwidth comes from the banks, latency is amortised by pipelining and buffered in the vector registers; a small scalar cache may serve the scalar side, which the vector side bypasses.

Answer 1: SISD. Flynn's classification counts instruction and data streams, not issue width: a superscalar fetches all its instructions from one program counter.

False. The latency is paid once per vector instruction (the start-up); then the pipeline delivers one result per clock cycle, so n elements take about L + n cycles, not L × n.

Answers 1, 2 and 3. Vector accesses are predictable and stream each element once: interleaved banks supply the bandwidth, pipelined units pay the latency once per vector, and the vector registers act as a compiler-managed buffer.

For comparison: one unpipelined adder would need 6 × 64 = 384 cycles of computation; an array of 64 unpipelined PEs about 6, with 64 adders instead of one.

Main concepts. A vector processor is a SIMD machine: one instruction operates on whole vectors held in vector registers. VMIPS is the scalar MIPS pipeline plus a vector unit: (1) a vector register file — 8 registers of 64 elements of 64 bits, with many read and write ports (16 and 8) through a crossbar — a compiler-controlled buffer between memory and the functional units; (2) deeply pipelined vector functional units (FP add/subtract, FP multiply, FP divide, integer, logical) that deliver one result per cycle after a start-up latency; (3) a vector load/store unit that streams one word per cycle from interleaved memory banks, with unit-stride, strided (LVWS) and indexed (gather/scatter) accesses; (4) scalar registers for addresses, strides and the scalar operands of instructions such as MULVS.D; (5) the vector-length register VLR (0 ≤ VLR ≤ MVL), used with strip mining for loops of any length, and the vector mask register for loops with an IF. Execution time is counted in convoys — instructions that run together, one per unit, dependent ones only with chaining — and chimes of about VL cycles: T ≈ convoys × VL.

Advantages and the feature that provides each. (a) Far fewer instructions fetched, decoded and issued: one vector instruction does the work of a whole loop (DAXPY on 64 elements: 6 instructions instead of about 578) — vector registers and vector instructions; less instruction bandwidth and energy. (b) Almost no loop overhead: index updates and loop branches disappear, one branch per strip of up to MVL elements instead of one per element, hence far fewer control hazards and mispredictions — vector-length semantics, VLR and strip mining. (c) Deep pipelines without stalls: the elements of a vector are independent, so no hazard checks inside an instruction, and dependences between vector instructions are checked once per vector, not once per element — pipelined vector units. (d) Overlap of dependent operations and of several units: chaining forwards element by element and several units run in one convoy (DAXPY in 3 chimes, 192 cycles, instead of 4 chimes, 256) — multiple units plus chaining. (e) Memory latency paid once per vector and a sustained bandwidth of one word per cycle: known access patterns let the load/store unit stream from interleaved banks, with little or no data cache — vector load/store unit plus banks. (f) Scalability without changing the code: L lanes process L elements per cycle, ⌈VL/L⌉ cycles per chime, same instructions. Limits: the gain needs data-level parallelism; masked elements still cost cycles; bad strides cause bank conflicts.

(1) Chaining: the result of a vector unit is forwarded element by element to the next unit, so a dependent vector instruction starts as soon as the first element of its operand is produced, instead of waiting until the whole vector is written back. Benefit: dependent instructions run overlapped in the same convoy, one chime instead of two per dependence (DAXPY: 4 convoys, 256 cycles → 3 convoys, 192 cycles). It is the vector analogue of forwarding; it does not remove structural hazards — one instruction per unit per convoy.

(2) Multiple lanes: each vector unit and the vector register file are split into L lanes; element i of every register lives in lane i mod L, so element-wise operations never cross lanes. Benefit: L elements per cycle, a chime of ⌈VL/L⌉ cycles (64 elements on 4 lanes: 16 cycles), with no change to the ISA or the code. Cost: register-file ports and memory bandwidth grow with L.

(3) VLR and strip mining: MVL is the hardware length of a vector register; the vector length register (0 ≤ VLR ≤ MVL) tells each instruction how many elements to process. Strip mining is the compiler transformation that cuts a loop of n iterations into ⌈n/MVL⌉ strips, the short one with VLR = n mod MVL (260 elements on MVL 64: 4 × 64 + 4). Benefit: one vector loop for any n, no access past the end of the arrays. Cost: a scalar strip loop with its overhead.

(4) Vector mask registers: one bit per element, set by a vector compare; instructions executed under the mask update only the elements whose bit is 1. Benefit: loops with an IF stay vectorizable (predication at vector level), no scalar fallback, any instruction can be masked. Cost: masked elements still take their cycle, so efficiency equals the fraction of active elements.

(5) Interleaved banks: consecutive words go to consecutive banks (bank = (address / word size) mod #banks), so a unit-stride access finds a free bank every cycle and the load/store unit sustains one word per cycle; strided loads (LVWS) and gather/scatter through index vectors handle matrix columns and sparse data. A stride visits #banks / gcd(stride, #banks) banks; if that is less than the bank busy time, accesses stall (8 banks, busy time 6, latency 12, 64 elements: stride 128 hits one bank and takes 391 cycles instead of 76). Fixes: pad rows (129 words), interchange the loops, choose a column-major layout.

Answer 3: 4 convoys; 64 clock cycles. Four memory instructions on one load/store unit need at least four convoys, and four are enough. A convoy lasts 16 cycles: 16 elements, one 64-bit element per cycle (bandwidth 64 bits), start-up ignored.

Answer 3: 4 convoys; 4 × 8 = 32 clock cycles (8 elements, one 64-bit element per cycle).

The single load/store unit serialises the three loads and the store; with chaining each multiply joins the convoy of its load, and each add the convoy of its multiply, its other operand being complete (V1 after the 1^ convoy, V2 after the 2^).

Strip mining. MVL = 64 < n = 260, so the loop is split into ⌈260/64⌉ = 5 strips: four strips of 64 elements and one of 260 mod 64 = 4 elements (first, in Hennessy and Patterson's code, or last), setting VLR before each strip. Each strip executes L.V V1, RX; L.V V2, RY; ADDVV.D V3, V1, V2; S.V V3, RY. A mask register is for an IF inside the loop, which is absent; trace scheduling and software pipelining are VLIW compiler techniques for scheduling scalar instructions.

Without chaining every true dependence ends a convoy, and the chain L.V V1 → ADDVS.D V1 → MULV.D V2 → DIVVS.D V2 → ADDVV.D V3 → S.V V3 has six instructions: 6 convoys. A convoy lasts 16 cycles (16 elements, one 32-bit element per cycle): 6 × 16 = 96 clock cycles.

With chaining, as in the January 2026 paper: 4 convoys, 64 cycles — L.V V1 + ADDVS.D + MULV.D; L.V V3 + DIVVS.D + ADDVV.D; S.V V2; S.V V3.

Each strip: 3 convoys (L.V + MULVS.D; L.V + ADDVV.D; S.V). Strips: ⌈1000/64⌉ = 16 — 15 of 64 elements and one of 1000 mod 64 = 40. With 4 lanes a chime takes ⌈VL/4⌉ cycles: 16 for a full strip, 10 for the short one.

750 clock cycles, 0.75 per element.

1. A scalar ISA extended with instructions that apply one operation to the elements packed in a wide register (128, 256 or 512 bits: 2, 4 or 8 doubles). Benefits: several data operations per fetched and decoded instruction; cheap to add as extra datapaths in the existing pipeline; little extra state, fed by the caches; available in every CPU, so compilers and libraries use it for media and ML kernels. Limits: the width is fixed in the opcode, so a wider register needs new instructions and recompiled code, leftovers need a scalar remainder loop, and strided/sparse access and masks came late (gather with AVX2, scatter and masks with AVX-512).

2. VLR holds the number of elements, 0 ≤ VLR ≤ MVL, that every vector instruction processes; MVL is the hardware length of a vector register. Strip mining (a compiler transformation) splits a loop of n iterations into ⌈n/MVL⌉ strips: full strips with VLR = MVL and one strip of n mod MVL. Benefits: one loop handles any n with no remainder loop, nothing beyond the arrays is touched, and the same binary uses more lanes or a longer MVL if the loop takes its strip length from the hardware (ARM SVE, RISC-V V).

3. A mask register holds one bit per element; a vector compare sets it, and the following vector instructions update only the elements whose bit is 1, leaving the others unchanged (predication). Benefits: loops with if statements stay vectorised, with no branch per element, and masked elements raise no exceptions. Cost: masked elements still use their slot, so an if-else executes both bodies. GPUs do the same per thread (branch divergence).

4. A GP-GPU streaming multiprocessor is a multithreaded SIMD processor. Threads are grouped into warps of 32; one instruction is fetched per warp and executed in lockstep on the SIMD lanes for all 32 threads, each thread with private registers (SIMT). Many warps are resident; every cycle the warp scheduler issues from a ready one, and since all their registers stay in a large register file, switching costs nothing. Benefits: DRAM latency of hundreds of cycles is hidden by the other warps instead of by caches or out-of-order logic; the programmer writes sequential code for one element; the same kernel scales over any number of SMs.

5. The CPU (host) and the GPU (device) have separate memory address spaces, physically two DRAMs linked by PCIe/NVLink. The host allocates device memory (cudaMalloc), copies the inputs (cudaMemcpy), launches the kernel and copies the results back. Benefit: the device memory (GDDR/HBM) is built for bandwidth and serves the kernel at full speed. Cost: every transfer crosses the link, so a kernel must do enough work per byte copied; unified memory only automates the migration.

6. Each thread of a warp computes its own address; the coalescing unit merges the 32 addresses of a warp's load or store into as few wide memory transactions as possible. Consecutive threads touching consecutive words cost one or two transactions — the run-time equivalent of a unit-stride L.V — while column or scattered accesses cost up to 32. Benefit: memory bandwidth is used efficiently without the program stating the stride; it rewards unit-stride data layouts.

7. A tensor core is a functional unit in each SM that computes D = A × B + C on small matrices as one operation (Volta: 4 × 4, A and B in FP16, accumulation in FP16 or FP32, 64 FMAs per clock), used through a warp-level matrix instruction. Benefits: one instruction for 64 FMAs; each input reused 4 times inside the unit, so less register traffic per flop; reduced precision halves data movement — up to 125 TFLOPS on a V100. Only matrix-shaped, high-intensity work (dense linear algebra, deep learning) gains.

8. A systolic array is a grid of multiply-accumulate cells in which data moves between neighbours in lockstep, so each operand fetched from memory is used by a whole row or column. In the TPU (256 × 256 8-bit MACs, weight-stationary) the weights stay in the cells, activations flow right and partial sums flow down into accumulators: one activation read feeds 256 MACs. Benefits: very high throughput (92 TOPS) at low energy per operation, simple control, software-managed on-chip memory instead of caches. Limits: only dense matrix work, and a fill/drain latency per stream.

True. The device has its own DRAM; pointers to device memory are valid only on the device, and data moves explicitly (cudaMalloc, cudaMemcpy host to device, kernel launch, cudaMemcpy device to host).

Answer 1. A 512-bit register holds 8 doubles, and 260 = 32 × 8 + 4: the SIMD loop runs 32 times, and the 4 leftover elements go to the scalar remainder loop. With the k-mask registers of AVX-512 the 4 leftovers would take one masked add (33 instructions); on a vector machine the loop is strip-mined with VLR instead (5 strips with MVL = 64).

Answers 1, 2 and 4. A warp is one instruction stream for 32 threads with private registers; latency is hidden by switching warps; divergent paths run one after the other under masks. A GPU has no VLR (the tail is masked), and a tensor core is a matrix unit, not a wider FMA.

1. A multiprocessor is a computer system with tightly coupled processors coordinated by a single operating system, typically offering a shared address space. Each processor runs its own instruction stream on its own data (MIMD), so the machine exploits thread-level parallelism. Benefits: high throughput on many threads or processes, performance that grows with the number of processors, tolerance of some faults through redundancy, one design from embedded systems to servers. Unlike a cluster, it has one OS and one address space.

2. A multicore puts several cores on the same chip; beyond about 32 cores it is called a manycore. A multicore chip is a small SMP on a chip: private L1/L2 caches, usually a shared last-level cache, uniform access to memory, snooping coherence. Benefit: it turns the transistor budget into throughput through TLP — the industry's answer to the ILP and frequency (power) walls — instead of a wider or faster single core.

3. In an SMP (centralized shared memory) all processors share one physical memory with the same access time for everyone (UMA), usually through a bus; cache coherence is kept by snooping. Benefits: simple, symmetric view for the programmer and the OS, cheap for a few processors. Limit: the shared bus and memory saturate, so SMPs typically stay at or below about 32 processors.

4. In a distributed shared-memory (DSM) multiprocessor the memory is physically distributed among the nodes (processor + caches + local memory module) connected by an interconnection network, but forms one shared address space. Access time is non-uniform (NUMA): local is fast, remote is slower. Benefits: it scales beyond about 32 processors because memory bandwidth grows with the nodes and there is no single memory bottleneck, and it is still programmed with loads and stores. Costs: data placement matters, coherence needs directories, the network is complex.

5. With shared memory, processors communicate implicitly by loads and stores to a common address space: natural to program, but it needs coherence hardware and explicit synchronization (locks, barriers). With message passing, each processor has a private address space and communicates explicitly with send and receive: simpler hardware, explicit control of data movement, harder programming. Both models are Turing complete and each can implement the other, so the choice affects performance, programmability and cost, not what can be computed.

6. All processors, the memory and the I/O share one bus; every memory access (cache miss) is a bus transaction, one at a time. Benefits: cheap, simple, and a broadcast medium — every cache sees every transaction, which snooping coherence needs. Drawback: saturation. If each processor alone uses a fraction d of the bus, throughput grows linearly and then flattens near 1/d processors (commercial systems maxed out at about 36); beyond that, adding a processor only lengthens the queue and slows every access.

7. An interconnection network connects the nodes with many point-to-point links and switches (ring, 2-D mesh, torus, hypercube, crossbar, fat tree), so many transfers proceed in parallel and the bandwidth grows with the system. Benefits: it removes the shared bus from the critical path and scales to hundreds or thousands of processors. Costs: switches and links are expensive, and multiple hops add latency. Networks are compared by total and bisection bandwidth, diameter and node degree.

8. Bisection bandwidth is the minimum, over all cuts that split the network into two halves with equal numbers of nodes, of the total bandwidth of the links crossing the cut. It is the worst case, when half of the nodes communicate with the other half, and it bounds global traffic, while the total bandwidth (M × b, the sum of all links) is the best case for local traffic. Examples: bus b, ring 2b whatever P, 2-D mesh √P·b, hypercube (P/2)·b.

All-to-all traffic crosses the machine, so it is bounded by the bisection bandwidth, not by the total. The fully connected network has the largest bisection (64 GB/s) and diameter 1, but needs 120 links and 15 ports per node. The hypercube gives 8 GB/s of bisection, so every node can send across the cut at its full link speed (8 GB/s for 8 senders), with only 32 links, 4 ports per node and a diameter of 4: the usual engineering choice at this size. The mesh is cheaper but has half the bisection and diameter 6; the ring and the bus would be throttled to 2 and 1 GB/s.

Without remote references the machine would be 1.3 / 0.5 = 2.6 times faster.

Answers 2, 3 and 4. Answer 1 describes the total bandwidth; the mesh bisection is N·b = √P·b, which grows as the square root of P.

Answer 3: N = log₂64 = 6, bisection = 2^(N−1)·b = (P/2)·b = 32 GB/s; the total is N·P/2·b = 192 GB/s.

True. Throughput ≤ bus capacity / demand per processor = 1 / 0.04 = 25 processors' worth; near that point the bus is saturated and every further processor only lengthens the queue for the bus.

Answer 3. Each node contains its own processor, private cache and memory module, so the memory is physically distributed and there is no single central memory: Answers 1 and 2 are wrong. Each memory module is annotated with P0, P1, P2, P3: every processor can access every module with ordinary loads and stores, so the memories form a single logically shared address space and Answer 4 is wrong. This is a Distributed Shared Memory (DSM) architecture, also known as NUMA.

1. All processors see one logical memory: an address names the same location for every processor, any processor can load or store any address, and communication is implicit (one processor stores, another loads). Programmed with threads (Pthreads, OpenMP). Benefits: easy to program, handles irregular and dynamic sharing, low latency for small items, caches reduce remote traffic automatically. Costs: complex hardware (cache coherence), synchronization with locks and barriers, little control of data placement.

2. Each processor has its own address space: the same address names different locations on different processors, no load or store crosses processors, and data moves by explicit send/receive (MPI_Send / MPI_Recv). Benefits: simple hardware with no coherence protocol, the programmer sees when and how much data moves, every send/receive synchronizes, explicit placement, fault isolation. Costs: harder programming, high overhead for fine-grain sharing, data decomposed by hand.

3. One centralized physical memory shared by all processors, with the same latency and bandwidth whichever processor accesses it (symmetric). Processors with private caches, possibly a shared L3, reach it through a bus or crossbar; coherence by snooping. Benefits: the simplest programming (no data placement), sequential code ports easily, a uniform view for the OS. Limit: the single memory and interconnect saturate under contention, about 32 processors in classic designs.

4. Memory physically distributed: each node is processor(s) + caches + a local memory module, and the nodes are joined by a scalable interconnection network. The union of the local memories is one global address space, so programs still use loads and stores. The access time depends on whether the address is in the local module (fast) or in a remote node (slower). Benefits: scales to hundreds of cores, aggregate memory bandwidth grows with the nodes. Costs: performance depends on data placement; a scalable network and directory-based coherence are needed.

5. The home node of a block is the node whose main memory holds it, fixed by the physical address (if every node owns 4 KiB, N2 owns 0x2000–0x2FFF and the block of 0x2200 is homed in N2). In a directory protocol it also keeps the block's directory entry (state and sharer bits), stored with the block in its memory, so every request for the block goes through it. The local node is the node that issues the request. Benefit: the data and its coherence information are found from the address alone, without broadcasts.

6. A multicore chip with a few cores (up to about 8, sometimes 16) is an SMP on a chip: identical cores, uniform access to one main memory, one shared-memory machine for the OS. Private L1 and L2 caches per core hold the working sets and reduce contention; a shared L3 cuts DRAM traffic and is where shared data meets; coherence by snooping on the shared bus. Beyond about 8 cores the L3 is split into banks and the bus becomes a network-on-chip (mesh, ring, crossbar), so several requests are served in parallel.

7. A set of independent computers, each with its own processors, private memory, local disk and OS instance, connected by a network (Ethernet, InfiniBand); no shared address space, communication by explicit message passing with MPI. Benefits: scales to tens of thousands of nodes, memory grows linearly with the nodes, commodity hardware is cheap, one node can fail without crashing the system. Costs: harder programming (partition the data, orchestrate the messages), network latency much higher and bandwidth lower than local DRAM, synchronization at every send/receive.

8. All processors run the same program, each on its own portion of the data (Single Program, Multiple Data): adding two 1000-element vectors, Proc 0 takes indices 0–249, …, Proc 3 750–999. Execution proceeds in bulk-synchronous phases: local computation, global communication or a barrier, next phase (Valiant's BSP model). Benefits: one simple program, high scalability for large and evenly split data, efficient on GPUs and vector units. Costs: load imbalance and stragglers stall everyone at the barrier; it suits regular array computations, not trees or graphs.

1. The home node of a block is the node whose main memory holds the block; it is fixed by the physical address, and in a directory protocol it also keeps the block's directory entry, so every request for the block goes through it. 0x2200 lies in 0x2000–0x2FFF: the home node is N2.

2. The local node is the node whose processor issues the request: N0.

3. C0 misses; the request leaves N0 and the interconnection network routes it, by address, to N2; MM2 supplies the block (offset 0x200 in its range); the data travels back to N0, is written into C0, and the load completes into F2. It is a remote access: two network crossings and a longer latency than a local access.

4. With 0x0200 the home is N0 itself: home and local coincide, and the miss is served by MM0 without using the network, with the shorter local latency. The program does not change — the same instruction in the same address space; only the latency changes.

With \(T_{CLK} = 1\) ns, a local miss costs 80 clock cycles and a remote miss 240. Case A: a quarter of the blocks are homed in the local node, so the average miss penalty and the CPI are

Case B:

Speed up in terms of CPI:

The same program on the same machine runs 25% faster only because of where its data are placed.

Answers 1, 3 and 5. A DSM has physically distributed memory, a single logically shared address space reached by loads and stores, non-uniform latency, and directory-based coherence. Answers 2 and 4 describe a distributed-memory cluster.

False. In a cluster every node has its own private memory and address space, and the memory of one node cannot be accessed directly by another node via loads and stores; data moves only through explicit messages, with MPI_Send and MPI_Recv.

1. A private cache keeps a copy of a block next to the core. For shared data it gives migration — the block moves to the cache of the core using it, so accesses no longer go to memory or over the interconnect — and replication — a read-shared block gets a copy in every reader's cache, so readers do not contend for one copy. Benefit: lower latency, less bus and memory traffic. Cost: several copies of one block, hence the coherence problem.

2. A memory system is coherent if (1) a processor that writes X and then reads X, with no other write in between, reads its own value; (2) a read of X by P2 after a write by P1 returns P1's value if enough time has passed and no other write intervened; (3) writes to the same location are serialized: all processors see them in the same order. It concerns one location at a time.

3. Consistency defines when a write becomes visible to the other processors and in which order loads and stores to different addresses may be observed. Example: P0 writes A = 1 then B = 2, P1 reads B then A: sequential consistency forbids reading B = 2 and A = 0, relaxed models allow it. A coherent memory need not be sequentially consistent.

4. Before writing a shared block, the writer broadcasts an invalidate; all other copies become Invalid and the writer gets exclusive ownership. Further writes are local and silent until another processor requests the block; that processor misses and gets the data from the owner or from memory. Benefit: traffic only on the first write — the choice of almost all modern multiprocessors, with write-back caches.

5. Every write broadcasts the new value to all caches holding the block (and usually to memory), which update their copies. Benefit: readers never miss and never see stale data. Cost: one bus transaction per write, also for repeated writes to one word or to the words of one block, so it wastes bandwidth; it pays off only for producer–consumer sharing.

6. The caches share a bus, which is a broadcast medium: every cache controller monitors every transaction and reacts if it holds the block (invalidates it or supplies the data). No central directory; one transaction informs all caches; the bus order serializes the writes. Suitable for small symmetric (UMA) multiprocessors; it does not scale, because broadcast traffic, electrical load and serialization grow with the number of processors.

7. A second copy of the cache's tag array — tag and coherence state, no data — used only by the snooper. Bus transactions are checked there while the processor keeps using the main tags, so snooping does not stall the pipeline: it removes the structural hazard on the tag array. Cost: area, and both copies must be updated together.

8. Each block is Modified (only copy, dirty), Shared (clean, possibly in other caches) or Invalid. A read miss puts a Read Miss on the bus (→ S), a write miss a Write Miss (→ M), a write hit in S an Invalidate (→ M); read hits and write hits in M are silent. A snooped Read Miss turns M into S with a write-back; a snooped Write Miss turns S or M into I (M supplies the block and writes it back first); a snooped Invalidate turns S into I. A replaced Modified block is written back, a replaced Shared block leaves silently.

A snooping, write-invalidate protocol with write-back caches (MSI, in practice MESI). The private caches of the two cores sit on a shared on-chip bus that acts as a broadcast medium: each cache controller monitors every transaction, with duplicate snoop tags, and keeps a coherence state per block. Before a core writes a block that the other core may hold, it broadcasts an invalidate, so the other copy becomes Invalid and later writes stay local. A read miss on a block that the other cache holds Modified is served by that cache, which writes the block back and goes to Shared. With two cores the broadcast is cheap and the bus serializes the writes, so no directory is needed — directories are for many nodes with distributed memory.