可重构混合任务调度算法

隐藏和减少配置时间是可重构任务调度的关键问题。针对同时存在相关联的软、硬件任务的可重构混合任务,提出一种可重构混合任务调度算法。通过预配置策略和优先级算法确定需要预先配置的任务及其预配置顺序,将后继任务的配置过程隐藏在前驱任务的运行时间中,并采用配置重用策略,减少相同任务的配置次数。实验仿真结果表明,同已有的算法相比,该调度算法调度效果明显,减少了可重构任务调度的整体开销。     

可重构混合任务调度算法

隐藏和减少配置时间是可重构任务调度的关键问题。针对同时存在相关联的软、硬件任务的可重构混合任务,提出一种可重构混合任务调度算法。通过预配置策略和优先级算法确定需要预先配置的任务及其预配置顺序,将后继任务的配置过程隐藏在前驱任务的运行时间中,并采用配置重用策略,减少相同任务的配置次数。实验仿真结果表明,同已有的算法相比,该调度算法调度效果明显,减少了可重构任务调度的整体开销。     

采用配置完成优先策略的可重构任务调度算法

如何隐藏和减少配置时间是相依性可重构任务调度的关键问题.提出一种采用配置完成优先策略的相依性可重构任务调度算法,通过基于预配置优先级的列表调度算法,实现将后续任务的配置时间隐藏于前驱任务的运行时间中,并采用基于配置完成优先策略的配置重用机制,减少了任务调度后的配置过程,从而在总体上缩短了相依性任务集合的运行时间.仿真结果表明,该调度算法能有效避免调度死锁,并可减少相依性可重构任务的整体运行时间.     

一种基于代价抢占的混合可重构任务调度算法*

针对同时存在独立任务和相依性任务的混合可重构任务调度,提出了基于代价抢占的混合可重构任务实时调度算法。提出了相依性任务等价运行截止时刻的计算方法,使混合可重构任务按照配置截止时刻排队配置。针对相依性任务调度特点,分析得到了相依性任务集合调度失败的充分条件,提前判定和丢弃无法调度成功的相依性任务集合;通过有限预配置防止相依性任务无效占用可重构资源;通过基于代价抢占减少调度失败任务个数。仿真结果表明,该调度算法提高了任务调度成功率。     

一种采用边界表进行可重构资源管理及硬件任务调度的算法

可重构计算兼具硬件的高效性和软件的灵活性,发挥可重构计算的高性能,对可重构资源及硬件任务进行有效管理和科学调度是关键.针对一维可重构器件中硬件任务调度问题,提出一种基于边界表的可重构资源管理方法,该方法用"边界表"数据结构记录R-T坐标系中的区域边界及其位置关系,实现对可重构资源的管理.以此为基础,提出了R-T坐标系下的任务调度及布局算法:BT-P算法,实现硬件任务的调度和布局.算法采用加权边界重叠长度作为任务调度的估值函数,与采用边界表的资源管理方法相结合,以较小的运行时开销实现调度的优化.实验表明,与Stuffing算法相比,BT-P算法下的可重构硬件的器件利用率随负载率的变化提高5%～11%,任务拒绝率随负载率和松弛因子的变化降低9%～11%,每个任务的平均调度布局时间开销在2～4μs之间.     

一种基于双仲裁时间片策略的可重构硬件任务调度算法

在可重构系统中,二维布局模型比一维布局模型具有更高的自由度.然而,二维模型获得较高的资源利用率要以复杂的资源管理和任务调度算法为代价,这不但使调度过程变得复杂,而且导致时间开销大,直接影响系统实时性.针对这一问题,在综合考虑性能和算法复杂度的基础上,提出了一种适用于二维可重构器件的双仲裁时间片可重构硬件任务调度算法DATS(Double Arbiters Time-Sliced).算法采用两个仲裁器对硬件资源进行管理,并根据空间和时间约束动态裁决任务布局位置;同时设计了双仲裁时间片任务调度模式图,对任务的调度和布局过程进行合理分离,使任务调度和布局过程相对独立并简化处理过程.DATS算法的调度时间复杂度为O(N),单任务布局算法的时间复杂度为O(E),其中N为被调度的任务总数,E(＜N)为器件中正在执行的任务数目,实验表明,DATS算法时间开销小,在轻负载情况下任务调度成功率比stuffing算法高1％～2％,在重负载情况下资源利用率保持在80％～85％的水平,与时间复杂度为O(N2)的算法基本一致,所以更适合于实时情况下的任务调度.     

动态可重构技术研究综述

动态可重构技术可使硬件设备在运行时根据不同的计算任务实现不同的功能,在发挥应用程序效率的同时,又能充分利用系统软硬件资源。根据固定器件与可重构器件的关系,可以将可重构系统划分为不同的结构。适应各自结构的特点,将任务合理的分解为软件部分和硬件部分,是高效完成计算任务的基础。当硬件任务较多时,系统需要一个良好的算法来进行调度。最后,可重构系统应该为用户提供一个结构透明的开发平台,使用户可以方便的利用可重构计算的强大能力。     

面向RSoC的过程级动态软硬件划分

软硬件划分作为可重构片上系统设计的重要技术手段,其结果直接影响到系统的性能。目前的软硬件划分大多只考虑从算法本身提高划分效果,忽略了划分结果的具体配置实现,导致划分效果很不理想。分析了预配置模型下的任务描述,给出了预配置调度优先级的计算方法,设计了一种预配置调度策略;针对软硬件划分与动态可重构的特点,提出并实现了一种结合预配置的软硬件划分算法,给出了一种评价软硬件划分方案优劣的方法。实验结果表明,该划分方法具有良好的划分效果。     

