Modern Computer

Architectures
Lecture-1:
Introduction
Ms. Nibedita Adhikari
Dept. of CSE, PIET, Rourkela

1
 Introduction
– Computer performance has been
increasing phenomenally over
the last five decades.
– Brought out by Moore’s Law:
●
Transistors per square inch roughly
double every eighteen months.
– Moore’s law is not exactly a law:
●
but has held good for nearly 50
years.
2
 Introduction
Cont…
●
If commercial aircrafts had similar
performance increase over the last
50 years, we should have:
– Commercial planes flying at 1000
times the supersonic speed.
– Aircrafts of the size of a chair.
– Costing couple of thousand rupees
only.

3
 Moore’s Law

Gordon Moore (co-founder of Intel)

predicted in 1965: “Transistor density
of minimum cost semiconductor chips
would double roughly every 18 Moore’s Law: it’s worked for
months.” a long time
Transistor density is correlated to
processing speed.
4
 Trends Related to Moore’s
Law
Cont…
• Processor performance:
• Twice as fast after every 2 years
(roughly).
• Memory capacity:
• Twice as much after every 18
months (roughly).

5
 Interpreting Moore’s
Law
●
Moore's law is not about just the density of
transistors on a chip that can be achieved:
– But about the density of transistors at which
the cost per transistor is the lowest.
●
As more transistors are made on a chip:
– The cost to make each transistor reduces.
– But the chance that the chip will not work due
to a defect rises.
●
Moore observed in 1965 there is a
transistor density or complexity:
– At which "a minimum cost" is achieved.
6
 How Did Performance
Improve?
●
Till 1980s, most of the performance
improvements came from using innovations in
manufacturing technologies:
– VLSI
– Reduction in feature size
●
Improvements due to innovations in
manufacturing technologies have slowed
down since 1980s:
– Smaller feature size gives rise to increased
resistance, capacitance, propagation delays.
– Larger power dissipation.
(Aside: What is the power consumption of Intel Pentium
Processor? Roughly 100 watts idle) 7
 Power Consumption in a
Processor
●
Power=Dynamic power + Leakage power
●
Dynamic power = Number of transistors x
capacitance x voltage2 x frequency
●
Leakage power is rising and will soon match
dynamic power.
Pentium P-Pro P-II P-III
P-4
Year 1993 95 97 99
2000
Transistors 3.1M 5.5M 7.5M
9.5M 42M
Clock Speed 60M 200M 300M 500M 8
1.5G
 Current Chip Manufacturing
Process
●
Most PC processors are currently
fabricated on a 65 nm process.
●
Intel in January 2007 demonstrated a
working 45nm chip:
– Intel would begin mass-producing in late 2007.
– Compare: the diameter of an atom is of the
order of 0.1 nm.
●
A decade ago, chips were built using a 500
nm (0.5 micron) process.
●
In 1971, 10micron process was used.
9
 How Did Performance
Improve?
●
Since 1980s, most
Cont…
of the
performance improvements have
come from:
– Architectural and organizational
innovations
●
What is the difference between:
– Computerarchitecture and
computer organization?
10
 Architecture vs.
Organization
●
Architecture:
– Also known as Instruction Set Architecture
(ISA)
– Programmer visible part of a processor:
instruction set, registers, addressing modes,
etc.
●
Organization:
– High-level design: how many caches? how
many arithmetic and logic units? What type
of pipelining, control design, etc.
– Sometimes known as micro-architecture
11
 Computer
Architecture
●
The structure of a computer that a
machine language programmer must
understand:
– To be able to write a correct program
for that machine.
●
A family of computers of the same
architecture should be able to run
the same program.
– Thus, the notion of architecture leads to
“binary compatibility.” 12
 Course Objectives
●
Modern processors such as Intel
Pentium, AMD Athlon, etc. use:
– Many architectural and organizational
innovations not covered in a first
course.
– Innovations in memory, bus, and
storage designs as well.
– Multiprocessors and clusters
●
In this light, objective of this course:
– Study the architectural and organizational
innovations used in modern computers. 13
 A Few Architectural and
Organizational Innovations
●
RISC (Reduced Instruction Set
Computers):
– Exploited instruction-level parallelism:
●
Initially through pipelining and later by
using multiple instruction issue
(superscalar)
– Use of on-chip caches
●
Dynamic instruction scheduling
●
Branch prediction
14
 Today’s Objectives
