Computer Architecture

Chapter 2
Computer Evolution and
Performance

Original Author:Adrian J Pullin Adapted by: Chi-Cheng Lin,

Winona State University
Topics
• History of Computers

• Designing for Performance

• Performance Measurement

2
History of Computers (1)
• Pre-mechanical Era
—Abacus (ancient China)
• Mechanical Era (1623 – 1940s)
—Wilhelm Schickhard (1623)
– Automatically +, -, x, 
—Blaise Pascal (1642)
– Mass produced first working machine (50)
– Only +, -
—Gottfried Liebniz (1673)
– Improved on Pascal’s machine (+, -, x, )

3
History of Computers (2)
• Mechanical Era (cont’d)
—Charles Babbage (1822)
– Father of modern computer
– Automatic computation of math tables
– Any math operation
– Punch cards
– Modern structure: I/O, storage, ALU
– +: 1 sec. x: 1 min.
—George Boole (1847)
– Mathmatical analysis of logic

4
History of Computers (3)
• Mechanical Era (cont’d)
—Herman Hollerith (1889)
– Modern day punch card machine
– Tabulating machine company became
—Konard Zuse (1938)
– First working mechanical computer, Z1 IBM
– Binary machine
—Howard Aiken (1943)
– Harvard Mark I, built by IBM
– Implementation of Babbage’s machine

5
History of Computers (4)
• Summary of Mechanical Era
—Contributions
– Reduce calculation time
– Increase accuracy
—Drawback
– Speed: limited by moving parts
– Cumbersome
– Expensive
– Unreliable
• Entered the Electronic Era (1945 – present)!!

6
ENIAC - background
• Electronic Numerical Integrator And Computer
• Eckert and Mauchly
• University of Pennsylvania
• Trajectory tables for weapons
• Started 1943
• Finished 1946
—Too late for war effort (Quiz: When did WWII end?)
• Used until 1955

7
ENIAC – details (It’s BIG)
• Decimal (not binary)
• 20 accumulators of 10 digits
• Programmed manually by switches
• 18,000 vacuum tubes
• 70,000 resistors
• 10,000 capacitors
• 6,000 switches
• 30 tons
• 15,000 square feet
• 140 KW power consumption
• 5,000 additions per second 8
von Neumann/Turing
• Stored Program concept
• Main memory storing programs and data
• ALU operating on binary data
• Control unit interpreting instructions from
memory and executing
• Input and output equipment operated by control
unit
• Princeton Institute for Advanced Studies
—IAS
• Completed 1952: Basis for virtually every
machine designed since then

9
Structure of von Neumann machine

10
IAS - details
• 1000 x 40 bit words
—Binary number
—2 x 20 bit instructions
• Set of registers (storage in CPU)
—Memory Buffer Register
—Memory Address Register
—Instruction Register
—Instruction Buffer Register
—Program Counter
—Accumulator
—Multiplier Quotient

11
IAS – von Neumann Architecture
• Features
—Data and instructions are stored in a single R/W
memory
—Memory contents are addressable by location,
regardless of the content
—Sequential execution

12
Structure of IAS –
detail

13
Commercial Computers
• 1947 - Eckert-Mauchly Computer Corporation
• UNIVAC I (Universal Automatic Computer)
• US Bureau of Census 1950 calculations
• Became part of Sperry-Rand Corporation
• Late 1950s - UNIVAC II
—Faster
—More memory

14
IBM
• Punched-card processing equipment
• 1953 - the 701
—IBM’s first stored program computer
—Scientific calculations
• 1955 - the 702
—Business applications
• Lead to 700/7000 series

15
Transistors
• Replaced vacuum tubes
• Smaller
• Cheaper
• Less heat dissipation
• Solid State device
• Made from Silicon (Sand)
• Invented 1947 at Bell Labs
• William Shockley et al.

16
Transistor Based Computers
• Second generation machines
• NCR & RCA produced small transistor machines
• IBM 7000
• DEC - 1957
—Produced PDP-1

• High level languages

• Floating point arithmetic

17
Microelectronics
• Literally - “small electronics”
• A computer is made up of gates, memory cells
and interconnections
• These can be manufactured on a semiconductor
• e.g. silicon wafer

18
Generations of Computer
• First generation: Vacuum tube - 1946-1957
• Second generation: Transistor - 1958-1964
• Third generation: Integrated circuits – 1965 –
1971
—Small scale integration - 1965 on
– Up to 100 devices on a chip
—Medium scale integration - to 1971
– 100-3,000 devices on a chip
—Semiconductor memory (1970)
—Microprocessor (1971)

19
Generations of Computer

• Fourth generation: Large scale integration (LSI)

