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

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

基于双仲裁机制和田口正交法的猫群优化任务调度算法

针对异构计算系统任务调度过程中通信冲突以及算法运行时间的问题,该文提出一种基于双仲裁机制和田口正交法的猫群优化任务调度算法。首先利用双仲裁机制对任务资源进行管理,动态判决任务的分配,有效避免通信冲突,再将田口正交法应用到猫群优化过程的跟踪模式中,降低算法运行时间,提高解的质量。实验结果表明,该算法运行速度明显高于其他算法至少约10%,算法在处理大量任务时的并行化效果最优,在异构环境中也体现出其相当大的优势。