UET scheduling with unit interprocessor communication delays.

*(English)*Zbl 0634.90031We consider the problem of scheduling a partially ordered set of unit execution time tasks (UET) on \(m>1\) processors where there is a communication delay of unit time between any pair of distinct processors. We show that the problem of finding an optimal schedule is NP-hard. A greedy schedule is one where no processor remains idle if there is some task available which it could process. We establish that the length of an arbitrary greedy schedule, \(\omega^ c_ g\) satisfies
\[
\omega^ c_ g\leq (3-\frac{2}{m})\omega^ c_{opt}-(1-\frac{1}{m})
\]
where \(\omega^ c_{opt}\) is the length of the optimal schedule. We define a generalized list schedule (a type of greedy schedule) and discuss anomalous behaviour of such schedules with respect to speed-up. The relevance of these results to the implementation of parallel languages is discussed.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

68Q25 | Analysis of algorithms and problem complexity |

65K05 | Numerical mathematical programming methods |

##### Keywords:

UET scheduling; list scheduling; multiprocessor systems; NP-completeness; speed-up anomaly; scheduling a partially ordered set of unit execution time; communication delay; NP-hard; greedy schedule; parallel languages
PDF
BibTeX
XML
Cite

\textit{V. J. Rayward-Smith}, Discrete Appl. Math. 18, 55--71 (1987; Zbl 0634.90031)

Full Text:
DOI

##### References:

[1] | Agerwala, T., Communication, computation and computer architecture, (), 209-215 |

[2] | Brucker, P.; Garey, M.R.; Johnson, D.S., Scheduling equal length tasks under treelike precedence constraints to minimize maximum lateness, Math. oper. res., 2, 3, 275-284, (1977) · Zbl 0397.90044 |

[3] | F.W. Burton, G.P. McKeown and V.J. Rayward-Smith, Applications of UET scheduling theory to the implementation of parallel languages, submitted for publication. · Zbl 0646.68108 |

[4] | Chen, N.-F.; Liu, C.L., On a class of scheduling algorithms for multiprocessor computing systems, () |

[5] | () |

[6] | Coffman, E.G.; Graham, R.L., Optimal scheduling for two processor systems, Acta informatica, 1, 3, 200-213, (1972) · Zbl 0248.68023 |

[7] | Cornett, D.H.; Franklin, M.A., Scheduling independent tasks with communications, (1979), Dept. Electrical Engineering, Washington University, Technical Report |

[8] | Didic, M.; Kohlhepp, P.; Oberle, R., Performance analysis of a distributed real time system, (), 57-68 |

[9] | Dempster, M.A.H.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Deterministic and stochastic scheduling, () · Zbl 0464.90037 |

[10] | El-Dessouki, O.J., Program partitioning and load balancing in network computers, () |

[11] | Dijkstra, E.W., Cooperative sequential processes (1965), () |

[12] | Graham, R.L., Bounds on multiprocessing timing anomalies, SIAM J. appl. math., 17, 2, 416-429, (1969) · Zbl 0188.23101 |

[13] | Hu, T.C., Parallel sequencing and assembly line problems, Operations research, 9, 6, 841-884, (1961) |

[14] | Lam, S.; Sethi, R., Worst case analysis of two scheduling algorithms, SIAM J. comput., 6, 3, 518-536, (1977) · Zbl 0374.90031 |

[15] | Lo, V.M., Task assignment in distributed systems, () |

[16] | McKeown, G.P.; Rayward-Smith, V.J., Communication problems on MIMD parallel computers, Inform. process. lett., 19, 2, 69-73, (1984) |

[17] | Pathak, G.C.; Agrawal, D.P., Task division and multicomputer systems, () |

[18] | R. Sethi, Algorithms for minimal length schedules, in [5]. |

[19] | Ullman, J.D., NP-complete scheduling problems, J. comput. system sci., 10, 384-393, (1975) · Zbl 0313.68054 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.