Luận Án Tiến Sĩ Về Lập Lịch Tiết Kiệm Năng Lượng Cho Hệ Thống Nhúng Thời Gian Thực

Nghiên cứu luận án tiến sĩ về lập lịch nhạy cảm với năng lượng cho hệ thống nhúng thời gian thực, tối ưu hóa hiệu suất và tiết kiệm năng lượng.

• Đề tài: Lập Lịch Tiết Kiệm Năng Lượng Cho Hệ Thống Nhúng Thời Gian Thực

Tóm tắt

I. Tổng Quan Lập Lịch Tiết Kiệm Năng Lượng Hệ Thống Nhúng

Hệ thống nhúng ngày càng phổ biến, từ thiết bị gia dụng đến công nghiệp. Việc tiết kiệm năng lượng hệ thống nhúng trở nên cấp thiết để kéo dài tuổi thọ pin, giảm chi phí vận hành và bảo vệ môi trường. Quản lý năng lượng hệ thống nhúng hiệu quả đòi hỏi sự kết hợp giữa phần cứng và phần mềm. Lập lịch đóng vai trò quan trọng trong việc điều phối tài nguyên và giảm tiêu thụ năng lượng. Bài viết này trình bày các phương pháp lập lịch thời gian thực để tối ưu hóa hiệu suất năng lượng cho hệ thống nhúng. Nhiều kỹ thuật low power design đã được phát triển, bao gồm Dynamic Voltage and Frequency Scaling (DVFS) và Clock gating. Nghiên cứu của Niu (2006) nhấn mạnh tầm quan trọng của việc phát triển các thuật toán lập lịch energy efficient algorithms phù hợp với các hệ thống thời gian thực.

1.1. Tầm Quan Trọng của Quản Lý Năng Lượng cho IoT

Trong bối cảnh IoT (Internet of Things) phát triển mạnh mẽ, số lượng thiết bị nhúng tăng lên đáng kể. Các thiết bị IoT thường hoạt động bằng pin và yêu cầu tiết kiệm năng lượng hệ thống nhúng để duy trì hoạt động lâu dài. Việc triển khai các giải pháp quản lý năng lượng hệ thống nhúng hiệu quả cho phép các thiết bị IoT thu thập và truyền dữ liệu trong thời gian dài hơn, đồng thời giảm thiểu tác động đến môi trường. Các thuật toán Power aware scheduling đóng vai trò then chốt trong việc tối ưu hóa năng lượng tiêu thụ của các thiết bị này. Đặc biệt quan trọng trong bối cảnh các thiết bị IOT thường xuyên hoạt động trong chế độ idle.

1.2. Thách Thức trong Thiết Kế Hệ Thống Nhúng Tiết Kiệm Năng Lượng

Thiết kế hệ thống nhúng tiết kiệm năng lượng gặp nhiều thách thức. Yêu cầu về thời gian thực đòi hỏi hệ thống phải phản ứng nhanh chóng và chính xác, trong khi việc giảm tiêu thụ năng lượng có thể làm chậm hiệu suất. Việc ước tính năng lượng tiêu thụ của các thành phần phần cứng nhúng và phần mềm nhúng cũng là một bài toán phức tạp. Các kỹ thuật như Power gating và DVFS cần được điều chỉnh cẩn thận để đảm bảo hệ thống hoạt động ổn định và đáp ứng các ràng buộc về thời gian thực.

II. Bài Toán Tiêu Thụ Năng Lượng trong Hệ Thống Nhúng Real Time

Tiêu thụ năng lượng trong hệ thống nhúng thời gian thực là một vấn đề nan giải, đặc biệt khi hiệu suất và độ tin cậy là tối quan trọng. Thiết kế low power design thường phải đánh đổi giữa tốc độ xử lý và mức tiêu thụ năng lượng. Phân tích năng lượng hệ thống nhúng chỉ ra rằng cả năng lượng động (dynamic power) và năng lượng tĩnh (static power hay leakage power) đều đóng góp đáng kể vào tổng mức tiêu thụ. Các ứng dụng thời gian thực đòi hỏi sự cân bằng tinh tế giữa việc đáp ứng đúng hạn và giảm thiểu lãng phí năng lượng. Theo Niu (2006), việc không xem xét kỹ lưỡng leakage power có thể dẫn đến việc sử dụng các kỹ thuật giảm năng lượng không hiệu quả.

2.1. Ảnh Hưởng của Năng Lượng Động và Năng Lượng Tĩnh

