论文部分内容阅读
在以往的片上系统(System-on-Chip,SoC)设计中,人们经常使用总线结构和点对点结构两种方式连接处理器。然而,面对着系统中处理器数目日益增多的情况,这两种互连方式也逐渐暴露出一些缺点,导致在SoC设计中出现了可扩展性差、资源可重用性弱等问题。片上网络(Network-on-Chip,NoC)的出现成功地解决了当前SoC系统设计中遇到的问题。目前,NoC的研究方向有很多,如硬件微结构的设计、数据通信协议、数据流控制技术、任务调度问题等。近年来,任务调度问题已经成为了学术界的研究热点。在过去的几十年里,任务调度问题得到了广泛研究,一个好的调度算法对提高NoC系统性能发挥着重要作用。一个好的调度算法能够充分利用片上资源,合理安排任务执行顺序,实现并行计算,能够尽量缩小调度时长,从而提高系统的工作效率。同时,一个好的调度方案能够尽量缩小任务之间数据传输的距离,从而降低系统中数据传输所消耗的能量,这对于提高系统性能十分重要。此外,一个好的调度算法可以优化多种性能指标,如处理器的负载均衡,处理器芯片的热管理等。本文将研究NoC上任务调度问题,并且重点针对有向无环图(Directed Acyclic Graph,DAG)任务集的调度算法进行探究,主要工作内容如下:1.对基于启发式的调度算法进行了分析,包括遗传调度算法、离散粒子群调度算法以及模拟退火调度算法,并且通过仿真对三种算法进行了对比。2.在人工免疫系统的基础上进行改进,并且引入毗邻结构(Neighborhood Structure,NS)技术,提出了自适应人工免疫算法(ADaptive Immune Algorithm,ADIA)算法,通过仿真验证了该算法提升了系统调度性能。3.在NoC任务调度问题研究中,本文引入了数据包络分析方法。针对四种性能指标,构建了数据包络分析中的决策单元,并在此基础上提出了基于BCC参考频数的调度方案的评估方法。然后,将离散粒子群算法与此评估方法相结合,提出了BCC-DPSO算法,并且仿真证明了在对比的五种算法中该算法输出的调度方案效率最高。