Computer Hardware Engineering

IS1200, spring 2015

Lecture 9: Parallelism, Concurrency, Speedup, and ILP

David Broman
Associate Professor, KTH Royal Institute of Technology
Assistant Research Engineer, University of California, Berkeley

Slides version 1.0

Course Structure

Module 1: Logic Design Module 4: I/O Systems

L L DCÖ1 DCÖ2 Lab:dicom L7 E6 E7 Lab: nios2io

E9 Lab: nios2int

Module 2: C and Assembly Module 5: Memory Hierarchy

Programming
L1 L2 E1 L8 E8 Home Lab: cache

L3 E2 E3 Lab: nios2time
L4 E4 Home lab: C

Module 3: Processor Design Module 6: Parallel Processors

and Programs
L5 L6 E5 L9 L10 E10

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 3

Abstractions in Computer Systems

Computer System Networked Systems and Systems of Systems

Application Software
Software
Operating System

Instruction Set Architecture Hardware/Software Interface

Microarchitecture

Logic and Building Blocks Digital Hardware Design

Digital Circuits

Analog Circuits
Analog Design and Physics
Devices and Physics

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

Agenda

Part I Part II
Multiprocessors, Parallelism, Instruction-Level Parallelism
Concurrency, and Speedup

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 5

Part I
Multiprocessors, Parallelism,
Concurrency, and Speedup

Acknowledgement: The structure and several of the good examples are derived from the book
“Computer Organization and Design” (2014) by David A. Patterson and John L. Hennessy

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

How is this computer revolution possible?

(Revisited)

Moore’s law:
•  Integrated circuit resources (transistors)
double every 18-24 months.

•  By Gordon E. Moore, Intel’s co-founder, 1960s.

•  Possible because refined manufacturing

process. E.g., 4th generation Intel Core i7
processors uses 22nm manufacturing.

•  Sometimes considered a self-fulfilling

prophecy. Served as a goal for the
semiconductor industry.

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 7

Have we reached the limit?

(Revisited)

During the last decade, the clock rate has

Why? increased dramatically.
•  1989: 80486, 25MHz
The Power Wall •  1993: Pentium, 66Mhz
•  1997: Pentium Pro, 200MHz
•  2001: Pentium 4, 2.0 GHz
•  2004: Pentium 4, 3.6 GHz

2013: Core i7, 3.1 GHz - 4 GHz

http://www.publicdomainpictures.net/view-image.php?
image=1281&picture=tegelvagg

Increased clock rate “New” trend since 2006: Multicore

implies increased power •  Moore’s law still holds
•  More processors on a chip: multicore
We cannot cool the system enough to •  “New” challenge: parallel programming
increase the clock rate anymore…

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

What is a multiprocessor?
A multiprocessor is a computer By contrast, a computer with one
system with two or more processors. processor is called a uniprocessor.

Multicore microprocessors are

multiprocessors where all processors (cores)
are located on a single integrated circuite
by Eric Gaba, CC BY-SA 3.0. No modifications made.

A cluster is a set of computers that are

connected over a local area network (LAN).
May be viewed as one large multiprocessor.

Photo by Robert Harker

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 9

Different Kinds of Computer Systems

(Revisited)

Photo by Kyro Photo by Robert Harker

Embedded Personal Computers and Warehouse

Real-Time Systems Personal Mobile Devices Scale Computers

Dependability Energy Performance

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

10

Why multiprocessors?

Possible to execute many

Performance computation tasks in parallel.

Replace energy inefficient

Multiprocessor
Energy processors in data centers with
many efficient smaller
processors.

If one out of N processors fails, still

Dependability N-1 processors are functioning.

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 11

Parallelism and Concurrency –

what is the difference?
Concurrency is about handling many things at the same time.
Concurrency may be viewed from the software viewpoint.

Software
Parallelism is about
Sequential Concurrent
doing (executing)
many things at the

Serial
Example: matrix Example: A Linux
same time. Parallelism multiplication on a OS running on a
may be viewed from
Hardware
unicore processor. unicore processor .
the hardware
viewpoint.
Parallel
Note: As always, everybody does Example: matrix Example: A Linux OS
not agree on the definitions of multiplication on a running on a multicore
concurrency and parallelism. The multicore processor. processor .
matrix is from H&P 2014 and the
informal definitions above are
similar to what was said in a talk
by Rob Pike.
Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

