CS 240 Lab 5: Processor Datapath

Peter Mawhorter

How do Computers Work?

How do Computer Circuits Work?

  • Power flows through chips in the computer, creating patterns of activation driven by a clock and determined by logic gates.
  • Flip-flops allow information to be stored and then updated on a clock edge, allowing circuits to compute values that change every tick.
  • An ALU performs basic operations, a register file stores operands & results, and RAM stores lots of data.

How do Computers Represent Things?

  • High/low voltage patterns represent numbers in binary and/or symbols.
    • These are stored in arrays of flip-flops called registers.
    • Random Access Memory provides bigger/slower storage.
    • A sequence of data in RAM can represent e.g., text.
  • Basic operations with these numbers, like addition, are done by an Arithmetic Logic Unit.
    • All other operations are sequences of basic operations.

But what about… ?

  • What controls the ALU?
  • How does the computer decide what to do next?
    • How does a program continue until input says to stop?
  • How is code in a language like C translated into machine instructions?

How does the OS Work?

  • OS allows user to launch programs.
    • Programs are files on the computer.
    • OS has a command-line for text control, plus maybe other interfaces.

But what about… ?

  • How does the “boot” process work? Where does the operating system actually start?
  • What language does the “shell” use? Why are shells still around when we have graphical interfaces?
  • How does one program launch another? How does the OS keep track of programs that are running? How do two programs run at the same time?
  • How do compliers actually work? How does our text written in a programming language turn into a program, and what does a “program” actually consist of?

What we’ll see today

  • What controls the ALU?
  • How does the computer decide what to do next?
  • What does a “program” actually consist of?

Outline

Computer Architecture

Instruction Set Architecture

  • What kinds of instructions can be used?
    • How big are they?
    • Which parts mean what?
    • What effect they will have?
  • What memory can instructions access directly?
    • How many registers?
    • How big are they?
    • How big is a program/RAM address?

An image of the table below showing the assembly syntax, meaning, and encoding for each instruction in the HW ISA. The Opcode, Rs, Rt, and Rd values together are encoded in 16 bits (4 bits = 1 hex digit each). The opcode bits are the most significant bits, while the Rd bits are least significant. Note: The JMP offset is unsigned. All other offsets are signed. 

Assembly Syntax Meaning
(R = register file, M = data memory)		 Opcode Rs Rt Rd
ADD Rs, Rt, Rd R[d] ← R[s] + R[t] 0010 s t d
SUB Rs, Rt, Rd R[d] ← R[s] - R[t] 0011 s t d
AND Rs, Rt, Rd R[d] ← R[s] & R[t] 0100 s t d
OR Rs, Rt, Rd R[d] ← R[s] | R[t] 0101 s t d
LW Rt, offset(Rs) R[t] ← M[R[s] + offset] 0000 s t offset
SW Rt, offset(Rs) M[R[s] + offset] ← R[t] 0001 s t offset
BEQ Rs, Rt, offset If R[s] == R[t] then
PC ← PC + 2 + offset * 2		 0111 s t offset
JMP offset PC ← offset * 2 1000 offset
HALT Stops the program 1111 ignored

Instruction Set Architecture

  • What kinds of instructions can be used? (ADD, SUB, etc.)
    • How big are they? (16 bits)
    • Which parts mean what? (4 bits opcode, etc.)
    • What effect they will have? (meanings)
  • What memory can instructions access directly?
    • How many registers? (16 registers)
    • How big are they? (16 bits)
    • How big is a program/RAM address?
      • (8 bits → 256b program; 16 bits → 65536b RAM)

Microarchitecture

  • The specific implementation of an ISA
    • Could have faster/smaller/cooler versions
    • Full chip layout + connections

The datapath for the HW architecture. At the left, we start with the PC, which is a single register and which gets input from a line we’ll get to later called “PC input”. The PC feeds into the read address input of instruction memory, which outputs an instruction (16 bits) to the right. The PC also feeds into an adder whose other input is the number 2, and this gets forwarded to the branch-equal (or BEQ) mechanism. Back to the instruction, it gets split into bits 0-3, 4-7, 8-11, and 12-15. Bits 12-15 go to the control unit, drawn as a circle, which generates “Mem,” “Branch,” “Mem store,” “Reg Write,” and “ALU Control” outputs. We’ll see those pop up later, for now going back to the Instruction Memory outputs, bits 0-3 and 4-7 go into a 2x1 mux which feeds the write address of the register file, and which is selected by the “Mem” control signal. Bits 0-3 also bypass the Register file, go through a sign extender to become 16 bits, which we’ll call “offset.” This offset feeds into another 2x1 mux for the second ALU operand that’s also controlled by the “Mem” signal, as well as going to a shift-left-by-1 to become the second input to the first adder in the BEQ mechanism mentioned before. This BEQ mechanism adds the PC + 2 to the offset and then selects between that result and the original PC + 2 result using a 2x1 mux which is selected by an AND result combining the “Branch” control signal and the “Zero” output of the ALU. The result of that mux is the PC input mentioned right at the beginning. That wraps up destinations for the “offset,” backing up to the instruction bits, bits 4-7 also go to the Read address 2 for the Register file, while bits 8-11 go to the Read address 1. The only other Register file input is the Write Data, but we’ll get to that later. With two read addresses specified, along with a write address, the register file takes the “Reg Write” control signal as its “Write Enable” input, and outputs “Read data 1” and “Read data 2.” Read data 1 is 16 bits and goes straight in as the first operand of the ALU. Read data 2 (also 16 bits) is the second input to the mux described earlier that feeds the second ALU operand (whose other input if you recall is the sign-extended bits 0-3 of the instruction itself). Read data 2 is also forwarded to the Data Memory as its “Write Data” input (more on that in a second). This takes care of the outputs of the register file; with two operands to work with, the ALU also gets the ALU control signal from the control unit, and produces the aforementioned “Zero” output plus a 16-bit result. The ALU result serves as input to the Data Memory “Address” input, and also goes to a 2x1 mux below data memory which connects back to the “Write Data” input of the register file we mentioned earlier. That mux is controlled by the “Mem” signal from the control unit, and its other input is the “Read Data” output of the Data Memory, so either the ALU result or a piece of data whose address is specified by the ALU result will get written to a register file (if “Write Enable” is on, of course). As mentioned previously, the Data Memory also gets Write Data input from the Register File’s Read Data 2 output. It’s third and final input is a “Write Enable” which comes from the “Mem store” control unit signal. As already mentioned, its only output (“Read Data”) feeds into a mux and (if selected) back to the register file’s write input. And that’s the end of the datapath! 

