Paper Info
Title
Optimal schedules for parallel prefix computation with bounded resources
Abstract
Given xl, . . . , XN, parallel prefix computes ~1 0 X2 0 . . . 0 xk, for 1 < k ~ N, with associative operation o. We show optimal schedules for parallel prefix computation with a fixed number of resources p > 2 for a prefix of size N ~ p(p + 1)/2 . The time of the opt imal schedules with p resources is [2N/(p + 1)1 for N ~ p(p + 1)/2, which we prove to be the strict lower bound(i.e., which is what can be achieved maximally). We then present a pipelined form of optimal schedules with [2N/(p + 1)1 + [(p — 1)/21 — 1 time, which takes a, constant overhead of [(p – 1)/21 time more than the c,ptimal schedules. Parallel prefix is an important common operation in many algorithms including the evaluation of pol ynomials, general Hornor expressions, carry look-ahead circuits and ranking and packing problems. A most important application of parallel prefix is loop parallelizing transformation.
Year
DOI
Venue
1991
10.1145/109626.109627
acm sigplan symposium on principles and practice of parallel programming
Keywords
Field
DocType
optimal schedule,parallel prefix computation,bounded resource,lower bound
Computer science,Parallel computing,Theoretical computer science,Schedule,Bounded function,Parallel prefix,Distributed computing,Computation
Conference
Volume
Issue
ISSN
26
7
0362-1340
ISBN
Citations 
PageRank 
0-89791-390-6
12
1.29
References 
Authors
7
2
Name
Order
Citations
PageRank
Alexandru Nicolau12265307.74
Haigeng Wang2687.39