●
Study some preliminary
concepts:
– Amdahl’s law, performance
benchmarking, etc.
●
RISC versus CISC architectures.
●
Types of parallelism in
programs versus types of
parallel computers.
●
Basic concepts in pipelining. 15
 Amdahl’s Law
●
Quantifies overall performance
gain due to improve in a part of a
computation.
●
Amdahl’s Law:
– Performance improvement gained from using
some faster mode of execution is limited by the
amount of time the enhancement is actually
[Link] time for a task without enhancement
Speedup =
Execution time for the task using enhancement

16
 Computer System
Components
CPU

Caches
Processor-Memory Bus

Adapter
RAM Peripheral Buses

Controllers Controllers

I/O devices
Displays Networks

Keyboards
17
 Amdahl’s Law and
Speedup
●
Speedup tells us:
– How much faster a machine will run due
to an enhancement.
●
For using Amdahl’s law two things
should be considered:
– 1st… Fraction of the computation time in
the original machine that can use the
enhancement
●
If a program executes in 30 seconds and 15
seconds of exec. uses enhancement, fraction
=½
– 2nd… Improvement gained by
enhancement
●
If enhanced task takes 3.5 seconds and 18
original task took 7secs, we say the speedup
 Amdahl’s Law Equations
Fractionenhanced
Execution timenew =
Execution timeold x(1 – Fractionenhanced) +
Speedupenhanced

Execution Timeold 1
Speedupoverall = =
Execution Timenew Fractionenhanced
(1 – Fractionenhanced) +
Speedupenhanced
Use previous equation,
Solve for speedup

Don’t
Don’t just
just try
try to
to memorize
memorize
these
these equations
equations and
and plug
plug numbers
numbers into
into them.
them.
It’s
It’s always
always important
important to
to think
think about
about the
the problem
problem too!
too!
19
Modern Computer
Architectures
Lecture-2:
A Few Basic Concepts

20
 Performance
Measurements
●
Performance measurement is
important:
– Helps us to determine if one
processor (or computer) works
faster than another.
– A computer exhibits higher
performance if it executes
programs faster.
21
 Clock-Rate Based
Performance
Measurement
●
Comparing performance based on
clock rates is obviously
meaningless:
– Execution time=CPI × Clock cycle
time
– Please remember:
●
Higher CPI need not mean better
performance.
●
Also, a processor with a higher clock 22

rate may execute programs much

 Example: Calculating
Overall CPI (Cycles per
Instruction)
Operation Freq CPI(i) (% Time)
ALU 50% 1 (40%)
Load 20% 2 (27%)
Store 10% 2 (13%)
Branch 20% 5 (20%)

Typical Instruction Mix

Overall CPI= 1*0.4+ 2*0.27+ 2*0.13+5*0.2

= 2.2

23
 MIPS and MFLOPS
●
Used extensively 30 years back.
●
MIPS: millions of instructions processed
per second.
●
MFLOPS: Millions of FLoating point
OPerations completed per Second

Instruction Count Clock Rate

MIPS = =
Exec. Time x 10 6
CPI x 106

24
 Problems with MIPS
●
Three significant problems with
using MIPS:
●
So severe, made some one
term:
– “MeaninglessInformation about
Processing Speed”
●
Problem 1:
– MIPS is instruction set dependent.
25
 Problems with MIPS
cont…
●
Problem 2:
– MIPSvaries between programs
on the same computer.
●
Problem 3:
– MIPScan vary inversely to
performance!
●
Let’s look at an example as to
why MIPS doesn’t work…
26
 A MIPS Example
●
Consider the following computer:
Instruction counts (in millions) for each
instruction class
Code A (1 cycle) B (2 cycle) C (3 cycle)
type-
Compiler 5 1 1
1
The Compiler
machine runs at10100MHz. 1 1
Instruction 2
A requires 1 clock cycle, Instruction B requires 2
clock cycles, Instruction C requires 3 clock cycles.

CPU Clock Cycles

S n
i =1
CPIi x Ni
CPI = =
Instruction Count Instruction Count
27
 A MIPS Example
cont…
count cycles

[(5x1) + (1x2) + (1x3)] x 106

