以演算法的角度探討多核相依系統調速之能耗最佳化問題

An Algorithmic Study on Energy-Minimizing Coherent Speed Scaling

羅倫斯(Ren-Ce Luo)

指導教授 ： 李德財

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201601913

摘要

在這份論文裡，我們在多核工作排程的模型下，考慮使所有核心的總消耗能量最小化的問題。

在此模型下，我們假設排程必須對於各個核心是相依(coherent)的，這代表在任意時間，所有核心的速度值必須相等；在符合此條件的前提下，我們可以任意調整核心的速度值。而能量的單位時間消耗是由一個速度的凸函數所決定。另外，我們假設每個工作事先皆已分別被指派給某一個核心並只能在該核心上被執行。一個可行的排程表必須保證所有的工作皆須在其到達時間和最後完成時間之中被執行完畢。

這個模型的情境是源於電壓島(voltage island)，在多核系統中，所有核心會被分群成數個島，而在同個島上的核心因為共用同一電壓源，故會受到相依的條件限制。我們藉由相依調速的設定來研究電壓島的情境，並計算出在最小化
核心的總消耗能量的前提下，各個島上的核心應當運作的速度。

關鍵字

相依系統調速問題 ； 電壓島 ； 多核心工作排程 ； 耗能最小化 ； 凸函數

並列摘要

In this thesis, we consider a model of multi-core job scheduling aimed at minimizing the energy consumption of the processors.

In this model, schedules with coherent speed scaling are assumed, which means that the speed of the processors can be adjusted as often as needed under the constraint that the speed of all processors must be identical at any time. The energy consumed per unit of time is a convex function of the processing speed. A feasible schedule requires that each job be executed between its arrival time and deadline on a processor to which the job is pre-assigned, possibly with preemption but without migration.

This model originates from the scenario of “voltage-islands” in a many-core system where there are multiprocessors, and the processors are clustered into islands such that the processors in an island are powered using a common voltage line, thereby restricting the processing speeds of the processors in the island. We study this model with coherent speed scaling and compute the speeds of the processors in each island such that the energy consumed is to be minimized.

並列關鍵字

coherent speed scaling ； voltage-island ； multi-core job scheduling ； energy minimization ； convex function

參考文獻

Nikhil Bansal, Tracy Kimbrel, and Kirk Pruhs. Speed scaling to manage energy and temperature. J. ACM, 54(1):3:1–3:39, March 2007.

M. Li, A. Yao, and F. Yao. Discrete and continuous min-energy schedules for variable voltage processors. In Proceedings of the National Academy of Sciences USA. Vol. 103. 39833987

Weiwei Wu, Minming Li and Enhong Chen. Min-Energy scheduling for aligned jobs in accelerate Model. Theoretical Computer Science 412(12-14): 1122-1139, March 2011.

M. Li, B. Liu., and F. Yao. Min-energy voltage allocation for tree structured tasks. Min-energy voltage allocation for tree-structured tasks. Journal of Combinatorial Optimization. 11(3): 305-319, 2006.

F. Yao, A. Demers, and S. Shenker. A scheduling model for reduced cpu energy. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS ’95, pages 374-382, Washington, DC, USA, 1995. IEEE Computer Society.