高级检索

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

    A Boundary-Table-Based Algorithm for Reconfigurable Resource Management and Hardware Task Scheduling

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

       

      Abstract: Reconfigurable computing (RC) is a kind of computation schema with hardware efficiency and software flexibility. The management of the reconfigurable resources and the scheduling of the hardware tasks are two critical factors that are concerned closely with the performance of RC. Focusing on the scheduling of hardware tasks in linear dimension reconfigurable device, one method based on boundary table (BT) is proposed for reconfigurable resource management by using the BT data structure to record the regional boundaries and their location relations in R-T coordinates. On the basis of the method, a new algorithm BT-P (boundary table placement) is also proposed to achieve the scheduling and placement of hardware tasks. By utilizing the weighted overlapping boundary length as the evaluation function and combining it with the reconfigurable resource management method, the proposed scheduling algorithm can realize optimization in a smaller runtime overhead way. The simulation results show that, compared with the stuffing algorithm, the proposed algorithm can effectively increase the chip utilization by 5% to 11% with the change of the load rate and lower rejection rate of the tasks by 9% to 11% with the change of load rate and the relaxation factor. The average time overhead of each task in scheduling and placement is between 2-4 microseconds.

       

    /

    返回文章
    返回