SUBOPTIMAL APPROACHES TO SCHEDULING MALLEABLE TASKS
Błażewicz Jacek 1, Machowiak M. 1, Mounié G. 2, Trystram D. 2
1 Institute of Computing Science, Poznań University of Technology
ul. Piotrowo 3a, 60-965 Poznań, Poland
2ID-IMAG, antenne de I’ENS IMAG
ZIRST de Montbonnot, 51 rue Jean Kuntzman
38330 Montbonnot Saint Martin, France
DOI: 10.12921/cmst.2000.06.01.25-40
OAI: oai:lib.psnc.pl:507
Abstract:
In the paper, the problem of scheduling a set of n malleable tasks on m parallel computers is considered. The tasks may be executed by several processors simultaneously and the processing speed of a task is a function of the number of processors alloted. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. Starting from the continuous version of the problem (i. e. where the tasks may require a fractional part of the resources), we propose a general approximation algorithm with a performance guarantee equal to 2. Then, some improvements are derived that lead to a very good average behavior of the scheduling algorithm.
References:
[1] E. Blayo, L. Debreu, G. Mounié. D. Trystram, Engineering Simulation, 22, 8 (2000).
[2] A. Barak, and O. La’adan, Journal ofFuture Generation Computer Systems, 1998.
[3] P. E. Bernard, Parallelisation et multiprogrammation pour line application irreguliere de
dynamique moleculaire operationnelle, Mathematiques appliques, Institut National Polytechnique de Grenoble, 1997.
[4] J. Błażewicz, M. Drabowski, J. Węglarz, IEEE Transactions on Computers 35, 389 (1986).
[5] J. Błażewicz, M. Machowiak, G. Mounié, D. Trystram, J. Węglarz, Revista Iberoamericana de
Computación, 2000, to appear.
[6] M. Berger and J. Oliger, J. Comp. Phys. 53, 484 (1984).
[7] E. Blayo and L. Debreu, J. Phys. Oceanogr. 29, 1239 (1998).
[8] P. E. Bernard, T. Gautier, D. Trystram, Proceedings of Second Merged Symposium IPPS/SPDP 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, San Juan, Puerto Rico, 1999.
[9] J. Dongarra, L. Duff, D. Danny, G. Sorensen, H. van der Vorst, Society for Industrial & Applied Mathematics, 1999.
[10] J. Du, J.Y-T. Leung, SIAM Journal on Discrete Mathematics, 2, 473 (1989).
[11] R. L. Graham, Bell System Tech. J. 45, 1563 (1966).
[12] E. Lloyd, Journal of the ACM, 29, 781 (1982).
[13] W. T. Ludwig, Algorithms for scheduling malleable and nonmalleable parallel tasks, PhD thesis, University of Wisconsin-Madison, Department of Computer Sciences, 1995.
[14] G. Mounié, C. Rapine, D. Trystram, Efficient approximation algorithms for scheduling malleable tasks, In: Eleventh ACM Symposium on Parallel Algorithms and Architectures (SPAA’99), ACM, 23 (1999).
[15] G. N. S. Prasanna and B. R. Musicus, Algorithmica (1995).
In the paper, the problem of scheduling a set of n malleable tasks on m parallel computers is considered. The tasks may be executed by several processors simultaneously and the processing speed of a task is a function of the number of processors alloted. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. Starting from the continuous version of the problem (i. e. where the tasks may require a fractional part of the resources), we propose a general approximation algorithm with a performance guarantee equal to 2. Then, some improvements are derived that lead to a very good average behavior of the scheduling algorithm.
[1] E. Blayo, L. Debreu, G. Mounié. D. Trystram, Engineering Simulation, 22, 8 (2000).
[2] A. Barak, and O. La’adan, Journal ofFuture Generation Computer Systems, 1998.
[3] P. E. Bernard, Parallelisation et multiprogrammation pour line application irreguliere de
dynamique moleculaire operationnelle, Mathematiques appliques, Institut National Polytechnique de Grenoble, 1997.
[4] J. Błażewicz, M. Drabowski, J. Węglarz, IEEE Transactions on Computers 35, 389 (1986).
[5] J. Błażewicz, M. Machowiak, G. Mounié, D. Trystram, J. Węglarz, Revista Iberoamericana de
Computación, 2000, to appear.
[6] M. Berger and J. Oliger, J. Comp. Phys. 53, 484 (1984).
[7] E. Blayo and L. Debreu, J. Phys. Oceanogr. 29, 1239 (1998).
[8] P. E. Bernard, T. Gautier, D. Trystram, Proceedings of Second Merged Symposium IPPS/SPDP 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, San Juan, Puerto Rico, 1999.
[9] J. Dongarra, L. Duff, D. Danny, G. Sorensen, H. van der Vorst, Society for Industrial & Applied Mathematics, 1999.
[10] J. Du, J.Y-T. Leung, SIAM Journal on Discrete Mathematics, 2, 473 (1989).
[11] R. L. Graham, Bell System Tech. J. 45, 1563 (1966).
[12] E. Lloyd, Journal of the ACM, 29, 781 (1982).
[13] W. T. Ludwig, Algorithms for scheduling malleable and nonmalleable parallel tasks, PhD thesis, University of Wisconsin-Madison, Department of Computer Sciences, 1995.
[14] G. Mounié, C. Rapine, D. Trystram, Efficient approximation algorithms for scheduling malleable tasks, In: Eleventh ACM Symposium on Parallel Algorithms and Architectures (SPAA’99), ACM, 23 (1999).
[15] G. N. S. Prasanna and B. R. Musicus, Algorithmica (1995).
