片上网络多目标映射算法设计与研究

发布时间：2020-06-25 00:52

【摘要】：在摩尔定律的指导下,半导体工艺节点不断向前推进,集成电路设计产业高速发展,单芯片上集成的IP核数量不断增多。传统的总线互连方式在扩展性、兼容性、通信速度和能耗等方面已经无法满足芯片中IP核的互连需求。片上网络技术借鉴了分布式设计和OSI通信模型的思想并将其结合,应用在SoC互连技术中,有效的提高了IP核之间的通信效率、扩展性和兼容性。本文对片上网络的多目标映射、超多目标映射、拓扑结构、路由算法和路由器微架构等技术进行了研究。分别针对片上网络多目标映射算法和超多目标映射算法进行了设计与实现。本文分析了NSGA2在求解NoC多目标映射问题时存在的缺陷,针对NoC多目标映射问题对NSGA2进行优化后提出了RNSGA2算法。RNSGA2采用了基于位置的编码方式,通过单点交叉进行全局搜索,通过三种变异方式进行局部搜索。RNSGA2保留了NSGA2中的快速非支配排序、拥挤距离计算和拥挤比较算子并在算法主循环中加入了去重算子。去重算子将第一非支配解集中的冗余解求出后进行多点交叉再放入下代种群中参与遗传。RNSGA2有两个特点:一是可以同时对两个目标函数的映射问题进行求解,二是去除了NoC映射问题解集中的冗余解并保证种群数目不变和优秀基因的保留。本文使用MATLAB对RNSGA2进行了建模仿真,主要包括快速非支配排序、拥挤比较算子和去重算子等模块。本文将NSGA3引入到NoC超多目标映射问题中,结合NoC的结构特性对NSGA3进行优化后得到了RNSGA3算法。RNSGA3是在RNSGA2的基础上加入了参考点和参考向量,并对所有个体的适应值进行了归一化处理再通过参考向量关联的个体数目进行选择。RNSGA3的主要特点有两个:一是可以将搜索空间用参考向量划分之后,降低搜索范围,同时对三个及三个以上的超多目标映射问题进行求解,二是有效去除了NoC映射问题解集中的冗余解并保证种群数目不变和优秀基因的保留。本文使用MATLAB对RNSGA3进行了建模仿真,主要包括参考点确定、适应度值归一化、个体关联参考点和选择算子等模块。本文还用可综合的Verilog HDL设计了一个基于2DMesh的拓扑结构和一个时钟精确的硬件仿真平台。片上网络采用了2DMesh拓扑结构、XY路由算法、虫孔交换和ACK-NACK流控策略。评估平台设计了软件接口,将片上网络映射问题的解输入到硬件平台进行仿真,并且可以输出片上网络的性能报告。仿真报告显示,在均匀、转置1、转置2、反转、混洗和蝶形六种流量模式下,当求解NoC多目标映射问题时,RNSGA2求出的解的饱和吞吐率分别高于NSGA2的解11.76%、23.26%、50%、48.65%、41.67%和33.33%,网络性能平均提升了35.1%,当求解NoC超多目标映射问题时RNSGA3求出的解的饱和吞吐率分别高于RNSGA2的解57.7%、46.67%、20.83%、52.78%、59.38%和39.53%,网络性能平均提升了43.72%。
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TN47
【图文】：

示意图,参考点,示意图,目标函数

西安电子科技大学硕士学位论文42图4.1 参考点示意图4.3.2 适应度值归一化上一步中提到将参考点均匀的分配到一个归一化的参考平面上。这一步做的工作就是将种群中的所有个体的适应度值都归一化这个参考平面。由于种群中所有个体的适应度值分布在原坐标系中，归一化所有个体意味着将坐标系平移。首先，确定理想点。计算 St中的所有个体的所有目标函数值，并求出每个目标函数的最小值 =( ) ，在搜索空间由( )这些最小值就是理想点的坐标。再如公式（4-2）所示，将每个个体的目标函数值与这个最小值相减得到。然后再通过 ASF 公式求出所有目标函数的最大值 i，其中 i的取值定义为固定一个维度，该维度的 i设为 1，其他维度的 i设为一个很小的值。最后将所有个体的目标函数值与其相除如公式（4-4）所示

对比图,吞吐率,对比图

从图 5.7 和图 5.8 中可以看出在六种抽象流量模型作为输入时，RNSGA2 求解出来的前沿曲线相比于 NSGA2 更加贴近原点和坐标轴，这表示 RNSGA2 在求解多目标映射优化问题时的收敛性优于 NSGA2，通过 RNSGA2 映射后的片上网络系统将具有更低的能耗和更均匀的负载。（3）硬件仿真片上网络的饱和吞吐率指的是当网络注入率增加到某一点时，网络的吞吐率不再随之线性增加，这一点的吞吐率为片上网络的饱和吞吐率。饱和吞吐率可以反映网络的处理拥塞的能力以及网络负载分布的均匀性。饱和吞吐率越高，表示网络处理拥塞的能力越强，网络的负载分布的越均匀。在抽象输入模型的两目标映射问题的解集中，分别取出 NSGA2、RNSGA2 和RNSGA3 中的最小负载解和最小能耗解，一共六个解，每个解代表一种连接方式。用时钟精确的硬件仿真平台中的数据产生器，按照六个解的连接方式和抽象输入模型的IP 核的通信关系，产生对应的流量，作为平台的输入，以 5.3.1 设计的 64 点 2DMesh片上网络为载体，运行后得出对应网络的饱和吞吐量的报告，如图 5.9 所示。

【参考文献】