基于关键任务的容错片上网络映射算法研究

摘要

NoC映射算法是片上网络研究的热点内容。目前，半导体工艺特征尺寸的降低以及芯片集成度的提高不断推动着NoC的复杂度和性能的提升，同时对NoC的可靠性映射带来了更大的考验和挑战。为了保障应用程序映射的可靠性，NoC容错技术成为NoC研究中的一个重要方面。本文提出了一个基于关键任务的容错片上网络映射算法FTMA-CTs，该算法不仅能够提高映射过程可靠性，而且还能降低系统总能耗。
　　FTMA-CTs映射算法将映射过程分为虚拟拓扑到物理拓扑的映射阶段和任务图到虚拟拓扑的映射阶段。其中，在虚拟拓扑到物理拓扑的映射阶段，本文采用了匈牙利算法来解决虚拟核到物理核的一对一映射问题。在任务图到虚拟拓扑的映射阶段，首先把基于节点的任务图转化为基于节点和边的加强型任务图，然后根据路径延时和系统延时，找到任务图中的关键路径，进一步找到关键任务。再把带有关键任务的任务图进行分簇，本文采用亲密度传播聚类算法进行分簇。在把分簇之后的任务图映射到虚拟拓扑的过程中，采用改进的分支限界算法，该算法在原有的分支限界算法的基础上增加两个界限，通过这两个界限继续对分支树进行剪枝，从而进一步减少可行解的数目，最终利用这种改进的分支限界算法能够高效快速的得出一个较优的映射方案。
　　最后，对Nirgam仿真器进行改造，进行能耗的仿真评估。通过与Zhang等人提出的退火法和Yue等人提出的基于冗余核的贪婪算法进行比较，分析FTMA-CTs映射算法的性能。结果证明FTMA-CTs映射算法不仅能够提高应用程序映射的可靠性，而且还能降低寻找映射方案的执行时间和系统能耗。

目录

声明

摘要

第1章 绪论

1．1 研究的背景及意义

1．2 NoC映射算法研究现状

1．2．1 国外研究现状

1．2．2 国内研究现状

1．3 论文主要研究内容

1．4 论文组织结构

第2章 NoC映射技术研究

2．1 NoC拓扑结构

2．1．1 物理拓扑结构

2．1．2 虚拟拓扑结构

2．2 NoC的映射和调度

2．3 系统模型和问题形式

2．3．1 任务和拓扑结构模型

2．3．2 能耗模型

2．3．3 延迟模型

2．3．4 问题形式

2．4 本章小结

第3章 容错NoC映射算法研究

3．1 故障核检测方法

3．2 基于匈牙利算法的一对一映射

3．3 基于AP算法的任务图分簇

3．4 FTMA-CTs映射算法总体结构

3．5 基于关键任务的容错NoC映射

3．5．1 虚拟拓扑到物理拓扑的映射

3．5．2 任务图到虚拟拓扑的映射

3．6 本章小结

第4章 算法仿真及结果分析

4．1 实验平台及原理

4．1．1 TGFF生成任务图

4．1．2 Nirgam模拟NoC平台

4．2 实验设计及结果分析

4．2．1 实验环境

4．2．2 实验参数配置

4．2．3 仿真实例

4．3 本章小结

结论

参考文献

攻读硕士学位期间发表的论文及取得的科研成果

致谢