Năng lượng động phụ thuộc vào tần số hoạt động và điện áp cung cấp, trong khi năng lượng tĩnh (leakage) tồn tại ngay cả khi hệ thống ở trạng thái nghỉ. Việc giảm điện áp có thể giảm đáng kể năng lượng động, nhưng đồng thời có thể làm tăng độ trễ và ảnh hưởng đến thời gian thực. Năng lượng tĩnh trở nên ngày càng quan trọng trong các hệ thống sử dụng công nghệ VLSI tiên tiến. Quản lý năng lượng hệ thống nhúng đòi hỏi sự hiểu biết sâu sắc về cả hai thành phần này để đưa ra các quyết định tối ưu.

2.2. Vai Trò của Lập Lịch trong Giảm Tiêu Thụ Năng Lượng

Lập lịch đóng vai trò trung tâm trong việc tiết kiệm năng lượng hệ thống nhúng. Bằng cách điều phối các tác vụ một cách thông minh, hệ thống có thể giảm thiểu thời gian hoạt động ở tần số cao và tận dụng các chế độ tiết kiệm năng lượng (ví dụ: sleep mode). Các thuật toán lập lịch power aware scheduling có thể dự đoán nhu cầu năng lượng và điều chỉnh tần số, điện áp một cách linh hoạt, đảm bảo đáp ứng yêu cầu thời gian thực trong khi vẫn tiết kiệm năng lượng.

2.3. Khó khăn trong đảm bảo QoS khi tiết kiệm năng lượng

Việc đảm bảo Quality of Service (QoS) trong khi tiết kiệm năng lượng là một bài toán khó. Các giải pháp tiết kiệm năng lượng có thể ảnh hưởng đến độ trễ và thông lượng, ảnh hưởng đến trải nghiệm người dùng. Do đó cần cân nhắc giữa việc giảm tiêu thụ năng lượng và duy trì mức QoS chấp nhận được. Cần có các chiến lược quản lý năng lượng linh hoạt, có thể thích ứng với các điều kiện tải khác nhau, để duy trì QoS ổn định trong khi tối ưu hóa hiệu suất năng lượng.

III. Phương Pháp DVS Cho Hệ Thống Nhúng Thời Gian Thực Tiết Kiệm

Dynamic Voltage and Frequency Scaling (DVFS) là một kỹ thuật phổ biến để tiết kiệm năng lượng hệ thống nhúng. Kỹ thuật này điều chỉnh điện áp và tần số hoạt động của bộ xử lý dựa trên tải công việc hiện tại. Khi tải thấp, điện áp và tần số giảm xuống, giảm tiêu thụ năng lượng. Khi tải cao, điện áp và tần số tăng lên để đảm bảo hiệu suất. Việc áp dụng DVFS trong hệ thống nhúng thời gian thực đòi hỏi sự cẩn trọng để không vi phạm các ràng buộc về thời gian thực. Các thuật toán lập lịch DVFS cần phải dự đoán chính xác nhu cầu tính toán và điều chỉnh tần số, điện áp một cách linh hoạt. Niu (2006) đã nghiên cứu các thuật toán lập lịch DVFS dựa trên EDF để giảm tiêu thụ năng lượng trong hệ thống nhúng thời gian thực.

3.1. Ưu Điểm của DVFS Trong Các Ứng Dụng Thời Gian Thực

DVFS có khả năng giảm đáng kể tiêu thụ năng lượng trong các ứng dụng thời gian thực. Bằng cách giảm điện áp và tần số khi tải thấp, hệ thống có thể tiết kiệm năng lượng mà không ảnh hưởng đến hiệu suất khi tải cao. DVFS đặc biệt hiệu quả trong các ứng dụng có tải biến đổi theo thời gian, chẳng hạn như xử lý đa phương tiện và truyền thông không dây. Quan trọng là cân nhắc kỹ các chi phí chuyển đổi tần số, điện áp để tối ưu hiệu quả.

3.2. Các Thuật Toán Lập Lịch DVFS Phổ Biến

Nhiều thuật toán lập lịch DVFS đã được phát triển, bao gồm các thuật toán dựa trên Earliest Deadline First (EDF) và Fixed Priority (FP). Các thuật toán này khác nhau về độ phức tạp và hiệu quả. Một số thuật toán cố gắng dự đoán tải trong tương lai và điều chỉnh tần số, điện áp trước, trong khi các thuật toán khác phản ứng với những thay đổi tải theo thời gian thực. Lựa chọn thuật toán phù hợp phụ thuộc vào đặc điểm của ứng dụng và yêu cầu thời gian thực.

