Title | ||
---|---|---|
A Multiprocessor Scheduling Heuristic for Functional Parallelism and its Performance Measure |
Abstract | ||
---|---|---|
This paper addresses the following scheduling problem: given a precedence graph with communication costs and a machine architecture with different types of processors, construct a schedule that runs on the given architecture at the minimum possible execution time. The main contributions are:- Firstly, we present a static scheduling algorithm that keeps processors idle for future important tasks and fills idle time slots incurred due to interprocessor communication.- Secondly, to evaluate the effectiveness of the algorithm, we develop a lower bound on the length of a optimal schedule as a yardstick.Experiments show that this new approach produces better schedules and takes much less compile time. |
Year | DOI | Venue |
---|---|---|
1997 | 10.1109/ICPADS.1997.652579 | ICPADS |
Keywords | Field | DocType |
parallel programming,processor scheduling,software performance evaluation,communication costs,functional parallelism,idle time slots,interprocessor communication,lower bound,machine architecture,multiprocessor scheduling heuristic,performance measure,precedence graph,static scheduling algorithm | Heuristic,Multiprocessor scheduling,Job shop scheduling,Scheduling (computing),Computer science,Compile time,Parallel computing,Real-time computing,Schedule,Concurrent computing,Precedence graph,Distributed computing | Conference |
ISBN | Citations | PageRank |
0-8186-8227-2 | 0 | 0.34 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dingchao Li | 1 | 1 | 2.76 |
Akira Mizuno | 2 | 6 | 6.03 |
Yuji Iwahori | 3 | 159 | 56.83 |
Naohiro Ishii | 4 | 461 | 128.62 |