Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 3033))
Included in the following conference series:
434Accesses
2Citations
Abstract
In order to harness the power of parallel computing we must firstly find appropriate algorithms that consist of a collection of (sub)tasks and secondly schedule these tasks to processing elements that communicate data between each other by means of a network. In this paper, we consider task graphs that take into account both, computation and communication costs. For a homogeneous computing system with a fixed number of processing elements we compute all the schedules with minimum schedule length. Our main contribution consist of parallelizing an informed search algorithm for calculating optimal schedules based on a Branch–and–Bound approach. While most recently proposed heuristics use task duplication, our parallel algorithm finds all optimal solutions under the assumption that each task is only assigned to one processing element. Compared to exhaustive search algorithms this parallel informed search can compute optimal schedules for more complex task graphs. In the paper, the influence of parameters on the efficiency of the parallel implementation will be discussed and optimal schedule lengths for 1700 randomly generated task graphs are compared to the solutions of a widely used heuristic.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11439
- Price includes VAT (Japan)
- Softcover Book
- JPY 14299
- Price includes VAT (Japan)
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
Aguilar, J., Gelenbe, E.: Task Assignment and Transaction Clustering Heuristics for Distributed Systems. Information Sciences 97(1&2), 199–219 (1997)
Bansal, S., Kumar, P., Singh, K.: An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems. In: IEEE Transactions on Parallel and Distributed Systems, vol. 14(6) (June 2003)
Dogan, A., Özgüner, F.: Optimal and Suboptimal reliable scheduling of precedenceconstrained tasks in heterogeneous distributed computing. In: International Workshop on Parallel Processing, Toronto, August 21-24, p. 429 (2000)
Geist, A., Beguelin, A., Dongarra, J., Jiang, W., Mancheck, R., Sunderam, V.: PVM 3 Users Guide and Reference Manual, Oak Ridge National Laboratory, Tennessee (1993)
Kafil, M., Ahmad, I.: Optimal Task assignment in heterogeneous distributed computing systems. In: IEEE Concurrency: Parallel, Distributed and Mobile Computing, pp. 42–51 (July 1998)
Kasahara, H., Narita, S.: Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing. IEEE Transactions on Computers 33(11), 1023–1029 (1984)
Kohler, W.H., Steiglitz, K.: Enumerative and Iterative Computational Approaches. In: Coffman, E.G. (ed.) Computer and Job-Shop Scheduling Theory, John Wiley & Sons, New York (1976)
Kwok, Y.-K., Ahmad, I.: Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys 31(4), 406–471 (1999)
Park, C.-I., Choe, T.Y.: An optimal scheduling algorithm based on task duplication. IEEE Transactions on Computerss 51(4) (April 2002)
Radulescu, A., van Gemund, A.J.C.: Low-Cost Task Scheduling for Distributed-Memory Machines. IEEE Transactions on Parallel and Distributed Systems 13(6) (June 2002)
Author information
Authors and Affiliations
Lehrgebiet Technische Informatik I, FernUniversität Hagen, 58084, Hagen, Germany
Udo Hönig & Wolfram Schiffmann
- Udo Hönig
Search author on:PubMed Google Scholar
- Wolfram Schiffmann
Search author on:PubMed Google Scholar
Editor information
Editors and Affiliations
Department of Computer Science and Engineering, Shanghai Jiatong University, 80 Dongcuan Road, 200240, Shanghai, China
Minglu Li
Department of Computer Science, Illinois Institute of Technology, Chicago, IL, USA
Xian-He Sun
Department. of Computer Science, Shanghai Jiaotong University, 1954 HuaShan Road, 200030, Shanghai, P.R. China
Qianni Deng
Department of Computer Science, College of Liberal Arts and Science, University of Iowa, IA 52242, Iowa City, USA
Jun Ni
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hönig, U., Schiffmann, W. (2004). A Parallel Branch–and–Bound Algorithm for Computing Optimal Task Graph Schedules. In: Li, M., Sun, XH., Deng, Q., Ni, J. (eds) Grid and Cooperative Computing. GCC 2003. Lecture Notes in Computer Science, vol 3033. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24680-0_3
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-21993-4
Online ISBN:978-3-540-24680-0
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative