Paper Info
Title
Multiprocessor scheduling algorithm utilizing linear clustering of directed acyclic graphs
Abstract
The multiprocessor scheduling is the method to allocate modules(or tasks) with precedence relationship onto the processors in such a way that the parallel time (completion time of a program in multiprocessor system) is minimized. In this paper, we propose a scheduling heuristic which is based on linear clustering scheme and uses only local information of a DAG (Directed Acyclic Graph). Proposed algorithm gives an optimal scheduling result for a coarse grain DAG with only fork or join nodes and a greatly reduced parallel time for general DAGs. Simulation results showed that proposed algorithm has better scheduling result and less algorithm execution time than any of compared algorithms
Year
DOI
Venue
1997
10.1109/ICPADS.1997.652578
ICPADS
Keywords
Field
DocType
processor scheduling,simulation results,coarse grain dag,multiprocessor scheduling algorithm,multiprocessor system,parallel time,optimal scheduling,precedence relationship,completion time,optimal scheduling result,multiprocessor scheduling algorithm utilizing,proposed algorithm,directed graphs,digital simulation,algorithm execution time,better scheduling result,multiprocessor scheduling,linear clustering,scheduling heuristic,linear clustering scheme,directed acyclic graphs,scheduling algorithm,polynomials,directed acyclic graph,cost function,very large scale integration,clustering algorithms
Computer science,Two-level scheduling,Real-time computing,Rate-monotonic scheduling,Distributed computing,Multiprocessor scheduling,Fair-share scheduling,Parallel computing,Flow shop scheduling,Algorithm,Least slack time scheduling,Earliest deadline first scheduling,Dynamic priority scheduling
Conference
ISBN
Citations 
PageRank 
0-8186-8227-2
0
0.34
References 
Authors
2
2
Name
Order
Citations
PageRank
Choung Shik Park100.34
Sang-Bang Choi2377.00