An Efficient List Scheduling Algorithm for Multiprocessor Systems 


Vol. 7,  No. 7, pp. 2060-2071, Jul.  2000
10.3745/KIPSTE.2000.7.7.2060


PDF
  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
  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.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals