成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	黃志祥 Huang, Chih-Shung
論文名稱：	運用動態電壓調整實現共用資源之偶發性硬即時工作排程 Scheduling Sporadic, Hard Real-time Tasks with Resources Sharing via Dynamic Voltage Scaling Approach
指導教授：	郭耀煌 Kuo, Yau-Hwang
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2005
畢業學年度：	93
語文別：	英文
論文頁數：	84
中文關鍵詞：	硬即時、偶發性工作、共用資源、工作排程、動態電壓調整、功率節省
外文關鍵詞：	power savings, dynamic voltage scaling, task scheduling, resource-sharing, sporadic task, hard real-time
相關次數：	點閱：149 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

　　當處理器的負載沒有全部滿載的時候，動態電壓調整演算法(dynamic voltage scaling algorithm)可以靠著調低電壓來節省能源，然而對於資源共用的硬即時性工作而言，僅考慮節能因素是無法得到良好的排程，為此本論文將針對同時具有省電(power savings)和任務間同步(task synchronization)的偶發性任務(sporadic tasks)排程問題加以研究，任務間可以共享一組可以重複使用、單一單位的軟體資源(software resource)。並希望能達到的目標為(1)每次工作都必須在期限之前執行完成(2)資源可以接受被兩個以上的任務使用(3)有效率的使用能源，到目前為止，如何運用電壓調整實現具有共用資源的偶發性任務排程依然是個懸而未決的問題，我們提出一種叫做DVSSR的動態電壓調整的演算法，此演算法結合強制式EDF/DDM演算法，可以解決排程共用資源之偶發性硬即時工作排程。

　　我們使用現有應用實例來進行研究，此現有應用為自動公路安全標示器(RMS)，並且與其他動態電壓調整的演算法作比較，我們的演算法提供了成本與功率節省之間合理的抉擇，在自動公路安全標示器這個應用中，DVSSR平均節省了92.03%的能源，有關偶發性工作的共用資源特性透過模擬中也加以說明。

　　Dynamic voltage scaling (DVS) algorithms save energy by scaling down the processor frequency when the processor is not fully loaded. How to schedule the sporadic, hard real-time tasks with shared resource in a power saving way is still an open problem. Thus, in the thesis, the problem of power aware scheduling for sporadic tasks that share a set of serially reusable, single unit software resources is considered. The goals of this work are that (1) each release of each task should be completed before a well-defined deadline, (2) a resource is serially used by more than one task simultaneously and (3) energy is used minimally. A DVS algorithm, called DVSSR (Dynamic Voltage Scaling for Sporadic Tasks with Shared Resource), is presented to solve the problem. DVSSR offers a power-minimized scheduling algorithm in conjunction with preemptive EDF/DDM scheduling to improve the effectiveness and efficiency of task scheduling.
　　In the simulation, RMS, a real application, is investigated. In this application, DVSSR and other DVS algorithms are simulated and compared. Our DVS algorithm offers reasonable trade-off between cost and power savings. In RMS application, DVSSR achieves 92.03% average power savings. The properties of resource-sharing sporadic task model are also explored in simulation results.

