John von Neumann
▶ Institute for Advanced Study, Princeton, USA
▶ Genius: significant impact in math, physics,
economics, statistics, computer science
▶ First written description of how an electronic
computer stores and processes information (1945)
▶ Inspired by Turing (maybe, maybe not)
▶ Architecture composed of:
1. Arithmetic logic unit and a control unit
2. Memory
1903-1957 3. Input/Output
▶ This design is still the basis of all computers and
most electronic devices today
1 / 36
Context: Turing Machines
Turing machines:
1,1,L
qb
0,1,L 0,1,L
1,1,R
start qa qc
0,1,R 0,1,L
qd
1,0,R 1,0,R
1,1,R
qe
0,1,R
von Neumann architecture:
2 / 36
Context: Modern Motherboard
3 / 36
Today’s Topics
Switches!
Vacuum Tubes
Transistors to Integrated Circuits
The Central Processing Unit (CPU)
The computing process
Moore’s Law
4 / 36
Why do computers operate in binary?
5 / 36
Why do computers operate in binary?
▶ Signal distinction is
otherwise difficult
▶ Digital representation of
numbers, logic, etc
▶ Circuits are consequences of
on/off switches
5 / 36
Representing numbers as sum-product of a base
Decimal (i.e., base 10) representation of a number, e.g. from R to L
1204 = 4 ∗ 100 + 0 ∗ 101 + 2 ∗ 102 + 1 ∗ 103
String s = sn−1 sn−2 . . . s1 s0 of n integers in base # symbols b:
n−1
X
to d(s, b) = si bi
i=0
▶ e.g., in 8-bits (binary base) for s = 10011011
1 · 20 + 1 · 21 + 0 · 22 + 1 · 23 + 1 · 24 + 0 · 25 + 0 · 26 + 1 · 27 = 155
6 / 36
Representing decimal numbers by turning wires off/on
7 / 36
Representing decimal numbers by turning wires off/on
Does a computer
actually add the
values?
7 / 36
Representing decimal numbers by turning wires off/on
Does a computer
actually add the
values?
No! Computers store and perform operations on representations of
numbers, so 10011011 is never actually converted to 155!
7 / 36
Using representations to perform binary addition
▶ Any computer operation is based on binary representation. Ex. to
perform the addition operation we need must solve the problem:
INPUT: equal length binary strings s1 and s2
OUTPUT: binary string s3 : to d(s3, 2) = to d(s1 , 2) + to d(s2 , 2)
8 / 36
Using representations to perform binary addition
▶ Any computer operation is based on binary representation. Ex. to
perform the addition operation we need must solve the problem:
INPUT: equal length binary strings s1 and s2
OUTPUT: binary string s3 : to d(s3, 2) = to d(s1 , 2) + to d(s2 , 2)
8 / 36
9 / 36
1-bit adder
Input A B Sum (XOR) Carry (AND)
0+0 0 0 0 0
0+1 0 1 1 0
1+0 1 0 1 0
1+1 1 1 0 1
10 / 36
2-bit adder
11 / 36
So, using an 8-bit adder...
But, if we have maximum 8-bit representation in our computer...what
happens?
12 / 36
So, using an 8-bit adder...
But, if we have maximum 8-bit representation in our computer...what
happens? Overflow!
12 / 36
Example 4-bit Arithmetic Logic Unit (ALU)
We can create circuits that use logic gates for multiple purposes:
13 / 36
The Computing Process
▶ tape = computer memory
▶ read/write = wires/circuits
▶ control unit = program
14 / 36
Switches
In order to physically create circuits to perform binary operations we
need some sort of switch that can be either on or off.
▶ Can be created using different materials/etc
▶ Can control information flow (i.e., by turning wires on/off)
▶ Synchronization/coordination of signals through circuits is a major
challenge!
Switches are grouped into logic gates, which are grouped into logic
blocks, and then into logic functions, and then into logic chips and
Central Processing Units (CPUs).
15 / 36
Vacuum tube-based computers
16 / 36
ENIAC and UNIVAC
ENIAC 1943-46 (Electronic Numerical Integrator And Computer):
▶ ≈18,000 vacuum tubes, 1800sq ft of floor space, 180,000 Watts
▶ punched cards served as the input and output
▶ decimal-based operations
▶ registers served as quick-access read/write storage
▶ had to be rewired for each program!
17 / 36
ENIAC and UNIVAC
UNIVAC 1951 (UNIVersal Automatic Computer):
▶ ENIAC+
▶ could be used for alphabetic and numerical programs, binary-based
▶ didn’t require rewiring!!! HOW????
17 / 36
Avoiding rewiring: CPU Instruction set
LOAD move number from RAM to CPU
STORE move number from CPU to RAM
ADD adds two numbers
COMPARE compares two numbers
JUMP skip to specified memory address
JUMPIF if condition true skip to memory address
..
.
CPUs have dozens to hundreds of CPU-dependent instructions
▶ “assembly language”
▶ each instruction has an associated binary value, e.g.,
LOAD ↔ 11101100
▶ every instruction has a circuit to perform the operation
18 / 36
Switches!
Vacuum Tubes
Transistors to Integrated Circuits
The Central Processing Unit (CPU)
The computing process
Moore’s Law
19 / 36
Transistor: an electronic switch
Dec 23, 1947: William Shockley, Walter Brattain, and John Bardeen
successfully test the point-contact transistor, setting off the
semiconductor revolution.
20 / 36
Integrated circuit/microchip
Kilby, 1958
Noyce, 1961
21 / 36
Intel
Intel 8080, 1974
Andy Grove, Bob Noyce, Gordon
Moore, 1978 (Intel 1968)
22 / 36
Modern CPUs
23 / 36
Modern CPUs
23 / 36
Modern CPUs
23 / 36
Cache
cache: a relatively small but very fast type of memory used to store
recently used information
▶ cpu first looks in cache, then RAM (next class)
▶ modern cpus typically have different levels of cache (smaller=faster)
▶ works because recently used info is typically more likely to be used
again soon (and so more likely to be in cache)
24 / 36
Today’s Topics
Switches!
Vacuum Tubes
Transistors to Integrated Circuits
The Central Processing Unit (CPU)
The computing process
Moore’s Law
25 / 36
Inside the CPU: parts
26 / 36
Inside the CPU: setting a register (single 8-bit pattern)
set/enable are “flags” (single bit) to show true/false
27 / 36
Inside the CPU: comparing two numbers
28 / 36
Inside the CPU: comparing two numbers
28 / 36
Inside the CPU: loading instructions/patterns
29 / 36
Inside the CPU: loading instructions/patterns
29 / 36
CPU Clock
Simulation: [Link]
Clock:
▶ “ticks” by turning on/off at fixed rate
▶ keeps everything in sync
▶ modern CPU measured in GHz (several billion times/second)
▶ 100MHz = 100 million cycles per second
▶ higher rate=less time between cycles → faster CPU
▶ BUT: not necc true for different CPUs (i.e., AMD vs Intel)
▶ CPU operation per clock tick is actually very simple
▶ allows CPU to do many complicated things very quickly
▶ all motherboard timings are wrt clock
30 / 36
CPU Clock
CPU synchronization:
▶ Each instruction requires a certain number of clock ticks to perform
▶ CPU has a lookup table that indicates how long each instruction
takes
▶ most cpus can handle multiple parallel operations (”cores” and
”threads”)
System clock:
▶ as CPUs became faster the wires on the MB started acting as
antennas
▶ signal would vanish as radio waves!
▶ special clock used to transfer between RAM and CPU
31 / 36
Today’s Topics
Switches!
Vacuum Tubes
Transistors to Integrated Circuits
The Central Processing Unit (CPU)
The computing process
Moore’s Law
32 / 36
Moore’s Law (Observation)
* modern desktop CPUs can have 10+ Billion transistors! 33 / 36
Moore’s Law (Observation)
* modern desktop CPUs can have 10+ Billion transistors!
33 / 36
GPU computing
GPU (Graphics Processing Unit)
▶ specially designed processor for graphics
34 / 36
GPU Computing
Key differences between CPU and GPU:
▶ CPU: few cores optimized for sequential tasks
▶ GPU: thousands of cores for many parallel tasks
▶ each core runs slower than CPU
▶ more transistors than a CPU (150-200 BILLION!)
▶ more power and cost efficient than a CPU
▶ can accelerate some applications 100’s of times over CPU
▶ has a very limited instruction set (cannot support a modern
operating system)
▶ terrific for math and simulation-based tasks (e.g. financial modeling,
scientific computing)
35 / 36
Other types of computing
Supercomputers:
▶ composed of a very large number of standard processors
▶ e.g., Conte
Distributed computing:
▶ sharing computers and computation over a network
▶ e.g., web servers, cloud
Embedded computers:
▶ dedicated function, often real-time computing
▶ e.g., phones, games, MRI, planes, weapons, refrigerators, ...
Each type trades off cost/power/size/speed/reliability/...
36 / 36