Transcript Monday, September 02, 2002

Friday, September 29, 2006
If all you have is a hammer,
then everything looks like
a nail.
- Anonymous
1

Domain Decomposition
1.
2.

Divide data in approx. equal parts
Partition the computation
Functional Decomposition
1.
2.
Divide the computation into disjoint tasks
Determine data requirements of these tasks
2

Domain Decomposition
1.
2.

Divide data in approx. equal parts
Partition the computation
Functional Decomposition
1.
2.


Divide the computation into disjoint tasks
Determine data requirements of these tasks
If data is disjoint then partition is complete
If there is significant overlap  consider
domain decomposition.
3
Task dependency graph?
4
 Typically maximum degree of
concurrency is less than the total number
of tasks.
5
 Typically maximum degree of
concurrency is less than the total number
of tasks.
 Degree of concurrency depends on shape
of task dependency graph.
6
 Degree of concurrency depends on shape of task
dependency graph.
7
Mapping
 Maximize use of concurrency.
 Task dependencies and interactions are
important in selection of good mapping.
 Minimize completion time by making
sure that the processes on critical path
execute as soon as they are ready.
8
Mapping
 Maximize concurrency and minimize
interaction among processors


Place tasks that are able to execute
independently on different processors to
increase concurrency.
Place tasks that communicate frequently on
same processor to increase locality.
9
Mapping
Cannot use more than 4 processors. Why?
10
Mapping
Prevent inter-task interaction from becoming
inter-process interaction
11
Agglomeration
12
Data partitioning: Block distribution
Higher
dimensional
distributions
may help
reduce the
amount of
shared data
that needs to
be accessed
13
Data partitioning: Block distribution
Higher
dimensional
distributions
may help
reduce the
amount of
shared data
that needs to
be accessed.
n2/p +n2 vs.
2n2/√p
14
Sum N numbers
 N numbers are distributed among N tasks
Centralized algorithm
15
Sum N numbers
 N numbers are distributed among N tasks
Distributing computation
16
Recursive Decomposition
 Divide and conquer
 Set of independent sub-problems
17
Recursive Decomposition
 Sum N numbers.
How many steps required?
18
19
20
Hybrid decomposition
 Possible to combine different techniques
 Finding minimum of a large set of
numbers by purely recursive
decomposition is not efficient.
21
Hybrid decomposition
22
Exploratory Decomposition
23
Unfinished
tasks can be
terminated
once solution
is found
24
25
 Read: Speculative Decomposition
26
Communications
 Most parallel problems need to
communicate data between different
tasks.
27
Embarrassingly Parallel Applications
 No communication between tasks.
 One end of spectrum of parallelization
 Examples?
28
Factors involving communication
 Machine cycles and resources that could be
used for computation are instead used to
package and transmit data.
 Sending many small messages can cause
latency to dominate communication
overheads.
 Package small messages into a larger
message results in increased bandwidth.
29
Factors involving communication
 Synchronous communications.
 Asynchronous communications.
 Interleaving computation with
communication.
30
npoints = 10000
circle_count = 0
do j = 1,npoints
generate 2 random
numbers between 0 and 1
xcoordinate = random1 ;
ycoordinate = random2 ;
if (xcoordinate,
ycoordinate) inside
circle then
circle_count =
circle_count + 1
end do
PI =
4.0*circle_count/npoints
31
32