COMPUTER ORGANIZATION AND DESIGN

5
Edition
th

The Hardware/Software Interface

Parallel Processing
Challenges
 §6.1 Introduction
Introduction

Parallel processing program

 Single program run on multiple processors

 Parallel processing challenges are explainable with

Amdahl's law
 Two important hurdles in parallel processing,
1) Limited parallelism
2) Long Latency to Remote Memory

Chapter 6 — Parallel Processors from Client to Cloud — 2

1. Limited Parallelism
The first major challenge in parallel processing arises with
the limited parallelism available in program.

 Limitation in available parallelism make it difficult to

achieve good speedups in any parallel processor
 Amdahl's Law
In computer architecture, Amdahl's law (or Amdahl's argument) is a formula which gives the theoretical
speedup in latency of the execution of a task at fixed workload that can be expected of a system whose
resources are improved.

Speedup due to enhancement E:

ExTime w/o E Performance w/E
Speedup(E) = =
ExTime w/ E Performance w/o E

Suppose that enhancement E accelerates a fraction F of the

task by a factor S, and the remainder of the task is unaffected,
then:
ExTime(E) =
Speedup(E) =
In computer programming, Amdahl's law is that, in a program with parallel processing , a relatively few
instruction s that have to be performed in sequence will have a limiting factor on program speedup such
that adding more processor s may not make the program run faster.

Performance CS510 Computer Architectures Lecture 3 - 4

 Amdahl’s Law
Complex instructions. eg. FP inst

FractionE
ExTimeE = ExTime x (1 - FractionE) +
SpeedupE
Execute complex
instructions parallely
by increasing the
speed up either by no.
of times faster or by
increasing the no. of
1 processors
ExTime
Speedup = =
ExTimeE (1 - FractionE) + FractionE
SpeedupE

1
=
(1 - F) + F/S
Performance CS510 Computer Architectures Lecture 3 - 5
 Amdahl’s Law
Floating point instructions are improved to run 2
times(100% improvement); but only 10% of
actual instructions are FP

1
Speedup =
(1-F) + F/S
1 1
= = = 1.053
(1-0.1) + 0.1/2 0.95
5.3% improvement

Performance CS510 Computer Architectures Lecture 3 - 6

Example
 Suppose we want to achieve a speedup of 80 with 100
processors. What is the fraction of original computation
that can be sequential?
1
Speedup =
(1-F) + F/S
1
80 =
(1-x) + x/100
1
(1-x) + x/100 =
80

x = 99.74

Sequential = 1 - 99.74
code
= 0.25 %
Amdahl’s Law
 Sequential part can limit speedup
 Example: 100 processors, 90× speedup?
 Tnew = Tparallelizable/100 + Tsequential
1
 Speedup= =90
(1−F parallelizable)+F parallelizable /100
 Solving: Fparallelizable = 0.999
 Need sequential part to be 0.1% of original
time

Chapter 6 — Parallel Processors from Client to Cloud — 9

Speed Up Challenge :
Increase in problem size
Scaling Example
 We have to perform two sums: one is a sum of
10 scalar variables and one is matrix sum of a
pair of 2-D arrays, with dimensions 10 by 10. Let
us assume only the matrix sum is parallelizable.
What speedup do we get with 10 versus 100
processors?
 Also calculate the speedups assuming the
matrices grow to 100 by 100.
Chapter 6 — Parallel Processors from Client to Cloud — 11
Scaling Example
 Solution:
Assumption: single addition can be performed in
time t.
 There are 10 additions that do not benefit from
parallel processors and 100( 10 X 10 ) additions
that do.
 ( Time required for a single processor to perform
all additions will be 110 X t. )

Chapter 6 — Parallel Processors from Client to Cloud — 12

Scaling Example
 Workload: sum of 10 scalars, and 10 × 10 matrix
sum
 Speed up from 10 to 100 processors
 Single processor: Exec Time = (10 + 100) × tadd
 10 processors : Exec Time


 ExecTime after improv = ExecTimeaffectedbyimprov + ExecTimeunaffected

Amount_of_improvent

 Time = 10 × tadd + 100/10 × tadd = 20 × tadd

 Speedup = 110 tadd/20 tadd = 5.5 (55% of potential)
( Exp :5.5/10 * 100 = 55%)

