Assembling SEQ

We have the parts and we have the wiring diagram in words. The stage tables gave the computations; the control logic gave the signals; the digital-logic module gave the units. This lesson bolts them together into SEQ, the complete sequential Y86-64 processor, and draws it the canonical way: the six stages as horizontal bands, Fetch at the bottom and PC update at the top, so that signals flow generally upward and the next-PC value loops back down to the PC register. Then we work out the timing (what one cycle must accomplish and what sets its length) and trace two instructions through the assembled datapath to prove the wiring is right.

The layout: stages as bands, bottom to top

CS:APP draws SEQ upside-down relative to the stage list: the work starts at the floor and rises. The reason is the data flow. Fetch reads the PC and produces the fields; those feed Decode just above; the register values rise into Execute; the ALU result rises into Memory; the loaded or computed values rise toward Write-back; and at the very top, PC update computes newPC and sends it back down the left margin to the PC register, ready for the next cycle. Drawing it this way keeps every hand-off vertical, and it puts the two long feedback paths — write-back into the register file, newPC into the PC — in the margins where they cross nothing they should not.

The figure is busy because the machine is, but the discipline is simple. Functional units sit in their band, and data rises through the center column. Values that skip stages ride bypass lanes in the margins: valC and valP climb the right side from Fetch straight to the New-PC mux, valA rides across to the data-memory write port, and valC cuts up the left into the aluA mux. The two write-back values, valE and valM, tee off their rising wires and descend the left margin into the register file's E and M write ports. The one wire that travels the whole height is newPC, looping from the top back down into the PC. Every wire in the figure is one row of some stage table made physical; if a wire seems unmotivated, some instruction in lesson 2 is its reason.

Two wires reward a second look. The valA lane into data memory exists because rmmovq and pushq store a register value the ALU never touches; the ALU is busy computing the address. And valM rises all the way into the New-PC mux because of one instruction, ret; for every other instruction that input is ignored.

Timing: one cycle, one instruction

SEQ has exactly four clocked state elements: the PC, the condition codes, the register file, and data memory. Everything else — every mux, the ALU, the control logic, the wires above — is combinational: outputs follow inputs after a gate delay, with no memory of their own. The processor's operation is then a strict two-beat rhythm:

1. During the cycle, the state elements hold still and the combinational logic settles. The PC's current value ripples up the figure: fetch produces the fields, decode reads registers, the ALU computes, memory reads, and the New-PC mux produces newPC. Late in the cycle every wire holds its final value.
2. At the rising clock edge, all four state elements load at once, each with its commit condition:

   State element	Loads	Commit condition
   PC	newPC	always
   Condition codes	ALU flags	set_cc
   Register file	valE→dstE, valM→dstM	dst ≠ RNONE
   Data memory	valA→mem_addr	mem_write

   
   The instant after the edge, the next instruction's cycle begins from the new state.

The design works only if a consistency condition holds: nothing computed during the cycle may depend on state the same instruction is about to write. Otherwise the combinational logic would chase its own tail: the write would change a value that fed the write.

The stage tables were written to respect this. pushq %rsp stores the old stack pointer because Memory stores valA, a wire that captured the register before any update; the decremented valE lands in %rsp only at the edge, after the store's data is already decided. popq %rsp never re-reads %rsp after its increment; both candidate values (valE, valM) are wires, and a mux picks which one the register file commits. Even the condition codes obey it: an OPq sets CC at the edge, and the jXX that reads CC is a later instruction, reading the committed value in its own cycle. State is read at the top of the cycle and written at the bottom, never both.

The critical path

The clock cannot tick until the slowest signal has settled, so the cycle time is set by the critical path: the longest chain of combinational delay between one rising edge and the next. Writing $t_i$ for the propagation delay of unit $i$ and $t_{\text{setup}}$ for the register setup time, the minimum clock period is

In SEQ that maximizing chain belongs to the instructions that use memory late and need its answer for state: think of ret, where the PC's value must traverse instruction memory (fetch the icode), the register file (read %rsp), the ALU path, then data memory (read the return address), and finally the New-PC mux — all before newPC is stable enough to clock in.

The numbers are illustrative; the structure is not. Two consequences matter. First, every instruction pays the worst-case time: a nop finishes its work almost instantly and then idles for the rest of the cycle, because the clock serves the slowest customer. Second, the path runs through two memory accesses in series (instruction fetch, then data access) plus the register file and ALU between them — which is most of the reason SEQ's clock must be slow. Cutting this chain into pieces that run concurrently is the job of pipelining, and the six-band drawing above is already the blueprint for those pipeline stages.

