Elements of Computing Systems, Nisan & Schocken, MIT Press

www.idc.ac.il/tecs

Computer Architecture
Usage and Copyright Notice:
Copyright 2005 Noam Nisan and Shimon Schocken
This presentation contains lecture materials that accompany the textbook The Elements of
Computing Systems by Noam Nisan & Shimon Schocken, MIT Press, 2005.
We provide both PPT and PDF versions.
The book web site, www.idc.ac.il/tecs , features 13 such presentations, one for each book
chapter. Each presentation is designed to support about 3 hours of classroom or self-study
instruction.
You are welcome to use or edit this presentation as you see fit for instructional and noncommercial purposes.
If you use our materials, we will appreciate it if you will include in them a reference to the books
web site.
If you have any questions or comments, you can reach us at [email protected]

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 1

Babbages Analytical Engine (1835)

We may say most aptly that the
Analytical Engine weaves algebraic
patterns just as the Jacquardloom weaves flowers and leaves
(Ada Lovelace)
Charles Babbage (1791-1871)

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 2

Other early computers and computer scientists

Blaise Pascal
1623-1662

Gottfried Leibniz
1646-1716

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 3

Von Neumann machine (c. 1940)

CPU
Memory

Arithmetic Logic
Unit (ALU)

Input
device

(data
+

Registers

instructions)

Output
device

Control

Stored
program
concept!

John Von Neumann (and others) ... made it possible

Andy Grove (and others) ... made it small and fast.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 4

Processing logic: fetch-execute cycle

CPU
Memory

Arithmetic Logic
Unit (ALU)

Input
device

(data
+

Registers

instructions)
Control

Output
device

Executing the current instruction involves one or more of

the following micro tasks:

Have the ALU compute some function f(registers)

Write the ALU output to selected register(s)

As a side-effect of executing these tasks,

figure out which instruction to fetch and execute next.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 5

The Hack chip-set and hardware platform

Elementary logic gates

Combinational chips

Sequential chips

Computer Architecture

Nand

HalfAdder

DFF

Memory

FullAdder

Bit

CPU

And

Add16

Register

Computer

Or

Inc16

RAM8

Xor

ALU

RAM64

Not

done

RAM512

Mux
Dmux

this lecture

done

RAM4K

Not16

RAM16K

And16

PC

Or16
Mux16

done

Or8Way
Mux4Way16
Mux8Way16
DMux4Way
DMux8Way

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 6

The Hack computer

16-bit Von Neumann platform
Instruction memory and data memory are physically separate
I/O: 512 by 256 black and white screen, standard keyboard
Designed to execute programs written in the Hack machine language
Can be easily built from the chip-set that we built so far in the course
Main parts of the Hack computer:

Instruction memory

Memory:

Data memory

Screen

Keyboard

CPU

Computer (the glue that holds everything together).

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 7

Lecture plan
Instruction memory
Memory:

Data memory

Screen

Keyboard

CPU
Computer

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 8

Instruction memory

out

address
ROM32K
15

16

Function:
Pre-loaded with a machine language program
Always emits a 16-bit number:
out = ROM32K[address]
This number is interpreted as the current instruction.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 9

Data memory
load

in

RAM16K

out
16

16

address
15

Reading/writing logic
Low level: Set address, in, load ; probe out
Higher level (e.g. OS level):

peek(address)
poke(address,value).

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 10

Lecture plan

Instruction memory
Memory:

Data memory

Screen

Keyboard

CPU
Computer

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 11

Screen
load
in
out

16

Screen
address

16

15
Physical
Screen

Functions exactly like a 16-bit 8K RAM :

out = Screen[address]

If load then Screen[address] = in

Side effect:
continuously refreshes a 256 by 512 black-and-white screen.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 12

Screen memory map

Screen

0 0011000000000000
1 0000000000000000
.
.
.

0 1 2 3 4 5 6 7
row 0

31 0000000000000000
32 0001110000000000
33 0000000000000000
.
.
.

0
1

.
.
.

...
...
...

511

.
.
.

row 1

63 0000000000000000

255

...

8129 0100100000000000
8130 0000000000000000
.
.
.
8160 0000000000000000

row
255

refresh several times

each second

Writing pixel(x,y) to the screen:

Low level: Set the y%16 bit of the word found at
Screen[x*32+y/16]
High level: Use drawPixel(x,y)