Chapter 6 — Parallel Processors from Client to Cloud — 13
Scaling Example
 100 processors : Exec time
 Time = 10 × tadd + 100/100 × tadd = 11 × tadd
 Speedup = 110/11 = 10 (10% of potential)
(Expl: 10/100 x 100 = 10 % )

 Assumes load can be balanced across

processors

Chapter 6 — Parallel Processors from Client to Cloud — 14

Scaling Example (cont)
 What if matrix size is 100 × 100?
 Single processor: Time = (10 + 10000) × tadd
 10 processors
 Time = 10 × tadd + 10000/10 × tadd = 1010 × tadd
 Speedup = 10010/1010 = 9.9 (99% of potential)
 100 processors
 Time = 10 × tadd + 10000/100 × tadd = 110 × tadd
 Speedup = 10010/110 = 91 (91% of potential)
 Assuming load balanced

Chapter 6 — Parallel Processors from Client to Cloud — 15

Strong vs Weak Scaling
 Strong scaling: problem size fixed
 As in example
 Weak scaling: problem size proportional to
number of processors
 10 processors, 10 × 10 matrix
 Time = 20 × tadd
 100 processors, 32 × 32 matrix
 Time = 10 × tadd + 1000/100 × tadd = 20 × tadd
 Constant performance in this example

Chapter 6 — Parallel Processors from Client to Cloud — 16

 §6.3 SISD, MIMD, SIMD, SPMD, and Vector
Instruction and Data Streams
 An alternate classification
Data Streams
Single Multiple
Instruction Single SISD: SIMD: SSE
Streams Intel Pentium 4 instructions of x86
Multiple MISD: MIMD:
No examples today Intel Xeon e5345

 SPMD: Single Program Multiple Data

 A parallel program on a MIMD computer
 Conditional code for different processors

Chapter 6 — Parallel Processors from Client to Cloud — 17

Example: DAXPY (Y = a × X + Y)
 Conventional MIPS code
l.d $f0,a($sp) ;load scalar a
addiu r4,$s0,#512 ;upper bound of what to load
loop: l.d $f2,0($s0) ;load x(i)
mul.d $f2,$f2,$f0 ;a × x(i)
l.d $f4,0($s1) ;load y(i)
add.d $f4,$f4,$f2 ;a × x(i) + y(i)
s.d $f4,0($s1) ;store into y(i)
addiu $s0,$s0,#8 ;increment index to x
addiu $s1,$s1,#8 ;increment index to y
subu $t0,r4,$s0 ;compute bound
bne $t0,$zero,loop ;check if done
 Vector MIPS code

l.d $f0,a($sp) ;load scalar a

lv $v1,0($s0) ;load vector x
mulvs.d $v2,$v1,$f0 ;vector-scalar multiply
lv $v3,0($s1) ;load vector y
addv.d $v4,$v2,$v3 ;add y to product
sv $v4,0($s1) ;store the result

Chapter 6 — Parallel Processors from Client to Cloud — 18

Vector Processors
 Highly pipelined function units
 Stream data from/to vector registers to units
 Data collected from memory into registers
 Results stored from registers to memory
 Example: Vector extension to MIPS
 32 × 64-element registers (64-bit elements)
 Vector instructions
 lv, sv: load/store vector
 addv.d: add vectors of double
 addvs.d: add scalar to each element of vector of double
 Significantly reduces instruction-fetch bandwidth

Chapter 6 — Parallel Processors from Client to Cloud — 19

Vector vs. Scalar
 Vector architectures and compilers
 Simplify data-parallel programming
 Explicit statement of absence of loop-carried
dependences
 Reduced checking in hardware
 Regular access patterns benefit from
interleaved and burst memory
 Avoid control hazards by avoiding loops
 More general than ad-hoc media
extensions (such as MMX, SSE)
 Better match with compiler technology
Chapter 6 — Parallel Processors from Client to Cloud — 20
Thank U
SIMD
 Operate elementwise on vectors of data
 E.g., MMX and SSE instructions in x86
 Multiple data elements in 128-bit wide registers
 All processors execute the same
instruction at the same time
 Each with different data address, etc.
 Simplifies synchronization
 Reduced instruction control hardware
 Works best for highly data-parallel
applications
Chapter 6 — Parallel Processors from Client to Cloud — 22
Vector vs. Multimedia Extensions
 Vector instructions have a variable vector width,
multimedia extensions have a fixed width
 Vector instructions support strided access,
