Some Parallel Algorithms
Notes
- This is a really general overview.
- Some problems are "Embarrassingly Parallel" in any world.
- Consider Leibniz's formula for π
- $\frac{\pi}{4} = \Sigma_{k=0}^{\infty}\frac{(-1)^k}{2k+1}$
- $ = 1 -\frac{1}{3} + \frac{1}{5} - \frac{1}{7} ... $
- Assume you have n processes each numbered 1 through n
-
FIND_PI(limit) assume each process has an id, and there are n processors
-
// before parallel execution
- if process id = 1
- set GLOBAL_SUM = 0
- set FINISHED_COUNT = 0 // begin parallel execution
- k = process id
- sum = 0
- while k < limit
- sum = sum + pow(-1,k)/(2*k + 1)
- k = k + n
- LOCK GLOBAL_SUM
- GLOBAL_SUM = GLOBAL_SUM + sum
- FINISHED_COUNT = FINISHED_COUNT + 1
- UNLOCK GLOBAL_SUM
- SIGNAL done
- if process id = 1
- Wait for all processes to finish
- GLOBAL_SUM = GLOBAL_SUM * 4
- This is easiest if we have a shared memory
- Used for both the GLOBAL_SUM and FINISHED_COUNT
- If we don't have shared memory, we can implement some form of this using messages.
- Note, that there is one process in "charge" of this computation.
- This means that the system is subject to failure.
- But we are in the "parallel" part for now.
- Note this is O(n/p + p) where n is the number we want to sum to, and p is the number of processors
- And if p==n if is O(n)
- But we could fix it with a sum that
- process n+1 sends to process n if n is even
- then process n+2 sends to process n
- ...
- Think heap for combining.
- This makes it O(log2p) when n = p
- But I would have to modify the synchronization steps.
- Other algorithms might involve more work
- Consider Mergesort
- Look at the sequential version.
- We will use a fork-join model
- fork starts a new process
- join joins two processes
- This is OS stuff
- But we could use a queue
PARALLEL_MERGE_SORT(A, low, high)
- if high ≤ low
- return
- else
- mid = (high + low) / 2
- if fork == parent
- PARALLEL_MERGE_SORT(A,low, mid)
- else
- PARALLEL_MERGE_SORT(A, mid+1, high)
- join
- PARALLEL_MERGE(A, low, mid, high)
- PARALLEL_MERGE can be done in O(log22n) with infinite processors.
- Find the middle element of the largest of the two arrays to be merged (m)
- Use binary search to find where the other array is smaller than the midpoint of the larger (n)
- One processor merges (low to m, mid+1 to n) the other merges (m+1 to mid, n to high)
low ... m ... mid ... n ... high In order from recursive call In Order from recursive call - Of course, we can do these merges recursively as well.
- In the end, with parallel merge, merge sort is O(n/log22n)
- But that is a little outside of our scope.
- Consider Mergesort