（计算机应用技术专业论文）局部可重构平台设计及空白区域搜索算法的研究.pdf

毫i “ 爹l ，? 1 ； 簿 略 j i 毫。 知锸 哗叫 ，“飞 + 鼢 _ - 一一 ，1九，础。惫誊夯拳豫 是舞。毒”；- 叫，j爹。参， ，r；i c ； 己 at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e r a p p l i c a t i o nt e c h n o l o g y d e s i g no f a p a r t i a l l yr e c o n n g u r a t i o np l a t f o r m a n ds t u d yo n a l g o r i t h m sf o rf i n d i n ge m p t y s p a c e b yg a oc h e n y a n g s u p e r v i s o r ：p r o f e s s o ry ug e n o r t h e a s t e r nu n i v e r s i t y j a n u a r y2 0 0 8 1 蠡氍x一l哩礴“唆漫 一 。 ，_ 一 p hgp0_pd#q、 吱 日l 铲夔 、j ；呻 l 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 = 也 思。 学位论文作者签名：弓硒 日 期：- - p o o g 。i 一、砂白 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 对可重构逻辑器件上的指定计算资源进行独立地配置，而不影响器件上其余部分的功 能，与早期的可重构计算技术相比，它减小了配置位流下载、重构f p g a 芯片的时间， 节省了硬件资源，有效地提高了系统的整体性能和资源利用率。 目前针对可重构计算领域国内外研究热点主要集中在可重构操作系统、可重构区域 碎片度和空白区域搜索算法的研究。然而，迄今为止还没有一种平台可用于在f p g a 上 进行动态硬件任务调度和局部重构，因此本文提出了一种支持在嵌入式系统中实现动态 局部硬件任务调度和重构的平台，它可以对硬件任务队列中的硬件任务进行动态调度和 配置，并对特定的硬件任务调度算法做出初步的性能评估和分析。 论文详细介绍了构建的基于v i r t e x 4 的动态局部重构平台，给出了平台搭建的解决 方案，并进行了方案的比较和选择，描述了构建系统所使用的关键技术和实现机制，对 构建的平台进行了一系列性能试验。通过对平台的构建和用于测试的硬件任务的设计和 实现，验证了技术方案的可行性，为今后重构计算系统的研究和设计打下了坚实的基础 并积累了大量的实践经验，更为重要的是，平台为基于v i r t e x - 4f p g a 的局部硬件任务调 度算法的研究奠定了基本的实验环境，使硬件任务调度算法的性能评估更加准确可信。 由于硬件任务在传统操作系统的时间管理下又引入了空白区域管理的问题，因此本 文对二维区域空间上空白区域搜索算法进行了研究，通过引入谷点和阀值的概念改进了 原有的阶梯算法，彻底消除了原有阶梯算法的搜索冗余性，显著提高了算法的搜索效率。 论文目前取得的阶段性成果为后续f p g a 动态重构的研究和硬件任务放置、调度算 法的性能验证积累了丰富的实践经验，同时为二维空间空白区域管理算法的研究奠定了 一定的理论基础。 关键词：可重构计算，动态局部可重构，f p g a ，v i r t e x - 4 ，改进型阶梯算法 - i i 各卜lt 蟠誊 东北大学硕士学位论文 1 ，d e s i g n o f ap a b s t r a c t a r t i a l l yr e c o n f i g u r a t i o np l a t f o r ma n ds t u d yo n a l g o r i t h m sf o rf i n d i n ge m p t ys p a c e a b s t r a c t n o w a d a y s ，埘mt h ec o m p l e x i t yr e q u i r e db ye m b e d d e ds y s t e mi n c r e a s i n g ，h a r d w a r e t r a n s i s t o rd e n s i t yi sa l s oi n c r e a s i n g i nt h i sc a s e ，s o p cd e s i g nm e t h o d o l o g yb a s eo nf p g a si s b o o m i n g ，m o r e o v e r , s y s t e md e s i g nl e v e lt e c h n o l o g y r e c o n f i g u r a b l ec o m p u t i n gg a i n e dm o r e c o n c e mf r o ma c a d e m i a d y n a m i cp a r t i a lr e c o n f i g u r a t i o n ( d p r ) i san o v e lt e c h n i q u ei nr e c o n f i g u r a b l e c o m p u t i n g t a k i n ga d v a n t a g eo fd p r , s y s t e mc a ni n d e p e n d e n t l yc o n f i g u r eap o r t i o no f s p e c i f i cc o m p u t i n gr e s o u r c e si nc o n f i g u m b l ed e v i c e sw i t h o u ta f f e c t i n gt h ee x e c u t i o no fo t h e r p a r t c o m p a r e d 诚t ht h ec o n f i g u r a b l et e c h n i q u ei ne a r l ya g e ，t h i sr e d u c e st h eo v e r h e a d i n t r o d u c e db yb i t s t r e a md o w n l o a d i n ga n dr e c o n f l g u r a t i o n d p rc o u l dg a i nb e t t e ra r e as a v i n g a n dr e s o u r c eu t i l i z a t i o na n di m p r o v et h eo v e r a l lp e r f o r m a n c eo fs y s t e m d p r p l a t f o r mi nv i r t e x - 4w h i c hs u p p o r t sh a r d w a r et a s kl o a d i n ga n ds c h e d u l i n gi su s e d f o rv e r i f i c a t i o n t h i st h e s i sd e t a i l st h ec o n s t r u c t i o no fv i r t e x - 4d p r p l a t f o r ma n dt h es o l u t i o n i nd e s i g nf l o w , f u r t h e rm o r e ，i tc o n d u c t st h ec o m p a r i s o na m o n gs e v e r a ld i f f e r e n ts o l u t i o n s ， d e s c r i b i n gs o m ec r i t i c a lt e c h n o l o g i e sa n di m p l e m e n t a t i o n s f i n a l l y , as e r i e so fe x p e r i m e n t s h a sb e e nc a r r i e do u to nt h i sp l a t f o r m a c c o r d i n gt oc o n s t r u c t i o na n di m p l e m e n t a t i o no fs u c h p l a t f o r m 。w ec h e c k e dt h ef e a s i b i l i t yo fo u rs o l u t i o ns oa st ol a yt h ef i r s ts t o n ea n da c c u m u l a t e al o to fe x p e r i e n c ef o rt h ef u r t h e rr e s e a r c ha n dd e s i g n m o r ei m p o r t a n t l y , p l a t f o r mp r o v i d e s t h ee n v i r o n m e n tf o rt e s t i n gh a r d w a r et a s ks c h e d u l i n ga l g o r i t h m s ，a n dm a k e st h ee v a l u a t i o no f s c h e d u l i n ga l g o r i t h m sm o r et r u s t a b l ea n dm o r ea c c u r a t e n o to n l yc o n s i d e r i n gt h et e m p o r a lm a n a g e m e n t , h a r d w a r et a s ks c h e d u l i n gb r i n g st h e n e wp r o b l e m s p a t i a lm a n a g e m e n t t h i st h e s i sc o n c e n t r a t e so ns e a r c h i n gf r e ea r e ai n2 d m o d e l b yu s i n gs o m ec o n c e p t ss u c ha sv a l l e yp o i n ta n dt h r e s h o l d ，t h ea l g o r i t h mp r o p o s e di n t h i st h e s i se l i m i n a t et h er e d u n d a n to fp r e v i o u ss t a i r - c a s ea l g o r i t h ma n di m p r o v et h ea l g o r i t h m e f f i c i e n c y t h ec u r r e n te x p e r i m e n tr e s u l t sp r e s e n t e di nt h i st h e s i sg u i d et h ef u r t h e rr e s e a r c ho n p e r f o r m a n c ee v a l u a t i o no fh a r d w a r et a s ka l l o c a t i o na n ds c h e d u l i n ga l g o r i t h mi nd p r , a n d p r o v i d es o m et h e o r e t i c a lb a s i sf o r2 da r e am a n a g e m e n t k e yw o r d s ：r e c o n f i g u r a b l ec o m p u t i n g ，r u n - t i m ep a r t i a lr e c o n f i g u r a t i o r t , f p g a ，i m p r o v e d s t a i t e a s ea l g o r i t h m i i i u ；0 一 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s a a c t h i 第一章引言1 1 1 研究背景1 1 2 平台的介绍与描述j 4 1 3 论文结构5 第二章可重构系统概述。7 2 1 可重构系统模型7 2 1 1 宿主机与可重构逻辑松耦合模式7 2 1 2 微处理器与可重构逻辑松耦合模式8 2 1 3 微处理器与可重构逻辑紧耦合模式8 2 1 4 微处理器、存储器与可重构逻辑紧耦合模式9 2 1 5 四种耦合模型的比较一9 2 。2 可重构系统的可重构特性1 0 2 2 1 静态可重构系统1 0 2 2 2 动态可重构系统1 1 2 3 动态局部可重构系统的研究意义1 3 2 4 本章小结1 4 第三章f p g a 基本概念和原理15 3 1f p g a 基本概念及分类15 3 2f p g a 配置模式介绍1 6 3 3v i r t e x 系列f p g a 的内部结构1 6 3 3 1 输入输出单元1 7 3 3 2 可配置逻辑单元17 3 4 基于i s e 的f p g a 设计流程18 3 5 基于模块的f p g a 局部重构流程简介1 9 3 5 1 模块设计入口和综合19 3 5 2 模块设计实现2 l 3 6 本章小结2 4 第四章基于vir t e x - 4 的局部重构平台的构建2 5 4 1 局部可重构平台搭建的基本原理和总体介绍。2 5 4 2 国外相关系统介绍2 6 东北大学硕士学位论文目录 4 3 可重构平台搭建方案的选择。2 7 4 3 1f p g a 的方案选择2 7 4 3 2 宿主机和可重构逻辑耦合模式的方案选择2 7 ，4 3 3 存储结构的方案选择2 8 4 3 4 宿主机操作系统的选择方案3 0 4 3 5f p g a 配置模式的方案选择3 0 4 3 6f p g a 重构模式的方案选择_ 3 2 4 4e a - p r 局部重构流程的设计和实现。3 3 4 4 1 工程目录结构3 4 4 4 2 局部重构设计流程。3 4 4 5 动态可重构硬件任务的设计与实现4 2 4 5 1 基本电路功能4 2 4 5 2 模块设计入口和综合4 3 4 5 3 模块设计实现。4 5 4 6 原型系统中的关键技术及实现4 6 4 6 1 动态局部可重构技术。2 4 6 4 6 2 比特流下载器的设计与实现- 4 8 4 6 3 f t e x 4 重构器的设计与实现5l 4 7 原型系统的实验5 2 4 7 1 硬件任务配置时间5 2 4 7 2 配置硬件任务的系统开销：5 2 4 7 3 硬件任务调度算法的调度时间5 3 4 8 本章小结5 4 第五章v ir t e x - 4 上2 d 空白区域搜索算法5 5 5 1 国内外相关研究工作5 5 5 2 问题模型的描述和概念5 5 5 3 阶梯的构造5 7 5 4 搜索极大空矩形5 8 5 5 复杂度分析和实验结果6 1 5 6 本章小结6 3 第六章结论与展望6 5 6 1 结论6 5 6 2 未来的工作及展望6 6 参考文献6 7 致谢。7 l 攻读硕士期间参加的项目7 3 v 卜 0 士学位论文 第一章引言 1 1 研究背景 第一章引言 在嵌入式系统快速发展的今天，嵌入式系统已经逐步渗透到社会领域的各个方面。 随着军事、航空航天、通信、汽车电子等应用领域中各类现代化智能设备的不断发展， 高性能信息处理系统的需求日益增长，高性能主要体现在要求大数据量、大计算量的高 速处理，计算密集型任务越来越多，这就要求嵌入系统的处理能力越来越强以便保证应 用的需要。同时，当今数字化应用的多样性、复杂性和灵活性要求系统具有针对应用环 境变化的自适应能力，这就要求嵌入式系统又需要保持较强的设计灵活性。系统开发者 要尽可能减少由领域变化或需求调整所带来的重新设计及重新实现的时间和成本开销， 所以嵌入式系统在原有特点的基础上，出现了另一个新的趋势，即在保持可靠性、高效 性和专用性特点的基础上，系统硬件平台还要具备多次编程，易于修改的特点。因此嵌 入式系统的性能和开发灵活度日益受到关注。特别是随着微电子技术的发展，可编程逻 辑器件( p l d ) 的出现，以及电子设计自动化( e d a ) 技术的发展，基于f p g a 的可重构技术 逐渐成为国内外学术界的研究热点。 另外，随着数字系统规模的不断扩大，数字系统逻辑电路资源的增长不断超越系统 逻辑功能的增长。然而在现实应用中，系统的逻辑电路资源都是有限的。系统设计要考 虑利用有限的逻辑资源实现更大规模的逻辑功能，在系统逻辑电路资源既定的条件下， 就要求对系统的逻辑电路资源在时间轴方向上分时复用，于是就提出了可重构计算【1 1 1 2 3 1 的概念。 可重构计算技术及f p g a ( f i e l dp r o g r a m m a b l eg a t ea r r a y ) 的出现和快速发展，为上述 问题带来了全新的解决方案。可重构计算技术的核心就是在电子系统工作的状态下，动 态地改变电路的结构，这种配置方式灵活而高效，通过硬件描述语言h d l ( h a r d w a r e d e s c r i p t i o l ll a n g u a g e ) 以可编程的方式来完成并实现电路的构建。通过引入可重构计算技 术，整个嵌入式系统既保持了设计灵活性，同时也获得了专用硬件电路的等价性能。 目前可重构计算领域的研究热点主要集中在如下几个方面： ( 1 ) 可重构操作系统的研究。 b r e b n e r 在 4 1 中最早提出了系统的概念。w i g l e y 等人在【5 】中很早就提出了构建可重构 操作系统中存在的问题，诸如任务下载、可重构器件的空白区域管理、调度、存储管理 r。t16咿 东北大学硕士学位论文第一章引言 和保护、i o 等，同时提出了关键的任务间通信问题和碎片度指标。 w a l d e r 和p l a t z n e r 在【6 】【7 】描述了他们所实现的原型系统，其对支持硬件任务的系统 结构进行了初步的尝试，用系统实践的方式描述了搭建可支持软硬件协同调度的操作系 统的若干基本概念，反映了这些概念实体在系统中以何种形式加以实现。 b a s k a r a n 和s r i k a n t h a n 在【8 】中较详细的提出了运行时可重构的基本结构，并描述了 h o p e s ( h a r d w a r e o p e r a t i n gs y s t e m ) 实现的一些具体技术。 r i s s a 和n i i t t y l a h t i 在【9 】中描述了他们的混合原型系统平台，这个平台中f p g a 构造 在一块p c i 板卡上，通过p c i 总线与p c 上的通用c p u 完成通信。同样，w i a n g t o n g 、 y k c h e u n g 等人在【1 0 】也用类似的结构实现了u l t r a s o n i c 的可重构系统，文中更关注的 是硬件任务如何在软硬件协同设计中加以体现，其构造了软硬件任务统一的设计环境 d a g 。m e r i c s o n 等人在【1 1 】中提出了利用a r m 和f p g a 连接的系统r e a r m 。 在操作系统内核级别中支持软硬件统一概念的良好系统应是k w o k - h a ys o 、 t k a c h e n k o 和b r o d e r s e n 等在【1 2 1 提出的b o r p h 系统，这个系统是首先在修改l i n u x 操作 系统上实现的，文中专门提出了遵循u n i x 标准统一的访问接口、以e l f 为基本格式的 硬件任务文件，实现了硬件进程的概念，统一了文件操作使之和任务间通信联系起来， 提出了具体的任务间通信的操作机制。 a g r o n 、p e c k 、a n d e r s o n 和a n d r e w s 等人在【1 3 】中提出了其在c s o c 中实现的 c p u f p g a 混合系统平台，不但c s o c 的实现方式令人注目，而且其将协同调度器、中 断处理等传统操作系统重要构件以硬件电路的形式在f p g a 中加以实现，使得c p u 从 传统操作系统要处理的调度开销中解放出来成为一个纯软件任务的平台，这使得系统效 率大大提高，对于实时系统的可预测性更强。以硬件方式实现的调度器首次实现了软硬 件任务的统一。该混合系统对于上层的开发者也提供统一的接口和编程模型，尤其在软 硬件任务的开发上提供中间语言层，力图将硬件描述语言和高级语言做进一步统一。 h o r t a 等人在【1 4 】中提出了利用自行开发的p a r b i t 局部配置比特流生成工具来进行 f p x 平台的开发，p a t b i t 可以生成一个指定2 d 区域中的比特流，这使得系统配置的 灵活性大大提高。自从x i l i n x 的v i r t e x4 t 1 5 】系列芯片出现以后，配置模式发生了变化， 其中的比特流中的帧( f r a m e ) 不再对整个高度方向上的逻辑单元进行配置，而是配置 一个局部高度，这样带有约束的2 d 模型可以在该系列的器件上进行实验了。s e d c o l e 等 人在【1 6 】叙述了这个技术的进展和基本的手段，但是由于支持此器件进行局部可重构的开 发环境和工具链( 如p l a n a h e a d ) 较为缺乏，所以目前还没有支持带有约束2 d 模型的 实际原型系统出现。 - 2 - 东北大学硕士学位论文第一章引言 国内的相关研究工作开展较晚，进展较慢，目前没有实际的原型系统和平台。仅仅 有一些概念性的系统框架提出。b oz h o u 等在【1 7 】中提出了s h u m u c o s 的系统框架，可 以看出这是对u c o s 系统的改造。 ( 2 ) 重构区域碎片度的研究。 j e s u s 1 8 】提出了一种维护f p g a 中空白区域的顶点链表( v e r t e xl i s t ) 的方法，利用该 链表进行空间管理，其根据顶点链表中的顶点个数给出了评估区域碎片度的经验公式。 h a n d a 等【1 9 】【2 0 1 根据空白单元在水平方向和垂直方向可扩展的尺度，提出每个空白单 元对碎片度的贡献( f f c ) 的概念来评估空白区域碎片度，它能较好的分析一个局部区域 的破碎程度。 先前的w i g l e y 等 2 1 1 以空白矩形的短边为依据提出了特征尺寸概念，它利用特征尺寸 得到了碎片度。而w m d e r 等【2 2 】也利用覆盖空白区域的矩形面积来求解碎片度。 ( 3 ) 区域空白区域搜索算法的研究。 b a z a r g a l l 等人【2 3 1 提出了维护非交叠空白矩形的方法，并给出了几种空白区域划分的 启发式算法。w a d d e r 等人【2 4 】通过延迟空白区域划分对进行了改进，提出了o t f 和增强o t f 算法。 h a n d a 和v e m u r i 2 5 】提出了一种通过构造阶梯( s t a i r c a s e ) 的方法搜索可重构区域极大 空矩形的算法，该算法通过遍历紧挨已放置任务上方的行和最下面一行，找到所有可能 为最大阶梯原点( o r i g i n ) 的单元( c e l l ) ，并构建以该单元为原点的阶梯，从阶梯中获 取的矩形包含了所有的极大空矩形。 j e s u s 等在 2 q 中给出了一种通过维护已放置任务的顶点链表来管理可重构空白区域 的算法。s e o n g m o oy 0 0 【2 刀给出了利用维护已被任务占据区域中的网格点来进行空白区 域的管理。 扫描线算法【2 8 1 针对硬件任务给出了高效的搜寻所有区域极大空矩形的扫描线算法； 同时通过改进的扫描线算法减少了实际的搜索区域。 综上所述，虽然针对可重构计算的研究在最近几年已经取得了一系列的成果，然而 上述针对可重构平台的研究中，还没有一种运行在嵌入式体系结构上、本身支持对f p g a 上硬件任务进行动态局部调度和重构的平台，因此本文基于上述分析，将针对可重构计 算系统的研究，重点展开以下两方面的工作： ( 1 ) 可重构操作系统中硬件任务调度、配置平台的设计与实现。 随着局部可重构技术的发展、f p g a 门阵列密度的增长以及支持二维局部重构f p g a 器件的出现和普及，在v i r t e x - 4 这样支持二维局部重构的器件上进行硬件任务调度算法 - 3 - _，ilj 。；每 东北大学硕士学位论文 第一章引言 的研究得到研究人员的广泛关注。然而，就目前研究而言，对调度算法进行检验的方式 还仅局限于模拟验证阶段，尚没有可以在真实的硬件平台上采用特定调度算法对已有硬 件任务队列中的硬件任务进行自动调度配置的系统平台。本文中描述的平台正是在这样 的需求下诞生的，研究人员可以使用该平台利用某一特定的硬件任务调度算法对硬件任 务队列中的硬件任务进行自动调度并配置到f p g a 设备中，完成算法性能的真实评估。 ( 2 ) 二维区域模型中空白区域搜索算法的研究。 二维模型的区域管理比一维模型的区域管理更为复杂，尤其是空白区域的维护和硬 件任务的放置问题都需要单独高效的搜索算法来支持，本文通过引入谷点和阀值的概念 对h a n d a c - r 和v e m u r i t 2 5 】提出的阶梯算法进行改进得到一种高效的二维空间空白区域搜索算 法。通过试验，证明了改进后的阶梯算法对于空白区域的管理是高效的，消除了原有阶 梯算法的搜索冗余性。 1 2 平台的介绍与描述 作为可重构系统的基石，f p g a ( f i e l dp r o g r a m m a b l eg a t ea r r a y ) 的发展支撑着可重构 系统的发展，它是可重构计算技术中最具代表性且使用最为广泛的器件之一。f p g a 基 于s r a m ( 静态随机存储器，s t a t i cr a m ) 的查找表( l o o k u pt a b l e ) 技术，其中的逻辑功 能和布线资源的状态都依赖于配置电路中s r a m 所存储的值，通过该数值来构造逻辑 运算的真值表或者充当线路的开关和连接点。这样，f p g a 就可以根据用户的需要改变 s r a m 中的数值，从而使f p g a 中的电路完成不同的逻辑功能和布线连接。因此，f p g a 就变为一种灵活可编程的计算资源。 配置电路中s r a m 数值的写入过程称为配置( c o n f i g u r a t i o n ) ，其写入的数据就称为 配置文件，或者比特流( b i ts t r e a m ) 。不同的配置会导致f p g a 不同的逻辑行为。配置不 但可以在整个器件上电后就立即完成，而且配置也可以在器件运行的过程中对其部分区 域进行修改而不影响其他部分的运作。上述的机制就是运行时局部可重配置技术( p r t r , p a r t i a lr u n - t i m er e c o n f i g u r a t i o n ) ，也称为动态局部可重配置技术。这就意味着整个f p g a 区域成为了一个可以不断复用的硬件资源池，不但其可以在运行的过程中动态改变逻辑 功能，使不同的任务复用f p g a 中同一区域，而且还可以把整个f p g a 区域划分成若干 个子区域，使得多个不同的任务可以在同一时间的不同区域中得以运行。因此，f p g a 成为一个多任务的并行处理器，使得整个计算系统的体系结构发生了根本性的变革。 硬件任务( h wt a s k ) 在这样的环境下就应运而生了。所谓硬件任务，就是以硬件电 路的方式完成特定功能的模块单元。我们知道，硬件和软件在逻辑功能上存在完全等效 4 毒 第一章引言 估模块用以评估当前硬件任务调度算法的真实调度性能。 1 3 论文结构 图1 1 重构平台的架构 f i g 1 1a r c h i t e c t u r eo fr e c o n f i g u r a t i o np l a t f o r m 本论文阐述了针对x i l i n x 公司的v i r t e x 4f p g a 的重构和局部重构原理，研究和总结 了实现基于x i l i n x 公司的v i r t e x 4 f p g a 的动态部分可重构、评估平台的关键技术和实现 方法，提出了可重构、评估平台的基本模型，设计并实现了重构平台及重构过程中性能 和消耗的评估，并对h a n d a 和v c m u r i l 2 5 1 所提出的s t a i r c a s e 放置算法进行改进，提出了一种 高效的改进型s t a i r c a s e 算法，最后应用该论文所述平台在基于x i l i n x 公司的v i r t e x - 4f p g a 的硬件基础上对平台所集成的三种算法进行测试和分析。验证了该平台的功能性并通过 实验验证了改进型阶梯算法的高效性。 本论文的内容安排如下： 第一章为引言，介绍了该设计的研究动机和背景，指出了当前可重构计算系统领域 _ 5 东北大学硕士学位论文 第一章引 的研究热点以及本文的设计实现与研究内容。大致介绍了本文所述平台的架构。 第二章从可重构系统的系统模型和可重构性两方面来介绍了可重构系统及可重构 计算技术。可重构系统系统模型方面主要阐述了静态可重构系统、动态可重构系统、全 局可重构系统以及部分可重构系统的概念，并重点分析和评价了动态部分可重构系统的 研究意义，为后续v i r t e x - 4 系列f p g a 的动态局部可重构机制的阐述做了铺垫。 第三章主要介绍了可重构系统的核心原件一p g a 。包括其基本原理、概念和分 类，介绍了基于查找表结构的f p g a 的基本实现原理以及f p g a 的四种配置模式。在此基 础上简要介绍了基于i s e 的f p g a 设计流程，包括电路设计与输入、功能仿真、综合、综 合后仿真、实现、布线后仿真与验证和下板调试等主要步骤。为后续v i r t e x - 4 系列f p g a 所特有的e a p r ( e a r l ya c c e s sp a r t i a lr e e o r d i g u r a t i o n ) 硬件任务比特流生成工具的比特流 生成流程的阐述打下了扎实的基础。 第四章为基于v i r t e x 4 系列f p g a 的动态局部可重构平台的设计和实现。包括硬件和 软件平台两个方面。硬件平台方面阐述了系统核心部件- v i r t e x - 4 系列f p g a 的器件特 性以及在其上进行动态局部可重构( d y n a m i cp a r t i a lr e e o n i i g u a t i o n , d p r ) 的机制，探讨了 配置模式、实现方式的选择。软件平台方面阐述了基于e a p r ( e a r l ya c c e s sp a r t i a l r e c o n f i g u r a t i o n ) 的v i r t e x - 4 系列f p g a 的i s e 设计流程以及s e l e c t l 儿廿配置模式时序的模 拟。完整描述了构建针对v i r t e x 4 系列f p g a 的动态局部可重构平台所涉及的技术方案选 择和关键技术，实现了对硬件任务进行加载、重构及调度算法性能的评测。 第五章阐述了调度器对于二维可重构器件的空白区域管理策略，提出在给定一个规 模固定的硬件任务以后，如何较快速的在当前空白矩形区域中查找到匹配当前硬件任务 的空白区域。本文针对原有的阶梯构造算法提出改进，改进后的算法完全避免了原算法 冗余的搜索过程，通过试验对比验证了算法效率的提高。 r 第六章为总结与展望，对论文的研究内容以及研究过程中遇到的问题作了总结，对 未来的研究工作做了展望。 6 j 一 ： 东北大学硕士学位论文第二章可重构系统概述 第二章可重构系统概述 f p g a 的出现使得可重构计算从理论研究走向实际应用，从八十年代中期开始，可 重构计算取得了较大的发展，在容错计算、并行处理、可重构指令集计算机等研究方面 得到了应用。一般来说，可以从系统模型和系统的可重构特性来描述一个可重构系统。 可重构系统模型主要是指可重构逻辑与宿主机处理器之间的耦合关系，可重构特性可从 可重构逻辑的重构时刻( 动态可重构和静态可重构) 和重构粒度( 全局可重构和局部可重 构) 两个方面来描述。 2 1 可重构系统模型 因为可重构逻辑资源不能有效完成像存储器的访问和分支控制这些类型的运算，单 纯f p g a 结构并不能很好地满足应用要求。因此把那些不容易在f p g a 上完成的运算放在 主处理器上运行，同时让高密度的运算在f p g a 上完成，更能提高整个系统的效率。目 前已有的可重构系统中都分别包含了可重构逻辑资源和固定逻辑资源。固定逻辑资源既 可是一个宿主机也可只是一个微控制器，按照它们之间的耦合程度可以将可重构计算系 统分为四类，分别为宿主机与可重构逻辑松耦合模式、微处理器与可重构逻辑松耦合模 式、微处理器与可重构逻辑紧耦合模式以及微处理器、存储器和可重构逻辑紧耦合模式。 2 1 1 宿主机与可重构逻辑松耦合模式 最松的耦合形式，可重构逻辑为外部独立的处理单元。属于这类系统的可重构逻辑 部分一般包含多个f p g a ，而固定部分则是一个宿主计算机，二者之间通过接口总线连 接起来。可重构逻辑类似于宿主机协处理器，接收宿主机发出的指令和数据，并将结果 通过i o 接i z i ( 女i i s a 、p c i 、并口等) 传回宿主机。具体结构如图2 1 所示。 独立处理单元 。 图2 1 宿主机与可重构逻辑松耦合结构 f i g 2 1l o o s e l yc o u p l e ds t r u c t u r eo f h o s tw i t hr e c o n f i g u r a b l el o g i c - 7 奄，蠼flj 东北大学硕士学位论文第二章可重构系统概述 该类系统的典型优点是设计简单。由于所有部件非常容易得到，所以可以快速地制 造，方便地编程，还可以根据需要灵活地选用不同的宿主机和c p u 。但其缺点也是明显 的，由于所有的数据交换都需要通过外部的接口总线来完成，这部分的性能成了系统的 瓶颈，限制了系统的性能加速比。 2 1 2 微处理器与可重构逻辑松耦合模式 该类系统中的f p g a 阵列直接与微处理器通过独立的数据和控制总线进行连接，相 对于微处理器来说相当于增加了一个多功能协处理器。该结构的最大改进在于取消了同 宿主机的外部通信接口，大大提高了f p g a 阵列同微处理器的数据交换速度。该类系统 结构如图2 2 所示。 图2 2 微处理器与可重构逻辑松耦合结构 f i g 2 2l o o s e l yc o u p l e ds t r u c t u r eo fm i c r o p r o c e s s o r sw i t hr e c o n f i g u r a b l el o g i c 该类系统中执行某个运算时，任务被分解到硬件部分( f p g a ) 和软件部分( c p u ) ，可 以用硬件结构快速实现的运算被映射到f p g a 上构成特定电路，而简单的运算处理可控 制功能则由c p u 来完成。任务划分主要由用户来决定，很大程度上由编译系统来完成或 由手工完成。可重构逻辑在系统中的组织形式非常灵活，既可以配置成一个复杂的功能 单元用来执行某些耗时的操作，也可以配置成为多个简单的单元来一次处理多个数据。 该类系统同样具有前一类系统的易用特点。该系统中的处理器可以根据需要选择不 同的产品，只要该c p u 支持类似协处理器的工作方式即可。该类系统更适合用于需要执 行大量复杂指令的场合。 2 1 3 微处理器与可重构逻辑紧耦合模式 可重构逻辑资源可以作为主处理器上的可重构功能单元 2 9 1 。这种结构允许在传统的 编程环境中附带定制的指令，这些定制指令可以随时间变化。在这里，可重构硬件带有 寄存器用于输入和输出，在主处理器的数据通路上像其它功能单元一样运行。该类系统 8 - 麓o，j ：0l多 、_ ， 之 东北大学硕士学位论文 第二章可重构系统概述 结构如图2 3 所示。 图2 3 微处理器与可重构逻辑紧耦合结构 f i g 2 3t i g h t l yc o u p l e ds t r u c t u r eo fm i c r o p r o c e s s o r sw i t hr e c o n f i g u m b l el o 酉c 该类系统中的c p u 通常是以i p 核形式提供的设计模块。需要与