（计算机应用技术专业论文）动态重构系统若干关键问题的研究.pdf

摘要 爬山算法实现了面向动态重构系统的软硬件划分，其中对划分结果的评价使用 了动态优先级调度算法。软硬件划分能够有效地将任务流图表示的应用调度到 系统中的微处理器和可重构硬件上，以充分发挥两者各自的优势，达到优化动 态重构系统性能的目 标. 关键词: f p g a ，可重构硬件，可重构计算，动态重构系统，可重构资源管理， 布局，软硬件划分 ab s t r a c t ab s t r a c t wit h t h e r a p i d i n c r e a s e o f t h e c o m p u t i n g r e q u i r e m e n t fr o m s o m e a p p l i c a t i o n s s u c h a s c o m m u n i c a t i o n a n d m u l t i m e d i a t e c h n o l o g i e s , t h e p e r f o r m a n c e im p r o v e m e n t o f t r a d i t i o n a l p r o c e s s o r s a n d a s i c s h a s b e e n re q u i r e d g r e a t l y . d u e t o t h e a d v a n c e m e n t o f t h e v l s i t e c h n o l o g y a n d t h e r e c o n f i g u r a b l e h a r d w a r e s u c h a s f p g 人 t h e r e c o n fi g u r a b l e c o m p u t i n g h a s b e c o m e a n i m p o r ta n t re s o l u t i o n f o r t h e s e k i n d s o f a p p l i c a t i o n s , e s p e c i a l l y t h e a d v e n t o f t h e p a r ti al l y r u n - t im e r e c o n fi g u r a b l e a b i l i ty o f r e c o n f i g ur a b l e h a r d w a re . b u t , i t i s v e ry d i f f i c u l ty f o r re c o n f i g u r a b l e c o m p u t i n g t o b e c o m e a c tu a l u n i v e r s a l a n d h i g h p e r f o rm a n c e c o m p u t i n g s y s t e m w i t h t h e c u rr e n t r e c o n fi g u r a b l e h a r d w a r e a r c h i t e c t u r e a n d r e c o n f i g u r a t i o n t e c h n o l o g y . b a s e d o n t h e d y n a m i c al r e c o n f i g u r a b l e s y s t e m c o m p o s e d o f t h e m i c r o p r o c e s s o r a n d r e c o n fi g u r a b l e h a r d w a re , s o m e i m p o r ta n t i s s u e s h a v e b e e n s t u d ie d in t h i s d i s s e r t a t i o n . f o r e x a m p l e , t h e r e c o n fi g u r a t i o n s c h e m e s , t h e m a n a g e m e n t o f r e c o n fi g u r a b l e re s o u r c e s , t h e s c h e d u l i n g a n d p la c e m e n t o f h a r d w a re t a s k a n d t h e h a r d w a re / s o ft w a r e p a r ti t i o n i n g . s o m e s o l u t i o n s a re p r o p o s e d a n d t h e e x p e r i m e n t re s u l t s a r e a n a l y z e d . t h e r e s u l t s s h o w t h a t t h e y a r e b e n e f i t f o r t h e r e c o n fi g u r a b l e c o m p u t i n g a n d i t s p r a c t i c al i ty . a l l o f t h e res e a r c h e s a r e a s f o l l o ws . b a s e d o n t h e a n a l y s i s o f t h e c o n f i g u r a t i o n a r c h i t e c t u r e o f f p g a a n d t h e s t ru c t u r e o f p a rt i al b i t s t r e a m f o r d y n a m i c a l m o d u l e , t h e d y n a m ic al mo d u l e r e l o c a t i o n m e t h o d ( d mr l ) i s i m p l e m e n t e d . mo d u le b a s e d p a r t i al r e c o n f i g u r a t i o n i s e f f i c i e n t f o r d e c r e a s 吨 t h e re c o n f i g u r a t i o n o v e r h e a d . t h e p a r t i al h i t s tr e a m w a s g e n e r a t e d o n s o m e a r e a o r r r v a m a a v a n c e . n o t hu s d y n a m i c a l m o d u l e v o n t b e c o n f i g u r e d ri g h t ly w h e n i t s o ri g in al a r e a h a s b e e n o c c u p i e d b y a n o t h e r r u n n in g m o d u l e . t h e d y n a m i c al m o d u l e c a n b e s h i ft e d t o a n o t h e r e m p t y a r e a o n t h e h o m o g e n e o u s r e s o u r c e u s i n g d m r l m e t h o d . a n d t h e e x e c u t i o n e f f i c i e n c y o f t h e r e c o n f i g u r a b le s y s t e m w i l l b e i m p r o v e d . t h e c o n fi g u r a t i o n p a g e b a s e d r e c o n f i g u r a b l e r e s o u r c e m a n a g e m e n t i s p r o p o s e d a n d t h e p r o t o t y p e s y s t e m is im p l e m e n t e d o n t h e v i r t e x 1 1 p l a t f o r m f p g a . t h e ab s t r a c t d i ff e r e n t r e c o n f i g u r a b l e r e s o u r c e i s m o d e l e d r e s p e c t i v e l y a n d o r g a n i z e d b y t h e c o n f i g u r a ti o n p a g e . a n d t h e s i z e o f t h e c o n f i g u r a t i o n p a g e i s d i s c u s s e d . d i ff e r e n t n u m b e r o f c o n t i n u o u s c o n f i g u r a t i o n p a g e s c a n b e a l l o c a t e d t o a h a r d w a re t a s k a t r u n t i m e - u n u s e d c o n f i g u r a t i o n p a g e s c a n b e r e c l a i m e d a n d s o m e n e i g h b o r i n g c o n f i g u r a t i o n p a g e s c a n b e m e r g e d . t h e re c o n f i g u r a b le re s o u r c e m a n a g e m e n t i s i m p l e m e n t e d e ff e c t i v e l y i n o n e - d i m e n s i o n a l a r e a m o d e l . a t w o - d i m e n s i o n a l a r e a m o d e l o f r e c o n f i g u r a b l e h a r d w a re i s p r o p o s e d i n t h i s d i s s e r t a t i o n . t h e r e c o n f i g u r a b l e r e s o u r c e m a n a g e m e n t a n d t h e h a r d w a r e ta s k p l a c e m e n t a r e p r e s e n t e d b a s e d o n t h e t w o - d i m e n s i o n a l a r e a m o d e l . t h e u n o c c u p i e d re s o u r c e s o n t h e re c o n f i g u r a b l e h a r d w a r e c a n b e e ff e c t i v e l y m a n a g e d b y t h e t a s k - t o p b a s e d k e e p a l l m a x i m a l e m p ty r e c ta n 乡 e s a lg o r it h m . i t f a c i l i t i e s t h e d y n a m i c a l a l l o c a t i o n a n d r e c l a m a t i o n o f t h e r e c o n ft g u r a b l e re s o u r c e , a n d t h e f f a n d h e u r i s t i c b f a l g o r it h m s t o s e l e c t a ma x i m a l e m p t y r e c t a n g l e t o p l a c e h a r d w a r e t a s k a t r u n t i m e . c o m p a r e d t o t h e o n e - d i m e n s i o n a l a r e a m o d e l , t h e u t i l i z a t i o n p e r c e n t o f r e c o n f i g u r a b l e h a r d w a r e i s i m p r o v e d , a n d s o t h e s y s t e m p e r f o r m a n c e . b a s e d o n t h e t w o - d i m e n s i o n a l a r e a m o d e l o f t h e p a rt i a l l y d y n a m i c a l re c o n fi g u r a b le h a r d w a r e , t h e h a r d w a r e / s o ft w a r e p a r ti t i o n i n g f o r t h e d y n a m i c a l r c o n f g u r a b l e s y s t e m i s i m p l e m e n t e d b y t h e g e n e t i c a l g o r it h m a n d h i l l - c l i m b a l g o r i t h m , w h e r e t h e c o n f i g u r a t i o n d e l a y a n d p a r a l l e l e x e c u t i o n o f h a r d w a re t a s k s a r e c o n s i d e r e d . a n d t h e p a r t i t i o n i n g re s u l t s a r e e v a l u a t e d勿 t h e d y n a m i c a l p r io r i t y s c h e d u l i n g a l g o r i t h m . t h e a p p l i c a t i o n p re s e n t e d b y t h e t a s k fl o w g r a p h c a n b e s c h e d u l e d t o t h e m i c r o p r o c e s s o r a n d re c o n f i g u r a b l e h a r d w a re e ff e c t i v e l y u s i n g t h e p a r ti t i o n i n g a l g o r i t h m . t h e r e s u l t s s h o w t h a t t h e p a r t i t i o n i n g a l g o r i t h m i s h e lp f u l f o r t h e m t o c o o p e r a t e w i t h e a c h o t h e r a n d i m p r o v e t h e i r p e r f o r m a n c e . k e y w o r d . 二f p g a , r e c o n fi g u r a b l e h a r d w a r e , r e c o fi n g r a b l e s y s t e m , r e c o n f i g u r a b l e re s o u r c e m a n a g e m e n t , p l a c e m e n t , 0 川n g d y n a m i c a l r e c o n f i g u r a b l e h a r d w a r e / s o 几 w a r e p a r t i t i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本;学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版; 在不以赢利为目 的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名 年月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 内部 5 年 ( 最长5 年，可少于5 年) 秘密1 0 年 ( 最长 1 0 年，可少于1 0 年) 机密2 0 年 ( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明:所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中己 经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、己公开发表或者没有公开发表的作品的内容。 对本论文所涉 及的研究工作做出贡献的其他个人和集体，均己 在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名: 年月日 第一章绪论 第一章绪论 第一节研究背景 结合处理器、 存储器和专用逻辑电路的芯片设计已经面世十几年了， 硅上集 成密度的每次增加都有更加复杂的设计要实现。但是，只通过使用更大的处理 器和更多的专用逻辑电 路并不能实现性能的按比 例提高，不断出现的应用产品 和计算需求的复杂性以 及设计成本压力的增长正 在超过半导体按比 例缩小和设 计生产率改进的能力，新的计算模式的研究成为一个重要的课题。 1 . 1 . 1 传统计算模式的问题 随着社会生产和生活的发展， 以数据密集型应用为代表的计算和数据处理需 求越来越复杂。 通信协议、多媒体编码和安全等不断 变化的标准和客户需求都 在经历快速的复杂度增长，例如 to 网际协议数据包转发、g7 2 9语音编码、 j p e g 2 0 0 。 图 形 压 缩 、 m p e g 4 视 频 和r j i n d a e l a e s 加 密 等 o 1 。 这 些 新 的 协 议 都 需 要更长的实现描述和更大的运算吞吐量，而且要求系统供应商必须能够快速地 升级产品，以满足不断变化的市场需求。 传统的计算系统由 微处理器和在其上运行的软件组成，软件实现比较灵活， 一旦需求发生变化比较容易做出相应的修改。目 前，在软件开发中广泛使用的 开发语言的标准化程度高，可以获得较好的移植性:模块化、面向对象思想提 高了软件可复用程度;开发和调试工具成熟，在开发过程中易于验证， 有利于 缩短开发周期;软件开发环境可以重复使用，节约投资. 尽管微处理器在理论上可以处理很多任务， 但它通常缺乏完成复杂数据处理 任务所需要的带宽，其性能不足以完成绝大多数要求很高的信号、图像、协议 和安全等数据密集型处理任务。很多应用领域中的数据处理需求要比基本的处 理器性能的 增长速度快得多， 如图1 . 1 所示， 无线通信的 性能需求一代比 一代高， 无线通信标准要求的计算需求的增长超过芯片速度的增长为每年 2 5 % 左右，这 类算法的 计算复 杂 度的 增长 速度比 摩尔定 律还 要快 1 1 -; 1 。 在其它应用领 域，比 如 多媒体应用、科学与工程计算领域，也都有同样的需求增长。由于微处理器过 第一章绪论 多地考虑通用性， 不是针对解决某类问题、算法而设计的，尽管其速度己 经达 到了g h z 量级，也难于高效地实现算法来满足实际应用对计算速度的要求。而 且，基于单微处理器的软件实现对于具有内在并行特性的复杂算法不能提供很 好的支持。 4 34 3 . -.，.一 住闷 l/ 口试剧 /口 些加 t份 2 %_r s o tw ir e le s s 材门 / “ 片 -e t g o r lt h m ( s h a nt-ic com plexityro ns law 1 门 m ic ro p ro c e s s o r 1 d s com putationaleff clencyl 吟 弓 刁 卜 了、 尹考a 1e gqeeno( e501h a tt e ry p e r f o r m a n c e洲乡 z 一1la )i一一卜-一 . .，. .中. .， 】l 图1 . 1 计算需求发展曲 线 微处理器的发展还受到散热、 功耗和制造工艺的限 制， 其计算速度的增长远 落后于摩尔定律，计算效率的增长速度己经减慢并逐步达到饱和，性能/ 面积效 率的每一次提高都是以越来越差的能耗为代价的，微处理器的灵活性伴随着很 大的能 量消 耗 2 3 1 。 例如， 流水 线r i s c处理器 在2 0 世纪8 0 年 代后期 就可以 使 用几十万个晶体管来实现， 每个时钟周期可以 运行大约0 . 5 - 0 . 7 5 条指令， 而当前 最先进的r i s c处理器需要一千万个以 上的晶体管， 但是仍然不能实现每周期执 行两 条指 令 d i 。 虽 然 采 用更 多 的 晶 体管， 可以 通 过 并 行 指 令 执 行的 方 法来 提高 其 性能，但相应互连延迟的增加、功耗的增加和片外存取性能的改进不足在很大 程度上抵消了性能的增加。 对很多数据密集型应用， 高性能和高吞吐率的唯一可行解决方案就是硬布线 逻辑设计.与软件实现相比，硬件电路具有并发特性，能够为固定不变的算法 提供高度的并行性，并且可针对具体的算法设计专用电路，能耗比较低，这些 都使得硬件电路具有很高的速度和效率。然而硬件设计、开发周期长，不易于 第一章绪论 调试和实现原型系统，制造之后就不能再次编程，可复用性比较差。尤其是， 对于j p e g 2 0 0 0 这种变化的标准中的复杂算法， 缺乏足够的灵活性。 使用现有的 通用器件搭建容易受器件型号、性能和市场等因素的制约，而专用芯片的设计 和生产成本都比较高。此外，使用硬件电路来设计复杂功能充满了风险，一是 随着应用领域范围的不断扩大，不可能为每种专用功能都提供专门的硬件电路 实现.二是随着电 子系统的复杂性和带宽需求不断增加，可提供的逻辑电 路资 源的增长很难满足对系统逻辑功能增长的需求，这些都限制着硬件实现的应用 范围。 半导体制造商一直在努力地实现摩尔定律的预期发展速度， 使得设计者大约 每两 年就能 有数 量 加倍的 逻辑门 可以 使 用 川 。 而且， 工艺 几何尺寸 和电 路 特性的 持续改进使得芯片设计者不断地将设计移植到能够使用的新的集成电路制造工 艺上。 但更重要的是，电子产品的终端市场， 例如消费类、计算和通信系统等， 总是在持续不断地剧烈变化，这使得设计者需要不断地推出新的功能和性能， 使得芯片设计变得越来越困难.因此，快速变化和高复杂度的结合成为系统设 计的当务之急。 1 . 1 . 2 可重构计算 ma k i m o t o曲线预测了半导体技术的 发展趋势， 描述了 集成电 路应用的 三个 阶 段， 如图1 .2 所 示 4 1 。 如s s i , m s i 和l s i 电 路 这 类硬 布 线 组 件是 不 能 被 编 程 的，计算资源和应用算法都是固定不变的。微处理器的出 现使得能够在固定的 计算资源 ( 微处理器)上运行变化的算法，通过使用软件编程的方式大大拓展 了其应用。同时，该曲线也说明了可重构硬件是微处理器时代以来最重要的革 新之一，与微处理器一样，它也是一种基于r a m实现的可编程数据处理平台， 打破了a s i c 不能 被编程的硬布线模式， 通过重复编程实现相应的逻辑功能， 实 现了类似于微处理器上执行软件的计算模式。 随着微电 子技术的不断创新和发展， v l s i 的集成度和工艺水平不断提高， 已 从深亚 微米 ( _ 0 , x , 十 w , w , y , + h , h ) ) ( 1 .2 ) 1 . 4 . 4 软硬件协同设计 在 可 重 构 系 统中 实 现 应 用 的 方 法 有 两 种 1 9 ,3 2 ,4 2 1 : 内 联 硬 件描 述， 即 在 程 序代 码中明确地加入硬件描述，一般使用己 有的i p 核，并提供与所用软件的接口， 常用于开发需要标准功能的应用， 如f f t , j p e g编解码器等。 二是自 动编译即 可重定位编译器，以便将高级编程语言编译为在微处理器上执行的目 标代码和 编程可重构硬件的配置信息，使用可重构硬件的程序只需调用系统函数即可。 但是，它们对编译器的要求很高，既要求编译器能自 动识别出软件部分和硬件 部分，将软件部分调度到微处理器上执行，又能对可重构硬件进行重构，并执 行相应的计算功能，是非常困难的。 软硬件协同设计即软件和硬件协同工作使得系统不仅功能正确而且满足系 统需求， 如性能要求、 面积和功耗等限制， 是嵌入式系统设计的重要方法6 3 ,6 4 1 软硬件划分是软硬件协同设计的关键问题之一，统计数据表明，包括软硬件划 分在内的最初1 0 %的系统级设计过程对于最终的设计质量和成本有8 0 %的影响 第一章绪论 6 5 1 。 由 于 可重构系统 通常都包 括微处 理 器和可重构硬 件两部分，因 此能够自 然 地应用软硬件协同设计的方法。但是可重构硬件的动态部分重构能力使得硬件 电路的功能可以根据程序的执行来选择，不象传统的软硬件协同设计中那样， 电路综合之后物理地配置到电路上之后便不能更改。这种灵活性打开了硬件电 路的新应用，出现了新的软硬件协同设计问题，必须要考虑可重构硬件的动态 重构和重构所带来的延时等特性。 基于i l p的时域划分和设计空间开发相结合的算法虽然考虑了f p g a的重 构特性， 但它仅仅实现了 运行时可重构设计的延时最小化，不能实现软硬件划 分 6 6 1 。 将 软 硬件 划分、 硬 件 设 计 空 间 开 发 和调 度 等集 成在 一 块 实 现的 启发 式技 术，能将任务图描述的应用映射到异构系统结构上，在硬件面积约束条件下追 求任务的最小执行时间。该技术采用了 迭代方法，并且考虑了硬件协处理器的 动态重构能力，但它没有考虑重构延时 和模块布局等问 题【6 7 1 基于动态重构系统结构的离散时间系统的运行时软硬件协同设计方法分为 三个阶段，应用阶段包括离散时间系统和设计约束的描述，系统描述使用独立 的离散事件类:静态阶段包括协同设计的代价估计、软硬件划分和综合等，此 阶段仅仅处理离散事件类;动态阶段包括软硬件调度和动态重构逻辑的多上下 文调度等，这里采用了 集中控制的手段，并与应用的执行并发进行，以更好地 满足 系统的时间 约束6 8 ,6 9 1 。 但是， 该 方法 通用 性不好， 且不 适合于 具 有 动态部分 重构特征的可重构系统应用. c o r d s 系统采用抢占 式动态优先级多 速率调度算法， 能够综合包含动态重 构f p g a的实时、 多 速率分布式系统上的 任务7 0 1 。 它从f p g a , 微处理器和通信 资源中自 动选择一个分配，并驱动任务和通信事件的调度。 此外，借助单个任 务的优先级，它还优化了 在 f p g a上执行的任务序列，以减小系统中的重构开 销。 c r u s a d e 是一个启发式构造协同综合算法， 能够综合由 动态重构f p g a构 成的分布式系统上的任务7 1 1 . 它在满足实时性和其它约束条 件的同时， 优化了 硬件系统结构的代价，而且还能满足容错系统的需求.然而，由 于它采用的启 发式算法，因此不能保证解的最优性，而且只考虑了可重构硬件的重构延时， 并没有考虑其部分重构特性。 c o s y n也是一个启发式协同综合技术， 支持多种 类型的处理元素和通信/ 计算的并发或串行执行，采用基于动态结束期优先级的 调度算 法， 以 及采用 任务聚 簇 技术来 处 理关 键路径的 动态 特征 7 2 1 。 但是， 对f p g a 的动态重构及其模块布局等考虑不足，而且也不能保证获得最优解。 第一章绪论 基于单个微处理器和单个可重构硬件构成的动态重构系统， 采用遗传算法实 现了系统的软硬件划分方法，虽然考虑了可重构硬件的动态重构及其带来的重 构延时等特性，但不考虑任务布局而仅从数量上分配可重构硬件资源是不合理 的 17 3 1 。 在实现软硬件划分时 虽然考虑了 可重构硬件上的资源分配， 但也仅限 于 1 d 线性任务布局的情况，尽管对任务进行了调度顺序上的优化，其资源的利用 率还是比 较低7 4 1 由于可重构硬件往往都只有一个配置端口， 因此对于可重构系统软硬件协同 设计的 研究，既要考虑可重构硬件动态重构及其带来的重构延时等开销， 还需 要考虑可重构硬件上的任务布局和电路功能的重构冲突等问题。传统的软硬件 协同设计虽然比较成熟，对于可重构系统而言，需要在充分考虑系统新特征的 基础上， 进一步研究适合发挥系统协同工作性能的有效方法。 1 . 4 . 5 其它 高级综合技术是一种有效利用可重构硬件的技术，使用一个基本的硬件库 可以 快速地产生硬件功能， 但传统的高级综合技术都是针对a s i c实现的， 其逻 辑综 合、 布局和 布线等 所 花费 的 开 销是 可重构系 统 所不可 接受的 7 5 ,7 6 1 现 在 使 用的 硬件 描 述 语言 主 要 是v h d l 和v e ri l o g ， 编 程 效 率比 较 低， 且 不 易 于软 件程序员 使用。 虽 然s y s t e m c , h a n d l - c 等高 级硬 件描 述 语言 也 取得了 很 好的发 展， 但程序效率比 较低【7 7 ,7 8 1 在可重构系统设计中，传统的e d a工具仍然不完善，不能充分利用可重构 硬件的动态部分重构等特征。 第五节本文主要工作 系统结构的现代发展趋势已 经表明 在以高性能为目 标时， 也需要考虑系统的 成本以及可扩展性和耐故障性。可重构硬件的动态部分重构能力使得可重构计 算成为一种灵活高效的计算模式，由微处理器和可重构硬件构成的动态重构系 统充分利用了 两者的优势，并在解决诸如通信、多媒体等领域的应用时表现出 了很好的性能。 在微处理器和可重构硬件构成的动态重构系统上解决应用问题时， 首要的就 第一章绪论 是确定出哪部分由微处理器以软件方式执行，哪部分由可重构硬件以电路方式 执行;找出在可重构硬件上执行的任务集合之后，使用可重构硬件高效地执行 它们，则需要良好的可重构资源管理以及任务布局的方法;当然，这都离不开 部分重构技术的支持，降低部分重构的运行时开销有利于提高系统的性能。本 文在当前可重构硬件及相关技术水平下，针对系统的重构开销优化、可重构资 源管理、任务调度与布局和软硬件划分等问题进行研究，提出了一些有效的理 论和方法，使系统能够充分利用微处理器和可重构硬件的优势，提高系统的整 体性能。本文的主要工作和创新点如下: ( 1 )分析了部分位流的结构和部分重构的性能，并实现了 一种动态模块重 定位的方法。v l s i 技术的发展提供了在运行时对可重构硬件进行动态部分重构 的能力，本文以 f p g a为硬件平台实验可知，基于模块的部分重构能够有效地 降低系统的重构开销，为实现可重构计算奠定了良 好的基础。动态模块重定位 方法能够快速地修改位流中的帧地址，从而改变模块在芯片上的重构位置，避 免了重新在新位置上产生位流的开销，基于模块重定位的重构方式为动态重构 系统的应用提供了有力支持。 ( 2 )提出了一种基于配置页的可重构资源管理方法，分析了配置页尺寸的 确定方法， 并基于v ort e x i i 平台f p g a实现了相应的原型系统。 系统对不同的可 重构资源进行分类建模，并以配置页为基本单位进行管理。系统在运行时可以 根据应用需求动态地分配一段由不同数量的连续配置页构成的逻辑区域，以及 回收和合并空闲配置页等， 有效地实现了1 d划分下的可重构资源管理。 ( 3 ) 提出了可重构硬件的一种2 d区域模型， 并实现了该模型下的可重构资 源管理和任务布局的算法及性能分析。基于任务上边界的最大空闲矩形保持方 法能够有效地管理可重构硬件上的空闲资源，为使用f f 和启发式b f算法实现 2 d任务布局提供条件， 有效地实现了可重构资源的动态分配、回收与合并等操 作。与 1 d划分相比，能够提高可重构硬件的资源利用率。 ( 4 )提出了一种面向 动态重构系统的软硬件划分方法。动态部分重构能力 打破了硬件电路的传统应用模式，传统的软硬件协同设计方法己 经不能满足动 态重构系统的需要. 本文在2 d区域模型下， 考虑可重构硬件的动态重构及其重 构延时和任务的并发执行等特性，研究了 对系统性能有重要影响的软硬件划分 与调度方法，较好地实现了应用到动态重构系统的映射。 第一章绪论 第六节本文内容安排 本文就动态重构系统结构涉及的几个关键问题进行了研究，全文共分为七 章。 动态重构系统的体系结构是本文工作的基础， 本文在第二章进行了阐述， 并 重点介绍了系统组成，提出了要解决的关键问题。 重构方式的选择和应用是动态重构系统的关键所在， 重构开销是影响系统性 能的关键因素。第三章对部分重构及性能进行分析，提出了在线改变动态模块 重构位置的方法和工具，为任务布局和软硬件协同 工作打下基础。 现有的可重构硬件易于实现以s l i c e 列为单 位的 重构， 利用v u t e x 1 1 f p g a为 平台， 第四章实现了1 d划分下的可重构资源管理原型系统， 并给出了相应的实 验分析。 考虑可重构硬件的内在结构及其发展趋势， 第五章实现了2 d区域模型下的 可重构资源管理和任务布局，比1 d划分更能充分地利用可重构硬件， 取得了较 高的资源利用率和系统性能。 目前还没有较好的可重构操作系统，考虑可重构硬件的动态重构及其重构 延时、 2 d区域模型下的资源管理以及硬件任务的并发执行等特性，第六章重点 研究了对可重构系统的性能有重要影响的软硬件划分与调度问题，并进行了性 能仿真与分析。 最后一章对全文进行总结并描述了未来的 工作。 第二章动态重构系统结构 第二章动态重构系统结构 近年来， 可重构硬件集成度和规模的提高， 为动态重构系统成为通信、 多媒 体技术等应用的解决方案提供了硬件基础。 与a s i c设计相比， 基于可重构硬件 的动态重构系统能够进行在系统编程，设计方式灵活、开发周期短，便于对系 统进行功能裁减、扩充和升级。 第一节整休结构 微处理器将整个系统看作是一系列内存位置， 与可重构硬件通过共享内存进 行通信。可重构硬件执行不同的面向应用的粗粒度任务，作为微处理器的协处 理器运行， 其系统结构如图2 . 1 所示。 在系统运行时， 编译好的程序存放在指令 存储器中，调度单元负责将指令调度到相应的处理单元上执行，根据不同的应 用或应用的不同阶段，可重构硬件的动态重构能力能够使其实现不同的面向应 用的专用电路，实现在微处理器中不能实现或者实现效率不高的任务，以加速 整个应用程序的执行。如果将微处理器的功能集成在可重构硬件上，则可以构 成动态重构片上系统。 初始化 微处理器 位流库 配里块 配置端口 i t a c等 位流缓存 微处理器核 ( 如mi c r o b l a m) i c a p 胧卜l 喇回善息丰 藻 蓬 q 帷程叫 动扁-口 一口 一口 一_._一_ 图2 . 1动态重构系统结构 2 5 第二章 动态重构系统结构 2 . 1 . 1 部分重构 目前已有很多可重构硬件支持全局重构和部分重构， 即使很小的逻辑功能修 改，全局重构也需要对整个芯片进行全部重新配置，因此配置的时间开销相对 较大。而部分重构能够针对被修改的逻辑区域进行局部功能配置，与全局重构 相比，时间开销大大降低， 有利于系统的性能提升。 在动态重构系统结构中， 动态重构区域是芯片上分配给管理功能占 用的逻辑 资源以外的区域，是在系统控制下实现部分重构的 载体。根据对动态重构区域 的逻辑资源重构和使用情况，可将其视为由若千个相互独立的相同大小的配置 块组成的， 如图2 . 1 所示。 在系统运行过程中， 相邻的多个配置块可以合并为一 个更大的配置块，供用户根据需求进行相应的配置，实现面向具体任务的电路。 目 前， x i l i n x , a tr n e l 等公司生产的f p g a可支持部分重构，而且提供了相 应的开发环境，能够有选择地更新芯片上指定区域的逻辑资源，不被选择的区 域基本不受影响，为运行时改变未被使用的动态模块提供了可能，能够更加有 效地利用逻辑资源。而且， 部分重构改变了时间上互斥的概念，将应用划分成 更细粒度的任务模块，突破了硬件容量的限制，通过适当的任务分解可以解决 任意规模的应用问题。 2 . 1 . 2 两阶段法 与a s i c实现方式不同， 在可重构硬件上实现的功能需要在执行之前进行相 应逻辑资源的配置，然后使用配置好的逻辑电路进行任务处理，因此将可重构 硬件上的任务处理分为两个阶段:重构和执行。重构阶段是根据应用的需求完 成逻辑资源的功能配置，执行阶段则完成实际需要执行的操作。根据解码预取 的指令，可以在执行之前足够长的时间内重构逻辑资源，从而隐藏重构延时， 减小任务的处理时间。 由于可重构硬件掉电后其逻辑功能即消失，因此每次使用时需要进行全局 配置， 可以 通过芯片外部连接的e p r o m来实现， 存储配置微处理器等静态功能 所需的配置信息。除了在设备启动时需要进行全局配置外，在应用执行的过程 中一般只进行逻辑资源的部分重构，因此系统只增加一些专门针对部分重构的 指令即可。应用需求的多样性导致了可重构硬件上的电 路模块的多样性，考虑 到指令空间的有限性，并不为每种功能的电路模块都设置重构和执行指令，而 第二章动态重构系统结构 是采用直接指向对应部分位流或者电路模块的位置作为参数，通过给出不同的 位流和电路模块的位置参数从而实现不同的功能，降低了指令集扩展的复杂性 和对指令空间的需求。 扩展指令的格式及其功能描述如下: 部分重构指令:使用相应的位流文件配置可重构硬件上的部分逻辑资 源， 从而实现运行所需功能的配置。 其中，位流文件的起始地址由位置 参数字段指定，根据逻辑资源的动态分配结果，可对位流中的位置信息 进行相应的修改以改变模块在芯片中的重构位置。 执行指令:用于启动一个在可重构硬件上的电路模块的执行， 真正实现 任务处理，位置参数字段指明了要执行的电路模块在芯片中的位置。 第二节 静态模块 在系统运行时，静态模块能够根据己定义的应用需求控制可重构硬件上的 所有活动，包括与微处理器的通信和对动态重构区域的逻辑资源管理与功能重 构.静态模块一般包括控制器、位流管理器、 位流缓存、资源管理器、重构调 度器、 配置端口 和互连总线等部分，它可以 在可重构硬件中完全由硬件实现， 或者将其部分功能在微处理器上实现。 ( 1 )控制器 控制器需要操作和监视所有的资源， 其典型流 程为: 接收应用并将其调 度到 相应的处理器上执行，如果是在微处理器上执行则视其忙闲而定，如果是硬件 电路执行，则检查当前可重构资源的使用情况，首先为其分配资源， 然后使用 位流并通过配置端口 将数据写入配置r a m，并启动电路模块的执行。 i p 核是一种预先设计好的、 己通过验证的、 具有某种确定功能的集成电 路或 部件， 具有良 好的可重用性。 控制器可以使用己 有处理器i p核来实现， 如x i l in x 的m ic r o b l a z e , a l te r a 的n io : 等5 ,6 ,7 9 . m ic r o b la z e 能 够配 置 为3 2 位的 微 处 理 器， 并且带有大量外设和接口 库，能够提高设计的可靠性，降低系统的设计成本。 对于某些速度要求很高的应用，为了解决软核处理速度不够的问题，可以采用 硬 核 来 实 现 ， 如x il in x 的p o w e r p c , a l te r a 的a r m 9 2 2 t 硬 核5 .6 .9 1 。 硬 核 提 供 给 用户的是电 路物理结构掩模版图和全套工艺文件，易于使用且性能很高。使用 第二章动态重构系统结构 处理器核的形式可以充分发挥处理器灵活性高的特点，对控制类操作的执行效 率高，有利于提高整个系统的性能。 ( 2 )互连总线 片上总 线 ( o n - c h i p b u s ) 技术便 于 使 用i p 核的 系统集 成，目 前 的 互 连总 线 结构主要有i b m的c o re c o n n e c t , a r m的a m b a和s i l i c o r e c o r p 的w i s h b o n e 三种i$ o -r 1 。 其中， 片上总 线协议w i s h b o n e 只定 义了 一 种高 速总线， 结 构简 单92 1 c o re c o n n e c t 提供了三种基本结构: 处理器内部总线p l b 、 片上外围总线o p b 和设备 控 制 总线d c r is 0 1 . p l b 是为总 线 传输的 发出 者和 接受 者之间 提供高 带宽、 低延迟的连接，性