Paper Info
Title
What is an effective schedule?
Abstract
Parallel algorithms are more difficult to analyze than sequential algorithms, in part because one has to account for communication between the processors in addition to the usual measures of time and space. To find meaningful lower bounds on communication, one has to restrict the kinds of schedules that are examined. The authors show that the traditional equal work restriction is insufficient, but they use it as a starting point, and, by successively refining their intuitive notions of what good and bad schedules are, they come up with the concept of an effective schedule. They then show that a communication/time tradeoff result which has been shown by Papadimitriou and Ullman for the diamond directed acyclic graph (DAG) (SIAM J. of Comput. vol.16, no.4, p.639-46, 1987) and Jayasimha and Loui for the triangular solver DAG (Tech. Rep.629, CSRD, Illinois Univ., Mar.1988) occurs with ineffective schedules.
Year
DOI
Venue
1991
10.1109/SPDP.1991.218284
Dallas, TX
Keywords
Field
DocType
parallel algorithm,siam j.,acyclic graph,ineffective schedule,time tradeoff result,intuitive notion,meaningful lower bound,bad schedule,effective schedule,illinois univ,communication complexity,directed acyclic graph,petroleum,scheduling,dag,time measurement,refining,algorithm design and analysis,lower bound,scheduling algorithm,directed graphs,parallel algorithms
Mathematical optimization,Algorithm design,Computer science,Scheduling (computing),Parallel algorithm,Parallel computing,Directed graph,Communication complexity,Directed acyclic graph,Schedule,Solver,Distributed computing
Conference
ISBN
Citations 
PageRank 
0-8186-2310-1
1
0.47
References 
Authors
1
2
Name
Order
Citations
PageRank
Lutz, D.R.110.47
D. N. Jayasimha215816.02