（通信与信息系统专业论文）可重构系统中任务实时调度和实时布局算法的研究.pdf

摘要 摘要 可重构计算是一种兼具通用处理器灵活性和专用集成电路高效性的计算体系 结构。为了能够充分发挥可重构系统的高性能和可编程能力，需要将可重构资源 和硬件任务的管理纳入到操作系统的范畴。因此，可重构硬件操作系统技术成为 一个新的研究热点。 可重构硬件操作系统抽象的编程模型简化了编程接口和共享资源的管理，任 务的实时调度和实时布局是资源管理中的关键部分；可重构器件资源规模的增长 也使多用户并发操作成为可能。据此，本文提出了一种多用户多任务的可重构计 算平台模型，并在此基础上对任务的实时调度和实时布局展开深入的研究，主要 包括以下内容。 首先，分析现有的可重构计算平台，提出了多用户多任务可重构计算系统模 型，并研究了针对此平台任务模型的一般形式。 其次，研究了此系统模型下的任务调度算法，用户任务集的调度采用了改进 的先来先服务的调度算法，而用户任务集中内部多任务的调度则提出了一种新的 时域划分技术一关键部分分割( c s c ) 算法。 再次，结合任务的调度策略，在处理数据无关的用户任务集布局时提出了基 于资源利用率为准则的最大剩余空闲矩阵 眦r ) 布局算法，而在处理具有数据相 关性的用户内部多任务时提出了基于通信成本为准则的最小路由成本( m r c ) 布局 算法。 最后从资源利用率，任务拒绝率，资源碎片率等多个角度对多用户多任务的 实时调度和实时布局算法进行了详细的分析和评估。 关键词：可重构硬件操作系统，关键部分分割，最大剩余空闲矩阵，最小路由成 本 a b s t r a c r a b s 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 m sh a v e b e e nd e v e l o p e d o nt h eb a s i so f m i c r o p r o c e s s o r a n da s i c ，w h i c hc a na c h i e v em u c hb e t t e r p e r f o r m a n c e t h a n m i c r o p r o c e s s o ra n dm a i n t a i n sah i g h e r1 e v e lo ff l e x i b i l i t yt h a na s i c i ti sn e c e s s a r yt o m a n a g et h er e c o n f i g u r a b l er e s o u r c e sa n dh a r d w a r et a s k sf o ro p e r a t i n gs y s t e m ，w h i c h c a nb r i n gh i g h e rp e r f o r m a n c ea n dp r o g r a m m a b l ea b i l i t y t h e r e f o r e ，r e c o n f i g u r a b l e h a r d w a r eo 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 ec o m p u t i n gh a sb e e nan o v e lh o tt o p i ci n l a s tf e wy e a r s r e c o n f i g u r a b l eh a r d w a r eo p e r a t i n gs y s t e r n s f i l lt w ok e yr o l e si nc o m p u t i n g ： s i m p l i f y i n gt h ep r o g r a m m i n gi n t e r f a c et h r o u g ha na b s t r a c t e dp r o g r a m m i n gm o d e la n d m a n a g i n gs h a r e dr e s o u r c e s t h eo n l i n es c h e d u l i n ga n do n l i n ep l a c e m e n ta st h ec r i t i c a l p a r to ft h er e c o n f i g u r a b l eh a r d w a r eo p e r a t i o ns y s t e m s t h en u m b e ro ft h er e s o u r c eo n r e c o n f i g u r a b l ed e v i c ei n c r e a s i n gd r a m a t i c a l l ym a k e si tp o s s i b l et oo p e r a t ec o n c u r r e n ti n am u l t i u s e rm a n n e r b e c a u s eo ft h i s t h e t h e s i sp r e s e n t sam u l t i - u s e rm u l t i t a s k i n g r e c o n f i g u r a b l ec o m p u t i n gm o d e l ，a n di n d e p t hs t u d yo nt h et a s ko n l i n es c h e d u l i n ga n d o n l i n ep l a c e m e n ta l g o r i t h mo nt h eb a s i so ft h i sm o d e l t l l i st h e s i sc o n s i s t so ft h e f o l l o w i n gp a r t s t h ef i r s tp a r ta n a l y s i so fe x i s t i n gr e c o n f i g u r a b l ec o m p u t i n gp l a t f o r m ，p r o p o s e da m u l t i u s e rm u l t i - t a s k i n gr 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 mm o d e l ，a n da n a l y z e st h e g e n e r a lf o r mo f at a s km o d e l t h es e c o n dp a r td i s c u s s e st h eo n l i n es c h e d u l i n ga l g o r i t h m u s e rt a s ks e t ( u t s ) i s s c h e d u l e db ya ni m p r o v e df i r s tc o m ef i r s ts e r v e ds c h e d u l e ( f c f s ) a l g o r i t h m t h e m u l t i t a s k sw i t h i nt h eu t sa r es c h e d u l e db yan e wt e m p o r a lp a r t i t i o nt e c h n i q u e - - - c r i t i c a ls e g m e n tc u t ( c s c ) a l g o r i t h m t h et h i r dp a r ts h o w st h ep l a c e m e n ta l g o r i t h m t h ed a t a - i n d e p e n d e n tu t su s e s r e s o u r c eu t i l i z a t i o na st h ep l a c e m e n tc r i t e r i o n ，s oan e wp l a c e m e n ta l g o r i t h m - - m a x i m a l r e s i d u a le m p t yr e c t a n g l e ( m r e r ) i sa p p l i e dt os o l v et h eu t s p l a c e m e n t r l l e nd e a l i n g w i t ht h ed a t a - d e p e n d e n tu t si n t e r n a lm u l t i t a s k s ，u s i n gc o m m u n i c a t i o n - c o s ta st h e c r i t e r i o n s oan e wp l a c e m e n ta l g o r i t b n r 1 n i n i m a lr o u t i n gc o s t ( m r c ) i sp r e s e n t e dt o r e s o l v et h eu t si n t e r n a lm u l t i t a s kp l a c e m e n tp r o b l e m t h ef i n a lp a r td e t a i l e da n a l y s e sa n de v a l u a t i o n so ft h es t r a t e g i e sf r o mt h er e s o u r c e u t i l i z a t i o n ，t a s kr e j e c t i o nr a t e ，f r a g m e n t a t i o no fr h da n dm a n yo t h e rp o i n t so f v i e w k e y w o r d s ：r e c o n f i g u r a b l eh a r d w a r eo p e r a t i o ns y s t e m ，c r i t i c a ls e g m e n tc u t ，m a x i m a l r e s i d u a le m p t yr e c t a n g l e ，m i n i m a lr o u t i n gc o s t 图目录 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图3 1 图3 2 图3 3 图3 - 4 图3 5 图3 - 6 图3 7 图3 8 图3 - 9 图3 1 0 图3 - 1 1 图3 1 2 图4 1 图4 2 图4 - 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 1 图5 1 图目录 x i l i n xx c 6 2 0 0 系列f p g a 配置存储器9 a t m e la t 6 0 0 0 系列f p g a 配置内存9 x p p 系统构架1 1 多用户多任务可重构计算系统1 2 不同用户设计空分复用整个r h d 1 4 每个用户时分复用为其分配的资源1 4 c p u 和可重构硬件交互图15 ( a ) 静态划分；( b ) 非空域划分；( c ) 自由空域划分一时域共享1 7 ( d ) 等资源隙划分；( e ) 一维划分；( f ) 二维划分18 数据流图( d f g ) 举例2 0 u t s 模型2 2 a s a p 算法调度结果2 4 a l a p 调度算法结果2 5 a s a p 级别与a i 。a p 级别分配算法2 6 d f g 关键部分示例2 6 u t s 调度算法流程2 8 c s c 时域划分算法举例3 2 ( a ) 初步划分的结果；( b ) 划分配置图3 3 划分的模块资源数目超过资源总数的情况3 4 ( a ) d f g n e w ；( b ) 对d f g - n e w 再次初步划分：z 3 5 ( a ) 最终划分结果；( b ) 最终配置图3 6 ( a ) 最终模块划分图；( b ) 对应的最终配置图3 6 模块v 的i p r 3 9 相对器件的i p r 和相对已放置任务的i p r 4 0 布局方案的示例4 1 行扫描编码4 l 列扫描编码4 2 行有效线段4 3 列扫描有效线段4 4 o p p 落在了i p r 区域4 7 o p p 对应的四个s u b o p p 4 8 从s u b o p p 中找出最佳布局点4 8 m r c 布局算法4 9 t o r s c h e 操作界面5 l 图目录 图5 2采用布局算法后跳过的单元数5 3 图5 3最坏情况下布局5 4 图5 4资源利用率与c p u 运行时间之间的关系5 4 图5 5f f , b f , m r e r 任务拒绝率的比较5 6 图5 - 6m r c ，f f ，b f 三种布局策略的路由代价5 7 图5 7u t s 调度算法举例5 8 图5 8较差的划分5 9 图5 - 9较好的划分5 9 v u 表目录 表目录 表5 1k a m e r 与m r e r 空间复杂度和时间复杂度比较5 5 表5 2c s c 和l s 时域划分算法划分质量的比较6 0 缩略词表 英文缩写 r h o s s o c s o p c i r c f p g a c p u s l u u t s f c f s d f g n l e r 口r p p r k 乙心 a s a p m 匝r 1 d 2 d f f b f 皿c c s c p o p p d a g l s 英文全称 缩略词表 r e e o n f i g u r a b l eh a r d w a r eo p e r a t i o ns y s t e m s y s t e mo nc h i p s y s t e mo np r o g r a m m a b l ec h i p r e c o n f i g u r a b l eh a r d w a r ed e v i c e r e c o n f i g u r a b l ec o m p u t i n g f i e l dp r o g r a m m a b l eg a t ea r r a y c e n t r a lp r o c e s s i n gu 1 1 i t s w a p p a b l el o g i cu n i t u s e rt a s ks e t f i r s tc o m ef i r s ts e r v e d d a t af l o wg r a p h m a x i m a lr e s i d u a le m p t yr e c t a n g l e i m p o s s i b l ep l a c e m e n tr e g i o n p o s s i b l ep l a c e m e n tr e g i o n a sl a t ea sp o s s i b l e a ss o o na sp o s s i b l e m a x i m a le m p t yr e c t a n g l e o n ed i m e n s i o n t w od i m e n s i o n f i r s t f i t b e s t - f i t m i n i m a lr o u t i n gc o s t c r i t i c a ls e g m e n tc u t i n t e g e rl i n e a rp r o g r a m m i n g o p t i m a lp l a c e m e n tp o i n t d i r e c t e da c y c l i cg r a p h l i s ts c h e d u l i n g i x 中文释义 可重构硬件操作系统 片上系统 片上可编程系统 可重构硬件 可重构计算 现场可编程门阵列 中央处理单元 交换逻辑单元 用户任务集 先来先服务 数据流图 最大剩余空闲矩阵 不可能布局区域 可能布局区域 尽可能晚 尽可能早 最大空闲矩阵 一维 二维 最先适合 最佳适合 最小路由成本 关键部分分割 整数线性规划 最佳布局点 有向无环图 表单调度 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成黔也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 鲞丝经日期：2 , o 口年多月；日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅b 本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：渣丝堕 导师签名：2 独 日期：刃矽年月弓e t 第一章绪论 第一章绪论弟一早三百。下匕 本章将简要介绍可重构硬件操作系统和资源管理策略的发展现状，对本课题 的研究意义进行分析，并最终确定本论文的研究内容。 1 1 课题研究背景 近年来，可重构器件从最初的粘和逻辑发展到今天的又一主要的计算平台， 其现场可编程重构的特点使得其设计应用灵活多便，能够实现以往只有通过a s i c 才能完成的计算密集型任务。对于实现具有多功能特点系统，传统的设计方法是 将不同标准的相应电路集成起来。这样一来，整个电路将变得相当复杂，而在实 际使用中，在某个时间段，多种功能集成的电路中往往只有一小部分在工作，而 系统的其它资源将处于闲置状态。这将导致巨大的功耗和硅片面积的浪费，并且 在如无线通信领域，视频编解码这些需要兼容多种标准的领域中不能很好的适应。 因此在实际应用中，就亟需要一个能够根据外界环境和系统状态变化的自适应构 架。 由于动态可重构技术的动态重构特性，能够分时复用有限的硬件资源，这个 特性可以使器件能够适应各种不同的应用。对于上述问题，动态可重构技术将不 同标准的电路分别设计，并产生相应的配置数据，根据系统的需要来动态的重构 相应的实际电路。这样一来，多种标准的处理电路可以在同一套硬件平台上运行， 而所需的硬件资源也只需和其中资源消耗最多的一套标准相同即可，使芯片规模 大幅度降低，功耗也大大减少。 但随着可重构计算的深入研究以及可重构器件应用范围的不断扩大，研究人 员发现在设计时往往忽略了器件的内在可重构特性以及任务潜在的并行性，这样 不仅增大了系统设计难度，也降低了性能。因此，最近几年，面向可重构计算的 操作系统，即可重构硬件操作系统r h o s 1 技术成为一个新的研究热点。 r h o s 在设计阶段将硬件任务( h a r d w a r et a s k ) 根据其功能抽象成为一系列与 器件无关的对象，隐藏了底层的操作细节，能够给开发者提供便利；可以为应用 程序提供运行时支持，实时解决了资源冲突，保证了各个应用对象之间的连通性 问题，充分发挥了r c 的高性能和可编程能力。其主要能够提供以下便利： 1 电子科技大学硕士学位论文 1 ) 改善设计效率：对各种对象和任务进行资源抽象( r e s o u r c ea b s t r a c t i o n ) ，简 化了可靠性电路或代码的复用，这样能够缩短开发周期和t i m e - t o - m a r k e t 的时间。 2 ) 易于移植：对于应用软件，操作系统屏蔽了硬件的细节和差异，简化了其 在各个不同的硬件平台上的移植。这使得开发者不必担心硬件变化导致程 序的大量修改，专注于性能指标的设计。 3 ) 简化了系统重划分：在运行的时候可以通过对硬件的重构以及重新划分系 统资源，以达到新建或者终止任务的目的，也可以把原本在c p u 上运行 的任务迁移到f p g a 上运行，以提高运行速度或者达到负载均衡。 4 ) 较高的运行性能：操作系统负责资源和任务管理，以最大限度提高系统的 并行性和资源的利用率。特别是对动态和部分可重构系统，选择合适的可 重构资源粒度和任务大小，可以极大提高系统的性能。 r i - i o s 又不同于传统的操作系统，它需要管理主处理器和可重构器件两种资源， 要处理软件任务和可重构系统中特有的硬件任务，即电路逻辑 2 1 。如何管理系统中 的硬件资源，任务的划分，调度，布局，任务的装载卸载，任务间的同步和通信， 都是r h o s 中的关键部分。本文主要在任务的调度和布局两个方面进行深入的研 究。 1 2 研究现状 r h o s 是一个新的研究方向，随着r c 研究的深入，r h o s 的研究取得了一定 进展，其中关键算法一实时调度和实时布局的也取得了一些成果。 1 2 1 可重构操作系统的研究现状 目前国际上并没有一种统一的可重构硬件操作系统标准，只有某些研究机构 提出了一些操作系统原型，下面是对当前研究成果的总结： - 早期关于可重构硬件操作系统在文献【3 坤实现了针对x p u t e r t a i 约o s 。这个o s 是对传统意义操作系统的一种扩展，其主要功能是用来决定设计的那些部分在可 重构硬件上执行，那些部分在c p u 上执行。这个操作系统支持多用户，但每一个 用户的操作是顺序执行的，而不是并发的，所以并不是真正意义的多用户、多任 2 第一章绪论 务操作系统。 g o r d o nb r e b n e r 在文斛5 】中提出了管理v i r t u a lh a r d w a r e ( 虚拟硬件资源) 的概念， 并用x i l i n xx c 6 2 0 0f p g a 实现了此操作系统原型。文中分析了x i l i n xx c 6 2 0 0 f p g a 的特点，此种类型的f p g a 支持对基本单元( c e l l ) 快速并有选择的配置，基 本单元阵列上的可寻址寄存器能够通过配置，使其与系统的其他模块进行交互。正 是上述两个特点，操作系统可以把f p g a 在物理上当成一个内存器件，而在逻辑 上可以对其进行存储映像的处理。最终，通过基于x c 6 2 0 0 的实验证明了两种模型 的可行性，但此系统要求设计规模固定，限制了设计的灵活性。 b 眦n s 【6 】通过分析三种应用动态可重构的实例，提出了一种可扩展的实时系统 用来管理f p g a 的动态配置，系统为应用程序提供了高级接口，用来完成复杂的 重配置和电路处理任务。系统分为虚拟硬件管理器，电路变换器( 可以将任务进 行任意角度旋转，以便更有效的利用资源) ，配置管理器，设备驱动。但是文中并 没有考虑对f p g a 资源的管理以及硬件任务的划分。 s h i 抛【7 】提出了一种自动把实时可重构设计映射到可重构系统的方法。该算法 基于匹配加权二分图，主要是针对设计框架中的分解这一步。在处理这一步时， 对设计进行划分，并将其映射到可重构器件的重构区域中，每个部分在合适的时 间开始执行。算法缩小了配置功耗，但是文章没有给出如何在f p g a 上寻找适合 硬件任务运行的资源。 i m e c ( i n t e ru n i v e r s i t ym i e r o e l e c t r o n i cc e n t e r ) 的可重构计算研究小组在【8 】中认 为o s 4 r s ( o 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 es y s t e m s ) 所包含的主要功能有任务 的创建销毁、异构任务的动态迁移、任务之间的相互通信等。他们也指出，支持 软、硬件任务调试以及允许对操作系统模块和用户任务的跟踪监控也是r h o s 的 一个重要特征。 目前国内对可重构硬件操作系统的研究非常少，复旦大学计算机与信息技术 系以u c o s i i 实时操作系统为原型9 】，提出了一种统一的多任务，多线程实时可重 构硬件操作系统模型，称为s h u m - u c o s ( s o f i ：w a r e t a s k sh a r d w a r e t a s k su n i f o r m m a n a g e m e n tu c o s ) 。此操作系统在处理硬件任务和软件任务时用统一的平台，大 大缩短了迁移时间。它能够跟踪和管理可重配置资源的使用，通过硬件任务预配置 技术，提高了资源利用率和任务并行性。然而此系统仅仅是u c o s i i 实时操作系统 的延伸，并且只支持全局可重构系统，有一定的局限性。 3 电子科技大学硕士学位论文 1 2 2r h o s 中关键算法的研究现状 任务的实时调度和实时布局是r h o s 中的关键算法，而关于这方面的研究与 硬件平台的发展密切相关。不同的可重构计算系统硬件平台，按照其支持的运行 时重构特性可以分为4 类：全局配置可重构计算系统，1 d 可重构计算系统，2 d 可重构计算系统，多维可重构计算系统。近年来研究者大量关注2 d 可重构计算系 统，下面是一些关于2 d 调度和布局算法的研究成果。 1 2 2 12 d 调度算法的研究现状 由于当前的f p g a 不支持细粒度的2 d 布局，研究人员不得做出一些假设，并 在此基础上来设计2 d 的调度算法。砧髓a d i l l i a 【l o 】提出了两种集群方法把将要放置 在全局可重构器件上执行的实时任务分为两类：第一种集群将有相同执行时间的 任务归为一类；第二种集群是通过一个衡量函数把任务间通信较少的任务集聚。 集群的主要思想是将具有相似特征的任务放置在一起执行。在布局时采用了f f 算 法，最终结果显示在通信代价方面有大幅度的降低。算法主要针对的是具有最后 期限约束的实时任务，所以算法在构建集群时必须保证其中的每个任务都满足任 务的最终期限( d e a d l i n e ) 。 t a b e ：r 1 1 】基于顶点列表数据结构提出了几种启发式算法来为任务选择合适的 布局位置【1 2 1 。文中的算法也是针对实时任务，并用任务的拒绝率来衡量算法的性 能。最后将经典的f f 算法和b o s o m 1 d t 算法比较，证明了顶点列表数据结构会提 高布局算法的性能。 h a n d a 和v 锄u r i 【1 3 】提出了种任务队列管理的数据结构用来调度i n - o r d e r 任 务和o u t - o f - o m c r 任务。i n - o r d e r 任务表示放置在优先权输入队列中的各个任务之间 是数据相关的，所以任务需要被按次序执行。而在o u t - o f - o r d e r 任务调度处理中， 由于这些任务之间是相互独立的，因此能够按照任何顺序执行。 b a z a r g a n 1 4 】提出了处理混合软硬件任务的算法。文中假设当任务没有找到空闲 区域来放置时，就将其放置在软件中执行。在调度算法中结合了离线布局，离线 布局算法用来估算可用的可重构功能单元的面积，调度器则可以利用此信息来调 度任务。在布局是也是应用了f f 和b f 两种基本算法。 w a l d e r 和p l a t z n e r 1 5 】提出了一种新的运算应用于在线调度脚本变换。脚本 变换用来改变任务的形状，其过程比任务迁移更加复杂。脚本变换前提是任务是 粗粒度且非矩形的，更符合实际情况。 4 第一章绪论 s t e i g e l l 6 】设计了两种布局器用来处理具有任意到达时间的任务。文中的算法是 对管理非重叠空闲矩阵思想的一种延伸。在算法中，将所有的空闲矩阵表示成为 树形数据结构中的节点来管理空闲区域。对空闲矩阵的操作转换成为对树的插入， 删除和融合。 1 2 2 22 d 实时布局算法的研究现状 在实时布局算法中，最关键的是对空闲资源的管理算法。b a z a r g a n t l 4 】提出一种 重要的技术来管理空闲的资源。在布局算法研究这个领域的大部分工作都与此有 关。文中提出将空闲的资源用一系列的非重叠( n o n o v e r l a p p i n g ) 矩阵来表示，这种 表示方法为新到任务的布局和已经处理完成任务的删除提供的相当的便利。但维 护n o n o v e r l a p p i n g 矩阵时会出现即使存在足够的连续空闲空间，也会有任务的拒 绝情况。为了解决此问题，他们提出了管理最大空闲矩阵( m e r s ) 的算法，称之为 k a m e r ( k e e p i n ga l lm a x i m a le m p t yr e c t a n g l e s ) 。对于n 个任务，有d ( 以) 个 n o n - o v e r l a p p i n g 的矩阵，而m e r s 数目为o ( n 2 ) 。在本论文中管理空闲资源的思想 也是基于m e r s ，但具体实现时采用了矩阵编码和平面扫描技术来找寻所有的 m e r s ，使算法大大加速。 s t e i g e r l l 7 1 在b a z a r g a n 1 4 】划分算法基础上提出了一种加强版的划分策略。 b a z a r g a n 利用启发式算法用来决定一个空闲空间是按照水平分割还是垂直方向分 割。而s t e i g e r 算法是等任务到来之后，在决定如何对空闲区域进行划分。 w a l d e r t r 7 】基于b a z a g a n 提出了三种划分算法，其中一种应用了2 d 哈希表算法 来寻找任务的布局位置，时间复杂度为d ( 1 ) ，但是他们并没有考虑配置时间和更新 哈希表所需时间。 t a b e r 0 【1 2 】提出了一种基于装箱( b i n - p a c k i n g ) 启发式算法的空闲空间管理策略。 算法中将空闲空间表示成一系列的顶点集合，每一个用来描述可重构器件上的一 个空闲的边界。算法复杂度为d ( 刀：) ，n 表示当前器件上正在运行的任务，此算法 具有较小的资源碎片率。 h a n d a 和v e m u r i 1 8 】提出了一种基于管理重叠的m e r s 算法，文中将空闲空间 用阶梯( s t a i r c a s e ) 数据结构表示，通过这种数据结构可以快速的寻找到所有的 n 【e 黜。 通过分析可以发现，任务在2 d 可重构阵列上布局时都采用了空闲资源管理的 思想，同时可以看出任务的实时调度和实时布局算法之间是紧密相关的，调度模 块和布局模块之间是需要交互的。 5 电子科技大学硕士学位论文 1 3 研究内容和研究意义 1 3 1 研究内容 本文在目前研究成果的基础上，首先建立一个通用的2 d 多用户多任务可重构 计算系统模型。根据当前部分可重构( p a r t i a lr e c o n f i g u r a b l e ) 的特点，模型中r h d 不 仅支持空分复用共享( s p a c e - m u l t i p l e x e ds h a r i n g ) ，即硬件资源r h d 可以划分成为不 同的部分s u b r h d 分配给每个用户设计使用，同时每个s u b r h d 也具有时分复 用共享( t i m e - m u l t i p l e x e ds h a r i n g ) 的特点，即为每个用户设计分配的硬件资源可以在 时间轴上由用户设计的各个部分分时共享，并在此系统模型上研究r h o s 中的关 键算法：实时布局和实时调度算法。 本文主要分为以下几个部分： 第一章介绍了研究背景和研究现状，概述了本文的研究内容和研究意义，最 后给出了论文的结构。 第二章建立多用户多任务r h d 的系统模型，并阐述其主要功能，同时提出了 本文所用的资源模型和任务模型，定义所要解决的两个问题：多用户多任务实时 调度和实时布局。 第三章在多用户多任务r h d 系统模型上研究了实时调度算法，分为两个部分： u t s 调度和u t s 内部多任务的调度。在处理u t s 调度时采用了改进了f c f s 调度 算法，而处理u t s 内部任务调度时采用了时域划分技术，并提出了关键部分分割 算法。 第四章研究了实时布局算法，分为u t s 布局和u t s 内部多任务布局。在处理 u t s 布局时提出了最大剩余空闲矩阵算法，并采用矩阵编码技术实现了对算法的 加速。在处理u t s 内部任务布局时，提出了最小路由成本算法，用来布局内部数 据相关任务，使任务间的路由成本最小化。 第五章详细分析本文提出的调度和布局算法并得出结论。 第六章总结全文，并对未来工作做出展望。 1 3 2 研究意义 在可重构硬件平台不断发展的今天，如何更加有效的利用硬件平台资源，更 深入的发掘任务之间的并行性，是亟需解决的问题。本论文提出的调度策略和布 局算法对实现一个优秀的可重构操作系统具有借鉴意义。目前大部分研究都是针 6 第一章绪论 对多任务分时复用硬件资源的管理，很少有真正意义上的多用户多任务r h o s 。但 随着半导体工艺的发展，可重构器件的资源数目大幅度的增加，在一块可重构器 件上实现多用户并发操作将成为一种趋势。基于此，提出了多用户多任务资源管 理策略，填补了国内外在这个方向上的研究空白，对r h o s 的研究有一定的参考 价值。 7 电子科技大学硕士学位论文 第二章可重构计算系统模型 本章主要介绍用于本论文算法的r c 系统构架模型、资源管理模型、任务模型， 并对本论文拟要解决的实时布局和实时调度问题进行了定义。 2 1 可重构系统模型 粒度是指系统中可重构处理单元( m u ：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 ) 的操作 数的宽度。可重构系统构架按照粒度可分为三类：细粒度，粗粒度以及两者的混 合粒度。在可重构结构应用中，粒度决定配置时间和配置数据量，是影响性能的 关键因素【憎】。 虽然可重构系统具有很好的灵活性，但是目前并没有一种能够支持所有应用 的构架。下面将介绍目前关于可重构系统构架的研究成果，进而得出本论文所使 用的系统模型。 2 1 1 细粒度构架 细粒度可重构硬件与当前的f p g a 构架非常相似，此构架中基本的配置单元 为l e 或则c l b ，这些基本的配置单元由l u t 或则触发器组成。细粒度的可重构 系统能进行位( b i t ) 级操作，具有较高灵活性。但在处理字级宽度的数据计算，细粒 度可重构则表现出硅片利用率低、功耗大；配置数据量大、重构时间长；在逻辑 层进行编程开发相对难度较高等缺点。在本小节将介绍几种与论文算法相关的细 粒度构架。 商用部分可重构f p g a 主要有a t m e l 2 0 和x i l i n x l 2 1 】两大厂商生产。在图2 1 中 展示了x i l i n x6 2 0 0 系列的配置模型。在这个模型中，配置存储器中的每一个配置 比特都可以单独访问。 8 第二章可亚构计算系统模蟹 圜 x y 单元阵列 ( 列汗码器 ) 雠2 i l i n x x c 6 2 0 0 系列f p g a 配置存储器 a t m e l 的f p g a 提供部分配置的能力，并且实现了逻辑缓存的技术1 2 ”。逻辑 缓存是一种提高f p g a 资源利用率的有效方式。一个时序系统中正在执行的部分 运行于f p g a 上，而其它部分则存储在逻辑缓存中当逻辑缓存中的部分被激活 后，再将其放簧在f p g a 上执行。a t m e la t 6 0 0 0 系列f p g a 的配背模型如图2 - 2 所示： 嘲2 2 a m a e la t 6 0 _ 0 0 系列f p g a 配簧内存 配置存储器中的存储比特是一种长链状结构。每一个逻辑单元和i o 单元都能 够通过访问每一个配置比特来独立的配置。空白的单元代表可配置单元，而阴影 部分的单元代表正在运行的部分。 9 电子科技大学硕士学位论文 a t m e l4 0 k 系列的f p g a 允许通过向存储器窗口中写入配置比特来随机访问配 置存储器。最小的窗口大小为一个字节，其部分配置的粒度要比x i l i n xx c 6 2 0 0 系 列f p g a 粗，其适用于本论文中的任务模型。因为a t 4 0 kq - 艺允许任务在f p g a 的任何位置放置。 细粒度的f p g a 存在的最大问题就是较长的重构时间。a t m e l4 0 k 4 0 是一个 4 8 行4 8 列的f p g a ，在全局配置时需要4 2 0 6 3 个8 b i t s 的字。最大的配置时钟为 8 m h z 。所以此器件的全局配置时间为5 2 6 毫秒。同样，x i l i n xv i r t e xx v c l 0 0 0 是一款6 4 行9 4 列的f p g a ，全局配置比特数为7 6 6 0 4 2 ，所以用5 0 m h z 的配置时 钟其全局配置时间为3 1 毫秒。 细粒度的可重构器件除了较高的配置开销外，实时综合也需要较长的时间。 这是由于细粒度的综合中包括工艺映射、布局布线这样需要较长时间的步骤，而 在粗粒度器件上的这些操作都比较快。 2 1 2 粗粒度构架 在粗粒度( c o a r s e c , r a i n e a ) 的可重构体系结构中，r p u 中的处理元素可能包括 完整的功能单元，像算术逻辑单元a l u 、乘法器等，它们进行字( w o r d ，由多个位 构成) 级的操作，它的高效性适用于计算密集型的应用。粗粒度的可重构计数采用 多比特宽度的数据通道和互连，能够在硅片上对复杂操作进行高效的实现，节省 了路由操作，提高了硅片利用率。配置数据相对细粒度较少，重构时间也相对减 少。 目前国际上提出了一系列粗粒度的可重构系统构架，它们的配置比特流较小， 具有较快的配置速度。在【2 3 】中对目前的主要粗粒度构架的进行了概述。相对于细 粒度，其具有配置开销较小的特点【2 4 】。在这些构架中，主要采用了三种拓扑逻辑。 第一种拓扑是网格形式构架。在这个构架中，所有的功能单元被安排在一个 规则的2 d 阵列中，周围被全局和本地的路由资源所包围。大部分构架都属于这种 类型。一些网格形式构架如下所示： 一c h e s sa r r a y t 2 5 1 ，用于多媒体应用中，4 b i t 的粒度。 _ r a w 2 6 1 ，用于一些通用的计算任务，8 b i t 的粒度。 一g a r p 2 7 1 ，用于循环加速，2 b i t 粒度 一m o r p h o s y s 2 8 ，用于图像处理和数据加密，1 6 b i t 的粒度。 1 0 第二章可重构计算系统模型 _ d r e a m 2 9 1 ，用于3 g 无线通信，8 1 6 b i t 的粒度 _ a d r e s 【3 0 1 ，用于设计空间探索，3 2 b i t 粒度 第二种类型是流水线类型构架。这类构架基于处理单元的线性阵列，能够有 效处理任务。 一p i p e r e n c h 3 1 1 ，用于流水任务，1 2 8 b i t 的粒度 一r a p i d 3 2 1 ，用于通用计算任务。8 b i t 的粒度 c r e c 3 3 1 ，用于通用计算任务，1 6 b i t 的粒度 第三种是交换矩阵类型的构架。这类架用一个交换矩阵c r o s s b a r 来完成处 理单元之间的连接。 一p a d d i _ i 3 4 和p a d d i _ 2 3 5 ，用于数字信号处理，1 6 b i t 的粒度。 一p l e i a d e s 3 6 1 ，用于多媒体应用，有多种粒度。 图2 3 是目前比较有代表性的粗粒度可重构系轴a