Communications of the ACM, 39(3), March, 1996.
Next: Sparse Matrix MultiplicationUp: Examples of Parallel Algorithms Previous: Examples of Parallel Algorithms
Primes
Our first algorithm finds all the prime numbers less than n. Thisexample demonstrates a common technique used in parallelalgorithms--solving a smaller case of the same problem to speed thesolution of the full problem. We also use the example to introducethe notion of work efficiency. An important aspect of developing agood parallel algorithm is designing one whose work is close to thetime for a good sequential algorithm that solves the same problem.Without this condition we cannot hope to get good speedup of theparallel algorithm over the sequential algorithm. Parallel algorithmsare referred to as work-efficient relative to a sequentialalgorithm if their work is within a constant factor of the time of thesequential algorithm. All the algorithms we have discussed so far arework efficient relative to the best sequential algorithms. Inparticular summing n numbers took O(n) work and parallel Quicksorttook O(n log n) expected work, both of which are the same asrequired sequentially. For finding primes our goal should again be todevelop a work-efficient algorithm. We therefore start by looking atefficient sequential algorithms. 
Figure 8: Pseudocode for the sieve of Eratosthenes
The most common sequential algorithm for finding primes is the sieveof Eratosthenes, which is specified in Figure 8. Thealgorithm returns an array in which the ith position is set totrue if i is a prime and to false otherwise. The algorithm works byinitializing the array A to TRUE and then setting to FALSE all multiples of each prime it finds. It starts with the firstprime, 2, and works it way up to sqrt(n). The algorithm only needsgo up to sqrt(n) since all composite numbers (non-primes) less thann must have a factor less or equal to sqrt(n). If line 7 isimplemented by looping over the multiples, then the algorithm can beshown to take O(n log log n) time and the constant is small. Thesieve of Eratosthenes is not the theoretically best algorithm forfinding primes, but it is close and we would be happy toderive a parallel algorithm that is work-efficient relative to it(i.e. does O(n log log n) work).
It turns out that the algorithm as described has some easyparallelism. In particular, line 7 can be implemented in parallel.In NESL the multiples of a value i can be generated in parallelwith the expression
[2*i:n:i]
and can be written into the array A in parallel with the writefunction. Using the rules for costs (see Figure 6),the depth of these operations is constant and the work is the numberof multiples, which is the same as the time of the sequential version.Given the parallel implementation of line 7, the total work of thealgorithm is the same as the sequential algorithm since it does thesame number of operations, and the depth of the algorithm isO(sqrt(n)) since each iteration of the loop in lines 5-8 hasconstant depth and the number of iterations is sqrt(n). Note thatthinking of the algorithm in terms of work and depth allows a simpleanalysis (assuming we know the running time of the sequentialalgorithm) without having to worry about how the parallelism maps ontoa machine. In particular, the amount of parallelism varies greatlyfrom the first iteration, in which we have 
multiples of 2 toknock out in parallel, to the last iteration where we have onlysqrt(n) multiples. This varying parallelism would make it messy toprogram and analyze on a processor based model.
We now consider improving the depth of the algorithm without giving upany work. We note that if we were given all the primes from 2 up tosqrt(n), we could then generate all the multiples of these primesat once. The NESL code for generating all the multiples is
{[2*p:n:p]: p in sqr_primes};where sqr_primes is asequence containing all the primes up to sqrt(n). This computationhas nested parallelism, since there is parallelism across the sqr_primes (outer parallelism) and also in generating the multiplesof each prime (inner parallelism). The depth of the computation isconstant since each subcall has constant depth, and the work is 
since the total number of multiples when summed acrossthe subcalls is the same as the number of multiples used by thesequential version. 
Figure 9: The code for the primes algorithm, an exampleof one level of the recursion, and a diagram of the work and depth.In the code [] int indicates an empty sequence of integers.The function isqrt takes the square root of an integer.The function flatten takes a nested sequence and flattens it.The function dist(a,n) distributes the value a to a sequenceof length n. The expression{i in [0:n]; fl in flags | fl} can be readas ``for each i from 0 to n and each fl in flagsreturn the i if the corresponding fl is true''.The function drop(a,n) drops the first nelements of the sequence a.
We have assumed that sqr_primes was given, but to generatethese primes we can simply call the algorithm recursively onsqrt(n). Figure 9 shows the full algorithm for findingprimes based on this idea. Instead of returning a sequence of flags,the algorithm returns a sequence with the values of the primes. Forexample primes(10) would return the sequence [2,3,5,7]. The algorithm recursively calls itself on a problem ofsize sqrt(n) and terminates when a problem of size 2 is reached.The work and depth can be analyzed by looking at the pictureat the bottom of Figure 9. Clearly most of the work is done atthe top level of recursion, which does O(n log log n) work. Thetotal work is therefore also O(n log log n). Now let's considerthe depth. Since each recursion level has constant depth, the totaldepth is proportional to the number of levels. To calculate thisnumber we note that the size of the problem at level i is 
, and that when the size is 2, the algorithm terminates.This gives us the equation 
, where d is the depth weseek. Solving for d, this method gives 
. Thecosts are therefore:
This algorithm remains work efficient relative to the sequential sieveof Eratosthenes and greatly improves the depth. It is actuallypossible to improve the depth to a constant, but we will leave this asan exercise for the reader.
Next: Sparse Matrix MultiplicationUp: Examples of Parallel Algorithms Previous: Examples of Parallel Algorithms
Guy Blelloch, [email protected]
