Skip to main content
Journal cover image

COMMUNICATION-EFFICIENT PARALLEL ALGORITHMS FOR DISTRIBUTED RANDOM-ACCESS MACHINES.

Publication ,  Journal Article
Leiserson, CE; Maggs, BM
Published in: Algorithmica (New York)
January 1, 2003

This paper introduces a model for parallel computation, called the distributed random-assess machine (DRAM), inwhich the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory accesses are implemented by routing messages through a communication network. A DRAM explicitly models the congestion of message across cuts of the network. We introduce the notion of a conservative algorithm as one whose communication requirements at each step can be bounded by the congestion of pointers of the input data structure across cuts of a DRAM. We give a simple lemma that shows how to 'shortcut' pointers in a data structure so that remote processors can communicate without causing undue congestion. We give O(lg n)-step, linear-processor, linear-space, conservative algorithms for a variety of problems on n-node trees.

Duke Scholars

Published In

Algorithmica (New York)

ISSN

0178-4617

Publication Date

January 1, 2003

Volume

38

Issue

9

Start / End Page

53 / 77

Related Subject Headings

  • Computation Theory & Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Leiserson, C. E., & Maggs, B. M. (2003). COMMUNICATION-EFFICIENT PARALLEL ALGORITHMS FOR DISTRIBUTED RANDOM-ACCESS MACHINES. Algorithmica (New York), 38(9), 53–77.
Leiserson, C. E., and B. M. Maggs. “COMMUNICATION-EFFICIENT PARALLEL ALGORITHMS FOR DISTRIBUTED RANDOM-ACCESS MACHINES.Algorithmica (New York) 38, no. 9 (January 1, 2003): 53–77.
Leiserson CE, Maggs BM. COMMUNICATION-EFFICIENT PARALLEL ALGORITHMS FOR DISTRIBUTED RANDOM-ACCESS MACHINES. Algorithmica (New York). 2003 Jan 1;38(9):53–77.
Leiserson, C. E., and B. M. Maggs. “COMMUNICATION-EFFICIENT PARALLEL ALGORITHMS FOR DISTRIBUTED RANDOM-ACCESS MACHINES.Algorithmica (New York), vol. 38, no. 9, Jan. 2003, pp. 53–77.
Leiserson CE, Maggs BM. COMMUNICATION-EFFICIENT PARALLEL ALGORITHMS FOR DISTRIBUTED RANDOM-ACCESS MACHINES. Algorithmica (New York). 2003 Jan 1;38(9):53–77.
Journal cover image

Published In

Algorithmica (New York)

ISSN

0178-4617

Publication Date

January 1, 2003

Volume

38

Issue

9

Start / End Page

53 / 77

Related Subject Headings

  • Computation Theory & Mathematics