An Approximation Algorithm for Scheduling Tasks on Varying Partition Sizes in Partitionable Multiprocessor Systems
Issue No.12 - December (1992 vol.41)
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/12.214665
<p>A partitionable multiprocessor system can form multiple partitions, each consisting of a controller and a varying number of processors. Given such a system and a set of tasks, each of which can be executed on partitions of varying sizes, the authors study the problem of choosing the partition sizes and a minimum completion time schedule for the execution of these tasks. They assume that the number of tasks to be scheduled on the system is no more than the maximum number of partitions that can be formed simultaneously by the system, and that parallelization of the tasks can achieve at most perfect speedup. They show this scheduling problem to be NP-hard, and present a polynomial time approximation algorithm for this problem. The authors derive a parameter dependent, asymptotically tight worst-case performance bound for the algorithm, and evaluate its average performance through simulation.</p>
task scheduling; polynomial time algorithm; parameter dependent bound; asymptotically tight bound; approximation algorithm; partition sizes; partitionable multiprocessor systems; multiple partitions; controller; processors; minimum completion time schedule; parallelization; NP-hard; worst-case performance bound; computational complexity; multiprocessing programs; multiprocessing systems; parallel algorithms; scheduling.
R. Krishnamurti, E. Ma, "An Approximation Algorithm for Scheduling Tasks on Varying Partition Sizes in Partitionable Multiprocessor Systems", IEEE Transactions on Computers, vol.41, no. 12, pp. 1572-1579, December 1992, doi:10.1109/12.214665