誌謝	III
中文摘要	                                                                  IV
ABSTRACT	                                                                  V
TABLE OF CONTENT	                                                         VI
TABLE LIST	                                                         IX
FIGURE LIST	                                                         X
ABBREVIATION LIST	                                                         XI
CHAPTER 1	INTRODUCTION	                                                1
CHAPTER 2	MODELING THE SCHEDULING OF SPORADIC, HARD REAL-TIME TASKS WITH RESOURCE-SHARING	                                                         5
2.1	DVS Model	                                                         6
2.2	Power Model	                                                7
2.2.1	Linear Power Model          	                              7
2.2.2	Non-Linear Power Model	                                       8
2.3	Task Model	                                                9
2.4	Goals of DVSSR	                                                11
CHAPTER 3	DVSSR: DYNAMIC VOLTAGE SCALING FOR SPORADIC TASKS WITH SHARED RESOURCES	                                                                  12
3.1	DVSST: Dynamic Voltage Scaling for Sporadic Tasks	           14
3.1.1	Feasibility conditions	                                      16
3.2	Scheduling Single Phase Task Systems	                             22
3.2.1	EDF/DDM scheduling	                                                22
3.2.2	DVSSR	                                                        24
3.2.3	Scheduling Example of DVSSR	                                       30
3.2.4	Comparaitive Examples of DVSSR and DVSST	                    36
CHAPTER 4	MATHEMATICAL ANALYSIS OF DVSSR	                             43
4.1	Feasibility of Task Scheduling in DVSSR	                    43
4.2	Power Savings	                                               51
4.3	Computational Complexity of DVSSR	                             55
CHAPTER 5	PERFORMANCE EVALUATION	                                      57
5.1	Comparison with other algorithms	                             59
5.1.1	Power Savings for a Robotic Highway Safety Marker	           59
5.1.2	The algorithms to be compared	                             60
5.1.3	Simulation Result under Linear Power Model	                    61
5.1.4	Simulation Result under Non-linear Power Model	           64
5.1.5	The power savings under different power level resolutions	  67
5.2	The property of sharing resource	                             69
5.2.1	Task set about shared resource	                             69
5.2.2	Only one resource shared by two tasks	                    70
5.2.3	One resource shared by multiple tasks	                    74
5.2.4	Multiple resource shared by multiple tasks	                    76
CHAPTER 6	CONCLUSION AND FUTURE WORKS	                                      78
6.1	Conclusions	                                               78
6.2	Future Works	                                               79
APPENDIX	                                                                  80
Introduction of the proof-by-contradiction method	                    80
REFERENCES	                                                         81
                                    

