請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33776完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 郭大維(Tei-Wei Kuo) | |
| dc.contributor.author | Nei-Chiung Perng | en |
| dc.contributor.author | 彭念劬 | zh_TW |
| dc.date.accessioned | 2021-06-13T05:45:56Z | - |
| dc.date.available | 2006-07-18 | |
| dc.date.copyright | 2006-07-18 | |
| dc.date.issued | 2006 | |
| dc.date.submitted | 2006-07-11 | |
| dc.identifier.citation | Bibliography
[1] James H. Anderson and Sanjoy K. Baruah. Energy-efficient synthesis of periodic task systems upon identical multiprocessor platforms. In Proceedings of the 24th International Conference on Distributed Computing Systems, pages 428–435, 2004. [2] Hakan Aydin and Qi Yang. Energy-aware partitioning for multiprocessor real-time systems. In Proceedings of 17th International Parallel and Distributed Processing Symposium (IPDPS), pages 113 – 121, 2003. [3] Anantha P. Chandrakasan, Samuel Sheng, and Robert W. Broderson. Low-power CMOS digital design. IEEE Journal of Solid-State Circuit, 27(4):473–484, 1992. [4] Jian-Jia Chen, Heng-Ruey Hsu, Kai-Hsiang Chuang, Chia-Lin Yang, Ai-Chung Pang, and Tei-Wei Kuo. Multiprocessor energy-efficient scheduling with taskmigration considerations. In Proceedings of EuroMicro Conference on Real-Time Systems (ECRTS’04), pages 101–108, 2004. [5] Wen-Hsiung Chen, C. Harrison Smith, and S. C. Fralick. A fast computational algorithm for the discrete cosine transform. IEEE Transaction on Communication, COM-25:1004–1009, September 1977. [6] Stephen Childs and David Ingram. The Linux-SRT integrated multimedia operating systems: Bring QoS to the desktop. In Proceedings of IEEE Real-Time Technology and Applications Symposium, pages 135–140, 2001. 85 86 BIBLIOGRAPHY [7] Pierre Cloutier, Paolo Mantegazza, Steve Papacharalambous, Ian Soanes, Stuart Hughes, and Karim Yaghmour. DIAPM-RTAI position paper. In Proceedings of Real Time Operating Systems Workshop, November 2000. [8] Giovanni DeMicheli, Rolf Ernst, andWayneWolf, editors. Readings in Hardware/- Software Co-Design. The Morgan Kaufmann Series in Systems on Silicon. Morgan Kaufmann, June 2001. [9] Giovanni De Micheli and Rajesh K. Gupta. Hardware/software co-design. Proceedings of the IEEE, 85(3):349–365, March 1997. [10] Andr´e DeHon. DPGA-coupled microprocessors: Commodity ICs for the early 21st century. In Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines, pages 31–39, April 1994. [11] Andr´e DeHon and John Wawrzynek. Reconfigurable computing: What, why, and implicatios for design automation. In Proceedings of the 36th ACM/IEEE Conference on Design Automation, pages 610–615, 1999. [12] Robert P. Dick, David L. Rhodes, and Wayne Wolf. TGFF: Task graphs for free. In Proceedings of International Workshop on Hardware/Software Codesign, 1998. [13] Michael R. Garey and David S. Johnson. Computers and Intractability. W. H. Freeman and Company, 1979. [14] Sabih H. Gerez. Algorithms for VLSI Design Automation. JohnWiley & Sons, 1999. [15] Soheil Ghiasi, Ani Nahapetian, and Majid Sarrafzadeh. An optimal algorithm for minimizing run-time reconfiguration delay. ACM Transactions on Embedded Computing Systems, 3(2):237–256, May 2004. BIBLIOGRAPHY 87 [16] J. Harkin, T. M. McGinnity, and L. P. Maguire. Partitioning methodology for dynamically reconfigurable embedded systems. IEE Proceedings on Computers and Digital Techniques, 147(6):391–396, November 2000. [17] J. Harkin, T. M. McGinnity, and L. P. Maguire. Modeling and optimizing run-time reconfiguration using evolutionary computation. ACM Transactions on Embedded Computing Systems, 3(4):661–685, November 2004. [18] Scott Hauck. Configuration prefetch for single context reconfigurable coprocessors. ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, 1998. [19] Scott Hauck. The roles of FPGA’s in reprogrammable systems. Proceedings of IEEE, 86(4), April 1998. [20] CoWare Homepage. http://www.coware.com. [21] eCos Homepage. http://ecos.sourceware.org. [22] uClinux Homepage. http://www.uclinux.org. [23] Sandy Irani and Kirk Pruhs. Algorithmic problems in power management. SIGACT News, 2005. [24] Johannes Kneip, Bernd Schmale, and Henning Moller. Applying and implementing the mpeg-4 multimedia standard. IEEE Micro, 19(6):64–74, November-December 1999. [25] Jean J. Labrosse. MicroC/OS-II: The Real-Time Kernel. CMP Books, 2002. [26] John P. Lehoczky, Lui Sha, and Ye Ding. The rate monotonic scheduling algorithms: - exact characterization and average behavior. In IEEE 10th Real-Time Systems Symposium, December 1989. 88 BIBLIOGRAPHY [27] C. L. Liu and JamesW. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. JACM, 20(1):46–61, January 1973. [28] Henry Neugass, Geoffrey Espin, Hidefume Nunoe, Ralph Thomas, and David Wilner. VxWorks: an interactive development environment and real-time kernel for gmicro. TRON Project Symposium, pages 196–207, November 1991. [29] Juanjo Noguera and Rosa M. Badia. Multitasking on reconfigurable architectures: Microarchitecture support and dynamic scheduling. ACM Transactions on Embedded Computing Systems, 3(2):385–406, May 2004. [30] William B. Pennebaker and Joan L. Mitchell. JPEG: Still Image Data Compression Standard. Kluwer Academic Publishers, 1st edition edition, September 1992. [31] Michael Pinedo. Scheduling Theory, Algorithms, and Systems. Prentice Hall, second edition, 2002. [32] Javier Resano, Daniel Mozos, and Francky Catthoor. A reconfigurable manager for dynamically reconfigurable hardware. IEEE Design and Test of Computers, 22(5):452–460, 2005. [33] Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky. Priority inheritance protocols: An approach to real-time synchronization. IEEE Transactions on Computers, pages 1175–1185, September 1990. [34] Satnam Singh and Phil James-Roxby. Lava and JBits: From HDL to Bitstream in seconds. In Proceedings of IEEE Symposium on FPGAs for Custom Computing Machines, April 2001. [35] Anil Telikepalli. Power vs. performance: The 90 nm inflection point. Technical report, Xilinx Inc., April 2005. BIBLIOGRAPHY 89 [36] Gustavo E. Tellez, Amir Farrahi, and Majid Sarrafzadeh. Activity-driven clock design for low power circuits. In Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, pages 62 – 65, 1995. [37] Filip Thoen and Francky Catthoor, editors. Modeling, Verification, and Exploration of Task-Level Concurrency of Real-Time Embedded Systems. Kluwer Academic Publishers, 2000. [38] L.M. Thompson. Using pSOS+ for embedded real-time computing. Compcon Spring ’90. ’Intellectual Leverage’. Digest of Papers. Thirty-Fifth IEEE Computer Society International Conference, pages 282–288, March 1990. [39] S. Trimberger, D. Carberry, A. Johnson, and J. Wong. A time-multiplexed FPGA. 5th IEEE Symposium on FPGA-Based Custom Computing Machines, 1997. [40] M. Weiser, B. Welch, A. Demers, and S. Shenker. Scheduling for reduced CPU energy. In Proceedings of Symposium on Operating Systems Design and Implementation, pages 12–23, 1994. [41] Douglas B.West. Introduction to Graph Theory. Prentice-Hall, Inc., second edition, 2001. [42] Wayne Wolf. FPGA-Based System Design. Prentice Hall, 2004. [43] Xilinx Inc. XAPP151 Virtex Series Configuration Architecture User Guide, (v1.7) edition, October 2004. [44] Chuan-Yue Yang, Jian-Jia Chen, and Tei-Wei Kuo. An approximation algorithm for energy-efficient scheduling on a chip multiprocessor. In Proceedings of the Eighth ACM/IEEE Conference of Design, Automation, and Test in Europe (DATE), pages 468–473, March 2005. 90 BIBLIOGRAPHY [45] V. Yodaiken. The RTLinux manifesto. Proceedings of the 5th Linux Expo, March 1999. [46] Ping-Hung Yuh, Chia-Lin Yang, and Yao-Wen Chang. Temporal floorplanning using the T-tree formulation. In Proceedings of ACM/IEEE International Conference on Computer-Aided Design, 2004. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33776 | - |
| dc.description.abstract | 隨著可重組式計算（reconfigurable computing）成為嵌入式系統設計的未來趨勢之一，嵌入式系統設計也面臨新的挑戰。本論文專注於三項可重組式計算的議題，分別為：配置面積最佳化、支援動態調變電壓的節能問題、以及嵌入式系統核心設計。本論文首先在可重組式硬體上的配置面積最佳化上，進行了在不同限制下的相關子問題分析，並對於特定條件下的子問題提出最佳演算法，由於該問題的求解難度甚高，本論文亦提出一些經驗法則演算法。本論文更進一步在已知一個程序排程下進行配置面積最佳化研究，當沒有任何工作重覆使用相同的處理單元時，我們提出數個最佳演算法，在較廣泛性的配置問題上，我們也提出適合的經驗法則演算法。本論文的第二個部份探討可重組式硬體的節能排程問題，在可動態調變電壓的平台上，倘若指定工作在特定配置上執行，我們提出最佳化演算法，反之則利用近似演算法得到相當良好的結果。最後，本論文討論了即時嵌入式系統核心的設計考量，並且實作出一個極小的即時作業系統核心，該核心也可套用至軟硬體協同設計工具內。本論文在所提出的方法與設計上，除了提出分析與佐證外，更藉由一系列實驗以證明演算法的正確性以及系統核心的優越效能。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T05:45:56Z (GMT). No. of bitstreams: 1 ntu-95-D90922011-1.pdf: 705346 bytes, checksum: a1ecec162dbe703e876744127139d2f0 (MD5) Previous issue date: 2006 | en |
| dc.description.tableofcontents | 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 93 | |
| dc.language.iso | en | |
| dc.title | 即時嵌入式可重組平台之面積最佳化及程序排程 | zh_TW |
| dc.title | Context Minimization and Task Scheduling for Reconfigurable Embedded Platforms of Real-Time Systems | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 94-2 | |
| dc.description.degree | 博士 | |
| dc.contributor.oralexamcommittee | 吳家麟(Ja-Ling Wu),施吉昇(Chi-Sheng Shih),林風(Phone Lin),逄愛君(Ai-Chun Pang),曾煜棋(Yu-Chee Tseng),袁賢銘(Shyan-Ming Yuan) | |
| dc.subject.keyword | 可重組平台,即時系統,嵌入式系統,程序排程, | zh_TW |
| dc.subject.keyword | Reconfigurable Platform,Real-Time System,Embedded System,Task Scheduling, | en |
| dc.relation.page | 94 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2006-07-14 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-95-1.pdf 目前未授權公開取用 | 688.81 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。