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

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

动态可重构片上系统的任务在线调度算法

针对动态可重构系统中为新到达任务安排任务启动时间和放置位置的问题,提出一种基于顶点链表的Look-aheadest算法。将任务调度的时间作为时间维,通过已到达任务与已放置任务在三维空间的邻接面构建代价函数,获取具有最大代价函数值的放置位置和启动时间,使硬件任务放置更为紧凑,提高调度成功率。仿真结果表明,在可接受的运行开销内,该算法能有效提高任务接受率。     

基于可重构系统的亚可抢占任务调度算法

针对目前在线调度算法忽略预留任务特殊性的问题,基于现有的放置策略,定义并证明一个可靠的基于最大邻接边数的放置策略。提出一种基于亚可抢占性的任务调度算法,即剥夺预留任务所占用的可重构资源再进行统一离线调度。实验表明,与已有算法相比,该算法具有更高的任务接受率和芯片利用率,且并未明显增加运行时的开销。     

可重构系统中基于空间邻接度的实时任务放置算法*

本文提出了一种基于三维空间邻接度的放置算法,该算法将硬件任务按照长、宽及调度时间构成一个三维资源模型,将每个硬件任务看成是一个空间块。首先对可重构资源进行编码,到达的任务总是通过某个顶点依附另一个任务的边界被放置,确定候选的放置顶点;然后以到达任务与已放置在三维空间的邻接度为代价函数,选择代价函数值最大的顶点放置任务,从而使得到达任务与已放置任务在三维空间接触的邻接面最大。可使任务安排得更紧凑,减小对系统资源的浪费,提高芯片利用率。     

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

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

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

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

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

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

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

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

面向异质结构的可重构任务在线布局算法

基于同质结构模型的可重构任务布局算法和内部资源多样的可重构器件不相适应,不利于实际运用.针对BlockRAM等静态单元在器件上的分布对硬件任务存在位置约束的问题,建立了异质结构的器件和硬件任务模型,并提出一种基于相对任务覆盖度的在线布局算法.通过为布局任务等待队列设立滑动窗口,根据窗内任务集合对器件空闲单元的相对任务覆盖度选择当前任务的放置位置,兼顾后续任务的布局需求,从而提高了整体布局效率.实验结果表明,该算法能取得较低的任务平均等待时间和较高的器件利用率,优于First Fit算法.     

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

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