Scheduling arbitrary number of malleable tasks on multiprocessor systems

• Autorzy: Barketau M. S. , Kovalyov M. Y. , Węglarz J. , Machowiak M.

Identyfikatory

DOI

10.2478/bpasts-2014-0025

• Języki publikacji: EN

Abstrakty

EN

The problem of scheduling n tasks in a multiprocessor system with m processors to minimize the makespan is studied. Tasks are malleable, which means that a task can be executed by several processors at a time, its processing speed depends on the number of allocated processors, and a set of processors allocated to the same task can change over time. The processing speed of a task is a strictly increasing function of the number of processors allocated to this task. The earlier studies considered the case n ≤ m. This paper presents results for arbitrary n and m including characterizations of a feasible domain and an optimal solution, polynomial time algorithms for strictly increasing convex and concave processing speed functions, and a combinatorial exponential algorithm for arbitrary strictly increasing functions.

Słowa kluczowe

EN

multi-processor scheduling; malleable tasks; makespan

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2014
• Tom: Vol. 62, nr 2
• Strony: 255--261
• Opis fizyczny: Bibliogr. 21 poz., wykr.

Twórcy

autor

Barketau M. S.

• United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, Belarus

autor

Kovalyov M. Y.

• United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, Belarus

autor

Węglarz J.

• Institute of Computing Science, Poznan University of Technology, 3a Piotrowo St., 90-965 Poznań, Poland

autor

Machowiak M.

• Institute of Computing Science, Poznan University of Technology, 3a Piotrowo St., 90-965 Poznań, Poland

Bibliografia

• [1] J. Błażewicz, M.Y. Kovalyov, M. Machowiak, D. Trystram, and J. We¸glarz, “Scheduling malleable tasks on parallel processors to minimize the makespan”, Ann. Oper. Res. 129 (1–4), 65–80 (2004).
• [2] P.E. Bernard, T. Gautier, and D. Trystram, “Large scale simulation of parallel molecular dynamics”, Proc. 13. IPPS / 10. SPDP 1, 638–644 (1999).
• [3] J. Dongarra, L. Duff, D. Danny, C. Sorensen, and H. van der Vorst, Numerical Linear Algebra for High Performance Computers (Software, Environments, Tools), Society for Industrial & Applied Mathematics, London, 1999.
• [4] J. Du and J.Y.-T. Leung “Complexity of scheduling parallel tasks systems”, SIAM J. Discrete Math. 2 (4), 473–487 (1989).
• [5] L. Bianco, J. Błażewicz, P. Dell’Olmo, and M. Drozdowski, “Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors”, Ann. Oper. Res. 58, 493–517 (1995).
• [6] J. Błażewicz, P. Dell’Olmo, M. Drozdowski, and M.G. Speranza, “Scheduling multiprocessor tasks on 3 dedicated processors”, Inform. Process. Lett. 49, 269–270 (1994).
• [7] J. Turek, J. Wolf, and P. Yu, “Approximate algorithm for scheduling parallelizable tasks”, Proc. ACM SPAA 1, 323–332 (1992).
• [8] W.T. Ludwig, “Algorithms for Scheduling malleable and nonmalleable parallel tasks”, PhD Thesis, University of Wisconsin-Madison, Department of Computer Science, Madison, 1995.
• [9] G. Mounie, C. Rapine, and D. Trystram, “Efficient approximation algorithms for scheduling malleable tasks”, Proc. ACM SPAA 1, 23–32 (1999).
• [10] G. Mounie, C. Rapine, and D. Trystram, “A 3/2-dual approximation algorithm for scheduling independent monotonic malleable tasks”, SIAM J. Comput. 37 (2), 401–412 (2007).
• [11] G.N.S. Prasanna and B.R. Musicus, “The optimal control approach to generalized multiprocessor scheduling”, Algorithmica 15 (1), 17–49 (1995).
• [12] J. Błażewicz, T.C.E. Cheng, M. Machowiak, and C. Oguz, “Berth and quay crane allocation: a moldable task scheduling model”, J. Oper. Res. Soc. 62 (7), 1189–1197 (2011).
• [13] M. Drozdowski, “Scheduling multiprocessor tasks – an overview”, Eur. J. Oper. Res. 94 (2), 215–230 (1996).
• [14] J. Błażewicz, K. Ecker, B. Plateau, and D. Trystram, Handbook on Parallel and Distributed Processing, Springer, Berlin, 2000.
• [15] J. We¸glarz, “Time-optimal control of resource allocation in a complex of operations framework”, IEEE T. Syst. Man Cyb. 6 (11), 783–788 (1976).
• [16] J. We¸glarz, “Multiprocessor scheduling with memory allocation – a deterministic approach”, IEEE T. Comput. 29 (8), 703–709 (1980).
• [17] P. Sanders and J. Speck, “Efficient parallel scheduling of malleable tasks”, IEEE Conf. IPDPS 1, 1156–1166 (2011).
• [18] K. Jansen and L. Porkolab, “Computing optimal preemptive schedules for parallel tasks: linear programming approaches”, Math. Program. 95 (3), 617–630 (2003).
• [19] K. Jansen, “Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme”, Algorithmica 39 (1), 59–81 (2004).
• [20] J. Błażewicz, M.Y. Kovalyov, M. Machowiak, D. Trystram, and J. We¸glarz, “Preemptable malleable task scheduling problem”, IEEE T. Comput. 55 (4), 485–490 (2006).
• [21] J. Klamka, “Controllability of dynamical systems. A survey”, Bull. Pol. Ac.: Tech. 61 (2), 221–229 (2013).