%0 Conference Paper
%B Application-Specific Systems, Architecture Processors, 2005. ASAP 2005. 16th IEEE International Conference on
%D 2005
%T CASPER: an integrated energy-driven approach for task graph scheduling on distributed embedded systems
%A Kianzad,V.
%A Bhattacharyya, Shuvra S.
%A Gang Qu
%K CASPER
%K combined-assignment-scheduling-and-power-management
%K computational complexity
%K distributed system
%K dynamic voltage scaling
%K embedded systems
%K energy reduction
%K genetic algorithm
%K Genetic algorithms
%K graph theory
%K homogeneous multiprocessor system
%K maximal energy saving
%K Multiprocessing systems
%K multiprocessor embedded system
%K optimization loop
%K power management
%K power variation
%K Processor scheduling
%K slack distribution algorithm
%K task assignment
%K task graph scheduling
%X For multiprocessor embedded systems, the dynamic voltage scaling (DVS) technique can be applied to scheduled applications for energy reduction. DVS utilizes slack in the schedule to slow down processes and save energy. Therefore, it is generally believed that the maximal energy saving is achieved on a schedule with the minimum makespan (maximal slack). Most current approaches treat task assignment, scheduling, and DVS separately. In this paper, we present a framework called CASPER (combined assignment, scheduling, and power-management) that challenges this common belief by integrating task scheduling and DVS under a single iterative optimization loop via genetic algorithm. We have conducted extensive experiments to validate the energy efficiency of CASPER. For homogeneous multiprocessor systems (in which all processors are of the same type), we consider a recently proposed slack distribution algorithm (PDP-SPM) by S. Hua and G. Qu (2005): applying PDP-SPM on the schedule with the minimal makespan gives an average of 53.8% energy saving; CASPER finds schedules with slightly larger makespan but a 57.3% energy saving, a 7.8% improvement. For heterogeneous systems, we consider the power variation DVS (PV-DVS) algorithm by Schmitz et al. (2004), CASPER improves its energy efficiency by 8.2%. Finally, our results also show that the proposed single loop CASPER framework saves 23.3% more energy over GMA+EE-GLSA by Schmitz et al. (2002), the only other known integrated approach with a nested loop that combines scheduling and power management in the inner loop but leaves assignment in the outer loop.
%B Application-Specific Systems, Architecture Processors, 2005. ASAP 2005. 16th IEEE International Conference on
%P 191 - 197
%8 2005/07//
%G eng
%R 10.1109/ASAP.2005.23