David A. Bader
IEEE Fellow
AAAS Fellow
College of Computing
Georgia Tech
Atlanta, GA 30332



Using PRAM Algorithms on a Uniform-Memory-Access Shared-Memory Architecture

The ability to provide uniform shared-memory access to a significant number of processors in a single SMP node brings us much closer to the ideal PRAM parallel computer. In this paper, we develop new techniques for designing a uniform shared-memory algorithm from a PRAM algorithm and present the results of an extensive experimental study demonstrating that the resulting programs scale nearly linearly across a significant range of processors (from 1 to 64) and across the entire range of instance sizes tested. This linear speedup with the number of processors is, to our knowledge, the first ever attained in practice for intricate combinatorial problems. The example we present in detail here is a graph decomposition algorithm that also requires the computation of a spanning tree; this problem is not only of interest in its own right, but is representative of a large class of irregular combinatorial problems that have simple and efficient sequential implementations and fast PRAM algorithms, but have no known efficient parallel implementations. Our results thus offer promise for bridging the gap between the theory and practice of shared-memory parallel algorithms.

Publication History

Versions of this paper appeared as:
  1. D.A. Bader, A. Illendula, B.M.E. Moret, and N.R. Weisse-Bernstein, ``Using PRAM Algorithms on a Uniform-Memory-Access Shared-Memory Architecture,'' presented at the Fifth Workshop on Algorithm Engineering (WAE2001), University of Aarhus, Denmark, Lecture Notes in Computer Science, 2141:129-144, August 2001.

Download this report in Adobe PDF



Last updated: July 25, 2004


Computational Biology

Parallel Computing