Algorithms PART II: Partitioning and Divide & Conquer
[Pages:30]Algorithms PART II: Partitioning and
Divide & Conquer
HPC Fall 2012 Prof. Robert van Engelen
Overview
Partitioning strategies Divide and conquer strategies Further reading
11/14/12
HPC Fall 2012
2
Partitioning Strategies
Block partitioning of a 2D domain
Data partitioning
Perform domain decomposition to run parallel tasks on subdomains
"Scatter-compute-gather" where local computation may require communication and scatter/gather may involve computations
function f(x,y) u=g(x) v=h(y) return u+v end
Thread 1 Thread 2
u=g(x) v=h(y)
return u+v
Task partitioning
Decompose functions into independent subfunctions and execute the subfunctions in parallel
11/14/12
HPC Fall 2012
3
Partitioning Strategies
Partitioning strategy (data partitioning):
1. Break up a given problem into P subproblems 2. Solve the P subproblems concurrently 3. Collect and combine the P solutions
Embarrassingly parallel
Is a simple form of data partitioning into independent subproblems without initial work and no communication between tasks (workers)
11/14/12
HPC Fall 2012
4
Partitioning Example 1: Summation
Summation of n values X = [x1,...,xn]
1. Divide X into P equally-sized sublists Xp, p = 0,...,P-1 and distribute the Xp sublists to the P processors
2. The processors sum the local parts sp = Xp 3. Combine the local sums s = sp
Algorithms: 1. Scatter list X using a scatter-tree 2. Serial summation of parts 3. Reduce local sums
11/14/12
HPC Fall 2012
5
Partitioning Example 1: Summation
n/4
n/8
n/8
n/2 n/8
Log2(P) steps
n/4
Total amount of
data transferred:
n/8 n/2 log2(P)
scatter (divide)
time
Local summations: n/P steps
reduce (combine)
11/14/12
1
1
1
1
1 Log2(P) steps
Total amount of
1
data transferred:
P-1 1
HPC Fall 2012
6
Partitioning Example 1: Summation
Communication time
Scatter:
tcomm1 = k=1..log2(P) (tstartup + 2-kn tdata) = log2(P)tstart + n(P-1)/P tdata
Reduce:
tcomm2 = log2(P) (tstart + tdata)
Total:
tcomm = 2 log2(P)tstart + ( n(P-1)/P + log2(P) ) tdata
Computation time
Local sum:
tcomp1 = n/P
Global sum:
tcomp2 = log2(P)
Total:
tcomp = n/P + log2(P)
Speedup, assuming tstartup = 0
Sequential time: ts = n-1
Parallel time: tP = ( n(P-1)/P + log2(P) ) tdata + n/P + log2(P)
Speedup:
SP = ts/tP = O(n / (n + log(P)))
Best speedup w/o communication:
SP = O(P/log(P))
11/14/12
HPC Fall 2012
7
General M-Ary Partitioning
divide compute
Example: partitioning an image, e.g. to
compute histogram by parallel reductions
(summations to count color pixels)
Second division
First division
Third division
time
combine
11/14/12
3-level 4-ary partitioning for 43 = 64 processors
HPC Fall 2012
8
................
................
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
- randomized median finding and quicksort
- sorting considerations sorting algorithms 1 virginia tech
- linked lists yeah a5 stanford university
- divide and conquer algorithms california state university long beach
- algorithms part ii partitioning and divide conquer
- the list is partitioned into two sublists each sublist is then sorted
- deciding functional lists with sublist sets new york university
- chapter 4 data structures purdue university
Related searches
- part of synonyms and antonyms
- divide give quotient and remainder
- ielts speaking part 1 questions and answers
- acls algorithms 2019
- acls algorithms pdf
- advantage ii flea and tick
- divide and simplify calculator
- part time evening and weekend jobs
- multiply and divide sig figs
- conquer your fears quote
- multiply and divide rationals calculator
- multiply and divide functions calculator