[1]W. Wolf, “Modern VLSI Design”, Prentice Hall Modern Semiconductor Design Series, Third Edition 2002.
[2]Liu, C.L., Layland, J.W., “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”, Journal of the ACM, 20, 1, pp. 46-61, January 1973
[3]Mok, A.K.-L., “Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment”, Ph.D. Thesis, MIT, Department of EE and CS, MIT/LCS/TR-297, May 1983.
[4]K. Jeffay, “Scheduling Sporadic Tasks with Shared Resources in Hard-Real-Time Systems”, In Proceedings of IEEE Real-Time Systems Symposium (RTSS’92), 1992.
[5]S. Goddard and S. Farritor, “A Dynamic Voltage Scaling Algorithm for Sporadic Tasks”, In Proceedings of IEEE international Real-Time Systems Symposium (RTSS’03), 2003.
[6]A. Qadi, S. Goddard Goddard and S. Farritor, “DVSST: A Dynamic Voltage Scaling Algorithm for Sporadic Tasks”, In University of Nebraska – Lincoln, Dept. of CSE, RT-CSE-UNL-2003-2, 2003.
[7]R. Jejurikar and R. Gupta, “Energy aware task scheduling with task synchronization for embedded real time systems”, In Proceedings of IEEE International Conference on Compilers, Architecture, And Synthesis for Embedded System (CASES 2002), 2002.
[8]R. Jejurikar and R. Gupta, “Energy Aware EDF Scheduling with Task Synchronization for Embedded Real Time Systems”, In Workshop on Compilers and Operating Systems for Low Power (COLP’02), 2002, Charlottesville, Virginia, USA. September 22, 2002.
[9]Hong, D. Kirovski, G. Qu, M. Potkonjak, and M. B. Srivastava, “Power Optimization of Variable-Voltage Core-Based Systems”, IEEE Transaction on Computer-Aided Design, vol. 18, no.12, pp. 1702-1714, Dec. 1999.
[10]H. Kawaguchi, Y. Shin, and T. Sakurai, “Experimental Evaluation of Cooperative Voltage Scaling (CVS): A Case Study”, In Proceedings of IEEE Workshop on Power Management for Real-Time and Embedded Systems, pp. 17-23, May 2001.
[11]Y. Doh and C. M. Krishna, “EDF Scheduling Using Two-Mode Voltage-Clock-Scaling for Hard Real-time Systems”, In Proceedings of Compilers, Architectures and Synthesis for Embedded Systems Conference (CASES’01), pp. 221-228, 2001.
[12]J. Luo and N. K. Jha, “Power-conscious Joint Scheduling of Periodic Task Graphs and Aperiodic Tasks in Distributed Real-time Embedded Systems”, In Proceedings of Computer Aided Design Conference (ICCAD’00), pp. 357–364, Nov 2000.
[13]Manzak and C. Chakrabarti, “Variable Voltage Task Scheduling for Minimizing Energy or Minimizing Power” In Proceedings of Acoustic, Speech, and Signal Processing Conference(ICASSP’00), pp. 3239–3242, June 2000.
[14]D. Mosse, H. Aydin, B. Childers and R. Melhem, “Compiler- Assisted Dynamic Power-Aware Scheduling for Real-Time Applications”, In Workshop on Compilers and Operating Systems for Low-Power (COLP’00), Philadelphia, PA, Oct. 2000.
[15]D. Shin and J. Kim, “A Profile-Based Energy-Efficient Intra-Task Voltage Scheduling Algorithm for Hard Real-Time Applications”, In Proceedings of International Symposium on Low Power Electronics and Design (ISLPED’01), 2001.
[16]D. Shin, J. Kim, and S. Lee, “Intra-Task Voltage Scheduling for Low-Energy Hard Real-Time Applications”, IEEE Design and Test Computers, 18(2): 20–30, 2001.
[17]Y. Shin and K. Choi, “Power Conscious Fixed Priority Scheduling for Hard Real-Time Systems”, In Proceedings of the Design Automation Conference (DAC’99), pp. 134–139, June 1999.
[18]Y. Shin, K. Choi, and T. Sakurai, “Power Optimization of Real-Time Embedded Systems on Variable Speed Processors”, In Proceedings of the International Conference on Computer-Aided Design (CAD’00), pp. 365–368, November 2000.
[19]M. Weiser, B. Welch, A. Demers, and S. Shenker, “Scheduling for Reduced CPU Energy”, In Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI’94), pp. 13–23, November 1994.
[20]F. Zhang and S. T. Chanson, “Processor Voltage Scheduling for Real-Time Tasks with Non-Preemptable Sections”, In Proceedings of IEEE Real-Time Systems Symposium (RTSS’02), Austin, Texas, pp. 235–245, Dec. 2002.
[21]S. Farritor and M. Rentchler, “Robotic Highway Safety Markers”, In Proceedings of ASME International Mechanical Engineering Congress, New Orleans, Louisiana, November 17-22, 2002.
[22]Cheol-Hoon Lee and Kang G. Shin, “On-Line Dynamic Voltage Scaling for Hard Real-Time Systems Using the EDF Algorithm”, In Proceedings of IEEE Real-Time Systems Symposium (RTSS’04), 2004.
[23]Intel XScale microarchitecture, http://developer.intel.com/design/intelxscale, Intel Inc.
[24]M. Fleischmann. Crusoe Processor Products and Technology, LongRun Power Management – Dynamic Power Management for Crusoe Processors. http://www.transmeta.com/developers/techdocs.html, Transmeta Inc., January 17, 2001.
[25]Rabbit Semiconductors. Rabbit 2000 Microprocesser User’s Manual, http://www.rabbitsemiconductor.com/products/rab2000/docs.shtml, Rabbit Inc.
[26]Chen, M.-I and Lin, K.-J, “Dynamic Priority Ceilings: A Concurrency Control Protocol for Real-Time Systems”, In Proceesings of IEEE Real-Time Systems Symposium (RTSS’90), 2, 4, (November 1990), pp. 325-346.
[27]Chen, M.-I., Lin, K.-J., “A Priority Ceiling Protocol for Multiple-Instance Resources”, In Proceedings of IEEE Real-Time Systems Symposium (RTSS’91), San Antonio, TX, December 1991, pp. 140-149.
[28]Sha, L., Rajkumar, R., Lehoczky, J.P., “Priority Inheritance Protocols: An Approach to Real-Time Synchronization”, IEEE Transaction on Computers, 39, 9, (September 1990), pp. 1175-1185.
[29]P. Kumar and M. Srivastava, “Predictive strategies for low-power rtos scheduling”, In Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD’00), pp. 343–348, 2000.
[30]V. Raghunathan, P. Spanos, and M. Srivastava, “Adaptive power-fidelity in energy aware wireless embedded systems”, In IEEE Real-Time Systems Symposium (RTSS’01), 2001.
[31]Gang Qu, “What is the Limit of Energy Saving by Dynamic Voltage Scaling?”, In Proceedings of Computer Aided Design Conference (ICCAD’01), 2001.
[32]Grimaldi, Ralph P., “Discrete and combinational mathematics: an applied introduction”, Addison-Wesley Longman, Fourth Edition, 2000.

2006-08-02公開

簡易檢索 / 詳目顯示

相關論文