臺灣博碩士論文加值系統

隨著數位無線多媒體的發展，嵌入式視訊編碼技術已被廣泛應用在3C 產品，
在低成本與高效能的考慮之下。由於系統在播放MPEG 影像時，一般使用者所
要求的效果是每秒能夠播放數張畫面(frame)，觀看時才不會有延遲性，然而，因
為畫面資料的多寡與編碼將影響處理時間，如果以最長執行時間作可排程測試雖
然可以保證系統的服務質量(Quality of Service)，但是卻可能讓系統有較高的消耗
電能，如何試圖降低總消耗電能，就變成需要解決的問題。本篇論文中，我們提
出一個基於EDF 的即時排程演算法並建構在多幀任務模型中，並且我們利用動
態電壓調節(DVS)技術，提出考量消耗電能EDF 排程演算法對多幀任務排程來降
低總電能消耗。最後以實驗的方式來此證實此方法並且得到不錯的結果。

An embedded system with a video decoder has become a new trend due to the
applications of mobile multimedia and the consuming electronic products required in
the life. For the considerations of low cost and high efficiency when the embedded
system plays MPEG video, users require a proper quality of service. However, the
amount of encoded data on each frame will affect the processing time. If the
maximum execution times of tasks are used to do schedulability test, the quality of
service of the system can be guaranteed. However, it will result in the higher energy
consumption. It is an important issue to reduce total energy consumption. In this
thesis, we propose an EDF-based real-time scheduling algorithm with considering
energy consumption for the multiframe task model. A simulation model is built to
investigate the performance of the proposed approach. The capability of the proposed
approach is evaluated by a series of simulations, for which we have encouraging
results.

中文摘要i
英文摘要ii
致謝iii
1 導論4
1.1 前言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 相關研究. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 全文架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 任務模型與處理器模型8
2.1 任務模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 處理器模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 問題定義. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 MF 任務省電排程演算法12
3.1 EDF 可排程測試. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 利用傳統EDF 排程機制對MF 任務排程. . . . . . . . . . . . . . . . . . 14
3.3 利用考量消耗電能EDF 排程演算法對MF 任務排程. . . . . . . . . . . . 16
4 效能評估20
4.1 實驗相關設定. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 實驗結果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5 結論32
Bibliography 34

[1] T.P. Baker. Multiprocessor edf and deadline monotonic schedulability analysis. In
Proceedings of the 24th IEEE International Real-Time Systems Symposium, pages
120–129, December 2003.
[2] T.P. Baker. Comparison of empirical success rates of global vs. partitioned fixedpriority
and edf scheduling for hard real time. Technical report, School of Information
Science, Computer and Electrical Engineering (IDE), Halmstad University,
July 2005.
[3] J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson, and S. Baruah. A
categorization of real-time multiprocessor scheduling problems and algorithms. In
Handbook on Scheduling Algorithms, Methods, and Methods, pages 30.1–30.19.
2004.
[4] J.-J. Chen and T.-W. Kuo. Procrastination determination for periodic real-time
tasks in leakage-aware dynamic voltage scaling systems. In Computer-Aided Design,
2007. ICCAD 2007. IEEE/ACM International Conference on, pages 635–645, 2007.
[5] A. Chilambuchelvan, S. Saravanan, and J.R.P. Perinbam. Performance analysis
of dvs algorithms for reducing processor energy consumption. In In Proceedings
of the 2007 International Conference Computational Intelligence and Multimedia
Applications, page 174–178, December 2007.
[6] K. Funaoka, A. Takeda, S. Kato, and N. Yamasaki. Dynamic voltage and frequency
scaling for optimal real-time scheduling on multiprocessors. In SIES’08, pages 27–
33, 2008.
[7] Intel. Xscale microarchitecture. In http://developer.intel.com/design/xscale.
[8] T.-W. Kuo, J.-J. Chen, and Chuan-Yue Yang. Energy-efficiency for multiframe realtime
tasks on a dynamic voltage scaling processor. In CODES+ISSS ’09 Proceedings
of the 7th IEEE/ACM international conference on Hardware/software codesign and
system synthesis, pages 211–220, October 2009.
[9] C.L. Liu and J.W. Layland. Scheduling algorithms for multiprogramming in a hardreal-
time environment. Journal of the ACM, 20(1):46–61, January 1973.
[10] J. Liu and E.A. Lee. Timed mutitasking for real-time embedded software. IEEE
Control System Magazine, 23(1):65–75, February 2003.
[11] J.R. Lorch and A.J. Smith. Improving dynamic voltage scaling algorithms with pace.
In Proceedings of the 2001 ACM SIGMETRICS Conference, pages 50–61, June 2001.
[12] J.R. Lorch and A.J. Smith. Pace: a new approach to dynamic voltage scaling. IEEE
Transactions on Computers, 53(7):856–869, July 2004.
[13] W.-C. Lu, K.-J. Lin, H.-W. Wei, and W.-K. Shih. New schedulability conditions for
real-time multiframe tasks. In Real-Time Systems 2007. ECRTS ’07. 19th Euromicro
Conference on, page 46–61, July 2007.
[14] T.L. Martin and D.P. Siewiorek. The impact of battery capacity and memory bandwidth
on cpu speed-setting: a case study. In Proceedings of the 1999 International
Symposium Low Power Electronics and Design, page 200–205, August 1999.
[15] A.K. Mok and D. Chen. A multiframe model for real-time tasks. In Proceedings of
the 17th Real-Time Systems Symposium, pages 22–29, December 1996.
[16] A.K. Mok and D. Chen. A multiframe model for real-time tasks. In IEEE Transactions
on Software Engineering, pages 635–645, October 1997.
[17] P. Pillai and K.G. Shin. Real-time dynamic voltage scaling for low-power embedded
operating systems. In Proceedings of the 18th Symposium on Operating Systems
Principles (SOSP 2001), page 89–102, December 2001.
[18] S. Gorinsky S.K. Baruah, D. Chen and A.K. Mok. Generalized multiframe tasks.
Real-Time Systems: The International Journal of Time-Critical Computing, 17(1):
5–22, 1999.
[19] Y. Tan and V. Mooney. Timing analysis for preemptive multi-tasking real-time
systems with caches. In Proceedings of Design, Automation and Test in Europe,
pages 1034–1039, February.
[20] T. Wiegand, G.J. Sullivan, G. Bjontegaard, and A. Luthra. Overview of the h.264/
avc video coding standard. IEEE Transactions on Circuits and Systems for Video
Technology, 13(7):560–576, July 2003.