支持可重构混成体系结构的操作系统研究
|
摘要
嵌入式系统在当今社会已无处不在，例如大家同常生活中用到的PDA、MP3、手机和在专门的场合应用的网络节点系统、医疗系统、穿戴电脑系统等，它一般由计算部件、外围设备、操作系统以及用户应用四个部分组成。可选的计算部件有专用集成电路ASIC(Application Specific Integrated Circuit)、指令集处理器ISP(Instruction Set Processor)和现场可编程门阵列FPGA(Field Programmable GateArray)。FPGA是一种可重构硬件，计算性能高且易于编程，非常适合同时具有高计算复杂度和多变工作集的应用。在嵌入式系统的复杂度、性能和上市时间等要求不断提高的今天，FPGA器件的应用范围正在变得越来越广泛。
随着半导体技术的发展，基于SRAM存储器件的FPGA容量已经达数百万门，且具有动态部分可重构功能，从而可随时加载、执行和删除独立的硬件逻辑模块。因此，FPGA已经成为一种可以动态分配的计算资源。由FPGA和ISP构成的可重构混成系统具有计算性能高、灵活性强、适用范围广等优点，目前已成为国际上研究的热点。
按照传统的设计观念，FPGA被视为硬件加速器，由用户直接管理和使用。而操作系统仅提供一些驱动作为支持。这种方式的设计难度很高，而且由于忽略了FPGA的可重构特性以及硬件逻辑模块间的潜在并行性，效率很低。为了提高FPGA的利用率、简化开发流程和提高系统的性能，操作系统必须对可重构器件提供更有效的支持。本文对可重构资源的管理和共享问题进行了深入的研究，提出了KVIT(Keeping the Vertexes Information of Tasks)布局算法、QFOAC(Quantifying Fragments by Occupied Area Concatenation)碎片量化方法和MGS(Minimum Gap Scheduling)调度算法。针对已有混成系统运行模型的缺陷，提出并设计了基于服务体／执行流模型SEFM(Servant & Exe-Flow Model)的，面向可重构混成体系结构的操作系统SEF-OSHRSfSEF Operating System for Hybrid Reconfigurable Systems)，实现了该操作系统的原型系统。
在OSHRS中，布局算法必须在保证布局质量的基础上，尽量减少布局开销。KVIT布局算法就是为解决这个问题而提出的。该算法尝试将新到达的硬件任务放置在已布局硬件任务的顶点处，并通过对可重构芯片内部计算单元进
Embedded computer systems are omnipresent. They can be found in almost all parts of our infrastructure that are directly and consciously used by people day-to-day, or that are not consciously perceived by most of people. Examples of such systems are PDAs, Mp3 players, mobile phones, network nodes, medical treatment systems and wearable computers etc. Commonly, An Embedded System can be composed of computing units, I/O devices, an operating system and user applications etc. Optional computing unit could be ASIC, ISP or FPGA. FPGA is a kind of reconfigurable hardware with high performance and flexibility for programming, which is appropriate for applications combining high performance demands with frequent changes of their workloads. With the increasing request on complexity, performance and time-to-market of embedded computer systems, FPGA is becoming more and more popular.
With the development of semiconductor technology, the capability of SRAM based FPGA has achieved several millions of gates. The partially reconfigurable FPGA can load, execute or delete individual hardware logic blocks at runtime which makes FPGA runtime allocable computing resource. The hybrid system composed of FPGA and ISP has the advantages of high performance, flexible programmability and more extensive usage, and it has become the focus of research in the recent years.
On the traditional opinion of designers, FGPA acts as the accelerator of hardware that managed directly by the programmers, while the operating system afford no more support than some device drivers. This manner leads to a complicated design flow in the process of development. Furthermore, it is inefficient because of ignoring the potential parallelism of the individual logic blocks. The
随着半导体技术的发展，基于SRAM存储器件的FPGA容量已经达数百万门，且具有动态部分可重构功能，从而可随时加载、执行和删除独立的硬件逻辑模块。因此，FPGA已经成为一种可以动态分配的计算资源。由FPGA和ISP构成的可重构混成系统具有计算性能高、灵活性强、适用范围广等优点，目前已成为国际上研究的热点。
按照传统的设计观念，FPGA被视为硬件加速器，由用户直接管理和使用。而操作系统仅提供一些驱动作为支持。这种方式的设计难度很高，而且由于忽略了FPGA的可重构特性以及硬件逻辑模块间的潜在并行性，效率很低。为了提高FPGA的利用率、简化开发流程和提高系统的性能，操作系统必须对可重构器件提供更有效的支持。本文对可重构资源的管理和共享问题进行了深入的研究，提出了KVIT(Keeping the Vertexes Information of Tasks)布局算法、QFOAC(Quantifying Fragments by Occupied Area Concatenation)碎片量化方法和MGS(Minimum Gap Scheduling)调度算法。针对已有混成系统运行模型的缺陷，提出并设计了基于服务体／执行流模型SEFM(Servant & Exe-Flow Model)的，面向可重构混成体系结构的操作系统SEF-OSHRSfSEF Operating System for Hybrid Reconfigurable Systems)，实现了该操作系统的原型系统。
在OSHRS中，布局算法必须在保证布局质量的基础上，尽量减少布局开销。KVIT布局算法就是为解决这个问题而提出的。该算法尝试将新到达的硬件任务放置在已布局硬件任务的顶点处，并通过对可重构芯片内部计算单元进
Embedded computer systems are omnipresent. They can be found in almost all parts of our infrastructure that are directly and consciously used by people day-to-day, or that are not consciously perceived by most of people. Examples of such systems are PDAs, Mp3 players, mobile phones, network nodes, medical treatment systems and wearable computers etc. Commonly, An Embedded System can be composed of computing units, I/O devices, an operating system and user applications etc. Optional computing unit could be ASIC, ISP or FPGA. FPGA is a kind of reconfigurable hardware with high performance and flexibility for programming, which is appropriate for applications combining high performance demands with frequent changes of their workloads. With the increasing request on complexity, performance and time-to-market of embedded computer systems, FPGA is becoming more and more popular.
With the development of semiconductor technology, the capability of SRAM based FPGA has achieved several millions of gates. The partially reconfigurable FPGA can load, execute or delete individual hardware logic blocks at runtime which makes FPGA runtime allocable computing resource. The hybrid system composed of FPGA and ISP has the advantages of high performance, flexible programmability and more extensive usage, and it has become the focus of research in the recent years.
On the traditional opinion of designers, FGPA acts as the accelerator of hardware that managed directly by the programmers, while the operating system afford no more support than some device drivers. This manner leads to a complicated design flow in the process of development. Furthermore, it is inefficient because of ignoring the potential parallelism of the individual logic blocks. The
引文
[1] C Plessl, R Enzler, H Walder, J Beutel, M Platzner, L Thiele, G Troster. The Case for Reconfigurable Hardware in Wearable Computing. Personal and Ubiquitous Computing, 2003, 299-308.
[2] IMEC Interuniversity Micro Electronic Center. T-ReCS Gecko. URL: http://www.imec.be
[3] S. Chakraborty, M. Gries, S. Kunzli, L. Thiele. Design Space Exploration of Network Processor Architectures. Network Processor Design: Issues and Practices, 2002, Vol. 1, 55-89.
[4] Katherin Compton. Reconfigurable Computing. URL: http://www.ee.washington.edu/hauck
[5] M Rencher, B L Hutchings. Automated target recognition on SPLASH2. In: Proceedings of the IEEE Symp on Field-Programmable Custom Computing Machines, 1997,
[6] M Weinhardt, W Luk. Pipeline vectorization for reconfigurable systems. In: Proceedings of the IEEE Symp on Field Programmable Custom Computing Machines, 1997,
[7] S Hauck, W D Wilson. Runlength compression techniques for FPGA configurations. 2001, Publisher: Dept of ECE, Northwestern University
[8] P Graham, B Nelson. Genetic algorithms in software and in hardware—A performance analysis of workstation and custom computing machine implementations. In: Proceedings of the IEEE Symp on FPGAs for Custom Computing Machines, 1996,
[9] Xilinx Inc. Virtex-Ⅱ Pro Platform FPGAs: Complete Data Sheet. November 11, 2003, URL: http://www.xilinx.com
[10] Altera Corp. Excalibur Device Overview. 2002, Date: May URL: www.altera.com
[11] Katherine Compton, Scott Hauck. Reconfigurable computing: a survey of systems and software. ACM Comput. Surv, 2002, Vol. 34, No. 2, 171-210.
[12] Tsugio Makimoto. The RisingWave of Field Programmability. Tenth International Conference on Field Programmable Logic and Applications, 2000,
[13] Xilinx Inc. The Programmalbe Logic Data Book. San Jose, CA: 1994.
[14] Xilinx Inc. XC6200: Advanced Product Specification. San Jose, CA: 2001.
[15] Altera Corporation. Data Book. San Jose, CA: 2001.
[16] J R Haynes, J Wawrzynek. Grap: A MIPS processor with a reconfigurable coprocesssor. In: Proceedings of the IEEE Symp on Field Programmable Custom Computing Machines, 1997,
[17] S D Haynes, P Y K Cheung. A reconfigurable multiplier array for video image processing tasks, suitable for embedding in an FPGA structure. In: Proceedings of the IEEE Symp on Field Programmable Custom Computing Machines, 1998,
[18] Lucent Technologies Inc. FPGA Data Book. 2001.
[19] A Marshall, T Standfield, I Kostarnov. A reconfigurable arithmetic array for multimedia applications. In: Proceedings of the ACM/SIGDA Int '1 Symp. on FPGAS, 2000, 135-143.
[20] C Ebeling, D C Corquist, P Franklin. RaPiD — Reconfigurable pipelined datapath. 1996, 126-135.
[21] Xilinx Inc. LogiBLOX: Product Specification. San Jose, CA: 1997.
[22] Xilinx Inc. 2.5 V Field Programmable Gate Arrays: Advanced Product Specification. San Jose, CA: 2001.
[23] M A S Khalid. Routing architecture and layout synthesis for multi FPGA systems, thesis, University of Toronto, 2000.
[24] A Takahara, T Miyazaki, T Murooka. More wires and fewer LUTs: A design methodology for FPGAs. In: Proceedings of the ACM/SIGDA Int'l Symp on FPGAs, 1998, 12-19.
[25] A DeHon. Balancing interconnect and computation in a reconfigurable computing array. In: Proceedings of the ACM/SIGDA Int'l Symp on FPGA, 2000, 69-78.
[26] A Aggarwal, D Lewis. Routing architectures for hierarchical field programmable gate arrays. In: Proceedings of the Proc of IEEE Int'l Conf on Computer Design, 1994,475-478.
[27] Y T Lai, P T Wang. Hierarchical interconnection structures for field programmable gate arrays. IEEE Trans on VLSI Systems, 1997, Vol.5, No.2, 186-196.
[28] R D Witting, P Chow. OneChip : An FPGA processor with reconfigurable logic. In: Proceedings of the IEEE Symp on FPGAs for Custom Computing Machines, 1996, 126-135.
[29] S Hauck. Configurable prefetch for single context reconfigurable coprocessors. In: Proceedings of the ACM/SIGDA Int'l Symp on FPGAs,
[30] C R Rupp, M Landguth, T Garverick. The NAPA adaptive processing architecture. In: Proceedings of the IEEE Symp on Field Programmable Custom Computing Machines, 1998,
[31] Brebner G. A virtual hardware operating system for the Xilinx XC6200. In: Proceedings of the Field-Programmable Logic: Smart Applications, New Paradigms and Compilers, 6th International Workshop, FPL 96 Proceedings, September 1996, 327-336.
[32] J Burns, A Donlin, J Hogg, S Singh, M Wit. A Dynamic Reconfiguration Run-Time System. In: Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines (FCCM'97), 1997,
[33] Wigley G, Kearney D. The first real operating system for reconfigurable computers. In 6th A. In: Proceedings of the Australiasian Computer Science Week (ACSAC), 2001,
[34] J.Y. Mignolet, S. Vernalde, D. Verkest, R. Lauwereins. Enabling Hardware-Software ultitasking on a Reconfigurable Computing Platform for Networked Portable Multimedia Appliances. In: Proceedings of the Proc. Int'l Conf. Eng. of Reconfigurable Systems and Algorithms (ERSA), 2002, 116-122.
[35] T. Marescaux, A. Bartic, D. Verkest, S. Vernalde, R. Lauwereins. Interconnection Networks Enable Fine-Grain Dynamic Multi-Tasking on FPGAs. In: Proceedings of the Proc. Int'l Conf. Field-Programmable Logic and Applications (FPL), 2002, 795-805.
[36] Nollet V, Coene P, Verkest D, Vernalde S, Lauwereins R. Designing an operating system for a heterogeneous reconfigurable SoC. In: Proceedings of the IPDPS, April 2003,
[37] 周博,王石记,邱卫东．SHUM-UCOS:基于统一多任务模型可重构系统的实时操作系统．计算机学报,2006,Vol．29,No．2,208-218．
[38] Bazargan K, Kastner R, Sarrafzadeh M. Fast template placement for reconfigurable computing systems. IEEE Design and Test of Computers, 2000, Vol.17, No. 1,68-83.
[39] Handa M, Vemuri R. An efficient algorithm for finding empty space for online FPGA placement. In: Proceedings of the Design Automation Conference, 2004, 960-965.
[40] Ahmadinia A, Bobda C, Jurgen T. A new approach for on-line placement on reconfigurable devices. In: Proceedings of the Reconfigurable Architectures Workshop, 2004,
[41] Wigley G, Kearney D. The management of applications for reconfigurable computing using an operating system. In: Proceedings of the Proceedings of the seventh Asia-Pacific conference on Computer systems architecture, 2002, 73-81.
[42] Steiger C, Walder H, Platzner M. Operating Systems for Reconfigurable Embedded Platforms: Online Scheduling of Real-Time Tasks. IEEE Transactions on Computers, 2004, Vol. 53, No. 11, 1393-1407.
[43] Walder H, Steiger C, Platzner M. Fast online task placement on FPGAs: Free space partitioning and 2-D hashing. In: Proceedings of the Proceedings of the 17th International Parallel and Distributed Processing Symposium (IPDPS)/Reconfigurable ArchitecturesWorkshop (RAW), 2003,
[44] Walder H, Steiger C, Platzner M, Thiele L. Online scheduling and placement of real-time tasks to partially reconfigurable devices. In: Proceedings of the Real-Time Systems Symposium, 2003, 224-225.
[45] F. P. Preparata, M. I. Sharnos. Computational Geometry: An Iniroduction. New York: Springer-Verlag, 1985.
[46] J. Edmonds, J. Gryz, D. Liang, R. J. Miller. Mining for Empty Spaces in Large Data Sets. Theoretical Comput. Sci., 2003, Vol. 296, No. 3, 435-452.
[47] Walder H, Platzner M. Non-preemptive multitasking on FPGA: task placement and footprint transform. In: Proceedings of the Proceedings of the 2nd International Conference on Engineering of Reconfigurable Systems and Architectures, June 2002,
[48] Handa M, Vemuri R. Area fragmentation in reconfigurable operating systems. In: Proceedings of the Engineering of Reconfigurable Systems and Algorithms, June 2004, 77-83.
[49] Seong Moo Yoo, Hyunseung Choo, Hee Yong Youn, Chansu Yu, Younghee Lee, On task relocation in two-dimensional meshes. Journal of Parallel and Distributed Computing, 2000, Vol. 60, 616-638.
[50] Li K, Hoi Cheng K. A two dimensional buddy system for dynamic resource allocation in a partitionable mesh connected system. In: Proceedings of the Proceedings of the 1990 ACM annual conference on Cooperation, 1990, 22-27.
[51] David Andrews, Douglas Niehaus. Programming Models for Hybrid FPGA-CPU Computational Components: A Misssing Link. IEEE Transactions on Micro, 2004, Vol. 24, No. 4, 42-53.
[52] G. Chen, M.Kandemir, U. Sezer. Configuration-Sensitive Process Scheduling for FPGA-Based Computing Platforms. In: Proceedings of the Proceedings of Design, Automation & Test in Europe(DATE'03), 2004, 486-493.
[53] Xilinx Inc. Virtex-Ⅱ platform FPGAs: complete data sheet. 2005, URL: http://www.xilinx.com
[54] G. Buttazzo. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Kluwer, 2000.
[55] Danne K, Platzer M. A heuristic approach to schedule periodic real-time tasks on reconfigurable hardware. In: Proceedings of the Field Programm- able Logic and Applications, 2005, 568-573.
[56] Ahmadinia A, Bobda C, Teich J. A Dynamic scheduling and placement algorithm for reconfigurable hardware. In: Proceedings of the ARCS, 2004, 125-139.
[57] Brandon Blodget, Philip James Roxby, Eric Keller, Scott McMillan, Prasanna Sundararajan. A Self-reconfiguring Platform. In: Proceedings of the Field-Programmable Logic and Applications (FPL), 2003, 565-574.
[58] 李宏，龚育昌，赵振西，吴明桥．服务体模型与操作系统内核设计技木．计算机研究与发展，2005，Vol．7，
[59] 李宏．基于服务体模型的操作系统设计与实现．博士thesis，中国科学技术大学，2004．
[60] 龚育昌，陈香兰，李曦，李宏，张晔，吴明桥，周学海，杨文增，赵振西．基于服务体／执行流模型的操作系统．中华人民共和国发明专利。公开号：CN1667573A．发明专利公报Vol．21(37)．page 209．
[61] G Wigley, D. Kearney. Research Issues in Operating Systems for Reconfigurable Computing. In: Proceedings of the Proc. of the 2nd International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA'02), June 2002, 10-16.
[62] lntel Inc. Intel 80x86 Instruction Set. URL: www.intel.com
[63] Diessel O, Kearney D, Wigley G. A Web-Based Multiuser Operating System for Reconfigurable Computing. In: Proceedings of the Proceedings of IPPS/SPDP'99 Parellel and Distributed Processing, 1999, 579 - 587.
[64] Gunther B. SPACE-2 as a reconfigurable stream processor. In: Proceedings of the Proceedings of PART'97 the 4 th Australasian Conference on Parallel and Real-Time Systems, September 1997, 286 - 297.
[65] N Shirazi, W Luk, P Cheung. Automating Production of Run-time Reconfigurable Designs. In: Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines (FCCM'98), 1998,
[66] D Davis, M Barr, T Bennett, S Edwards, J Harris, I Miller, C Schanck. A Java Development and Runtime Environment for Reconfigurable Computing. In: Proceedings of the Workshop on Parallel and Distributed Processing, (IPPS/SPDP'98), 1998,
[67] D Rakhmatov, S Vrudhula, T Brown, A Nagarandal. Adaptive Multiuser Online Reconfigurable Engine. IEEE Design & Test of Computers, 2000, Vol.17, 53-67.
[68] J Jean, K Tomko, V Yavagal, J Shah, R Cook. Dynamic Reconfiguration to Support Concurrent Applications. IEEE Transactions on Computers, 1999, Vol.48, 591-602.
[69] H Simmler, L Levinson, R Manner. Multitasking on FPGA Coprocessors. In: Proceedings of the Proc 10th Int Conf. Field Programmable Logic and Applications, August 2000, 121- 130.
[70] Willian Stallings. Operating System: internals and design principles, 3th edition. Prentice Hall, 1996.
[71] A.S. Tanenbaum, A.S. Woodhull. Operating system:design and implementation, 2th edition. Prentice Hall, 1996.
[72] Silbcrschatz A. Operating System Concepts Reading. Addison-Wesley, 1994.
[73] S.J. Leffler, M.K. Mckusick, M.J. Karels, J.S. Quarterman. The design and implementation of the 4.4BSD UNIX operating system. Addison-Wesley, 1992.
[74] Uresh Vahalia. Unix internals-the new frontiers. Prentice Hall, 1996.
[75] M.Acceta, R.Baron, W.Bolosky, D.Golub, R.Rashid, A.Tevanian, M.Young. Mach: A new kernel foundation for Unix development. In: Proceedings of the Summer USENIX conference, 1986,
[76] Richard Rashid, Alessandro Forin, David Golu. Mach: A System Software kernel. In: Proceedings of the Proceedings of the 34th Computer Society International Conference COMPCON 89,1989,
[77] J. Bradley Chen, Brian N. Bershad. The Impact of Operating System Structure on Memory System Performance. In: Proceedings of the Proceedings of The Fourteenth Symposium on Operating System Principles, 1994,
[78] Tevanian A, Jr Rashid, R F Golub, Young M W. Mach Tereads and the UNIX Kernel: The Battle for Control. In: Proceedings of the Procedding of the 1987 USENIX Technical conference, 1987, 185-197.
[79] Yousef A. Khalidi, Mcihael N. Nelson. The spring virtual memory system. 1993, URL:http://www.sun.com
[80] Graham Hamilton, Panos Kougiouris. The spring nucleus:A microkernel for objects. 1993,
[81] Yoself A. Khalidi, Michael N. NNelson. A flexible external paging interface. 1993,
[82] Christian Bac, Guy Bernard, Denis Conan. Experience with Chorus. In: Proceedings of the Conference on Current Trends in Theory and Practice of Informatics,
[83] M. Rozier, V. Abrossimov, F. Armand, I. Boule, M. Gien, M. Guillemont, F. Herrmann, C. Kaiser, P. Leonard, S. Langlois, W. Neuhauser. Chorus Distributed Operating Systems. Computing Systems, 1988, Vol.1, No.1, 305-379.
[84] Rob Pike, Dave Presotto, Sean Dorward, Bob Flandrena, Ken Thompson. Plan 9 From Bell Labs.URL:http://www.cs.bell-labs.com/sys/doc/
[85] Sape J. Mullender, Guido van Rossum, Andrew S. Tanenbaum. Amoeba A Distributed Operating System for the 1990s. IEEE Computer, 1990,
[86] A Tanenbaum, R. Van Renesse, H. Van Staveren, G. J. Sharp, S. J. Mullendar, J. Jansen, G. van Rossum. Experiences with the Amoeba Distributed Operating System. Communications of the ACM, 1990, Vol. 33, 46-63.
[87] Jochen Liedtke. On u-kemel construction. In: Proceedings of the 15th ACM Symposiun on Operating System Principles, 1995,
[88] Hermann H, Michael H, Jochen L, Sebastian S. The performance of u-kernel-based systems. In: Proceedings of the 16th ACM Symposium on Operating System, 1997,
[89] L4 other papers. URL: http://os.inf.tu-dresden.de/L4/doc.html
[90] R. P. Draves, B. N. Bershad, R. F. Rashid, R. W. Dean. Using continuations to implement thread management and communicateon in operating systems. 1991, Publisher: Department of computer science, Carnegie Mellon University
[91] Alan Dearle, Rex di Bona, James Farrow, Frans Henskens, Anders Lindstrom, John Rosenberg, Francis Vaughan. Grasshopper: An Orthogonally Persistent Operating System. Computing Systems, 1994, Vol. 7, No. 3, 289-312.
[92] Gernot Heiser, Kevin Elphinstone, Stephen Russell, Jerry Vochteloo. Mungi: A Distributed Single Address-Space Operating System In: Proceedings of the Proc 17th Australasian Comp. Sci. Conf, Jan 1994, 271-280.
[93] Sheetal V. Kakkad. Address Translation and Storage Management for Persistent Object Stores. Ph. D thesis, The University of Texas at Austin, 1997.
[94] P. J. Tomasevic, M. V. Milutinovic. Distributed shared memory: concepts and systems. IEEE Parallel&Distributed Technology Systems & applications, 1996, 63-71.
[95] A. M. Mainwaring, D. E. Culler. Active Messages: Organization and Applications Programming Interface. Technical Document, 1995,
[96] Steve Rodrigues, Tom Anderson, David Culler. High-performance local-area communication using fast sockets. Proc in USENIX, 1997,
[97] B. N. Bershad, T. E. Anderson, E. D. Lazowska, H.M. Levy. User-Level Interprocess Commuication for shared memory multiprocessors. ACM transactions on computer system, 1991,
[98] M. N. Nelson, Y. A. Khalidi, P. W. Madany. The Spring file system. 199. 3.
[99] 龚育昌，吴明桥，李宏．一种基于服务体／执行流的新型操作系统构造模型．中国科学技术大学学报，2006，Vol．36，
[100] Jochen Liedtke. Improving IPC by Kernel Design. In: Proceedings of the SOSP, 1993, 175-188.
[101] David Mosberger, Stephane Eranian. IA-64 Linux Kernel Design and Imolementation. Prentice Hall PTR, 2002.
[102] 龚育昌，王立刚，陈香兰，齐骥．一种严格按比例派发服务的混合实时调度算法．软件学报，2006 Vol．17，No．3，611-619．
[103] Xilinx Inc. Xilinx XUP Virtex Ⅱ Pro Development System. 2005, URL: http://www.xilinx.com/univ/xupv2p.html
[104] AAEON Inc. PCM-6892 Data Sheet. 2003, URL: http://www.aaeon.com.br/6892.htm
[105] Title: The Anubis Block Cipher URL: http://paginas.terra.com.br/informatica/paulobarreto/AnubisPage.htm
[2] IMEC Interuniversity Micro Electronic Center. T-ReCS Gecko. URL: http://www.imec.be
[3] S. Chakraborty, M. Gries, S. Kunzli, L. Thiele. Design Space Exploration of Network Processor Architectures. Network Processor Design: Issues and Practices, 2002, Vol. 1, 55-89.
[4] Katherin Compton. Reconfigurable Computing. URL: http://www.ee.washington.edu/hauck
[5] M Rencher, B L Hutchings. Automated target recognition on SPLASH2. In: Proceedings of the IEEE Symp on Field-Programmable Custom Computing Machines, 1997,
[6] M Weinhardt, W Luk. Pipeline vectorization for reconfigurable systems. In: Proceedings of the IEEE Symp on Field Programmable Custom Computing Machines, 1997,
[7] S Hauck, W D Wilson. Runlength compression techniques for FPGA configurations. 2001, Publisher: Dept of ECE, Northwestern University
[8] P Graham, B Nelson. Genetic algorithms in software and in hardware—A performance analysis of workstation and custom computing machine implementations. In: Proceedings of the IEEE Symp on FPGAs for Custom Computing Machines, 1996,
[9] Xilinx Inc. Virtex-Ⅱ Pro Platform FPGAs: Complete Data Sheet. November 11, 2003, URL: http://www.xilinx.com
[10] Altera Corp. Excalibur Device Overview. 2002, Date: May URL: www.altera.com
[11] Katherine Compton, Scott Hauck. Reconfigurable computing: a survey of systems and software. ACM Comput. Surv, 2002, Vol. 34, No. 2, 171-210.
[12] Tsugio Makimoto. The RisingWave of Field Programmability. Tenth International Conference on Field Programmable Logic and Applications, 2000,
[13] Xilinx Inc. The Programmalbe Logic Data Book. San Jose, CA: 1994.
[14] Xilinx Inc. XC6200: Advanced Product Specification. San Jose, CA: 2001.
[15] Altera Corporation. Data Book. San Jose, CA: 2001.
[16] J R Haynes, J Wawrzynek. Grap: A MIPS processor with a reconfigurable coprocesssor. In: Proceedings of the IEEE Symp on Field Programmable Custom Computing Machines, 1997,
[17] S D Haynes, P Y K Cheung. A reconfigurable multiplier array for video image processing tasks, suitable for embedding in an FPGA structure. In: Proceedings of the IEEE Symp on Field Programmable Custom Computing Machines, 1998,
[18] Lucent Technologies Inc. FPGA Data Book. 2001.
[19] A Marshall, T Standfield, I Kostarnov. A reconfigurable arithmetic array for multimedia applications. In: Proceedings of the ACM/SIGDA Int '1 Symp. on FPGAS, 2000, 135-143.
[20] C Ebeling, D C Corquist, P Franklin. RaPiD — Reconfigurable pipelined datapath. 1996, 126-135.
[21] Xilinx Inc. LogiBLOX: Product Specification. San Jose, CA: 1997.
[22] Xilinx Inc. 2.5 V Field Programmable Gate Arrays: Advanced Product Specification. San Jose, CA: 2001.
[23] M A S Khalid. Routing architecture and layout synthesis for multi FPGA systems, thesis, University of Toronto, 2000.
[24] A Takahara, T Miyazaki, T Murooka. More wires and fewer LUTs: A design methodology for FPGAs. In: Proceedings of the ACM/SIGDA Int'l Symp on FPGAs, 1998, 12-19.
[25] A DeHon. Balancing interconnect and computation in a reconfigurable computing array. In: Proceedings of the ACM/SIGDA Int'l Symp on FPGA, 2000, 69-78.
[26] A Aggarwal, D Lewis. Routing architectures for hierarchical field programmable gate arrays. In: Proceedings of the Proc of IEEE Int'l Conf on Computer Design, 1994,475-478.
[27] Y T Lai, P T Wang. Hierarchical interconnection structures for field programmable gate arrays. IEEE Trans on VLSI Systems, 1997, Vol.5, No.2, 186-196.
[28] R D Witting, P Chow. OneChip : An FPGA processor with reconfigurable logic. In: Proceedings of the IEEE Symp on FPGAs for Custom Computing Machines, 1996, 126-135.
[29] S Hauck. Configurable prefetch for single context reconfigurable coprocessors. In: Proceedings of the ACM/SIGDA Int'l Symp on FPGAs,
[30] C R Rupp, M Landguth, T Garverick. The NAPA adaptive processing architecture. In: Proceedings of the IEEE Symp on Field Programmable Custom Computing Machines, 1998,
[31] Brebner G. A virtual hardware operating system for the Xilinx XC6200. In: Proceedings of the Field-Programmable Logic: Smart Applications, New Paradigms and Compilers, 6th International Workshop, FPL 96 Proceedings, September 1996, 327-336.
[32] J Burns, A Donlin, J Hogg, S Singh, M Wit. A Dynamic Reconfiguration Run-Time System. In: Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines (FCCM'97), 1997,
[33] Wigley G, Kearney D. The first real operating system for reconfigurable computers. In 6th A. In: Proceedings of the Australiasian Computer Science Week (ACSAC), 2001,
[34] J.Y. Mignolet, S. Vernalde, D. Verkest, R. Lauwereins. Enabling Hardware-Software ultitasking on a Reconfigurable Computing Platform for Networked Portable Multimedia Appliances. In: Proceedings of the Proc. Int'l Conf. Eng. of Reconfigurable Systems and Algorithms (ERSA), 2002, 116-122.
[35] T. Marescaux, A. Bartic, D. Verkest, S. Vernalde, R. Lauwereins. Interconnection Networks Enable Fine-Grain Dynamic Multi-Tasking on FPGAs. In: Proceedings of the Proc. Int'l Conf. Field-Programmable Logic and Applications (FPL), 2002, 795-805.
[36] Nollet V, Coene P, Verkest D, Vernalde S, Lauwereins R. Designing an operating system for a heterogeneous reconfigurable SoC. In: Proceedings of the IPDPS, April 2003,
[37] 周博,王石记,邱卫东．SHUM-UCOS:基于统一多任务模型可重构系统的实时操作系统．计算机学报,2006,Vol．29,No．2,208-218．
[38] Bazargan K, Kastner R, Sarrafzadeh M. Fast template placement for reconfigurable computing systems. IEEE Design and Test of Computers, 2000, Vol.17, No. 1,68-83.
[39] Handa M, Vemuri R. An efficient algorithm for finding empty space for online FPGA placement. In: Proceedings of the Design Automation Conference, 2004, 960-965.
[40] Ahmadinia A, Bobda C, Jurgen T. A new approach for on-line placement on reconfigurable devices. In: Proceedings of the Reconfigurable Architectures Workshop, 2004,
[41] Wigley G, Kearney D. The management of applications for reconfigurable computing using an operating system. In: Proceedings of the Proceedings of the seventh Asia-Pacific conference on Computer systems architecture, 2002, 73-81.
[42] Steiger C, Walder H, Platzner M. Operating Systems for Reconfigurable Embedded Platforms: Online Scheduling of Real-Time Tasks. IEEE Transactions on Computers, 2004, Vol. 53, No. 11, 1393-1407.
[43] Walder H, Steiger C, Platzner M. Fast online task placement on FPGAs: Free space partitioning and 2-D hashing. In: Proceedings of the Proceedings of the 17th International Parallel and Distributed Processing Symposium (IPDPS)/Reconfigurable ArchitecturesWorkshop (RAW), 2003,
[44] Walder H, Steiger C, Platzner M, Thiele L. Online scheduling and placement of real-time tasks to partially reconfigurable devices. In: Proceedings of the Real-Time Systems Symposium, 2003, 224-225.
[45] F. P. Preparata, M. I. Sharnos. Computational Geometry: An Iniroduction. New York: Springer-Verlag, 1985.
[46] J. Edmonds, J. Gryz, D. Liang, R. J. Miller. Mining for Empty Spaces in Large Data Sets. Theoretical Comput. Sci., 2003, Vol. 296, No. 3, 435-452.
[47] Walder H, Platzner M. Non-preemptive multitasking on FPGA: task placement and footprint transform. In: Proceedings of the Proceedings of the 2nd International Conference on Engineering of Reconfigurable Systems and Architectures, June 2002,
[48] Handa M, Vemuri R. Area fragmentation in reconfigurable operating systems. In: Proceedings of the Engineering of Reconfigurable Systems and Algorithms, June 2004, 77-83.
[49] Seong Moo Yoo, Hyunseung Choo, Hee Yong Youn, Chansu Yu, Younghee Lee, On task relocation in two-dimensional meshes. Journal of Parallel and Distributed Computing, 2000, Vol. 60, 616-638.
[50] Li K, Hoi Cheng K. A two dimensional buddy system for dynamic resource allocation in a partitionable mesh connected system. In: Proceedings of the Proceedings of the 1990 ACM annual conference on Cooperation, 1990, 22-27.
[51] David Andrews, Douglas Niehaus. Programming Models for Hybrid FPGA-CPU Computational Components: A Misssing Link. IEEE Transactions on Micro, 2004, Vol. 24, No. 4, 42-53.
[52] G. Chen, M.Kandemir, U. Sezer. Configuration-Sensitive Process Scheduling for FPGA-Based Computing Platforms. In: Proceedings of the Proceedings of Design, Automation & Test in Europe(DATE'03), 2004, 486-493.
[53] Xilinx Inc. Virtex-Ⅱ platform FPGAs: complete data sheet. 2005, URL: http://www.xilinx.com
[54] G. Buttazzo. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Kluwer, 2000.
[55] Danne K, Platzer M. A heuristic approach to schedule periodic real-time tasks on reconfigurable hardware. In: Proceedings of the Field Programm- able Logic and Applications, 2005, 568-573.
[56] Ahmadinia A, Bobda C, Teich J. A Dynamic scheduling and placement algorithm for reconfigurable hardware. In: Proceedings of the ARCS, 2004, 125-139.
[57] Brandon Blodget, Philip James Roxby, Eric Keller, Scott McMillan, Prasanna Sundararajan. A Self-reconfiguring Platform. In: Proceedings of the Field-Programmable Logic and Applications (FPL), 2003, 565-574.
[58] 李宏，龚育昌，赵振西，吴明桥．服务体模型与操作系统内核设计技木．计算机研究与发展，2005，Vol．7，
[59] 李宏．基于服务体模型的操作系统设计与实现．博士thesis，中国科学技术大学，2004．
[60] 龚育昌，陈香兰，李曦，李宏，张晔，吴明桥，周学海，杨文增，赵振西．基于服务体／执行流模型的操作系统．中华人民共和国发明专利。公开号：CN1667573A．发明专利公报Vol．21(37)．page 209．
[61] G Wigley, D. Kearney. Research Issues in Operating Systems for Reconfigurable Computing. In: Proceedings of the Proc. of the 2nd International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA'02), June 2002, 10-16.
[62] lntel Inc. Intel 80x86 Instruction Set. URL: www.intel.com
[63] Diessel O, Kearney D, Wigley G. A Web-Based Multiuser Operating System for Reconfigurable Computing. In: Proceedings of the Proceedings of IPPS/SPDP'99 Parellel and Distributed Processing, 1999, 579 - 587.
[64] Gunther B. SPACE-2 as a reconfigurable stream processor. In: Proceedings of the Proceedings of PART'97 the 4 th Australasian Conference on Parallel and Real-Time Systems, September 1997, 286 - 297.
[65] N Shirazi, W Luk, P Cheung. Automating Production of Run-time Reconfigurable Designs. In: Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines (FCCM'98), 1998,
[66] D Davis, M Barr, T Bennett, S Edwards, J Harris, I Miller, C Schanck. A Java Development and Runtime Environment for Reconfigurable Computing. In: Proceedings of the Workshop on Parallel and Distributed Processing, (IPPS/SPDP'98), 1998,
[67] D Rakhmatov, S Vrudhula, T Brown, A Nagarandal. Adaptive Multiuser Online Reconfigurable Engine. IEEE Design & Test of Computers, 2000, Vol.17, 53-67.
[68] J Jean, K Tomko, V Yavagal, J Shah, R Cook. Dynamic Reconfiguration to Support Concurrent Applications. IEEE Transactions on Computers, 1999, Vol.48, 591-602.
[69] H Simmler, L Levinson, R Manner. Multitasking on FPGA Coprocessors. In: Proceedings of the Proc 10th Int Conf. Field Programmable Logic and Applications, August 2000, 121- 130.
[70] Willian Stallings. Operating System: internals and design principles, 3th edition. Prentice Hall, 1996.
[71] A.S. Tanenbaum, A.S. Woodhull. Operating system:design and implementation, 2th edition. Prentice Hall, 1996.
[72] Silbcrschatz A. Operating System Concepts Reading. Addison-Wesley, 1994.
[73] S.J. Leffler, M.K. Mckusick, M.J. Karels, J.S. Quarterman. The design and implementation of the 4.4BSD UNIX operating system. Addison-Wesley, 1992.
[74] Uresh Vahalia. Unix internals-the new frontiers. Prentice Hall, 1996.
[75] M.Acceta, R.Baron, W.Bolosky, D.Golub, R.Rashid, A.Tevanian, M.Young. Mach: A new kernel foundation for Unix development. In: Proceedings of the Summer USENIX conference, 1986,
[76] Richard Rashid, Alessandro Forin, David Golu. Mach: A System Software kernel. In: Proceedings of the Proceedings of the 34th Computer Society International Conference COMPCON 89,1989,
[77] J. Bradley Chen, Brian N. Bershad. The Impact of Operating System Structure on Memory System Performance. In: Proceedings of the Proceedings of The Fourteenth Symposium on Operating System Principles, 1994,
[78] Tevanian A, Jr Rashid, R F Golub, Young M W. Mach Tereads and the UNIX Kernel: The Battle for Control. In: Proceedings of the Procedding of the 1987 USENIX Technical conference, 1987, 185-197.
[79] Yousef A. Khalidi, Mcihael N. Nelson. The spring virtual memory system. 1993, URL:http://www.sun.com
[80] Graham Hamilton, Panos Kougiouris. The spring nucleus:A microkernel for objects. 1993,
[81] Yoself A. Khalidi, Michael N. NNelson. A flexible external paging interface. 1993,
[82] Christian Bac, Guy Bernard, Denis Conan. Experience with Chorus. In: Proceedings of the Conference on Current Trends in Theory and Practice of Informatics,
[83] M. Rozier, V. Abrossimov, F. Armand, I. Boule, M. Gien, M. Guillemont, F. Herrmann, C. Kaiser, P. Leonard, S. Langlois, W. Neuhauser. Chorus Distributed Operating Systems. Computing Systems, 1988, Vol.1, No.1, 305-379.
[84] Rob Pike, Dave Presotto, Sean Dorward, Bob Flandrena, Ken Thompson. Plan 9 From Bell Labs.URL:http://www.cs.bell-labs.com/sys/doc/
[85] Sape J. Mullender, Guido van Rossum, Andrew S. Tanenbaum. Amoeba A Distributed Operating System for the 1990s. IEEE Computer, 1990,
[86] A Tanenbaum, R. Van Renesse, H. Van Staveren, G. J. Sharp, S. J. Mullendar, J. Jansen, G. van Rossum. Experiences with the Amoeba Distributed Operating System. Communications of the ACM, 1990, Vol. 33, 46-63.
[87] Jochen Liedtke. On u-kemel construction. In: Proceedings of the 15th ACM Symposiun on Operating System Principles, 1995,
[88] Hermann H, Michael H, Jochen L, Sebastian S. The performance of u-kernel-based systems. In: Proceedings of the 16th ACM Symposium on Operating System, 1997,
[89] L4 other papers. URL: http://os.inf.tu-dresden.de/L4/doc.html
[90] R. P. Draves, B. N. Bershad, R. F. Rashid, R. W. Dean. Using continuations to implement thread management and communicateon in operating systems. 1991, Publisher: Department of computer science, Carnegie Mellon University
[91] Alan Dearle, Rex di Bona, James Farrow, Frans Henskens, Anders Lindstrom, John Rosenberg, Francis Vaughan. Grasshopper: An Orthogonally Persistent Operating System. Computing Systems, 1994, Vol. 7, No. 3, 289-312.
[92] Gernot Heiser, Kevin Elphinstone, Stephen Russell, Jerry Vochteloo. Mungi: A Distributed Single Address-Space Operating System In: Proceedings of the Proc 17th Australasian Comp. Sci. Conf, Jan 1994, 271-280.
[93] Sheetal V. Kakkad. Address Translation and Storage Management for Persistent Object Stores. Ph. D thesis, The University of Texas at Austin, 1997.
[94] P. J. Tomasevic, M. V. Milutinovic. Distributed shared memory: concepts and systems. IEEE Parallel&Distributed Technology Systems & applications, 1996, 63-71.
[95] A. M. Mainwaring, D. E. Culler. Active Messages: Organization and Applications Programming Interface. Technical Document, 1995,
[96] Steve Rodrigues, Tom Anderson, David Culler. High-performance local-area communication using fast sockets. Proc in USENIX, 1997,
[97] B. N. Bershad, T. E. Anderson, E. D. Lazowska, H.M. Levy. User-Level Interprocess Commuication for shared memory multiprocessors. ACM transactions on computer system, 1991,
[98] M. N. Nelson, Y. A. Khalidi, P. W. Madany. The Spring file system. 199. 3.
[99] 龚育昌，吴明桥，李宏．一种基于服务体／执行流的新型操作系统构造模型．中国科学技术大学学报，2006，Vol．36，
[100] Jochen Liedtke. Improving IPC by Kernel Design. In: Proceedings of the SOSP, 1993, 175-188.
[101] David Mosberger, Stephane Eranian. IA-64 Linux Kernel Design and Imolementation. Prentice Hall PTR, 2002.
[102] 龚育昌，王立刚，陈香兰，齐骥．一种严格按比例派发服务的混合实时调度算法．软件学报，2006 Vol．17，No．3，611-619．
[103] Xilinx Inc. Xilinx XUP Virtex Ⅱ Pro Development System. 2005, URL: http://www.xilinx.com/univ/xupv2p.html
[104] AAEON Inc. PCM-6892 Data Sheet. 2003, URL: http://www.aaeon.com.br/6892.htm
[105] Title: The Anubis Block Cipher URL: http://paginas.terra.com.br/informatica/paulobarreto/AnubisPage.htm