12

Speedup
Execution time of
How much can we improve the one program before
Tbefore improvement
performance using parallelization? Speedup =
Tafter Execution time after
improvement
Superlinear speedup. Either wrong,
Speedup or due to e.g. cache effects.
4
Linear speedup
3 (or ideal speedup)

Still increased speedup, but

2 less efficient
1
Danger: Relative speedup
measures only the same program
1 2 3 4 Number of True speedup compares also with
processors the best known sequential program,
Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 13

Amdahl’s Law (1/4)

Can we achieve linear speedup?
Time affected by the Time unaffected of
Divide execution time before improvement of improvement
improvement into two parts. parallelization (sequential part)

T = Taffected + Tunaffected

Execution time after

improvement Taffected
Tafter = + Tunaffected Amount of improvement
N (N times improvement)

Tbefore Tbefore
Speedup = = This is sometimes referred
Tafter Taffected to as Amdahl’s law
+ Tunaffected
N

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

14

Amdahl’s Law (2/4)

Tbefore Tbefore
Speedup = =
Tafter Taffected
+ Tunaffected
N

Exercise: Assume a program consists Solution:

of an image analysis task, sequentially 4 = 80 / (60 / N + 80 – 60)
followed by a statistical computation
task. Only the image analysis task can 60/N + 20 = 20
be parallelized. How much do we need
to improve the image analysis task to 60/N = 0
be able to achieve 4 times speedup?
It is impossible to achieve this
Assume that the program takes 80ms speedup!
in total and that the image analysis task
takes 60ms out of this time.
Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 15

Amdahl’s Law (3/4)

Tbefore Tbefore
Speedup = =
Tafter Taffected
+ Tunaffected
N
Assume that we perform 10 scalar
integer additions, followed by one matrix Solution A:
addition, where matrices are 10x10. (10+10*10) / (10*10/10 + 10) = 5.5
Assume additions take the same amount
of time and that we can only parallelize Solution B:
the matrix addition. (10+10*10) / (10*10/40 + 10) = 8.8
Exercise A: What is the speedup with
10 processors? Solution C:
Exercise B: What is the speedup with (10+10*10) / (10*10/N + 10) = 11 when
40 processors? N ! infinity
Exercise C: What is the maximal
speedup (the limit when N ! infinity)
Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

16

Amdahl’s Law (4/4)

Example continued. What if we change the size of the
problem (make the matrices larger)?

Number of processors
10 40 But was not the maximal
speedup 11.1 when N ! infinity?
10x10

Speedup Speedup
Size of matrices

5.5 8.8
Strong scaling = measuring
speedup while keeping the
problem size fixed.
Weak scaling = measuring
20x20

Speedup Speedup
8.2 20.5
speedup when the problem
size grows proportionally to
the increased number of
processors.
Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 17

Main Classes of Parallelisms

Example – Sheep shearing

Assume that sheep are data
Data-Level Parallelism (DLP) items and the task for the farmer
DLP Many data items can be is to do sheep shearing (remove
processed at the same time. the wool). Data-level parallelism
would be the same as using
several farm hands to do the
shearing.

Example – Many tasks at the farm

Task-Level Parallelism (TLP) Assume that there are many different
TLP Different tasks of work that can things that can be done on the farm
work in independently and in (fix the barn, sheep shearing, feed the
parallel pigs etc.) Task-level parallelism would
be to let the farm hands do the
different tasks in parallel.

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

18

SISD, SIMD, and MIMD

An old (from the 1960s) but still very useful classification of
processors uses the notion of instruction and data streams.
Data-level parallelism. Examples
Data Stream are multimedia extensions (e.g.,
SSE, streaming SIMD
Single Multiple extension), vector processors.
Single

SISD
Instruction Stream

SIMD Graphical Unit Processors

E.g. Intel (GPUs) are both SIMD and
E.g. SSE MIMD
Pentium 4 Instruction in x86
Task-level parallelism.
Examples are multicore and
MISD MIMD
Multiple

cluster computers
No examples today E.g. Intel Physical Q/A
Core i7 What is a modern Intel CPU,
such as Core i7? Stand for
MIMD, on the table for SIMD

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 19

