片上网络下智能化静态任务调度算法研究

发布时间：2024-02-27 19:45

　　在多核技术的发展过程中,如何优化任务调度问题,提升多核并行计算能力一直是人们关注的重点问题。在传统的任务调度问题研究中,诸如任务复制、任务聚簇、列表调度等传统方法,往往不能完全反映解空间的构成情况,很难从可能的调度解中一次性获得较好的调度结果,因此针对此类问题的搜索算法成为这方面研究的主要方向。本文以智能搜索算法中的遗传算法作为搜索最优调度解的方法,设计了基于全局列表和聚簇-列表混合的两种搜索算法GLPGA和CLGA。GLPGA算法使用并行遗传算法中的岛式模型,使用不同遗传算子并行搜索全局调度列表,通过迁移的方式,扩大较优解空间的搜索范围;CLGA算法使用聚簇和列表调度相结合的方式,求解任务到计算单元较优分配方式,通过全局任务列表确定各簇中任务的执行优先级,并使用一种自适应收敛判断标志主动结束搜索过程的方法寻找最优解。在多核系统模型上,本文采用了基于片上网络通讯架构中2D-Mesh结构的多核模型,对任务处理中通讯过程进行行为级建模。算法使用大量随机静态任务图在2D-mesh结构模型下模拟调度结果,测试表明,算法在片上的规范化调度长度在低于1.9,并行度加速比Speedup可达3.9,具...

【文章页数】：59 页

【学位级别】：硕士

【部分图文】：

图1.1任务图G1Fig1.1TaskGraphG1

值表示任务的计算开销和通讯量，可以使用集合G=V,E,W,C来完全概括一张任务图。其中V=Ti是所有任务的集合，Ti表示单个任务;E=ei,j是任务之间驱动关系的集合，ei,j表示任务Ti是任务Tj的前驱任务(pred_task)，而任务Tj是任务Ti的后继任务(succ_tas....

图2.2全互联多核模型

第三章NoC下基于遗传算法的静态任务调度方案112.2任务调度算法的多核模型全互联模型是现有的调度算法大量使用的一种多核模型，如图2.2所示。在这种多核模型下，每个计算单元都有互相连接的通路，不同计算单元间的通讯可独立进行，互不干扰。全互联模型完全消除了通讯中的拥堵和等待，是通讯....

图4.1GLPGA算法流程

第四章NoC下基于遗传算法的静态任务调度算法26图4.1GLPGA算法流程Fig4.1GLPGAalgorithmflow4.1.2GLPGA算法的编码GLPGA算法的优化目标是寻找到更为合理的任务列表，使得在任务调度过程中，处于关键位置的任务能够尽可能优先被调度，提高任务并行性....

图4.4SPX算子Fig4.4SPXoperator

第四章NoC下基于遗传算法的静态任务调度算法274.1.3GLPGA算法的遗传算子遗传算子一般由突变算子和交叉算子两种构成。通过突变算子可以快速产生丰富的新基因型，通常作用于一条基因上；交叉算子能够实现两条基因对应位置上片段的交换，可以用于整合不同的基因特征。GLPGA算法是一种....

本文编号：3912882