What is an effective schedule?

Author

Lutz, D.R. ; Jayasimha, D.N.

Author_Institution

Dept. of Comput. & Inf. Sci., Ohio State Univ., Columbus, OH, USA

fYear

1991

fDate

2-5 Dec 1991

Firstpage

158

Lastpage

161

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

Keywords

communication complexity; directed graphs; parallel algorithms; scheduling; DAG; communication complexity; communication/time tradeoff; diamond directed acyclic graph; effective schedule; equal work restriction; lower bounds; parallel algorithms; triangular solver DAG; Algorithm design and analysis; Costs; Extraterrestrial measurements; Parallel algorithms; Performance analysis; Petroleum; Processor scheduling; Refining; Scheduling algorithm; Time measurement;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on

Conference_Location

Dallas, TX

Print_ISBN

0-8186-2310-1

Type

conf

DOI

10.1109/SPDP.1991.218284

Filename

218284