Parallel Sieve algorithms on a hypercube multiprocessor

ABSTRACT

Two sieve algorithms, a pipeline and a parallel version are presented for a distributed-memory multiprocessor. Traditionally, the sieve algorithm is solved using a pipeline approach. This algorithm has a high communication to computation ratio and as a result performs poorly. The parallel algorithm is a substantial improvement over the traditional pipeline algorithm. It has a low communication to computation ratio. The speedup for this algorithm is nearly linear. Further, unlike the pipeline algorithm, the parallel algorithm performs just as well or even better on a shared memory multiprocessor system.

REFERENCES

• 1: Shahid H. Bokhari, Multiprocessing the Sieve of Eratosthenes, Computer, v.20 n.4, p.50-58, April 1987 [doi>10.1109/MC.1987.1663535]
• 2: J.R. Edwards and G. Hartwig, Benchmarking the clones, Byte, Vol. i0, No. Ii, Nov. 1985, pp. 195-201.
• 3: NCUBE Corporation, NCUBE System Manual, 1987.
• 4: T.A. Peng, One Million Primes Through Sieve, Byte, Vol. i0, NO. ii, Nov. 1985, pp. 243-244.
• 5: Roger L. Wainwright, Deriving parallel computations from functional specifications: a seismic example on a hypercube, International Journal of Parallel Programming, v.16 n.3, p.243-260, June 1987 [doi>10.1007/BF01407935]
• 6: R.L. Wainwright, Message Passing Considerations for Hypercube Multiprocessors, Proceedings of the Second Workshop on Applied Computing, Unlversity of Tulsa, Tulsa, Oklahoma, March, 1988.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.2 COMPUTER-COMMUNICATION NETWORKS

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design