(OS service, later).

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 13

Keyboard
out

Keyboard
Keyboard

16

Keyboard chip = 16-bit register

Input: 16-bit value coming from a physical keyboard
Output: the scan code of the pressed key, or 0 if no key is pressed
Special keys:

Reading the keyboard:

Low level: probe the contents of the Keyboard register
High level: use keyPressed()

(OS service, later).

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 14

The Hack computer

Instruction memory
Memory:

Data memory

Screen

Keyboard

CPU
Computer

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 15

Memory
load

Memory
0

in
RAM
(16K)

16

address
15

16383
16384

24575
24576

out
16

Screen
memory map
(8K)
Keyboard
memory map

Screen

Keyboard

Function:
Access to any address from 0 to 16,383 results in accessing the RAM
Access to any address from 16,384 to 24,575 results in accessing the Screen
memory map
Access to address 24,576 results in accessing the keyboard memory map
Access to any address > 24576 is invalid.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 16

The Hack computer

Instruction memory
Memory:

Data memory

Screen

Keyboard

CPU
Computer

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 17

CPU
from
data memory

inM
outM

16

instruction
16

CPU

from
instruction
memory

16

writeM
1

to data
memory

addressM
15

pc
reset

15

to instruction
memory

CPU components: ALU + A, D, PC registers

CPU Function: Executes the instruction according to the Hack language specification:
The M value is read from inM
The D and A values are read from (or written to) these CPU-resident registers
If the instruction wants to write to M (e.g. M=D), then the M value is placed in outM, the
value of the CPU-resident A register is placed in addressM, and writeM is asserted
If reset=1, then pc is set to 0;
Otherwise, pc is set to the address resulting from executing the current instruction.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 18

CPU
from
data memory

inM
outM

16

from
instruction
memory

instruction
16

CPU

16

writeM
1

to data
memory

addressM
15

pc
reset

15

to instruction
memory

CHIP
CHIP CPU
CPU {{
IN
IN inM[16],
inM[16], instruction[16],
instruction[16], reset;
reset;
OUT
outM[16],
writeM,
addressM[15],
OUT outM[16], writeM, addressM[15], pc[15];
pc[15];
PARTS:
PARTS:
//
// Implementation
Implementation missing
missing
}}

CPU implementation: next 3 slides.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 19

The C-instruction revisited

dest = comp; jump
binary:

comp
1

c1 c2 c3 c4

dest
c5 c6

d1 d2

jump
d3 j1 j2 j3

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 20

dest = comp; jump

CPU implementation

binary:

comp
1

dest

c1 c2 c3 c4

c5 c6

d1 d2

jump
d3 j1 j2 j3

Chip diagram:
Includes
most of the
exec. logic

ALU output

Control
logic is
hinted.

D
C

decode

outM
ALU

Mux

Mux

instruction

A/M

inM

writeM
addressM

reset
A

PC

pc

Cycle:

Execute logic:

Fetch logic:

Reset logic:

Fetch

Decode

Execute

Execute

If jump then set PC to A

else set PC to PC+1

Set reset to 1,
then to 0.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 21

The Hack computer

Instruction memory
Memory:

Data memory

Screen

Keyboard

CPU
Computer

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 22

Computer-on-a-chip interface

reset

Screen

Computer

Keyboard

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 23

Computer-on-a-chip implementation

inM
writeM
instruction

(ROM32K)

outM
CPU

Instruction
Memory

addressM
pc

reset

Data
Memory
(Memory)

CHIP
CHIP Computer
Computer {{
IN
IN reset;
reset;
PARTS:
PARTS:
//
// implementation
implementation missing
missing
}}

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 24

The Big Picture

Instruction memory
Memory:

Data memory

Screen

Keyboard

CPU
Computer

Ya, right,
but what about
the software?

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 25

How it actually looks (thank goodness for abstractions!)

Extension
slots / ports

RAM

CPU

bus

I/O board
(graphics card)

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 26

Perspective
I/O: more units, processors
Special-purpose processors (graphics, communications, )
Efficiency
CISC / RISC (HW/SW trade-off)
Diversity: desktop, laptop, hand-held, game machines,
General-purpose VS dedicated / embedded computers
Silicon compilers
And more ...

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.idc.ac.il/tecs , Chapter 5: Computer Architecture

slide 27