The schematic diagram of the full CPU.

The CPU connections listed as a table:

Component Inputs Outputs
PC
  • Next Address from BEQ Logic
  • PC to read address of Instruction Memory
  • PC + 2 to next address for BEQ Logic
Instruction Memory
  • Read Address from PC
  • 16-bit Instruction splits into
    • Bits 12-15 go to the Control Unit
    • Bits 8-11 go to Read Addr 1 of Register File
    • Bits 4-7 go to:
      • Read Addr 2 of Register File
      • Register File Write Addr Mux
    • Bits 0-3 go to:
      • Register File Write Addr Mux
      • Sign extend to 16 bits and then:
        • ALU 2nd Operand Mux
        • Shift left 1 into Offset for BEQ Logic
Control Unit
  • Bits 12-15 of Instruction
  • Reg Write signal goes to Write Enable of Register File
  • ALU Control signal goes to control inputs of ALU
  • Branch signal goes to BEQ Logic Branch input
  • Mem Store signal goes to Write Enable of Data Memory
  • Mem signal goes to:
    • Register File Write Addr Mux
    • ALU 2nd operand Mux
    • ALU/Memory result Mux
Register File
  • Read Addr 1 from bits 8-11 of Instruction
  • Read Addr 2 from bits 4-7 of Instruction
  • Write Addr from Register File Write Addr Mux (either bis 0-3 or 4-7 of instruction)
  • Write Data from Final Result Mux (either ALU Result or Data Memory Read Data output)
  • Write Enable from Reg Write output of Control Unit
  • Read Data 1 goes to ALU 1st Operand
  • Read Data 2 goes to:
    • The ALU 2nd operand Mux (along with sign-extended instruction bits)
    • The Write Data input for Data Memory
Arithmetic Logic Unit (ALU)
  • 1st operand from Read Data 1 of the Register File
  • 2nd operand from the ALU 2nd operand Mux (either Read Data 2 from the Register File or bits 0-3 of the instruction after sign extension to 16 bits)
  • ALU Control output from Control Unit
  • 16-bit result goes to:
    • Address input for Data Memory
    • Final Result Mux (along with Read Data from Data Memory)
  • Zero flag goes to Zero input to BEQ Logic
Data Memory (RAM)
  • Read Address from ALU result
  • Write Data from Register file Read Data 2 output
  • Write Enable from Control Unit Mem Store signal
  • Read Data result goes to Final Result Mux (along with ALU result)
BEQ Logic
  • Next Address from PC + 2
  • Offset from bits 0-3 of instruction after sign extend and shift left by 1
  • Branch from Control Unit
  • Zero from ALU Zero Flag
  • Adds PC + 2 and Offset inputs and then selects that result or the original PC + 2 result using an AND between the Branch and Zero inputs. Takes this result as the Next Address and feeds it back to the PC.

The Program Counter

  • Instructions are stored in special instruction memory
  • Program Counter holds address of current instruction
  • By default Program Counter advances by 1 instruction
    • (16 bit instructions → 2 bytes)
  • Branch/Jump may alter PC

Branching

  • JMP instruction allows arbitrary ordering & infinite loops
  • BEQ instruction allows conditional jump → if/else
  • JMP + BEQ can do a conditional loop:
    • JMP up by default
    • BEQ across the JMP when loop is done

The Power of Branching

  • BEQ makes assembly code Turing-complete
    • (Well, almost…)
    • See CS 235
  • Without BEQ, each instruction is always or never executed
  • With BEQ, we can have conditional execution: execution depends on data values
    • Things like key presses are really just data values to the CPU

Using Assembly

An image of the table below showing the assembly syntax, meaning, and encoding for each instruction in the HW ISA. The Opcode, Rs, Rt, and Rd values together are encoded in 16 bits (4 bits = 1 hex digit each). The opcode bits are the most significant bits, while the Rd bits are least significant. Note: The JMP offset is unsigned. All other offsets are signed. 

Assembly Syntax Meaning
(R = register file, M = data memory)		 Opcode Rs Rt Rd
ADD Rs, Rt, Rd R[d] ← R[s] + R[t] 0010 s t d
SUB Rs, Rt, Rd R[d] ← R[s] - R[t] 0011 s t d
AND Rs, Rt, Rd R[d] ← R[s] & R[t] 0100 s t d
OR Rs, Rt, Rd R[d] ← R[s] | R[t] 0101 s t d
LW Rt, offset(Rs) R[t] ← M[R[s] + offset] 0000 s t offset
SW Rt, offset(Rs) M[R[s] + offset] ← R[t] 0001 s t offset
BEQ Rs, Rt, offset If R[s] == R[t] then
PC ← PC + 2 + offset * 2		 0111 s t offset
JMP offset PC ← offset * 2 1000 offset
HALT Stops the program 1111 ignored