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

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

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

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

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

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

可重构混合任务调度算法

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

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

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

可重构混合任务调度算法

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

可重构计算的硬件任务调度算法

提出一种可以减少数据传输量的调度算法RDMS。通过在调度过程中综合考虑任务中数据的关联性、硬件任务的资源利用率及内部任务之间的通信量,采用动态编程方法,减少微处理器和FPGA可重构协处理器之间的通信量及FPGA可重构资源的消耗。实验结果表明,RDMS能提高映射在FPGA器件上硬件任务的整体性能,有效降低通信开销和重构开销。     

基于离散时间距的在线可重构任务调度算法

任务调度是影响动态可重构系统性能的重要因素.针对现有预约算法中由于维护预约资源逻辑单元信息而带来系统额外开销大、任务调度自私性等问题,提出一种基于离散时间距的非预约调度算法.算法的特点在于通过任务紧迫度和时间距信息能够动态更新任务优先级和设置任务的启动时间,从而有效避免了复杂的系统开销和任务调度的自私性.实验表明,该算法能提高任务的调度成功率,而运行时间开销没有明显增加.     

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

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

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

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