Energy-Aware Task Scheduling on Heterogeneous Computing Systems With Time Constraint

Abstract

As a technique to help achieve high performance in parallel and distributed heterogeneous computing systems, task scheduling has attracted considerable interest. In this paper, we propose an effective Cuckoo Search algorithm based on Gaussian random walk and Adaptive discovery probability which combined with a cost-to-time ratio Modification strategy (GACSM), to address task scheduling on heterogeneous multiprocessor systems using Dynamic Voltage and Frequency Scaling (DVFS). First, to overcome the shortcomings of poor performance in exploitation of the cuckoo search algorithm, we use chaos variables to initialize populations to maintain the population diversity, a Gaussian random walk strategy to balance the exploration and exploitation capabilities of the algorithm, and an adaptive discovery probability strategy to improve population diversity. Then, we apply the improved Cuckoo Search (CS) algorithm to assign tasks to resources, and a widely used downward rank heuristic strategy to find the corresponding scheduling sequence. Finally, we apply a cost-to-time ratio improvement strategy to further improve the performance of the improved CS algorithm. Extensive experiments are conducted to evaluate the effectiveness and efficiency of our method. The results validate our approach and show its superiority in comparison with the state-of-the-art methods.

Keywords

• Task scheduling
• DVFS
• cuckoo search algorithm
• heterogeneous multiprocessor system