Worked examples — Single-cycle datapath design

This page is the drill room for single-cycle datapath design. The parent note built the machine; here we run every kind of question an exam or real design can throw at you. Before every solution you must forecast — write your own guess, then compare.

Everything numeric is machine-checked at the bottom.

---

The scenario matrix

Every single-cycle problem lives in one of these boxes. We will hit all of them.

#	Case class	What makes it tricky	Covered by
A	R-type timing (no memory)	path skips the data-memory block	Ex 1
B	lw timing (touches everything)	the usual critical path	Ex 2
C	sw / beq short paths	write-back or memory absent	Ex 3
D	Adding a slow instruction	one instruction raises the clock for all	Ex 4
E	Zero / degenerate delay	a block delay of 0 ps (or removed)	Ex 5
F	Branch target arithmetic — positive offset	sign-extend then shift, forward branch	Ex 6
G	Branch target arithmetic — negative offset	the sign bit must survive; backward loop	Ex 7
H	Control-signal fill-in incl. "don't care" X	when a mux value truly doesn't matter	Ex 8
I	Real-world word problem (speedup)	translate English → the performance equation	Ex 9
J	Exam twist: "reuse the ALU?"	why single-cycle forbids time-sharing	Ex 10

The delays we reuse everywhere (same as the parent note, in picoseconds, ps = one-trillionth of a second):

The bar chart above is our map: each instruction is a stack of the blocks it touches. The tallest stack wins and becomes the clock period. Keep looking back at it.

---

Case A — R-type timing

Recall Forecast: does

add touch the data memory? Guess its total ps. It does not touch data memory. Guess before reading on.

Steps.

1. List the blocks add walks through: Instruction Memory → Register read → ALU → Register write-back. Why this step? An R-type reads two registers, does one ALU operation, and stores the result back. It never loads or stores memory, so the Data Memory block is skipped entirely.
2. Sum them: $200+100+200+100$. Why this step? Blocks on one path run in series (one feeds the next), so delays add.
3. Total $=600$ ps.

Verify: Look at figure s01 — the R-type stack rises to 600 and there is a visible gap where Data Memory would be. Units are all ps summed to ps. ✓

---

Case B — lw, the usual critical path

Recall Forecast: which extra block does

lw add compared to add? The Data Memory read. So it should be add + $t_{DMem}$.

Steps.

1. lw blocks: IMem → RegRead → ALU (computes the address) → Data Memory (reads) → RegWrite. Why this step? A load must compute an address (ALU adds base register + offset), then read memory, then write the loaded value back into a register. That is literally all five logical stages.
2. Sum: $200+100+200+200+100$.
3. Total $=800$ ps.

Verify: $800=600(\text{R-type})+200(\text{DMem})$. The lw stack in s01 is the tallest — it alone sets the clock. ✓

---

Case C — short paths (sw, beq)

Recall Forecast:

sw stores — does it write a register at the end? beq — does it touch memory? sw drops the final register write-back. beq drops both memory and write-back.

Steps.

1. sw blocks: IMem → RegRead → ALU (address) → Data Memory (writes). No write-back — a store produces no register result. $200+100+200+200=700$ ps. Why this step? Storing means the value flows out to memory; nothing comes back to a register, so $t_{RegWrite}$ is not on the path.
2. beq blocks: IMem → RegRead → ALU (subtracts to compare). No memory, no write-back. $200+100+200=500$ ps. Why this step? A branch just compares two registers; the ALU's Zero output decides the branch. It never touches data memory and writes no register.

Verify: $700<800$ and $500<800$, so neither is the critical path — the clock stays 800 ps. All four sit under the lw bar in s01. ✓

---

Case D — a new slow instruction raises the clock for everyone

Recall Forecast: does the

lw path get slower? Which instruction is now critical? lw is unchanged (still 800). But mul might exceed it.

Steps.

1. mul path (R-type shape, slow ALU): $t_{IMem}+t_{RegRead}+t_{ALU,mul}+t_{RegWrite}=200+100+500+100$. Why this step? mul writes a register and does no memory, so it has the R-type block list — only its ALU cost changed.
2. Total $=900$ ps.
3. New clock $=\max (800,900)=900$ ps. Why this step? The clock period is the maximum over all instructions (parent formula $T_{clk}\ge {\max }_{\text{instr}}(\dots )$). One slow instruction wins.

Verify: $200+100+500+100=900>800$, so $\max =900$. ✓

---

Case E — zero / degenerate delay

Recall Forecast: which instructions shrink? Is

lw still critical? Every instruction that writes a register loses 100 ps; sw/beq don't (they never write-back).

Steps.

1. New paths with $t_{RegWrite}=0$:
   • R-type: $200+100+200+0=500$
   • lw: $200+100+200+200+0=700$
   • sw: $700$ (unchanged — no write-back to remove)
   • beq: $500$ (unchanged) Why this step? Setting a block delay to 0 means signals pass it "for free"; the block is still logically there, it just adds nothing.
2. New clock $=\max (500,700,700,500)=700$ ps. Why this step? Now lw and sw tie at 700 — the critical path became shared. Zeroing one block can change who is critical.

Verify: $\max (500,700,700,500)=700$. Note the surprise: shaving write-back did not help sw, so the ceiling only dropped from 800 to 700, not to 600. ✓

---

Case F — branch target with a positive (forward) offset

Recall Forecast: apply

$(\text{PC}+4)+(\text{SignExt(imm)}\ll 2)$. Which way does it jump? Positive offset ⇒ jumps forward.

Steps.

