施吉昇Shih, Chi-Sheng臺灣大學:資訊網路與多媒體研究所卓士傑Zhuo, Shih-JieShih-JieZhuo2010-05-052018-07-052010-05-052018-07-052009U0001-1808200913383800http://ntur.lib.ntu.edu.tw//handle/246246/180735管線排程是一種於異質多核心平台上提升系統效能的重要方法，然而當今許多應用程式是具備高變動執行時間的軟性即時工作，由於執行時間的不確定性，要設計並執行包涵這類工作的管線排程是一項重要的挑戰，因此我們需要一個有效率的方法去排程不具固定執行時間的軟性工作。在本論文中，我們提出一個高效率的排程演算法去排程具備高變動執行時間的軟性即時工作，我們提出的演算法採用一個以資源預留為基礎的方法去達到工作間的隔離以及保證各工作可使用的運算資源，更進一步的，藉由根據其平均的資源使用來預留資源給軟性執行工作以達到一個管線排程中的有效資源利用，在我們所提出演算法的排程之下，透過一個不影響其他工作的剩餘時間再利用，來適當地處理超過限度的工作以及消除不必要的工作間內容切換，最後並藉由大量的模擬實驗來證實該演算法在降低工作間內容切換次數以及工作錯失最後期限比例的有效性。On a heterogeneous multi-core platform, pipelined schedule is an important approach to enhance system performance. However, for several modern applications, they are soft real-time tasks with highly variable execution time. Designing and executing a pipelined schedule for these kinds of tasks becomes an important challenge due to the uncertainty of their execution time. As a result, an efficient approach for scheduling soft real-time tasks without constant execution time is required. In this thesis,e present a scheduling algorithm for scheduling tasks of highly variable execution time in a pipelined schedule. The proposed algorithm employs the reservation-based approach to isolate tasks and provide the guaranteed computing resource. Furthermore, an effective resource utilization in pipelined schedule is achieved by reserving an average-case resource usage for soft real-time tasks with variable execution time. Under the schedule of proposed approach, overrun of soft real-time task is properly handled and redundant context switches are also eliminated by an effective slack reclaiming without interfering others’ guaranteed resource. The effectiveness of proposedlgorithm in decreasing deadline miss rate and number of context switch is demonstrated by extensive set of simulations.Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiihinese Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vist of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiist of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixhapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Objectives and Contributions . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4hapter 2 Background and Related Works . . . . . . . . . . . . . . . . . . . . . 6.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9hapter 3 Formal Model and Problem Description . . . . . . . . . . . . . . . . 11.1 Architecture Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Workload Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.3 Workload Model on a Single Core . . . . . . . . . . . . . . . . . . . . . . . 15.4 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19hapter 4 Slack Reclaiming for Pipelined Schedule . . . . . . . . . . . . . . . 22.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2 Slack Time Collection and Distribution . . . . . . . . . . . . . . . . . . . . 23.3 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33hapter 5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 36.1 Simulation Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 36.2 Experimental Result and Analysis . . . . . . . . . . . . . . . . . . . . . . 38hapter 6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48.2 FutureWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49eferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50application/pdf670718 bytesapplication/pdfen-US剩餘時間再利用管線排程多核心平台資源預留slack reclaimingpipelined schedulemulti-core platformresource reservationthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/180735/1/ntu-98-R96944002-1.pdf