multimedia extensions do not
 Vector units can be combination of pipelined and
arrayed functional units:

Chapter 6 — Parallel Processors from Client to Cloud — 23

 §6.4 Hardware Multithreading
Multithreading
 Performing multiple threads of execution in
parallel
 Replicate registers, PC, etc.
 Fast switching between threads
 Fine-grain multithreading
 Switch threads after each cycle
 Interleave instruction execution
 If one thread stalls, others are executed
 Coarse-grain multithreading
 Only switch on long stall (e.g., L2-cache miss)
 Simplifies hardware, but doesn’t hide short stalls
(eg, data hazards)

Chapter 6 — Parallel Processors from Client to Cloud — 24

Simultaneous Multithreading
 In multiple-issue dynamically scheduled
processor
 Schedule instructions from multiple threads
 Instructions from independent threads execute
when function units are available
 Within threads, dependencies handled by
scheduling and register renaming
 Example: Intel Pentium-4 HT
 Two threads: duplicated registers, shared
function units and caches

Chapter 6 — Parallel Processors from Client to Cloud — 25

Multithreading Example

Chapter 6 — Parallel Processors from Client to Cloud — 26

Future of Multithreading
 Will it survive? In what form?
 Power considerations  simplified
microarchitectures
 Simpler forms of multithreading
 Tolerating cache-miss latency
 Thread switch may be most effective
 Multiple simple cores might share
resources more effectively

Chapter 6 — Parallel Processors from Client to Cloud — 27

 §6.5 Multicore and Other Shared Memory Multiprocessors
Shared Memory
 SMP: shared memory multiprocessor
 Hardware provides single physical
address space for all processors
 Synchronize shared variables using locks
 Memory access time
 UMA (uniform) vs. NUMA (nonuniform)

Chapter 6 — Parallel Processors from Client to Cloud — 28

Example: Sum Reduction
 Sum 100,000 numbers on 100 processor UMA
 Each processor has ID: 0 ≤ Pn ≤ 99
 Partition 1000 numbers per processor
 Initial summation on each processor
sum[Pn] = 0;
for (i = 1000*Pn;
i < 1000*(Pn+1); i = i + 1)
sum[Pn] = sum[Pn] + A[i];
 Now need to add these partial sums
 Reduction: divide and conquer
 Half the processors add pairs, then quarter, …
 Need to synchronize between reduction steps

Chapter 6 — Parallel Processors from Client to Cloud — 29

Example: Sum Reduction

half = 100;
repeat
synch();
if (half%2 != 0 && Pn == 0)
sum[0] = sum[0] + sum[half-1];
/* Conditional sum needed when half is odd;
Processor0 gets missing element */
half = half/2; /* dividing line on who sums */
if (Pn < half) sum[Pn] = sum[Pn] + sum[Pn+half];
until (half == 1);

Chapter 6 — Parallel Processors from Client to Cloud — 30

 §6.6 Introduction to Graphics Processing Units
History of GPUs
 Early video cards
 Frame buffer memory with address generation for
video output
 3D graphics processing
 Originally high-end computers (e.g., SGI)
 Moore’s Law  lower cost, higher density
 3D graphics cards for PCs and game consoles
 Graphics Processing Units
 Processors oriented to 3D graphics tasks
 Vertex/pixel processing, shading, texture mapping,
rasterization

Chapter 6 — Parallel Processors from Client to Cloud — 31

Graphics in the System

Chapter 6 — Parallel Processors from Client to Cloud — 32

GPU Architectures
 Processing is highly data-parallel
 GPUs are highly multithreaded
 Use thread switching to hide memory latency
 Less reliance on multi-level caches
 Graphics memory is wide and high-bandwidth
 Trend toward general purpose GPUs
 Heterogeneous CPU/GPU systems
 CPU for sequential code, GPU for parallel code
 Programming languages/APIs
 DirectX, OpenGL (Open Graphics Library)
 C for Graphics (Cg), High Level Shader Language
(HLSL)
 Compute Unified Device Architecture (CUDA)

Chapter 6 — Parallel Processors from Client to Cloud — 33

Graphics Processing Units
Given the hardware invested to do graphics well, how can be
supplement it to improve performance of a wider range of
applications?

Basic idea:
Heterogeneous execution model

CPU is the host, GPU is the device

Develop a C-like programming language for GPU

NVIDIA: CUDA

