The parallel complexity of scheduling with precedence constraints |
| |
| Authors: | Danny Dolev Eli Upfal Manfred K. Warmuth |
| |
| Affiliation: | 1. Department of Industrial Engineering, TOBB University of Economics and Technology, Ankara, Turkey;2. Department of Management Sciences, University of Waterloo, Waterloo, ON, Canada;3. Department of Industrial Engineering, Bilkent University, Ankara, Turkey;1. School of Data Science, Yokohama City University, Japan;2. Faculty of Information Science and Technology, Hokkaido University, Japan;3. Department of Mathematical Informatics, Nagoya University, Japan;1. Department of Informatics, King''s College London, London, UK;2. Institute of Informatics, University of Warsaw, Warsaw, Poland;3. Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel;4. CWI, Amsterdam, the Netherlands;5. Vrije Universiteit, Amsterdam, the Netherlands;1. Center Algoritmi, Department of Industrial Electronics, University of Minho, Guimarães, Portugal;2. Center of Mathematics, Department of Mathematics and Applications, University of Minho, Guimarães, Portugal;1. Department of Mathematics, University of Pannonia, Veszprem, Hungary;2. Department of Mathematics, University of Haifa, Haifa, Israel |
| |
| Abstract: | We study the problem of parallel computation of a schedule for a system of n unit-length tasks on m identical machines, when the tasks are related by a set of precedence constraints. We present NC algorithms for computing an optimal schedule in the case where m, the number of available machines, does not vary with time and the precedence constraints are represented by a collection of outtrees. The algorithms run on an exclusive read, exclusive write (EREW) PRAM. Their complexities are O(log n) and O((log n)2) parallel time using O(n2) and O(n) processors, respectively. The schedule computed by our algorithms is a height-priority schedule. As a complementary result we show that it is very unlikely that computing such a schedule is in NC when any of the above conditions is significantly relaxed. We prove that the problem is P-complete under logspace reductions when the precedence constraints are a collection of intrees and outtrees, or for a collection of outtrees when the number of available machines is allowed to increase with time. The time span of a height-priority schedule for an arbitrary precedence constraints graph is at most 2 − 1/(m − 1) times longer than the optimal (N. E Chen and C. L. Liu, Proc. 1974 Sagamore Computer Conference on Parallel Processing, T. Fend (Ed.), Springer-Verlag, Berlin, 1975, pp. 1–16). Whereas it is P-complete to produce the classical height-priority schedules even for very restricted precedence constraints graphs, we present a simple NC parallel algorithm which produces a different schedule that is only 2 − 1/m times the optimal. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