CPI1 = = 10/7 = 1.43
(5 + 1 + 1) x 106

100 MHz
MIPS1 = = 69.9
1.43

[(10x1) + (1x2) + (1x3)] x 106

CPI2 = = 15/12 = 1.25
(10 + 1 + 1) x 106

100 MHz So, compiler 2 has a higher

MIPS2 = = 80.0 MIPS rating and should be
1.25
faster?
28
 A MIPS Example
cont…

●
Now let’s compare CPU time:
Note Instruction Count x CPI
! important CPU Time =
formula!
Clock Rate

7 x 106 x 1.43
CPU Time1 = = 0.10 seconds
100 x 106

12 x 106 x 1.25
CPU Time2 = = 0.15 seconds
100 x 106

Therefore
Therefore program
program 11 is
is faster
faster despite
despite aa lower
lower MIPS!
MIPS!
29
 Toy Benchmarks
●
The performance of different
computers can be compared by
running some standard programs:
– Quick sort, Merge sort, etc.
●
But, the basic problem remains:
– Even if you select based on a toy
benchmark, the system may not
perform well in a specific application.
– What can be a solution then?

30
 Synthetic
Benchmarks
●
Basic Principle: Analyze the distribution of
instructions over a large number of
practical programs.
●
Synthesize a program that has the same
instruction distribution as a typical
program:
– Need not compute something meaningful.
●
Dhrystone, Khornerstone, Linpack are
some of the older synthetic benchmarks:
– More recent is SPEC..
31
 SPEC Benchmarks
●
SPEC: Standard Performance
Evaluation Corporation:
– A non-profit organization
([Link])
●
CPU-intensive benchmark for
evaluating processor performance of
workstation:
– Generations: SPEC89, SPEC92, SPEC95,
and SPEC2000 …
– Emphasizing memory system
performance in SPEC2000. 32
 Problems with
Benchmarks
●
SPEC89 benchmark included a small
kernel called matrix 300:
– Consists of 8 different 300*300 matrix
operations.
– Optimization of this inner-loop resulted
in performance improvement by a factor
of 9.
●
Optimizing performance can discard
25% Dhrystone code
●
Solution: Benchmark suite 33
 Other SPEC
Benchmarks
●
SPECviewperf: 3D graphics performance
– For applications such as CAD/CAM,
visualization, content creations, etc.
●
SPEC JVM98: performance of client-side
Java virtual machine.
●
SPEC JBB2000: Server-side Java
application
●
SPEC WEB2005: evaluating WWW servers
– Contains multiple workloads utilizing both
http and https, dynamic content
implemented in PHP and JSP. 34
 BAPCo
●
Non-profit consortium
[Link]
●
SYSmark 2004 SE
– Office productivity benchmark

35
 Instruction Set
Architecture (ISA)
●
Programmer visible part of a
processor:
– Instruction Set (what operations can be
performed?)
– Instruction Format (how are instructions
specified?)
– Registers (where are data located?)
– Addressing Modes (how is data accessed?)
– Exceptional Conditions (what happens if
something goes wrong?) 36
 ISA cont…

●
ISA is important:
– Not only from the programmer’s
perspective.
– From processor design and
implementation perspectives as
well.

37
 Evolution of Instruction
Sets
Single Accumulator
(Manchester Mark I,
IBM 700 series 1953)
Stack
(Burroughs, HP-3000 1960-70)

General Purpose Register Machines

Complex Instruction Sets RISC

(MIPS,IBM RS6000, . . .1987)
(Vax, Intel 386 1977-85)

38
 Different Types of ISAs
●
Determined by the means used for
storing data in CPU:
●
The major choices are:
– A stack, an accumulator, or a set of
registers.
●
Stack architecture:
– Operands are implicitly on top of the
stack.
39
 Different Types of ISAs
●
Accumulator architecture:
cont…
– One operand is in the accumulator
(register) and the others are
elsewhere.
– Essentially this is a 1 register
machine
– Found in older machines…
●
General purpose registers:
– Operandsare in registers or specific
memory locations. 40
 Comparison of
Architectures

Consider the operation: C =A + B

Stack Accumulator Register-Memory Register-Register

Push A Load A Load R1, A Load R1, A
Push B Add B Add R1, B Load R2, B
Add Store C Store C, R1 Add R3, R1, R2
Pop C Store C, R3