AMD/ATI: Brook+
OpenCL (Open Computing Language)

Chapter 6 — Parallel Processors from Client to Cloud — 33

What is GPU Today ?
It is a processor optimized for 2D/3D graphics, video, visual
computing, and display.

It is highly parallel, highly multithreaded multiprocessor optimized

for visual computing.

It provide real-time visual interaction with computed objects via

graphics images, and video.

It serves as both a programmable graphics processor and a

scalable parallel computing platform.

Heterogeneous systems: combine a GPU with a CPU

It is called as Many-core

Chapter 6 — Parallel Processors from Client to Cloud — 33

CPU Vs. GPU
Different design philosophies
CPU
- A few out-of-order cores
- Sequential computation
GPU
- Many in-order cores
- Massively parallel computation

Chapter 6 — Parallel Processors from Client to Cloud — 33

 Example: NVIDIA Tesla
ROP : render output unit raster operations pipeline, is a hardware component in modern graphics processing
units (GPUs) [one of the Final steps) Streaming
multiprocessor

8 × Streaming
processors

Chapter 6 — Parallel Processors from Client to Cloud — 34

The TPC is a concept we find on NVIDIA GPUs. On G80 and GT200 architectures, a TPC, or
Texture / Processor Cluster, is a group made up of several SMs, a texture unit and some logic control.
The SM is a Streaming Multiprocessor and is made up to several SPs (or Streaming Processors),
several SFUs (or Special Function Unit – the unit used for transcendental functions such as sine or
cosine). A Streaming Processor is also called a CUDA core (in the new Fermi terminology).

The TPC of a G80 GPU has 2 SMs while the TPC of a GT200 has 3 SMs.

A SP includes several ALUs and FPUs. An ALU is an arithmetical and Logical Unit and a FPU is a
Floating Point Unit. The SP is the real processing element that acts on vertex or pixel data.

Several TPCs can be grouped in higher level entity called a Streaming Processor Array.

In OpenCL terminology, a SM is called a Compute Unit or CU.

But in NVIDIA’s new GPU, the GF100 / Fermi, the TPC is no longer valid: only remain the SMs.
We can also say that on Fermi architecture, a TPC = a SM.

In Fermi architecture, a SM is made up of two SIMD 16-way units. Each SIMD 16-way has 16 SPs
then a SM in Fermi has 32 SPs or 32 CUDA cores.
Graphics Processing Units
• A texture mapping unit (TMU) is a component in modern graphics
processing units (GPUs). Historically it was a separate physical processor.
• A TMU is able to rotate, resize, and distort a bitmap image (performing
texture sampling), to be placed onto an arbitrary plane of a given 3D
model as a texture.
• This process is called texture mapping.

• In modern graphics cards it is implemented as a discrete stage in a

graphics pipeline, whereas when first introduced it was implemented as a
separate processor, e.g. as seen on the Voodoo2 graphics card.

Chapter 6 — Parallel Processors from Client to Cloud — 33

CUDA(Compute Unified Device Architecture)
Both an architecture and programming model
Architecture and execution model
- Introduced in NVIDIA in 2007
- Get highest possible execution performance requires understanding
of hardware architecture
Programming model
- Small set of extensions to C
- Enables GPUs to execute programs written in C
- Within C programs, call SIMT “kernel” routines that are executed on
GPU.

Chapter 6 — Parallel Processors from Client to Cloud — 33

GPU CUDA Programming
Four important things

1. Offloading computation
2. Single Instruction Multiple Threads (SIMT):
- Streaming and massively-parallel multithreading
3. Work well with the memory
- Both between host memory and GPU memory
4. Make use of CUDA library

Chapter 6 — Parallel Processors from Client to Cloud — 33

 GPU Computing – Offloading Computation
