片上网络Noc任务调度研究

论文摘要

随着技术的发展,传统的基于总线的互连方式无法满足系统通信性能的要求,因此出现了基于网络互连的方式。这种互连方式以交换机为节点,在需要路由功能时,可用路由器代替交换机作为节点,以此将设计复用技术应用到了互连结构中,形成了目前的基于网络拓扑结构的片上网络系统。目前的研究在片上网络的任务分配与调度主要是指将通讯任务分配到合适的处理单元,并且尽可能以最佳的方式为这些任务进行排序。同时,目前研究并行任务的调度主要是以带节点权值和边权值的有向无环图即DAG图来表示,DAG调度问题一般为NP问题。因此本文研究各种DAG上面的调度算法。目前的DAG调度算法一般有表调度算法,聚簇调度算法,基于任务复制的调度算法,基于遗传算法、退火算法等。传统的DAG调度算法的目标是使性能最佳,但是在片上网络特别是异构多核的情况下,还需要考虑调度算法对功耗的影响。针对此种情况,本文对粗粒度与细粒度的通信模型情况下分别提出了一种新型的低功耗的调度算法,实验结果表明,与传统的以性能要求为目标的调度算法相比,该算法能节省许多功耗。

论文目录

• 摘要
• ABSTRACT
• 图目录
• 表目录
• 第1章 绪论
• 1.1 课题背景
• 1.1.1 片上网络系统简介
• 1.1.2 片上网路的特点
• 1.1.3 片上网络面临的挑战
• 1.1.4 并行调度模型以及DAG介绍
• 1.2 国内外研究现状
• 1.3 本文论文结构
• 第2章 常见的DAG调度算法
• 2.1 表调度算法
• 2.1.1 基本的表调度算法
• 2.1.2 BNP的表调度算法
• 2.1.3 APN（Arbitrary Processors Networks）的表调度算法
• 2.2 聚簇调度算法
• 2.3 基于任务复制的调度算法
• 2.4 遗传算法和模拟退火算法
• 2.5 冒泡迁移算法
• 第3章 DAG图的搜索算法
• 3.1 A搜索算法
• 3.2 BELLMAN-FORD算法
• 3.3 双向搜索法
• 3.4 广度优先搜索
• 3.5 深度优先搜索
• 第4章 片上网络的低功耗调度算法
• 4.1 引言
• 4.2 数学模型
• 4.3 平台描述
• 4.3.1 路由相关问题
• 4.3.2 架构相关问题
• 4.4 算法描述
• 4.4.1 功耗建模
• 4.4.2 问题描述
• 4.5 粗粒度低功耗调度算法
• 4.6 细粒度低功耗调度算法
• 第5章 结论展望
• 5.1 本文结论
• 5.2 未来研究工作
• 参考文献
• 攻读学位期间发表/录用的学术论文
• 致谢