Part II
Instruction-Level Parallelism

Acknowledgement: The structure and several of the good examples are derived from the book
“Computer Organization and Design” (2014) by David A. Patterson and John L. Hennessy

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

20

What is Instruction-Level Parallelism?

Instruction-Level Parallelism (ILP) may increase

performance without involvement of the programmer. It may
be implemented in a SISD, SIMD, and MIMD computer.

Two main approaches:

1. Deep pipelines with more pipeline stages
If the length of all pipeline stages are balanced, we may
increase performance by increasing the clock speed.

2. Multiple issue
A technique where multiple instructions are
issued in each in cycle.
ILP may decrease the CPI to lower than 1,
or using the inverse metric instructions per
clock cycle (IPC) increase it above 1.

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 21

Multiple Issue Approaches

Determining how many and which instructions to
issue in each cycle. Problematic since instructions
Issues with typically depend on each other.
Multiple
Issue
How to deal with data and control hazards

The two main approaches of multiple issue are

1. Static Multiple Issue
Decisions on when and which instructions to issue at
each clock cycle is determined by the compiler.

2. Dynamic Multiple Issue

Many of the decisions of issuing instructions are made
by the processor, dynamically, during execution.

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

22

Static Multiple Issue (1/3)

VLIW

Very Long Instruction Word (VLIW) An issue package may be

processors issue several instructions in each seen as one large instruction
cycle using issue packages. with multiple operations.

add $s0, $s1, $s2 F D E M W Each issue package has

two issue slots.
add $t0, $t0, $0 F D E M W

and $t2, $t1, $s0 F D E M W

lw $t0, 0($s0) F D E M W

The compiler may insert

no-ops to avoid hazards.
How is VLIW affecting the
hardware implementation?

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 23

Static Multiple Issue (2/3)

Changing the hardware
To issue two instructions in each cycle, we Fetch and Double the number Add another
need the following (not shown in picture): decode 64-bit of ports for the ALU
(two instructions) register file
CLK
CLK CLK CLK CLK CLK
CLK
WE3
0 3
A RD A1 WE
1 RD1 0
32

ALU
Instruction

PCnext A2 A RD 1
Memory

RD2 0 32

Memory
1

Data
A3

WD3
WD
32
20:16
0
15:11
+

1
4
<<2

+
Sign Extend
32

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

24

Static Multiple Issue (3/3) E

VLIW
Exercise: Assume we have a VLIW processor addi $s1, $0, 10
that can issue two instructions in the same clock L1: lw $t0, 0($s2)
cycle. For the following code, schedule the ori $t1, $t0, 7
instructions into issue slots and compute IPC. sw $t1, 0($s2)
Assume that no hazards occurs. addi $s2, $s2, 4
addi $s1, $s1, -1
Solution. IPC = (1 + 6*10) / (1 + 4*10) = 1.487… bne $s1, $0, L1
(max 2)
Slot 1 Slot 2 Cycle
Reschedule to
addi $s1, $0, 10 1
avoid stalls
because of lw L1 lw $t0, 0($s2) 2
addi $s2, $s2, 4 addi $s1, $s1, -1 3
ori $t1, $t0, 7 4
bne $s1, $0, L1 sw $t1, -4($s2) 5
Empty cells means no-ops

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 25

Dynamic Multiple-Issue Processors (1/2)

Superscalar Processors
In many modern processors (e.g., Intel Core i7), instruction issuing
is performed dynamically by the processor while executing the
program. Such processor is called superscalar. The first unit fetches
and decodes several
Instruction Fetch instruction in-order
and Decode unit
Reservation Stations (RS) buffer
operands to the FU before
execution. Data dependencies
RS RS RS RS
are handled dynamically.
Functional Units (FU) execute
the instruction. Examples are
FU FU FU FU integer units, floating point units,
and load/store units.
The commit unit commits instructions
Results are sent back to
Commit (stores in registers) concervatively,
RS (if a unit waits on the
Unit respecting the obervable order of
operand) and to the
instructions. Called in-order commit.
commit unit.
Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

26

Dynamic Multiple-Issue Processors (2/2)

Out-of-Order Execution, RAW, WAR
If the superscalar processor can reorder the instruction execution
order, it has an out-of-order execution processor