41
 Types of GPR Computers
●
Register-Register (0,3)
●
Register-Memory (1,2)
●
Register-Memory (2,2) (3,3)

42
Modern Computer
Architectures
Lecture-3:
Some More Basic
Concepts

43
Some More Architectural
Issues
●
Instruction length needs to be in
multiples of bytes.
●
Instruction encoding can be:
– Variable or Fixed
●
Variable encoding tries to use as few
bits to represent a program as possible:
– But at the cost of complexity of decoding.
●
Fixed Encoding: Alpha, ARM, MIPS
instructions:
Operation
Addr1 Addr2 Addr3
and Modes
44
 Flynn’s Classification
of Computers
●
SISD (Single Instruction Single Data):
– Uniprocessors.
●
MISD (Multiple Instruction Single
Data):
– No practical examples exist
●
SIMD (Single Instruction Multiple
Data):
– Specialized processors
●
MIMD (Multiple Instruction Multiple
Data):
– General purpose, commercially
important 45
 Basics of Parallel
Computing
●
If you are ploughing a field,
which of the following would
you rather use:
– One strong OX?
– A pair of cows?
– Two pairs of goats?
– 128 chicken?

46
 Basics of Parallel
Computing
cont…
●
Consider another scenario:
– You have get a color image printed on
a stack of papers.
●
Would you rather:
– For each sheet print red, then green,
and blue and then take up the next
paper? or
– As soon as you complete printing red
on a paper advance it to blue, in the
mean while take a new paper for 47

printing red?
 Classification for MIMD
Computers
●
Shared Memory:
– Processors communicate through a
shared memory.
– Typically processors connected to each
other and to the shared memory
through a bus.
●
Distributed Memory:
– Processors do not share any physical
memory.
– Processors connected to each other
through a network. 48
 Shared Memory
●
Shared memory located at a
centralized location:
– May consist of several
interleaved modules –-- same
distance (access time) from any
processor.
– Also called Uniform Memory
Access (UMA) model.
49
 Distributed Memory
●
Memory is distributed to each
processor:
– Improves scalability.
●
Non-Uniform Memory Access (NUMA)
– (a) Message passing architectures – No
processor can directly access another
processor’s memory.
– (b) Distributed Shared Memory (DSM)–
Memory is distributed, but the address
space is shared.
50
UMA vs. NUMA Computers

P1 P2 Pn P1 P2 Pn
Cache Cache Cache Cache Cache Cache
Bus
Main Main Main
Memory Memory Memory
Main
Memory

Network

(a) UMA Model (b) NUMA Model

51
 RISC/CISC Controversy
●
RISC: Reduced Instruction Set
Computer
●
CISC: Complex Instruction Set
Computer
●
Genesis of CISC architecture:
– Implementing commonly used instructions
in hardware can lead to significant
performance benefits.
– For example, use of a FP processor can
lead to performance improvements.
●
Genesis of RISC architecture:
52
– The rarely used instructions can be
 Features of A CISC
Processor
●
Rich instruction set:
– Some simple, some very complex
●
Complex addressing modes:
– Orthogonal addressing (Every possible
addressing mode for every instruction).
·
Many instructions take multiple cycles:
· Large variation in CPI
·
Instructions are of variable sizes
·
Small number of registers
·
Microcode control
·
No (or inefficient) pipelining 53
 Examples of CISC
Philosophy
●
One instruction could do the work of several
instructions.
– For example, a single instruction could load two
numbers to be added, add them, and then store the
result back to memory directly.
●
Many versions of the same instructions were
supported:
– Different versions did almost the same thing with
minor changes.
– For example, one version would read two numbers
from memory, and store the result in a register.
Another version would read one number from memory
and the other from a register and store the result to
memory. 54
 Features of a RISC
Processor
●
Small number of instructions
●
Small number of addressing modes
·
Large number of registers (>32)
·
Instructions execute in one or two clock
cycles
·
Uniformed length instructions and fixed
instruction format.
·
Register-Register Architecture:
· Separate memory instructions (load/store)
·
Separate instruction/data cache
·
Hardwired control
·
Pipelining (Why CISC are not pipelined?) 55
 CISC vs. RISC
Organizations

Microprogrammed
Control Unit Hardwared
Cache Control Unit