The GPU is connected to the CPU by a reasonable fast bus (8 GB/s is

Terminology
- Host: The CPU and its memory (host memory)
- Device: The GPU and its memory (device memory)
Chapter 6 — Parallel Processors from Client to Cloud — 33
Streaming MultiProcessors
 Simple Processing Flow

PCI Bus

1. Copy input data from CPU memory to

GPU memory

48 48
 Simple Processing Flow

PCI Bus

1. Copy input data from CPU memory to

GPU memory
2. Load GPU program and execute,
caching data on chip for performance

49 49
 Simple Processing Flow

PCI Bus

1. Copy input data from CPU memory to

GPU memory
2. Load GPU program and execute,
caching data on chip for performance
3. Copy results from GPU memory to
CPU memory

50 50
A CUDA kernel is executed by an array of threads. All threads run the same code. Each thread has an ID that it uses to compute memory
addresses and make control decisions.

Offloading Computation
// DAXPY in CUDA
__global__
void daxpy(int n, double a, double *x, double *y) {
int i = blockIdx.x*blockDim.x + threadIdx.x; CUDA kernel
if (i < n) y[i] = a*x[i] + y[i];
}

int main(void) {
int n = 1024;
double a;
double *x, *y; /* host copy of x and y */
double *x_d; *y_d; /* device copy of x and y */
int size = n * sizeof(double)
// Alloc space for host copies and setup values
x = (double *)malloc(size); fill_doubles(x, n);
y = (double *)malloc(size); fill_doubles(y, n); serial code
// Alloc space for device copies
cudaMalloc((void **)&d_x, size);
cudaMalloc((void **)&d_y, size);

// Copy to device
cudaMemcpy(d_x, x, size, cudaMemcpyHostToDevice);
cudaMemcpy(d_y, y, size, cudaMemcpyHostToDevice);

// Invoke DAXPY with 256 threads per Block parallel exe on GPU
int nblocks = (n+ 255) / 256;
daxpy<<<nblocks, 256>>>(n, 2.0, x_d, y_d);

// Copy result back to host

cudaMemcpy(y, d_y, size, cudaMemcpyDeviceToHost);

// Cleanup serial code

free(x); free(y);
cudaFree(d_x); cudaFree(d_y);
return 0;
}

51 51
Streaming Processing
To be efficient, GPUs must have high throughput, i.e.
processing millions of pixels in a single frame, but may
be high latency

 “Latency is a time delay between the moment something

is initiated, and the moment one of its effects begins or
becomes detectable”
 For example, the time delay between a request for
texture reading and texture data returns
 Throughput is the amount of work done in a given
amount of time
 CPUs are low latency low throughput processors

 GPUs are high latency high throughput processors

52 52
 Parallelism in CPUs v. GPUs
 CPUs use task parallelism  GPUs use data parallelism
 Multiple tasks map to multiple  SIMD model (Single
threads Instruction Multiple Data) 
SIMT
 Tasks run different
instructions  Same instruction on different
data
 10s of relatively heavyweight
threads run on 10s of cores  10,000s of lightweight threads
on 100s of cores
 Each thread managed and
scheduled explicitly  Threads are managed and
scheduled by hardware
 Each thread has to be
individually programmed  Programming done for
(MPMD) batches of threads (e.g. one
pixel shader per group of
pixels, or draw call)

53 53
Streaming Processing to Enable Massive Parallelism

 Given a (typically large) set of data(“stream”)

 Run the same series of operations (“kernel” or
“shader”) on all of the data (SIMD)

 GPUs use various optimizations to improve

throughput:
 Some on chip memory and local caches to reduce
bandwidth to external memory
 Batch groups of threads to minimize incoherent
memory access
 Bad access patterns will lead to higher latency and/or
thread stalls.
 Eliminate unnecessary operations by exiting or
killing threads

54 54
Example: NVIDIA Tesla
 Streaming Processors
 Single-precision FP and integer units
 Each SP is fine-grained multithreaded
 Warp: group of 32 threads
 Executed in parallel,
SIMD style
 8 SPs
× 4 clock cycles
 Hardware contexts
for 24 warps
 Registers, PCs, …

Chapter 6 — Parallel Processors from Client to Cloud — 35

Classifying GPUs
 Don’t fit nicely into SIMD/MIMD model
 Conditional execution in a thread allows an
illusion of MIMD
 But with performance degredation
 Need to write general purpose code with care

Static: Discovered Dynamic: Discovered

at Compile Time at Runtime

Instruction-Level VLIW Superscalar

Parallelism

Data-Level SIMD or Vector Tesla Multiprocessor

Parallelism

Chapter 6 — Parallel Processors from Client to Cloud — 36

GPU Memory Structures

Chapter 6 — Parallel Processors from Client to Cloud — 37

Putting GPUs into Perspective
Feature Multicore with SIMD GPU
SIMD processors 4 to 8 8 to 16
SIMD lanes/processor 2 to 4 8 to 16
Multithreading hardware support for 2 to 4 16 to 32
SIMD threads
Typical ratio of single precision to 2:1 2:1
double-precision performance
Largest cache size 8 MB 0.75 MB
Size of memory address 64-bit 64-bit
Size of main memory 8 GB to 256 GB 4 GB to 6 GB
Memory protection at level of page Yes Yes
Demand paging Yes No
Integrated scalar processor/SIMD Yes No
processor
Cache coherent Yes No

Chapter 6 — Parallel Processors from Client to Cloud — 38

Guide to GPU Terms

Chapter 6 — Parallel Processors from Client to Cloud — 39

 §6.7 Clusters, WSC, and Other Message-Passing MPs
Message Passing
 Each processor has private physical
address space
 Hardware sends/receives messages
between processors

Chapter 6 — Parallel Processors from Client to Cloud — 40

Loosely Coupled Clusters
 Network of independent computers
 Each has private memory and OS
 Connected using I/O system
 E.g., Ethernet/switch, Internet
 Suitable for applications with independent tasks
 Web servers, databases, simulations, …
 High availability, scalable, affordable
 Problems
 Administration cost (prefer virtual machines)
 Low interconnect bandwidth
 c.f. processor/memory bandwidth on an SMP

Chapter 6 — Parallel Processors from Client to Cloud — 41

Sum Reduction (Again)
 Sum 100,000 on 100 processors
 First distribute 100 numbers to each
 The do partial sums
sum = 0;
for (i = 0; i<1000; i = i + 1)
sum = sum + AN[i];
 Reduction
 Half the processors send, other half receive
and add
 The quarter send, quarter receive and add, …
Chapter 6 — Parallel Processors from Client to Cloud — 42
Sum Reduction (Again)
 Given send() and receive() operations
limit = 100; half = 100;/* 100 processors */
repeat
half = (half+1)/2; /* send vs. receive
dividing line */
if (Pn >= half && Pn < limit)
send(Pn - half, sum);
if (Pn < (limit/2))
sum = sum + receive();
limit = half; /* upper limit of senders */
until (half == 1); /* exit with final sum */

 Send/receive also provide synchronization

 Assumes send/receive take similar time to addition

Chapter 6 — Parallel Processors from Client to Cloud — 43

Grid Computing
 Separate computers interconnected by
long-haul networks
 E.g., Internet connections
 Work units farmed out, results sent back
 Can make use of idle time on PCs
 E.g., SETI@home, World Community Grid

Chapter 6 — Parallel Processors from Client to Cloud — 44

 §6.8 Introduction to Multiprocessor Network Topologies
Interconnection Networks
 Network topologies
 Arrangements of processors, switches, and links

Bus Ring

N-cube (N = 3)
2D Mesh
Fully connected

Chapter 6 — Parallel Processors from Client to Cloud — 45

Multistage Networks

Chapter 6 — Parallel Processors from Client to Cloud — 46

Network Characteristics
 Performance
 Latency per message (unloaded network)
 Throughput
 Link bandwidth
 Total network bandwidth
 Bisection bandwidth
 Congestion delays (depending on traffic)
 Cost
 Power
 Routability in silicon

Chapter 6 — Parallel Processors from Client to Cloud — 47

 §6.10 Multiprocessor Benchmarks and Performance Models
Parallel Benchmarks
 Linpack: matrix linear algebra
 SPECrate: parallel run of SPEC CPU programs
 Job-level parallelism
 SPLASH: Stanford Parallel Applications for
Shared Memory
 Mix of kernels and applications, strong scaling
 NAS (NASA Advanced Supercomputing) suite
 computational fluid dynamics kernels
 PARSEC (Princeton Application Repository for
Shared Memory Computers) suite
 Multithreaded applications using Pthreads and
OpenMP
Chapter 6 — Parallel Processors from Client to Cloud — 48
Code or Applications?
 Traditional benchmarks
 Fixed code and data sets
 Parallel programming is evolving
 Should algorithms, programming languages,
and tools be part of the system?
 Compare systems, provided they implement a
given application
 E.g., Linpack, Berkeley Design Patterns
 Would foster innovation in approaches to
parallelism

Chapter 6 — Parallel Processors from Client to Cloud — 49

Modeling Performance
 Assume performance metric of interest is
achievable GFLOPs/sec
 Measured using computational kernels from
Berkeley Design Patterns
 Arithmetic intensity of a kernel
 FLOPs per byte of memory accessed
 For a given computer, determine
 Peak GFLOPS (from data sheet)
 Peak memory bytes/sec (using Stream
benchmark)

Chapter 6 — Parallel Processors from Client to Cloud — 50

Roofline Diagram

Attainable GPLOPs/sec
= Max ( Peak Memory BW × Arithmetic Intensity, Peak FP Performance )

Chapter 6 — Parallel Processors from Client to Cloud — 51

Comparing Systems
 Example: Opteron X2 vs. Opteron X4
 2-core vs. 4-core, 2× FP performance/core, 2.2GHz
vs. 2.3GHz
 Same memory system

 To get higher performance

on X4 than X2
 Need high arithmetic intensity
 Or working set must fit in X4’s
2MB L-3 cache

Chapter 6 — Parallel Processors from Client to Cloud — 52

Optimizing Performance
 Optimize FP performance
 Balance adds & multiplies
 Improve superscalar ILP
and use of SIMD
instructions
 Optimize memory usage
 Software prefetch
 Avoid load stalls
 Memory affinity
 Avoid non-local data
accesses

Chapter 6 — Parallel Processors from Client to Cloud — 53

Optimizing Performance
 Choice of optimization depends on
arithmetic intensity of code
 Arithmetic intensity is
not always fixed
 May scale with
problem size
 Caching reduces
memory accesses
 Increases arithmetic
intensity
Chapter 6 — Parallel Processors from Client to Cloud — 54
 §6.11 Real Stuff: Benchmarking and Rooflines i7 vs. Tesla
i7-960 vs. NVIDIA Tesla 280/480

Chapter 6 — Parallel Processors from Client to Cloud — 55

Rooflines

Chapter 6 — Parallel Processors from Client to Cloud — 56

Benchmarks

Chapter 6 — Parallel Processors from Client to Cloud — 57

Performance Summary
 GPU (480) has 4.4 X the memory bandwidth
 Benefits memory bound kernels
 GPU has 13.1 X the single precision throughout, 2.5 X
the double precision throughput
 Benefits FP compute bound kernels
 CPU cache prevents some kernels from becoming
memory bound when they otherwise would on GPU
 GPUs offer scatter-gather, which assists with kernels
with strided data
 Lack of synchronization and memory consistency support
on GPU limits performance for some kernels

Chapter 6 — Parallel Processors from Client to Cloud — 58

 §6.12 Going Faster: Multiple Processors and Matrix Multiply
Multi-threading DGEMM
 Use OpenMP:

void dgemm (int n, double* A, double* B, double* C)

{
#pragma omp parallel for
for ( int sj = 0; sj < n; sj += BLOCKSIZE )
for ( int si = 0; si < n; si += BLOCKSIZE )
for ( int sk = 0; sk < n; sk += BLOCKSIZE )
do_block(n, si, sj, sk, A, B, C);
}

Chapter 6 — Parallel Processors from Client to Cloud — 59

Multithreaded DGEMM

Chapter 6 — Parallel Processors from Client to Cloud — 60

Multithreaded DGEMM

Chapter 6 — Parallel Processors from Client to Cloud — 61

 §6.13 Fallacies and Pitfalls
Fallacies
 Amdahl’s Law doesn’t apply to parallel
computers
 Since we can achieve linear speedup
 But only on applications with weak scaling
 Peak performance tracks observed
performance
 Marketers like this approach!
 But compare Xeon with others in example
 Need to be aware of bottlenecks

Chapter 6 — Parallel Processors from Client to Cloud — 62

Pitfalls
 Not developing the software to take
account of a multiprocessor architecture
 Example: using a single lock for a shared
composite resource
 Serializes accesses, even if they could be done in
parallel
 Use finer-granularity locking

Chapter 6 — Parallel Processors from Client to Cloud — 63

 §6.14 Concluding Remarks
Concluding Remarks
 Goal: higher performance by using multiple
processors
 Difficulties
 Developing parallel software
 Devising appropriate architectures
 SaaS importance is growing and clusters are a
good match
 Performance per dollar and performance per
Joule drive both mobile and WSC

Chapter 6 — Parallel Processors from Client to Cloud — 64

Concluding Remarks (con’t)
 SIMD and vector
operations match
multimedia applications
and are easy to
program

Chapter 6 — Parallel Processors from Client to Cloud — 65