小型微型计算机系统.pdf

收稿日期:2006207217作者简介:梁克,男,1982年生,博士研究生,研究方向为网络化嵌入式计算技术;张凯龙,男,1977年生,博士研究生,讲师,研究方向为网络化嵌入式计算技术;周兴社,男,1955年生,硕士,教授,博士生导师,CCF高级会员,研究方向为嵌入式、分布式计算.可重构硬件操作系统技术梁克,张凯龙,周兴社(西北工业大学 计算机学院,陕西 西安710072)E2mail:摘要:为了充分发挥可重构计算的高性能和可编程能力,需要将可重构资源和硬件任务纳入到操作系统管理范畴.因此面向可重构计算的操作系统技术可重构硬件操作系统技术成为一个新的研究热点.本文在简要介绍可重构计算系统体系结构的基础上,详细介绍了国内外的研究现状.最后,结合可重构计算系统的特点,阐述了可重构硬件操作系统的关键技术.关 键 词:可重构计算;可重构硬件操作系统;FPGA;硬件任务中图分类号:TP313文献标识码:A文 章 编 号:100021220(2007)1122047204Reconf igurable Hardware Operating SystemL I AN G Ke,ZHAN G Kai2long,ZHOU Xing2she(S chool of Computer,N orthw estern Poly technical U niversity,X ian710072,China)Abstract:It is necessary to manage the reconfigurable resources and hardware tasks for operating system,which can bring high2er performance and programmable ability.Therefore,reconfigurable hardware operating system for reconfigurable computinghas been a novel hot topic in last few yeas.In this paper,the architectures of reconfigurable computing system s are presentedbriefly.A nd then existing research is introduced in detail.Finally,the key technology for reconfigurable hardware operating sys2tem is set forth according to the features of the reconfigurable computing system.Key words:reconfigurable computing;reconfigurable hardware operating system;FPGA;hardware task1引言可重构计算提供了一种新的技术路线与方法,既具有A2SIC的高性能、高速度和高可靠性,又具有微处理器的高度“柔性”和强大的可编程功能.早在20世纪60年代末,美国加利福尼亚大学的Geraid Estrin就提出了重构计算的概念,并研制了原型系统.1986年Xilinx公司第一款基于SRAM的FPGA问世,为可重构计算的实现提供了技术支持,也标志着现代可重构计算的开端.可重构计算基于现场可编程门阵列,即FPGA.可以这样认为,FPGA技术的发展,推动了可重构技术的发展,而可重构技术的进步和需求,也促进了FPGA技术的进步1.然而在传统的设计中,FPGA在系统中类似于A SIC,基本上都是作为硬件加速器由用户直接管理和使用,操作系统作为资源管理者并不参与管理,至多提供一些驱动作为支持.但是,随着可重构计算的深入研究以及FPGA应用范围的不断扩大,人们发现这种方式忽略了FPGA内在的可重构特性以及任务潜在的并行性,增大了系统设计难度,也降低了FP2GA的性能.因此,在最近几年,面向可重构计算的操作系统,即可重构硬件操作系统2技术成为一个新的研究热点.操作系统不仅能够给应用开发者提供便利,而且可以为应用程序提供运行时的支持,可重构硬件操作系统的发展至少可以带来以下好处223:(1)软件可移植性(Portability).对于应用软件,操作系统屏蔽了硬件的细节和差异,对资源进行了抽象.这使得开发者可以专注于软件的功能和性能,而不必担心硬件变化导致程序的大量修改.(2)系统的适应性.在运行的时候,可以通过对硬件的重构以及重新划分系统资源,以达到新建或者终止任务的目的.也可以把原本在CPU上运行的任务迁移到FPGA上运行,以提高运行速度或者达到负载均衡.(3)较高的运行性能.操作系统负责资源和任务管理,以最大限度提高系统的并行性和资源的利用率.特别是对动态和部分可重构系统,选择合适的可重构资源粒度和任务大小,可以极大提高系统的性能.但可重构硬件操作系统又不同于传统的操作系统,它拥有并管理通用微处理器和FPGA两种资源,要处理软件任务和可重构系统特有的硬件任务(Hardware Task),即电路逻辑.这些特点为可重构硬件操作系统的研究提出了新的问题.2可重构计算系统体系结构现有的可重构计算系统不仅包含了可重构逻辑资源,还包括了固定逻辑资源,可能是一个宿主机或者微控制器.按照它们之间的耦合程度,可以将可重构计算系统的体系结构划小型微型计算机系统Journal of Chinese Computer System s2007年11月 第11期Vol128 No.112007分为四类4.2.1独立处理单元模式这是最松散的耦合形式.可重构逻辑一般包含多个FP2GA,作为主处理机(宿主机)外部独立的处理单元,两者通过通用外部接口总线连接起来.显然,这种结构容易构造,方便编程,并且可以根据需要灵活选用不同的宿主机.但是接口总线承担了所有的数据交换,它的性能成为系统的瓶颈,限制了系统的性能加速比.2.2协处理器模式FPGA阵列与CPU之间通过独立的数据总线和控制总线连接,对CPU来看,相当增加了一个协处理器.执行运算时,任务被划分为硬件部分和软件部分,分别在FPGA和CPU上运行.和第一种结构相比,取消了外部通用接口,大大提高了数据交换速度.CPU也可以选择适合应用的各种产品,只要它支持类协处理器的工作方式即可.2.3功能单元模式CPU不是通常商业上可以直接应用的成品,而是以核的形式提供,与可重构逻辑资源集成为一个芯片.可重构资源可以作为主处理器类似于ALU的功能单元,通过系统总线相连,解决了数据交换的瓶颈问题.但这类结构的系统要求按照全定制的方式设计专用集成电路,难度较大.A ltera公司和Xilinx公司各自推出了Excalibur和V irtex2II Pro系列,增加了内嵌式的微处理器核.2.4处理器、存储器和可重构逻辑紧耦合在实现了CPU和FPGA之间高速通信后,增加片上的高速 缓存可以明显提高CPU的性能,因此这种结构实现了CPU、存储器和可重构逻辑集成在同一个芯片上,三者之间以很高的带宽传递数据,称为单芯片可重构计算系统.3相关研究Brebner在文献5中提出了虚拟硬件操作系统的概念,这 是对可重构硬件操作系统的最早研究.他分析了XilinxXC6200 FPGA的特点,认为这种类型的FPGA支持对基本单元(Cell)有选择地进行快速重构,同时每个Cell都有一个寄存器,可以通过寄存器的配置实现FPGA和其他系统模块的交互.由于这些特点,虚拟硬件操作系统把FPGA看作是微处理器的一部分内存,像对内存操作一样对其进行操作.在此基础上,他提出应用程序可以被设计成可交换逻辑单元SLU(SwappableLogicU nit)的集合,而操作系统负责SLU的部署以及通信.为此,他提出两种虚拟硬件模型:sea of accelerator和parallel harness.前一个模型中,每个SLU是独立的,各自完成一定的计算功能,通过对寄存器的操作进行访问;后者的SLU是相互协作的并行处理单元,通过操作系统提供的外围信号和连接设施实现通信.最终,Brebner通过基于XC6200的实验证明了两种模型的可行性.Burns6通过对可重构计算多个应用实例的研究分析,认为一个用来管理FPGA动态可重构的运行时系统必须包含以下几个功能:提供给应用程序访问FPGA的接口;支持多个任务或者应用共享一个FPGA;允许改变一个硬件任务在FPGA上的部署;对硬件任务以及FPGA的抽象表示.基于此,他还介绍了一个可扩展的运行时系统RA GE,核心部件包括虚拟硬件管理器、转换器、配置管理器以及设备驱动.但是Burns没有考虑对FPGA资源的管理以及硬件任务的划分.Shiraz7提出了一个可重构管理器,它包含了一个监视器,用来接收正在运行的应用程序的请求,然后通知装载器把对应的电路配置信息下载到FPGA的某个地方.这里的监视器所扮演的正是操作系统的角色,但是文章没有给出如何在FPGA上寻找适合硬件任务运行的资源.Davis8基于JAVA提出了一个层次性的可重构计算运行环境.他将硬件资源抽象成硬件对象,对这些对象的操作就实现了对底层硬件的操作.最底层是设备抽象层(Device A b2straction L ayer),也是软?硬件映射层;中间是部署?路由层,用来指明硬件对象应该部署的位置以及相互的连接关系;最上层是可重构硬件对象调度器,用来解决多个任务使用同一个硬件对象的问题.遗憾的是,文章没有给出这种层次性体系结构的实现.Jean9定义动态可重构系统是指当一部分可重构硬件在运行的时候允许另一部分重构,并提出了一个针对动态重构系统的资源管理器(RM),负责给任务分配资源或者剥夺正运行任务所占有的资源.文章通过实验证明,引入RM对缩短任务执行时间、提高系统并行性有很大帮助.但是该RM的设计和实现是基于多个FPGA作为可重构硬件资源,没有涉及到单个FPGA内部资源的管理.Rakhmatov10提出的自适应多用户联机可重构引擎AMORE(A daptiveM ultiuser Online Reconfigurable Engine)也是面向多个FPGA组成的硬件集群(hardware cluster)的运行支撑环境,它不仅包含了资源的分配,还包括任务的调度和同步.G.W igley在文献11212较为系统地介绍了可重构硬件操作系统所提供的服务,操作系统的体系结构中包括的功能模块有:划分(Partitioning),实现对任务图的划分;分配(A llocation),决定任务在FPGA上运行的位置,用一个矩形框描述;部署(Placement),实现映射在FPGA上的各个任务节点之间的连接.I M EC(Interuniversity M icro Electronic Center)的可重构计算研究小组在13中认为OS4RS(Operating System forReconfigurable System s)所包含的主要功能有任务的创建?销毁、异构任务的动态迁移、任务之间的相互通信等.他们也指出,支持软、硬件任务调试以及允许对操作系统模块和用户任务的跟踪监控也是可重构硬件操作系统的一个重要特征.H.W alder在14中提出了基于Xilinx V irtex的部分可重构系统运行环境,详尽地介绍了可重构硬件操作系统的体系结构以及相应的硬件任务设计.他把操作系统的功能模块分为两部分,分别运行在CPU和FPGA上,通过OS2Brige进8402小型微型计算机系统2007年行通信.操作系统将FPGA划分为运行操作系统功能的静态区和运行用户任务的动态区.每一个硬件任务有多个输入、输出接口及一个控制接口和CL K信号.W alder开发了XF2Board平台15,并在此之上实现了该硬件操作系统模型.目前国内对可重构硬件操作系统的研究非常少,复旦大学计算机与信息技术系提出了基于统一多任务模型可重构系统的实时操作系统SHUM2UCOS16.它能够跟踪和管理可重配置资源的使用,通过硬件任务预配置技术,提高了资源利用率和任务并行性.定义了两种标准硬件线程接口,对总线型和星型通信拓扑结构提供支持.4可重构硬件操作系统的关键技术4.1统一的任务模型软件任务和硬件任务由于实现方式和物理基础不同,存在较大差异2,4:软件任务是串行执行的指令集合,可以被任意分割成相同大小的子集合,但是硬件任务是二维的逻辑电路,分割比较困难;软件任务的挂起可以通过保存固定数目寄存器的值来以及任务堆栈来实现,而硬件任务的挂起操作与实现方式有关,所要保存的任务状态数目是不固定的;软件任务中,代码和数据是分开的,但是对于硬件任务数据和计算元素(computational elements)之间的区别不是那么明显;软件任务的数量受限于存储器容量,而硬件任务的数量受限于可重构资源的数量.因此,软件任务模型不能直接运用于可重构硬件操作系统中.我们的最终目标是使得软硬件任务对设计者透明,因此,建立统一的任务的模型是可重构硬件操作系统需要解决的关键问题.4.2资源管理相比普通的计算系统,可重构系统中的特殊资源包括:可重构逻辑阵列、路由资源、输入?输出块、外部存储器等.目前大多数研究主要集中在可重构逻辑块的分配,它实现了硬件任务到FPGA的映射,且满足分配的区域不超过可用区域的边界.图1可重构区域的一维(左)和二维模型(右)Fig.1Reconfigurable resource models:1D area model(left);2D area model(right)资源管理部件要随时跟踪可重构逻辑区域的使用情况,当有新的硬件任务到达时,首先判定可用区域的大小是否达到了任务的要求,如果有一个或者多个满足要求的连续区域,按照特定的原则选择最合适的区域,然后返回任务在该区域中部署的位置;如果可用区域不是连续的,则交给任务分割部件进行处理;若空闲区域不满足要求大小,则将任务置于等待队列.显然,可重构逻辑区域的分配是一个典型的装箱问题(bin packing),我们希望有尽可能多的任务被部署到FPGA上运行,以提高FPGA的利用率和系统的并行性能.分配算法的复杂度取决于可重构逻辑区域的模型是一维还是二维模型.前者是将可重构区域划分为槽(slot),后者划分为块(block),如图1所示.其中各个槽或者块的大小可以相同,也可以不同.最大可以是整个可重构逻辑区域,最小可能是FP2GA的每个可重构逻辑单元.可重构区域的分配过程需要考虑以下问题:碎片问题,这是衡量算法有效的主要标准.其中,选择合适的槽或者块的大小是减少碎片的一个重要因素.算法复杂度.当有新的任务不断到达时,需要在较短的时间内完成分配以满足任务的时间约束.对可重构区域的划分,即资源模型的选择,对任务的调度也有影响,17中给出了一种评价机制.4.3任务划分如果空闲的可重构逻辑区域满足任务的资源需求但区域不是连续的,就需要对任务进行分割.关于任务图的逻辑划分在过去的几十年间一直是一个热点问题,并提出了很多算法,比如KL(Kernighan and L in)、FM(Fiduccia andM attheyses)和模拟退火算法4.如何保证划分后子图之间通信量最小是这些算法所要考虑的主要问题,另外,由于任务图的划分针对的是多处理机领域,且假定各个处理机的处理能力是相同的,因此这些算法都是将任务图划分为相同大小的子图,以满足负载均衡的原则.但在可重构计算领域,任务划分将面临一些新的困难:硬件任务大多是被划分为不同大小的子任务,以适应不同大小的可重构逻辑区域;任务划分多是在运行时执行,因此算法复杂性要有严格限制.Woo以及Kuznar等人改进了FM算法,将其应用于可重构计算领域,但是由于算法复杂度太高,并不适用于可重构硬件操作系统4.Purna18提出了时间分割的思想,任务图中每个节点都有自己的A SA P(A s Soon A s Possible)值,用来反映节点执行时间的先后顺序.根据A SA P值来划分任务图,同时保证每个划分不能超过可重构单元的大小SRPU.在此基础上,Purna给出了两种算法:基于层次的划分算法和基于簇的划分算法.前者的目标是获得最大并行度,后者则是尽可能减少划分之间的通信代价.4.4任务调度任务调度是操作系统的关键功能,尤其是实时操作系统.因此针对不同的应用场景,人们提出了很多任务调度算法.针对可重构硬件操作系统,由于软、硬件任务的区别,需要根据可重构系统的特点提出新的调度算法,比如结合任务所需要的可重构资源数量综合考虑.对于可重构系统,同时存在基于空间和基于时间两种多任务19.前者通过多个任务在FPGA上并行执行来实现,后者通过时间片轮转来共享FPGA资源.基于空间的多任务调度实际上是满足时间约束的可重构资源分配问题.而基于时间的多任务调度,有抢占式和非抢占式两种模940211期梁克 等:可重构硬件操作系统技术式.前者允许中断当前执行的任务来运行新任务,后者只有在当前任务执行完毕才能开始新任务.对于抢占式调度,需要解决的首要问题是任务切换.这需要系统在硬件设计上提供以下支持19:必须提供访问所有寄存器以及内部存储器的接口;硬件任务状态的保存以及配置要在较短时间内完成;要对时钟有完全的控制权;如果硬件任务使用了多个时钟,那么所有的时钟频率必须是最慢的时钟频率的整数倍;在任务切换的时刻,要采取一定的措施保证停止时钟是安全的,以免此时如果有读取外部存储器的操作而导致错误.由于目前技术水平的限制,硬件任务的状态保存以及重新配置将耗费较长时间,这对于运行时间短以及需要频繁切换的任务是不能容忍的,因此大多数针对可重构系统的调度算法并不考虑任务切换的情况,如文献20.但是针对可重构系统的抢占式多任务调度是必要的19,特别是当有多个硬件任务同时需要访问某些资源时,轮换执行可以避免任务的“饿死”,以及满足任务的实时性要求.5结论可重构计算技术的出现使计算技术具有比以往更广泛的适应性和灵活性,目前已经在神经网络、多媒体、信号处理等方面取得应用.而随着深亚微米VL SI技术的迅速发展,以FPGA为先导的可重构计算技术将会朝着更高性能和更广的适应性不断发展.可重构硬件操作系统技术作为可重构计算领域的基础研究,它的发展将有利于可重构计算技术优势的更好发挥,从而推动可重构计算技术在各个领域广泛应用.References:1 L i Ren2fa,Zhou Zu2de,Chen You2ping,et al.Hardware for re2configurable computing J.Journal of Computer Research andDevelopment,2003,40(3):5002506.2 HerbertW alder,M arco Platzner.Reconfigurable hardware oper2ating system s:from design concepts to realizationsC.In Pro2ceedings of the 3rd International Conference on Engineering ofReconfigurable System s and A rchitectures(ERSA),2842287.CSREA Press,June 2003.3 Diessel O,W igley G.Opportunities for operating system s re2searchinreconfigurable computing R.Technical ReportACRC2992018,Advanced Computing Research Centre,SchoolofComputer and Information Science,U niversity of South Aus2tralia,1999.4 Grant Brian W igley.An operating system for reconfigurablecomputingD.U nversity of South Australia,2005.5 Brebner G.A virtual hardware operating system for the xilinxXC6200 C.In 6thInternational Workshop on Field2Pro2grammable Logic and Applications(FPL96),Darm stadt,Ger2many,1996.6 Burns J,Donlin A,Hogg J,et al.A Dynam ic reconfiguration run2ti me system C.In IEEE Symposium on FPGA s for CustomComputing M achines(FCCM 97),Napa Valley,CA,U SA,1997.7 ShiraziN,LukW,Cheung P.Automating production of run2ti mereconfigurable designsC.In IEEE Symposium on FPGA s forCustom Computing M achines(FCCM 98),Napa Valley,CA,U SA,1998.8 Davis D,BarrM,Bennett T,et al.A Java development and run2ti me environment for reconfigurable computingC.Presented at9th Symposium on Parallel and Distributed Processing(IPPS?SPDP98),O rlando,FL,U SA,1998.9 Jean J,Tomko K,Yavagal V,et al.Dynam ic reconfiguration tosupport concurrent applicationsJ.IEEE Transactions on Com2puters,1999,48():5912602.10 Rakhmatov D,V rudhula S,Brown T,et al.Adaptive multiuseronline reconfigurable engine J.In IEEE Design&Test ofComputers,2000,17():53267.11 GrantW igley,David Kearney.The development of an operatingsystem for reconfigurable computingC.In Proceedings of theIEEE Symposium on FPGA s for Custom Computing M achines(FCCM).IEEE CS Press,April 2001.12 W igley G,Kearney D.Research issues in operating system s forreconfigurable computing C.In International Conference onEngineeringofReconfigurableSystem sandA lgorithm s(ERSA02),2002,CSREA Press.13 M arescaux T,M ignolet J Y,BarticA,et al.Networks on chip ashardware components of an OS for reconfigurable system sC.In Proceedings of the 13th International Conference on FieldProgrammable Gate A rrays(FPL03),volume LNCS 2778,Springer,9 2003,5952605.14 HerbertW alder,M arco Platzner.Reconfigurable hardware oper2ating system s:from design concepts to realizationsC.In Pro2ceedings of the 3rd International Conference on Engineering ofReconfigurable System s and A rchitectures(ERSA),CSREAPress,June 2003,2842287.15 Herbert W alder,Samuel Nobs,M arco Platzner.XF2Board:aprototyping platformfor reconfigurable hardware operatingsystem sC.In 4th International Conference on Engineering ofReconfigurable System s and A rchitectures(ERSA04)LasVe2gas(NV),U SA,June 2004.16 Zhou Bo,W ang Shi2ji,Q iuW ei2dong,et al.SHUM2UCOS:a rea2ti me operation system for reconfigurable system s using uniformmulti2task modelJ.Chinese Journal of Computers,2006,29(2):2082218.17 HerbertW alder.Operating system design for partially reconfig2urable logic devicesD.Sw iss Federal Institute of Technology(ETH),Zurich(Sw itzerland),April 2005.18 Purna K,Bhatia D.Temporal partitioning and scheduling dataflow graphs for reconfigurable computers J.IEEE Transac2tions on Computers,1999,48():5792590.19 Si mm ler H,Levinson L,M anner R.M ultitasking on FPGA co2processors C.Presented at 10th International Workshop onField2Programmable Logic and Applications,V illach,Austria,2000.20 Christoph Steiger,Herbert W alder,M arco Platzner.Operatingsystem s for reconfigurable embedded platform s:online schedul2ing of real2ti me tasks J.IEEE Transactions on Computers,2004,53(11):139221407.附中文参考文献:1 李仁发,周祖德,陈幼平,等.可重构计算的硬件结构J.计算机研究与发展,2003,40(3):5002506.16周博,王石记,邱卫东,等.SHUM2UCOS:基于统一多任务模型可重构系统的实时操作系统J.计算机学报,2006,29(2):2082218.0502小型微型计算机系统2007年