Put numbers to it to see what the single-cycle rule costs. With the illustrative delays above — 90, 60, 80, 120, 20 ps — a ret needs $90+60+80+120+20=370$ ps of settling; add $t_{\text{setup}}=20$ ps and $T_{\text{clk}}\ge 390$ ps, an $f_{\text{max}}\approx 2.56$ GHz ceiling. But addq stops at the ALU: its longest path skips data memory, giving $t_{\text{addq}}=90+60+80+20=250$ ps, a would-be 4 GHz. SEQ does not allow it: one clock serves every instruction, so addq runs at 390 ps and idles the slack $390-250=140$ ps every cycle. A program that is mostly arithmetic pays the memory instructions' worst-case time on every single cycle. This is the concrete, measurable cost of one cycle per instruction, sized for the worst instruction, and it is the motivation for everything that comes after SEQ.

Walking an OPq through SEQ

Take a concrete OPq: subq %rdx, %rbx, computing $R[\text{\%rbx}]\leftarrow R[\text{\%rbx}]-R[\text{\%rdx}]$. Follow it up the bands.

• Fetch reads two bytes at the PC: 61 23. icode:ifun = 6:1 (OPq, subq); the register byte is rA:rB = 2:3 (%rdx:%rbx). valP = PC + 2.
• Decode sets srcA = rA = %rdx and srcB = rB = %rbx, reading valA = R[%rdx] and valB = R[%rbx]. dstE = rB = %rbx; dstM = RNONE.
• Execute sends valA to aluA and valB to aluB, with alufun = ifun = subq, so valE = valB - valA. Because icode == IOPQ, set_cc is true and the ALU flags will latch into ZF/SF/OF at the edge.
• Memory does nothing: mem_read and mem_write are both false for OPq.
• Write-back commits valE into dstE = %rbx through the E port; the M port is idle (dstM = RNONE).
• PC update finds icode is not call, jump, or ret, so newPC = valP, and PC advances to the next instruction.

Every band did exactly what its row in the OPq stage table promised, and the only muxes that mattered were aluA/aluB (picking the register values) and New PC (picking valP).

Walking a ret through SEQ

ret exercises the parts OPq left idle: the stack, the memory read port, and the interesting input to the New-PC mux. Its one byte is 90.

• Fetch reads 90: icode:ifun = 9:0. There is no register byte and no constant, so valP = PC + 1.
• Decode has no rA/rB, but the control logic sets srcA = %rsp and srcB = %rsp for ret, so both valA and valB read the stack pointer. dstE = %rsp; dstM = RNONE.
• Execute picks aluA = +8 and aluB = valB, with alufun = ADD, so valE = R[%rsp] + 8, the incremented stack pointer. set_cc is false; the flags are untouched.
• Memory has mem_read true with mem_addr = valA = R[%rsp] — the old stack top — so valM = M[R[%rsp]], the return address.
• Write-back commits valE (the incremented pointer) into dstE = %rsp. dstM is RNONE, so the loaded valM is not written to any register; it is bound for the PC instead.
• PC update finds icode == IRET, so newPC = valM. The processor jumps to the return address, and %rsp has moved up by 8.

The decisive wire is the one carrying valM past Write-back and into the New-PC mux: that single connection, selected only when icode == IRET, is what makes ret a control transfer rather than a load. Contrast popq, which routes the very same valM into a register (dstM = rA) and lets newPC fall through to valP. Same memory read, different destination — and the difference is one mux input.

SEQ+ and the road to the pipeline

The SEQ we just assembled computes newPC at the very end of the cycle, at the top of the drawing, and loops it all the way back down to the PC register. That long feedback wire is harmless in a single-cycle machine, but it is precisely the wrong shape for pipelining, where each stage must begin and end at a clean register boundary. CS:APP's next step, SEQ+ (Bryant & O'Hallaron, CS:APP §4.5.1), fixes this with a small rearrangement: move the PC computation to the start of the cycle, so the machine computes the address of the instruction it is about to run from signals it saved on the previous cycle.

What SEQ+ does not have is a program-counter register. The PC is reconstructed each cycle from the saved control signals pIcode, pValC, pValM, and so on. CS:APP names this move circuit retiming (Leiserson & Saxe, 1991) — a transformation that relocates state across combinational logic without changing what the circuit computes, used here to balance stage delays. It rests on a principle worth stating plainly: a processor may represent its state in any form, as long as it produces the correct programmer-visible values for any program. SEQ+ exploits this in a small way (no PC register); the pipelined PIPE design exploits it heavily, and out-of-order cores take it to the extreme of running instructions in an order entirely unlike the program's (CS:APP §5.7). SEQ+ is the single, cheap step that turns SEQ's stage bands into pipeline stages: insert a register between each band and several instructions can occupy the machine at once, which is where the pipelining module begins.

The datapath is assembled, timed, and demonstrably correct on two instructions. The final lesson runs whole programs through it, cycle by cycle, and watches real machine state evolve.