A 58 ns Critical Path and Two Cache Options: A Design Judgement on the FPGA Project
A polytechnic's final-year project team is building a single-cycle 8-bit CPU on an FPGA at a target clock of 25 MHz (40 ns period). Static timing analysis reports a critical path of 58 ns: register-file read 3 ns, an 8-bit ripple-carry adder built from eight 6 ns full-adder stages (48 ns), instruction decode 4 ns, plus 2 ns register setup and 1 ns clock skew. The team's proposed fix is to 'add a pipeline register' so the clock can be raised. Separately, the memory subsystem is being evaluated: a direct-mapped 1 KB cache with 8-byte blocks, hit time 1 cycle, miss penalty 30 cycles, measured hit rate 0.82. A 2-way set-associative version of the same total size raises the hit rate to 0.90 but raises hit time to 2 cycles. About 30% of executed instructions are loads or stores. The guide asks for a defensible design decision rather than a bigger FPGA.
1. Compute the maximum clock frequency of the current design and show why the proposed pipeline register does not by itself solve the 25 MHz problem. State what has to change.
Read the worked answer
Period = 3 + 48 + 4 + 2 + 1 = 58 ns, so fmax = 1000/58 ≈ 17.2 MHz. For 25 MHz the budget is 40 ns, so the design misses by 18 ns - over 40% over budget. Nothing about the clock tree will rescue that.
Now test the proposal. A pipeline register placed after the ALU does not shorten the adder; it only moves the boundary. The worst stage still contains 3 + 48 + 2 + 1 = 54 ns, i.e. about 18.5 MHz, and you have added a register, a valid bit and hazard logic for the privilege. A pipeline register helps only when the longest combinational segment per stage is under 40 − 3 = 37 ns, and here one element - the adder - is 48 ns on its own.
The real bottleneck is the ripple-carry chain: the carry must propagate through all eight stages, so delay grows linearly with word length. Replace it with a carry-lookahead (or carry-select) adder, which generates and propagates carries in parallel and brings an 8-bit add to roughly 12 ns here. New combinational path = 3 + 12 + 4 = 19 ns; period = 19 + 2 + 1 = 22 ns, i.e. about 45 MHz - comfortably above 25 MHz, with single-cycle simplicity intact.
Judgement: fix the arithmetic, do not pipeline around it. Pipelining a 48 ns adder buys complexity and still misses the target.
2. Compute AMAT and CPI for both cache options and recommend one, showing the speedup and a break-even check.
Read the worked answer
AMAT = hit time + miss rate × miss penalty.
Direct-mapped: 1 + 0.18 × 30 = 1 + 5.4 = 6.4 cycles. 2-way: 2 + 0.10 × 30 = 2 + 3.0 = 5.0 cycles.
CPI impact, with 30% loads/stores and a base CPI of 1.0 for a perfect cache: the stall contribution is 0.30 × (AMAT − 1).
Direct-mapped: 0.30 × 5.4 = 1.62 → CPI 2.62. 2-way: 0.30 × 4.0 = 1.20 → CPI 2.20.
Speedup = 2.62 / 2.20 = 1.19, about 19% fewer cycles.
Break-even check: the extra hit cycle is worth paying only if 2 + 30(1 − h) < 6.4, i.e. 1 − h < 0.1467, i.e. h > 0.853. The measured 0.90 clears that by a margin, so the 2-way design wins - but only because the miss penalty is 30 cycles. If the miss penalty were 10 cycles the 2-way AMAT would be 3.0 against 2.8, and the simpler cache would win.
Recommendation: take the 2-way set-associative cache. Note the cost: an extra tag comparator, an LRU/replacement bit and one extra cycle of latency, which the pipeline must tolerate. Also state the assumption honestly - the gain depends on the measured 0.90 hit rate holding on real workloads, not just the benchmark.
3. If the team still insists on pipelining, describe where the register must go and what new cost appears. End with the design decision you would sign off.
Read the worked answer
To gain anything, the register must go inside the long element, not after it: split the eight-stage carry chain with a register after bit 3, so each half is about 24 ns and the stage fits inside 40 ns. That makes an 8-bit add take two cycles instead of one.
New costs: the ALU result is only available one cycle later, so the control unit needs a 'wait' state for dependent instructions; branches are resolved later, adding a taken-branch penalty; and the forwarding/stall logic must know that the adder's carry-out register is an internal state bit. That is real RTL work, plus new verification cases, on a final-year timeline.
Compare honestly: the carry-lookahead route is a one-module swap that keeps the single-cycle datapath, the control FSM and the testbench unchanged, and reaches about 45 MHz. The pipelined ripple-carry route rewrites the control path, introduces hazards, and lands near the same clock with more failure modes.
Decision I would sign off: carry-lookahead adder, keep single-cycle, target 25 MHz with margin; keep the 2-way cache. Record the pipelined version as future work in the report, with the note that at 25 MHz the project does not need it. Naming what you deliberately did not do, and why, is the mark of a defensible design rather than a bigger FPGA.