（计算机科学与技术专业论文）动态可重构片上系统的任务在线放置和调度算法研究.pdf

硕十学位论文 摘要 可重构计算技术结合了通用处理器( g e n e r a l p u r p o s ep r o c e s s o r ，g p p ) 和专用集成电 路( a p p l i c a t i o ns p e c i 丘ci n t e g r a t e dc i r c u i t s ，a s i c ) 两者的优点，能够提供硬件的高效性 和软件的可编程性，是当前热门的研究课题之一。动态部分可重构技术是可重构计算技 术的最新进展之一，该技术能够在可重构系统正常工作的情况下，配置其中部分可重构 资源，使得一部分任务的执行能够与另一部分任务的配置同时进行，具有节约硬件资源 和增强系统灵活性的优点。 在动态可重构系统中，如何管理芯片上的空闲资源和在线分配可重构计算资 源，成为影响动态可重构系统性能的关键因素之一。为了尽量降低硬件任务的拒 绝率，减少整体任务的运行时间，提高可重构资源的面积利用率，使系统的性能 达到最优和次优，这需要采用高质量的放置和调度算法来对硬件任务进行合理的 管理和调度。 本文针对实时任务在二维可重构器件上的在线放置和调度问题，主要完成了 以下工作： ( 1 ) 提出了一种针对动态可重构系统的基于已放置任务三维邻接面( 3 da d js u r ) 的 放置算法。该算法采用顶点链表的任务管理方法，以到达任务与已放置任务的邻接 面最大化为目标，从所有可行的位置顶点中，选择最佳顶点来放置任务。 ( 2 ) 提出了一种基于顶点链表的l o o k a h e a d e s t 调度算法。该算法考虑在任务到达 时间后的一段时间内，通过模拟任务的开始和结束，获取代价函数值最大的放置 顶点和启动时间，从而使得任务更加整齐、紧密的放置，模拟时间一直持续到任 务的截止时间。仿真试验结果表明，在可接受的运行开销内，l 0 0 k - a h e a d e s t 算法 提高了芯片面积利用率并且降低了任务的拒绝率。 ( 3 ) 设计了一个支持软硬件透明编程模型的原型系统，然后在移植的l i n u 】【操作系统 内实现了所提原型系统的可重构资源管理器，该资源管理器能够对硬件函数的动态配置 与运行状态等进行统一管理，最后通过对实验室开发的硬件函数库进行测试，验证了 设计和实现的正确性。 关键字：可重构操作系统；实时；最迟开始执行时间；填充技术；邻接面；代价函 数 h a bs t r a c t r e c o n f i g u r a b l e c o m p u t i n gt e c l l l l o l o g y c o m b i n e st h e a d v a n t a g e s o f g p p ( g e n e r a l - p u 印o s ep r o c e s s o r )a n da s i c ( a p p l i c a d o ns p e c i f i c h l t e g r a t e dc i r c u i t s ) ， p r o v i d i n gt h eh a r d w a r ee 伍c i e n c ya n ds o r w a r ep r o g r a m m a b i l i t yi no n ep l a t f o 瑚i ti s o n eo ft h eh o t t o p i c so fc u r r e n tc o m p u t e rr e s e a r c h a st h em o s tr e c e n td e v e l o p m e n to f r e c o n f i g u r a b l ec o n l p u t i n gt e c h n o l o g y ，d y n a m i cp a r t i a lr e c o n f j g u r a t i o nc a nr e c o n f i g u r e ap a r to ft h er e c o n f i g u r a b l el o g i cd e v i c ew h i l eo t h e rp a r t so ft h es y s t e mc o n t i n u et o o p e r a t e ，e n 百b l i n gt h ep a r a l l e le x e c u t i o no fr l l n n i n gt a s k sa n dr e c o n f 豇蚤u r a t i o n s i tc a n e f 6 c i e n t l y u t i l i z et h e r e c o n n g u r a b l e r e s o u r c ea n d i m p r o v en e x i b i l i t y o ft h e 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 m a n a g i n gt h ef r e er e s o u f c eo nt h ec h i pa n ds c h e d u l i n gt h eh a r d w a r et a s k so n l i n ei n d y n a m i cr e c o n f i g u r a b l es y s t e mi so n eo ft h ec r i t i c a lf a c t o r st h a ti sc o n c e n l e dc l o s e l v w i t ht h ep e r f o m a n c eo ft h ei i y n a m i cr 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 i no r d e rt ol o w t h et a s k sr c je c t i o nr a t i o ，r e d u c et h eo v e r a l lr u n t i m ea n dh i g h e rc h i pu t i l i z a t i o n ，s oi t r e q u i r e sah i g hq u a l i t yp l a c e m e n ta n ds c h e d u l i n ga l g o r i t h mt om a k et h ep e r f o m a n c e o ft h es y s t e mo p t i m i z a t i o no rn e a r l yo p t i m i z a t i o n t h i sp a p e rf 0 c u s e so nt h eo n - l i n ep l a c e m e n ta n ds c h e d u l i n go fr e a l t i m et a s k so na t w o 。d i m e n s i o n a lr e c o n f i g u r a b l ed e v i c e ，t h er e s e a r c ho ft h i st h e s i sa d d r e s s e sa l lt h e s e a s p e c t s ，i nw h i c ht h en e wc o n t r i b u t i o n sa r e ： ( 1 ) ap l a c e m e n tm e t h o d o l o g yo np a r t i a l l yr e c o n f i g u r a b l ed e v i c e sb a s e do na d j a c e n t s u r f a c eo ft h ea l r e a d y 1 1 1 n n i n gt a s k s a c c o r d i n gt ov e r t e x e so ft h ea l r e a d y1 1 l n n i n gt a s k s ， t h ea l g o r i t h ms e l e c t st h eb e s tv e r t e xw h i c hh a st h em a x i m u ma d ia c e n ts u r f a c ev a l u e f r o ma l lt h ef e a s i b l ep l a c e m e n t st op l a c et h ea r r i v a l t a s k s ( 2 ) t h el o o k - a h e a d e s ts c h e d u l i n ga l g o r i t h mf o rd y l l 锄i cr e c o n f i g u r a b l ec o m p u t i n g b a s e do nt h ev e r t e x e so f p l a c e dt a s k s a f t e rt h en e wt a s ka 1 1 r i v a l i ts i m u l a t et h et a s k s b e g i n n i n go ft h er e s e r v a t i o n1 i s ta n dt h et a s k se n d i n go ft h ee x e c u t i o nl i s tu n t i lt h e l a t e s ts t a i r t i n gt i m e ，a n dg e tt h ev e r t e xa n ds t a r t i n gt i m et h a th a v et h em a x i m u mc o s t 如n c t i o nv a l u et os c h e d u l et h ea 玎i v a l t a s k s ，s oi tm i n i m i z et h ea r e af r a g m e n t a t i o n t h e s i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mc a na c h i e v eh i g h e rc h i pu t i l i z a t i o n a n dl o w e rt a s kr c je c t i o nr a t i o h o w e v e r ，t h er u n t i m ee m c i e n c yi sa c c e p t a b l e ( 3 ) d e s i g nap r o t o t y p es y s t e mw h i c hs u p p o r t st h es o f t w a r e m a r d w a r et r a n s p a r e n t p r o g r a m m i n gm o d e l ， t h e n i m p l e m e n tar e c o n f i g u r a b l er e s o u r c e m a n a g e ri n a t 1 7 a n s p l a n t i n g e m b e d d e dl i n u x o p e r a t i n gs y s t e m i tc a nm a n a g et h ed y n a m i c m 硕_ ：学位论文 c o n f i g u r a t i o na n dn l n n i n gs t a t e so ft h eh a r d w a r ef u n c t i o n s l a s ta f t e rt e s tt h eh a r d w a r e f u n c t i o nl i b r a r yo fo u rp r o je c tt e a m ，v e r i f yt h ec o r r e c t n e s so ft h ep r o t o t y p es y s t e m k e yw o r d s ：o p e r a t i n gs y s t e mf o rr e c o n f i g r a b l es y s t e m ( o s 4 r s ) ；r e a lt i m e ；l a t e s t s t a n i n gt i m e ；s t u m n gt e c h n o l o g y ；a d ja c e n ts u r f a c e ；c o s tf u n c t i o n 硕七学位论文 插图索引 2 1 基于s r a m 的f p g a 可编程位心1 4 2 2 可编程的路由连接口1 5 2 3f p g a 基本逻辑模块5 2 4f p g a 的路由结构哺1 6 2 5 典型的可重构计算系统的体系结构图口1 一6 3 1 可重构资源模型1 1 1 3 2b a z a r g a n 的划分决定1 3 3 3 最大空闲矩形放置( m e r ) 1 3 3 4 基于顶点链表的任务放置1 4 3 5 资源编码和顶点链表1 5 3 6 可重构芯片的编码1 6 3 7 顶点链表1 6 3 8 三维邻接面放置算法流程图1 8 3 9 初始放置图2 0 3 10 任务放置比较图2 1 3 1 1 实验结果比较2 2 4 1l o o k - a h e a d e s t 算法流程图2 9 4 2 任务放置图31 4 3 任务拒绝数比较3 3 4 4 可重构资源利用率比较3 3 5 1 软硬件协同函数库3 6 5 2 透明编程模型实现框架3 7 5 3 系统模型设计3 8 5 4 任务处理过程3 9 5 5 状态链表3 9 5 6 硬件函数状态图4 0 5 7 硬件函数调用过程4 1 5 8 可重构资源管理测试实例图4 3 v i l i 图图图图图图图图图图图图图图图图图图图图图图图图图图图图 动态可重构片，l ：系统的任务在线放置和调度算法研究 附表索引 表3 1 示例任务集2 0 表4 1 示例任务集3 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：彭日劾 日期1 年j 月夕日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“) 作者签名：童勺曰刎 刷醛长弧、垤火 日期：叫年，月f 7 日 嗍：1 钳肌7 日 硕上学位论文 1 1 课题来源 第1 章绪论 本课题取题于国家8 6 3 项目：“面向可重构片上系统的过程级动态软硬件划分 研究”，该项目面向可重构片上系统的特点和需求，以研究和发展灵活和高效的软 硬件划分工具为目标，重点研究过程级动态软硬件划分方法。其内容主要包括： 研究面向可重构片上系统的编程模型，统一封装和管理各种软硬件资源； 研究过程级动态软硬件划分算法，根据系统运行时信息进行动态软硬件划分， 并通过过程( 函数) 动态链接技术实现动态软硬件任务切换； 软件任务划分完之后，对可重构资源进行有效的管理和合理分配可重构资源； 研究过程级软硬件通信与同步方法，在保证过程语义正确性的基础上，为微 处理器上软件过程与可重构硬件上硬件过程提供并行运行支持。 本研究则主要关注项目中可重构资源的管理和分配的研究，使之同软硬件划 分形成一个完美的搭配。本课题研究受到该项目的支持，本研究课题在这种研究 背景下具有一定的前沿性。 1 2 研究的目标 动态可重构计算作为一种新的计算模式，对动态可重构计算及系统的研究正 成为目前国际上计算机系统结构及应用技术研究中的一个热点，目前还存在较多 的问题需要进一步的探索和研究。本文深入地研究了关于动态可重构片上系统的 任务在线放置和调度的若干算法，并且深入分析了与放置和调度相关的若干因素， 包括硬件逻辑模块的放置( 布局) 、资源碎片以及动态可重构系统的运行模型。在 考虑这些相关因素的基础上，通过分析已有算法的优缺点，分别提出了一种性能 更优的放置算法和调度算法。 1 3 研究的意义 随着集成电路制造工艺的不断发展，芯片的价格正在不断下降，嵌入式系统 中硬件加速器的应用会越来越广泛。在保证足够灵活性的前提下，我们把更多的 任务交给硬件加速器来完成，从而获得系统性能的提升。 而当任务被划分到硬件后，如何对硬件资源进行管理来充分利用资源，如何 完成任务在可重构资源的布局以减小资源碎片从而减少资源的浪费，按怎样的时 间顺序调度硬件任务，使得更多的任务能够得以并行运行，这就要求采用高质量 的任务放置算法和调度算法。 动态可重构片j ：系统的任务在线放置和调度算法研究 总之，通过对动态可重构片上系统的任务在线放置算法和调度算法的研究， 来尽量降低可重构系统的硬件任务拒绝率，尽可能地缩短整体任务的运行时间， 最大化地提高可重构硬件的面积利用率。从而，使得系统的性能得到提高。 1 4 拟解决的关键问题 第一，动态可重构系统中任务放置问题的研究。任务放置算法的优劣严重影 响着动态可重构片上的芯片利用率和计算性能，如何保证减小资源碎片，尽量提 高任务放置的质量，是本论文研究的一个重要问题。 第二，部分可重构片上系统资源碎片问题的研究。可重构片上系统的资源， 类似于计算机中的内存资源，随着任务的放置和调度，系统中的资源碎片可能会 越来越多，这严重地影响着系统的整体性能，如何结合放置算法来减小资源碎片 也是本论文研究的关键问题之一。 第三，动态可重构片上系统中调度问题的研究。动态可重构系统的应用场合 非常复杂，往往结合了实时的任务。本论文研究的是在实时环境下，在保证任务 接收率和芯片利用率的基础上，使调度开销在可接受的范围内。 1 5 本文的组织 本论文共分五章，其组织结构为： 第1 章：绪论。介绍本论文的课题来源、研究的目的、意义、拟解决的关键 问题以及论文组织结构。 第2 章：概述了可重构计算和动态可重构计算的基础知识，分析了国内外对 可重构操作系统的研究现状。 第3 章：动态可重构资源的放置问题。首先描述了放置模型和相关的基本概 念，然后详细分析了国内外在放置算法的相关工作，在此基础上，提出了一种基 于三维邻接面的放置算法，最后详细介绍了仿真试验设计方案、平台和采用的数 据结构，并对仿真试验结果做了深入地分析。 第4 章：动态可重构系统的调度问题。首先描述本文中可重构硬件任务调度 问题的相关模型，并给出了一些关键的概念和定义，然后分析了国内外的研究现 状，在此基础上提出了一种基于l o o k a h e a d e s t 的调度算法并给出了该论文所提算 法的调度实例，最后详细介绍了仿真试验设计方案、平台和采用的数据结构，并 对仿真试验结果做了深入地分析。 第5 章：支持软硬件透明编程模型的o s 4 r s 的可重构资源管理器的实现。首 先设计了一个支持实验室提出的软硬件透明编程模型的原型系统，然后在移植的 l i n u x 操作系统内实现了所设计原型系统的可重构资源管理器，最后用实验室开发 的图形函数库测试了可重构资源管理器，并分析了测试结果。 2 硕上学位论文 第2 章基础原理与相关理论 近年来，随着微电子技术、计算机技术的发展，尤其是大规模高性能的可编 程器件的出现、软硬件设计方法和设计工具上的改进，实时电路重构 ( r e c o n f i g u r a t i o no fc i r c u i t r ) ra tm n t i m e ) 技术逐渐成为国际上计算系统研究中的一 个新热点。它的出现使过去传统意义上硬件和软件的界限变得模糊，让硬件系统 软件化。实时电路重构的本质是利用可编程器件可多次重复配置逻辑状态的特性， 在运行时根据需要动态改变系统的电路结构，从而使系统兼具灵活、简捷、硬件 资源可复用、易于升级等多种优良性能。基于此技术设计的可重构系统 ( r e c o n f i g u r a b l es y s t e m ) 在高速数字滤波器、图像压缩、硬件演化计算、定制计算 ( c u s t o mc o m p u t i n g ) 、嵌入式系统等方面，都有着广泛的应用前景。 2 1 可重构计算基本技术 在可重构计算出现以前，主要使用a s i c 或者通用处理器来完成系统的开发。 a s i c 针对不同系统需求在设计上进行专门优化，因此可以达到非常高的执行效率。 但是a s i c 在完成制造以后不能进行修改，一旦遇到不同的工作环境，就需要对 a s i c 重新设计，往往导致a s i c 的设计成本高，灵活性差。通用处理器则恰恰相反， 一般拥有一套属于自己的指令集。在执行任务之前都是将任务转化为一系列自身 可识别的指令集，然后根据相应的指令来完成整个计算过程。因此通用处理器拥 有很高的灵活性，但执行效率下降。而可重构计算技术结合了a s i c 和通用处理器 两者的优点，既有通用处理器的灵活性，也有a s i c 一样高效的硬件电路，以达到 软件的灵活及硬件的优化。 2 1 1 编程技术 可重构计算系统的可重构处理单元( 或者称为可重构协处理器) 主要有两种 类型，一种是应用最为广泛的现场可编程门阵列( f p g a ) ，本文使用的可重构处 理单元就属于这一类型；另一种是针对特定应用需求设计的可重构处理单元，例 如针对面向图像处理、d s p 变换等领域专门设计的。在本文中只讨论第一种可重 构处理单元为f p g a 的类型。 f p g a 的基本组成成分是可配置的逻辑块c l b ( c o n f i g u r a b l el o g i cb l o c k ) 。通 常每个c l b 由许多个基本逻辑元素b l e ( b l o c k1 0 9 i ce l e m e n t ) 组成。c l b 包括组合 函数模块、触发器和内部连线，组合函数通常用查找表的方式实现，函数的真值 表保存在局部寄存器，通过改写真值表的内容，就可以改变函数关系；而且c l b 的 内部连接关系也是可重构的。对于基于现场可编程门阵列( f p g a ) 的可重构计算来 动态可重构片上系统的任务在线放置和调度算法研究 说，可以这样认为，f p g a 技术的发展推动了可重构计算的发展，同时可重构计算 的进展和需求，也促进了f p g a 技术的进步。 可重构计算的底层技术是f p g a 编程技术。f p g a 的编程技术主要有两种， 一种是反熔丝技术，即通常所说的电可擦写技术，但是由于这种技术的可重构实 时性太差，不适用于现在高性能的可重构计算。 另一种是基于静态存储器( s r a m ) 可编程原理的f p g a 编程技术，其基本原 理是：f p g a 中各部件之间由类似s r a m 功能的路由模块相连接( 由于这里的 s r a m 并不具备一般s r a m 中的随机存取功能，所以称之为类似s r a m ) 。部件 间的连接关系，通过对s r a m 编程便可实现应用的需求，这样f p g a 硬件就如同 一般s r a m 一样可以重复编程了瞪1 。 需要特别指出的是f p g a 的可编程实现运用了静态存储器的基本原理，但实 质与通常意义上的可编程是完全不一样的。比如说，考虑一个信号处理系统，一 般对这样的系统来说，大量的不同复杂算法如z 变换、傅立叶变换还有各种滤波 器等，但是对每一种算法可能运行不同的字长。在使用通用处理器来求解这些问 题，设计上一般会采用折衷方案，在考虑能满足功能需求的时候还必须顾及到资 源的使用情况。如果采用基于f p g a 的可重构计算，则可根据字长与算法的需要 实时地改变硬件结构，在满足性能需要的同事节约宝贵的计算资源，并且其性能 接近或者完全达到a s i c 的处理效率。 如图2 1 所示，给出了基于s r a m 的f p g a 中最小单元的电路原理图。图2 2 给出的是它的编程原理电路图，这里的f p g a 单元只是一个简单的反相器1 。编 程的原理也比较简单，当编程端的输入信号为真，通过路由将左右两边资源直接 相连，否则就不相连，从而实现了电路结构的改变。 鬣| 马丁 图2 1 基于s r a m 的f p g a 可编程位 4 硕上学位论文 路由路由 p 编程段 图2 2 可编程的路由连接1 2 1 2 逻辑模块 f p g a s 是一个阵列，阵列中有多个构成阵列的单元，称之为逻辑模块。典型 的f p g a s 基本模块如图2 3 所示，由一个d 触发器( d f f ) ，一个快速的进位逻辑 ( c a r r ) rl o g i c ) ，一个四变量函数器( 4 一l u t ) 等基本电路构成，其中四变量函数器用于 组合逻辑的实现，d 触发器则可用于构造如寄存器、存储器、流水线、有限自动 机等时序逻辑的实现，进位逻辑则主要用于构造算术运算逻辑h 1 。 图2 3f p g a 基本逻辑模块 2 1 3 路由资源 当f p g a 中的基本逻辑模块确定后，模块间的互连技术至关重要，因为它直 接关系可重构系统的具体实现。这种用于f p g a s 中模块间互连的电路资源，称之 为路由资源嘲。对路由资源的研究，如同对逻辑模块的研究一样，也是f p g a s 内 部结构研究的主要问题之一，人们在这方面研究投入的代价不比逻辑模块少。 f p g a 中有丰富的路由资源，基本逻辑块嵌入在通用路由结构中，如图2 4 所 示。基本逻辑块的输入输出和连接块相联，可编程的交换盒控制基本逻辑块之间 的连接关系，这样基本逻辑块在路由的控制下便能以任意的方式互联，实现不同 动态可重构片i ：系统的任务在线放置和调度算法研究 的计算功能。 图2 4f p g a 的路由结构6 1 2 2 可重构计算系统的体系结构 虽然不同的可重构计算系统的结构会有很大的区别，但其组成成分基本上是 相同的，即通用处理器、可重构处理单元、存储器、输入输出设备。图2 5 是一个 典型的可重构计算系统的体系结构图。 困巨巫司臣固 i 可重构处理单元 i 本地存储器 图2 5 典型的可重构计算系统的体系结构图1 其中通用处理器用于控制和处理通用的计算任务，可重构处理单元用于处理 专用领域的计算任务，在某些系统中处理器与可重构处理单元集成在同一块芯片 上，而在另外一些系统中，处理器与可重构处理单元分别位于不同的芯片上。 6 f 位论立 2 3 动态可重构计算 动态重构现在是当前可重构计算的研究热点之一，它又被成为运行时可重构 ( r u n t i m er e c o n 丘e u r a b l e ) ，是指在运行时进行重构，即程序执行时为重构硬件注 入或换出不同的配置信息，实时地改变硬件的结构以适应不同的硬件算法，从 而具有更高的灵活性、芯片利用率和系统运行效率使得整个系统的性能得到提 升”3 。 根据不同配置存储结构类型，动态重构可以进一步分为单上下文可重构 ( s i n g l ec o n t e x tr e c o n n g w a b l e ) 、多上下文可重构( m u l t i c o n t e x tr e c o n n g u r a b l e ) 、 部分可重构( p a n l a l l yr e c o n n g u r a b l e ) “1 ，如下图26 所示。 i i i 、骂叠 l l y g “m l 。 一。i ；i 二：7 一l 珲。 7 、! 望曼| i i要嘎 f i j 亏一h - - - 一t ，_ “ 图26 动态可重构方式 在单上下文可重构体系架构中，配置信息以串行流( s e r i a ls l r e a m ) 的形式存 储在配置存储器中。当发生上下文切换时，即改变系统的配置时，需要重新装入 新的配置信息，才能完成对可重构部件的配置，因此配置信息在串行流中的分割 会对重构延迟产生较大影响。 在多上下文可重构体系结构中，每个配置位对应着配置存储器中的多个存储 位但是任一时刻只有个存储位处于激活状态。当需要上下文切换时，只需要 改变配置位和存储位的对应关系即可实现系统的快速重构。多上下文重构相当于 多个单上下文重构的堆叠变现。 部分可重构体系结构针对配置只需要使用全部可重构硬件的一部分，或者只 有一部分配置需要改变的情况。部分可重构硬件可以在部分硬件运行的同时改 变另外部分硬件的配置，这是通过给每个可配置位编址访问来实现的。部分可 重构硬件体系结构可以进一步减少重构时间，缩短重构延迟。 动态重构是可重构计算豹发展方向，虽然现在可重构计算广泛的实际应用仍 动态可重构片上系统的任务1 乍线放置和调度算法研究 停留在静态重构的层次上，动态可重构暂时还处于实验研究中，但在不久的将来， 动态重构很可能会成为可重构计算应用的主流技术。目前对动态可重构的研究主 要集中在如何减少器件重构开销、预配置技术、更加灵活的配置布局和优化资源 调度等方面。本文研究的动态可重构片上系统的任务在线放置和调度算法考虑的 就是资源的配置布局和优化资源调度方面。 2 4 可重构计算操作系统 传统的实时操作系统的缺陷是没有利用硬件来实现操作系统的任何功能。文 献n 们提出的实时操作系统组合了软件的重使用和硬件的性能，给硬件以内核级的 支持。操作系统上的应用分为硬件任务和软硬任务，操作系统用统一接口对它们 进行了抽象。任务粒度的大小本身是一个重要问题，该论文提供了可重构资源管 理方法，特别是f p g a 的划分算法，得出了如果在初级阶段软硬件划分合理，任务 粒度和片段宽度恰当，任务重新划分将变得很少的结论。 文献n u 针对传统设计的缺陷和对统一多任务模型的改进，实现了对软硬件任 务统一管理的实时操作系统( r t o s ) s h u m u c o s ，该操作系统能够跟踪和管理 可重构配置资源的使用，通过硬件任务预配置技术，提高了资源利用率和任务并 行性。定义了资源控制块来管理可重构资源的使用，每一个资源控制块结构中有 指向下一个资源控制块的指针和指向该可配置资源的第一个任务的指针。作者给 出了软硬件任务创建的算法，硬件任务分为三层实现，每个硬件任务拥有任务接 口控制块。采用r h e a l s t o n eb e n c h m a r k 测试程序集来测试该操作系统的性能，通过 测试，该操作系统能够在提升系统性能的同时，有效缩减从软件实现到硬件实现 的迁移时间。 w a l d e r 与s t e i g e r n 2 1 等对实时可重构计算操作系统进行了研究，并着重关注了 其中的任务调度问题。他们提出为可重构平台提供操作系统，这个操作系统提供 一个最小的编程模型和运行时系统。编程模型定义了执行对象和它们的内部交互 活动，并提供了一系列定义好的系统服务给开发者。运行时系统执行在线任务并 负责可重构资源的管理。操作系统被分为两部分：第一部分是软件代码，软件代 码可以运行在外部主机上，它负责生成配置文件及进行任务调度与布局。任务的 布局由资源管理器来实现。第二部分是一个硬件管理器，该管理器从一开始就被 配置到可重构器件当中，在运行的过程中不会改变。它主要负责硬件任务的配置， 并维护硬件的运行状态，为硬件任务提供基本的操作系统服务，例如进程通信、 内存管理及访问外部i o 端口等。针对实时系统的特殊要求，他们提出了两种任务 调度算法：h o r i z o n 调度算法与s t u 艏n g 调度算法，均取得了较好的实验效果。 8 硕十学位论文 2 5 小结 本章从可重构基本技术出发，然后简要介绍了可重构的体系结构和动态可重 构计算技术，最后分析了国内外在可重构操作系统方面的研究现状。 9 动态可重构片i ：系统的任务在线放置和调度算法研究 第3 章可重构资源的放置问题 管理部分可重构芯片上的空闲资源和在线分配可重构资源都是动态可重构片 上系统的核心问题，本章主要研究上述问题的第一个问题，将之称为可重构系统 的放置问题。已有的放置算法开销很大，或者放置算法的质量比较低，无法在实 际的可重构系统中采用。作为动态可重构系统的核心问题之一，放置算法必须在 能够接收的时间开销内，尽量增加可重构资源的利用率。本章提出了一种可重构 资源的放置算法一一基于三维邻接面的放置算法。 已有的基于二维邻接边的放置算法以任务放置的邻接边数目最大化为目标进 行放置，在一定程度上使得硬件任务放置更为紧凑，减少资源碎片，提高可重构 资源的利用率，但是它没有考虑任务调度的时间维，与基于二维邻接边放置算法 相比，基于邻接面的放置算法考虑在三维空间中，以任务在三维空间的邻接面最 大化为放置目标，使得任务更加整齐、紧密的放置，从而更进一步减少资源碎片， 提高资源的利用率。 3 1 概述 在基于f p g a 的可重构系统中，一个大的应用任务能够被综合和划分成一些 更小的任务集合。在一个典型的可重构操作系统中n 3 1 4 1 ，包含许多互相独立的任 务集合的多个应用任务能够并发地在可重构资源上执行。在这些小的任务集合被 执行之前，它们需要放置在f p g a 的空闲资源上，而当这些任务执行完成之后， 被这些任务占用的可重构资源需要被重构，以至于接下来的任务集合能够继续执 行。 在研究放置算法时，通常将划分后的任务抽象成小的逻辑模块，而将整个可 重构资源抽象成一个大的逻辑模块，这些小的逻辑模块可以以并行方式放置到大 的逻辑模块执行。放置问题是指这些较小的逻辑模块如何进行布局，放置不仅关 系到芯片资源的合理、有效利用，而且是研究可重构芯片上硬件模块重定位、调 度和可重构资源碎片整理的基础，它一直是可重构计算系统的瓶颈问题，因此成 为国际上的研究热点。 3 2 模型的描述和基本概念 可重构器件内部由一系列可重构逻辑单元r l u s ( r e c o n n g u r a b l el o g i cu n i t s ) 组 成，相互之间相连并可配置。一般在f p g a 由成千上万个r l u s 组成，每一个r l u 由组合和时序逻辑单元组成，是分配给任务的资源的基本单位。硬件任务调度和 放置问题的难度严重依赖于可重构器件的资源模型。一般用矩形区域对可重构芯 l o 硕 学位论文 片表面计算资源进行抽象建模，根据可重构资源的特性和运行时硬件所占资源的 约束方式，可将任务放置在可重构资源上的布局方式抽象成两种资源模型：1 ) 一 维资源模型，如图3 1 ( a ) 。硬件任务可被布局在水平方向上的任何位置，但在竖直 方向上，每列不能同时存在一个以上的硬件任务。该模型降低了任务放置问题的复 杂度，但由于碎片过多而难于管理。2 ) 二维资源模型，如图3 1 ( b ) 。硬件任务的 布局在水平和竖直方向上都没有限制，只要其所占区域不相重叠。由于二维资源模 型允许将矩形任务分配到可重构器件的任何位置，其优点是由于放置灵活从而有 利于提高器件面积的利用率，困难在于开发在线算法时，为一个任务找到最优、 甚至可行的调度都是非常困难的。目前x i l i n x 公司已经提供二维可重构器件支持。 二维模型可明显减少资源浪费，能够提高资源利用率，因此，当前对可重构系统放 置问题的研究大多基于二维放置方式。本文的研究工作是基于二维资源模型展开 的。 l 3 2 4 操作系统区域 a ) 一维资源模型b ) 二维资源模型 图3 1 可重构资源模型n 1 1 上述抽象模型在实际使用中存在很多限制。虽然目前的e d a 设计工具可以将 任务约束在一个矩形区域内，但可重构器件的异构性、任务通信时间及部分可重 构性质都将给我们的研究结果投入实用带来诸多限制。实际上假设可重构器件表 面的资源都是均匀的与当前主要的f p g a 产品特点不相符，它们一般都包含很多 专用处理模块。目前大多数的研究均假设有足够的资源支撑通信需求。 在二维资源模型下描述带期限的硬件任务调度问题时，f p g a 器件表面用坐标 体系来表示矩形模型r c u ，列与行都是从左至右、从下至上增加。相关的定义如 下： 部分可重构资源：指允许重新配置可重构资源的一部分，而其它部分仍然可 以继续执行。部分可重构资源由h 行w 列可重构逻辑单元( r l u s ) 组成，h 和 w 分别是单列和单行可重构逻辑单元的个数。部分可重构资源由h w 的二维矩 阵描述，矩阵的每一个元素与可重构资源的单个r l u 相对应。 可配置任务t i ：通常是指可以被配置到可重配置器件中的数字功能模块。运 行时可配置任务t i 的属性包含面积和时间两个方面，可以将其看作五元组t i = ，其中： w i 表示t i 在水平方向所占用的r l u 数目，即任务的宽度。 h i 表示t i 在垂直方向所占用的r l u 数目，即任务的高度。 a i 表示可配置任务的到达时间。 e i 表示可配置任务的执行时间，可以通过计算可配置任务的时钟周期数确定 任务的执行时间。 d i 表示可配置任务的截止期( d e a d l i n e ) 。实时任务的必须满足以下的时间约 束关系：d i 2 a i + e i 。 最迟开始执行时间：任务为了能够满足其截止时间，而需要被加载到可重构 资源上的最迟时间。由上可知，最迟开始时间s il a t e s t = d i e i 。 任务的邻接边：指对于新到达的硬件任务，其与已放置的任务相邻的可重构 单元边的数目。 任务的邻接面：指将任务的调度时间抽象成时间抽后，在三维虚拟空间中， 到达任务与已放置任务相互接触的区域。 碎片：指在硬件任务边界外无法利用的资源。 放置算法：指为新到达的硬件任务选取放置位置时，需要根据评价标准，从 多个候选位置中选择“最优的。代价函数即为选择时所利用的评价标准。 任务的拒绝率：被拒绝硬件任务的总和与所有硬件任务数的比值。 可重构资源利用率：指一段时间内，被接受任务的面积之和与整个可重构资 源面积的比值。 3 3 相关研究工作 当前研究任务的放置的算法可以分为两类：离线的和在线的两种算法。离线 的放置算法对预先给定的任务集合，采用最优和次优的放置方案，使任务放置得 更加紧密，更好地利用可重构资源。相反，对于在线的放置算法，由于不能预先 知道执行的任务集合，所以不能够对其进行整体优化。本论文主要研究的是任务 的在线放置方法。对于在线的放置算法，根据对空闲资源管理方式所采用的数据 结构不同，可分为基于矩形的放置算法和基于顶点链表的放置算法。 3 3 1 基于矩形的放置算法 在在线放置算法的研究中，b a z a r g a n 最先使用集装箱的方法来处理任务分配 问题，并提出了两种基于矩形的任务管理算法n 引。第一种算法利用启发性机制来 减小更新矩形的数目，当一个空闲的矩形被用来放置任务时，剩下的空闲区域被 划分成两个非重叠的矩形用来放置到达的任务，如图3 2 所示。b a z a r g a n 虽然提供 了一些划分标准，但是由于空闲区域被划分成许多非重叠的矩形。因而无论采用 哪种划分标准，仍然可能存在即使有足够的空闲区域，算法也找不到可行的放置 1 2 硕士学位论文 位置的情况。第二种算法利用跟踪最大空闲区域( m e r ) ( 如图3 3 ) 来放置到达 的任务，能够确保如果存在一个可行的放置，那么算法就能够找到它并用来放置 任务，从而降低任务的拒绝率，但是该算法更新相应的数据结构的时间复杂度非 常高。 a ) f r e er e c t 锄g l eb ) v e r t i c a ls p l i tc ) h o r i z o n t a ls p l i t 图3 2b a z a 唱a n 的划分决定 图3 3 最大空闲矩形放置( m e r ) w a l d e r 对b a z a r g a n 划分自由矩形的方法进行了改进n 们n7 1 ，其基本思想是延迟 基本的水平垂直划分决定来管理重叠的矩形，提出了o t f ( o n t h e n y ) 划分方 法，该算法用h a s h 矩阵来存储指向带有不同自由矩形大小链表的指针，维护一个 空闲区域