基于局部搜索策略的多目标芯片调度问题算法研究

发布时间：2020-06-18 16:21

【摘要】：随着科技的发展与新技术的出现,多处理器片上系统(MPSoC)现在越来越多地被用于设计新兴的复杂嵌入式系统。设计人员需要在考虑各种因素的情况下将处理器上的任务以合理的调度顺序分配给相应的处理器进行处理来满足时间以及计算资源和能源资源的限制要求,在提高企业经济效益的同时节约开发成本。众所周知,由于处理器单位时间内的能量消耗和处理器的处理速度正相关,导致时间成本和能源消耗成为两个相互冲突目标,我们需要尽可能同时优化这两个目标。目前,多目标优化问题受到各界研究人员的广泛关注。任务的映射和调度逐渐成为研究人员关注的重要问题之一。为了满足资源匮乏情况下MPSoC系统中完成时间最小化(makespan)和负载(workload)尽可能平衡的要求,本文提出了一个统一的整数规划模型来找到满足条件的任务调度和映射的解决方案。该模型考虑了计算和通信成本,并且能够应用动态电源管理DPM(dynamic power management)进行能源优化。为了尽可能有效逼近最优化问题的帕累托(Pareto)前沿,我们通过对问题进行特定的初始化并集成Pareto局部搜索到多目标进化算法过程中,提出了一种基于进化算法的多目标混合算法(MOHA)。进化算法引用优胜劣汰原理,通过模拟生物进化过程中的基因表达过程,选择优秀的基因片段(目标值更优),过滤掉劣质的基因片段(目标值较劣),最终得到近似最优解。局部搜索则是解决最优化问题的一种启发式算法,由于多目标芯片调度问题是一个NP-hard问题,完备算法的时间复杂度往往不能满足现实生活中的要求,而局部搜索是一种近似算法,它采用时间换精度的思想大大减少算法搜索到无穷接近最优解所需要的时间。在最后的实验阶段,本文选择了现实工业界中几个经典的基准样例对算法进行性能评估和比较实验。在多个基准样例的测试结果中表明,该算法比传统的NSGA-Ⅱ算法更优秀。
【学位授予单位】：东北师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18;TN47
【图文】：

任务图

有限的任务集合，T→N 代表每个任务要完成的工作量，E T×T 用一组 c 值代表一组优先关系，E→N 代表每一组任务之间需要传送的数据量。如果一组任务之间没有明确定义的传送数据量，那么它们的通信消费为 0。如图 3-1（a）所示，一共有四个任务，每一个都被记录所需要完成的工作量。四个任务分别需要完成的工作量是 2，6，8，4。有三条边表明了需要传输数据的数据量，如图所示，任务 2 需要任务 1 传输的数据，数据量为 3，并且它的执行依赖任务 1。同理，任务 2 是任务 4 的前置任务，他们之间需要传输的数据量为 1，任务 3 是任务 4的前置任务，需要传输的数据量为 5。由其下两个映射可以看出，第一个映射中工作负载是均衡的，它的完工时间在第一次迭代和第二次迭代过程中分别是 20和 30。另外一个映射在工作负载不均衡的情况下，完工时间在第一次迭代和第二次迭代过程中分别是 12 和 24。

伪代码,算法编,算法

和最小的工作量，有：= （21）工作量距离越小，在极端的情况下的差异较小，相比于工作距离大的配置更优秀。在上面的例子中，我们有 = 6和 = 7。所以第一种配置比第二种优秀。3.3 多目标混合算法为了获得大规模系统的帕累托最优前沿解集，我们基于 NSGA-II 算法结合局部搜索算法提出了多目标混合算法（MOHA），在初始化和演化过程中具有与目标相关启发式扩展。图 3-2(a)显示了映射和调度问题的染色体编码。每个染色体都包含一组映射任务和分配的处理器的计划执行顺序，这些顺序与一般用于映射优化的常规编码不同。因此，我们需要额外的指针来分离属于各个处理器的任务。

【参考文献】