Improving Execution Time of Scheduling Tasks onto Dynamically Reconfigurable Hardware Using Adapted SA
Current reconfigurable systems suffer from a significant overhead due to the time it takes to reconfigure their hardware. In order to deal with this overhead, it is important to develop scheduling algorithms to minimize the execution time of a set of dependent tasks in a dynamically reconfigurable hardware. Many heuristic methods exist which find suboptimal schedules for multiprocessor systems but for dynamically reconfigurable devices it is more complicated to find such schedules because there are configurations other than tasks that need to be scheduled. Evolutionary Algorithms have demonstrated considerable success in providing efficient solutions to many NP-hard optimization problems. With some changes on SA, in this study, we made it fit the problem of task scheduling on reconfigurable systems. These changes were mainly applied on cooling schedule and the way new solutions are generated. To prove the efficiency of the proposed method we compared it with GA and list scheduler and the exhaustive search method was taken as a criterion. The performance of these methods is validated using a number of random task graphs. Experimental results show that GA, our method and list schedulers average error in comparison with Exhaustive Search are 3.1％, 3.3％ and 20.1％ respectively and as the execution time point of view;our method is 32 times quicker than the GA. So the proposed method is favorably comparable to GA but considerably faster.
genetic algorithm reconfigurable systems scheduling simulated annealing list scheduling
Morteza Mollajafari Hadi Shahriar Shahhoseini
Electrical Engineering Department Iran University of Science and Technology Tehran, Iran
国际会议
太原
英文
28-33
2011-02-26（万方平台首次上网日期，不代表论文的发表时间）