Massively Parallel Mathematical Sieves

Abstract

The Sieve of Eratosthenes is a well-known algorithm for finding all prime numbers in a given subset of integers. A parallel version of the Sieve is described that produces computational speedups over 800 on a hypercube with 1,024 processing elements for problems of fixed size. Computational speedups as high as 980 are achieved when the problem size per processor is fixed. The method of parallelization generalizes to other sieves and will be efficient on any ensemble architecture. We in vestigate two highly parallel sieves using scattered de composition and compare their performance on a hyper cube multiprocessor. A comparison of different paralleli zation techniques for the sieve illustrates the trade-offs necessary in the design and implementation of mas sively parallel algorithms for large ensemble computers.