Lecture 35:
Parallel Computing
CMPS 221 – Computer Organization and Design
Adapted by Izzat El Hajj from textbook slides for Computer Organization and Design, by David Patterson and John Hennessy, Morgan Kaufmann.
Recall: Processor Trends
108
Transistors
107 (thousands)
106
105
104 Frequency
103 (MHz)
Typical Power
102 (Watts)
101
100
1970 1980 1990 2000 2010 2020
Source: M. Horowitz, F. Labonte, O. Shacham, K. Olukotun, L. Hammond, C. Batten (1970-2010 ). K. Rupp (2010-2017).
Processor Trends
108
Transistors
107 (thousands)
106
Single-thread
105 Performance
(SpecINT x 103)
104 Frequency
103 (MHz)
Typical Power
102 (Watts)
101
100
1970 1980 1990 2000 2010 2020
Source: M. Horowitz, F. Labonte, O. Shacham, K. Olukotun, L. Hammond, C. Batten (1970-2010 ). K. Rupp (2010-2017).
Stagnation in frequency led to a stagnation in single-thread performance,
except for some improvements due to architecture and compiler advancements
Processor Trends
108
Transistors
107 (thousands)
106
Single-thread
105 Performance
(SpecINT x 103)
104 Frequency
103 (MHz)
Typical Power
102 (Watts)
Number of
101
Logical Cores
100
1970 1980 1990 2000 2010 2020
Source: M. Horowitz, F. Labonte, O. Shacham, K. Olukotun, L. Hammond, C. Batten (1970-2010 ). K. Rupp (2010-2017).
Stagnation in single-thread performance made parallel computing
mainstream as transistors were invested in adding more cores to processors
Multi-core Processors
Core 0 Core 1 Core 2 Core 3
L1 I- L1 D- L1 I- L1 D- L1 I- L1 D- L1 I- L1 D-
cache cache cache cache cache cache cache cache
L2 cache L2 cache L2 cache L2 cache
L3 cache
Real Stuff: Core i7
§6.4 Hardware Multithreading
Recall: Pipeline Stalls
◼ Pipelines stall due to hazards
◼ Exacerbated when pipelines ae made
deeper and wider
◼ How to fill those stalls with useful work?
◼ Execute instructions from other threads on
the same core
Chapter 6 — Parallel Processors from Client to Cloud — 7
Multithreading
◼ Multithreading: executing multiple threads on
the same core
◼ Replicate registers, PC, etc.
◼ Share functional units
◼ Fine-grain multithreading
◼ Switch threads after each cycle
◼ If one thread stalls, others are executed
◼ Coarse-grain multithreading
◼ Only switch on long stalls (e.g., L2-cache miss)
◼ Simplifies hardware, but doesn’t hide short stalls
(e.g., data hazards)
Chapter 6 — Parallel Processors from Client to Cloud — 8
Multithreading Example
Chapter 6 — Parallel Processors from Client to Cloud — 9
Multithreading Example
Still have empty
issue slots
Chapter 6 — Parallel Processors from Client to Cloud — 10
Simultaneous Multithreading
◼ Simultaneous multithreading (SMT)
◼ Schedule instructions from multiple threads
simultaneously
◼ In a multiple-issue dynamically scheduled
processor (i.e., superscalar)
◼ Typically: two threads per core on a
modern CPU
Chapter 6 — Parallel Processors from Client to Cloud — 11
SMT Example
Chapter 6 — Parallel Processors from Client to Cloud — 12
Multi-core Processor with SMT
Four cores
execute
eight threads
(two each)
Core 0 Core 1 Core 2 Core 3
L1 I- L1 D- L1 I- L1 D- L1 I- L1 D- L1 I- L1 D-
cache cache cache cache cache cache cache cache
L2 cache L2 cache L2 cache L2 cache
L3 cache
§6.3 SISD, MIMD, SIMD, SPMD, and Vector
Instruction and Data Streams
◼ Flynn’s taxonomy
Data Streams
Single Multiple
Single
Instruction
Streams
Multiple
Chapter 6 — Parallel Processors from Client to Cloud — 14
Instruction and Data Streams
◼ Flynn’s taxonomy
Data Streams
Single Multiple
SISD:
Single Sequential
processor
Instruction
Streams
MIMD:
Multiple Multi-core
processor
Chapter 6 — Parallel Processors from Client to Cloud — 15
Instruction and Data Streams
◼ Flynn’s taxonomy
Data Streams
Single Multiple
SISD: SIMD:
Single Sequential Vector
processor processor
Instruction
Streams
MIMD:
Multiple Multi-core
processor
Chapter 6 — Parallel Processors from Client to Cloud — 16
Instruction and Data Streams
◼ Flynn’s taxonomy
Data Streams
Single Multiple
SISD: SIMD:
Single Sequential Vector
processor processor
Instruction
Streams
MISD: MIMD:
Multiple No examples Multi-core
today processor
Chapter 6 — Parallel Processors from Client to Cloud — 17
SIMD
◼ All units execute the same instruction at
the same time
◼ Each with a different data address
◼ Operate elementwise on vectors of data
◼ E.g., MMX and SSE instructions in x86
◼ Multiple data elements in 128-bit wide registers
◼ Reduced instruction control hardware
◼ Amortize the cost of instruction fetch and
decode over more actual computations
Chapter 6 — Parallel Processors from Client to Cloud — 18
§6.6 Introduction to Graphics Processing Units
Graphics Processing Units
◼ Graphics Processing Units (GPUs)
◼ Processors originally oriented at graphics tasks
◼ Vertex/pixel processing, shading, texture mapping,
rasterization
◼ Design focused on processing a large number of
pixels within a time constraint
◼ i.e., optimized for throughput
◼ Later evolved to more general purpose throughput-
oriented processors
Chapter 6 — Parallel Processors from Client to Cloud — 19
Recall: Which has better performance?
It depends on the performance metric we care about
Design Approaches
Latency-Oriented Design Throughput-Oriented Design
Minimize the time Maximize the number of
it takes to perform tasks that can be performed
a single task in a given time frame
Approaches to Processor Design
CPU: Latency-Oriented Design GPU: Throughput-Oriented Design
ALU ALU
Control
ALU ALU
Cache
• A few powerful ALUs • Many small ALUs
• Reduced operation latency • Long latency, high throughput
• Heavily pipelined for further throughput
• Large caches • Small caches
• Convert long latency memory accesses to • More area dedicated to computation
short latency cache accesses
• Sophisticated control • Simple control
• Branch prediction to reduce control hazards • More area dedicated to computation
• Data forwarding to reduce data hazards • SIMD execution to amortize cost of control
• Modest multithreading to hide short • Massive number of threads to hide the very
latency (e.g., two threads per core) high latency (e.g., 32 threads per core)
GPU Architecture
A GPU consists of multiple Streaming Multiprocessor (SMs), each
consisting of multiple cores with shared control and memory
(e.g., an NVIDIA Hopper H100 GPU has 132 SMs with 128 cores each which totals 16,896 cores)
SM SM SM SM
Control Control Control Control
Core Core Core Core Core Core Core Core
Core Core Core Core Core Core Core Core
…
Core Core Core Core Core Core Core Core
Core Core Core Core Core Core Core Core
Memory Memory Memory Memory
Global Memory
Parallel Vector Addition
Input Vector x:
Input Vector y:
Output Vector z:
To extract a massive number of threads:
assign one GPU thread per vector element
Parallel Vector Addition in CUDA
Input Vector x:
Input Vector y:
Output Vector z:
__global__ void vecadd_kernel(float* x, float* y, float* z, int N) {
int i = blockDim.x*blockIdx.x + threadIdx.x;
z[i] = x[i] + y[i];
Identify a thread’s global index
}
and use it to index the arrays
Textbook Sections
• The content in these slides corresponds to:
• Textbook:
• Computer Organization and Design, 5th Edition by David
Patterson and John Hennessy, Morgan Kaufmann, 2014.
• Sections:
• 6.1-6.6