应用于片上网络系统的调度算法的研究

摘要

在以往的片上系统(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算法,并且仿真证明了在对比的五种算法中该算法输出的调度方案效率最高。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1研究背景与意义

1.2研究现状与发展趋势

1.3本文研究工作及内容安排

第二章 片上网络系统任务调度模型

2.1基于片上网络的硬件模型

2.2片上网络调度问题建模

2.3任务调度算法的优化目标

2.4本章总结

第三章 面向DAG任务集的调度算法研究

3.1应用于片上网络系统的启发式调度算法

3.2基于人工免疫系统的任务调度算法研究

3.3本章总结

第四章 基于BCC参考频数的调度方案的评估方法以及调度算法设计

4.1数据包络分析方法

4.2基于BCC模型参考频数的调度方案评估方法

4.3基于BCC参考频数评估方法的调度算法设计

4.4仿真结果与分析

4.5本章总结

第五章 总结与展望

5.1本文工作总结

5.2未来工作展望

致谢

参考文献

个人简历及攻读硕士学位期间的学术成果