Evaluating arithmetic expressions using tree contraction: A fast and scalable parallel implementation for symmetric multiprocessors (SMPs)

David A. Bader, Sukanya Sreshta, Nina R. Weisse-Bernstein

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

24 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationHigh Performance Computing - HiPC 2002 - 9th International Conference, Proceedings
EditorsSartaj Sahni, Viktor K. Prasanna, Uday Shukla
PublisherSpringer Verlag
Pages63-75
Number of pages13
ISBN (Print)3540003037, 9783540003038
DOIs
StatePublished - 2002
Externally publishedYes
Event9th International Conference on High Performance Computing, HiPC 2002 - Bangalore, India
Duration: Dec 18 2002Dec 21 2002

Publication series

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

Conference

Conference9th International Conference on High Performance Computing, HiPC 2002
Country/TerritoryIndia
CityBangalore
Period12/18/0212/21/02

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Expression evaluation
  • High-performance algorithm engineering
  • Parallel graph algorithms
  • Shared memory
  • Tree contraction

Fingerprint

Dive into the research topics of 'Evaluating arithmetic expressions using tree contraction: A fast and scalable parallel implementation for symmetric multiprocessors (SMPs)'. Together they form a unique fingerprint.

Cite this