Static vs. Dynamic List-Scheduling Performance Comparison
DOI:
https://doi.org/10.14311/490Keywords:
list scheduling, compile time scheduling, task graph scheduling, homogeneous computingAbstract
The problem of efficient task scheduling is one of the most important and most difficult issues in homogeneous computing environments. Finding an optimal solution for a scheduling problem is NP-complete. Therefore, it is necessary to have heuristics to find a reasonably good schedule rather than evaluate all possible schedules. List-scheduling is generally accepted as an attractive approach, since it pairs low complexity with good results. List-scheduling algorithms schedule tasks in order of priority. This priority can be computed either statically (before scheduling) or dynamically (during scheduling). This paper presents the characteristics of the two main static and the two main dynamic list-scheduling algorithms. It also compares their performance in dealing with random generated graphs with various characteristics.Downloads
Download data is not yet available.
Downloads
Published
2003-01-06
Issue
Section
Articles
How to Cite
Hagras, T., & Janeček, J. (2003). Static vs. Dynamic List-Scheduling Performance Comparison. Acta Polytechnica, 43(6). https://doi.org/10.14311/490