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
The Program Counter
Branching
Using Assembly

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 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

wasm - Web Assembly (spec; examples)
Shaders & WebGL are related (they’re the equivalent for the GPU instead of the CPU).
High-performance computing and/or custom architectures (example: simulating fluids using huge chips)
Making things fast and/or small (e.g., Kolibri OS; this 127-byte program)
- Demoscene: the most impressive small programs
- Pico-8
Disassembly + hacking/security

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