（计算机应用技术专业论文）支持硬件任务可抢占的cpufpga混合架构的软硬件任务迁移研究.pdf

浙江大学硕士学位论文摘要 摘要 由于c p u 的通用性好，但是性能差；而可重构硬件并行加速性能好，但配置 代价大及加速类型的局限，从而c p u f p g a 混合架构成为可重构计算的重要形式， 它兼顾了硬件加速的高性能和软件的通用灵活性。针对软硬件混合任务的调度大 致可以分为两类，第一类是不允许抢占运行时任务，之前的绝大多数研究都属于 此类，但是这大大的限制了系统的灵活性和性能；另一类则是允许对运行时任务 的抢占，然后根据需求在软件或者硬件上恢复被抢占任务的执行，但由于一方面， 抢占的实现需要硬件的底层支持，另一方面软硬件任务的差异性使被抢占的任务 以不同形态在不同平台继续运行变的困难，所以目前这一类的研究相对较少。 为了支持可抢占硬件任务及软硬件任务迁移，本文提出了支持运行时任务抢 占和软硬件任务迁移的系统框架，抢占迁移机制。框架中的可重构设备中对每个 可重构区域增加了额外的中间数据存储器，用于对可重构任务中执行到预设的抢 占点时输出的中间数据的存储。同时新增了一个可重构任务迁移管理器用于对可 重构任务中断和恢复的管理。本文通过对任务流图及可重构任务配置比特流的分 析，确定出需保存数据小的点，然后通过插入信号来将这些点预设为抢占点。提 出了适合新框架下的调度算法。由于增加了软硬件迁移的过程，本文在原有调度 算法的基础上加入了对迁移的支持以适应新的框架。增加专用命名模块来解决任 务迁移后的重定位问题。由于支持软硬件任务之间任务的迁移，同一个硬件任务 在不同时刻可能存在于不同的可重构区域内，本文最后还针对n o c 互联的可重构 架构提出增加专用命名模块来提供命名服务，使任务间通过任务名称通讯，从而 保证了任务间的正常通讯。 实验表明，本文提出的迁移调度算法能有效的提高硬件任务的接受率 1 2 9 4 。因而本文提出的支持运行时任务抢占和软硬件任务之间迁移的系统可以 有效的提高整体性能。 关键词： 可抢占，迁移点，迁移调度算法 a b s t r a c t a st h ec p uh a sg o o df l e x i b i l i t yb u tp o o rp e r f o r m a n c e ，t h er e c o n f i g u r a b l ed e v i c e h a sb e t t e rp e r f o r m a n c eb u tw i t hl o n gc o n f i g u r ed e l a y , t h ec p u f p g ah y b r i d a r c h i t e c n l r eb e c a m eo n eo ft h em o s ti m p o r t a n tf o r m s t h er e s e a r c ha b o u tt h e s c h e d u l e a b o u th y b r i dt a s k si sah o t s p o t t h es c h e d u l ea p p r o a c h e sa b o u th y b r i dt a s k sc a n c l a s s i f yi n t ot w oc l a s s i f i c a t i o n s o n ei sa b o u t n o n - p r e e m p t i v em u l t i t a s k i n g ，t h eo t h e ri s p r e e m p t i v em u l t i t a s k i n g f o rt h es e c o n dc l a s s i f i c a t i o n ，a si tn e e d s t h ea r c h i t e c t u r e s u p p o r t , t h er e s e a r c hi sf e w e r t h i sp a p e rp r e s e n t st h ea r c h i t e c t u r ew h i c hs u p p o r tp r e e m p t i v em u l t i t a s k i n g f o r e a c hr e c o n f i g u r er e g i o n ，a ni n t e r m e d i a t ed a t a b u f f e ri sa d d e d t os t o r et h es t a t e i n f o r m a t i o nd u r i n gp r e e m p t i n g ar e c o n f i g u r em i g r a t i o nm a n a g e r i sa d d e df o rt h e e n t i r er e c o n f i g u r ed e v i c et om a n a g et h er e c o n f i g u r er e g i o n sf o rp r e e m p t t h i sp a p e r p r e s e n t sa na l g o r i t h mt os e l e c tt h ea p p r o p r i a t em i g r a t i o np o i n t a s t h em i g r a t i o n i n t r o d u c e d t h et r a d i t i o n a ls c h e d u l ea l g o r i t h m sa r en o ts u i t a b l e ，t h i sp a p e rp r e s e n t a n e ws c h e d u l ea l g o r i t h mb a s e dm i g r a t i o n a st h et a s kc a nm i g r a t e f r o mo n ep l a c et o a n o t h e r , t h e nt h et r a d i t i o n a lc o m m u n i c a t i o nb a s e d n o cb e t w e e nt h e mm a ye r r o r t o d e a lw i t ht h es i t u a t i o n ，t h i sp a p e ra l s oi n t r o d u c e sa nd e d i c a t e dn a m i n gn o d e f o r t r a n s f o r m a t i o nb e t w e e nt h en o d ei da n dn o d en a m e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mb a s e dm i g r a t i o ni n c r e a s e s t h e 12 9 4 a c c e p tr a t ef o rh a r d w a r et a s k s s ot h ea r c h i t e c t u r et h i sp a p e rp r o p o s e dc a n s u p p o r tt h ep r e e m p t i n gw e l l a n dc a ng e t t h ei m p r o v e m e n tp e r f o r m a n c e k e y w o r d s ： p r e e m p t i v e ，m i g r a t i o np o i n t ，s c h e d u l ea l g o r i t h m 浙江大学硕j ：学位论文图臼录 图目录 图3 1 数据流图1 5 图3 2 迁移点的设置方法1 7 图3 3 迁移点设置实例19 图3 4 增加了迁移点的硬件任务2 0 图3 5 增加了迁移点的软件任务2 1 图3 6 可重构资源模型2 1 图3 7 软硬件任务模型参数2 3 图4 1 支持硬件任务抢占和软硬件迁移的框架2 5 图4 2 混合任务状态转换图2 9 图4 3 可重构任务迁移管理器3 0 图4 4 中间数据缓存结构3l 图5 1 硬件任务执行完的判断3 6 图5 2 新任务到达时的调度算法3 7 图5 3 命名功能的两种实现3 8 图5 4 增加命名服务后的接口3 9 图5 5 命名服务查询过程4 0 图6 1 迁移算法对不同任务类的接收率比较4 2 图6 2 迁移算法对不同任务类的接收率提升比较4 3 图6 3 原始模式和片外命名服务模式的延时比较4 5 图6 4 原始模式和片上命名服务模式的延时比较。：4 7 图6 5 片上和片外命名服务模式的延时比较4 8 图6 68 x 8 网络中定位模块在网络内不同位置的延时比较4 9 图6 71 6 x 1 6 网络中定位模块在网络内不同位置的延时比较4 9 图6 8 平均吞吐率比较5 0 i i i 浙江大学硕士学位论文表目录 表目录 表4 1 运行时任务信息表2 8 表6 1 实验结果比较中缩写的意义4 4 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得浙江大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：签字日期：年月 日 学位论文版权使用授权书 本学位论文作者完全了解浙江大学有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权浙江大学可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期：年月 日 签字日期：年月 日 浙江大学硕i ：学位论文第1 章绪论 第1 章绪论 1 1 课题背景 通用处理器采用简单的并且固定的结构，可以执行任何类型的计算，由于其 通用性而得到了广泛的使用，但是针对所有应用其性能一般。特定领域的处理器 根据特定应用定制硬件结构，实现对特定应用的加速，适合于特定领域的一类计 算。特定应用处理器根据具体应用的特性定制硬件结构，对特定应用性能很好。 但是特定领域处理器尤其是特定应用处理器由于针对应用的定制性，虽然性能很 好，但是适用范围有限。可重构硬件的出现填补了通用处理器的灵活性但低性能 和专用处理器的性能高但专用性之间的空白，既拥有通用处理器的灵活性又拥有 专用处理器的高性能。可重构硬件通过运行时载入不同的配置动态改变硬件结构 来适应和加速不同的应用。可重构硬件中得到广泛使用的是现场可编程逻辑阵列 ( f p g a ) 。 可重构计算的概念最早由g e r a l de s t r i n 在19 5 9 年提出，随后提出了“固定部 分+ 可变部分+ 管理控制部分”的机器模型嘎但由于工艺的限制而一直没有得到 很好的发展。直到1 9 8 5 年，x i l i n x 公司生产了商用f p g a ，基本模型仍基于g e r a l d e s t r i n 提出的模型，随后得到了越来越多的关注和应用。尤其当通用处理器遇到 了性能提升的瓶颈，c p u f p g a 混合架构得到了越来越多的关注。 f p g a 的应用领域，包括用于原型创建和模拟；由于更短的投放市场时间而 作为a s i c 的替换产品：用于硬件的升级等。支持多任务的f p g a 由于其灵活性 在频繁改变工作集的高性能计算领域有着广泛的应用，主要有用户请求会随时变 化的可穿戴计算【2 】；网络流变化频繁的移动通信系统网络【3 】o 但由于仍没有操作 系统很好的支持f p g a ，并且配置时间长等限制而没有得到更好的应用。 动态可重构硬件不仅有高的硅复用率，还能给计算密集型任务带来高性能。 运行时重配置允许多个任务同时映射到相同设备上即时域复用。任务集需要最佳 或近似最佳调度来有效利用可重构设备。部分可重构允许在部分硬件上配置和执 浙江大学硕t 学位论文第l 章绪论 行新任务而不影响相同设备上其他正在执行的任务。最早的描述了硬件多任务的 研究之一出现在【4 】中。 最初的多任务可重构环境是不支持硬件任务抢占【5 】的，运行时间长的任务一 旦开始执行，只能等待该任务执行完成来释放可重构资源用于后续的任务，从而 阻塞了后续任务的执行导致任务集总体执行时间变长，性能降低。为了提高系统 性能，需要支持多任务可重构系统中可重构硬件任务的抢占，为每次任务的切换 提取和重组f p g a 的状态。现存文献中关于状态提取的方法包括读回所有数据流 然后滤取出状态位睁9 1 。这种方法的实现过程中需要假设知道信息位在数据流的位 置或者要求读回的数据流与配置比特流位置一一对应。第二种方法是在设计时加 入一个扫描路径寄存器结构【s - l o ，此方法不用读取所有片上存储，但是会降低时 钟频率，而且增加了硬件消耗。 可重构硬件任务的调度和使用操作系统来管理可重构硬件一直是可重构研究 领域的热点 4 1 。解决动态可重构架构的调度都是基于两类解决方法，一是静态f 编 译时1 调度技术，假设任务具有可确定的执行时间；二是动态联机调度算法，任务 的依赖关系在运行时确定。调度模块将任务分派给处理器，指定任务在处理器上 执行顺序及任务的开始时间。联机调度技术主要解决的问题足对依赖关系在运行 时确定的任务集的动态管理和支持。动态调度相关的大多数工作可以分为固定优 先级和动态优先级的分派策略。 现存文献中关于运行时软硬件任务之间的重分配的研究只有寥寥几个，并仅 限在系统级分析。状态转换器【8 】用于帮助软硬件任务之间的上下文转换，但是文 中并没有提出具体的实现。i n 中作者将分析限制在提出的关于任务是在硬件还是 软件执行的调度算法和各自的可行性测试。但是它既没考虑跨c p u 和f p g a 动 态重置的开销也没有提供任何完成的策略。 1 2 - 1 3 主要有两个贡献，一是使用统一 格式来高阶抽象任务执行流的；二是提出了迁移点的概念，用于软硬件之间的安 全迁移。但是他们的不足是，没有考虑到实现这种软硬件重定位的所有方面和挑 战，也没有对上下文数据抽取和恢复没有进一步的研究。为了支持调度和重调度 任务到硬件或软件的能力， 1 2 - 1 3 开发了下部构造，结合允许实现和管理可重定位 2 浙江大学硕士学位论文第l 章绪论 软硬件任务的设计环境提出了研究的一般范围，详述了通信方案，设计环境和软 硬件上下文切换问题。 1 2 研究动机 为了提高系统性能，需要支持对多任务可重构系统进行抢占，为每次任务切 换提取和重组f p g a 的状态。可重构硬件任务的切换不同于c p u 上的软件任务 切换，现代c p u 上的任务切换只需保存一些表示了当前进程状态的特殊寄存器值 用于恢复过程中的重组，在i n t e lp e n t i u mi i 中只有1 0 4b y t e s 需要保存和恢复；而 f p g a 中数据散落在各处，因而所有使用过的寄存器，l a t c h 和内部存储器中的数 据都必须保存下来用于任务的恢复，在x i l i n xx c v l 0 0 0 中的数据大小是3 5 0 k b 睁7 】。基于上述论述，现存文献中没有合适的状态存取和恢复的实现，而且也没 有对体系结构抢占支持的研究。 由于硬件任务的复杂性，硬件任务不能随时的抢占，而需要在硬件任务中预 设抢占点，只有等到任务执行到抢占点时才能进行任务的挂起，状态保存。抢占 点的设置足抢占环节中一个相当重要的问题。迁移点设置需要考虑两个方面的因 素，一是保存的数据要尽可能少，另一方面是抢占的反应时间要尽可能短。为了 使反应时间尽量短，则迁移点的粒度要尽可能小；即迁移点个数尽可能多，同时 还要求抢占点分布尽量均匀。硬件任务执行过程中，每个时间点都有数据的流动， 不同时间点的数据大小不同，如果抢占点的个数多，则一些需要保存数据多的时 间点也会被设置成迁移点。综合考虑反应时间和中间数据的大小，一方面要求合 适的迁移粒度，另一方面也需要合适的算法找出中间数据小的时间点同时要求这 些点尽量分布均匀。但是关于抢占点设置方法的研究很少。 现存的关于可抢占可重构任务的相关研究中，多是局限在单独的可重构硬件 平台，而不是针对c p u f p g a 的混合架构。因而没有很好的关于软硬件任务的迁 移调度算法及迁移后硬件任务的通讯问题的研究。 因此，本文试图通过对硬件任务的抢占在体系结构上提供支持，并在此基础 上解决迁移调度问题和任务恢复后的通讯问题。 3 浙江大学硕1 j 学位论文第1 章绪论 1 3 本文工作 为了支持硬件任务的抢占及软硬件任务迁移，本文提出了： 支持运行时任务抢占和软硬件任务迁移的系统框架。框架中的可重构设备中 对每个可重构区域增加了额外的中间数据存储器，用于对可重构任务中执行到预 设的抢占点时输出的中间数据的存储。同时新增了一个可重构任务迁移管理器用 于对可重构任务中断和恢复的管理，通过与c p u 中的迁移管理进程交互共同完成 软硬件任务的迁移。 硬件任务抢占点的设置方法。由于硬件任务与软件任务不同，硬件任务需要 设置抢占点才能在执行过程中被抢占，本文通过对任务流图及可重构任务配置比 特流的分析，确定出需保存数据量小的时间点，然后通过插入信号束将这些点预 设为抢占点。同时根据软硬件统一描述模型映射到软件任务，从而对软件任务也 预设抢占点。 适合新框架下的迁移调度算法。由于增加了软硬件迁移的过程，本文在原有 调度算法的基础上加入了软硬件任务迁移的策略用于新的框架的调度。 增加命名服务来解决任务迁移后的通讯问题。由于支持软硬件任务之间任务 的迁移，同一个硬件任务在不同时刻可能存在于不同的可重构区域内，而传统基 于片上网络( n o c ) 连接的可重构架构是单纯基于位置信息来通讯的，这将导致任 务问通讯失败，因而本文最后还针对n o c 互联的可重构架构提出增加命名服务使 任务间通过任务名称通讯，从而保证了任务间的正常通讯。 最后本文通过实验比较了增加了迁移调度策略的调度算法与基本调度算法 的比较。同时还对软硬件迁移调度后的两种不同的解决方法在平均延时和平均吞 吐率两方面进行了比较。 1 4 论文组织 本文的结构组织如下： 第l 章绪论：简要介绍了课题背景，本文的动机及本文的组织。 第2 章相关研究综述：详细介绍和分析了论文相关的背景研究及存在的不 4 浙江大学硕士学位论文第1 章绪论 足。 第3 章软硬件任务统一描述模型：从描述模型入手，提出了抢占点的设置方 法及设置实例。 第4 章支持可抢占和软硬件迁移的框架：提出了支持硬件任务抢占的体系结 构，并对每个模块进行了分析。 第5 章软硬件迁移机制：提出了增加了软硬件迁移策略的迁移调度算法。 第6 章实验设计和数据分析：介绍了实验的原理和对结果的比较分析。 第7 章总结和展望：首先总结了本文工作，然后指出了下一步的研究方向。 1 5 本章小结 本章首先介绍了可重构的历史及存在的必要性，接着是可重构硬件支持多任 务的必要性和方法，接着对现有的支持抢占的方法及调度算法的分析。然后根据 课题背景引入了解决现有研究不足的研究动机，接着提出了本文针对背景中的不 足所作的工作。最后叙述了本文的组织结构。 5 浙江大学硕士学位论文 第2 章相关研究综述 第2 章相关研究综述 f p g a 最甲于上世纪8 0 年中期作为实现随机逻辑引入，之后开发出新的应用 领域，包括用于原型创建和模拟；由于更短的投放市场时间作为a s l c 的替换产 品；用于硬件的升级等。支持多任务的f p g a 由于其灵活性在频繁改变工作集的 高性能计算领域有着广泛的应用，主要有可穿戴计算【2 1 ，其用户请求会随时变化； 和移动通信系统网络【3 】，其网络流变化频繁。随着f p g a 密度增加，广泛应用于 嵌入式系统中。 2 1 多任务可重配置架构 动态可重构硬件不仅有高的硅复用率，也能给计算密集型任务带来高性能。 运行时重配置允许多个任务同时映射到相同设备上或者时域复用。任务集需要最 佳或近似最佳调度来有效利用可重构设备。由于任务调度，分配和配置预取都需 要考虑，是这个问题成为一个n p 完全问题。动态可重构逻辑允许运行时重配置 硬件逻辑。部分可重构允许在部分硬件上配置和执行新任务而不影响同设备上其 他正在执行的任务。 f p g a 在可定制计算领域针对一些流水级深而且并行性高的算法显示出很好 的加速性能【6 1 。在f p g a 作为协处理器的应用中，整体执行时间及c p u 总线与协 处理器之间数据速率也是取得高性能的重要因素。 为了实现可重构硬件的多任务执行，一种方法是时间复用，将占用资源超过 f p g a 总资源的任务分成多个配置，然后顺序调度到可重构硬件上执行，但每个 时刻只有一个任务在可重构硬件上执行。但是时间复用引入了可重构延时，必须 最小化延时来提高性能。有两种方法解决这个问题，一是时间划分，任务必须分 成时间上独占的片段( 称作可重构上下文) 【1 4 1 。另一个不同的方法是为执行的任务 集找到一个合适的执行顺序来达到系统设计目标( 最小化执行n f b j ) ，这一般称为 可重构逻辑多上下文调度 1 4 - 1 6 】。另一种方法是空间复用，在f p g a 上并行执行多 个占用资源小的任务，每个任务占用自己的一部分可重构资源，而且可重构资源 6 浙江大学硕士学位论文第2 章相关研究综述 不能与其他的任务有重叠。【4 】是最早的描述了硬件多任务的研究之一。 在f p g a 作为协处理器的c p u f p g a 混合架构中，c p u 中的硬件管理器负责 多任务的控制和数据传输。由于c p u 与f p g a 之间的连接用于f p g a 上所有任 务的控制和数据传输，在每个任务中必须加入仲裁共享资源的逻辑，因而每个任 务的性能都会下降。并且同样的瓶颈也存在于f p g a 与外部r a m 和外部设备的 接口，由于外设在任一时刻只能被一个任务使用。 在支持多任务的动态可重构硬件中，任务管理类似与多处理器系统。但是不 同于多处理器的调度是还要处理任务分配和配置问题。在多处理器调度中，目标 系统往往有一定数量的同种处理器组成，任务可以映射到任意的处理器中。但是 动态町重构硬件的调度中，任务分配到不合适的区域会造成碎片，从而导致在空 闲面积足够的情形下后续的任务不能被映射。这是可重构硬件调度的一个挑战， 另一个挑战是配置的管理问题。支持多任务的可重构硬件的运行时重构引入了配 置延时和功耗，这将很大程度上降低系统性能。在设计阶段，提出了不同的方法 【1 7 】隐藏或减少配置延时的技术，如配置预取( 在需要之前载入任务) 。基本思想是 在任务需要之前载入下一个重配置上下文，因而重叠了设备配置和应用执行过 程。预取最早由【1 8 】提出，并且提出了一个单上下文预取技术。配置缓存f 重用已载 入任务) 和配置压缩( 压缩比特流) 。通常来说，这些系统级方法嵌入在任务调度过 程中可以有效地减少配置延时。 在不支持硬件任务抢占【5 】的多任务可重构环境中，运行时间长的任务需要执 行很长时间，即意味着将占用可重构资源很长时间，而其他任务在可重构资源不 足时必须等待可重构硬件上执行的任务释放可重构资源，这就将导致任务集总体 执行时间变长，尤其针对有截止时间限制的任务，会造成不能执行，最终造成总 体性能的下降。为了提高系统性能，任务管理器必须能够挂起正在执行的任务来 避免长时间阻塞的状况。为了避免运行时间长的硬件任务阻塞之后的硬件任务， 类似现代操作系统的可抢占多任务环境，为每次任务的切换提取和重组f p g a 的 状态。在未考虑部分可重构的【】中中提出了为了实现可抢占多任务系统必需满足 的硬件特性。文中通过读回的所有数据流，然后从中滤出所有信息位，此选择减 7 浙江大学硕l - 学位论文第2 章相关研究综述 少了大约9 0 需保存的比特数。但是没有提出具体的滤出信息位的方法。为了提 取出这些状态位，它们在回读流中的比特位置必须知道。但是读回所有数据流将 花费很长的时间，从而增加了总体延时。而在任务的恢复是通过直接在配置流中 正确的设置每个寄存器和r a m 的位。所有初始化位在比特流中的位置必须知道 才能支持直接编码比特流的位。【1 9 】提出的j b i t s t m 提供了用于存取x i l i n x 的f p g a 比特流的a p i 。 现代c p u 上的任务切换只需保存一些表示了当前进程状态的特殊寄存器值用 于恢复过程中的重组，在i n t e lp e n t i u mi i 中只有10 4b y t e s 需要保存和恢复；而 f p g a 中数据散落在各处，因而所有使用过的寄存器，l a t c h 和内部存储器必须保 存用于任务之后的恢复，在x i l i n xx c v l 0 0 0 中要求3 5 0k b t 6 一。 s - 9 针对硬件任务抢占提出了两种方法，第一种也是读回全部的数据流，然后 与配置流进行逐位异或操作滤出信息位，然后进行压缩存储。与 6 - 7 1 不同的是此方 法的实现不要求知道状态位在回读流中的位置，但是与之类似的限制是回读流必 须与配置流一一对应，而这样的假设是很没有实际意义的，因为经过一些的计算 操作，回读的流不太可能仍然和配置流位置对应。这种方法的好处是不需要增加 额外的硬件结构。第二种方法是在设计时加入一个扫描路径寄存器结构，扫描路 径跟随数据通路的结构，用一个全局信号来指定寄存器是普通节点还是在扫描路 径上。此方法可以减少捕获状态信息的时间消耗，但是会降低时钟频率，而且增 加了硬件消耗。【9 】提出支持配置比特流存储在s r a m 单元中f p g a 流的回读结构， 此方法在回读流的基础上将被换出任务数据流读出与新任务部分配置流载入两 个过程并行执行，从而隐藏了回读流造成的延时。t l o 提出了一个改进的扫描路径 寄存器结构。 减少回读的数据量主要分为两种方法，一种方法是在每个状态寄存器t - _ 增加 读写接口用于抢占过程中的直接读取保存和恢复过程中直接写入【1 2 2 0 】。实现可以 是扫描链【8 j o 】或者r a m 支持可寻址。为了减少需要处理的寄存器数量，可以为每 个任务实现关闭过程。此方法的数据效率高，但是实现关闭过程需要额外的硬件 资源和关闭时间代价。但当运行的任务是i p 核时，这种方法就不可能实现。另一 8 浙江大学硕士学位论文第2 章相关研究综述 种方法是所有寄存器读写都通过同一个端1 2 1 读写9 2 l 】。此方法的好处是不需要增 加额外的硬件消耗，但数据效率低。1 2 1 1 通过在任务执行过程中将信息写到一个数 据库中，在回读过程中对比数据库提取状态信息而不是在读取完成后再处理，这 可以减少回读数据的数量，从而降低了时间代价。 2 2 可重构任务的调度 片上系统的任务调度一直是嵌入式系统设计的一个难点。嵌入式系统已经有 大量的调度方法 2 2 】。而解决动态可重构架构的调度方法都是基于两类解决方法， 一是静态( 编译时) 调度技术，假设任务具有可确定的执行时间；二是动态联机调 度算法，任务的依赖关系在运行时确定。调度将任务分派给处理器，指定任务在 处理器上执行顺序及任务的开始时间。典型的静态调度算法假设任务执行时间是 最差执行时间( w c e t ) 【2 2 1 。但是系统设计使用w c e t 估计会使可重构资源没有充 分利用。任务执行时间很少是确定的。例如，它可能是数据依赖的( 视频帧编码的 运行长度依赖与帧内的信息1 。此外，执行时间可能依赖于可用的资源，尤其当多 个应用程序共享一个系统。 针对编译时确定的任务集，静态调度技术【2 3 1 专注于最优或局部最优的解决方 法。已有一些加入了配置管理的启发式静态调度器被提出。 预取配置通过提前载入需要的配置来隐藏配置时问从而显著减少可重构延 时。 1 8 1 针对单上下文可重构处理器提出了在软件指令序列里插入预取指令，从而 在软件指令序列执行到调用可重构硬件进行计算之前将所需配置载入到f p g a 中。f 2 4 】开发了一种混合设计时运行时支持预取的启发式配置调度算法，在设计时 进行启发式调度算法中的所有计算密集型的计算，只有小部分依赖于非确定动态 行为的计算在运行时进行，并且在运行时调度重配置。 【2 5 】提出了第一个多目标协同综合系统，提出了一个二维多速率循环调度算法， 算法中考虑了任务周期，模型中使用了配置缓存来处理周期任务。 还有一些编译驱动的任务调度器， 2 6 1 中提出指令调度算法来最小化执行重配 置指令的数量。算法是基于编译分析和反馈定向技术，指令调度器将配置指令移 9 浙江大学硕上学位论文第2 章相关研究综述 出循环来减少需要的配置次数。【2 7 】提出了一个改进的指令调度器，缓存最频繁的 可重构任务配置来进一步减少需要的配置数量。动态可重构逻辑的多上下文调度 已经有一些研究【1 5 】。其中 2 8 1 中提出了基于回溯的递归算法来用于多上下文的调 度。但是所有的方法都足基于静态的调度技术，在【2 9 】提出了一个集成的算法用于 软硬件划分，调度，时域划分和上下文调度。与此方法类似的还有【3 0 】，但也是基 于静态调度的。 优化静态调度方法，包括【3 1 】中的映射任务到动态可重构硬件的优化布局器， 将配置代价作为常数对待。由于重配置过程不是单独处理的，此方法没有考虑预 取和重配置限制等问题。 与之前工作相似的是，【2 3 】专注于静态调度，使用了有向无环图建模任务解决 一维配置模型的调度问题。提出了三种不同的解决策略来解决调度问题。第一个 是从传统基于列表算法【3 2 】改进得到的基于优先级的启发式调度算法，任务的优先 级依赖于当前的调度状态和代表任务集的有向无环图的结构。此算法有效性高但 是精度低。第二个是基于约束规划【3 3 】，一个应用程序可以针对给定任务图和设备 模型自动生成约束模型。可以保证给出最优解但是需要显著的搜索代价。第三个 是一个遗传算法，一个有指导的随机搜索策略，灵活性好，使用者可以权衡计算 代价和精度。拥有合理的效率和比启发式算法更好的精度。 【3 4 】提出基于块的一维可重构资源模型，最小的重构单元是一个b l o c k ，每个 b l o c k 垂直方向上占据了可重构设备的整个高度，而水平方向上的宽度各不相同。 可重构硬件上从左到右b l o c k 按降序排列。b l o c k 的宽度在任务调度时是固定的。 调度过程分成两个部分，第一步称作f s p l i t 的过程，将新到达的任务按宽度按一 定的排列方法分配到满足面积要求的最右的队列中，如果该队列不存在，则建立 这个队列。每个队列对应着一个b l o c k 。第二步是f s e l e c t 过程，选择在每个b l o c k 中下一个执行的任务，配置到满足面积要求的最小的b l o c k 中。选择过程有两个 模式，一种是严格模式，即队列里的任务只能放置在对应的b l o c k 中；而另一种 更好( p r e f e r r e d ) 模式则是允许任务放置在对应b l o c k 的左侧的任意b l o c k 中。 【3 5 】针对一维资源模型，提出了两种调度方法。两种方法都维护执行列表e 和 l o 浙江大学硕士学位论文第2 章相关研究综述 保存列表r ，执行列表用于记录正在运行的任务，位置和完成时间；保存列表记 录的是被调度的任务，位置和开始时间。第一种称为l dh o r i z o n 算法，额外维护 着一张水平列表( s c h e d u l i n gh o r i z o n ) h ，记录了所有位置及对应的释放时间。当一 个新任务到达时，调度算法扫描h 列表，在满足截止时间条件下按释放时间顺序 匹配满足任务条件的最小位置，若找到，则将任务添加到r 中，更新h ，否则拒 绝此任务。第二种算法是1 ds t u f f i n g 算法，额外维护一张空闲表f ，当新任务到 达时，调度器考察未来所有可能的空闲位置，包括可能与r 中任务冲突的位置， 然后进行冲突检测，将没有冲突的最小位置分配给新任务，并加入到r 中。算法 实现中有3 个事件，一是任务停止，二是任务开始，三是新任务到达。新任务到 达时，首先将停止的任务停掉，运行r 中满足开始时间的任务，然后选取此时刻 符合任务条件的所有位置，接着与r 进行冲突检测，无冲突则将新任务添加到r 中，否则查看下一个事件点的。针对2 d 资源模型，将h o r i z o n 和s t u f f i n g 算法扩 充，将l d 中的左端起点w i 改变为2 d 中的左上角( x j ，y i ) ，同时相邻空闲面积的合 并存在差异。 区分调度和放置算法优劣的标准包括总的调度时间和碎片数量，而现存调度 算法一般不考虑或者推迟考虑碎片问题。【3 6 】提出了基于一维的可重构资源模型在 放置任务时减少碎片的调度和放置算法。在原有s t u f f i n g 技术【3 5 】的基础上改进得 到了分类s t u f f i n g 技术用于在满足任务所有属性的情况下最小化调度时间和浪费 的空间数量。根据“面积执行时间”的比值将任务分为两类，将比值大于l 的划 分为高面积利用率，比值小于等于l 的归为低面积利用率。不同的类放置位置不 同，将高面积利用率的任务从左往右放置，而低面积利用率的任务从右往左放置。 联机调度技术主要解决的问题是对依赖关系在运行时确定的任务集的动态管 理和支持。动态调度的相关的大多数工作可以分为固定优先级和动态优先级的分 派策略。单调速率分析( r a t em o n o t o n i c a n a l y s i s r m a ) 是固定优先级的一个例子； 最早时限优先( e a r l i e s td e a d l i n ef i r s t e d f ) 是动态优先级的策略。e d f 在理论改进 方面好过r m a ，但是e d f 由于其运行时代价大而没有广泛使用。 部分可重构技术一方面提高了设备利用率，但同时也导致了复杂的调度情形 浙江大学硕i ：学位论文第2 章相关研究综述 ( 由于多任务执行) 。如果再考虑任务同有的动态性，任务的调度将会变的更加复 杂。鉴于操作系统对应用的运行时有很好的支持，一些研究使用o s 4 3 5 3 7 佣于管 理可重构设备来解决复杂调度情形。但有研究表明o s 会消耗大量的功耗【38 1 。1 4 最早工作在虚拟硬件操作系统，o s 的主要目标足可交换逻辑单元的放置。【3 5 】中 提出了用操作系统服务束调度动态可重构硬件上的实时任务。与其他方法不同之 处在于新任务到达时要么拒绝要么保证满足截止时间的接受。在 3 7 3 9 】中作者将目 光集中在资源碎片的管理，提出了不同的重新打包和替换已载入的任务的技术。 但是没有讨论任务运行时重新安排的代价。 在【5 4 0 的在线任务调度被建模成装箱问题，提出了不同算法来解决这个n p 完 全问题。1 4 1 】用一个数据结构记录空闲面积的顶点的轨迹。提出了一个使用顶点列 表为就绪任务搜寻空闲位置的低碎片启发式的分配算法。【4 2 】提出了配置敏感的在 线调度器，尽可能多的重用已载入的配置。在一个在线情形中，配置管理引入代 价，在要求高性能和低功耗的系统中不可用。 4 3 - 4 4 弓i 入了一个基于硬件的多任务 支持单元的动态调度方法，针对有硬件配置预取单元和没有配置预取单元两种情 况分别进行了实现。两种算法都使用设备的可重构特性重叠任务的执行尽量最小 化重配置代价。畔】提出了新颖的方法解决在部分可重构架构的非抢占多任务问 题。这种方法的主要特性是使用了支持动态调度的微架构，微架构使用了基于硬 件的配置预取单元。【5 】处理了f p g a 上的非抢占多任务，专注于任务的放置和足 迹的变化。解决f p g a 可抢占多任务方法有【7 1 。 2 3 软硬件混合调度和迁移 在任务迁移中，减少对正常( 非迁移) 执行引入新的代价和减少迁移过程中的反 应时间( r e a c t i o nt i m e l 很重要。自从1 9 8 0 年以来，已经相继有一些多计算机之间任 务迁移机制开发出来，其中有两个比较独特的迁移启动方法。第一种是基于 p o l l i n g 4 5 1 ，它在执行代码中的迁移点的位置引入初始p o l l i n gp o i n t s ；代码中p o l l p o i n t s 的数量和位置决定了性能：p o l lp o i n t s 太多会导致运行时代价大；而不足则 增加了反应时间。为了激活迁移请求，o s 所需做的工作就像设置一个全局变量 1 2 浙江大学硕十学位论文第2 草相关研究综述 一样少。第二种方法是基于动态改变代码。当接收到一个迁移请求时，运行时改 变执行代码来引入迁移启动请求。t u i 系统【删停止相关任务并在每个迁移点放置 断点指令，然后任务继续执行直到遇到断点。为了避免插入断点时覆盖其他指令， 可以在代码中插入空指令来预留额外的空间。但是此方法为普通执行也引入了性 能开销。p r a s h a n t h 4 7 】使用了侦测迁移点之间的代码碎片的技术，然后在代码的副 本中插入迁移起始指令。此技术不需要占位符指令。第二种方法相比第一种方法 使能一个迁移点需要更多的工作，从而拉长了反应时问。vn o l l e t 4 8 】提出了一种 重用处理器的调试寄存器i n s t r u c t i o na d d r e s sc o m p a r e ( i a c ) 寄存器来产生一个异 常中断硬件执行来完成硬件任务的抢占，此方法最小化了任务的普通执行代价。 但是此方法存在明显的不足，主要是调试寄存器有限，x i l i n xv i r t e x l ip r of p g a 自 带的p o w e r p c 4 0 5 只包含4 个3 2 位的i a c 寄存器，而任务的迁移点必须比调试 寄存器的数量少，从而限制了此方法的应用。另一个不足是会干扰调试器，还有 迁移点的设置缺少编译器支持。 【2 1 】中提出的r e p l i c af i l t e r , 负责操纵部分比特流来重新安置硬件任务到合适 的新位置，但是仅限于域内重定位。【4 9 】包含对混合任务重放置的支持，帮助用户 设计一个混合任务，实现混合任务在c p u 和f p g a 之间的重分配。 运行时软硬件任务之间的重分配只有寥寥几个，并仅限在系统级分析。【8 】中 提出了状态转换器，用于帮助软硬件任务之间的上下文转换，但是没有提出具体 的实现。【l l 】中作者将分析限制在提出的关于任务是在硬件还是软件执行的调度算 法和各自的可行性测试。但是它既没考虑跨c p u 和f p g a 动态重置的开销也没 有提供任何完成的策略。 1 2 - 1 3 】主要有两个贡献，一是使用统一格式来高阶抽象任 务执行流的；二是提出了迁移点的概念，用以安全的软硬件之间的迁移。但足他 们的不足是，没有考虑到实现这种软硬件重定位的所有方面和挑战，还有就是上 下文数据抽取和恢复没有进一步的研究。为了支持( 重) 调度任务到硬件或软件的 能力， 1 2 3 】开发了下部构造，结合允许实现和管理可重定位软硬件任务的适合的 设计环境。提出了研究的一般范围，详述了通信方案，设计环境和软硬件上下文 切换问题。 浙江大学硕一 ：学位论文第2 章相关研究综述 【8 】提出了针对没有考虑通讯模式的任务模型下软硬件混合调度的算法，算法 首先确定混合任务足运行在软件还足硬件。然后调度器针对混合任务决定是抢占 一个运行时任务还是运行在软件上，插入到软件或硬件队列，调度软件和硬件队 列，根据截止时间对两个队列中任务各自排序，作为队列中的第一个任务，由于 等待时间，需要再次确认。针对硬件任务，还需确认是否有足够的空间；若不足， 先查看缓存；若没用，则根据截止时间抢占正在运行的任务。1 5 0 1 增加了联机接纳 控制测试单元并提出了一个新颖的资源分配方案包括对混合任务调度和软硬件 任务之间的重分配算法，用于最大化接纳的实时任务。但是没有对任务抢占的底 层支持。 2 4 本章小结 本章首先列举了可重构硬件需要支持多任务的重要性，分析多任务系统中现 存研究减少存在延时的一些解决办法。基本的多任务可重构系统是不支持抢占 的，但是由于此限制导致长的等待时间。解决的办法是支持对硬件任务的抢占， 本章分析了现存研究对硬件抢占支持的一些实现方法。然后对可重构硬件任务的 静态调度方法和动态调度方法的实现进行分析。最后对软硬件任务之间迁移的支 持实现和提出的一些新的调度和迁移混合任务算法的分析。 1 4 浙江大学硕j j 学位论文第3 章软硬件任务统描述模型 第3 章软硬件任务统一描述模型 3 1 软硬件任务模型 每一个混合任务都可以根据其具体行为生成一张数据流图，软件实现和硬件 实现都遵循这个任务流图。图3 1 就表示了一个简单的任务流图，图中