Title :
A new list scheduling method based on structural properties of task graphs
Author :
Fujita, Satoshi ; Nakagawa, Tadanori ; Yamashita, Masafumi
Author_Institution :
Fac. of Eng., Hiroshima Univ., Japan
Abstract :
We propose a new list scheduling method for obtaining a quasi-optimal solution to the multiprocessor scheduling problem that has been recognized as a key problem for realizing parallelizing compilers. Our approach for achieving a nearly optimal performance is to take a linear combination of several characteristics to obtain a heuristic function instead of taking a lexicographical combination. The goodness of the resultant heuristics is evaluated by experiments
Keywords :
parallelising compilers; processor scheduling; heuristic function; linear combination; list scheduling method; multiprocessor scheduling problem; nearly optimal performance; parallelizing compilers; quasi-optimal solution; structural properties; task graphs; Information science; Multiprocessing systems; Processor scheduling; Program processors;
Conference_Titel :
Parallel and Distributed Systems: Workshops, Seventh International Conference on, 2000
Conference_Location :
Iwate
Print_ISBN :
0-7695-0571-6
DOI :
10.1109/PADSW.2000.884507
