基于2D-mesh拓扑分类的NoC映射技术研究

作     者：桑晓丹 

作者单位：解放军信息工程大学 

学位级别：硕士

导师姓名：罗兴国

授予年度：2011年

学科分类：080903[工学-微电子学与固体电子学] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 

主      题：片上网络 映射技术 2D-mesh 映射等价位 架构感知模型 特殊可达性矩阵 混沌遗传算法 

摘      要：片上网络(Network-on-Chip,NoC)映射用于将应用任务映射到实际网络资源,是NoC设计中的重要步骤,直接影响着网络的整体性能。不同的NoC映射结果会对NoC功耗、时延、可靠性以及温度等性能产生很大影响,而不同的映射技术直接决定着映射效果。有关映射技术的研究工作主要存在以下两方面问题:(1)在规则2D-mesh拓扑下,当前映射算法对拓扑的对称性问题考虑不足,导致收敛速度过慢;(2)当规则2D-mesh变为不规则2D-mesh时,传统映射算法无法进行有效映射。因此,本文基于2D-mesh拓扑的分类对NoC映射技术展开研究。 本文在深入分析已有映射算法的基础上,提出了一种规则2D-mesh拓扑下的映射算法;然后,针对不规则2D-mesh拓扑下的映射算法失效问题,对A3MAP架构感知映射模型进行了改进,并在该改进模型的基础上提出了一种混沌遗传映射算法。主要研究内容包括: 1、提出了一种基于规则2D-mesh的快速映射算法(MARM)。该算法提出了映射等价位的概念,利用分支界限及“剪枝原理快速消除映射等价位来提高映射效率。仿真实验表明:MARM同随机映射相比,通信功耗大约节省了41%～61%;同GA算法相比,通信功耗节省比值在4%～60%。并且与随机算法、GA算法相比,该算法获得了较快的收敛速度。 2、提出了一种基于特殊可达性矩阵的架构感知模型(A3MAP-SRM)。该模型把Tile间通信量的等级权重作为可达性矩阵的系数参数,使两者结合成为一个特殊可达性矩阵加入到A3MAP模型的目标函数之中,解决了原有A3MAP模型的总失真度函数误差大和不可达路径处理盲区的问题。仿真实验表明,该模型在规则2D-mesh拓扑方面适用于中大规模通信密集性任务映射;在不规则2D-mesh拓扑方面不仅解决了通信模块不可达的任务映射问题,而且与A3MAP的映射结果相比,该模型在通信功耗方面大约降低了10%。 3、提出了一种基于A3MAP-SRM的混沌遗传映射算法(CGNM)。该算法根据A3MAP-SRM模型属于0-1整数规划问题这一特殊性,通过将混沌搜索算法嵌入到遗传算法中的策略,使之为遗传算法产生新个体、新模式;同时,通过引入幂函数载波技术改善了混沌搜索解空间的遍历性能,提高了群体多样性和搜索效率。仿真实验表明,该算法在通信功耗和收敛速度两方面均较A3MAP-GA算法有所改进,相较A3MAP模型,该算法在A3MAP-SRM模型中可以获得更低的通信功耗。