Transcript TI1400 Computer Organization at TU Delft

Basic Concepts
http://www.pds.ewi.tudelft.nl/~iosup/Courses/2011_ti1400_2.ppt
1
Making functions
nand gates
A
Y
ADD
B
A,B
Y

delay
time
2
TI1400/11-PDS
TU-Delft
Functional Units
• It would be very uneconomical to construct
separate combinatorial circuits for every
function needed
• Hence, functional units are parameterized
• A specific function is activated by a special
control string F
3
TI1400/11-PDS
TU-Delft
Arithmetic and Logic Unit
A
B
F
add
subtract
compare
or
f1 f 0
0
0
1
1
Y
F
0
1
0
1
F
A
B
F
F
Y
4
TI1400/11-PDS
TU-Delft
Repeated operations
• Y : = Y + Bi, i=1..n
• Repeated addition requires feedback
• Cannot be done without intermediate storage
of results
B
F
Y
F
5
TI1400/11-PDS
TU-Delft
Registers
B
Y
F
F
= storage element
6
TI1400/11-PDS
TU-Delft
Outline
1. Programmable Devices
2. A History of Computer Architectures
1.
2.
3.
4.
5.
Pre-History (to 1930s)
1st Generation: Electro-Mechanical (1930s-1950s)
2nd Generation: Transistors (1955—1975)
3rd Generation: Microprocessors (1960s—today)
4th Generation: Multi-Computing (1969—today)
7
TI1400/11-PDS
TU-Delft
Memory Organization
• In most computers bitstrings are grouped in
strings of 8 bit, called byte
• A word consists of a number of bytes
• Is dependent on the type of computer
8
TI1400/11-PDS
TU-Delft
Main memory
• Organized as a linear list of registers or
memory locations
• Each memory location has a separate
address, usually starting from 0 onwards
9
TI1400/11-PDS
TU-Delft
Memory Organization
• A main memory with a total number of bits can
be organized in various ways depending on:
- the size of the smallest addressable word
- the number of memory locations
• For example: memory contains 4096 bits
- 512 bytes of 8 bit
- 256 words of 16 bit
- 128 words of 32 bits
10
TI1400/11-PDS
TU-Delft
Question
Why is the memory size usually a power
of 2 ?
11
Programmable devices
• A program is a sequence of operations on a
stream of operands
• Operations are functions, like F
• Operands are data elements (e.g. numbers)
12
TI1400/11-PDS
TU-Delft
Programmable device
2,1
input stream
Programmable
Device
READ(X)
READ(Y)
ADD(X,Y,Z)
WRITE(Z)
3
output stream
program
• READ(X) means read next input value from input stream
and store it internally as variable X
• WRITE(X) means put value in variable X on output stream
• ADD(X,Y,Z) means assign value of X+Y to Z
13
TI1400/11-PDS
TU-Delft
Program sequencing
• We need a mechanism to execute a program
- FETCH operation that reads next instruction
- EXECUTE operation that performs specified
operation on operands
• And....repeat it forever:
forever loop
FETCH
EXECUTE
end loop
14
TI1400/11-PDS
TU-Delft
FETCH
Central Processing Unit
X: 1
Y: 2
Z: ??
•
•
TEMP_A:
TEMP_B:
RESULT:
arithmetic
unit
IR: ADD(X,Y,Z)
READ(X)
READ(Y)
ADD(X,Y,Z)
WRITE(Z)
PC:
Harvard Architecture
15
TI1400/11-PDS
TU-Delft
EXECUTE
Central Processing Unit
X: 1
Y: 2
Z: 3
•
•
TEMP_A: 1
TEMP_B: 2
RESULT: 3
arithmetic
unit
IR: ADD(X,Y,Z)
READ(X)
READ(Y)
ADD(X,Y,Z)
WRITE(Z)
PC:= PC+1
Harvard Architecture
16
TI1400/11-PDS
TU-Delft
Question
How can the previous scheme be
simplified ?
17
Von Neumann
“Conceptually we have [...] two different forms of
memory: storage of numbers and storage of
orders. If, however, the orders to the machine
are reduced to a numerical code and if the
machine can in some fashion distinguish a
number from an order, the memory organ can
be used to store both numbers and orders”
Burks, Goldstine, von Neumann “Preliminary
discussion of the logical design of an electronic
computing instrument”
18
TI1400/11-PDS
TU-Delft
Von Neumann Architecture
Memory
X: 1
Y: 2
Z: 3
•
•
READ(X)
READ(Y)
ADD(X,Y,Z)
WRITE(Z)
Central Processing Unit
TEMP_A:
TEMP_B:
RESULT:
IR:
arithmetic
unit
CONTROL
Input
Output
PC:
19
TI1400/11-PDS
TU-Delft
High Level Programming
• Simple program: P:= M*N
• Simplify program: P:= M+ .... + M (N times)
• Can be expressed as:
R:=0;
P:=0;
while R<N loop
P:=P+M;
R:=R+1;
end loop
20
TI1400/11-PDS
TU-Delft
Three levels of instructions
high level programming
language
program expressed in a
high-level language
translation
instruction set
program expressed as
a series of instructions
direct implementation
fetch/execute
implementation
program execution
in hardware
21
TI1400/11-PDS
TU-Delft
Operating system
service programs
keyboard
handler
storage
main store manager
processor
disks
keyboard
processor
scheduler
hardware
disk
handler
22
TI1400/11-PDS
TU-Delft
Virtual, Multi-layer Machine
operating system interface
service programs
programming language
language translator
instruction set
hardware
23
TI1400/11-PDS
TU-Delft
Outline
1. Programmable Devices
2. A History of Computer Architectures
1.
2.
3.
4.
5.
Pre-History (to 1930s)
1st Generation: Electro-Mechanical (1930s-1950s)
2nd Generation: Transistors (1955—1975)
3rd Generation: Microprocessors (1960s—today)
4th Generation: Multi-Computing (1969—today)
24
TI1400/11-PDS
TU-Delft
History
• Improving speed of operation by mechanical
means
- bicycle -> 5 times faster than walking (1 order of
magnitude)
- airplane -> 200 times faster than walking (2 o.m.)
• Multiplication of two 9 figure numbers
- by hand: 10 minutes
- by computer: 100 nanosec (10 o.m.)
• Predicting weather? (accurately)
25
TI1400/11-PDS
TU-Delft
Invention
• Computer is not a single invention
• Ideas from mathematics, physics, mechanical
and electrical engineering
• Development of calculation machines strated
in 17-th Century:
- Pascal: two (+,-) operation machine in 1642
- Leibnitz: four operation machine in 1671
26
TI1400/11-PDS
TU-Delft
Calculators
• Machines of Pascal and Leibnitz were
mechanical calculators
• Could do single operation at a time
• Lead to electronic calculators in 1975
27
TI1400/11-PDS
TU-Delft
Programmable devices
• Devices that could execute a program existed
in different areas:
• Mechanical Music Instruments
- Bagdad, 9-th Century
- Carillons
• Chess / Mechanical Turk (1770)?
• Punch Cards for weaving machines
- Jaquard (end 18-th Century)
28
TI1400/11-PDS
TU-Delft
The Jaquard Loom (actually, Head)
29
TI1400/11-PDS
TU-Delft
Difference Engine
• Invented by Johann Helfrich von Müller (1786)
• Used by Charles Babbage (1822)
30
TI1400/11-PDS
TU-Delft
Charles Babbage
•
•
•
•
Inspired by Jaquard mechanism
Designed “Analytical Engine” (1837)
Never completed
First machine with stored
program concept
(calculations+order
sequences)
31
TI1400/11-PDS
TU-Delft
Herman Hollerith
• Punch Cards for processing census data of
the 1890 census in US
• Great success
• Founded Tabulating Machine Company
(1889). Later became IBM.
32
TI1400/11-PDS
TU-Delft
Mathematical Influence
• George Boole (1854) showed that logic could
be reduced to a simple algebraic system
• Work remained a curiosity until rediscovered
by Whitehead and Russell in Principia
Mathematica (1910-1913)
• Then, formal logic developed resulting in
Gödel and the work of Alan Turing
33
TI1400/11-PDS
TU-Delft
Analog Computers
• Analog computers predated digital computers
- Slide rule
- Mechanical integrators used in differential
analyzers (Vannevar Bush, 1931)
• First systems that enabled significant
reduction of calculation times
34
TI1400/11-PDS
TU-Delft
Mechanical analog computer
35
TI1400/11-PDS
TU-Delft
Outline
1. Programmable Devices
2. A History of Computer Architectures
1. Pre-History (to 1930s)
2. 1st Generation: Electro-Mechanical (1930s1950s)
3. 2nd Generation: Transistors (1955—1975)
4. 3rd Generation: Microprocessors (1960s—today)
5. 4th Generation: Multi-Computing (1969—today)
36
TI1400/11-PDS
TU-Delft
Electro-Mechanical Devices
ASCC
• 1937-1944, Howard Aiken builds the Automatic
Sequence Controlled Calculator (ASCC), an electromechanical device
- First general-purpose digital computer
- 750,000 components, 5 tons
• Goal: 100 times faster than by hand
• Reality: 3-5 times faster
“Only six electronic digital
computers would be
required to satisfy the
computing needs of the
entire United States.”
37
TI1400/11-PDS
TU-Delft
Electro-Mechanical Devices
ENIAC
• 1943-1947, John Mauchly and John Presper Eckert
started building the Electronic Numerical Integrator
and Calculator (ENIAC).
- First all-electronic computer
- 18,000 tubes, 1,500 relays, 150 kilowatt dissipation
- Large office space
38
TI1400/11-PDS
TU-Delft
Electro-Mechanical Devices
Problems with ENIAC
•
•
•
•
•
•
Each time switched on: 10 tubes failed
Difficult to program
Not very flexible
Technologically too complex
Decentralized control
Too small a memory
39
TI1400/11-PDS
TU-Delft
Electro-Mechanical Devices
EDVAC
• Problems analyzed by John von Neumann
• Proposed new design: Electronic Discrete
Variable Automatic Computer (EDVAC)
• Basis so called Von Neumann Architecture
Memory
CPU
I
O
40
TI1400/11-PDS
TU-Delft
Harvard or von Neumann Architecture?
• Harvard Architecture
- Separate Instruction and Data memories (word size)
- Separate memory-CPU pathways
• Von Neumann Architecture
- Single Instruction and Data memory
- Separate memory-CPU pathways
• Answer: Modified Harvard Architecture (hybrid)
- Separate CPU (L1) caches for Instruction and Data
- Unified memory hierarchy outside L1
41
TI1400/11-PDS
TU-Delft
Outline
1. Programmable Devices
2. A History of Computer Architectures
1.
2.
3.
4.
5.
Pre-History (to 1930s)
1st Generation: Electro-Mechanical (1930s-1950s)
2nd Generation: Transistors (1955—1975)
3rd Generation: Microprocessors (1960s—today)
4th Generation: Multi-Computing (1969—today)
42
TI1400/11-PDS
TU-Delft
Transistors (1955—1975) and
Microprocessors (1960s—today)
• Transistors
- Reliable
- Less power
- Smaller
• Integrated Circuits
•
• U. Manchester (1953) •
•
• PDP-1
- 10 us / arith. instruction •
- Enabled small, low-cost
microprocessors
MOS Tech (ATARI)
Commodore PET
Apple & Apple ][
Current technology
43
TI1400/11-PDS
TU-Delft
Outline
1. Programmable Devices
2. A History of Computer Architectures
1.
2.
3.
4.
5.
Pre-History (to 1930s)
1st Generation: Electro-Mechanical (1930s-1950s)
2nd Generation: Transistors (1955—1975)
3rd Generation: Microprocessors (1960s—today)
4th Generation: Multi-Computing (1969—today)
44
TI1400/11-PDS
TU-Delft
The Internet: Early History
• 1965-1969 ARPANET
- Leonard Kleinrock develops
the Queueing Theory
(theoretical properties of the Internet)
- 4 computers at
UC Santa Barbara
UC Los Angeles
Stanford Research Inst.
U of Utah
Drawing
by Alex
McKenzie,
Dec 1969
• 1972 ARPANET public + Email
• 1974 TCP/IP at Stanford
• 1982 ARPANET + TCP/IP = the (early) Internet
45
TI1400/11-PDS
TU-Delft
The Internet Today
net, ca, us
com, org
mil, gov, edu
asia
de, uk, it, fr, pl
br, kr, nl
unknown
Source: http://www.opte.org/maps/
TI1400/11-PDS
46
TU-Delft
Internet-Based Applications
47
TI1400/11-PDS
TU-Delft
Research
ABILENE: Backbone Research Network
• Test: Land Speed Record
• ~ 7 Gb/s in single TCP
stream from Geneva to Caltech
48
TI1400/11-PDS
Source: MonALISA monitoring framework, 2005
TU-Delft
Research
Grid Computing
Just plug in the computing grid
and get your results
• The Grid = integration of computers as day-to-day
computing utility, similar to phone, water, and electricity
- Economy of scale: better service at lower cost
- Large-scale reality: operational overhead, functionality (robustness
+ manageability), real heterogeneity
• Primary users
- E-Science: high-energy physics, earth sciences, bioinformatics
- Industry: financial services, search engines (Google)
49
TI1400/11-PDS
TU-Delft
Research
Grids: Vision vs. Reality
• Many grids deployed, but not The Grid
• Cloud computing?
50
TI1400/11-PDS
TU-Delft