可重构计算中的任务在线调度与放置策略评述

《可重构计算中的任务在线调度与放置策略评述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、可重构计算中的任务在线调度与放置策略评述Abstract:WiththeappearanceofSRAM-basedFPGA,thereconfigurablecomputingtechnologyhasbeenincreasinglywellstudied,whileon-lineshedulingandplacementoftasksisaimportantresearchdirectionforreconfigurablecomputingarchitecture・Thispapersummarizesthebasicmod

2、eloftaskson-lineshedulingandplacement,introducesthefundamentalimplementationmechanismofexistingrepresentativealgorithmswhichbasedonthemodel,andcomparesandanalyzestheiradvantagesanddefects・Finally,itdiscussesrestrictionsofintegratingthetaskson-lineshedulingandplacement

3、forreconfigurablecomputingintothepracticalapplicationsandfutureresearchtopicsarepointedoutaswell.Keywords:FPGA;Reconfigurablecomputing;on-linescheduling;taskplacement摘要：棊于SRAMFPGA的出现，使得可重构计算得到口益广泛而深入的研究，而任务的在线调度与放登是可重构计算体系结构屮重耍的研究方向。概述了任务在线调度与放登的基木模型，介绍了当前典型的基于该模型算法的实

4、现机制，并分析与比较了这些算法优势与缺陷。最后，根据当前研究进展，讨论了将可重构计算中任务在线调度与放置融入实际工程应用中亟待解决的若干关键问题，指出了未来的研究方向。关键字：FPGA;可重构计算;在线调度;任务放置1.引言基于SRAM的FPGA可重构器件很好的融合了专用集成电路快速、精确的计算性能与通用集成电路灵活性高的优点，并且可以对其进行反复的编程⑴，因此在学术界与工业界可重构计算都成为了研究的热点。硬件设计中可重构技术的出现，对嵌入式系统与片上系统（SOC）的设计都产牛了重要的影响，支持可重构技术的硬件日益成熟，但与之和关

5、的软件工具与设计系统平台仍处于刚刚起步的阶段⑵。如XilinxVirtcx-IIPro⑶⑷FPGA的有全部可重构功能与部分可重构功能,全部可重构每次要对可重构区域进行全部的重配置，部分可重构特性允许可配置资源与内部互联网络在不影响其它逻辑单元运行的情况下实时的重构。山于这一技术能使多个任务在FPGA±并行执行，并允许芯片上的任务被移除或被具它任务替换，这为在可重构设备上构建一种能提供任务调度、资源管理以及基木的编程模型⑸⑹的嵌入式可重构操作系统带来了研究机遇。早期可重构操作系统人多侧重于非实时的任务调度模型⑹，不过近儿年也开始提出

6、了一些实时任务调度阳冏模型的操作系统。而无论是基于哪种模型的口J重构操作系统，其中任务调度都是一个极其重要的的方面,利用合理高效的调度算法有效地对硬件任务进行调度与管理，减少任务的总执行时间，降低任务的拒绝率，提高芯片利用率已经成为了重要的研究课题。尤其在可重构计算屮，目前基于ChristophSteiger与HerbertWaldci•⑸⑹提出的系统模型的任务调度与放置算法，主要冇在线与离线两种。在离线任务调度与放置[7][8][9][10]屮，系统开始运行前对任务优先级以及释放时间等各种信息是已知的，调度器可以対硬件任务进行各

7、种优化以达到满足某种评价标准的最住放置方案；而在线方法屮，任务的到达时间事先是不知道的，对可重构资源与硬件任务的管理需要在系统运行屮实时进行，而无论是在线还是离线的任务调度与放置部是NP・难问题⑸。木文首先介绍了可重构任务在线调度与放置的架构模型，然后综述了任务在线调度与放置领域的研究状况，主要针対调度/放置的算法分析、实现机制以及所血临的问题与挑战展开论述。2.可重构计算系统模型2.1系统模型ChristophSteiger,HerbertWalder[2]⑶为动态可重构SOC的设计与实现，提出了如图1所示的系统模型。整个系统的

8、架构是由主处理器与町重构设备组成，到达的任务都存储在图1系统模型任务队列屮，可重构资源与硬件任务的管理主要由处理器上运行的三个模块：调度器、放置器与装载器实现。其中调度器使用某种调度算法为到达的任务分配开始吋间，它将放置器看成一个了功能；放置器管理