Pseudocode 1. Create list of unmarked natural numbers 2, 3, …, n
2. k 2
3. Repeat
(a) Mark all multiples of k between k2 and n
(b) k smallest unmarked number > k
until k2 > n
4. The unmarked numbers are primes
Sources of Parallelism Domain decomposition
Divide data into pieces
Associate computational steps with data
One primitive task per array element
Making 3(a) Parallel Mark all multiples of k between k2 and n
for all j where k2 j n do
if j mod k = 0 then
mark j (it is not a prime)
endif
endfor
Making 3(b) Parallel Find smallest unmarked number > k
Min-reduction (to find smallest unmarked number > k)
Broadcast (to get result to all tasks)
Agglomeration Goals Consolidate tasks
Reduce communication cost
Balance computations among processes
Data Decomposition Options Interleaved (cyclic)
Easy to determine “owner” of each index
Leads to load imbalance for this problem
Block
Balances loads
More complicated to determine owner if n not a multiple of p
Block Decomposition Options Want to balance workload when n not a multiple of p
Each process gets either n/p or n/p elements
Seek simple expressions
Find low, high indices given an owner
Find owner given an index
Method #1 Let r = n mod p
If r = 0, all blocks have same size
Else
First r blocks have size n/p
Remaining p-r blocks have size n/p
Examples 17 elements divided among 7 processes 17 elements divided among 5 processes 17 elements divided among 3 processes
Method #1 Calculations First element controlled by process i
Last element controlled by process i
Process controlling element j
Method #2 Scatters larger blocks among processes
First element controlled by process i
Last element controlled by process i
Process controlling element j
Examples 17 elements divided among 7 processes 17 elements divided among 5 processes 17 elements divided among 3 processes
Comparing Methods Operations Method 1 Method 2 Low index 4 2 High index 6 4 Owner 7 4 Assuming no operations for “floor” function Our choice
Pop Quiz Illustrate how block decomposition method #2 would divide 13 elements among 5 processes. 13(0)/ 5 = 0 13(1)/5 = 2 13(2)/ 5 = 5 13(3)/ 5 = 7 13(4)/ 5 = 10
Comments