Energy-Aware Task Scheduling for NoC-based Dynamic Voltage Scalable System

本文提出一個新的低耗能排程(energy-aware scheduling)演算法，應用在NoC架構上並使用動態調整電壓來達到省電的效果。在處理器各個核心使用率不高的情況下，透過平行化和動態電壓調整(DVS, dynamic voltage scaling)的技術，以提高各核心使用率來降低功率的消耗。在排程的過程中相較於傳統的方式，我們多考慮了DVS帶來的影響，在減少核心之間的溝通(communication)產生的耗能外也試著去增加執行DVS的機會。在DVS方面把問題轉換成最大點集團(Maximum Weight Clique)問題來解，可以讓DVS的執行更有效率。提出的演算法相較於EAS演算法，可以節省22%的耗能。另外改良過的DVS演算法，相較於PV-DVS演算法，在耗能節省方面有97%的增進。Energy-aware task assignment and scheduling over a many-core network-on-chip (MC-NoC) platform is investigated. For real time applications, time slacks of a preliminary task schedule may be exploited to conserve energy. This can be accomplished by leveraging the dynamic voltage scaling (DVS) technique to slow down clock frequency of certain cores so long as the deadline is met. In this Thesis, the task of fine-tuning an existing task assignment and schedule and using DVS to lower overall energy consumption is formulated as a graph-theoretic maximum weight clique (MWC) problem. An efficient heuristic algorithm is proposed to systematically solve this problem. A unique feature of our approach is concurrently applying DVS to slow down execution of multiple tasks to achieve better energy saving. Extensive simulations are performed to compare this proposed algorithm against leading energy-aware task scheduling algorithm and DVS algorithm. Our algorithm exhibits a 22% more energy saving than the EAS algorithm. As for energy saving in DVS process, our MWC-based method provides a 97% saving improvement over the PV-DVS algorithm.ABSTRACT iIST OF FIGURES vHAPTER 1 INTRODUCTION 1.1 Scheduling Problem on NoC 1.2 Voltage Selection Technique 2.3 Contributions on this Thesis 2.4 Thesis Organization 3HAPTER 2 PRELIMINARIES 5.1 Basic Concept of NoC 5.2 Previous Work 7.2.1 EEGMA 9.2.2 CASPER 11.2.3 ETAHM 11.2.4 The algorithm Zhang et al. proposed 12.2.5 The algorithm Varatkar et al. proposed 13.2.6 EAS 14.3 Problem Description 16HAPTER 3 MOTIVATIONAL EXAMPLE 21HAPTER 4 PROPOSED ALGORITHMIC SOLUTION 25.1 Task Prioritization 26.2 Task Assignment 29.3 Power Optimization 32.4 Re-Scheduling Setup 36.5 Repair Process 37HAPTER 5 EXPERIMENTAL RESULTS 41HAPTER 6 CONCLUSION 47EFERENCE 4