Name
Title | ||
|---|---|---|
A Performance Evaluation of List Scheduling Heuristics for Task Graphs without Communication Costs |
Abstract | ||
|---|---|---|
In this paper, we propose three new static scheduling algorithms for allocating task graphs without communication costs to fully connected multiprocessors. Proposed algorithms, called MCP/ABS, MCP/CLR, and MCP/CLRR, are based on the well known MCP algorithm, and all of them have the same complexity of O(v2 log v), where v is the number of nodes in the task graph. A global comparison of proposed algorithms with three recently reported scheduling algorithms is carried out. The proposed algorithms generate similar or even better solutions than the previous algorithms in terms of the completion times of resulting schedules using a Prototype Standard Task Graph Set. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1109/ICPPW.2000.869147 | ICPP Workshops |
Keywords | Field | DocType |
communication costs,performance evaluation,communication cost,new static scheduling algorithm,prototype standard task graph,task graph,mcp algorithm,completion time,proposed algorithm,v2 log v,better solution,global comparison,task graphs,clustering algorithms,scheduling algorithm,np hard problem,computational complexity,parallel algorithms,directed graphs,prototypes,critical path,dynamic scheduling | Fixed-priority pre-emptive scheduling,Fair-share scheduling,Computer science,Parallel computing,Directed graph,Two-level scheduling,Rate-monotonic scheduling,Critical path method,Earliest deadline first scheduling,Dynamic priority scheduling | Conference |
ISBN | Citations | PageRank |
0-7695-0771-9 | 4 | 0.49 |
References | Authors | |
12 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Janez Brest | 1 | 2190 | 90.76 |
| Viljem Zumer | 2 | 268 | 21.78 |