负载自适应的异构MPSoC任务调度算法研究

摘要

In heterogeneous MPSoC,the parallel tasks were dispatched to each cores by task scheduling algorithm.Therefore,the performance of heterogeneous MPSoC directly was affected by task scheduling algorithm.A novel task scheduling algorithm with load-adaptive capability was proposed.In order to reduce the communication overheads,the algorithm divided task-set into task-subsets based on core types and tasks dependencies.Taking into the account of the cores load,then weighted bipartite graph was then created by tasksubsets,cores and the execution efficiency of the task-subsets on each core.Finally,task-subsets were dispatched to appropriate load cores by finding a maximum weight matching in the weighted bipartite graph.In this way,the average scheduling length of task-set was reduced and the utilization of cores was improved,which jointly improved the performance of the heterogeneous MPSoC.Under the simulation scenarios with different number of tasks,maximum number of predecessors,number of core types,and number of cores,the proposed algorithm was quantitatively analyzed in terms of the average scheduling length of task-set and the utilization of the cores.The results showed that the proposed algorithm could effectively reduce the average scheduling length of task-set,and improved the utilization of heterogeneous MPSoC cores while achieving-adaptive loading.%在异构MPSoC中,并行任务通过调度算法被分配到各个处理器核上运行,因而任务调度算法的优劣将直接影响异构MPSoC的应用性能.根据处理器核类型和任务间依赖关系,以减小任务间通信开销为目标,提出一种具备负载自适应能力的异构MPSoC任务调度算法.首先,将待调度任务集划分为多个并行任务子集;其次,在考虑处理器核负载的基础上,根据并行任务子集集合、处理器核集合及任务子集在各个核上的执行效率生成赋权二部图;最后,利用赋权二部图最大权匹配方法,将并行任务子集合理地调度到负载适应的处理器核上运行,以降低任务集的平均调度长度,并提高处理器核利用率,从而实现异构MPSoC应用性能的提升.仿真实验在不同的任务总数、任务最大前驱数、核类型、核数量的应用场景下,通过任务集平均调度长度、处理器核利用率两项指标对提出算法进行了定量分析.结果表明,提出算法能有效降低任务集平均调度长度,在实现负载自适应的同时提高异构MPSoC处理器核的利用率.