An Efficient List Scheduling Algorithm for Multiprocessor Systems


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 7, No. 7, pp. 2060-2071, Jul. 2000
10.3745/KIPSTE.2000.7.7.2060,   PDF Download:

Abstract

Scheduling parallel tasks, represented as a Directed Acyclic Graph (DAG) or task graph, on a multiprocessor system has been an important research area in the past decades. List scheduling has been a typical approach for solving the problem. List scheduling algorithms assign priorities to a node or an edge in an input DAG, and then generate a schedule according to the assigned priorities. This paper proposes a list scheduling algorithm with effective method of priority assignments. The paper also analyzes the worst case performance and optimality condition for the proposed algorithm. The performance comparison study shows that the proposed algorithm outperforms existing scheduling algorithms especially for input DAGs with high communication overheads. The performance improvement over existing algorithms becomes larger as the input DAG becomes more dense and the level of parallelism in the DAG is increased.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
G. L. Park, H. S. Choo, J. H. Lee, "An Efficient List Scheduling Algorithm for Multiprocessor Systems," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 7, no. 7, pp. 2060-2071, 2000. DOI: 10.3745/KIPSTE.2000.7.7.2060.

[ACM Style]
Gyung Leen Park, Hyun Seung Choo, and Jeong Hoon Lee. 2000. An Efficient List Scheduling Algorithm for Multiprocessor Systems. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 7, 7, (2000), 2060-2071. DOI: 10.3745/KIPSTE.2000.7.7.2060.