Chapter Six (1/2)

Introduction
• Goal: connecting multiple computers to get higher performance
– Multiprocessors
– Scalability, availability, power efficiency
• Job-level (process-level) parallelism
– High throughput for independent jobs
• Parallel processing program
– Single program run on multiple processors
• Multicore microprocessors
– Chips with multiple processors (cores)

CE, KWU Prof. [Link] 2 / 33

Multiprocessor motivation
• Scientific applications
– Many scientific applications take too long to run on a single
processor machine
• Modeling of weather patterns, astrophysics, chemical reactions,
ocean currents, etc.
– Many of these are parallel applications which largely consist of
loops which operate on independent data
• Multiple users
– Many multi-user environments require more compute power than
available from a single processor machine
• Airline reservation system, department store chain inventory
system, file server for a large department, web server for a major
corporation, etc.
– These consist of largely parallel transactions which operate on
independent data
• Such applications can make efficient use of a multiprocessor
machine with each loop iteration running on a different processor
and operating on independent data
CE, KWU Prof. [Link] 3 / 33

Parallel Programming
• Parallel software is the problem
• Need to get significant performance improvement
– Otherwise, just use a faster uniprocessor, since it’s easier!
• Difficulties
– Partitioning
– Coordination
100 100
Synchronization
– Communications Data-remote Data-local
overhead Busy-overhead Busy-useful
75 75
Time (s)

Time (s)

50 50

25 25

0 0
P0 P1 P2 P3
(a) Sequential (b) Parallel with four processors

CE, KWU Prof. [Link] 4 / 33

Hardware and Software
• Hardware
– Serial: e.g., Pentium 4
– Parallel: e.g., quad-core Xeon e5345
• Software
– Sequential: e.g., matrix multiplication
– Concurrent: e.g., operating system
• Sequential/concurrent software can run on serial/parallel hardware
– Challenge: making effective use of parallel hardware

CE, KWU Prof. [Link] 5 / 33

Amdahl’s Law
• Sequential part can limit speedup
• Example: 100 processors, 90× speedup?

$
– $% & = + $( )* %+
'
1
= = 90
(1 − )+ /100

– Solving: = .

• Need sequential part to be 0.1% of original time

CE, KWU Prof. [Link] 6 / 33

Scaling Example
• Workload: sum of 10 scalars, and 10 × 10 matrix sum
– Assume the scalar sum is sequential
– Speed up from 10 to 100 processors
• Single processor: Time = (10 + 100) × tadd
• Assumes load can be balanced across processors

• 10 processors
– Time = 10 × tadd + 100/10 × tadd = 20 × tadd
– Speedup = 110/20 = 5.5 (5.5/10 = 55% of potential)

• 100 processors
– Time = 10 × tadd + 100/100 × tadd = 11 × tadd
– Speedup = 110/11 = 10 (10/100 = 10% of potential)

CE, KWU Prof. [Link] 7 / 33

Scaling Example (cont)

• What if matrix size is 100 × 100?
• Single processor: Time = (10 + 10000) × tadd
• Assuming load balanced

• 10 processors
– Time = 10 × tadd + 10000/10 × tadd = 1010 × tadd
– Speedup = 10010/1010 = 9.9 (9.9/10 = 99% of potential)

• 100 processors
– Time = 10 × tadd + 10000/100 × tadd = 110 × tadd
– Speedup = 10010/110 = 91 (91/100 = 91% of potential)

CE, KWU Prof. [Link] 8 / 33

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 = 10 × tadd + 100/10 × tadd = 20 × tadd
– 100 processors, 32 × 32 matrix
• Time = 10 × tadd + 1024/100 × tadd ≈ 20 × tadd
– Constant performance in this example

CE, KWU Prof. [Link] 9 / 33

Multiprocessor
• Shared Memory Multiprocessors
– Communication through shared memory
• Load/Store
– Shared address space
– Variants
• UMA (Uniform Memory Access)
• NUMA (Non-Uniform Memory Access)
• COMA (Cache-Only Memory Architecture)

• Message Passing Multiprocessors

– Communication through message passing
• Send/Receive
– Independent address space

CE, KWU Prof. [Link] 10 / 33

Multiprocessor organizations
• Uniform memory access (UMA) shared memory multiprocessors
– All processors share the same memory address space
– Single copy of the OS (although some parts may be parallel)
– Relatively easy to program and port sequential code to
– Hardware-intensive to scale to large numbers of processors

CE, KWU Prof. [Link] 11 / 33

Multiprocessor organizations
• Non-uniform memory access (NUMA) shared memory multiprocessors
– All memory can be addressed by all processors, but access to a
processor’s own local memory is faster than access to another
processor’s remote memory
– Looks like a distributed machine, but interconnection network is
usually custom-designed switches and/or buses

CE, KWU Prof. [Link] 12 / 33

Multiprocessor variants
• Shared memory machines connected together over a network
(operating as a distributed memory or DSM machine)

network network
controller controller

network

CE, KWU Prof. [Link] 13 / 33

Shared Memory
• SMP: shared memory multiprocessor
– Hardware provides single physical
address space for all processors
– Synchronize shared variables using
locks

• Major design issues

– Cache coherence: ensuring that stores to cached data are seen by
other processors
– Synchronization: the coordination among processors accessing
shared data
– Memory consistency: definition of when a processor must observe
a write from another processor

CE, KWU Prof. [Link] 14 / 33

Example: Sum Reduction
• Sum 100,000 numbers on 100 processor UMA
– Each processor has ID: ≤ -% ≤
– 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

CE, KWU Prof. [Link] 15 / 33

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

CE, KWU Prof. [Link] 16 / 33

Message Passing
• Each processor has private physical address space
• Hardware sends/receives messages between processors

Memory Memory Memory

Cache Cache Cache

Processor Processor … Processor

NI NI NI

Interconnection Network

CE, KWU Prof. [Link] 17 / 33

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

CE, KWU Prof. [Link] 18 / 33

Interconnection Networks
• Network topologies
– Arrangements of processors, switches, and links

Bus Ring

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

CE, KWU Prof. [Link] 19 / 33

Multistage Networks

CE, KWU Prof. [Link] 20 / 33

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

CE, KWU Prof. [Link] 21 / 33

Sum Reduction (Again)

• Sum 100,000 on 100 processors
• First distribute 1000 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, …

CE, KWU Prof. [Link] 22 / 33

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

CE, KWU Prof. [Link] 23 / 33

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

CE, KWU Prof. [Link] 24 / 33

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)

CE, KWU Prof. [Link] 25 / 33

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

CE, KWU Prof. [Link] 26 / 33

Multithreading Example

CE, KWU Prof. [Link] 27 / 33

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

architecture of a CORE i7 AMD RX-580 GPU architecture

CE, KWU Prof. [Link] 28 / 33

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

CE, KWU Prof. [Link] 29 / 33

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

CE, KWU Prof. [Link] 30 / 33

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
• SIMD instructions are also vector instructions

CE, KWU Prof. [Link] 31 / 33

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
CE, KWU Prof. [Link] 32 / 33
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

CE, KWU Prof. [Link] 33 / 33