基于异构CMP的静态任务调度研究

Research on Static Task Scheduling Based on Heterogeneous Chip Multi-processor

现有任务调度算法在选取任务优先级参数时仅仅考虑单一属性,且没有及时处理冗余任务,针对这一问题,提出一种异构CMP中列表与复制优化任务调度算法-HLDOTS算法.该算法首先对任务图中某些特殊的任务进行优化;综合考虑任务的多个属性来为任务分配优先级,构造调度列表;在任务分配阶段,采用基于插入的策略和任务复制技术将当前任务分配到最早执行完成该任务的处理器上;并逐层对调度结果中产生的冗余任务进行处理,将任务分配与冗余任务处理交替进行,避免了冗余任务对处理器资源的浪费,提高了处理器的资源利用率和任务调度效率.采用随机生成图进行模拟实验,实验结果表明,HLDOTS算法较HEFT算法、CPOP算法和HCPFD算法取得了更好的调度性能.

Aiming at the issue that the singleness attribute of task priority parameter selection and redundancy task handled untimely in the existing task scheduling algorithms, this paper proposes a heterogeneous multi-core list and duplication optimization task scheduling algorithm named HLDOTS. This algorithm optimizes certain specific tasks in task graph firstly; Considering multiple attributes of task assigns priorities to the tasks, which builds scheduling list; In the task assignment phase, using a strategy insertion based and task duplication technique assign the current task to processor, which has the earliest execution completion time of task; The algorithm processes redundancy tasks caused by the scheduling result layer by layer, assigning tasks alternates with processing redundancy task, which avoids a waste of processor resources caused by redundancy tasks, this improves processor resource utilization and the efficiency of task scheduling. The simulation experiment uses randomly generated graphs, the experimental result shows that HLDOTS algorithm can achieve better performance than HEFT,CPOP and HCPFD algorithms.