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


 
 

 

Evaluating Arithmetic Expressions using Tree Contraction: A Fast and Scalable Parallel Implementation for Symmetric Multiprocessors (SMPs)

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 and across the entire range of instance sizes tested. This linear speedup with the number of processors is one of the first ever attained in practice for intricate combinatorial problems. The example we present in detail here is for evaluating arithmetic expression trees using the algorithmic techniques of list ranking and tree contraction; 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, S. Sreshta, and N.R. Weisse-Bernstein, ``Evaluating Arithmetic Expressions using Tree Contraction: A Fast and Scalable Parallel Implementation for Symmetric Multiprocessors (SMPs),''  9th International Conference on High Performance Computing (HiPC 2002), Bangalore, India, Lecture Notes in Computer Science, 2552:63-75, December 2002.

Download this report in Adobe PDF

 

 
 

Last updated: July 25, 2004

 




Computational Biology



Parallel Computing



Combinatorics