IV. Giải Pháp Lập Lịch Power Aware cho Hệ Thống Nhúng Real Time

Lập lịch Power aware scheduling là một hướng tiếp cận quan trọng để giảm tiêu thụ năng lượng trong hệ thống nhúng thời gian thực. Các thuật toán lập lịch này không chỉ xem xét các ràng buộc về thời gian thực mà còn tính đến các yếu tố liên quan đến năng lượng. Các thuật toán lập lịch power aware scheduling có thể sử dụng thông tin về điện áp, tần số, và trạng thái năng lượng của các thành phần để đưa ra các quyết định lập lịch tối ưu. Mục tiêu là giảm thiểu tổng tiêu thụ năng lượng trong khi vẫn đảm bảo đáp ứng đúng hạn các tác vụ thời gian thực. Theo Niu (2006), việc kết hợp các kỹ thuật power aware scheduling với các kỹ thuật quản lý năng lượng hệ thống nhúng khác có thể mang lại hiệu quả tiết kiệm năng lượng đáng kể.

4.1. Các Yếu Tố Cần Xem Xét Trong Lập Lịch Power Aware

Khi thiết kế các thuật toán lập lịch power aware scheduling, cần xem xét nhiều yếu tố, bao gồm: Mức tiêu thụ năng lượng của các tác vụ, thời gian chạy của các tác vụ, thời hạn của các tác vụ, trạng thái năng lượng của các thành phần, và chi phí chuyển đổi năng lượng. Việc cân bằng các yếu tố này là rất quan trọng để đạt được hiệu quả tiết kiệm năng lượng tối ưu.

4.2. Các Loại Thuật Toán Lập Lịch Power Aware

Có nhiều loại thuật toán lập lịch power aware scheduling khác nhau, bao gồm các thuật toán dựa trên EDF, FP, và các thuật toán lai. Các thuật toán này có thể sử dụng các kỹ thuật khác nhau để giảm tiêu thụ năng lượng, chẳng hạn như: DVFS, Dynamic Power Down (DPD), và Task Migration. Lựa chọn thuật toán phù hợp phụ thuộc vào đặc điểm của ứng dụng và yêu cầu thời gian thực.

4.3. Tối ưu bằng phương pháp Delay Execution

Để tối ưu tiêu thụ, một phương pháp là delay execution (trì hoãn thực thi), trì hoãn các task đến thời điểm gần deadline, để gom các khoảng thời gian idle lại thành các khoảng lớn hơn. Điều này giúp cho hệ thống có thể tận dụng các kỹ thuật như power gating hiệu quả hơn. Các công trình nghiên cứu như LC-EDF đã sử dụng chiến lược này, nhưng vẫn còn hạn chế.

V. Nghiên Cứu Thuật Toán Lập Lịch Giảm Leakage Hệ Thống Nhúng

Nghiên cứu của Niu (2006) tập trung vào việc giảm leakage power trong hệ thống nhúng bằng cách kết hợp DVFS và các kỹ thuật lập lịch. Nghiên cứu này đề xuất một thuật toán lập lịch cho phép bộ xử lý chuyển đổi giữa các chế độ năng lượng khác nhau để giảm thiểu leakage power trong thời gian rảnh rỗi. Thuật toán này cũng xem xét chi phí chuyển đổi giữa các chế độ năng lượng khác nhau để đảm bảo rằng việc chuyển đổi mang lại hiệu quả tiết kiệm năng lượng thực sự. Kết quả nghiên cứu cho thấy rằng thuật toán này có thể giảm đáng kể tiêu thụ năng lượng so với các thuật toán lập lịch truyền thống. Các nghiên cứu khác cũng tập trung vào giảm leakage power thông qua các kỹ thuật Clock gating và Power gating.

5.1. Kết Hợp DVS và Lập Lịch Để Giảm Leakage

Việc kết hợp DVFS và các kỹ thuật lập lịch có thể mang lại hiệu quả giảm leakage power đáng kể. Bằng cách giảm điện áp và tần số trong thời gian rảnh rỗi, hệ thống có thể giảm leakage power mà không ảnh hưởng đến hiệu suất khi tải cao. Các thuật toán lập lịch cần phải dự đoán chính xác thời gian rảnh rỗi và điều chỉnh điện áp, tần số một cách linh hoạt.

5.2. Tối Ưu Hóa Chuyển Đổi Giữa Các Chế Độ Năng Lượng

