施吉昇臺灣大學：資訊網路與多媒體研究所賈立Chia, LiLiChia2007-11-272018-07-052007-11-272018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/58420可重組態硬體能以低廉的成本及低功耗提供多樣化的功能。可程式化邏輯閘陣列（ＦＰＧＡ）為一種可重組態硬體，其技術的快速進展已使其可以應付高速及複雜的邏輯運算。以靜態記憶體技術為基礎製造的ＦＰＧＡ可以在執行時期內進行重組態以便在需要時提供邏輯運算功能而降低成本及功耗，但是重組態的延遲時間和ＦＰＧＡ上的資源管理為傳統的即時排程演算法帶來了新挑戰，為了最佳化硬體使用及重組態延遲時間，ＦＰＧＡ上的排程及資源管理需要新的技術。我們考量了ＦＰＧＡ的限制並提出以模板式演算法來管理硬體資源，並避免對效能造成影響或是違反重組態的截限時間限制。我們提出的解決方式利用離線時期產生的模板協助執行時期排程。Reconfigurable hardwares can provide multiple functions with low cost and power consumption. Field Programmable Gate Array (FPGA), a form of reconfigurable hardware, is developing rapidly to handle high speed and complex applications. SRAM-based FPGA can be reconfigured during runtime to provide functionalities as they are required, thus reducing cost and power assumption. However, the reconfiguration delay time and resource management of FPGA poses new challenges to traditional real-time scheduling algorithms. In order to optimize hardware usage and reconfiguration delay time, the scheduling and resource management on FPGA requires new techniques. In this thesis, we study the constraints of FPGA and propose a template-based approach to reuse hardware resources without compromising performances and violating the reconfiguration deadline constraint. The proposed solution uses offline generated templates to assist the job of generating schedules during runtime.Chapter 1 Introduction . . . 1 1.1 Motivation . . . 1 1.1.1 Application examples . . . 2 1.2 Objectives and Contributions . . . 4 1.3 Organization . . . 5 Chapter 2 RelatedWorks and Problem Definition . . . 6 2.1 Backgrounds . . . 6 2.2 RelatedWorks . . . 8 2.3 Formal Model . . . 10 2.3.1 Terms . . . 10 2.3.2 Constraints . . . 14 2.4 Problem Definition . . . 15 Chapter 3 Template-based Runtime Reconfiguration Algorithm . . . 16 3.1 Overview . . . 16 3.2 Templates . . . 17 3.3 Template Design Phase . . . 22 3.3.1 Design Templates with ILP . . . 25 3.3.2 Filtering Templates . . . 28 3.4 Template Selection Phase . . . 31 Chapter 4 Experiments . . . 33 Chapter 5 Conclusion . . . 37 References . . . 38 Vita . . . 40379008 bytesapplication/pdfen-US局部重組態可程式化邏輯閘陣列排程可重組態硬體partial reconfigurationFPGAschedulingreconfigurable hardwarethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/58420/1/ntu-95-R93944010-1.pdf