可獨立動態調整時脈之異質多核系統上的節能批次工作排程

Energy-efficient Batch Task Scheduling for Heterogeneous Multi-core Platforms with per-core DVFS

許祐程(You-Cheng Syu)

指導教授 ： 劉邦鋒

共同指導教授 ： 吳真貞(Jan-Jan Wu)

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2015年)

https://doi.org/10.6342/NTU.2015.11301

摘要

節能排程在行動裝置以及資料中心等應用領域上都是相當重要的議題。
現代的多核心處理器可以支援獨立動態調整時脈，
這樣的機制讓我們能夠訂定出既省電又高效能的排程計畫。

為了在多核心平台上達到省電的目的，我們提出了一個批次工作的排成演算法，
能夠找出最佳的排程計畫以最小化耗電量以及總處理時間的和。
這個演算法建立在兩個關鍵上。
首先我們證明一個工作要用什麼樣的頻率來執行只跟排在它後面的工作數量有關。
再來我們提出了一個線性時間的演算法能夠建出一個能決定一個工作該用什麼樣頻率
來執行的表格。
有了這兩項我們的排程演算法就能夠排出能使總成本最小的排程計畫。

關鍵字

省電 ； 節能 ； 排程 ； 多核 ； 動態電壓調節 ； 動態時脈調節 ； 處理時間 ； 迴轉時間

並列摘要

Energy-efficient scheduling is a fundamental issue in many application
domains, such as energy conservation for mobile devices and the
operation of green computing data centers. Modern multi-core
processors support dynamic voltage and frequency scaling (DVFS) on a
per-core basis. That is, the CPU can adjust the power consumption and
frequency of each core individually. This flexibility provide a
feasible mechanism for a schedule to adjust the speed of individual
cores so that the applications can run in the optimal speed in terms
of both performance and energy conservation.

To conserve energy in multi-core platforms, we propose a batch task
scheduling algorithm, which can find an optimal schedule that minimize
the weighted sum of energy consumption and the total turnaround time
of tasks where the sizes of tasks are known in advance. This
algorithm is based on two key ideas. First, we show that the best
frequency to run a task on a core only depends on the number of tasks
that run before it in this core. Second, we can build a table that
helps determine the frequency when the number of tasks behind it
is given in linear time, i.e., linear in the number of available
frequencies. With the help of these two key ideas our scheduling
algorithm can assign tasks to cores so that the total cost is
minimized.

並列關鍵字

Energy-efficient ； Scheduling ； Multi-core ； DVFS ； Turnaround time ； Flow time

參考文獻

communication review, 39(1):68–73, 2008.

[2] Daniel Hackenberg, Robert Schöne, Thomas Ilsche, Daniel Molka, Joseph

Schuchart, and Robin Geyer. An energy efficiency feature survey of the intel haswell

[4] Enhanced Intel. Speedstep® technology for the intel® pentium® m processor, 2004.

[5] Takayasu Sakurai et al. Alpha-power law mosfet model and its applications to cmos