L 1 ParallelProcess Challenges

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
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

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

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.
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. )

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%)

Scaling Example
 100 processors : Exec time
 Speedup = 110/11 = 10 (10% of potential)
(Expl: 10/100 x 100 = 10 % )
 Assumes load can be balanced across

processors

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

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
 Constant performance in this example

§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

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

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

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
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
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:

§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)

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

Multithreading Example

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

§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)

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

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);

§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

Graphics in the System

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)

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)

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

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

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

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.

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.

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

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)
Streaming MultiProcessors
Simple Processing Flow
PCI Bus
1. Copy input data from CPU memory to

GPU memory
48 48
PCI Bus

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

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, …

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

GPU Memory Structures

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

Guide to GPU Terms

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

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

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, …
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

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

§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

Multistage Networks

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

§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
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

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)

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

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

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

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
§6.11 Real Stuff: Benchmarking and Rooflines i7 vs. Tesla
i7-960 vs. NVIDIA Tesla 280/480

Rooflines

Benchmarks

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

§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);
}

Multithreaded DGEMM

Multithreaded DGEMM

§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

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

§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

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

L 1 ParallelProcess Challenges

Uploaded by

Copyright:

Available Formats

L 1 ParallelProcess Challenges

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

L 1 ParallelProcess Challenges

Uploaded by

Copyright:

Available Formats

COMPUTER ORGANIZATION AND DESIGN

The Hardware/Software Interface

Parallel processing program

 Parallel processing challenges are explainable with

Chapter 6 — Parallel Processors from Client to Cloud — 2

 Limitation in available parallelism make it difficult to

Speedup due to enhancement E:

Suppose that enhancement E accelerates a fraction F of the

Performance CS510 Computer Architectures Lecture 3 - 4

Performance CS510 Computer Architectures Lecture 3 - 6

Chapter 6 — Parallel Processors from Client to Cloud — 9

Chapter 6 — Parallel Processors from Client to Cloud — 12

 ExecTime after improv = ExecTimeaffectedbyimprov + ExecTimeunaffected

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

 Assumes load can be balanced across

Chapter 6 — Parallel Processors from Client to Cloud — 14

Chapter 6 — Parallel Processors from Client to Cloud — 15

Chapter 6 — Parallel Processors from Client to Cloud — 16

 SPMD: Single Program Multiple Data

Chapter 6 — Parallel Processors from Client to Cloud — 17

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

Chapter 6 — Parallel Processors from Client to Cloud — 18

Chapter 6 — Parallel Processors from Client to Cloud — 19

Chapter 6 — Parallel Processors from Client to Cloud — 23

Chapter 6 — Parallel Processors from Client to Cloud — 24

Chapter 6 — Parallel Processors from Client to Cloud — 25

Chapter 6 — Parallel Processors from Client to Cloud — 26

Chapter 6 — Parallel Processors from Client to Cloud — 27

Chapter 6 — Parallel Processors from Client to Cloud — 28

Chapter 6 — Parallel Processors from Client to Cloud — 29

Chapter 6 — Parallel Processors from Client to Cloud — 30

Chapter 6 — Parallel Processors from Client to Cloud — 31

Chapter 6 — Parallel Processors from Client to Cloud — 32

Chapter 6 — Parallel Processors from Client to Cloud — 33

Develop a C-like programming language for GPU

Chapter 6 — Parallel Processors from Client to Cloud — 33

It is highly parallel, highly multithreaded multiprocessor optimized

It provide real-time visual interaction with computed objects via

It serves as both a programmable graphics processor and a

Heterogeneous systems: combine a GPU with a CPU

Chapter 6 — Parallel Processors from Client to Cloud — 33

Chapter 6 — Parallel Processors from Client to Cloud — 33

Chapter 6 — Parallel Processors from Client to Cloud — 34

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

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

Chapter 6 — Parallel Processors from Client to Cloud — 33

Chapter 6 — Parallel Processors from Client to Cloud — 33

Chapter 6 — Parallel Processors from Client to Cloud — 33

1. Copy input data from CPU memory to

1. Copy input data from CPU memory to

1. Copy input data from CPU memory to

// Copy result back to host

// Cleanup serial code

 “Latency is a time delay between the moment something

 GPUs are high latency high throughput processors

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

 GPUs use various optimizations to improve

Chapter 6 — Parallel Processors from Client to Cloud — 35

Static: Discovered Dynamic: Discovered

Instruction-Level VLIW Superscalar