Microprogrammed
Control Memory Instruction Data
Cache Cache

Main Memory Main Memory

(a) CISC Organization (b) RISC Organization

56
 Why Does RISC Lead to
Improved Performance?
●
Increased GPRs (Also, Register
Windows)
– Lead to decreased data traffic to memory.
– Remember memory is the bottleneck.
●
Register-Register architecture leads to
more uniform instructions:
– Efficient pipelining becomes possible.
●
However, large instruction memory
traffic:
– Because of larger number of instructions
results. 57
 Why Does RISC Lead to
Improved
Performance? Cont…
●
RISC-Like instructions can be scheduled
to achieve efficiency:
– Either by compiler or
– By hardware (Dynamic instruction
scheduling).
●
Suppose we need to add 2 values and
store the results back to memory.
●
In CISC:
– It would be done using a single instruction.
●
In RISC:
– 4 instructions would be necessary. 58
Early RISC Processors
●
1987 Sun SPARC
●
1990 IBM RS 6000
●
1996 IBM/Motorola PowerPC

59
 Parallel Execution of
Programs
●
Parallel execution of a program can be
done in one or more of following
ways:
– Instruction-level (Fine grained):
individual instructions on any one thread
are executed parallely.
●
Parallel execution across a sequence of
instructions (block) -- could be a loop, a
conditional, or some other sequence of
stmts.
– Thread-level (Medium grained): different
threads of a process are executed
parallely. 60
– Process-level (Coarse grained): different
 Exploitation of Instruction-
Level Parallelism
●
ILP can be exploited by deploying
several available techniques:
– Temporal parallelism (Overlapped
execution):
●
Pipelining
– Spatial Parallelism:
●
Superscalar execution (Multiple instructions
that use multiple data MIMD)
●
Vector processing (single instruction
multiple data SIMD)
61
Modern Computer
Architectures
Lecture-4:
ILP Exploitation
Through Pipelining

62
 Original ILP
Apprehensions
●
Flynn’s Bottleneck (1970):
– Speedup due to ILP can at best be 2.
– Flynn’s study focused on ILP found in the
basic blocks of some common programs.
– Crossing basic block boundaries would
involve crossing control dependencies ---
Would require flushing the pipeline.
●
Flynn’s Bottleneck appears too
pessimistic in retrospective:
– Present ILP exploitation level is much
beyond Flynn’s bottleneck.
63
 Pipelining
●
Pipelining incorporates the
concept of overlapped
execution:
– Used in many everyday
applications without our notice.
●
Has proved to be a very
popular and successful way to
exploit ILP:
– Instruction pipes are being used 64
 A Pipeline Example
●
Consider two alternate ways in
which an engineering college can
work:
– Approach 1. Admit a batch of
students and next batch admitted only
after already admitted batch
completes (i.e. admit once every 4
years).
– Approach 2. Admit students every
year.
– In the second approach: 65
 Pipelining

First Year Second Year Third Year Fourth Year

First Year Second Year Third Year Fourth Year
First Year Second Year Third Year Fourth Year

66
 Pipelined Execution
Time

IFetch Dcd Exec Mem WB

IFetch Dcd Exec Mem WB

IFetch Dcd Exec Mem WB

IFetch Dcd Exec Mem WB

IFetch Dcd Exec Mem WB

Program Flow
IFetch Dcd Exec Mem WB

67
 Advantages of Pipelining
●
An n-stage pipeline:
– Can improve performance upto n
times.
●
Not much investment in hardware:
– No replication of hardware resources
necessary.
– The principle deployed is to keep the
units as busy as possible.
●
Transparent to the programmers:
– Easy to use 68
 Basic Pipelining
Terminologies
●
Pipeline cycle (or Processor cycle):
– The time required to move an
instruction one step further in the
pipeline.
– Not to be confused with clock cycle.
●
Synchronous pipeline:
– Pipeline cycle is constant (clock-driven).
●
Asynchronous pipeline:
– Time for moving from stage to stage
varies 69
– Handshaking communication between
 Pipeline Cycle
