Lets build a computer!

Designing a CPU

CPU: central processing unit computer: CPU + display + optical disk + metal case + power supply + ...

Last lecture: circuit that implements an adder This lecture: circuit that implements a CPU
Introduction to Computer Science Robert Sedgewick and Kevin Wayne Copyright 2008 http://www.cs.Princeton.EDU/IntroCS

the difference between your computer and a TV set

TOY Lite
TOY machine. 256 16-bit words of memory.

Primary Components of Toy-Lite CPU

16 16-bit registers. 1 8-bit program counter. 2 instruction types 16 instructions.

opcode

Rs

Rd1

Rd2
4 bits to specify one of 16 registers

! Arithmetic and Logic Unit (ALU)

opcode

Rs

addr

Memory
8 bits to specify one of 256 memory words

TOY-Lite machine. 16 10-bit words of memory.

opcode

Rs

Rd1

Rd2
2 bits to specify one of 4 registers

Toy-Lite Registers

4 10-bit registers. 1 4-bit program counter. 2 instruction types 16 instructions.

opcode

Rs

addr

Processor Registers: Program Counter and Instruction Register

4 bits to specify one of 16 memory words

Control Goal: CPU circuit for TOY-Lite (same design extends to TOY, your computer)
3 4

A New Ingredient: Circuits With Memory

Combinational circuits. SR Flip-flop.

SR Flip-Flop
x y OR x+y x y NOR ( x + y )

Output determined solely by inputs. Ex: majority, adder, decoder, MUX, ALU. Output determined by inputs and current state. Ex: memory, program counter, CPU. Two controlled switches A and B, both connected
to power, each blocked by the other. State determined by whichever switches first.

Sequential circuits.

Two cross-coupled NOR gates A way to control the feedback loop. Abstraction that "remembers" one bit. Basic building block for memory and registers.

OR gate

NOR gate write 0 write 1

memory bit

Ex. Simplest feedback loop.

Stable.

Aside. Feedback with an odd number of switches is a buzzer (not stable). Doorbell: buzzer made with relays. Caveat. Timing, switching delay.

Memory Overview
Computers and TOY have several memory components. Program counter and other processor registers.

Processor register Bit

Processor register bit. Extend a flip-flop to allow easy access to values.

TOY registers (4 10-bit words in Toy-Lite). Main memory (16 10-bit words in Toy-Lite).

write 0

write 1

Implementation. Use one flip-flop for each bit of memory.

memory bit

Use buses and multiplexers to group bits into words.

read

Access mechanism: when are contents available? Processor registers: enable write.

Main memory: select and enable write. TOY register: dual select and enable write

need to be able to read two registers at once

Memory Bit Interface

Memory and TOY register bits: Add selection mechanism.

Memory Bit: Switch Level Implementation

Memory and TOY register bits: Add selection mechanism.

[ TOY PC, IR ]

[ TOY main memory ]

[ TOY registers ]

[ TOY PC, IR ]

[ TOY main memory ]

[ TOY registers ]

10

Processor Register
Processor register. Stores k bits.
don't confuse with TOY register

Processor Register
Processor register. Stores k bits.
don't confuse with TOY register

Register contents always available on output bus. If enable write is asserted, k input bits get copied into register.

Register contents always available on output bus. If enable write is asserted, k input bits get copied into register.

Ex 1. TOY-Lite program counter (PC) holds 4-bit address. Ex 2. TOY-Lite instruction register (IR) holds 10-bit current instruction.

Ex 1. TOY program counter (PC) holds 8-bit address. Ex 2. TOY instruction register (IR) holds 16-bit current instruction.

(4-bit)

11

12

Processor Register
Processor register.
don't confuse with TOY register

Memory Bank
Memory bank.

Stores k bits. Register contents always available on output bus. If enable write is asserted, k input bits get copied into register.

Ex 1. TOY program counter (PC) holds 8-bit address. Ex 2. TOY instruction register (IR) holds 16-bit current instruction.

Bank of n registers; each stores k bits. Read and write information to one of n registers. Address inputs specify which one. log n address bits needed Addressed bits always appear on output. If write enabled, k input bits are copied into addressed register.
2

Ex 0 (for lecture). 4-by-6 (four 6-bit words) Ex 1. Main memory bank. TOY: 256-by-16

(4-bit)

TOY-Lite: 16-by-10 TOY: 16-by-16 TOY Lite: 4-by-10 Two output buses.

Ex 2. Registers.

13

14

Memory: Interface

Memory: Component Level Implementation

Decoder plus memory selection: connect only to addressed word.

(four 6-bit words)

6-bit

2-bit 6-bit

15

16

Memory: Switch Level Implementation

16 10-bit words
(four 6-bit words)

TOY-Lite Memory

input connected to registers for store output connected to registers for load addr connect to processor Instruction Register (IR)

to registers (out)

to registers (in) to IR

17

18

Another Useful Combinational Circuit: Multiplexer

Multiplexer (MUX). Combinational circuit that selects among input buses. Exactly one select line i is activated.

Nuts and Bolts: Buses and Multiplexers

Multiplexer (MUX). Combinational circuit that selects among input buses. Exactly one select line i is activated.

Copies bits from input bus i to output bus.

Copies bits from input bus i to output bus.

19

20

Toy-Lite Registers
4 10-bit words

Primary Components of Toy-Lite CPU

Dual-ported to support connecting two different registers to ALU Input MUX to support input connection to ALU, memory, IR, PC
to ALU (in) MUX select to ALU (out)

! ALU

Memory

Registers

Processor Registers: Program Counter and Instruction Register

Not quite done. Need to be able to increment.

Control
to PC to memory, IR
21 22

How To Design a Digital Device

How to design a digital device. Design interface: input buses, output buses, control wires.

