Access Restriction

Author Blelloch, Guy E. ♦ Gibbons, Phillip B. ♦ Matias, Yossi
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1999
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Many high-level parallel programming languages allow for fine-grained parallelism. As in the popular work-time framework for parallel algorithm design, programs written in such languages can express the full parallelism in the program without specifying the mapping of program tasks to processors. A common concern in executing such programs is to schedule tasks to processors dynamically so as to minimize not only the execution time, but also the amount of space (memory) needed. Without careful scheduling, the parallel execution on $\textit{p}$ processors can use a factor of $\textit{p}$ or larger more space than a sequential implementation of the same program.This paper first identifies a class of parallel schedules that are provably efficient in both time and space. For any computation with <?Pub Fmt italic>w<?Pub Fmt /italic> units of work and critical path length <?Pub Fmt italic>d<?Pub Fmt /italic>, and for any sequential schedule that takes space s1, we provide a parallel schedule that takes fewer than w/p + d steps on p processors and requires less than s1 + p˙d spaces for the common case where $\textit{d}<<\textit{s}1.The$ paper then describes a scheduler for implementing high-level languages with $\textit{nested}$ parallelism, that generates schedules in this class. During program execution, as the structure of the computation is revealed, the scheduler keeps track of the active tasks, allocates the tasks to the processors, and performs the necessary task synchronization. The scheduler is itself a parallel algorithm, and incurs at most a constant factor overhead in time and space, even when the scheduling granularity is individual units of work. The algorithm is the first efficient solution to the scheduling problem discussed here, even if space considerations are ignored.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1999-03-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 46
Issue Number 2
Page Count 41
Starting Page 281
Ending Page 321

Open content in new tab

   Open content in new tab
Source: ACM Digital Library