ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2016, Vol. 53 ›› Issue (7): 1503-1516.doi: 10.7544/issn1000-1239.2016.20160137

Special Issue: 2016绿色计算专题

Previous Articles     Next Articles

Energy Optimization Heuristic for Deadline-Constrained Workflows in Heterogeneous Distributed Systems

Jiang Junqiang1,2, Lin Yaping1,2, Xie Guoqi1, Zhang Shiwen1,2   

  1. 1(College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082);2(Key Laboratory for Dependable System and Networks of Hunan Province (Hunan University), Changsha 410082)
  • Online:2016-07-01

Abstract: Most of existing energy optimization heuristics with deadline constraint for workflows in DVFS-enabled heterogeneous distributed systems usually trap in local optima. In this paper, we propose a new energy optimization heuristic called backward frog-leaping global energy conscious scheduling: BFECS. This algorithm makes full use of surplus time between the lowerbound of the workflow and the constrained deadline. Specifically, it starts from the constrained deadline, and leapfrogs towards the lowerbound of the workflow with different leap interval. During the whole process of leapfrogging, the leap intervals are continually changed according to the locally optimal value until the endpoint of leapfrogging is reached; the scheduling sequence with least run energy consumption is also saved at the same time. Furthermore, more energy consumption can be reduced by leveraging slack time reclamation technique, and the idle time slots caused by precedence constraints can be assimilated by the tasks through running at a lower and suitable voltage/frequency using DVFS technique, without violating the precedence constraints of the workflow and breaking the deadline. The experimental results show that the proposed algorithm can decrease energy consumption significantly.

Key words: heterogeneous distributed systems, energy optimization, deadline constraint, workflow, slack time reclamation

CLC Number: