郭大維臺灣大學：資訊工程學研究所彭念劬Perng, Nei-ChiungNei-ChiungPerng2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/53915隨著可重組式計算（reconfigurable computing）成為嵌入式系統設計的未來趨勢之一，嵌入式系統設計也面臨新的挑戰。本論文專注於三項可重組式計算的議題，分別為：配置面積最佳化、支援動態調變電壓的節能問題、以及嵌入式系統核心設計。本論文首先在可重組式硬體上的配置面積最佳化上，進行了在不同限制下的相關子問題分析，並對於特定條件下的子問題提出最佳演算法，由於該問題的求解難度甚高，本論文亦提出一些經驗法則演算法。本論文更進一步在已知一個程序排程下進行配置面積最佳化研究，當沒有任何工作重覆使用相同的處理單元時，我們提出數個最佳演算法，在較廣泛性的配置問題上，我們也提出適合的經驗法則演算法。本論文的第二個部份探討可重組式硬體的節能排程問題，在可動態調變電壓的平台上，倘若指定工作在特定配置上執行，我們提出最佳化演算法，反之則利用近似演算法得到相當良好的結果。最後，本論文討論了即時嵌入式系統核心的設計考量，並且實作出一個極小的即時作業系統核心，該核心也可套用至軟硬體協同設計工具內。本論文在所提出的方法與設計上，除了提出分析與佐證外，更藉由一系列實驗以證明演算法的正確性以及系統核心的優越效能。While reconfigurable computing is identified as one important direction for future embedded systems design, various challenges exist! In this dissertation, we explore several critical issues in reconfigurable computing: reconfiguration plan derivation, configuration context minimization, dynamic-voltage-scaling energy-efficiency, and embedded operating systems. The minimization problem of configuration contexts is first explored, provided that deadline and precedence constraints are given. We exploit different constraints on the context minimization problem and their corresponding subproblems. We then propose scheduling algorithms for the derivation of reconfiguration plans based on a given schedule. When no two tasks in a schedule share a processing element, optimal scheduling algorithms are presented. A heuristic-based scheduling algorithm is proposed for general cases. When dynamic voltage scaling is considered, we propose algorithms to schedule the loadings and the executions of tasks in a multi-context FPGA at run-time. Optimal scheduling algorithms and approximation algorithms are presented for cases in which task partitions over contexts are or are not given. The dissertation is concluded by the proposing of a tiny real-time kernel for embedded systems. The kernel is ported to run over hardware/software co-design tools. A series of experiments was also done to evaluate the kernel performance.Contents Abstract in Chinese v Abstract vii Acknowledgment ix Contents xi List of Figures xvi List of Tables xvii 1 Introduction 1 1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Scheduling in Reconfigurable Computing . . . . . . . . . . . . . 4 1.1.2 Energy-Efficient Scheduling . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Real-Time Kernels of Embedded Systems . . . . . . . . . . . . . 6 1.2 Dissertation Organization . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 The Context Minimization Problem 9 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Problem Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 xi xii CONTENTS 2.3.1 NP-Complete Subproblems . . . . . . . . . . . . . . . . . . . . 14 2.3.2 Subproblems in P . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Context Minimization: A Greedy Approach . . . . . . . . . . . . . . . . 21 2.5 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.5.1 Experiment Setup and Performance Metrics . . . . . . . . . . . . 25 2.5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . 26 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3 FPGA Context Number Minimization for Task Schedules 31 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3 No Duplication of Processing Elements . . . . . . . . . . . . . . . . . . 36 3.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3.2 Simultaneous Reconfigurations of Multiple Configuration Contexts 38 3.3.3 Exclusive Reconfiguration of Multiple Configuration Contexts . . 40 3.4 Duplications of PEs and Mutual Exclusion on Loading . . . . . . . . . . 46 3.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.5.1 Experiment Setup and Performance Metrics . . . . . . . . . . . . 48 3.5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . 49 3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4 Energy-Efficient Scheduling on Multi-Context FPGAs 55 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3 The Proposed Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.3.1 Scheduling with a Given Task Partition . . . . . . . . . . . . . . 59 4.3.2 Scheduling without a Given Task Partition . . . . . . . . . . . . . 62 4.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 CONTENTS xiii 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5 A Tiny Real-Time Kernel for Embedded Systems 69 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.2 Programming Hazards for Embedded Software . . . . . . . . . . . . . . 71 5.3 Design Issues and Performance Evaluation for Real-Time Kernels . . . . 73 5.3.1 Fundamental Design Issues for Real-Time Kernels . . . . . . . . 73 5.3.2 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . 76 5.4 System Architecture and System Prototypes . . . . . . . . . . . . . . . . 79 5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6 Conclusion 83 Bibliography 85 Curriculum Vitae 91 Publication List 93705346 bytesapplication/pdfen-US可重組平台即時系統嵌入式系統程序排程Reconfigurable PlatformReal-Time SystemEmbedded SystemTask Schedulingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53915/1/ntu-95-D90922011-1.pdf