（计算机系统结构专业论文）可重构嵌入式系统样机平台与操作系统研究.pdf

摘要 摘要 目前可重构计算技术已成为计算系统研究中的一个新热点。作为一种新的体 系结构，可重构计算同时具有软件的灵活性和硬件的高性能，在嵌入式系统和高 性能计算等领域获得了越来越广泛的应用。然而操作系统和应用开发工具目前仍 是可重构系统研究中的一个薄弱之处。 本文重点研究可重构嵌入式系统的操作系统支持，而创建一个合适的样机平 台是开展进一步研究的基础。本文主要进行几个方面的研究工作： 首先，对目前主要的可重构计算平台进行了分类，提出了操作系统对于可重 构平台的要求，然后给出了可重构嵌入式系统硬件平台的设计方案。 第二，针对可重构嵌入式系统样机平台，提出并初步实现了一个基于e c l i p s e 的集成开发环境以支持样机平台上的应用开发。它采用自项向下的软硬件协同设 计流程：利用插件技术集成了不同抽象层次的设计工具和外部的e d a 工具；通 过口库和内部通信机制实现各设计层次间的数据交换和设计人员之间的协作； 其口库集成了不同抽象层次、不同来源和不同实现方式的异构口。 第三，提出了一个r t l 级异构口集成算法，并在集成工具中得到了实现。 该算法以及采用该算法的r t l 级设计工具利用参数化类隐藏了口的不同实现方 式；层次化的集成方式和灵活的互连逻辑口能够支持非常复杂的口互连结构； 通过总线转换接口的包装，实现了不同总线接口m 的集成；通过虚拟设计和自 动化的口集成，显著地降低了设计的工作量。 第四：在分析软硬件任务区别的基础上提出统一多任务模型的操作系统框 架；然后给出操作系统中的任务问通信设计方案，包括硬件任务与接口设计和通 信控制器的设计。最后给出基于l i n u x 的可重构操作系统设计方案。该操作系统 具有以下特点：以l d n u x 为基础扩展，兼容p t h r e a d 等现有的并行编程模型规范， 能够更好地支持应用系统的开发；通过硬件任务桩线程实现任务间的通信，简化 了硬件任务的实现，并能完全兼容现有的软件任务问通信机制；支持动态部分可 重构的f p g a ，动态创建硬件任务，更有效地管理硬件资源。 最后，研究了硬件任务的在线放置与调度问题。为了进行可重构硬件任务的 动态管理，要为硬件任务在可重构器件上找到合适的配置位置，并且进行配置后 才能运行硬件任务。在总结了现有工作的基础上，针对硬件任务的调度提出了最 早识别的概念，并首次实现了两个最早识别的在线调度算法，新算法在调度质量 上显著优于原有的算法，而运行时开销没有明显增加。此外还提出了一个硬件任 务放置算法，与原有算法相比，新算法在放置效果和运行时开销方面均有优势。 摘要 关键字： 可重构计算、样机平台、口集成、实时操作系统、硬件任务放置、硬件任务 调度 中图法分类号： t p 3 1 6 摘要 a b s t r a c t a san e w c o m p u t i n ga r c h i t e c t u r e , r e c o n f i g a r a b l ec o m p u t i n gh a sb c 咖c as u b j e c t o fag r e a td e a lo fr e s e a r c h i t sk e yf e a t u r ei st h ea b i l i t yt op e r f o r mc o m p u t a t i o n si n h a r d w a r et oi n c r e a s ep e r f o r m a n c e ，w h i l e r e t a i n i n gm u c ho ft h ef l e x m i l i t yo fa s o f t w a r es o l u t i o n r e c o n f i g u r a b l ec o m p u t i n gi ss p r e a d i n gw i d e l yi nv a r i o u sd o m a i n s f r o me m b e d d e ds y s t e mt o h i g hp e r f o r m a n c ec o m p u t i n g h o w e v e r , d e v e l o p e r s w o r k i n gw i t hr e c o n f i g u r a b l ec o m p u t i n gs t i l ll a c kt h es u p p o r to fo p e r a t i n gs y s t e m sa n d c o n v e n i e n ta p p l i c a t i o nd e v e l o p i n gt o o l s t h i sp a p e rm a i n l yf o c u s e so nt h eo p e r a t i n gs y s t e ms u p p o r tf o rr e c o n f i g u r a b l e c o m p u t i n g , a n db u i l d i n gas u i t a b l ep r o t o t y p ep l a t f o r m i st h eb a s e o ff u r t h e r r e s e a r c h i n g t h em a i nw o r k so ft h i sp a p e ra r es h o w n a sf o l l o w ： f i r s t l y , t h i sp a p e rc l a s s i f i e sc u r r a n tm o d e mr e c o n f i g n r a b l ec o m p u t i n gp l a t f o r m s i n t os e v e r a lg r o u p s t h ep r o p e r t i e so fr e c o n f i g u m b l ec o m p u t i n g p l a t f o r m sr e q u i r e db y a no p e r a t i n gs y s t e ma r eg i v e n t h e nt h ed e s i g no far e c o n f i g n r a b l ee m b e d d e d s y s t e m p r o t o t y p ep l a t f o r mi sp r e s e n t s e c o n d l y , t h i sp a p e rp r e s e n t sa n di m p l e m e n t se m b e d d e ds y s t e mi n t e g r a t e d d e s i g ne n v i r o n m e n t ( e s m e ) b a s e do nt h ee c l i p s ep l a t f o r m , f o rs u p p o r t i n gt h e a p p l i c a t i o nd e v e l o p m e n to nt h ep r o t o t y p ep l a t f o r m e s i d es u p p o r t se m b e d d e d s y s t e md e s i g na ts e v e r a la b s t r a c tl e v e l sa n da c h i e v e sat o p - d o w nd e s i g np r o c e d u r e t h ed e s i g nt o o l sa te a c hl e v e la n do t h e re x t e r n a le d at o o l s 撒i n t e g r a t e di n t oa w h o l ee n v i r o n m e n t w i t ht h em a n a g e m e n to ft h ei pd a t a b a s e , e s i d ep r o v i d e sw e l l s u p p o r tf o rt e a mc o o p e r a t i o n t h i r d l y , ah e t e r o g e n e o u si pi n t e g r a t i o na l g o r i t h mi sp r e s e n t e da n di si m p l e m e n t e d i ne s i d e i ta d o p t sh i e r a r c h i c a li n t e g r a t i o na n df l e x i b l ec o n n e c t i o ni p sw h i c he n a b l e i ts u p p o r tv e r yc o m p l e xi pc o n n e c t i o ns t r u c t u r e s i p sw i t hd i f f e r e n tb u si n t e r f a c e sc a l l b ei n t e g r a t e df r e e l yv i ab u sp r o t o c o lc o n v e r t e r s t h ep r a c t i c eo fv i r t u a ld e s i g n t e c h n i q u ea n da u t o m a t i ci pi n t e g r a t i o nr e d u c et h ec o m p l e x i t yo fs y s t e md e s i g n s i g n i f i c a n t l y f o u r t h l y , b a s e do nt h ee s s e n t i a ld i f f e r e n c e sb e t w e e ns o f t w a r e t a s k sa n d h a r d w a r e - t a s k s ，t h i sp a p e rp r e s e n t sa no p e r a t i n gs y s t e mf r a m e w o r kf o rr e c o n f i g u r a b l e s y s t e m su s i n gu n i f o r mm u l t i - t a s km o d e l t h e nt h ei n t e r - t a s kc o m m u n i c a t i o n a r c h i t e c t u r ei sp r e s e n t e d ，a n dal i n u xb a s e do p e r a t i n gs y s t e mf o rr e c o n f i g u r a b l e m 摘要 c o m p u t i n gi sp r e s e n t e d ah a r d w a r et a s ks t u bt h r e a di sc o m b i n e dt oe a c h h a r d w a r e t a s kt od e a lw i t hi n t e r - t a s kc o m m u n i c a t i o n s t h i ss i m p l i f i e sh a r d w a r et a s kd e s i g n i n g , a n dm a k e st h eo p e r a t i n gs y s t e mc o m p a t i b l ew i t hc u r r e n ts o f t w a r ep r o g r a m m i n g m o d e l sa n di n t e r - t a s kc o m m u n i c a t i o nm e c h a n i s m s i ts u p p o r t sd y n a m i cp a r t i a l l y r e c o n f i g u r a b l ef p g a sa n dd y n a m i ct a s kc r e a t i o n , s oi t c a nm a n a g eh a r d w a r e r e s o u r c e sm o r ee f f i c i e n t l y f i n a l l yw cf o c u so nt h ep l a c e m e n ta n ds c h e d u l i n go fh a r d w a r et a s k so n r e c o n f i g u r a b l e d e v i c e s p r e v i o u sw o r k sa r cs u m m a r i z e d , a n dt h en o t i o no f r e c o g n i t i o n - e a r l i e s ti si n t r o d u c e d , t h a ti st h ea l g o r i t h mc a l la r r a n g et h es t a r tt i m eo fa n e w l ya r r i v e dt a s k a s e a r l y a sp o s s i b l e af a s tp l a c e m e n ta l g o r i t h ma n dt w o r e c o g n i t i o n - e a r l i e s to n - l i n es c h e d u l i n ga l g o r i t h m sa r ep r o p o s e d t h ee v a l u a t i o n r e s u l t ss h o wt h a to u rn e ws c h e d u l i n g a l g o r i t l m la c h i e v e st h eb e s tp e r f o r m a n c e c o m p a r e dw i t hp r e v i o u sa l g o r i t h m s w h i l eh a saq u i t el o wm n t i m ec o s t , a n dt h e p l a c e m e n ta l g o r i t h mi so n e o ft h eb e s ta l g o r i t h m sa m o n ga l lp r e v i o u sw o r k s k e y w o r d ：r e c o n f i g u r a b l ec o m p u t i n g , p r o t o t y p ep l a t f o r m , l l i n t e g r a t i o n , r e a l - t i m e o p e r a t i n gs y s t e m , h a r d w a r et a s kp l a c e m e n t , h a r d w a r et a s ks c h e d l l l i n g i v 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均己在论文中作了明确的声明 并表示了谢意。 作者签名： 铜髻j 6 论文使用授权声明 日期：塑1 2 ：! ：z 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 靛。酬型一名：衄 作者签名：! 翌茎堑导师签名：q ，：! 堡趴期：丝! ! ：! ：z 可重构嵌入式系统样机平台与操作系统研究 1 1 研究背景 第1 章引言 在传统的计算系统中，算法可以采用两种不同的方法来实现。一是用软件编 程实现，并在通用处理器上运行。该方法灵活性高，通过编写软件指令就可改变 系统的功能，但指令的串行执行以及指令集的有限性使得通用处理器的性能往往 不能满足要求：二是采用硬件功能模块如专用集成电路( a p p l i c a t i o ns p e c i f i c i n t e g r a t e dc i r c u i t s ，a s i c s ) 实现。这种方法具有很高的执行速度和运算精度， 但功能单一、灵活性差，要想实现不同的算法必须重新设计集成电路，开发成本 和周期都很高。 可重构计算作为一种新的体系结构，采用可编程的硬件模块来实现计算，填 补了软硬件之间的鸿沟，既保证了系统的性能( 比软件高) ，又保证了灵活性( 比 硬件灵活) 【1 】。以现场可编程门阵列( f i d dp r o g r a m m a b l e g a t e a r r a y s ，f p g a s ) 为代表的可重构逻辑器件可以被任意次地重新配置，使得一片可重构器件能够在 不同时间运行不同的硬件算法，就像不同的算法运行在传统的处理器上一样。 可重构计算通过在时域上重用硬件资源来完成对计算任务并行性的利用，可 简单定义为至少包含一个可变硬件模块的计算系统，此模块的功能应能够被最终 用户修改。修改过程主要是通过对系统中的可编程器件进行重构或部分重构来实 现的。利用这一技术设计的可重构系统，能在只增加少量硬件资源的情况下，将 软件实现和硬件实现的优点合二为一。它的出现使得过去传统意义上硬件和软件 的界限变得模糊，硬件系统得以软件化【2 】。 从可重构系统被提出的一开始，它就以在各种应用场合表现出的优越性能而 倍受瞩目。 早期最成功的例子是s p l a s h2 。在基因组分析的应用中，它比当时的s p a r c 1 0 工作站的运算速度整整快了2 5 0 0 倍；若做灰度图象的中值滤波器，则比s p a r c 1 0 快了几乎1 4 0 倍【3 ，4 】。需要指出的是，s p l a s h2 使用了1 7 块f p g a 而s p a r c 1 0 只有1 个c p u ，按芯片数平均，在以上两个应用中每块f p g a 分别使性能提 高了1 4 7 倍和8 倍，这一结果是相当惊人的，并引发了学术界对可重构计算的巨 大兴趣。 随着应用场合的不同，可重构计算系统对性能的提高程度也不大相同。一般 情况下，按系统中f p g a 的芯片数量进行平均，每块f p g a 能使运算速度提高7 3 0 倍左右。只有少量特别的例子能使速度提得更高【5 】。一般系统内f p g a 数 可重构嵌入式系统样机平台与操作系统研究 量越多，总体的性能就越高，而平均每块芯片提高的速度倍数越低。 可重构计算系统已被广泛地应用于从嵌入式系统到高性能计算的许多领域 【6 】，包括数字图像处理、网络安全、生物信息学和超级计算等。 1 2 可重构计算概述 1 2 1 可重构计算的概念 人们从不同的研究角度出发，对可重构计算的理解也不尽相同。目前比较公 认的定义由加州大学伯克利分校可重构技术研究中心的a n d r ed e h o n 和j o h n w a w r z y n e k 于1 9 9 9 年a c i d 设计自动化国际会议上提出的一种广义的定义吲， 将其视为一类计算机组织结构，并具有区别于其它组织结构的两类突出特点： 1 ) 制造后芯片的定制能力( 区别于a s i c ) ； 能实现很大程度的算法到计算引擎的空间映射( 区别于通用处理器) 。 凡具备以上两特点的计算方式都属可重构计算的范畴。 图1 1 所描述的基本体系结构可以基本概括和抽象目前已出现的可重构计算 平台。这种结构结合了可编程处理器和可编程的硬件，因而能够提供更多的设计 探索空间，同时也兼具了硬件的高性能和软件的灵活性，这也是可重构计算的研 究初衷和目标。 图1 1 可重构计算的基本结构 1 2 2 可重构计算的起源 可重构计算虽然直到最近才受到重视并逐渐流行起来，实际上其概念早在2 0 2 可重构嵌入式系统样机平台与操作系统研究 世纪6 0 年代就已经提及。美国加利福尼亚大学的g e r a i de s t r i n 提出可重构的概 念，并研制了原型系统。该系统由非柔性但可编程的处理器和柔性的由程序控制 重构的数字逻辑部件两部分组成【8 】。尽管系统软件和硬件的抽象层次不高但均 可编程重构。由于当时实现技术尚不完善，e s t d n 研制的系统只是其设计理念的 粗略近似。但这种结构奠定了以后可重构计算系统的核心基础。 1 9 8 6 年x i l i n x 公司开发出世界上第一片现场可编程门阵列( f p g a ) 芯片， 并在实践中获得了很好的应用效果。到上世纪九十年代初期，出现了一些以 f p g a 为核心开发的面向某一类应用的计算设备。一般做法是将一片或多片 f p g a 、c p u 和存储器等组合到一起，f p g a 作为协处理器加速c p u 程序中的一 些可并行执行成分( 一般为循环体) ，同时c p u 还要管理f p g a 的重构。当时这 种结构的运算设备被称为可重构计算机，这种工作方式也被称为重构计算。它们 在一些特殊的应用领域显示出了超强的计算性能和数据处理能力，尤其对于算法 内部蕴涵很大的并行性和流水性的应用表现尤为出色，并显著地降低了设计的费 用。其中最具有代表性的是美国超级计算机研究中心( s u p e r e o m p u t i n gr e s e a r c h c e n t e r ) 在1 9 9 2 年研制的s p l 勰h2 1 4 ，它对基因组测序的计算工作起到了极大的 加速作用。该研究成果的成功极大增强了人们对可重构芯片进一步研究和应用的 信心，也引导人们开始对其重新认识和定位。九十年代中后期相继出现了一些著 名的研究项目，其中包括c a r p 9 】，r a w 1 0 】，p i p e r e n c h 1 1 】，c h a m e l e o n 1 2 】， m o r p h s o s 1 3 等。 1 2 3 可重构计算的特征 从本质而言，可重构计算是一种时空域上的计算模式【1 4 】，而传统的通用处 l t ：- x 1 2 ：- ao 1 2 ：- t 2 + 1 2 1 2 _ y ：一t 2 + x a yy c ( a ) 传统处理器：时域计算a s l c i 争态r c ：空域计算( c ) 动态r c ：时空域计算 图1 2 时空域计算模式 3 可重构嵌入式系统样机平台与操作系统研究 理器计算是时域上的计算模式，a s i c 则位于空域上。图1 2 显示了它们的差别。 处理器具有通用的、固定的结构，按照指令的命令执行相应的操作。在处理 器上的计算首先要将问题分解为一条条可以在处理器上运行的指令，这些指令以 时间的顺序依次流过处理器，产生时域的运算序列。图1 2 ( 幻显示了传统处理器 计算表达式y = a o 譬+ b * x + c 的过程。处理器被简单地表示为由保存数据的 寄存器和执行运算功能的a l u 部件组成。该问题被分解为5 条指令，依次执行 每条指令将得出最终结果。从运算过程可知，虽然通用处理器的硬件结构固定不 变，但依然可以通过指令序列的不同来实现不同的功能，因此具有很高的通用性。 但( 1 ) 出于同样的原因，由于其硬件结构是通用的，并不为特定的目标算法优化； ( 2 ) 同时为照顾通用性，其关键路径上不可避免地存在一些不必要的计算，比如 即使工是1 2 位整数，计算过程也必须运行在3 2 位的a l u 通路上，造成性能浪 费；( 3 、所有运算过程必须映射到处理器指令集上，指令集的有限性造成了映射 效率下降，如即使处理器有可能同时执行一条加法和一条乘法，但通常必须映射 到2 条指令上，对非乱序执行结构或同时发射指令数不足时，不能充分发挥处理 器的本身的计算带宽；( 4 ) 数据通常保存在全局r a m 中，计算时需装载入寄存器， 然而全局r a m 的访问延迟非常大；( 5 ) 对于循环、跳转等运算不可避免地要安排 改变程序流向的控制指令，但这些控制指令就自身而言对数据运算是毫无用处 的，自自浪费了时钟周期。这诸多的原因，使得通用处理器计算方式的运算性能 并不理想。 一种改进方式是使用运算能力更强的定制指令集处理器( a s l e ) 、超长指令集 处理器( v u w ) 或数字信号处理器( d s p ) 等。它们继承了通用处理器易编程 的优点，通过提供更多的硬件运算单元( 如多乘法部件) ，甚至使用专门的硬件 加速协处理器( 如向量处理器) ，以及增加特殊指令( 如乘加指令) 或提供更宽 的指令( 如v u w ) ，提高了处理器对具有某类运算特征的应用领域的处理能力， 如多媒体处理和网络处理等。但很显然，它们应用范围较为受限，甚至导致了在 通用处理方面的不足( 如d s p 的程序控制能力较弱) 。 终极提速方案是使用硬件执行上述算法。如图1 2 ( b ) 所示。考虑到y = 4 + b * x + c 总共执行3 次乘法2 次加法，在硬件上专门制作3 个乘法器，2 个加 法器，并按照计算要求的通讯关系安排乘法器和加法器之间的连接，于是能够在 一个周期内完成所有的运算过程。如果x 宽度只有1 2 位，那么只需设计1 2 位的 乘法器，比3 2 位乘法运算具有更快的速度。硬件针对算法的专门性优化是硬件 具有高性能的原因之一。同时，硬件执行是全空间域、全芯片内的并行执行；其 次，硬件方式中只有必需的数据流过处理单元，没有无关紧要的指令流和中间数 据流，去除了相互之间的依赖关系，进而也消除了访问指令所需的存储器带宽。 4 可重构嵌入式系统样机平台与操作系统研究 这些原因使得硬化计算成为高性能计算中的一种值得期待的计算方式。 早期采用定制应用专用芯片a s l c 的方式来硬化计算。但a s i c 一经设计， 其功能便不能发生变化。尤其是在制造后，用户不能做任何的编程，除了一些参 数上的调整等。a s i c 的应用范围比a s i p 更为狭窄，但却是性能最高的方案。 用户要想改换用其它算法，必须重新设计电路、重新开模制片，开发难度、开发 周期以及开发费用等都比较高，使得a s i c 只有在大批量生产的时候才能显示出 其优越性。 另一种方法是采用硬件可编程器件如f p g a 、c t l d 等来硬化算法。这种方 式无需一次性工程费用，设计快速方便，逐渐有取代a s l c 的趋势。这就是静态 可重构计算。设计时根据算法的特点，设计出最优化的硬件电路，并在运行过程 中保持该电路不变。可编程性使得静态可重构计算比a s i c 具有更高的灵活性。 但为了提供可编程能力，器件必须付出额外编程通路的开销；其次，算法必须映 射到器件特定的逻辑运算资源和布线资源上，并不能完全自由地设计。因此性能 要比a s i c 大约低一个数量级，但比通用计算高出两个数量级左右的性能依旧使 得静态可重构成为引入注目的高速运算方式。 再进一步，将算法在整个运行过程中继续细分，在不同的时刻研究算法的不 同特征。假设我们开始要求计算y = 彳譬4 - 曰+ c ，随后随着时间的推移要求 计算y = 口+ 工勺0 + 伊啧4 - a 。后者也需要3 个乘法器和2 个加法器，但它们之 间的连接关系与前者不同。也就是说，连接结构的不同造成了系统具有不同的功 能。如果需要改变硬件以适配这两个不同的表达式，这在a s i c 上是不可能做到 的，在静态重构计算中要求关机并重新加载硬件设计，这通常是不合适的。动态 可重构计算允许在运行时改变硬件的功能，匹配目标算法的动态特征，如图1 2 ( c ) 所示。动态可重构计算的这种在时域上高度灵活的特点，更能充分发挥硬件的高 速计算的能力。 性 能 灵活性 图1 3 四种计算模式的比较 根据以上分析，可得出四种计算模式在性能和编程灵活性方面的优劣比较， 5 可重构嵌入式系统样机平台与操作系统研究 参见图1 3 。可重构计算作为一种新型的计算模式，弥补了通用计算和专用计算 之间的空白，在大部分有高性能要求的专用应用领域中，是一种较为合适的解决 方案。 1 3 可重构系统研究中存在的问题 可重构计算的发展现状是硬件远远领先于软件。当前，f p g a 的容量正按照 摩尔定律的速度发展，大容量的f p g a 不仅提供了大量的可编程硬件资源，还集 成了乘法器、存储器和微处理器等功能部件，形成了一个完整的可编程片上系统。 多个硬件计算模块可以在大容量f p g a 上并行地运行，动态部分可重构的f p g a 使得硬件计算模块可在运行时动态配置，这进一步提高了其性能优势。另一方面， 应用开发工具和设计方法却还很原始，远远跟不上可重构器件的发展【6 】。 目前各个公司及研究机构发布的可重构计算平台均沿着各自的路线发展，缺 少统一的计算模型。绝大多数的可重构计算平台上的开发工具还不成熟，软硬件 的设计还是分开完成的，很少有统一的系统级的软硬件协同开发平台，给实际应 用造成了巨大障碍。这方面的方法学和具体技术还很不完备，尚需进一步的探索 和研究。 动态可重构系统的实现需要一个运行时环境对丰富的可编程硬件资源进行 有效的管理。这也对开发工具提出了更高的要求。 目前可重构系统的应用开发类似于早期的计算机软件开发，那时程序员需要 细致地安排处理器、内存、外存和外设等硬件资源的使用，操作系统的出现使得 程序员从这些琐碎的细节中解脱出来。同样，在可重构计算中也需要一个操作系 统来管理新的可重构硬件资源，屏蔽硬件的细节，并向开发人员提供高层次的编 程模型。 可重构计算在体系结构等方面还有其他一些需要进一步研究的问题，但与本 文的工作无关，这里就不详细展开了。 1 4 本文的工作 本文针对可重构嵌入式系统样机平台与操作系统支持进行了一定的探讨，设 计了可重构嵌入式系统硬件平台和集成开发工具，并在统一多任务模型的指导下 设计了基于l i n u x 的支持可重构计算操作系统，同时对硬件任务调度和放置问题 进行了研究。 本文共分8 章，其组织结构如下： 第1 章：引言。首先介绍可重构计算的概念、起源和特征，然后分析可重构 6 可重构嵌入式系统样机平台与操作系统研究 系统研究中存在的问题，最后介绍本文的工作和文章的组织结构。 第2 章：可重构计算平台。首先介绍可重构计算平台的发展状况和几个典型 的平台的实现，并对可重构计算平台作了分类。然后介绍可重构计算平台的操作 系统支持以及操作系统可重构计算平台的要求。最后提出了可重构嵌入式系统硬 件平台的设计方案。 第3 章：可重构嵌入式系统集成设计环境。首先介绍自顶向下的软硬件协同 设计流程，其次介绍集成设计环境的总体结构，并给出数据交换和团队协作的实 现，最后介绍口的库组织与管理。 第4 章：异构口的快速集成。首先介绍研究背景和口库的实现，然后给出 球集成算法以及复杂互连逻辑的生成和总线协议转换接口的实现，最后通过实 例分析算法的效果。 第5 章：统一多任务模型与操作系统设计。首先在分析软硬件任务区别的基 础上提出统一多任务模型的操作系统框架。然后给出操作系统中的任务间通信设 计方案，包括硬件任务与接口设计和通信控制器的设计。最后给出基于i j n u x 的 可重构操作系统设计方案，包括可重构资源管理和硬件任务管理。 第6 章：硬件任务的放置算法。首先介绍相关领域的研究现状，然后提出一 个新的放置算法。最后通过模拟评估比较算法的性能。 第7 章：硬件任务的调度算法。首先介绍相关领域研究的现状，并提出2 个 新的调度算法。然后分析了调度算法与放置算法间的关系。最后通过模拟评估比 较算法的性能。 第8 章：结论和展望。对全文的工作进行总结，归纳本文的重要创新点，并 提出进一步的研究方向和设想。 7 可重构嵌入式系统样机平台与操作系统研究 第2 章可重构计算平台 可重构计算平台的体系结构是由f p g a 发展而来的。目前已见报道的多数平 台都采用了多f p g a 的结构，根据应用场景的不同，可能还包含多c p u 或专用 存储器【1 5 】。另外为了减轻通信和访存的开销，也有不少研究项目将处理器和可 重构单元整合到一块芯片上。总体来看，现代可重构计算平台的发展过程基本上 可以分为三个阶段i x 6 ，如图2 1 。第一代可重构计算平台的主要目标是提供一 套高性能计算平台，其典型代表为s p l a s h 系统。在这个过程中，研究者们发现 通信、互连以及重构时间都存在改进和提升的空间，因此开发了第二代可重构平 台( 典型代表有g a r p 、r a w 、s p l a s h 等) ，并提出了一些方法和手段进行改 善，比如部分可重构、上下文切换以及动态重构等。进一步，开发了主要面向数 据流应用的第三代可重构系统。 第一代 i 第二代第三代 图2 1 可重构计算平台的发展 2 1 典型的可重构计算平台 2 1 1s p l a s h 和s p l 躺h 2 从概念上讲，s p l a s h 和s p l a s h 2 可以看做由小的处理单元构成的线性阵 列，这也使得s p l a s h 计算平台非常适合于线性脉动计算，在诸如文本检索【1 7 】、 目标识别【1 8 】、边缘检测【4 】、数据库检索【1 9 】等应用中s p l a s h 平台显示了良好 的加速效果。s p l a s h2 系统包括一台s u ns p a r c 工作站，一块接口板，一至1 6 8 可重构嵌入式系统样机平台与操作系统研究 块s p l a s h 阵列板( 菊花链方式连接) 。图2 2 为s p l a s i - 1 2 计算平台的结构【3 】。 图2 2s p l a s h 2 系统结构图 接口板包括4 路d m a 通道( 两路输入，两路输出) 。每路带宽为5 0 m b y t e s s ， 通过2 5 6 个字的f i f o 与主机通信。用户可以通过定制f p g a ( x l ，x r ) 来 对输入输出数据进行预处理，其时钟主频可以从1 0 k 4 0 m h z 选择。 阵列板一共包括1 7 个处理单元( p r o c e s s i n ge l e m e n t s ，p e s ) ，处理单元x 1 x 1 6 通过交叉开关完成全互连，其输入输出由x 0 进行管理。每个p e 包括 一片x c 4 0 1 0 和5 1 2 k b y t 船的存储器，其中存储器采用统一编址，可以被主 机直接访问。每个p e 可以通过3 6 位的数据总线与左右相邻的p e 或者交叉 开关通信。 主机的信息通过x l 和x 0 ( x 1 ) 之间的3 6 位s i m d 总线传输。多块阵列板 可以扩展为更大的线性阵列，所有阵列板的输出通过r b u s 送回到s p a r e 工作 站。 除了p e 以外，交叉开关也是可重构的。每个开关可以存储8 种配置，每种 配置反映了其1 6 个端口的互连结构。被配置为输入的端口可以连接到任意一个 被配置为输出的端口上，这样通信节点之间就可以很容易被设定为点对点、多播 或者广播的方式。 s p l a s h 支持多种编程模型，包括s i m d 模型，多维脉动计算模型。编程环 境上，s p l a s h2 系统采用v h d l ，并为此开发了相应的支持库，库中包含 s p l a s h 系统所定义的数据类型、过程和其他一些部件。为了方便开发和仿真， 9 可重构嵌入式系统样机平台与操作系统研究 s p l a s h 系统还提供了一些c 语言的通信库支持。 2 1 2g a r p g a r p 是由u cb e r k e l e y 的b r a s s 研究小组启动的研究计划【9 ，2 0 】。其目标 是将可重构计算单元与普通r l s c 处理器集成到一块芯片上，借以探索可重构计 算对于应用的加速能力。图2 3 为g a r p 系统的模块框图。 图2 3g a r p 系统的模块框图 g a r p 采用了m i p s 作为其主处理器的原型，通过扩展指令集获得对可重构计 算的支持。其可重构部分采用x i l i n x4 0 0 0 系列构成阵列，同时规定每行必须包 括2 4 个模块。至于阵列包括多少行，则由具体的应用决定。 可重构阵列的配置和执行由主处理器完成。扩展指令集主要用于支持可重构 计算，包括在可重构阵列和处理器之间传输数据。在c a r p 系统中，所有的配置 数据都存入主存，并采取了很多措施来减少配置带来的延迟，包括支持部分可重 构和配置重定位，以及采用配置存储器c a c h e 。 g a r p 系统同时还包括了支持c 语言的编译器。该编译器能够在预处理阶段 分析用户程序，自动提取其中适合可重构阵列执行的部分。被提取出来的部分可 以被离线综合为配置文件，其余部分依然在m i p s 上执行。 2 1 3c h a m e l e o n c h a m e l e o n 可重构通信处理器( r e c o n f i g u r a b l ec o m m u n i c a t i o n sp r o c e s s o r ， r c p ) 【1 2 】是由c h a m e l e o ns y s t e m s 公司设计的工业界第一款可重构处理器。r c p 内部包含一个3 2 位嵌入式处理器，3 2 位可重构单元，高速系统总线和可编程的 l o 可重构嵌入式系统样机平台与操作系统研究 1 0 系统。不同的功能模块采用1 2 8 位的r o a d r u n n e r 总线连接，能够在片内提供 高达2 g b ”e s 的数据交换带宽。 r c p 内的嵌入式处理器采用3 2 位的a r c 处理器，可以工作在1 2 5 m 主频。 r c p 内可重构单元的基本计量单位为s l i c e ，不同型号的r c p 内部所包含的 s l i c e 数目不同。每个s l i c e 中包含了3 个能够分别进行配置的t i l e ( 最小的配置 单元) ，其基本结构如图2 4 。每个t i l e 又包括3 2 位的数据通路处理单：元；( d a t a p a t h p r o c e s s i n gu n i t s ，d p u s ) ，1 6 x 2 4 位的乘法器，本地存储器( l o c a ls t o r em e m o r i e s ， l s m s ) 和控制逻辑单元( c o n t r o ll o g i cu n i t s ，c l u s ) 。 图2 4c h a m e l e o n 系统 r c p 内部的互连结构分为三个层次：内部互连、s l i c e 内部互连和s l i c e 外部 互连。内部互连用于连接同一t i l e 中的d p u ，同时引入一个时钟周期的延迟。 s l i c e 内部互连用于连接同一s l i c e 内的d p u ，也引入一个时钟周期的延迟。s l i c e 外部互连则在将不同s l i c e 的d p u 连接起来时引入2 个时钟周期的延迟。 每个d p u 都与一个c u u 关联，c l u 中可以存储8 条配置指令，具体哪一条 指令有效，取决于c l u 内的状态机和数据通路上结果，也使得用户程序可以通 过运算结果直接选择硬件配置。此外，为了加速配置过程，r c p 的配置子系统 还引入了多现场的配置方式。 c h a m e l e o n 系统提供了基于g n uc 的集成开发环境，能够提供基本的设计、 调试和验证功能。c 语言的源程序由支持a r c 的g n uc 编译器编译，v c r i l o g 代码被综合到可重构单元上，二者被链接后在r c p 上运行。此外，用户能够可 以通过p c i 总线采用标准的g d b 工具对程序进行跟踪和调试。 另外值得一提的是c h a m e l e o n 系统中提供了软件工具自动生成e b i o s ( e c o n f i g u r a b l eb a s i ci 0s e r v i c e s ) ，e b i o s 能够提供资源分配，配置管理和d m a 服务，使得用户不用过多的考虑配置过程的细节。 可重构嵌入式系统样机平台与操作系统研究 r a w ( r e c o n f i g u r a b l ea r c h i t e c t u r ew o r k s t a t i o n ) 项目是由m r r 的e l l i o t w a i n g o l d 和m i c h a e lt a y l o r 等人于1 9 9 7 年左右开展的，该项目的主要目的是为 了设计一种简单的、高度并行的v l s i 结构，使得编译器能够充分评估、优化和 利用硬件资源。其基本结构如图2 5 所示【2 1 】。 图2 5 r a w 体系结构 每个r a w 微处理器由1 6 个完全相同的可编程t i l e 构成，每个t d e 本身又 包括：两条静态路由( 路由关系在编译时指定) ，两条动态路由( 路由关系在运 行时能够改变) ，一个含8 级流水线基于m i p s 的处理器，3 2 k b y t e 的数据c a c h e 和9 6 k b y t e 的指令c a c h e 。每个t i l e 能够通过全双工的3 2 位数据总线和任意相 邻的t i l e 进行通信。尽管目前的r a w 微处理器只包含了1 6 个啊e ，但是m i c h a e