Ant-Colony Optimization Based Algorithm for Energy-Efficient Scheduling on Dynamically Reconfigurable Systems

摘要

Dynamically reconfigurable systems such as FPGA have become widely used in numerous application fields for their high performance, low cost, flexibility and reconfigurablity on the fly. Energy reduction is growing importance of system design. This paper studies the crucial problem of energy-efficiency scheduling on dynamically reconfigurable systems. Several challenges have to be addressed, such as transformable tasks, integral allocation, reconfiguration overhead, exclusive reconfiguration at one time, and energy minimization with deadline constraints. To address these challenges, we propose a two-phase algorithm for energy efficient scheduling on dynamically reconfigurable systems. First, the algorithm determines the feasible task placement with a minimum makespan satisfying the deadline constraints. Due to the NP-Complete nature of this placement problem, we propose an efficient ant colony optimization (ACO) based algorithm with low computational complexity. Second, we propose two greedy algorithms that dynamically adjust speed levels and minimize the overall power dissipation with all tasks finished before deadlines. We developed comprehensive trace-driven simulation experiments to evaluate our algorithm and results show that our energy-efficient scheduling algorithm successfully process all tasks without violating deadline requirements and lower system power consumption by as high as 25%.