Memory Sleep-Aware Task Allocation and Scheduling Algorithm Design for Energy Efficiency

Abstract

Nowadays memory energy reduction attracts significant attention as main memory consumes large amount of energy among all the energy consuming components. With the memory chips being larger and denser with smaller technology scales, the static power (standby power) occupies more significant portion among the overall memory energy consumption. To reduce the static power, a conventional way is to put the memory into low-power modes when it is not used. In this thesis, we explore memory power management schemes with considering the interactions of memory and other components such as multi-core processor and the heterogenous memory systems. The major work is outlined as follows.

Firstly, we study the hybrid PRAM and DRAM memory architectures, which combines the advantages of DRAM and PRAM, such as low leakage power in PRAM and short write latency in DRAM. We explore the leakage power reduction of DRAM in hybrid memories by partitioning variables to DRAM/PRAM properly and turning DRAM into sleep state when it is idle. A novel proximity concept is proposed to guide the variable partitioning to maximize the possibility of turning DRAM into sleep mode. Based on the concept, a Sleep-Aware Variable Partition Algorithm (SAVPA) is then proposed with the objective of maximizing the sleep time of DRAM while satisfying the performance and endurance constraints. The experiment results show that SAVPA reduces the energy consumption by 11.25% in average (up to 15.84%) compared to the state-of-art work with simple sleep technique.

Secondly, we focus on reducing the energy consumption of the shared main memory in multi-core processors by putting the memory into sleep state when all cores are idle. Based on this idea, we present systematic analysis of different models and propose a series of scheduling schemes to maximize the common idle time of all cores. The target problem is classified into two cases based on whether task migration is allowed or not among cores. Considering task migration, an optimal scheduling scheme is proposed assuming the number of cores is unbounded. When the number of cores is bounded, an ILP formulation and two efficient heuristic algorithms are proposed. When task migration is not allowed, we first prove the NP-hardness of the problem, and then propose the optimal solutions when task partitions are given in advance. The energy overhead caused by transitions between active and sleep modes of the memory is analyzed. The experimental results show that the heuristic algorithms work efficiently and can save 7.25% and 11.71% system energy respectively with 1GB memory, compared to an energy-efficient multi-core scheduling scheme. Larger energy reduction can be further achieved with larger size of memory.

Thirdly, based on a similar system given in the second item, we explore the system-wide energy minimization. Now the multi-core processor can apply DVS on each core while the shared memory can be turned into sleep when no core is accessing it to minimize the energy cost of both processor and memory. Systematic analyses are presented for different system models and task models. For tasks with common release time, optimal schemes are presented for the systems both with and without considering the static power of the cores. For agreeable deadline tasks, different Dynamic Programming-based optimal solutions are proposed for negligible and non-negligible static power of cores. For the general task model, we propose a heuristic online algorithm. Furthermore, the scheme is extended to handle the problem when the transition overhead between the active and sleep modes is considered. The optimality of the proposed schemes for common release time and agreeable deadline tasks are proved. The validity of the proposed heuristic scheme is evaluated through experiments. Experimental results confirm the superiority of the heuristic scheme in terms of the energy saving improvement compared to the most related existing work.

Finally, we explore the memory system energy efficiency for a general multi-core architecture, which integrates a local memory in each processing core, with a large off-chip memory shared among multiple cores. Decisions need to be made on whether tasks will be executed with the shared memory or the local memory to minimize the total energy consumption within real-time constraints. Towards this problem, we propose optimal schemes as well as a polynomial-time approximation algorithm with constant ratio. The complexity analysis of the problem for different task and system models is also presented. Experimental results show that the proposed approximation algorithm performs close to the optimal solution in average.

Date of Award	19 Jan 2017
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chun Jason XUE (Supervisor)