Scheduling arbitrary number of malleable tasks on multiprocessor systems

Bulletin of the Polish Academy of Sciences. Technical Sciences

J. W?glarzInstitute of Computing Science, Poznan University of Technology, 3a Piotrowo St., 90-965 Pozna?, PolandOther articles by this author:De Gruyter OnlineGoogle Scholar¹  M. MachowiakInstitute of Computing Science, Poznan University of Technology, 3a Piotrowo St., 90-965 Pozna?, PolandEmailOther articles by this author:De Gruyter OnlineGoogle Scholar¹  M.S. BarketauUnited Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, BelarusOther articles by this author:De Gruyter OnlineGoogle Scholar²  M.Y. KovalyovUnited Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, BelarusOther articles by this author:De Gruyter OnlineGoogle Scholar² 

[1] Institute of Computing Science, Poznan University of Technology, 3a Piotrowo St., 90-965 Pozna?, Poland;United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, Belarus

关键词: Keywords: multiprocessor scheduling;    malleable tasks;    makespan;   

DOI  :  10.2478/bpasts-2014-0025

学科分类：工程和技术（综合）

来源: Polska Akademia Nauk * Centrum Upowszechniania Nauki / Polish Academy of Sciences, Center for the Advancement of Science

【 摘 要 】

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.

【 授权许可】

Unknown