1. Compute $\text{PC}+4=\text{0x00400010}+4=\text{0x00400014}$. Why this step? MIPS branches are relative to the already-incremented PC (the next instruction), not the branch itself. That "+4" is baked into the definition.
2. Sign-extend imm: 0x0003 = decimal $3$. Top bit is 0, so the 32-bit value is still $+3$. Why this step? Sign-extension copies the top (sign) bit leftward. Here it's 0, so no change — but we do this before shifting (order matters, see the parent's mistake note).
3. Shift left 2: $3\ll 2=3\times 4=12=\text{0x0000000C}$ bytes. Why this step? The offset counts instructions (words); each word is 4 bytes, so $\times 4$ (= shift left 2) turns a word-count into a byte-address distance.
4. Add: $\text{0x00400014}+\text{0x0000000C}=\text{0x00400020}$.

Verify: $0x00400010=4194320$; target $=4194320+4+12=4194336=\text{0x00400020}$. The arrow in s02 points 3 instructions past the next one — a forward jump. ✓

---

Case G — branch target with a negative (backward) offset

Recall Forecast: the top bit of

0xFFFC is 1. What does that mean for the sign? Top bit 1 ⇒ negative ⇒ jumps backward.

Steps.

1. $\text{PC}+4=\text{0x00400014}$ (same reason as Ex 6).
2. Sign-extend imm = 0xFFFC. Its 16-bit sign bit is 1, so it is negative. As a signed 16-bit number, 0xFFFC $=-4$. Why this step? This is the whole point of sign-extension: a 1 in the top bit must be copied all the way left so the 32-bit number stays $-4$, not a giant positive 0x0000FFFC. Do this before shifting or you'd shift the wrong (unsigned) value.
3. Shift left 2: $-4\ll 2=-4\times 4=-16=\text{0xFFFFFFF0}$ bytes (in two's complement). Why this step? $\times 4$ still converts word-count → bytes; the sign carries through.
4. Add: $\text{0x00400014}+(-16)=\text{0x00400004}$.

Verify: $4194320+4-16=4194308=\text{0x00400004}$ — that is 3 instructions before the branch, exactly a loop back. If we had forgotten sign-extension, we'd have added $0x0000FFFC\times 4$, a huge forward jump — the classic bug. ✓

---

Case H — control signals with "don't care"

Recall Forecast:

sw writes memory but no register. Which signals become "don't care"? Any signal that only matters when we write a register is a don't-care.

Steps.

1. RegWrite = 0. Why? A store produces no register result; writing would corrupt a register.
2. ALUSrc = 1. Why? The ALU's second input must be the sign-extended offset to form the address, not a register.
3. MemRead = 0, MemWrite = 1. Why? We are writing memory, not reading it.
4. Branch = 0. Why? sw is not a branch; next PC is just PC+4.
5. MemToReg = X. Why? This mux only chooses what value to write into a register — but RegWrite=0, so nothing is written; its value is irrelevant.
6. RegDst = X. Why? This mux only chooses which register to write. Again RegWrite=0, so the destination is never used.

Verify: RegWrite=0 justifies both X's; every non-X value matches the parent's control table row for sw. ✓

---

Case I — real-world word problem (speedup)

Recall Forecast: the

Performance equation is $\text{Time}=N\times \text{CPI}\times T_{clk}$. Guess the speedup ratio. Same $N$, same CPI ⇒ speedup is just the ratio of clock periods.

Steps.

1. Single-cycle time: $T_1=N\times \text{CPI}\times T_{clk}=10^6\times 1\times 800\text{ps}=8.0\times 10^8$ ps $=800\mu s$. Why this step? This is the Performance equation: total time = instructions × cycles-per-instruction × seconds-per-cycle.
2. Pipelined time: $T_2=10^6\times 1\times 200\text{ps}=2.0\times 10^8$ ps $=200\mu s$.
3. Speedup $=T_1/T_2=800/200=4\times$. Why this step? With $N$ and CPI identical, the ratio collapses to the clock-period ratio.

Verify: $10^6\times 800=8\times 10^8$ ps and $10^6\times 200=2\times 10^8$ ps; ratio $=4$. Units: ps × count = ps of total wall-clock. ✓

---

Case J — exam twist: "just reuse the ALU"

Recall Forecast: within

one cycle, how many additions must happen at the same instant for an R-type? At least two: the instruction's own arithmetic and PC+4.

Steps.

1. In single-cycle, PC+4 must be ready in the same tick the ALU is doing the instruction's arithmetic. Why this step? Everything finishes in one cycle, so PC+4 and the ALU result are needed simultaneously, not one-after-another.
2. A single ALU can perform only one operation per cycle. If it computed PC+4, it could not also compute, say, $t1+$t2 in that same cycle. Why this step? You cannot time-share hardware within a single cycle — there is no second sub-step to hand the ALU back to.
3. Therefore a dedicated adder for PC+4 (and another for the branch target) is mandatory in single-cycle.
4. Contrast: a Multi-cycle datapath can reuse the ALU because it spreads an instruction across several cycles, giving the ALU different jobs on different cycles.

Verify: Consistent with the parent's mistake note ("cannot time-share within a cycle"); the resolution is different across designs, which is the examiner's trap. ✓ (No number to check.)

---

Recall One-line summary of the whole matrix

Every question reduces to two ideas: (1) sum the blocks a specific instruction actually touches, and (2) the clock is the max over all instructions — plus the branch-address recipe sign-extend, then shift-left-2, then add to PC+4.

---

Active-recall