面向区分服务的可重构任务在线调度算法

现有的先来先服务和预约调度算法中可重构任务调度顺序取决于该任务到达次序,无法体现不同任务的优先级差异以及前后任务的时间关联性,为此提出一种基于预约抢占的可重构任务在线调度算法.通过区分不同任务的优先级属性,并引入任务紧迫度的概念,实现差异化任务调度;对已预约任务采用预约失效机制,使高优先级或同优先级中紧迫度较大的新任务优先调度,从而实现对已预约任务队列进行抢占式调度.实验结果表明,该算法能有效地提高任务的整体调度成功率,并可优先保证高优先级任务的调度成功率.     

基于遗传算法的可重构系统软硬件划分

在考虑动态部分重构及重构延时等特征的基础上,采用遗传算法及其与爬山算法的融合实现可重构系统软硬件任务的划分,并采用动态优先级调度算法进行划分结果的评价。实验表明,在可重构系统的资源约束等条件下,算法能够有效地实现应用任务图到可重构系统的时空映射。     

一种面向动态可重构计算的调度算法

硬件任务的调度是影响动态可重构系统性能的关键因素之一.提出一种任务间最小空隙调度算法MGS(minimum gap scheduling algorithm),该算法借助任务投影和调度代价函数,采用二维时空坐标系协调各硬件任务占用的芯片资源和执行时间,可有效减少系统资源浪费,提高并行度.MGS算法策略直观,调度开销小,且同时适用于实时和非实时场合.仿真实验表明,与已有算法相比,MGS算法不但降低了硬件任务的调度时间开销,而且具有更高的芯片利用率和更低的任务拒绝率.     

一种动态可重构系统的实时任务调度算法

硬件任务的软实时调度是影响动态可重构系统性能的关键因素之一。本文提出了一种基于顶点链表的硬件任务间最小空间调度算法MSSA,该算法将硬件任务按照长、宽及调度时间构成一个三维资源模型,以到达任务与已放置任务在三维空间的邻接度来构建代价函数,获取具有最大代价函数值的放置位置和启动时间,可使任务安排得更紧凑,减小对系统资源的浪费,提高并行度。仿真实验表明,与MSG-4V和Stuffing算法相比,本文算法具有更高的芯片利用率和任务接受率。     

Online scheduling and placement of hardware tasks with multiple variants on dynamically reconfigurable field-programmable gate arrays

Hardware task scheduling and placement at runtime plays a crucial role in achieving better system performance by exploring dynamically reconfigurable Field-Programmable Gate Arrays (FPGAs). Although a number of online algorithms have been proposed in the literature, no strategy has been engaged in efficient usage of reconfigurable resources by orchestrating multiple hardware versions of tasks. By exploring this flexibility, on one hand, the algorithms can be potentially stronger in performance; however, on the other hand, they can suffer much more runtime overhead in selecting dynamically the best suitable variant on-the-fly based on its runtime conditions imposed by its runtime constraints. In this work, we propose a fast efficient online task scheduling and placement algorithm by incorporating multiple selectable hardware implementations for each hardware request; the selections reflect trade-offs between the required reconfigurable resources and the task runtime performance. Experimental studies conclusively reveal the superiority of the proposed algorithm in terms of not only scheduling and placement quality but also faster runtime decisions over rigid approaches.     

基于放置代价的可重构系统任务统一调度算法

高效的任务调度算法对可重构系统的性能有极大的影响。针对目前可重构系统任务在线调度算法的不足,提出了一种基于放置代价的调度算法。该算法考虑了3种代价,分别为:硬件任务在FPGA上的执行时间、占用的FPGA面积以及FPGA的碎片情况,并且也考虑了软硬件任务的统一调度。在调度过程中,当代价超过设定的阈值时,就拒绝其在FPGA上运行,并由CPU执行其软实现。通过合理地拒绝一些代价较大的任务,能够从整体上提高任务调度成功率。实验表明,同已有算法相比,该算法能够获得更高的任务截止保证率。     

Configuration Reusing in On-Line Task Scheduling for Reconfigurable Computing Systems

Reconfigurable computing systems can be reconfigured at runtime and support partial reconfigurability which makes us able to execute tasks in a true multitasking manner.To manage such systems at runtime,a reconfigurable operating system is needed.The main part of this operating system is resource management unit which performs on-line scheduling and placement of hardware tasks at runtime.Reconfiguration overhead is an important obstacle that limits the performance of on-line scheduling algorithms in reconfigurable computing systems and increases the overall execution time.Configuration reusing (task reusing) can decrease reconfiguration overhead considerably,particularly in periodic applications or the applications in which the probability of tasks recurrence is high.In this paper,we present a technique called reusing-based scheduling (RBS),for on-line scheduling and placement in which configuration reusing is considered as a main characteristic in order to reduce reconfiguration overhead and decrease total execution time of the tasks.Several experiments have been conducted on the proposed algorithm.Obtained results show considerable improvement in overall execution time of the tasks.     

一种可重构资源管理模型及其调度技术

针对多任务操作系统的可重构资源管理,提出了一种管理模型和在线调度算法,具体实现了把任务分配给基于块划分的可重构器件。一方面,可重构器件由一个主CPU控制,主CPU运行在线调度器和放置器;另一方面,可重构器件由具有相同垂直尺寸的固定大小的块构成,但块可以有不同的宽度,目的是为了在资源和任务之间实现更好的匹配;同时在在线调度器和放置器运行两个函数fSPLIT和fSELECT来实现任务在可重构器件上的配置和调度。仿真结果表明,提出的资源管理模型和调度算法不仅能够实现任务集平均响应时间的最小化和有效调度,而且相比于其他调度算法,还能获得更高的资源利用率。