即時嵌入式可重組平台之面積最佳化及程序排程

Abstract

隨著可重組式計算（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.