- 1971-1977
—3,000 - 100,000 devices on a chip
—Intel 8080: first general-purpose microprocessor
(1974)
• Fifth generation: 1978 – present
—Very large scale integration (VLSI) - 1978 to date
– 100,000 - 100,000,000 devices on a chip
—Ultra large scale integration (ULSI)
– Over 100,000,000 devices on a chip
—GSI ??
20
Moore’s Law
• Increased density of components on chip
• Gordon Moore - cofounder of Intel
• Number of transistors on a chip will double every year
• Since 1970’s development has slowed a little
— Number of transistors doubles every 18 months
• Cost of a chip has remained almost unchanged
• Higher packing density means shorter electrical paths,
giving higher performance
• Smaller size gives increased flexibility
• Reduced power and cooling requirements
• Fewer interconnections increases reliability

21
Growth in CPU Transistor Count

22
IBM 360 series
• 1964
• Replaced (& not compatible with) 7000 series
• First planned “family” of computers
—Similar or identical instruction sets
—Similar or identical O/S
—Increasing speed
—Increasing number of I/O ports (i.e. more terminals)
—Increased memory size
—Increased cost
• Multiplexed switch structure

23
DEC PDP-8
• 1964
• First minicomputer
• Did not need air conditioned room
• Small enough to sit on a lab bench
• $16,000
—$100k+ for IBM 360
• Embedded applications & OEM
• BUS STRUCTURE

24
DEC - PDP-8 Bus Structure

Main Memory I/O I/O

Console CPU Module Module
Controller

OMNIBUS

25
Semiconductor Memory
• 1970
• Fairchild
• Size of a single core
—i.e. 1 bit of magnetic core storage
• Holds 256 bits
• Non-destructive read
• Much faster than core
• Capacity approximately doubles each year

26
Intel
• 1971 - 4004
—First microprocessor
—All CPU components on a single chip
—4 bit
• Followed in 1972 by 8008
—8 bit
—Both designed for specific applications
• 1974 - 8080
—Intel’s first general purpose microprocessor

27
Designing for Performance (1)
• Support-Demand Cycle
Computer Performance

Demands Supports
(Motivates)
Application Requirement

28
Designing for Performance (2)
• Performance balance
—The rate at which performance is changing in the
various technology areas (processor, buses, memory,
peripherals) differs greatly from one type of elements
to another.
—New applications and new peripheral devices
constantly change the nature of the demand on the
system.

29
Speeding it up (Processor)
• Pipelining
• On board cache
• On board L1 & L2 cache
• Branch prediction
• Data flow analysis
• Speculative execution

30
Performance Mismatch
• Processor speed increased
• Memory capacity increased
• Memory speed lags behind processor speed

31
DRAM and Processor Characteristics

32
Solutions
• Increase number of bits retrieved at one time
—Make DRAM “wider” rather than “deeper”
• Change DRAM interface
—Cache
• Reduce frequency of memory access
—More complex cache and cache on chip
• Increase interconnection bandwidth
—High speed buses
—Hierarchy of buses

33
Pentium Evolution (1)
• 8080
— first general purpose microprocessor
— 8 bit data path
— Used in first personal computer – Altair
• 8086
— much more powerful
— 16 bit
— instruction cache, prefetch few instructions
— 8088 (8 bit external bus) used in first IBM PC
• 80286
— 16 Mbyte memory addressable
— up from 1Mb
• 80386
— 32 bit
— Support for multitasking
34
Pentium Evolution (2)
• 80486
—sophisticated powerful cache and instruction
pipelining
—built in maths co-processor
• Pentium
—Superscalar
—Multiple instructions executed in parallel
• Pentium Pro
—Increased superscalar organization
—Aggressive register renaming
—branch prediction
—data flow analysis
—speculative execution
35
Pentium Evolution (3)
• Pentium II
—MMX technology
—graphics, video & audio processing
• Pentium III
—Additional floating point instructions for 3D graphics
• Pentium 4
—Note Arabic rather than Roman numerals
—Further floating point and multimedia enhancements
• Itanium
—64 bit
—see chapter 15
• See Intel web pages for detailed information on
processors 36
Performance Measurement (1)
• Performance
—Execution time (latency):
– Time between the start and the completion of an event
– Performance  1/(Execution time)
—Throughput (bandwidth)
– Total amount of work done in a given time
• Machine X is n% faster than Machine Y:

n Execution timeY PerformanceX

1  
100 Execution timeX PerformanceY

37
Performance Measurement (2)
• Example:
Machine A runs a program in 10 seconds,
Machine B runs the same program in 15
seconds,
A is __% faster than B.

n Execution timeB 15 50
1    1
100 Execution timeA 10 100
 n  50
38
 Performance Measurement (3)
• Improve performance  Increase performance
• Improve execution time  Decrease execution time
• Question: Can we improve performance 10 times
faster by using a 10-time-faster machine?

39
 Amdahl’s Law (1)
• The performance improvement to be gained from
using some faster mode of execution is limited by
the fraction of the time the faster mode can be
used.
• It defines the speedup can be gained by using a
particular enhancement.

40
 Amdahl’s Law (2)
• Speedup
=
Performance for entire task using the enhancement
when possible
Performance for entire task w/o using the
enhancement
=
Execution time for entire task w/o using the
enhancement
Execution time for entire task using the
enhancement when possible

