(3.235.25.169) 您好!臺灣時間:2021/04/18 05:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:羅倫斯
研究生(外文):Ren-Ce Luo
論文名稱:以演算法的角度探討多核相依系統調速之能耗最佳化問題
論文名稱(外文):An Algorithmic Study on Energy-Minimizing Coherent Speed Scaling
指導教授:李德財李德財引用關係
口試委員:趙坤茂陳和麟林清池
口試日期:2016-06-28
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電子工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:英文
論文頁數:38
中文關鍵詞:相依系統調速問題電壓島多核心工作排程耗能最小化凸函數
外文關鍵詞:coherent speed scalingvoltage-islandmulti-core job schedulingenergy minimizationconvex function
相關次數:
  • 被引用被引用:0
  • 點閱點閱:59
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在這份論文裡,我們在多核工作排程的模型下,考慮使所有核心的總消耗能量最小化的問題。

在此模型下,我們假設排程必須對於各個核心是相依(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.


口試委員會審定書 i
誌謝 ii
Chinese Abstract iii
English Abstract iv
1 Introduction 1
The Results Obtained in This Thesis 5
2 Notations and Problem Definition 8
3 The Structure of the Optimal Schedules 10
3.1 Sufficient and Necessary Conditions of an Optimal Schedule 10
3.2 Relations Between Jobs 14
3.3 Relations Between Jobs in Different Schedules 16
4 Our Algorithm 19
4.1 The Algorithm 20
4.1.1 The Optimal Substructure 20
4.1.2 Configuration Update after a New Job Arrival 20
4.1.3 Properties and Classification of Events 21
4.2 Proof of Correctness 24
4.3 Running Time Analysis 28
5 The Agreeable Deadline Case 31
Analysis of the Complexity of Events 31
6 Conclusion 35
Future Research Topics 35
Reference 38


List of Figures
Figure 1 A single processor example to illustrate the first type configuration problem 3
Figure 2 A two processor example to illustrate the second type configuration problem 4


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

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.

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.

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.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