Chi phí chuyển đổi giữa các chế độ năng lượng khác nhau có thể ảnh hưởng đến hiệu quả tiết kiệm năng lượng. Các thuật toán lập lịch cần phải tính đến chi phí này khi đưa ra các quyết định chuyển đổi. Việc tối ưu hóa chuyển đổi giữa các chế độ năng lượng có thể giúp giảm tiêu thụ năng lượng và cải thiện hiệu suất hệ thống.

VI. Tương Lai Xu Hướng Phát Triển Lập Lịch Tiết Kiệm Năng Lượng

Tương lai của việc lập lịch tiết kiệm năng lượng hệ thống nhúng hứa hẹn nhiều tiềm năng. Các xu hướng phát triển bao gồm: Tích hợp trí tuệ nhân tạo (AI) để dự đoán tải và điều chỉnh năng lượng một cách thông minh hơn. Phát triển các thuật toán lập lịch cho các hệ thống đa lõi (multicore systems) và hệ thống phân tán. Nghiên cứu các kỹ thuật Embedded systems power management mới để giảm tiêu thụ năng lượng một cách hiệu quả hơn. Việc kết hợp các kỹ thuật phần mềm nhúng và phần cứng nhúng sẽ đóng vai trò quan trọng trong việc đạt được hiệu quả tiết kiệm năng lượng hệ thống nhúng tối đa. Pin quản lý năng lượng cũng sẽ được cải tiến.

6.1. Ứng Dụng Trí Tuệ Nhân Tạo Trong Lập Lịch Năng Lượng

Trí tuệ nhân tạo (AI) có thể được sử dụng để dự đoán tải và điều chỉnh năng lượng một cách thông minh hơn. Các thuật toán AI có thể học hỏi từ dữ liệu lịch sử và đưa ra các quyết định lập lịch tối ưu dựa trên các điều kiện hiện tại. Việc tích hợp AI vào các thuật toán lập lịch có thể mang lại hiệu quả tiết kiệm năng lượng đáng kể.

6.2. Lập Lịch Cho Hệ Thống Đa Lõi và Hệ Thống Phân Tán

Các hệ thống nhúng ngày càng trở nên phức tạp hơn, với nhiều lõi xử lý và các thành phần phân tán. Việc phát triển các thuật toán lập lịch cho các hệ thống này đòi hỏi sự hiểu biết sâu sắc về các đặc tính của hệ thống và các yêu cầu của ứng dụng. Các thuật toán lập lịch cần phải điều phối các tác vụ trên nhiều lõi xử lý và các thành phần phân tán một cách hiệu quả để đạt được hiệu suất cao và tiết kiệm năng lượng.

Trích đoạn nội dung tài liệu