41
 Amdahl’s Law (3)
• Execution timenew
fE
= Execution timeold x ((1  fE )  )
sE
where fE: fraction of enhancement
sE: improvement gained by the
enhancement mode
Execution timeold 1

 Speedup =Execution timenew fE
(1  fE ) 
sE
42
 Amdahl’s Law (4)
• Example: An enhancement run 10 times faster
than the original machine, but it is usable 40% of
the time, then the speedup = __.

Sol:fE = 0.4
sE = 10
 Speedup= 1/((1-0.4) + 0.4/10)
= 1.56

43
 Amdahl’s Law (5)
• Extreme Cases
1
Speedup 
fE
(1  fE ) 
sE
—fE = 0  Speedup = 1
—fE = 1  Speedup = sE

44
CPU Performance (1)
• Most computers are constructed using a clock
running at a constant rate
—Distinct time events
 ticks  clock ticks  clocks
 cycles  clock periods  clock cycles
—Referred to by
Clock cycle time
length/time, e.g., 10 ns, or = 1/ clock rate
rate, e.g., 100 MHz
—ms = 10–3 sec, s = 10–6 sec, ns = 10–9 sec
—Hz = 1/sec, KHz = 103 Hz, MHz = 106 Hz, GHz = 109 Hz

45
CPU Performance (2)
• CPI = clock cycle per instruction
CPU clock cycles for a program

Instructio n Count
• CPU time for a program
= CPU clock cycles for a program x clock cycle time
CPU clock cycles for a program

clock rate
CPI  Instruction Count

clock rate

46
CPU Performance (3)
• CPI x Instruction Count x 1/(clock rate)
clock cycles instructio ns seconds
  
instructio n program clock cycle
= CPU time
seconds

program
• BUT, not every instruction takes the same number
of clock cycles to execute.  Take the average.

47
CPU Performance (4)
n
• CPI   (CPIi  fi ), where
i 1

n: number of different instructions in a program

CPIi: CPI of instruction i
fi: frequency of instruction i in a program
• Example:
Operations frequency clock cycle
ADD 60% 1
LOAD 40% 2
CPIoverall = _____

48
Improve CPU Performance (1)
• How do we improve CPU performance (i.e.,
reduce CPU time)?
• Again, CPU time
= CPI x Instruction Count x 1/(clock rate)
• So, we want to _____ CPI
_____ Instruction Count
_____ clock rate
_____ clock cycle time

49
Improve CPU Performance (2)
• Clock rate
—HW technology
—Organization
• CPI
—Organization
—Instruction set architecture
• Instruction Count
—Instruction set architecture
—Compiler technology

50
MIPS (1)
• MIPS: Million Instruction Per Second
• MIPS
Instruction Count 106

Execution time
Instruction Count 1
  6
Execution time 10
clock rate 1
  6
CPI 10

51
MIPS (2)
• Given MIPS,
Instruction Count
Execution time 
MIPS  106
 MIPS  Execution time 
Performance 

52
MIPS (3)
• Advantage:
—Easy to understand (especially by customers)
• Disadvantages
—Difficult to compare MIPS of computers with different
instruction sets
—MIPS varies between programs on the same computer
—MIPS can vary inversely to performance

53
Other Measurements
• MFLOPS:
Millions of floating point operations per second
• Cost

54
SPEC Speed Metric
• Single task
• Base runtime defined for each benchmark using
reference machine
• Results are reported as ratio of reference time to system
run time
— Trefi execution time for benchmark i on reference machine
— Tsuti execution time of benchmark i on test system

• Overall performance calculated by averaging

ratios for all 12 integer benchmarks
— Use geometric mean
– Appropriate for normalized numbers such as ratios
SPEC Rate Metric
• Measures throughput or rate of a machine carrying out a number of
tasks
• Multiple copies of benchmarks run simultaneously
— Typically, same as number of processors
• Ratio is calculated as follows:
— Trefi reference execution time for benchmark i
— N number of copies run simultaneously
— Tsuti elapsed time from start of execution of program on all N
processors until completion of all copies of program
— Again, a geometric mean is calculated
Amdahl’s Law
• Gene Amdahl [AMDA67]
• Potential speed up of program using multiple
processors
• Concluded that:
—Code needs to be parallelizable
—Speed up is bound, giving diminishing returns for
more processors
• Task dependent
—Servers gain by maintaining multiple connections on
multiple processors
—Databases can be split into parallel tasks
Amdahl’s Law Formula
• For program running on single processor
— Fraction f of code infinitely parallelizable with no
scheduling overhead
— Fraction (1-f) of code inherently serial
— T is total execution time for program on single
processor
— N is number of processors that fully exploit parralle
portions of code

• Conclusions
— f small, parallel processors has little effect
— N ->∞, speedup bound by 1/(1 – f)
– Diminishing returns for using more processors
Internet Resources
• http://www.intel.com/
—Search for the Intel Museum
• http://www.ibm.com
• http://www.dec.com
• Charles Babbage Institute
• PowerPC
• Intel Developer Home

59