Program Counter: Interface

Counter. Holds value that represents a binary number. Load: set value from input bus.

Determine components. Determine datapath requirements: Establish control sequence.

"flow" of bits.

Increment: add one to value. Enable Write: make value available on output bus.

Ex. TOY-Lite program counter (4-bit).

Warmup. Design a program counter (3 devices, 3 control wires).

Goal. Design TOY-Lite computer (10 devices, 27 control wires).

23

24

Program Counter: Components

Components. Datapath.

Program Counter: Datapath and Control

Register. Incrementer. Multiplexer (to provide connections for both load and increment).

Layout and interconnection of components. Connect input and output buses.

Control. Choreographs the "flow" of information on the datapath.

25

26

Program Counter: Datapath and Control

Datapath. Layout and interconnection of components.

Program Counter: Datapath and Control

Datapath. Layout and interconnection of components.

Connect input and output buses.

Connect input and output buses.

Control. Choreographs the "flow" of information on the datapath.

Control. Choreographs the "flow" of information on the datapath.

27

28

Program Counter: Datapath and Control

Primary Components of Toy-Lite CPU

! ALU

!
1. load: copy input to register 3. increment: output plus 1 available in MUX copy to register

Memory

Toy-Lite Registers

Processor Registers: Program Counter and Instruction Register

Control
2. enable write: register contents available on output 4. enable write: register contents available on output
29 30

How To Design a Digital Device

How to design a digital device. Design interface: input buses, output buses, control wires. CPU is a circuit.

TOY-Lite: Interface

Determine components. Determine datapath requirements: Establish control sequence.

"flow" of bits.

Interface: switches and lights. set memory contents set PC value

Warmup. Design a program counter (3 devices, 3 control wires).

press RUN [details of connection to circuit omitted]

Next. Design TOY-Lite computer (10 devices, 27 control wires).

31

32

TOY-Lite: Components

TOY-Lite: Layout

33

34

TOY-Lite Datapath Requirements: Fetch

Basic machine operation is a cycle. Fetch

TOY-Lite Datapath Requirements: Execute

Instructions determine datapaths and control sequences for execute

Execute

Fetch
0 1 halt add subtract and xor shift left shift right load address load store load indirect store indirect branch zero branch positive jump register jump and link

... ...

Fetch.

Memory[PC] to IR Increment PC Datapath depends on instruction

IR opcode to control control to ALU two registers to ALU ALU to register MUX

Execute

3 4 5 6 7 8 9 A B C D E F

Execute.

... ... ... ... ...

...

35

36

TOY-Lite: Datapaths and Control

Datapath: Add

control wires

fetch:
Memory[PC] to IR

execute:
IR opcode to control

increment
datapaths

control to ALU two registers to ALU ALU to register MUX

38

increment PC

37

Datapath: Load

Last step
Control. Each instruction corresponds to a sequence of control signals. Q. How do we create the sequence? A. Need a physical clock.

Solution 2: Use a buzzer [need sufficiently long cycle to cover CPU switching]

clock
Solution 1: Use some other technology

fetch:
Memory[PC] to IR

CPU

CPU

execute:
IR opcode to control

increment
increment PC

IR to addr MUX memory to register MUX

39

40

Clock
Clock.
Solution 3?

How much does it Hert?

Frequency is inverse of cycle time.
n

Fundamental abstraction: regular on-off pulse.

fetch phase off: execute phase external device.
on:

Expressed in hertz. Frequency of 1 Hz means that there is 1 cycle per second. 1 kilohertz (kHz) means 1000 cycles/sec. 1 megahertz (MHz) means 1 million cycles/sec.
1 1

Synchronizes operations of different circuit elements. Requirement: clock cycle longer than max switching time.

gigahertz (GHz) means 1 billion cycles/sec. terahertz (THz) means 1 trillion cycles/sec.

cycle time

on
Clock

off

Heinrich Rudolf Hertz (1857-1894)

41

42

Clocking Methodology
Two-cycle design. Each control signal is in one of four epochs.
fetch fetch

One Last Combinational Circuit: Control

Control. Circuit that determines control line sequencing.
data bus to memory input external clock just ticks

and clock and clock

execute execute

[set memory address from pc] [write instruction to IR] [set ALU inputs from registers] [write result of ALU to registers]

control lines to processor registers

Fetch

Fetch Execute Clock

43

opcode from IR control lines to ALU data bus from ALU

44

Tick-Tock
CPU is a circuit, driven by a clock. Switches initialize memory, PC contents Clock ticks

TOY "Classic", Back Of Envelope Design

fetch instruction from memory[PC] to IR increment PC execute instruction

[details of instruction execution differ]
Fetch

fetch next instruction ...

Thats all there is to it!

Execute

45

46

TOY-Lite CPU

Real Microprocessor (MIPS R10000)

47

48

Layers of Abstraction
Abstraction Abstract Switch Connector Clock Logic Gates Built From raw materials raw materials raw materials abstract switches, connectors logic gates, connectors logic gates, clock, connector decoder, multiplexer, adder, flip-flop components Examples transistor, relay wire crystal oscillator AND, OR, NOT decoder, multiplexer, adder, ALU flip-flop registers, ALU, counter, control TOY
49

History + Future
Computer constructed by layering abstractions.

Better implementation at low levels improves everything. Ongoing search for better abstract switch! 1820s: mechanical switches. 1940s: relays, vacuum tubes. 1950s: transistor, core memory. 1960s: integrated circuit. 1970s: microprocessor. 1980s: VLSI. 1990s: integrated systems. 2000s: web computer. Future: quantum, optical soliton,

History.

Combinational Circuit

Sequential Circuit

Components Computer

Ray Kurzweil
http://en.wikipedia.org/wiki/Image:PPTMooresLawai.jpg

50