POWER-AWARE SCHEDULING FOR REAL-TIME EMBEDDED SYSTEMS by Linwei Niu Master of Science State University of New York at Stony Brook, 2001 Bachelor of Science Beijing University, China, 1998 Submitted in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in the Department of Computer Science and Engineering College of Engineering and Information Technology University of South Carolina 2006 Gaye—— Major Professbt ag. Chairman, Examining Committee Le án Committee Member Comntittee Mémber (2.z— Dean of The Graduate School UMI Number: 3245425 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.

Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3245425 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.

ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 Acknowledgments First of all, I would like to express my sincere gratitude to my advisor, Dr. Gang Quan, for his invaluable hard work, guidance, support and encouragement throughout my graduate study at the University of South Carolina. Without him, none of the work would have been possible.

At the same time, I would like to thank Dr. Srihari Nelakuditi, and Dr. Antonello Monti for serving on my committee and for their valuable and constructive comments for my dissertation. I would like to thank all other faculty members and the staff for their valuable help and support throughout my graduate study at the University of South Car- olina.

I addition, I would like to thank all my friends in Columbia for their warm friendship, which made my life at the University of South Carolina memorable. Finally, Iam grateful to my parents. Although they are far away from me, they always give me unconditional love and support, which made my hard times much easier. ii Abstract Driven by the remarkable evolution of IC technology and the ever-increasing human appetite for higher computing power, the dramatically increased power /energy consumption for real-time embedded systems has presented a profound challenge to researchers and developers.

Battery-operated embedded devices, which have already been ubiquitous, demand low power consumption to extend the bat- tery life and thus the mission cycles. Even for power-rich platforms, rapidly el- evated power consumption raised serious concerns regarding the reliability and packaging /cooling cost as a result of the heat dissipation. It is fair to say that en- ergy reduction has become one of the most critical design issues in the design of next generation real-time embedded systems. Power/energy reduction for real-time embedded systems is a challenging prob- lem that requires research efforts in all fronts be pursued to form the effective so- lution.

Tremendous research studies have been conducted on reducing the power /energy consumption. They differ by their abstraction levels, underlying architec- tures, and design perspectives. In our research, we seek to address this problem at the operating system level. Specifically, we believe that real-time scheduling plays a critical role in power/energy reduction not only because most embedded sys- tems have real-time requirements, but also because significant energy savings can be achieved by taking advantage of the knowledge in application characteristics and underlying architectures known at this level.

The goal of our research is to study and develop appropriate real-time schedul- iii ing techniques that can exploit the advanced power manageable features in state- of-the-art architecture to minimize the power/energy consumption while satisfy- ing other design requirements at the same time. The contributions of the disser- tation include: (i) we developed several advanced power-aware scheduling al- gorithms for hard real-time systems with emphasis on reducing both dynamic and leakage power consumption; (ii) We extended the system model from sim- ple hard real-time systems to soft real-time systems with more complicated Qual- ity of Service constraints; (iii) We also developed efficient scheduling algorithms to minimize the system-wide energy consumption with peripheral devices taken into consideration. Experimental results have demonstrated that our techniques greatly outperform existing ones. The problems discussed in this dissertation are rather general in real-time embedded system designs, and these methodologies and techniques are important both in the theoretical and practical sense.

iv Contents Acknowledgments ii Abstract iii List of Figures xii 1 Introduction 11 Real-Time Embedded Systems.2 The Power Consumption in Embedded Systems .3 Power-Aware Design Techniques in Embedded Systems .4 Real-Time Scheduling.1 Power-Aware Scheduling on Hard Real-Time Systems 18 1.2 Power-Aware Scheduling on Soft Real-Time Systems. ch HH he he 27 2 Leakage-Aware Scheduling 2. ee HQ HH Ha an Ra 2. ee es 23 Prelminaries.So ẶẶ Q SỈ PowerModel.

Ặ eee eee eee 35 2.4 The General Approach. eee ee he he 38 2.1 Computing The LST for The EDF-Based JobSet .2 Computing The LST for The FP-Based Job Set. eee ee ees 54 2. {So Number ofldlelntervals.3 Overall Energy Reduction.4 Energy Reduction with Higher Threshold Speed.

ch HH HH HH HH kh Ha 62 DVS Scheduling for Real-Time Systems with QoS-Guarantee 65 31 Introduction ©. ch HH HH kh ha 71 3.1 System Models and Problem Formulation.2 ee ee Motivatons.4 Mandatory/OptionalJob Parttionng .41 Static Partiioning Strategy with (m,k)-Pattern.2 Dynamic Partitioning Strategy With (mm, k)-Pattern Adjustment 88 3.5 DVS Scheduling for The Task Set with ee ee tt .1 The Offline Phase. ee ee es 0.2 The Online Phase. ee es 98 vi 3.1 Experimental Results for Synthesized Task Sets .2 Experimental Results from Real Applications.

ee ee 106 DPD Scheduling for Real-Time Systems with QoS-Guarantee 107 41. ch HH he hi hở 111 421 System Models. ee eee te ee ee 111 4. eee ee es 112 4.

Meeting The (m,k)-Constraints .4 Delaying The Execution of Mandatory Jobs. ch HH HH h HH nh 126 4.1 Experimental Results for Synthesized Task Sets .2 Experimental Results from Real Applications. ee 133 Combining DVS and DPD Scheduling for Real-Time Systems with QoS- Guarantee 135 51 Introducton. ee es 136 52 Preliminary.

‹ ‹ che HH HH he ng 138 521 - ch SystemModel. HH nh nen 138. HH HH he 140 5.3 The Hybrid Partitioning Strategy. eee eee eee 141 53.1 The Feasibility Condiion .2 The Pattern Assignment ++ 0s eee -.

147 The Dynamic Scheduling Algorthm. ee es 153 vii 5.1 Experimental Results for Synthesized Task Sets .2 Experimental Results for Real Applications. 159 6 Conclusions and Future Work 161 Bibliography 164 Viii List of Figures 1. Embedded systems everywhere.6eee ee eee ees 1.2 Embedded systems dominate the 32-bit market [55].3 Growth for the embedded system market by 2009 [154].4 Low Operating Power (LOP) Device Power Increment [72] .5 The performance/power gaps tend to become larger in the future [14] 2.1 (a) A job set with five jobs scheduled with EDF.

(d) The job schedule with Sty = OB. Q Q Q Q Q nu ch nh kg k k k ko cà Ko R K K Ko Ko th ho ky 36 2.2 (a) The delay bound.5, using the minimum of the latest start times of the jobs arriving before Tz as LST for the job set causes J> to miss its deadline. (c) The idle intervals are not effec- tively merged using T;s = 6, computed based on the completion time of the jobs according to the DVS voltage schedule. (d) With Trs = 8, all the idle intervals are merged into one single interval and all jobs can meet their deadlines.3 (a) A job set with four jobs scheduled with FP, and the LST is com- puted as 3 according to Lemma 1(s* = 0.

(b) Delay the job set until t = 6 and every job can meet its deadline. (d) Delay execution of the job set till t = 8 and J, misses its deadline.4 The average total energy consumption by the different approaches.5 The average total energy consumption by the different approaches.6 The average idle energy consumption by the different approaches with s4, =0.1 The greedy approach in [64] fails to guarantee the schedulability of an underloaded task set.2 Examples of mandatory jobs based on R-patterns, E-patterns, and ER-patterns.4 (a) Executing only the mandatory jobs of task set according to their ER.patterns; (b) Dynamically restarting the E”-Pattern at t = 8 for Tạ. chkh kh kh 91 3.5 (a)The original mandatory jobs according to the Z”-pattern of task 7;; (b) The mandatory jobs of 7; after restarting the #” pattern.6 (a) The average total energy consumption by the different approaches; (b) The average number of effective jobs by the different approaches.7 (a) Energy consumption for webphone by the different approaches on IBM PowerPC 405LP processor model; (b) The average number of effective jobs for webphone by the different approaches on IBM PowerPC 405LP processor model.8 (a) Energy consumption for CNC by the different approaches on IBM PowerPC 405LP processor model; (b) The average number of effective jobs for CNC by the different approaches on IBM PowerPC 405LP processor model. eee ee eee 104 3.9 (a) Energy consumption for INS by the different approaches on IBM PowerPC 405LP processor model; (b) The average number of effec- tive jobs for INS by the different approaches on IBM PowerPC 405LP ee processor model.1 (a) The EDF schedule for three tasks according to E-patterns; (b) The EDF schedule for same tasks based on R-patterns; (c) A better schedule for the same task set.2 (a) Three tasks scheduled based on their R-Pattern; (b) Jz, cannot be delayed according to Theorem 8; (c) Delaying the mandatory jobs to t = 23 ( [114]) cannot remove the idle interval; (d) Delaying the mandatory jobs to t = 27 and eliminating the idle interval.3 The average number of idle intervals by different approaches.4 The average total energy consumption by different approaches when (a) Pact = Poacti (bP) Paact = 10Ppacte ss ee ee es 129 4.5 The average total energy consumption by different approaches.6 (a) The average total energy consumption for CNC by different ap- proaches; (b) The average number of idle intervals for CNC by dif- ferent approaches.7 (a) The average total energy consumption for INS by different ap- proaches; (b) The average number of idle intervals for INS by differ- entapproaches.8 (a) The average total energy consumption for Webphone by different approaches; (b) The average number of idle intervals for Webphone .1 (a) Executing the mandatory jobs of task set (7¡ = (4,4,2, 2, 4); Ta = (8, 8, 4, 2, 4);) according to their E-patterns; (b) Executing the manda- tory jobs of the same task set according to their R-patterns; (c) Ex- ecuting the mandatory jobs of the same task set according to their hyb-patterns.2 (a) The average total energy consumption by the different approaches; (b) The energy comparison for different shut-down interval length; (c) The energy comparison for different preemption control tech- NIQUES.3 (a) The average total energy consumption by the different approaches; (b) The energy comparison for different shut-down interval length; (c) The energy comparison for different preemption control tech- THQUES.

6 Q Q Q SH HH HH HH HH Ko 157 xii Chapter 1 Introduction This chapter first gives a brief introduction on real-time embedded systems, fol- lowed by the power consumption issues in embedded systems. Thereafter, we survey the state of the art in the research of power-aware design methodology, real-time scheduling and power-aware scheduling. We then discuss the contribu- tion of our research. This chapter ends with the description of the organization of this dissertation.1 Real-Time Embedded Systems An embedded system is a special-purpose computer system built into a larger sys- tem for the purpose of controlling and monitoring the system [11, 58].