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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳柏瑋
研究生(外文):Bo Wei Chen
論文名稱:雙核心即時系統中節能排程演算法之研究
論文名稱(外文):Energy-Efficient Tasks scheduling Algorithm for Dual-core Real-time Systems
指導教授:謝萬雲謝萬雲引用關係
指導教授(外文):W. Y. Shieh
學位類別:碩士
校院名稱:長庚大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:99
論文頁數:67
中文關鍵詞:雙核心即時系統節能排程演算法線性程式
外文關鍵詞:integer linear programmingenergy-efficient task schedulingdual-core real-time system
相關次數:
  • 被引用被引用:0
  • 點閱點閱:107
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近年來,嵌入式系統裝置已經大量融入我們的生活之中。隨著這些計算裝置的功能需求增加,這些裝置逐漸朝向多核心處理器架構發展來負荷計算上的需求。但是,這些計算裝置隨著處理器核心的數量增加而導致電能的需求更加龐大。因此為了節省電能,這些計算裝置在電能的消耗限制上必須較為嚴苛。隨著動態電壓調整(DVS)電路的技術成熟,這些裝置大部份都會使用動態電壓調整電路來為裝置的效能以及電耗上進行取捨,以達到效能與電耗上的平衡。在本篇研究中,我們針對雙核心即時系統中的工作排程提出兩種有效的排程演算法。我們的目標是降低這些裝置在執行運算時的電能消耗並且維持一定的運算效能。我們所提出的兩種方法分別為針對off-time以及run-time的應用來設計。對於off-time,我們提出一個ILP-model來為工作排程找出最佳解。但是由於ILP-model的運算求解時間過於複雜,不適合運用於run-time的環境上,因此我們針對run-time的應用來設計一套近似最佳解的演算法。實驗結果顯示,我們的近似最佳解演算法與ILP的最佳解演算法在電能節省幅度上,差距大約僅在5%左右。
Real-time embedded devices have been widely used in our daily life. To satisfy the performance requirements, most current designs tend to apply the dual- or multi-core processor architecture in the systems. Such systems, however, usually have low power consumption demands. Therefore the Dynamic Voltage Scaling (DVS) technique has been included in most designs. In this paper, we focus our study on the energy-efficient task scheduling algorithm for the dual-core real-time systems. Our goal is to minimize the system’s energy consumption and maintain the performance of task execution at the same time. To achieve this goal, we propose two approaches for off-time and run-time applications. For the off-time approach, we propose an Integer Linear Programming (ILP) based algorithm to find the optimal scheduling. For the run-time approach, we propose a heuristic algorithm. The experimental results show that the energy consumption can be reduced effectively by the heuristic algorithm, and is close to the optimal bounds obtained by the ILP model.
Figure 1.1 Periodic task schedule result………………………………….3
Figure 1.2 Aperiodic task schedule by ASAP policy……………………..5
Figure 1.3 (a) Aperiodic task scheduling by ASAP policy with DVS at time 0……....………………………………………………………..7
Figure 1.3 (b) Aperiodic task scheduling by ASAP policy with DVS at time 1……………………………………………………………………..7
Figure 1.3 (c) Aperiodic task scheduling by ASAP policy with DVS at time 2………………………………………………………………..……7
Figure 1.3 (d) Aperiodic task scheduling by ASAP policy with DVS of final result……...…………………………………………………....……7
Figure 1.4 (a) Aperiodic task scheduling by special schedule time point at time 0……………………………………..………………………………9
Figure 1.4 (a) Aperiodic task scheduling by special schedule time point at time 2……………………………………………………………………9
Figure 1.4 (a) Aperiodic task scheduling by special schedule time point at time 7…….………………….……………………………………………9
Figure 2.1 (a) Scheduling results by not allowing multiple voltages…...13
Figure 2.1 (b) Scheduling results by allowing multiple voltages…..…...13
Figure 3.1 Architecture model of the System…………………………...19
Figure 4.1 Design flow chart……………………………………………21
Figure 4.2 Example of unique constraints.………………………….….23
Figure 4.3 (a) Two possible overlap case when Mi≧Lj≧Li…………….24
Figure 4.3 (a) Two possible overlap case when Mj≧Li≧Lj…………….24
Figure 4.4 Example of deadline constraints…………………………….25
Figure 4.5 Heuristic algorithm…………………………………………26
Figure 4.6 Example of current core has been allocated free time space..28
- x -
Figure 4.7 The algorithm of DVS_decision…………………………..29
Figure 4.8 Example of workload_density≧α………………………….32
Figure 4.9 (a) Example of workload_density <αwhen choose the core with small free time space first………………………………………….33
Figure 4.9 (b) Example of workload_density <α when choose the core with small free time space first………………………………………….33
Figure 4.9 (c) Example of workload_density <αof Task T5 miss its deadline……………….………………………………………….33
Figure 4.9 (d) Example of workload_density <αof all tasks satisfy its deadlines………………….………………………………………….33
Figure 4.10 The algorithm of Core_decision……………………………34
Figure 5.1 (a) Energy consumption of different α value……………..38
Figure 5.1 (b) Deadline miss rate of different α value……………….38
Figure 5.2 (a) The energy consumption of heuristic algorithm compare with ILP…………………………………………………………………40
Figure 5.2 (b) The deadline miss rate of heuristic algorithm……………40
Figure 5.3 (a) The energy consumption of heuristic algorithm compare with other algorithms……………………………………………………42
Figure 5.3 (b) The deadline miss rate of heuristic algorithm compare with other algorithms…………………………………………………………42
Figure 5.4 Core utilization of heuristic algorithm………………………43
Table 1.1 Periodic task table……………………………………………...3
Table 1.2 Aperiodic task table………………………………………….....5
Table 3.1 Frequency, voltage and power consumption model of the Intel XScale processor………………………………………………18
Table 3.2 Parameters of a DVS System…………………………………20
Table 5.1 Energy consumption of core in different execute speed……..36
[1] AYDIN, H et al., “Dynamic and aggressive scheduling techniques for power-aware real-time systems,” IEEE Real-Time Systems Symposium (RTSS), 95-105, 2001
[2] BURD, T. et al., “Design issues for dynamic voltage scaling,” In Proceedings of International Symposium on Low Power Electronics and Design (ISLPED-00), 9-14, 2000
[3] Euiseong Seo et al., “Energy Efficient Scheduling of Real-Time Tasks on Multicore Processors,” IEEE Transactions on Parallel and Distributed System, Vol.19, No. 11, 1540-1552, 2008
[4] F. YAO et al., “A Scheduling Model for Reduced CPU Energy,” In Proceedings of IEEE Symposium on Foundations of Computer Science, 374-382, 1995.
[5] G. Magklis et al., “Dynamic Frequency and Voltage Scaling for a Multiple-Clock-Domain Microprocessor,” IEEE Micro., Vol.23, 62-68, 2003
[6] G. QUAN et al., “Energy Efficient DVS Scheduling for Fixed-Priority Real-Time Systems,” ACM Transactions on Embedded Computing System, Vol 6, No. 4, Article 29, 2007
[7] T. ISHIHARA et al., “Voltage Scheduling Problem for Dynamically Variable Voltage Processor,” In Proceedings of International Symposium on Low Power Electronic Syste, 197-202, 1998
[8] J. Chen et al., “Energy-Efficient Real-Time Task Scheduling in Multiprocessor DVS System,” Asia and South Pacific Design Automation Conference, 342-349, 2005
[9] J. ZHUO et al., “Energy-Efficient Dynamic Task Scheduling Algorithms for DVS System,” ACM Transactions on Embedded Computing System, Vol 7, Article 17, 2008
[10]J. ZHUO et al., “System-level energy-efficient dynamic task scheduling ,” IEEE Design Automation Conference, 628-631, 2005
[11]J.M. Lopez et al., “Worst-Case Utilization Bound for EDF Scheduling on Real-Time Multiprocessor Systems,” Proc. 12th Euromicro Conf. Real-Time Systems, 25-33, 2000
[12]P. Tan, “Task scheduling of Real-time System Systems on Multi-Core Architectures,” IEEE Computer Society, 190-193, 2009
[13]P. Mohanty, “Peak Power Minimization Through Datapath Scheduling,” IEEE Computer Society Annual Symposium on VLSI,
- 4 8 -
121-126, 2003
[14]P. Mohanty, “Energy-Efficient Datapath Scheduling Using Multiple Voltages and Dynamic Clocking,” ACM Transactions on Embedded Computing System, Vol10, No. 2, 330-353, 2005
[15]R. Jerjurikar et al., “Leakage Aware Dynamic Voltage Scaling for Real-Time Embedded Systems,” Proc. 41st Ann. Technical Conf. Design Automation, 275-280, 2004
[16]S.K. Baruah, “Optimal Utilization Bounds for the Fixed-Priority Scheduling of Periodic Task Systems on Identical Multiprocessors,” IEEE Trans. Computers,Vol.53, 781-784, 2004
[17]W. Shiue, “Low-Power Scheduling with Resource Operating at Multiple Voltages,” IEEE Transactions on Circuits and System, Vol. 47, No 6, 536-543, 2000
[18]W. KWON et al., “Optimal Voltage Allocation Techniques for Dynamically Variable Voltage Processors,” ACM Transactions on Embedded Computing System, Vol 4, 211-230, 2005
[19]X. FEN et al., “Intraprogram Dynamic Voltage Scaling:Bounding Opportunities with Analytic Modeling,” ACM Transactions on Architecture and Code Optimization, Vol. 1, No. 3, 323–367, September 2004
[20]http://www.lindo.com
[21]ROY D. YATES., Probability and stochastic processes, second edition
[22]http://www.sonyericsson.com/cws/products/mobilephones/overview/x
2?lc=zh&cc=tw
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
系統版面圖檔 系統版面圖檔