Robust scheduling for heterogeneous architectures

• Main Author: Wong, Yi Wen.
• Other Authors: Low Yoke Hean, Malcolm
• Format: Final Year Project
• Language: English
• Published: 2010
• Subjects: DRNTU::Engineering::Computer science and engineering::Computer systems organization::Processor architectures
• Online Access: http://hdl.handle.net/10356/39719
• Institution: Nanyang Technological University

In this report, the robust scheduling problem for heterogeneous architectures is de ned and discussed. This problem is compared to the classic makespan minimization prob- lem. Two di erent methods, a static heuristic and a dynamic rescheduling algorithm are proposed to solve this problem. The static heuristic is based on the minimizing the longest path through a scheduled node. The results show that the static heuristic is not only e ective in solving the robust scheduling problem but also the makespan minimization problem. To our knowledge, no heuristic in literature has been designed to address the robust scheduling problem, although studies have been done to compare the robustness of current heuristics. The dynamic rescheduling algorithm improves on any existing static list-scheduling heuris- tic by utilizing additional information obtained during runtime to improve on the robust- ness of the schedule. A number of schemes controlling the rescheduling are proposed. The results show that dynamic rescheduling is able to signi cantly improve the robustness of a static heuristic. The di erent schemes for rescheduling are also compared. These algorithms are compared against existing solutions in literature using both ran- domly generated graphs and modi ed standard benchmark graphs for the homogeneous scheduling problem.