（计算机应用技术专业论文）可重构计算的任务在线调度与放置策略研究.pdf

r e s e a r c hi ns t r a t e g i e so fo n l i n et a s k ss c h e d u l i n ga n dp l a c e m e n tf o r r e c o n n g u r a b l ec o m p u t i n g b y c h e nz h i b e ( h u a i h u au n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n c o m p u t e rs c i e n c ea n dt e c h n o l o g y i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl ir e n f a ，i n s t r u c t o rf ub i n j u n e ，2 0 1 l 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：1 斌考 日期：d _ pt m 歹月拥 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名：倔魄 导师签名翰逡 t 、矿3 日期：文州年王月沙日 日期：妇c 侔多月加日 可重构计算的任务在线调度与放置策略研究 摘要 有效融合了专用集成电路( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t 。a s i c ) 与通 用目的处理器( g e n e r a lp u r p o s ep r o c e s s o r ) 优势的可重构计算系统，以其良好的灵 活性，可重构性以及优异的计算性能，日益成为学术界与工业界应用研究的热点。 可重构计算研究主要涉及可重构软硬件平台、可重构操作系统、编程语言及相关 算法与实际工程应用等领域。 针对可重构计算及其硬件平台的特点，阐述了可重构计算中任务调度与放置 的重要性。任务调度主要关注硬件任务与可重构区域的映射，受可重构资源数与 任务间时序关系等的影响，目标为降低任务的总执行时间与可重构平台的配置开 销；硬件任务放置旨在提高可重构芯片的利用率与任务的接受率，侧重对可重构 资源的管理，主要受制于可重构空闲区域的大小与放置方案。 充分考虑了任务间的数据依赖与通信约束、可重构平台的异质性以及任务非 并发执行对可重构系统性能的影响，对任务调度机制进行建模与分析，用有限状 态机( f i n i t es t a t em a c h i n e ，f s m ) 描述任务的时序转换、以有向无环图( d i r e c t e d a c y c l i cg r a p h ，d a g ) 表述任务间的依赖，提出了一种基于组策略的硬件任务调度 算法( c l u s t e r i n gs t r a t e g ys c h e d u l i n g ，c s s ) 。该算法能较好地平衡任务调度开销与 调度性能( 如任务总执行时间，f p g a 配置开销) ，并通过实验指出随非并发任务在 系统中比例的增加，任务总执行时间将急剧上升。 针对当前任务放置算法如h o r i z o n 、s t u f f i n g 、b e s t f i t t 和f i r s t f i t 等的不足提 出了基本改进方法。在一维资源模型中，提出了一种任务长度感知度的放置策略 ( l h a p s ) ，该策略是对h o r i z o n 与s t u f f i n g 放置策略的改进，能够有效地降低任务 的总执行时间与碎片数。 对硬件平台与调度算法进行了实验与性能测试。在x i l i n xv i r t e x i ip r o 上实 现了d e s 的部分动态可重构，验证了其在f p g a 上部分动态可重构的运行效果。 关键字：可重构计算；硬件任务；有向无环图；组策略调度；任务放置；部分动 态可重构 硕士学位论文 a bs t r a c t r e c o n f i g u r a b l ec o m p u t i n gs y s t e me f f e c t i v e l yi n t e g r a t e dt h ea d v a n t a g e so f g e n e r a lp u r p o s ep r o c e s s o r ( g p p ) a n da p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ( a s i c ) f o ri t s h i g hf l e x i b i l i t y , e x c e l l e n t c o m p u t i n gp e r f o r m a n c ea n dr e c o n f l g u r a 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 si n c r e a s i n g l yg a i n i n gt h ef o c u so fa l lc o m m u n i t i e s ，w h i c h m a i n l y i n v o l v e st h er e s e a r c hi n t or e c o n f i g u r a b l e c o m p u t i n gh a r d w a r e s o f t w a r e p l a t f o r m s ，r e c o n f i g u r a b l eo p e r a t i n gs y s t e m s ，p r o g r a m m i n gl a n g u a g e s ，c o m p i l i n g e n v i r o n m e n t ，t h er e l a t e da l g o r i t h m sa n da p p l i c a t i o n s i nt h ef o u n do ft h o r o u g h l y d i s c u s s i n ga n da n a l y z i n gt h ec h a r a c t e r i s t i c so f r e c o n f i g u r a b l eh a r d w a r ep l a t f o r m sa n dh a r d w a r et a s k s ，t h es i g n i f i c a n c eo f t a s k s c h e d u l i n ga n dp l a c e m e n t i n r e c o n f i g u r a b l ec o m p u t i n gs y s t e m a r ee l a b o r a t e d h a r d w a r et a s ks c h e d u l i n g ，o nt h ep u r p o s eo fr e d u c i n gt h er e c o n f i g u r a t i o no v e r h e a d f o rf p g aa n dt h eo v e r a l le x e c u t i o nt i m ef o rt a s k s ，i sm a i n l yd e d i c a t e dt os c h e d u l i n g t a s kt ot h eg i v e nr e c o n f i g u r a b l er e g i o n s ，w h i c hg e n e r a l l yr e s t r a i n e db yt h en u m b e ro f r e c o n f i g u r a b l er e s o u r c e s a n dt h et i m i n gb e t w e e nt a s k s w h i l e ，t a s kp l a c e m e n ta i m st o i m p r o v et h eu t i l i z a t i o no fr e c o n f i g u r a b l ec h i p sa n da d v a n c e st h ea c c e p t a n c er a t i oo f h a r d w a r et a s k s ，w h i c h u s u a l l ym o r et a k e s t h e m a n a g e m e n tf o rr e c o n f i g u r a b l e r e s o u r c e si n t oa c c o u n t b u ti t se f f i c i e n c yh a sd i r e c tb e a r i n gw i t ht h es i z eo ff r e e s p a c e sa sw e l la st h es t r a t e g yf o rp l a c i n gt a s k s b ys c r u t i n i z i n gt h ei n f l u e n c et ot h es y s t e mp e r f o r m a n c e ，w h i c hi sc a u s e db yt h e d e p e n d e n c i e sa n dc o m m u n i c a t i o nb e t w e e nt a s k s ，t h eh e t e r o g e n e i t yo fr e c o n f i g u r a b l e p l a t f o r m s ，p l u st h ec o n c u r r e n c yo fh a r d w a r et a s k s ，t h et a s ks c h e d u l i n gm e c h a n i s ma r e d i s c u s s e da n dm o d e l e d f u r t h e r , af i n i t es t a t em a c h i n e ( f s m ) w a si n t r o d u c e dt o d e s c r i b et h et r a n s f o r m a t i o no ft a s ki nr e c o n f i g u r a b l es y s t e m ，a n dt h ed i r e c t e da c y c l i c g r a p h ( d a g ) w a su t i l i z e dt op r e s e n tt h ed e p e n d e n c i e sb e t w e e nt a s k s ，a n dac l u s t e r i n g s t r a t e g y b a s e ds c h e d u l i n ga l g o r i t h m ( c s s ) w a sp r o p o s e d ，w h i c hn o to n l ye f f e c t i v e l y c o n t r i b u t e dt ot h ei m p r o v e m e n to fw h o l ee x e c u t i o nt i m ef o rt a s ka n dr e c o n f i g u r a t i o n o v e r h e a d ，b u ta l s og a i n e dag o o db a l a n c eb e t w e e ns c h e d u l i n gp e r f o r m a n c ea n dt i m e c o m p l e x i t y a d d i t i o n a l l y , r e s e a r c h e sa n de x p e r i m e n t si n d i c a t et h a tt h es e r i a l i z a t i o no f h a r d w a r et a s k sw i l li m p a c tt h ep e r f o r m a n c eo fr e c o n f i g u r a b l es y s t e m ss e v e r i o u s l y , w h i c hs h o u l db ew e l ls t u d i e da n ds e t t l e di nf u t u r e t h e n ，b a s e do na n a l y z i n gt h ee x i s t i n gs y s t e mm o d e l ，t a s km o d e la n dr e s o u r c e i i i 可重构计算的任务在线调度与放置策略研究 m o d e l ，a sw e l l a st h e i rr e l a t i n g h y p o t h e s i z e s ，t h eg e n e r a l l yu s e dt a s kp l a c e m e n t a l g o r i t h m sa r ed i s c u s s e d ，s u c ha sh o r i z o np l a c e m e n t ，s t u f f i n g ，b e s t f i ta n df i r s t f i t f u r t h e r , t h er e l a t e di m p r o v i n ga p p r o a c h e sf o rt h e s ea l g o r i t h m sa r ep r o p o s e d ，w h i c h p r o v i d e saf i r mf o u n d a t i o nf o rt h ei m p l e m e n t a t i o no ff u t u r ea l g o r i t h m s w i t hr e s p e c t t ot h eh i g hd e f r a g m e n t s ，a n dl o n gt a s ke x e c u t i o nt i m eo fh o r i z o na n ds t u f f i n g p l a c e m e n t ，al e n g t h - h e i g h t a w a r ep l a c e m e n ts t r a t e g i e sw a sp r o p o s e d ，w h i c hc a n c o n t r i b u t et ol o w e ro v e r a l lt a s ke x e c u t i o nt i m ea n dl e s sd e f r a g m e n t s f i n a l l y , b a s e do nt h ex i l i n xv i r t e x i ip r op l a t f o r m ，u n d e rt h es u p p o r to fs e v e r a l s o f t w a r et o o l sp r o v i d e db yx i l i n x ，t h ep a r t i a ld y n a m i c a lr e c o n f i g u r a t i o nf o rd e sw a s i m p l e m e n t e d ，a n dt h er e s u l t so fi tw e r ev e r i f i e d 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 ；h a r d w a r et a s k s ；d i r e c t e da c y c l i c g r a p h ；c l u s t e r i n gs c h e d u l i n gs t r a t e g y ；t a s kp l a c e m e n t ；p a r t i a ld y n a m i c a l r e c o n f i g u r a t i o n i v 硕士学位论文 目录 学位论文原创性声明与学位论文版权使用授权书i 摘要j i i a b s t r a c t i i i 插图索引v i i 附表索引i x 第1 章绪论1 1 1 课题来源1 1 2 目的与意义1 1 3 研究内容2 1 4 本文工作3 1 5 本文结构3 第2 章相关研究综述4 2 1 可重构技术的出现一4 2 2 可重构技术的相关理论5 2 2 1 可重构技术的定义与分类5 2 2 2 可重构计算的研究现状6 2 3 任务调度与放置策略研究现状8 2 3 1 可重构计算系统模型9 2 3 2 任务模型9 2 3 3 资源模型1 0 2 4 当前基于不同资源模型的研究1 l 2 4 1 基于1 d 资源模型1 1 2 4 2 基于2 d 资源模型1 2 2 5 相关研究分析1 5 2 5 1 挑战与问题1 5 2 5 2 亟待解决的问题1 6 2 6 本章小结16 第3 章组策略硬件任务调度l8 3 1 硬件任务调度的相关研究1 8 3 2 问题建模与相关定义2 0 3 2 1 任务模型：。2 0 v 可重构计算的任务在线调度与放置策略研究 3 3 调度策略2 2 3 3 1 调度目标2 2 3 3 2 调度算法( c s s ) 及描述2 4 3 4 本章小结2 6 第4 章硬件任务放置策略2 7 4 1 相关概念与定义2 7 4 2 问题建模与假设2 8 4 2 1 系统模型2 8 4 2 2 可重构平台模型2 9 4 2 3 任务模型2 9 4 3 放置策略2 9 4 3 1 一维放置算法2 9 4 3 2 二维放置算法3 4 4 4 总结3 6 第5 章实验与性能测试3 7 5 1 部分动态可重构的实现3 7 5 1 1 硬件平台3 7 5 1 2 软件平台3 9 5 2 实验设计与实现4 l 5 2 1d e s 的动态可重构。4 1 5 2 2c s s 算法实验与分析4 4 5 3 本章小结4 9 总结与展望5 0 参考文献5 2 致谤f 5 8 附录a 攻读学位期间所发学术论文及参与科研项目5 9 v i 硕士学位论文 图1 1 图1 2 图1 3 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 l 图2 1 2 图3 1 图3 2 图3 3 图3 4 图3 5 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图5 1 图5 2 图5 3 插图索引 异构可重构平台结构图2 任务间的数据依赖2 任务间的数据相关2 可重构系统的发展4 细粒度f p g a 内部结构图5 c h e s s 的逻辑结构图6 静态可重构原理图6 动态可重构原理图6 可重构硬件体系结构图7 s o h r s 的体系结构8 可重构调度系统模型图9 硬件任务执行模型1 0 可重构芯片结构10 一维资源模型1o 二维资源模型1o 硬件任务执行模型1 9 硬件任务调度过程2 0 状态转换时序图2 1 一个d a g 实例2 2 经c s s 调度后2 2 可重构资源块2 8 可重构计算系统模型2 8 l h a p s 算法流程图3 2 h o r i z o n 放置效果3 3 l h a p s 放置效果3 3 s t u f f i n g 放置效果3 4 l h a p s 放置效果3 4 可重构资源的管理3 5 v i r t e x i ip r o 开发板整体框架3 8 v 2 p r o 实现部分可重构的框架3 8 基于i c a p 的部分动态可重构架构3 9 i 可重构计算的任务在线调度与放置策略研究 图5 4e d k 9 1 主界面4 0 图5 5i s e 综合、实现d e s 加密模块后所生成的文件4 l 图5 6d e s 加密模块i p 核的主要部分4 2 图5 7d e s 解密模块i p 核的主要部分4 2 图5 8利用s d k 编写d e s 的测试用例4 3 图5 9 利用p l a n a h e a d 进行p r 设计后的生成文件4 3 图5 10加密结果显示4 3 图5 1 l解密结果显示4 4 图5 1 2任务数与总执行时间的关系一4 5 图5 1 3任务数与配置个数的关系4 5 图5 1 4 任务总执行时间与芯片占用面积的关系4 6 图5 15串行任务所占比例与总执行时间之间的关系4 7 图5 1 6 任务数与计算开销之间的关系4 7 v i i i 附表索引 表3 1基于d a g 任务调度的形式化描述2 3 表4 1任务集实例3 0 表4 2放置算法复杂度对比3 6 表5 1f p g a 资源列表3 7 表5 2i s e 设计工具表4 0 表5 3部分参数取值表4 4 i x 硕士学位论文 1 1 课题来源 第1 章绪论 本课题源自国家高技术研究发展计划( 8 6 3 计划) ：“面向可重构片上系统的过 程级动态软硬件划分研究”。该项目以研究与发展统一规范的软硬件划分工具为目 标，以如下方面为主要研究内容： ( 1 ) 高效、灵活的动态软硬件划分算法； ( 2 ) 可重构片上系统编程模型； ( 3 ) 过程级软硬件的同步与通信策略。 而硬件任务的在线调度与放置是软硬划分后的一个必然步骤，因此该课题是 对此项目研究扩展，具有一定的延续性与前瞻性。 1 2 目的与意义 可重构计算系统结合了通用目的处理器( g e n e r a lp u r p o s ep r o c e s s o r ) 灵活、 可反复编程的优势与专用集成电路( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ) 计算 精度高速度快的特点，已广泛应用于各种高性能计算( h i g h p e r f o r m a n c e c o m p u t i n g ) 中，如通信、图形图像处理、信号处理、加解密、航天航空、医疗器 械以及军事领域，具有强大的研究潜力与市场前景。 可重构计算领域的研究涉及软件硬件平台、操作系统、编程语言、编译工具、 算法等多个方面，并且从2 0 世纪6 0 年代开始逐渐由起步到发展，再日趋成熟， 但相对可重构硬件，软件工具与算法的发展要滞后许多。针对该现状，本项目集 中在理论研究，如动态软硬件划分算法与统一编程模型，与工程实现( 设计一个软 硬协同设计工具，封装一些软硬件函数协同函数库等) 两方面进行了深入的工作。 当软硬件任务划分完成后，必须对该过程中所得到的硬件任务进行调度与放置， 使其能够在f p g a 可重构芯片上高效地执行。没有合理、高效的调度算法，软硬 件划分的效果就很难到延续；而好的划分策略，对硬件任务调度性能也至关重要。 两者相辅相成，调度是划分的扩展；划分是调度的前提。 针对可重构计算平台与硬件任务的特点，可重构计算环境下任务调度与放置 目前主要存在以下挑战： ( 1 ) 任务处理量较嵌入式计算环境下大一个甚至几个数量级。可重构计算主 要用于计算密集型与高性能计算环境，计算复杂度大，精度要求高。 ( 2 ) 任务并行性高。可重构计算硬件任务的一个重要特点是具有较高的并行 可重构计算的任务在线调度与放置策略研究 性，能同时布局到可重构非重叠区域执行。 ( 3 ) 平台较为复杂、可靠性要求高。可重构计算平台通常包括微处理与可重 构处理平台如图1 1 所示，其异构性给算法设计带来了新的挑战。 国壶 图1 1异构可重构平台结构图 ( 4 ) 需要考虑任务间的依赖关系约束与相关性，如图1 2 与图1 3 所示。典型 情况下，任务在平行执行过程中，可能存在数据与控制相关。 盈 甜 图1 2 任务间的数据依赖图1 3 任务间的数据相关 因此，基于充分考虑硬件任务与可重构平台的特点，设计一种合理、高效的 硬件任务调度算法提高调度性能、降低任务的总执行时间与f p g a 的配置开销， 具有重大的理论与现实意义。 1 3 研究内容 针对以上挑战，本文将重点着力于研究与探讨可重构片上系统的以下问题： ( 1 ) 可重构计算硬件平台。硬件平台是理论研究的基础、算法实现的载体。 只有深入了解f p g a 平台的体系结构与特点，才能提出高效的算法并实现部分动 态可重构。 ( 2 ) 硬件任务调度与放置的可重构体系结构。体系结构设计的合理性对系统 功能的实现起决定性作用，也影响着调度算法的有效性与可靠性。可重构计算中 调度器面临的任务特点和环境特点与传统冯诺伊曼体系结构的计算方式大相径 庭，所以其设计方法和基本架构也必定与之相去甚远。基于该混成异构模式的任 务调度体系结构与是本文研究内容之一。 ( 3 ) 可重构计算任务调度与放置算法。本文将对现有针对硬件任务调度与放 置算法进行详细研究，讨论其优势与不足，为本文的调度与放置机制建模提供坚 实的理论基础。 ( 4 ) v i r t e x i i 系列f p g a 部分可重构特性。对f p g a 的可重构特性进行详细 且深入的研究，为以后实现与嵌入式实时操作系统，如u c l i n u x ，u c o s 等与f p g a 的无缝连接提供理论与工程基础。 一一 2 硕士学位论文 1 4 本文工作 本文在“面向可重构片上系统的过程级动态软硬件划分研究 项目的基础上， 对其进行延续，主要进行以下工作： ( 1 ) 硬件任务调度策略建模与分析。针对硬件任务与可重构平台的特点，本 文将对调度过程进行建模，并将系统中任务间的依赖关系进行抽象，提炼出一个 直观的调度模型并对其进行理论分析与实验证明，以说明该模型的有效性。 ( 2 ) 硬件任务调度算法设计与分析。通过对现有相关研究进行分析与综述， 本文将提出一个合理的任务调度模型为调度算法的设计与实现提供理论框架，在 该模型的基础上，以任务间的依赖关系、系统资源约束、配置数、平台异质性、 部分任务独占资源为评价因子，提出一种基于簇调度硬件任务调度策略。 ( 3 ) 硬件任务放置算法的详细分析。详细分析几种任务在线放置算法实现方 式，算法性能与优劣，为进一步设计高效合理的任务放置算法而提供可靠的理论 依据。同时基于当前放置算法的不足，提出一种有效的方法对其进行改进，以减 少硬件任务放置产生的碎片数，并降低总硬件任务执行时间。 ( 4 ) 部分动态可重构的设计与实现。部分动态可重构是项目工程实现的一部 分，通过实现部分动态可重构技术，可以在将来的研究中将操作系统和调度算法 融入到这一技术中，与之有机结合，高效地对可重构资源进行管理，充分发挥可 重构平台动态可重构的优势。 1 5 本文结构 本文共包括6 章内容：第1 章为绪论。介绍课题的来源，目的与意义，以及 本课题的研究内容与主要工作。第2 章介绍了可重构计算中的基本概念，并对国 内外相关研究进行综述，以说明该环境下的研究需求与着力点。第3 章对调度问 题进行建模与分析，并提出一种基于组策略的调度算法。第4 章对当前基于一维 资源模型与二维资源模型的经典算法进行了分析与探讨，讨论了对其进行改进的 构想，并针对基于一维资源模型放置算法的不足，提出一种任务长宽感知度的放 置策略。第5 章首先介绍了实验平台与工具，并给出了实现d e s 部分动态可重的 方法与步骤，然后对文章调度算法进行定量分析。最后，第6 章对总结了本文工 作，并展望未来的研究。 可重构计算的任务在线调度与放置策略研究 第2 章相关研究综述 2 1 可重构技术的出现 传统的专用集成电路( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t s ，a s i c ) 虽然具有 较好的计算速度，可靠的计算性能，但它的发展空间在很大程度上限制受限于其 灵活性。因为通常它专为特定算法或电路设计，一旦固定后，很难根据实际需要 对其进行更改。加之，近年来随着微电子技术与纳米工艺技术的蓬勃发展，使得 在一个微型芯片上便可以集成数百万门电路，并且还能在保证其嵌入式系统良好 性能的前提下对大量复杂性信息进行高效处理。这使得a s i c 设计方式的复杂度 急剧攀升，并且系统潜在出错的风险也日益增加，也导致了该方式设计成本与设 计周期的不断上升，从而影响上市时间。 而通用集成电路( g e n e r a lp u r p o s ep r o c e s s o r , g p p ) ，一般通过软件程序来驱动 处理器。因此，该方式往往拥有优越的灵活性，并且开发周期短，成本低；还能 够通过升级程序来对其进行复写。但是这种电路计算慢、精度低，很难满足日益 增长计算密集型处理需求。 在2 0 世纪中下叶开始，不少研究者开始关注如何在一块芯片上结合这两者的 优势。上世纪6 0 年代加州大学洛杉矶分校( u c l a ) 的g e r a l de s t r i n 就提出了可重 构计算设想的雏形，并设计了原型系统【l 】；7 0 年代末，前苏联的s u e t l a n ap k a r t a s h e v 和s t e v e ni k a r t a s h e v 博士率先引入了动态可重构系统的基本概念与基本 架构；1 9 8 5 年，x l i n x 公司推出了第一款现场可编程门阵列( f i e l dp r o g r a m m a b l e g a t ea r r a y s f p g a ) 逻辑器件将可重构计算技术带入了人们的视野，并逐渐促进了 对该领域应用研究的升温。文献【2 】指出了可重构计算系统如图2 1 所示的发展。 第一代第二代第三代 发现问题 i蛔蚺由c ，i 1p 。口 。v m t 个口口1 基于计算流的1 s c 0 盹 通信瓶颈 卜一租私厦3 乱广1 m 盯叭隧广 暮+ 系统l 。l f i p s 0 ct r 【脚e tl +叠 配置方案 p r i s a叫细粒度s 卜1 一玉泣1h 钽 圣 i d e c p e r l e 内部互连网络 - d 林韶鳍网睁詈l s p i s h ，l 娶 刊 沉水配置 卜1 p i p e r e n 嘣 运 s p l a s h - 厂 7 1 1 9 铺”艮且厂 “。”“ i+丑 i i 流水线t o l i e h 唧磷“ s p y d e r 灵活度低 t r a a s a o g z i f i e r 一一 e 下文切换l t r u m p e tf p s l i cl j 蠹； + 配置时同开镑。l “”“i i 。i 一 嚼 s o c 部分动态v i r t e x - i i 大 l 部分动态可重l一i文+ _ 叫。矿卜1 叭s cy i r t e x 广 玎重构 p r o 图2 1 可重构系统的发展 4 硕士学位论文 2 2 可重构技术的相关理论 2 2 1 可重构技术的定义与分类 。 可重构技术是通过改变数据流或控制流实现软件或硬件模块的不同功能，从 而在不改变硬件结构的前提下对系统进行重新配置【3 】。可重构计算是研究面向可 重构技术的重要方向之一，该领域主要研究高灵活性、高精度、低功耗、计算密 集型应用与体系结构。 通常可根据以下参数对可重构硬件进行分类： ( 1 ) 构建可重构模块的粒度：根据可重构系统中处理数据的大小可以将其分 成粗粒度体系结构、中粒度体系结构与细粒度体系结构【4 】。其中粗粒度体系结构 主要是为实现任务的字宽操作而设计。这些逻辑块通常为大型计算而作特殊优化， 具有良好的计算速度与精度。在实现函数级或过程级可重构时，粗粒度体系结构 往往比细粒度体系结构更有效率，如r a p i d 5 】架构是一种典型的粗粒度体系结构。 而细粒度的体系结构一般由一些混合内部网络与触发器组成，如图2 2 所示，这 种逻辑块通常可以写入简单的程序，如2 位的加法器等。由b r a s s 小组研发出 的g a r p 6 】便是一种典型细粒度结构，它可以根据2 - b i t 的输入进行多种操作 图2 2 细粒度f p g a 内部结构图 中粒度体系结构中通常使用比细粒度体系结构中稍大的逻辑块作为基本处理 单位，其目的为加速f p g a 计算，如c h e s s 7 1 体系结构的基本计算单元是4 b i t 的 a l u ，其设计主要是为了增加计算密度与提供足够的内部存储空间和带宽。逻辑 结构如图2 3 所示。 可重构计算的任务在线调度与放置策略研究 图2 3c h e s s 的逻辑结构图 ( 2 ) 可重构方式。根据可重构的方式可分为静态可重构与动态可重构。静态 可重构又称编译时可重构，其可重构资源在任务开始运行前便已配置好，在运行 期间保持不变。在该种可重构方式下，若要对f p g a 进行重新配置，系统必须先 暂停以等待对可重构资源进行重新配置。如图2 4 所示。 图2 4 静态可重构原理图 动态可重构也称为运行时可重构，如图2 5 所示，它允许可重构系统在运行 时进行重新配置，它又包括单上下文( s i n g l ec o n t e x t ) 可重构，多上下文可重构 ( m u l t i c o n t e x t ) ，如文献【8 】【9 】中提出的可重构系统，以及部分可重构，如x i l i n x v i r t e x 1 0 1 系列等。 图2 5 动态可重构原理图 2 2 2 可重构计算的研究现状 目前针对可重构计算的应用研究已日益深入，但总体集中在如下方面： ( 1 ) 可重构硬件平台； ( 2 ) 可重构软件平台及编程语言； 6 硕士学位论文 ( 3 ) 可重构操作系统； 2 2 2 1 可重构软硬件平台与编程语言 可重构硬件是可重构计算技术的基础与载体，对该领域的研究主要包括：可 重构硬件设备的基本架构，如f p g a 的体系结构、可重构粒度、偶合方式以及可 重构方式等。f p g a 的硬件体系结构通常如图2 6 所示，而f p g a 芯片一般由l u t ， c l b 以及触发器等可重构资源组成。可重构粒度如前所述一般分为粗粒度、细粒 度与中粒度。可重构方式有逻辑可重构、指令级可重构、静态可重构和动态可重 构。偶合方式即可重构处理单元( r e c o n f i g u r a b l ep r o c e s s i n gu n i t ，r p u ) 与可重构 计算系统的连接方式，包括以下方