一种面向部分可重构系统的实时调度算法

针对当前可重构资源模型难以实现或资源利用率低等不足,提出一种新的资源模型。基于此模型,设计一种能够调度周期和非周期任务的混合实时任务调度算法。把周期任务分成若干组,在FPGA上为每组任务预留一个槽。当有非周期任务到达时,预先调度当前忙碌期内的所有周期任务,在保证当前忙碌期内周期任务满足截止期限且不影响下一个忙碌期内周期任务执行的情况下,把非周期任务调度到某个槽内执行。实验结果表明,该算法能够充分利用可重构资源,满足所有接收任务的截止期限。     

可重构系统中的实时任务在线调度与放置算法

有效的任务调度与放置是发挥可重构计算性能优势的重要因素.针对实时任务在二维可重构器件上的在线调度问题,定义了调度算法完全识别的概念,即算法不会拒绝能够成功调度的任务.提出了新的实时在线调度与放置算法,充分利用了任务的时间信息,实现了完全识别的调度.实验表明,与已有的算法相比,新算法显著地改善了调度效果,而运行开销没有明显增加.     

一种基于可重构多FPGA 的任务调度与任务复制方法

在可重构多现场可编程逻辑门阵列（FPGA）系统中,任务调度是一个极其重要的研究方向。参照同构与异构计算领域的调度算法,结合可重构多FPGA计算模型的自身特点,在现有的调度算法的基础上,将任务复制方法引入到可重构多FPGA系统计算领域,如果任务余图最长路经上的父子节点不在同一FPGA上,通过寻找FPGA上的复制空间,提出的算法将父节点尽可能复制在子节点所在的FPGA上,减小了任务之间的通信开销。实验结果表明,对于任务调度有向无环图,提出方法的调度长度优于或等于前人方法的性能下界,而且,FPGA利用率有所提高。     

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

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

一种异构可重构片上系统的实时任务调度算法

动态可重构系统中为新到达的任务实时地安排任务启动时间和放置位置是硬件任务调度算法的关键.硬件任务的调度在很大程度上影响可重构计算系统的性能.提出了一种基于二维资源模型的分组-邻接边在线调度算法,该算法将硬件任务按照长宽比分为垂直任务和水平任务两组分别考虑在可重构资源上的放置位置,同时引入任务邻接边数作为选择合理放置位置的重要指标,可使得硬件任务放置更为紧凑,减少资源碎片,提高调度成功率.对两种硬件任务放置策略进行了对比,结果表明尽可能旱的安排任务启动有利于提升高负载情况下的调度成功率.仿真实验表明,与已有算法相比,该算法具有更高的任条接受率,而运行时开销没有显著增加.     

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

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

可重构系统在线任务预约重调度算法

针对可重构系统的任务调度问题,提出一种基于最小裕度优先策略的在线任务预约重调度算法。该算法在任务预约的基础上,对预约失败的任务和已预约的任务按特定优先策略进行重调度。仿真实验结果显示,在正常负载率区间中,该算法有效降低了任务拒绝率,且运行开销较小。     

基于均衡适应度的云工作流调度算法

针对工作流任务调度优化问题,提出一种云工作流任务调度遗传算法。为了寻找工作流执行时间与执行代价的同步最优解,建立了遗传调度模型。在个体编码方面,采用了一种二维排列编码方法,可以更好地展现工作流任务间的执行次序;综合考虑任务执行代价与最早完成时间两个因素,设计了一种均衡适应度函数;为了丰富种群个体多样性,引入三种遗传交叉操作和两种遗传变异操作,以产生新的个体,增加了最优解的求解概率。通过数值仿真实验,在多个性能指标上对算法进行分析。结果表明,该调度算法能更好地平衡执行代价与调度效率,性能优于同类算法。     

车辆移动云可靠性任务调度

车辆移动性使得移动车辆云中的任务调度可靠性问题变得尤为复杂。针对这一问题,提出一种基于混合整数线性规化最优化方法的云任务调度算法。借助于MapReduce构建车辆云任务的调度模型,并设计一种复杂度更低的启发式调度方法,在有效降低任务执行延时的同时,确保了任务调度的可靠性。通过在网络仿真器NS3中运行城市道路环境下的MapReduce应用,对算法的调度结果进行性能评估。结果表明,与同类的车辆云中的调度方法相比,该算法在作业平均执行时间、作业调度成功率、系统吞吐量及任务执行开销等性能指标上均优于对比算法。     

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

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

可重构资源管理及硬件任务布局的算法研究

可重构系统具有微处理器的灵活性和接近于ASIC的计算速度,可重构硬件的动态部分重构能力能够实现计算和重构操作的重叠,使系统能够动态地改变运行任务,可重构资源管理和硬件任务布局方法是提高可重构系统性能的关键.提出了基于任务上边界计算最大空闲矩形的算法(TT-KAMER),能够有效地管理系统的空闲可重构资源;在此基础上使用FF和启发式BF算法进行硬件任务的布局.实验表明,算法能够有效地实现在线资源分配与任务布局,获得较高的资源利用率.     

Resource management and task partitioning and scheduling on a run-time reconfigurable embedded system

There are many design challenges in the hardware-software co-design approach for performance improvement of data-intensive streaming applications with a general-purpose microprocessor and a hardware accelerator. These design challenges are mainly to prevent hardware area fragmentation to increase resource utilization, to reduce hardware reconfiguration cost and to partition and schedule the tasks between the microprocessor and the hardware accelerator efficiently for performance improvement and power savings of the applications.In this paper a modular and block based hardware configuration architecture named memory-aware run-time reconfigurable embedded system (MARTRES) is proposed for efficient resource management and performance improvement of streaming applications. Subsequently we design a task placement algorithm named hierarchical best fit ascending (HBFA) algorithm to prove that MARTRES configuration architecture is very efficient in increased resource utilization and flexible in task mapping and power savings. The time complexity of HBFA algorithm is reduced to O(n) compared to traditional Best Fit (BF) algorithm’s time complexity of O(n²), when the quality of the placement solution by HBFA is better than that of BF algorithm. Finally we design an efficient task partitioning and scheduling algorithm named balanced partitioned and placement-aware partitioning and scheduling algorithm (BPASA). In BPASA we exploit the temporal parallelism in streaming applications to reduce reconfiguration cost of the hardware, while keeping in mind the required throughput of the output data. We balance the exploitation of spatial parallelism and temporal parallelism in streaming applications by considering the reconfiguration cost vs. the data transfer cost. The scheduler refers to the HBFA placement algorithm to check whether contiguous area on FPGA is available before scheduling the task for HW or for SW.     

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

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

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.     

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

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

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.     

可重构混合任务调度算法

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