跳到主要內容

臺灣博碩士論文加值系統

(34.226.244.254) 您好!臺灣時間:2021/08/02 22:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:許祐程
研究生(外文):You-Cheng Syu
論文名稱:可獨立動態調整時脈之異質多核系統上的節能批次工作排程
論文名稱(外文):Energy-efficient Batch Task Scheduling for Heterogeneous Multi-core Platforms with per-core DVFS
指導教授:劉邦鋒
指導教授(外文):Pangfeng Liu
口試委員:施吉昇
口試委員(外文):Chi-Sheng Shih
口試日期:2015-07-24
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊網路與多媒體研究所
學門:電算機學門
學類:網路學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:23
中文關鍵詞:省電節能排程多核動態電壓調節動態時脈調節處理時間迴轉時間
外文關鍵詞:Energy-efficientSchedulingMulti-coreDVFSTurnaround timeFlow time
相關次數:
  • 被引用被引用:0
  • 點閱點閱:102
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
節能排程在行動裝置以及資料中心等應用領域上都是相當重要的議題。
現代的多核心處理器可以支援獨立動態調整時脈,
這樣的機制讓我們能夠訂定出既省電又高效能的排程計畫。

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

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.

Acknowledgement 2
Chinese Abstract 3
Abstract 4
Contents 5
List of Figures 7
List of Tables 8
1 Introduction 1
2 Related Work 6
3 Model 8
3.1 Task Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 CPU Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4 Scheduling
4.1
4.2
10
Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.1.1 Local Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.1.2 Global Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2.1 12
Local Schedule Optimization . . . . . . . . . . . . . . . . . . . .
54.2.2 Global Schedule Optimization . . . . . . . . . . . . . . . . . . . 14
4.2.3 Efficient Cost Coefficient Computation . . . . . . . . . . . . . . 17
4.2.4 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Conclusion 21
Bibliography 22

[1] Albert Greenberg, James Hamilton, David A Maltz, and Parveen Patel. The cost
of a cloud: research problems in data center networks. ACM SIGCOMM computer
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
processor. 2015.
[3] ARM Peter Greenhalgh. Big. little processing with arm cortex-a15 & cortex-a7,
2013.
[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
inverter delay and other formulas. Solid-State Circuits, IEEE Journal of, 25(2):584–
594, 1990.
[6] David M Brooks, Pradip Bose, Stanley E Schuster, Hans Jacobson, Prabhakar N
Kudva, Alper Buyuktosunoglu, John-David Wellman, Victor Zyuban, Manish
Gupta, and Peter W Cook. Power-aware microarchitecture: Design and modeling
challenges for next-generation microprocessors. Micro, IEEE, 20(6):26–44, 2000.
[7] Frances Yao, Alan Demers, and Scott Shenker. A scheduling model for reduced
cpu energy. In Foundations of Computer Science, 1995. Proceedings., 36th Annual
Symposium on, pages 374–382. IEEE, 1995.
22[8] Nikhil Bansal, Ho-Leung Chan, and Kirk Pruhs. Speed scaling with an arbitrary
power function. ACM Transactions on Algorithms (TALG), 9(2):18, 2013.
[9] Padmanabhan Pillai and Kang G Shin. Real-time dynamic voltage scaling for low-
power embedded operating systems. In ACM SIGOPS Operating Systems Review,
volume 35, pages 89–102. ACM, 2001.
[10] David P Bunde.
Power-aware scheduling for makespan and flow.
Journal of
Scheduling, 12(5):489–500, 2009.
[11] Kirk Pruhs, Patchrawat Uthaisombut, and Gerhard Woeginger. Getting the best re-
sponse for your erg. ACM Transactions on Algorithms (TALG), 4(3):38, 2008.
[12] Jian-Jia Chen, Kazuo Iwama, Tei-Wei Kuo, and Hseuh-I Lu. Flow time minimization
under energy constraints. In Design Automation Conference, 2007. ASP-DAC’07.
Asia and South Pacific, pages 866–871. IEEE, 2007.
[13] Susanne Albers and Hiroshi Fujiwara. Energy-efficient algorithms for flow time
minimization. ACM Transactions on Algorithms (TALG), 3(4):49, 2007.
[14] Nikhil Bansal, Ho-Leung Chan, Tak-Wah Lam, and Lap-Kei Lee. Scheduling for
speed bounded processors. In Automata, Languages and Programming, pages 409–
420. Springer, 2008.
[15] Tak-Wah Lam, Lap-Kei Lee, Isaac KK To, and Prudence WH Wong. Nonmigratory
multiprocessor scheduling for response time and energy. Parallel and Distributed
Systems, IEEE Transactions on, 19(11):1527–1539, 2008.
[16] Tak-Wah Lam, Lap-Kei Lee, Isaac KK To, and Prudence WH Wong. Improved
multi-processor scheduling for flow time and energy. Journal of Scheduling, 15(1):
105–116, 2012.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top