Abstract
In parallel and distributed computing scheduling low level tasks on the available hardware is a fundamental problem. Traditionally, one has assumed that the set of tasks to be executed is known beforehand. Then the scheduling constraints are given by a precedence graph. Nodes represent the elementary tasks and edges the dependencies among tasks. This static approach is not appropriate in situations where the set of tasks is not known exactly in advance, for example, when different options how to continue a program may be granted.
In this paper a new model for parallel and distributed programs, the dynamic process graph, will be introduced, which represents all possible executions of a program in a compact way. The size of this representation is small - in many cases only logarithmically with respect to the size of any execution. An important feature of our model is that the encoded executions are directed acyclic graphs having a ”regular” structure that is typical of parallel programs. Dynamic process graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. With respect to such a compact representation we investigate the complexity of different aspects of the scheduling problem: the question whether a legal schedule exists at all and how to find an optimal schedule. Our analysis takes into account communication delays between processors exchanging data. Precise characterization of the computational complexity of various variants of this compact scheduling problem will be given in this paper. The results range from easy, that is \( \mathcal{N}\mathcal{L}\mathcal{O}\mathcal{G}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E} \) -complete, to very hard, namely \( \mathcal{N}\mathcal{E}\mathcal{X}\mathcal{P}\mathcal{T}\mathcal{I}\mathcal{M}\mathcal{E} \) -complete.
Supported by DFG Research Grant Re 672/2.
On leave of Instytut Informatyki, Uniwersytet Wrocławski, Wrocław, Poland.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Burns, Programming in Occam 2, Addison-Wesley Publishing Company, 1988.
H. El-Rewini and H. H. Ali, Static Scheduling of Conditional Branches in Parallel Programs, J. Par. Distrib. Comput. 24, 1995, 41–54.
H. Galperin, A. Wigderson, Succinct Representations of Graphs, Information and Control, 56, 1983, 183–198.
S. Ha, E. Lee, Compile-time Scheduling and Assignment of Data-flow Program Graphs with Data-dependent Iteration, IEEE Trans. Computers 40, 1991, 1225–1238.
A. Jakoby, M. Liśkiewicz, R. Reischuk, Scheduling Dynamic Graphs, Technischer Bericht, Institut für Theoretische Informatik, Med. Universität zu Lübeck, 1998.
A. Jakoby and R. Reischuk, The Complexity of Scheduling Problems with Communication Delay for Trees, Proc. 3. SWAT, 1992, 165–177.
H. Jung, L. Kirousis, P. Spirakis, Lower Bounds and Efficient Algorithms for Multiprocessor scheduling of DAG s with Communication Delays, Proc. 1. SPAA, 1989, 254–264.
R. Kieckhafer, Fault-Tolerant Real-Time Task Scheduling in the MAFT Distributed System, Proc. 22. Hawaii Int. Conf. on System Science, 1989, 145–151.
R. Kieckhafer, C. Walter, A. Finn, P. Thambidurai, The MAFT Architecture For Distributed Fault-Tolerance, IEEE Trans. Computers, April 1988, 398–405.
T. Lengauer, K. Wagner, The Correlation between the Complexities of the Nonhierarchical and Hierarchical Versions of Graph Problems, J. CSS 44, 1992, 63–93.
C. Papadimitriou and M. Yannakakis, A Note on Succinct Representations of Graphs, Information and Control, 71, 1986, 181–185.
C. Papadimitriou and M. Yannakakis, Towards an Architecture-Independent Analysis of Parallel Algorithms, Proc. 20. STOC, 1988, 510–513, see also SIAM J. Comput. 19, 1990, 322–328.
B. Veltman, Multiprocessor Scheduling with Communication Delays, Ph.D. Thesis, University of Technology Eindhoven, Department of Computer Science, Eindhoven, The Netherlands, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jakoby, A., Liśkiewicz, M., Reischuk, R. (1999). Scheduling Dynamic Graphs. In: Meinel, C., Tison, S. (eds) STACS 99. STACS 1999. Lecture Notes in Computer Science, vol 1563. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49116-3_36
Download citation
DOI: https://doi.org/10.1007/3-540-49116-3_36
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65691-3
Online ISBN: 978-3-540-49116-3
eBook Packages: Springer Book Archive