臺灣博碩士論文加值系統

目前市面上消費性電子的趨向，已經有越來越多的配備與裝置從單核心處理器發展至多核心處理器，原因不外乎就是看重多核心處理器的運算能力以及即時運算的優點。未來的多媒體應用傾向採用極為複雜的演算法來處理大量資料，純軟體解決方案可以因應多樣化的多媒體標準。
能源管理一直都是嵌入式系統研究的重點，尤其目前大多數的嵌入式系統的電力來源都以電池為主，好的能源管理方案可以有效的大幅提昇系統續航力和效能。在本篇論文中，我們研究多核心嵌入式系統即時排班配置問題，排程規劃須考慮每筆資料之優先執行順序。實驗結果顯示我們的方法在週期性即時系統以及非週期性即時系統下，不管是套用Intel Q6600 或是Intel XScale 的電源模組，都可以大幅減少能源消耗。

Power management is always an emphasis for embedded real-time systems. In order
to achieve real time performance and low energy consumption, low power scheduling
becomes a critical issue.
In this thesis, we propose a low power scheduling algorithm in multiprocessor
real-time systems. Our algorithm adjusted the frequency based on the slack time and the deadlines for two consecutive jobs. Simulation results show that our algorithm can reduce power consumption 7% ~ 12%(30%~50%) in periodic(aperiodic) real-time systems.

摘要 i
Abstract ii
目 錄 iii
表目錄 v
圖目錄 vi
第一章 緒論.................................................................................................................. 1
1.1 研究背景與動機........................................................................................... 1
1.2 論文架構....................................................................................................... 3
第二章 文獻探討.......................................................................................................... 4
2.1 即時系統模型............................................................................................... 4
2.2 電源功率模型............................................................................................... 5
2.3 動態電壓管理............................................................................................... 7
2.4 可靠性........................................................................................................... 7
2.5 相關研究....................................................................................................... 8
第三章 問題描述.......................................................................................................... 9
3.1. 參數定義..................................................................................................... 10
3.2. 效能評估..................................................................................................... 11
3.2.1 Task-Level & Job-Level .................................................................... 11
3.2.2 多核心系統......................................................................................... 12
3.2.3 電源模組............................................................................................. 14
3.2.4 錯誤回復機制..................................................................................... 15
3.3. 排程演算法................................................................................................. 17
3.3.1 Greedy................................................................................................. 19
3.3.2 RA-DPM............................................................................................. 25
3.3.3 SATSS ................................................................................................. 31
第四章 研究方法........................................................................................................ 35
4.1 Proposed algorithm................................................................................... 35
4.2 演算法分析................................................................................................. 39
第五章 模擬實驗........................................................................................................ 44
5.1 模擬環境..................................................................................................... 44
5.2 週期性即時工作模擬結果分析................................................................. 45
5.2.1 Intel Q6600 電源模組........................................................................ 45
5.2.2 Intel XScale 電源模組....................................................................... 47
5.3 非週期性即時工作模擬結果分析............................................................. 48
5.3.1 Intel Q6600 電源模組........................................................................ 49
5.3.2 Intel XScale 電源模組....................................................................... 50
iv
第六章 結論................................................................................................................ 52
參考文獻 54

