Using PRAM algorithms on a uniform-memory-access shared-memory architecture

David A. Bader, Ajith K. Illendula, Bernard M.E. Moret, Nina R. Weisse-Bernstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithm Engineering - 5th International Workshop, WAE 2001, Proceedings
Number of pages16
StatePublished - 2001
Externally publishedYes
Event5th International Workshop on Algorithm Engineering, WAE 2001 - Arhus, Denmark
Duration: Aug 28 2010Aug 31 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2141 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference5th International Workshop on Algorithm Engineering, WAE 2001

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Using PRAM algorithms on a uniform-memory-access shared-memory architecture'. Together they form a unique fingerprint.

Cite this