郭大維臺灣大學：資訊工程學研究所陳雅淑Chen, Ya-ShuYa-ShuChen2007-11-262018-07-052007-11-262018-07-052007http://ntur.lib.ntu.edu.tw//handle/246246/53810雖然嵌入式的應用已經遍佈一般使用者的生活，但由於可用資源相當有限，使得此類系統的設計日趨複雜。為滿足使用者應用程式的需求，目前大部分的嵌入式系統通常會配備中央處理器與多個執行單元，每一單元負責特定的功能，例如H.264的解碼功能。此外，由於多數嵌入式系統必須具備高度可移動性，此類系統在設計時必須兼顧低價格，高效能和低耗電。 本篇論文探討如何利用在多執行單元下的嵌入式系統之有效排程，同時兼顧價格，效能與耗電的問題。我們首先探討在多執行單元下資源共享時，為何會發生排程異常的主因和如何維持系統穩定的方式。進一步，討論如何在多執行單元下分析工作的排程行為，並研究如何在滿足效能要求下，規劃最低價格產品的問題。接下來，考慮耗電問題，我們提出即時資源的同步協定，此協定可以有效降低中央處理器的頻率轉換次數，並大大降低整體的耗能。此協定不僅可以用於一般信號機的同步，也可用於多執行單元的外部硬體加速器或是協同處理器的同步需求。The designs of embedded systems are complicated by various limitations on resource supports, such as computing power, even though their potential application domains grow exponentially. In order to support applications with strong resource demands, many embedded systems are now equipped with multiple processing elements with particular functionalities, such as H.264 decoding. Since many embedded systems are running on mobile devices, their designs must explore tradeoffs among cost, performance, and energy efficiency. This thesis investigates resource scheduling issues of embedded systems with multiple processing elements with respect to the above tradeoffs. We first explore scheduling anomaly problems in resource sharing when there is more than one processing elements, referred to as active resources. Rules are then proposed for anomaly prevention. The work is later extended by considering the blocking behavior of tasks that share multiple active resources. The cost optimization problem is resolved under the schedulability requirements of task executions. When energy efficiency is under considerations, we propose real-time resource synchronization protocols with an objective to minimize the number of processor frequency switchings and the total energy consumption. Protocols are first proposed for the access synchronization of passive resources, e.g., semaphores and memory, that do not own any computing capability and are used by tasks in a passive way. We then address synchronization issues over active and passive resources.誌謝………………………………………………………………………………. i 中文摘要………………………………………………………………………… i ii 英文摘要…………………………………………………………………………. v 1 Introduction ………………………………………………………1 2 RelatedWork ………………………………………………………5 2.1 Real-Time Task Scheduling on Single Processor ……………………………5 2.2 Real-Time Task Scheduling on Multiple Processing Elements ……………………6 2.3 Real-Time Task Scheduling with Energy Consideration………………………………………… 8 3 An Anomaly Prevention Approach for Active and Passive Resources………………………………… 11 3.1 Overview ………………………………… 11 3.2 System Model and Problem Definition …………… 12 3.2.1 Motivation …………………………………………12 3.2.2 Problem Formulation ……………………………14 3.3 Scheduler Stability - Greediness versus Stability ……15 3.4 Anomaly Prevention ……………………………16 3.4.1 Anomaly Prevention - Passive Resources ……………………………16 3.4.2 Anomaly Prevention - Active and Passive Resources …………………………… 20 3.5 Performance Evaluation ……………………………23 3.5.1 Experimental Setup and Performance Metrics …………………………… 23 3.5.2 Experimental Results ……………………………24 3.6 Summary ……………………………28 4 Scheduling and Blocking Analysis for Active Resources 29 4.1 Overview ……………………………29 4.2 System Model and Problem Definition ……………………………31 4.3 Starting Time Controller for Multi-Function SoCs . …………………………… 33 4.3.1 STC Algorithm ……………………………33 4.3.2 Schedulability Test …………………………… 40 4.4 Optimal Processing Elements Allocation for Multi-Function SoCs …………………………… 42 4.4.1 Equivalent Processing Element Cost ……………………………42 4.4.2 Non-Equivalent Processing Element Cost …………………………… 44 4.5 Performance Evaluation …………………………… 47 4.5.1 Performance Metrics and Workload Generation ……………………………47 4.5.2 Experimental Results …………………………… 48 4.6 Summary ……………………………50 5 Energy-Efficient Synchronization of Passive Resources…… 51 5.1 Overview ……51 5.2 System Model and Problem Definition ……52 5.3 Frequency Locking for Energy-Efficient Real-Time Task Synchronization…… 53 5.3.1 Frequency Locking: FL-PCP and FL-PIP ……54 5.3.2 Slack Reclaiming and Dynamic Priority Assignment ……66 5.4 Performance Evaluation …… 67 5.4.1 Data Sets and Performance Metrics ……67 5.4.2 Experiment Results ……68 5.5 Summary …… 72 6 Energy-Efficient Synchronization of Active and Passive Resources ……73 6.1 Overview……………………………73 6.2 System Model and Problem Definition ……………………………74 6.3 Energy-Efficient Real-Time Task Synchronization over Active Resources……………………………75 6.3.1 Energy-Efficient Real-Time Multiprocessor Scheduling: FL-MPCP……………………………76 6.3.2 Frequency Assignment of FL-MPCP ……………………………80 6.4 Performance Evaluation …………………………… 89 6.4.1 Data Sets and Performance Metrics ……………………………89 6.4.2 Experiment Results …………………………… 91 6.5 Summary……………………………92 7 Conclusion ……………………………93 Bibliography ……………………………95en-US省電資源管理系統晶片排程嵌入式系統同步協定Energy EfficiencyResource ManagementSoCSchedulingEmbedded SystemSynchronization Protocol[SDGs]SDG7thesis