Example of a Read After Write (RAW)

dependency (dependency on $t0). The
lw $t0, 0($s2) superscalar pipeline must make sure that
the data is available before read.
addi $t1, $t0, 7
Example of a Write After Read (WAR)
dependency (dependency on $t1). If the
sub $t0, $t1, $s0 order is flipped due to out-of-order
addi $t1, $s0, 10 execution, we have a hazard.
WAR dependencies can be resolved using register
renaming, where the processor writes to a
nonarchitectural renaming register (here in the pseudo
asm code called $r1, not accessible to the programmer)
addi $r1, $s0, 10
sub $t0, $t1, $s0 Note that out-of-order processor is not rewriting the code, but
keeps track of the renamed registers during execution.

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 27

Some observations on Multi-Issue

Processors

VLIW processors tend to be more energy efficient

than superscalar out-of-order processors (less
hardware, the compiler does the job)
Multi-Issue
Processors
Superscalar processors with dynamic scheduling
can hide some latencies that are not statically
predictable (e.g., cache misses, dynamic branch
predictions).

Although modern processors issues 4 to 6

instructions per clock cycle, few applications results
in IPC over 2. The reason is dependencies.

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

28

Intel Microprocessors, some examples

Pipeline Issue Cores Power
Processor Year Clock Rate Stages Width
Intel 486 1989 25 MHz 5 1 1 5W
Intel Pentium 1993 66 MHz 5 2 1 10W
Intel Pentium Pro 1997 200 MHz 10 3 1 29 W
Intel Pentium 4 Willamette 2001 2000 MHz 22 3 1 75W
Intel Pentium 4 Prescott 2004 3600 MHz 31 3 1 103W
Intel Core 2006 2930 MHz 14 4 2 75W
Intel Core i5 Nehalem 2010 3300 MHz 14 4 1 87W
Intel Core i5 Ivy Bridge 2012 3400 MHz 14 4 8 77W

Pipeline stages first increased The power consumption

Clock rate increase stopped and then decreased, but the
(the power wall) around 2006 peaked with Pentium 4
number of cores increased
after 2006.
Source: Patterson and Hennessey, 2014, page 344.

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 29

Bonus Part
Time-Aware Systems Design
Research Challenges
David Broman @ KTH
(not part of the Examination in IS1200)

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

30

Time-Aware Systems - Examples

Cyber-Physical Systems (CPS)

Process Industry and Aircraft

Automotive
Industrial Automation

Time-Aware Simulation Systems Time-Aware Distributed Systems

Time-stamped
Physical simulations distributed systems
(Simulink, Modelica, etc.) (E.g. Google Spanner)

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 31

What is our goal?

“Everything should be made as simple as possible,

but not simpler“
attributed to Albert Einstein

Execution time should be as short as possible, but not shorter

Objective:
Minimize the slack Minimize area, memory,
No point in making the energy.
execution time shorter, as
long as the deadline is met. Challenge:
Still guarantee to meet
Deadline all timing constraints.

Task Slack

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

32

Programming Model and Time

Timing is not part of the software semantics

Correct execution of programs (e.g., in C, C++, C#, Java, Scala, Haskell,
OCaml) has nothing to do with how long time things takes to execute.
Traditional Approach

Programming
Model

Timing Dependent on the

Our Objective Hardware Platform

Programming
Model

Make time an abstraction within the Timing is independent of the hardware

programming model platform (within certain constraints)
Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism
 33

Are you interested to be challenged?

If you are interested in

•  Programming language design, or
•  Compilers, or
•  Computer Architecture

You are
•  ambitious and interested in learning new things
You want to
•  do a real research project as part of you Bachelor’s or Master’s
thesis project
Please send an email to dbro@kth.se, so that we can discuss
some ideas.

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism

34

Summary

Some key take away points:

•  Amdahl’s law can be used to estimate maximal

speedup when introducing parallelism in parts of a
program.

•  Instruction Level Parallelism (ILP) has been very

important for performance improvements over the years,
but improvements have not been as significant lately.

Reading for next lecture:

P&H Chapter 6 about parallel
Thanks for listening! processors and the cloud

Part I Part II
David Broman Multiprocessors, Parallelism, Instruction-Level
dbro@kth.se Concurrency, and Speedup Parallelism