●
Pipeline cycle:
– Determined by the time required by the slowest
stage.
●
Pipeline designers try to balance the length (i.e.
the processing time) of each pipeline stage.
– For a perfectly balanced pipeline, the execution
time per instruction is t/n,
●
where t is the execution time per instruction on
nonpipelined machine and n is the number of pipe stages.
●
However, it is very difficult to make the
different pipeline stages perfectly balanced.
●
Besides, pipelining itself involves some
overhead.
70
– The pipeline overhead arises due to the latches used
 Synchronous
Pipeline
- Transfers between stages are
simultaneous.
- One task or operation enters the pipeline
per cycle.
L L L L L
Input Output
S1 S2 Sk

Clock
 m d

71
 Asynchronous Pipeline
- Transfers performed when individual stages are
ready.
- Handshaking protocol between processors.
Input Output

Ready S1 Ready S2 Ready Sk Ready

Ack Ack Ack Ack

- Different amounts of delay may be experienced at

different stages.
- Can display variable throughput rate.

72
A Few Pipeline Concepts

Si Si+1

 m d

Pipeline cycle : 

Latch delay : d
 = max {m } + d

Pipeline frequency : f
f=1/

73
 Ideal Pipeline
Speedup
●
k-stage pipeline processes n tasks in
k + (n-1) clock cycles:
– k cycles for the first task and n-1
cycles for the remaining n-1 tasks.
●
Total time to process n tasks
● Tk = [ k + (n-1)] 
●
For the non-pipelined processor
T1 = n k 

74
 Pipeline Speedup
Expression
●
Speedup=

T1 nk nk
Sk = = [ k + (n-1)] = k + (n-1)
Tk

●
Observe that the memory
bandwidth must increase by a
factor of Sk:
–
Otherwise, the processor would stall waiting for data to
75
arrive from memory.
 Pipelines: A Few Basic
Concepts
●
Historically, there are two different types of
pipelines:
– Instruction pipelines
– Arithmetic pipelines
●
Arithmetic pipelines (e.g. FP multiplication) are
not popular in general purpose computers:
– Need a continuous stream of arithmetic operations.
– E.g. Vector processors operating on an array.
●
On the other had instruction pipelines being
used in almost every modern processor.

76
 Pipelines: A Few Basic
Concepts
●
Pipeline increases instruction
throughput:
– But, does not decrease the execution
time of the individual instructions.
– In fact, slightly increases execution time
of each instruction due to pipeline
overheads.
●
Pipeline overhead arises due to a
combination of:
– Pipeline register delay 77
– Clock skew
 Pipelines: A Few Basic
Concepts
●
Pipeline register delay:
– Caused due to set up time
●
Clock skew:
– the maximum delay between clock
arrival at any two registers.
●
Once clock cycle is as small as the
pipeline overhead:
– No further pipelining would be useful.
– Very deep pipelines may not be useful.
78
 Pipeline Registers
●
Pipeline registers are essential part of pipelines:
– There are 4 groups of pipeline registers in 4 stage
pipeline.
●
Each group saves output from one stage and
passes it as input to the next stage:
– IF/ID
– ID/EX
– EX/MEM
– MEM/WB
●
This way, each time “something is computed”...
– Effective address, Immediate value, Register content,
etc.
– It is saved safely in the context of the instruction that
needs it. 79
 Pipeline Registers
IF/ID ID/EX EX/MEM MEM/WB

inst. 1 IF

inst. 2

inst. 3

80
 Pipeline Registers
IF/ID ID/EX EX/MEM MEM/WB

inst. 1 IF

inst. 2

inst. 3

81
 Pipeline Registers
IF/ID ID/EX EX/MEM MEM/WB

inst. 1 IF ID

inst. 2 IF

inst. 3

82
 Pipeline Registers
IF/ID ID/EX EX/MEM MEM/WB

inst. 1 IF ID

inst. 2 IF

inst. 3

83
 Pipeline Registers
IF/ID ID/EX EX/MEM MEM/WB

inst. 1 IF ID EX

inst. 2 IF ID

inst. 3 IF

84
 Pipeline Registers
IF/ID ID/EX EX/MEM MEM/WB

inst. 1 IF ID EX

inst. 2 IF ID

inst. 3 IF

85
 Pipeline Registers
IF/ID ID/EX EX/MEM MEM/WB

inst. 1 IF ID EX MEM

inst. 2 IF ID EX

inst. 3 IF ID

86
 Pipeline Registers
IF/ID ID/EX EX/MEM MEM/WB

inst. 1 IF ID EX MEM

inst. 2 IF ID EX

inst. 3 IF ID

87
 Pipeline Registers
IF/ID ID/EX EX/MEM MEM/WB

inst. 1 IF ID EX MEM WB

inst. 2 IF ID EX MEM ...

inst. 3 IF ID EX ...
●
Typically, we will not think too much about pipeline
registers and one just assumes that values are
passed “magically” down stages of the pipeline.
88
 Pipeline Register
Depiction

EX/MEM

MEM/WB
ALU
ID/EX
IF/ID

IM Reg DM Reg
instructions

MEM/WB
EX/MEM
ALU
ID/EX
IF/ID

IM Reg DM Reg

MEM/WB
EX/MEM
ALU
ID/EX
IF/ID
IM Reg DM Reg

EX/MEM
ID/EX

ALU
IF/ID
every stage reads IM Reg DM
input
and writes output to
89
the pipeline registers
 Why Pipelining RISC
Processors is Easy
●
Recall the main principles of RISC:
– All operands are in registers
– The only operations that affect memory are loads
and stores.
– Few instruction formats, fixed encoding (i.e., all
instructions are the same size)
●
Although pipelining could conceivably be
implemented for any architecture,
– It would be inefficient.
– Pentium has characteristics of RISC and CISC --- CISC
Instructions are internally converted to RISC-like
instructions.
90
 Drags on Pipeline
Performance
●
Things are actually not so
rosy, due to the following
factors:
– Difficultto balance the stages
– Pipeline overheads: latch delays
– Clock skew
– Hazards

91
 Exercise
●
Consider an unpipelined processor:
– Takes 4 cycles for ALU and other
operations
– 5 cycles for memory operations.
– Assume the relative frequencies:
●
ALU and other=60%,
●
memory operations=40%
– Cycle time =1ns
●
Compute speedup due to pipelining:
– Ignore effects of branching.
– Assume pipeline overhead = 0.2ns
92
 Solution
●
Average instruction execution time for
large number of instructions:
– unpipelined= 1ns * (60%*4+ 40%*5)
=4.4ns
– Pipelined=1.2ns
●
Speedup=4.4/1.2=3.7 times

93
 Pipeline Hazards
●
Hazards can result in incorrect
operations:
– Structural hazards: Two instructions
requiring the same hardware unit at
same time.
– Data hazards: Instruction depends on
result of a prior instruction that is still in
pipeline
●
Data dependency
– Control hazards: Caused by delay in
decisions about changes in control flow
(branches and jumps).
●
Control dependency 94
 Pipeline Interlock
●
Pipeline interlock:
– Resolving
of pipeline hazards
through hardware mechanisms.
●
Interlock hardware detects all
hazards:
– Stalls
appropriate stages of the
pipeline to resolve hazards.

95
 MIPS
●
MIPS architecture:
– First publicly known implementations of
RISC architectures
– Grew out of research at Stanford
University
●
MIPS computer system founded in
1984:
– R2000 introduced in 1986.
– Licensed the designs rather than selling
the design. 96
 Commercial Success of
MIPS
●
Popularly used as IP-cores (building-blocks)
for embedded processor designs.
– Both 32-bit and 64-bit basic cores are offered ---
the design is licensed as MIPS32 and MIPS64.
– MIPS cores have been commercially successful ---
used in many consumer and industrial
applications.
●
MIPS cores can be found in:
– Modern Cisco and Linksys routers, cable modems
and ADSL modems, smartcards, laser printer
engines, set-top boxes, robots, handheld
computers, Sony PlayStation 2 and Sony
PlayStation Portable.
●
In cell phone/PDA applications, the MIPS core
has been unable to displace the incumbent, 97
competing ARM core
 MIPS
cont…
●
MIPS: Microprocessor Without
Interlocked Pipeline Stages
●
Operates on 64bit data
●
32 64bit registers
●
2 128KB high speed cache
●
Constant 32bit instruction length
●
Initial MIPS processors achieved
1instr/cycle (CPI =1)
98
 MIPS
