DocumentCode
2427666
Title
Local search for DAG scheduling and task assignment
Author
Wu, Min-You ; Shu, Wei ; Gu, Jun
Author_Institution
Dept. of Comput. Sci., State Univ. of New York, Buffalo, NY, USA
fYear
1997
fDate
11-15 Aug 1997
Firstpage
174
Lastpage
180
Abstract
Scheduling DAGs to multiprocessors is one of the key issues in high-performance computing. Local search can be used to effectively improve the quality of a scheduling algorithm. In this paper, based on topological ordering, we present a fast local search algorithm which can improve the quality of DAG scheduling algorithms. This low complexity algorithm can effectively reduce the length of a given schedule
Keywords
computational complexity; directed graphs; multiprocessing systems; processor scheduling; complexity algorithm; directed acyclic graph scheduling; high-performance computing; local search; multiprocessors; task assignment; topological ordering; Computer science; Constraint optimization; Costs; Input variables; Job shop scheduling; Processor scheduling; Random variables; Scheduling algorithm; Search methods; Stochastic processes;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Processing, 1997., Proceedings of the 1997 International Conference on
Conference_Location
Bloomington, IL
ISSN
0190-3918
Print_ISBN
0-8186-8108-X
Type
conf
DOI
10.1109/ICPP.1997.622584
Filename
622584
Link To Document