Decisive path scheduling: a new list scheduling method

Scheduling parallel tasks represented as a Directed Acyclic Graph (DAG), on a multiprocessor system has been an important research area in the past decades. One of the critical aspects of a class of scheduling algorithms, called "List Scheduling", is how to decide which task is to be sched...

Full description

Saved in:
Bibliographic Details
Main Authors: Gyung-Leen Park, Shirazi, B., Marquis, J., Hyunseung Choo
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Clustering algorithms
Concurrent computing
Distributed computing
Multiprocessing systems
Parallel processing
Partitioning algorithms
Performance analysis
Processor scheduling
Scheduling algorithm
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Scheduling parallel tasks represented as a Directed Acyclic Graph (DAG), on a multiprocessor system has been an important research area in the past decades. One of the critical aspects of a class of scheduling algorithms, called "List Scheduling", is how to decide which task is to be scheduled next. This is achieved by assigning priorities to the nodes or the edges of the input DAG, and thus the task with the highest priority will be scheduled next. This paper proposes a low complexity scheduling algorithm to improve the priority node selection criteria in list scheduling algorithms. The worst case performance of the proposed algorithm is analyzed for general input DAGs. Also, the worst case performance and the optimality conditions are obtained for free structured input DAGs. 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.
ISSN:0190-3918
2332-5690
DOI:10.1109/ICPP.1997.622682