●
Registers R0 to R31: cont…
– Value of R0 is always 0
●
Small number of addressing modes:
– Only immediate and displacement modes
supported, besides register mode.
– Register indirect achieved by placing 0 in
displacement field.
●
Add R4, 0(R1) //[R4] <- [R4] + [[R1]]
– Absolute addressing achieved by using R0 as
the base register.
●
Add R1, 100(R0) //[ R1] <- [R1]+100
99
 MIPS
●
R0 is used to synthesize
popular instructions:
– E.g.,there is no Mov
instruction
– Add R3,R0,#3 // move 3 to R3
●
R0 helps in reducing the
number of instructions.
100
 MIPS
●
MIPS memory:
– Byteaddressable with 64-bit
address.
●
MIPS provides 4 broad classes
of instructions:
– Load/Store
– ALU operations
– Branches and jumps
– Floating point operations
101
 MIPS Pipeline
●
Uses a 5-stage pipeline
●
IF: Instruction fetch
●
ID: Decode operands and fetch
register operands
●
ALU: ALU operation or data
operand address generation
●
MEM: Data memory reference
●
WB: Write back into register file
102
 MIPS Pipelining
Stages
●
5 stages of MIPS Pipeline:
– IF Stage:
●
Needs access to the Memory to load the instruction.
●
Needs a adder to update the PC.
– ID Stage:
●
Needs access to the Register File in reading operand.
●
Needs an adder (to compute the potential branch
target).
– EX Stage:
●
Needs an ALU.
– MEM Stage:
●
Needs access to the Memory.
– WB Stage:
●
Needs access to the Register File in writing. 103
 More Complete Picture
of a Pipeline
Fetch Decode Execute Memory Writeback

Instruc
Cache Funit Dunit EXunit Memuni WBunit
t

Register File

Data
Cache

104
 Details of Pipeline Stages:
MIPS R2000
Stage Phase Function performed
name
1. IF 1 Translate virtual instr. addr. using TLB
2 Access I-cache using physical address
2. RD 1 Decode Instruction
2 Read reg. file; if a branch, generate target
addr.
3. ALU 1 Start ALU op.; if a branch, check br. Condition
2 Finish ALU op; if load/store, Add base Reg and
offset form Effective addr, translate virtual
addr.
4. MEM 1 Access D-cache
2 Return data from D-cache, check tags & parity
5. WB 1 Write register file for both mem and other
instrs. 105
2 ---
 Extending MIPS to Handle
FP Operations
●
It is impractical to expect:
– all MIPS FP operations complete in 1 or 2
cycles.
●
FP should have the same pipeline stages
as integer instructions:
– EX cycles may be repeated many times to
complete an operation.
– There may be multiple functional units.
Ex int

IF ID FP Me W
Mul m B
FP 106

Add
 Further MIPS
Enhancements
cont…
●
MIPS could achieve CPI of 1, to improve
performance further, two possibilities:
– Superscalar
– Superpipelined
●
Superscalar:
– Replicate each pipeline stage so that two
or more instructions can proceed
simultaneously.
●
Superpipeline:
– Split pipeline stages into further stages.
107
Superscalar Processing
Stages
S4
S1 S2 S3 u v S5 S6
1 I-1
2 I-2 I-1
3 I-3 I-2 I-1
Cycles

4 I-4 I-3 I-2 I-1

5 I-4 I-3 I-1 I-2
6 I-4 I-3 I-2 I-1
7 I-3 I-4 I-2 I-1
8 I-4 I-3 I-2
9 I-4 I-3
10 I-4

108
 Summary
●
RISC architecture style saves chip
area that is used to support more
registers and cache:
– Also instruction pipelining is facilitated
due to small and uniform sized
instructions.
●
Three main types of parallelism in a
program:
– Instruction-level
– Thread-level
– Process-level
109
 Summary
Cont…
●
Two main types of parallel computers:
– SIMD
– MIMD
●
Instruction pipelines are found in almost
all modern processors:
– Exploits instruction-level parallelism
– Transparent to the programmers
●
Hazards can slowdown a pipeline:
– In the next lecture, we shall examine hazards
in more detail and available ways to resolve
hazards. 110
 References
[1]J.L. Hennessy & D.A. Patterson,
“Computer Architecture: A Quantitative
Approach”. Morgan Kaufmann
Publishers, 3rd Edition, 2003
[2]John Paul Shen and Mikko Lipasti,
“Modern Processor Design,” Tata Mc-
Graw-Hill, 2005

111