[1] Intel XScale Technology and Processors, http://developer.intel.com/design/intelxscale/,
2008.
[2] Intel Corporation, Enhanced Intel SpeedStep Technology for the Intel Pentium M Processor, http://www.intel.com/design/intarch/papers/301174.htm, March 2004.
[3] H. Aydin, V. Devadas and D. Zhu, “System-Level Energy Management for Periodic Real-Time Tasks,” In Proc. of the 27th IEEE Real-Time Systems Symp. (RTSS), pp. 313-322, Dec. 2006.
[4] H. Aydin, R. Melhem, D. Mosse’ and P. Mejia-Alvarez, “Dynamic and aggressive
scheduling techniques for power-aware real-time systems,” In Proc. of the 22th IEEE Real-Time Systems Symposium, Dec. 2001.
[5] H. Aydin, R. Melhem, D. Mosse’ and P. Mejia-Alvarez, “Power-Aware Scheduling for Periodic Real-Time Tasks,” IEEE Transactions on Computers, vol. 53, no. 5, pp.584-600, May. 2004
[6] N. Bansal, T. Kimbrel and K. Pruhs, “Dynamic speed scaling to manage energy and temperature,” In Proc. of the Symposium on Foundations of Computer Science, Oct.2004
[7] V. Berten, C.J. Chang and T.W. Kuo, “Discrete Frequency Selection of Frame-Based Stochastic Real-Time Tasks,” In Proc. of the 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pp. 269-278, 2008
[8] M. Caccamo, G. Buttazzo and L. Sha, “Capacity Sharing for Overrun Control,” Proc. Real-Time Systems Symp. (RTSS), pp. 295-304, 2000.
[9] J. J. Chen and T. W. Kuo, “Multiprocessor Energy-Efficient Scheduling for Real-Time Tasks with Different Power Characteristics,” In Proc. of the International Conference on Parallel Processing (ICPP'05), pp. 13-20, June 2005.
[10] J. J. Chen and T.W. Kuo, “Procrastination determination for periodic real-time tasks in leakage-aware dynamic voltage scaling systems,” In Proc. of the IEEE/ACM 55 international conference on Computer-aided design, pp. 289-294, 2007.
[11] K. Y. Chen, A. Liu and C. H. L. Lee, ”A Multiprocessor Real-Time Process
Scheduling Method,” In Proc. of the IEEE Fifth International Symposium on
Multimedia Software Engineering (ISMSE'03), pp. 29-36, Dec. 2003
[12] F. M. David, J. C. Carlyle and R. H. Campbell, “Context Switch Overheads for Linux on ARM Platforms,” In Proc. of the Workshop on Experimental Computer Science, 2007.
[13] E. Elnozahy, R. Melhem and D. Mosse’, “Energy-Efficient Duplex and TMR
Real-Time Systems,” In Proc. of the 23rd IEEE Real-Time Systems Symposium, pp.
256-265, Dec. 2002.
[14] J. Goossens, S. Funk and S. Baruah, “Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors,” Real-Time Systems, vol. 25, no. 2-3, pp.187-205, Sep. 2003
[15] M. K. Huang, J. M. Chang and W. M. Chen, “Grouping-Based Dynamic Power
Management for Multi-threaded Programs in Chip-Multiprocessors,” In Proc. of the
2009 International Conference on Computational Science and Engineering, pp. 56-63, 2009
[16] S. Irani, S. Shukla and R. Gupta, “Algorithms for power savings,” ACM Transactions on Algorithms (TALG), vol. 3, no. 4, Nov. 2007
[17] J. Leung and J. Whitehead, “On the complexity of fixed-priority scheduling of periodic, real-time tasks,” Performance Evaluation, vol. 2, no. 4, pp.237-250, Dec. 1982
[18] P. Mej’ıa-Alvarez, E. Levner and D. Moss’e, “Adaptive scheduling server for
power-aware real-time tasks,” ACM Transactions on Embedded Computing Systems,
vol. 3, no. 2, pp.284-306, 2004
[19] D. Moss’e, H. Aydin, B. R. Childers and R. Melhem, “Compiler assisted dynamic power-aware scheduling for real-time applications,” In Proc. of the Workshop on 56 Compiler and OS for Low Power, Oct. 2000.
[20] P. Pillai and K.G. Shin, “Real-Time Dynamic Voltage Scaling for Low-Power
Embedded Operating Systems,” In Proc. of the eighteenth ACM symposium on
Operating systems principles, pp. 89-102, Oct. 2001.
[21] D.K. Pradhan, Fault Tolerance Computing: Theory and Techniques, Prentice-Hall, 1986
[22] C. Scordino and G. Lipari, “A Resource Reservation Algorithm for Power-Aware Scheduling of Periodic and Aperiodic Real-Time Tasks,” IEEE Transactions on Computers, vol. 55, no. 12, pp. 1509-1522, Dec. 2006
[23] B. Sprunt, L. Sha and J. P. Lehoczky, “Aperiodic Task Scheduling for Hard Real-Time Systems,” The Journal of Real-Time Systems, vol.1, no.1, pp. 27–60, June 1989.
[24] M. Weiser, B. Welch, A. Demers and S. Shenker, “Scheduling for Reduced CPU
Energy,” In Proc. of the 1st USENIX conference on Operating Systems Design and
Implementation, Nov. 1994.
[25] F. Yao, A. Demers and S. Shenker, “A Scheduling Model for Reduced CPU Energy,” In Proc. of the 36th Annual Symposium on Foundations of Computer Science, pp. 374-382, Oct. 1995.
[26] J. Y. Yin and G. C. Guo, “An Algorithm for Scheduling Aperiodic Real-Time Tasks on a Static Schedule,” In Proc. of the 2009 Second International Conference on Information and Computing Science, vol. 1, pp. 70-74, May 2009
[27] Y. Zhang, K. Chakrabarty and V. Swaminathan, “Energy-Aware Fault Tolerance in Fixed-Priority Real-Time Embedded Systems,” In Proc. of the 2003 IEEE/ACM
international conference on Computer-aided design, pp. 209, Nov. 2003.
[28] D. Zhu and H. Aydin, “Reliability-Aware Energy Management for Periodic Real-Time Tasks,” IEEE Transactions on Computers, vol. 58, no. 10, Oct. 2009