@inproceedings{f79540de876f47f2897519a008d5898e,
title = "Lower bounds and efficient algorithms for multiprocessor scheduling of dags with communication delays",
abstract = "We present here an n τ+ 1 algorithm for optimally scheduling a dag of n nodes on a multiprocessor when the message-To-instruction ratio parameter is τ. Our algorithm constructs an optimum schedule which uses at most n processors. We furthermore show lower bound results on the amount of recomputations needed, thus answering an open question posed by Papadimitriou and Yannakakis. In addition, precise lower bounds are demonstrated for the scheduling time of full binary trees. Our techniques may contribute to an important new understanding of parallel scheduling when the message delay is significant, which is usually the case.",
author = "Hermann Jung and Lefteris Kirousis and Paul Spirakis",
note = "Publisher Copyright: {\textcopyright} 1989 ACM.; 1st Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1989 ; Conference date: 18-06-1989 Through 21-06-1989",
year = "1989",
month = mar,
day = "1",
doi = "10.1145/72935.72962",
language = "English (US)",
series = "Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1989",
publisher = "Association for Computing Machinery, Inc",
pages = "254--264",
editor = "F.T. Leighton",
booktitle = "Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1989",
}