• 面向实时与智能融合系统的列表调度算法研究

    Research on list scheduling algorithm for real-time and intelligent integrated systems

    • 针对实时与智能融合系统的多处理器任务调度问题,提出两种启发式列表调度算法——TB-LST及其改进算法TB-PLST。所提算法充分利用任务周期性特征以提升调度性能,均包含三个阶段。在时间节点添加阶段,TB-LST与TB-PLST通过引入时间节点,将任务的到达时刻属性转化为任务间的依赖约束。在优先级计算阶段,为合理地利用任务前驱信息,TB-LST与TB-PLST分别采用向下秩及平均反向乐观成本作为任务优先级。在处理器选择阶段,TB-LST以最晚开始时刻为决策依据,TB-PLST则在TB-LST基础上引入反向乐观成本表,并采用贪心策略最小化任务集乐观完工时长。复杂度分析表明:两种算法的时间复杂度与同类算法相当。基于随机生成图和实际应用图的实验结果表明:TB-LST与TB-PLST在完工时长、加速比及更优调度方案出现频率等指标上优于IPPTS、HEFT、CPOP、PEFT等主流列表调度算法。

       

      Abstract: To address the multiprocessor task scheduling problem in real-time and intelligent integrated systems, this paper proposes two heuristic list scheduling algorithms: TB-LST and its improved variant TB-PLST. Both algorithms fully exploit the periodic characteristics of tasks to improve scheduling performance and consist of three phases. In the phase of adding time nodes, TB-LST and TB-PLST introduce time nodes to convert the arrival time attributes into dependency constraints between tasks. In the priority calculation phase, to rationally utilize predecessor tasks' information, TB-LST employs the downward rank while TB-PLST adopts the average reverse optimistic cost as task priorities. In the processor selection phase, TB-LST uses the Latest Start Time (LST) as the decision criterion for processor selection. Building upon TB-LST, TB-PLST introduces Reverse Optimistic Cost Table (ROCT) and employs a greedy strategy to minimize the optimistic makespan of the task set. Complexity analysis demonstrates that the time complexities of the two proposed algorithms are comparable to those of state-of-the-art algorithms in the same category. Experimental results on both randomly generated graphs and real-world application graphs demonstrate that TB-LST and TB-PLST outperform mainstream list scheduling algorithms, including IPPTS, HEFT, CPOP, and PEFT, in terms of makespan, speedup ratio, and the frequency of yielding superior schedules.

       

    /

    返回文章
    返回