Scheduling malleable and nonmalleable parallel tasks
Scheduling malleable and nonmalleable parallel tasks
复制标题
DOI：
--
复制
发表时间：
1994-01
期刊：
影响因子：
--
通讯作者：
W. Ludwig;Prasoon Tiwari
中科院分区：
文献类型：
--
作者：
W. Ludwig;Prasoon Tiwari
可延性并行任务是指可以在任意数量的处理器上执行的任务，其执行时间是分配给它的处理器数量的函数。不可延展性并行任务是指需要特定数量的处理器的任务。给定n个独立的并行任务和m个相同的处理器，我们考虑调度这些任务以最小化makespan的问题。我们证明了任何非延展性任务调度算法都可以推广到延展性任务调度算法。新算法的近似因子与原算法相同。同时，运行时间只增加了一个0（mn）项。由此，我们得到了调度可延性并行任务的多项式时间算法的最佳已知近似因子，以及该因子所能达到的最快运行时间。这些结果可以扩展到特定的并行体系结构，其中不仅分配给任务的处理器数量，而且它们的配置也是一个因素。此外，我们还提供了一种在线性处理器阵列上调度可延展任务的算法。在这种情况下，分配给每个任务的处理器地址必须是连续的。在对任务执行时间的自然假设下，我们的算法有一个近似因子为2。相反，对于这种情况下的不可延展性任务，最著名的近似因子是2.5。据我们所知，这是唯一一种情况，即可塑任务的最佳已知近似因子严格小于不可塑任务的近似因子。
Walter Ludwig+ A malleable parallel task is one that can be executed on any number of processors, with its execution time being a function of the number of processors allotted to it. A nonmalleable parallel task is one that requires a specific number of processors. Given n independent parallel tasks and m identical processors, we consider the problem of scheduling these tasks to minimize makespan. We show that any algorithm for scheduling nonmalleable tasks can be extended to an algorithm for scheduling malleable tasks. The approximation factor of the new algorithm is identical to that of the original algorithm. Meanwhile, only an 0(mn) term is added to the running time. Thus we get the best known approximation factor of a polynomial-time algorithm for scheduling malleable parallel tasks, and the fastest running time in which that factor can be achieved. These results can be extended to specific parallel architectures, where not only the number of processors allotted to a task, but also their configuration is a factor. Furthermore, we provide an algorithm for scheduling malleable tasks on a linear array of processors. In this case the addresses of the processors assigned to each task must be contiguous. Our algorithm has an approximation factor of 2, under a natural assumption on the task execution times. In contrast, the best known approximation factor for nonmalleable tasks in this case is 2.5. To the best of our knowledge, this is the only case where the best known approximation factor for malleable tasks is strictly less thanthat for nonmalleable tasks.