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

Abstract

節能排程在行動裝置以及資料中心等應用領域上都是相當重要的議題。 現代的多核心處理器可以支援獨立動態調整時脈， 這樣的機制讓我們能夠訂定出既省電又高效能的排程計畫。 為了在多核心平台上達到省電的目的，我們提出了一個批次工作的排成演算法， 能夠找出最佳的排程計畫以最小化耗電量以及總處理時間的和。 這個演算法建立在兩個關鍵上。 首先我們證明一個工作要用什麼樣的頻率來執行只跟排在它後面的工作數量有關。 再來我們提出了一個線性時間的演算法能夠建出一個能決定一個工作該用什麼樣頻率 來執行的表格。 有了這兩項我們的排程演算法就能夠排出能使總成本最小的排程計畫。

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.