引入增强型混沌机制的2D Mesh片上网络映射算法研究

摘要

片上网络(NoC)是一种有别于总线架构的多核系统解决方案，用以解决传统片上系统(SoC)由于集成资源越来越多所造成的总线竞争问题。低功耗和低延时是NoC系统设计中的关键问题，本文以此作为切入点对NoC设计中系统层级的关键步骤映射问题进行了研究。文章对功耗和延时多约束条件进行了单约束转换，建立了统一的评估函数，并设计实现了一种用于搜索功耗-延时受限条件下最优映射方案的高效算法。
　　基于2D Mesh结构的NoC平台具有诸多优点，已被广泛应用于NoC关键问题的研究中，本文同样采用这种拓扑结构进行讨论。在分析了NoC架构的功耗和延时组成之后，结合2D Mesh的结构特征，本文提出了与任务规模、任务间通信量和传输路径长度相关的功耗和延时模型。在此基础上，给出了功耗-延时约束下的NoC映射问题的数学描述，该数学描述不仅适用于2D Mesh结构，也可延伸应用于其他的拓朴结构中。
　　NoC映射已被证明为属于NP-Complete问题，对于较大规模的问题直接求解已超过现有计算能力，为此，在这一研究领域多采用启发式算法来搜索能满足工程要求的映射方案。在对一系列启发式算法进行了总结之后，结合NoC映射的特点，并不是所有的算法都适用于解决这一问题。在进行了广泛的对比之后，选取了依照概率进行二次优化的人工蜂群算法作为本文研究的基本算法。在对原算法进行了离散化设计和特点分析之后，针对算法原有的缺陷进行了改造，提出了引入增强型混沌机制的人工蜂群算法，保留了原算法概念简单、易于实施的优点，并且，针对NoC映射问题具有较少迭代次数内优化效果明显、不易得到早熟优化结果的特点，十分适用于解决NoC映射这种离散解空间的搜索问题。
　　最后经过一系列的仿真对比，在可行性、搜索性能和质量、针对原有缺陷的改进等方面对算法进行了验证，仿真证明，本文提出的引入增强型混沌机制的人工蜂群算法是一种高效解决NoC映射问题的算法。

目录

封面

声明

中文摘要

英文摘要

目录

缩略词表

第一章绪论

1.1研究背景

1.2 FNoC研究热点与现状

1.3本文的结构与安排

第二章片上网络低功耗和低延时研究

2.1片上网络功耗分析

2.2片上网络延时分析

2.3 NoC拓扑结构和映射

2.4本章总结

第三章功耗-延时约束下的NoC映射问题

3.1 NoC映射描述

3.2约束条件描述

3.3多目标约束规划

3.4功耗-延时约束下的NoC映射

3.5本章总结

第四章引入增强型混沌机制的映射优化算法研究

4.1人工蜂群算法(Article Bee Colony Algorithem,ABC)

4.2离散人工蜂群算法

4.3增强型混沌机制

4.4引入增强型混沌机制后的算法实现步骤

4.5本章总结

第五章仿真与性能分析

5.1算法可行性验证

5.2算法性能验证

5.3增强型混沌机制性能验证

5.4本章总结

第六章总结与展望

6.1总结

6.2展望

致谢

参考文献

攻硕期间取得的研究成果