Exercises — Register file organization

WHAT: we want the smallest $k$ with $2^k\ge 16$. WHY: each address bit doubles how many registers you can name; you need enough patterns to give every register a unique name. $k=\lceil {\log }_{2}16\rceil =\lceil 4\rceil =4\text{ bits.}$ Check: $2^4=16$ exactly, so 4 bits name all 16 registers with none left over.

• Read = a ==$2^k$-to-1 multiplexer== (MUX): many inputs, choose one onto the output wire. One MUX per read port.
• Write = a ==$k$-to-$2^k$ decoder== whose outputs are ANDed with a global WriteEnable: it lights up exactly one register's capture line. WHY these two and not others? "Pick one of many onto a wire" is the definition of a MUX; "send one wire to one of many" is the definition of a decoder. They are mirror images of each other. See Multiplexers and Decoders.

WHAT: total state $=N\cdot n$. WHY: ports affect wiring/area, not stored data. The amount you can store is simply (number of slots) × (width of each slot). $N\cdot n=32\times 64=2048\text{ bits.}$

WHAT: each register field is $k=5$ bits, and there are 3 fields. $3\times k=3\times 5=15\text{ bits.}$ WHY it matters: those 15 bits are gone before you even spend a single bit on the opcode. This is exactly why enlarging $N$ is not free — it widens every instruction. See Instruction Set Architecture (ISA).

WHAT: area $\propto (R+W{)}^2$, and $N,n$ are unchanged so they cancel. $\frac{(4+2{)}^2}{(2+1{)}^2}=\frac{6^2}{3^2}=\frac{36}{9}=4.$ WHAT IT LOOKS LIKE: in the grid figure, doubling the ports both thickens the wire bundle through each cell (more wires) and stretches each cell taller and wider — height × width both grow, so the product grows as the square. Four times bigger, not twice.

WHAT the instruction demands: add rd, rs1, rs2 must read rs1 and rs2 in the same cycle (that is 2 simultaneous reads) and later store one result into rd (1 write). WHY that maps to ports: the ALU has two operand inputs and one result output (see Datapath and ALU). Two operands read at once ⇒ $R=2$; one result ⇒ $W=1$. Fewer read ports and the ALU would starve waiting for its second operand. What would change it: issuing more instructions per cycle (superscalar), or an instruction with 3 source operands (e.g. fused multiply-add reads 3), pushes $R$ up; committing two results per cycle pushes $W$ up. Each bump costs the square.

WHAT happens depends on the timing policy:

• Read-first: the read port sees the old R5 value (the write lands on the clock edge, after the read has already sampled).
• Write-first / internal forwarding: the new value is steered onto the read bus, so the reader gets the new R5. WHY it matters: if a later dependent instruction needs the just-computed value and the file is read-first with no help, it reads stale data — a data hazard. Real designs add a forwarding/bypass MUX that compares the read address to the write address and, on a match, feeds the fresh value straight through. See Pipeline Hazards.

WHAT: every issued op needs 2 reads and 1 write, and 3 issue in parallel. $R=3\times 2=6,W=3\times 1=3.$ Area factor: $\frac{(R+W{)}^2}{(2+1{)}^2}=\frac{(6+3{)}^2}{3^2}=\frac{81}{9}=9.$ WHY this shapes real chips: a 3-wide file is 9× the area of a single-issue one. That's why wide machines often bank or cluster the register file — split it into smaller copies so each copy has fewer ports, dodging the square law. This is a core reason superscalar design is hard.

WHAT the trick buys you:

• mov rd, rs $\equiv$ add rd, rs, r0 because $\text{rs}+0=\text{rs}$.
• nop $\equiv$ add r0, r0, r0 — it computes $0+0=0$ and the write to R0 is discarded, so nothing changes. WHY it saves opcodes: you reuse the ALU's add you already built; no dedicated mov/nop opcode needed, freeing encoding space (see RISC vs CISC). Hardware cost: essentially nothing — you don't build flip-flops for R0; its read-MUX input line is tied low (constant 0), and its decoder line is disconnected so writes vanish.

(a) Address width. $k=\lceil {\log }_{2}32\rceil =5$ bits. Why: $2^5=32$ names all registers, R0 included (it still has a name, it just always reads 0). (b) Usable stored bits. All 32 slots have a name but R0 has no flip-flops, so 31 real registers store data: $31\times 64=1984\text{ bits.}$ (The naive $32\times 64=2048$ counts a slot that stores nothing.) (c) Register-name bits per add. Three fields, each $k=5$: $3\times 5=15$ bits. (d) Widening factor. $\frac{(4+2{)}^2}{(2+1{)}^2}=\frac{36}{9}=4$ — four times the area.

Design A area (drop the common $n$): $A_A\propto N(R+W{)}^2=32\times (4+2{)}^2=32\times 36=1152.$ Design B area (two banks, add them): $A_B\propto 2\times [16\times (2+1{)}^2]=2\times (16\times 9)=2\times 144=288.$ Ratio: $A_A/A_B=1152/288=4$. Design B is 4× smaller in this simplified model. WHY it reflects reality: banking dodges the square law by keeping each bank's port count low. The catch (not in the area formula): an operand living in the "wrong" bank forces a cross-bank read, so real designs must schedule operands into the right bank — a genuine engineering trade-off. See Datapath and ALU.

1. $N=16$ ⇒ how many address bits? → $k=4$.
2. $N=32,n=64$, R0 hardwired ⇒ usable stored bits? → $31\times 64=1984$.
3. Going $R=2,W=1\to R=4,W=2$ multiplies area by? → $36/9=4$.
4. 3-issue, 2R+1W each ⇒ $(R,W)$ and area factor? → $R=6,W=3$; $81/9=9$.
5. Why bank a register file? → keeps ports-per-bank low, beating the $(R+W{)}^2$ square law.