Parallel Processing and Multiprocessors Why Parallel Processing
[Pages:22]Parallel Processing and Multiprocessors
why parallel processing? types of parallel processors cache coherence synchronization memory ordering
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
1
Why Parallel Processing
go past physical limits of uniprocessing (speed of light) pros: performance
? power ? cost-effectiveness (commodity parts) ? fault tolerance
cons: difficult to parallelize applications ? automatic by compiler hard in general cases ? parallel program development ? IT IS THE SOFTWARE, stupid!
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
2
Amdahl's Law
speedup = 1/(fracenhanced/speedupenhanced + 1 - fracenhanced) speedup of 80 with 100 processors => fracparallel = 0.9975 only 0.25% work can be serial may help: problems where parallel parts scale faster than serial
? O(n2) parallel vs. O(n) serial
challenge: long latencies (often several microsecs) ? achieve data locality in some fashion
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
3
Application Domains
Parallel Processing - true parallelism in one job ? data may be tightly shared
OS - large parallel program that runs a lot of time ? typically hand-crafted and fine-tuned ? data more loosely shared ? typically locked data structures at differing granularities
transaction processing - parallel among independent transactions ? throughput oriented parallelism
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
4
Types
Flynn Taxonomy ? 1966 ? not all encompassing but simple ? based on # instruction streams and data streams ? SISD - uniprocessor ? SIMD - like vector ? MISD - few practical examples ? MIMD - multiprocessors - most common, very flexible
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
5
Single Instruction Single Data (SISD)
Instruction Storage
single instruction stream
Instruction Unit
your basic uniprocessor
Operand Storage
Execution Unit
single data stream
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
6
Single Instruction Multiple Data (SIMD)
Data Memory
registers flag
ALU
Interconnect/Alignment Network
Data Memory
. . .
Data Memory
registers flag
ALU
. . .
registers flag
ALU
. . .
Control Processor
instruction broadcast
Instruction Memory
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
7
Single Instruction Multiple Data (SIMD)
Vectors are same as SIMD ? deeply pipelined FUs vs. multiple FUs in previous slide
intrs and data usually separated leads to data parallel programming model works best for very regular, loop-oriented problems
? many important classes- eg graphics not for commercial databases, middleware (80% of server codes) automatic parallelization can work
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
8
Multiple Instruction Multiple Data (MIMD)
most flexible and of most interest to us has become the general-purpose computer automatic parallelization more difficult
Perfection: PRAM
unit latency
Main Memory no
contention
. . .
Interconnection Network no
contention
. . . Processor Processor
Processor
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
parallel RAM - theoretical model fully shared memory - unit latency no contention, no need to exploit locality
9
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
10
Perfection not achievable
latencies grow as the system size grows bandwidths restricted by memory organization and interconnect dealing with reality leads to division between
? UMA and NUMA
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
11
UMA: uniform memory access
long latency
Main Memory contention in memory banks
. . .
Interconnection Network contention in network
. . . Processor Processor
Processor
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
12
UMA: uniform memory access
latencies are the same ? but may be high
data placement unimportant latency gets worse as system grows => scalability issues typically used in small MPs only contention restricts bandwidth caches are often allowed in UMA systems
Caches
another way of tackling latency/bandwidth problems holds recently used data BUT cache coherence problems
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
13
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
14
NUMA: non-uniform memory access
Interconnection Network
long
contention in network
latency
. . . Memory Memory
Memory
short
latency
. . . Processor Processor
Processor
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
15
NUMA: non-uniform memory access
latency low to local memory latency much higher to remote memories performance very sensitive to data placement bandwidth to local may be higher contention in network and for memories
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
16
NUMA Multiprocessors
shared memory ? one logical address space ? can be treated as shared memory ? use synchronization (e.g., locks) to access shared data
multicomputers (message passing) ? each processor has its own memory address space ? use message passing for communication
Clustered Systems
small UMA nodes in large UMA systems hybrid of sorts note: ambiguity of the term "cluster"
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
17
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
18
Cluster types
Shared Memory
...
Cluster Memory 0
...
. . .
...
Cluster Memory 7
...
Proc.
Proc.
0
7
Proc.
Proc.
56
63
globally shared memory - Illinois Cedar
Cluster types
Cluster Interconnect
...
Cluster Memory 0
. . .
...
Cluster Memory 7
...
...
Proc.
Proc.
0
7
Proc.
Proc.
56
63
No global memory - Stanford Dash, Wisconsin Typhoon
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
19
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
20
COMA: cache only memory architecture
long latency
Interconnection Network contention in network
. . . Cache Cache
Cache
short
latency
. . . Processor Processor
Processor
effectively a form of NUMA ? caches only causes data to migrate naturally
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
21
Writing Parallel Programs
Decomposition, ? where is the parallelism ? Break up work
Assignment ? which thread does what (think of data)
Orchestration ? synchronization, communication
Mapping ? which thread runs where (usually thru OS)
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
22
Process communication
for most interesting parallel applications ? parallel processes (tasks) need to communicate
communication method leads to another division ? message passing ? shared memory
Shared memory vs message passing
shared memory ? programs use loads/stores + conceptually compatible with uniprocessors/small MPs + ease of programming if communication complex/dynamic + lower latency communicating small data items + hardware controlled sharing allows automatic data motion
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
23
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
24
Shared memory vs message passing
message passing ? programs use sends/receives + simpler hardware + communication pattern explicit and precise + but they MUST be explicit and precise + least common denominator ? shared memory MP can emulate message passing easily ? biggest programming burden: managing communication artifacts
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
25
Shared memory vs message passing
message passing distribute data carefully to threads
? no automatic data motion)
partition data if possible, replicate if not ? replicate in s/w not automatic (so extra work to ensure ok)
asynchronous or synchronous sends? coalesce small mesgs into large, gather separate data into one mesg to send and scatter received mesg into separate data
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
26
Shared Mem
Thread1
Thread2
....
.....
compute (data)
synchronize
store( A,B, C, D, ...)
load (A, B, C, D, ....)
synchronize
compute
......
.....
A B C D SAME in both threads- SINGLE shared memory
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
27
Mesg Passing
Thread1
Thread2
....
.....
compute (data)
receive (mesg)
store (A,B, C, D ..)
scatter (mesg to A B C D ..)
gather (A B C D into mesg)
load (A, B, C, D, ....)
send (mesg)
compute
......
.....
A B C D are DIFFERENT in each thread -- PRIVATE memory
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
28
Eg: Sequential Ocean
Eg: Shared Memory Ocean
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
29
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
30
Eg: Mesg Passing Ocean
Eg: Mesg Pass Ocean
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
31
? 2009 by Vijaykumar
ECE565 Lecture Notes: Chapter 4
32
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- multiprocessing architectures and algorithms city university of new york
- python 3 child processes university of cambridge
- multiprogramming vs multiprocessing 8 bit avenue
- parallel computing in python using mpi4py yale university
- secrets of the multiprocessing module usenix
- python multiprocessing module
- multithreading vs async io multiprocessing vs
- parallel processing and multiprocessors why parallel processing
- speed up your data processing europython 2021
- python multiprocessing university of colorado boulder computer
Related searches
- purchasing and processing checklist
- parallel and series resistor calculator
- parallel and series voltage calculator
- calculate series and parallel circuits
- parallel circuit and series circuit
- plastics materials and processing pdf
- parallel processing with python
- python parallel processing example
- python parallel processing for loop
- auditory processing and adhd
- adhd and processing disorder
- semantic and orthographic processing skills