熊　昕　赖国明

1(广州番禺职业技术学院现代教育技术与信息中心　广东 广州 511483) 2(惠州学院信息科学技术学院　广东 惠州 516007)

0　引　言

集成电路的发展已经达到了深亚微米及纳米级别阶段，但仍然遵循着著名的摩尔定律：芯片上晶体管数量每18个月翻一番，且仍将按这个规律所指示的方向推进。为此，单芯片上晶体管的规模达到数亿个，从而其计算能力的提高为嵌入系统带来了根本性变革。首先，嵌入系统的功能越来越强大，系统复杂度也越来越高；其次，IC芯片的集成度越来越高，系统体积也越来越小。嵌入式系统向着微型化方面的发展使得将整个嵌入式系统集成单块芯片上形成所谓的片上系统SoC(System on Chip)。片上系统SoC是指在单个芯片上集成了专用处理器、通用处理器，DSP、共享内存块、专用内存块、I/O部件等多个知识产权(IP)核的复杂系统，其具有更强大的功能、更低的成本、更小的产品体积、更好的可靠性和更灵活的配置，从而成为新一代应用电子技术的核心。片上系统SOC为集成电路技术的应用和集成电路产业发展提供了的广阔市场和全新的发展机遇，是当今大规模集成电路(VLSI)技术的主要发展趋势和发展主流[1]。

今后高端的SoC片内互连的处理核数量都很多，例如Intel实验室已经有80核心的SoC,片内的通信就会成为SoC的主要性能瓶颈，如何解决其高通信需求是当前高端SoC面临的迫切问题，片上网络NoC为解决SoC的通信问题提供了新的有效途径。网络拓扑结构中处理核的相对位置及其之间的连接方式极大地影响着片上网络的时延、功耗等性能指标[2]。网络拓扑结构是网络路由算法设计、缓冲区分配、容错处理等的其他后继相关研究的前提和基础。由于SoC主要是面向特定应用或者少数应用类的，一旦应用通信特征图确定，其所需要的节点间的通信带宽和时延限制就基本确定，因此，片上网络的设计必须利用特定应用的通信特征来定制片上网络的拓扑才能设计出符合特定应用通信特征需求的优化片上网络[3]。近年来，特定应用的拓扑优化得到了许多研究人员的深入研究，Srinivasan[4]提出了一种基于整数线性规划的拓扑综合方法，Murali[5]介绍一种定制可靠和高效的片上网络拓扑结构方法。为了更好地利用特定应用的通信特征信息来定制和优化特定应用片上网络的拓扑结构，必须根据应用的通信特征来优化其拓扑。Leary等[6]提出了基于三级遗传算法的片上网络体系结构设计。本文主要针对其进行改进，提出了一种改进的三级遗传算法来定制特定应用片上网络拓扑结构，相对于Leary等的算法，我们的算法取得了较好的优化效果和运行效率。

1　Leary等的三级遗传算法及不足

2009年，Leary等在IEEE Transactions on Very Large Scale Integration (VLSI) Systems的第17卷第5期中提出了一个三级的遗传算法来解特定应用片上网络拓扑优化问题。该算法以应用通信特征图ACCG、互连部件特性参数和系统平面布局为输入，首先初始化种群个体，计算个体的适应度值，然后不断迭代交叉、变异和选择操作直到满足终止条件为止，并输出最小能耗值和相应的固定路由。该遗传算法采用如图1所示的三层结构。

图1　Leary的三级层次表示图[6]

这三个层次分别是路由器的选择层、节点与路由端口的映射层和通信交通层。其中第一层次的路由器选择层表示从所有可能的路由器集合中选取出一定数量的可用路由器。第二级别表示应用通信特征图中的结点到选中的路由器端口的映射。第三层表示应用通信交通从源点到目的点经过中间路由器端口的可能通信路由路径。但是，他们的方法存在着明显的不足：

(1) 在第二层的节点与路由器端口的映射层，他们对所选的路由器的所有端口进行统一编号，然后把节点与端口之间进行映射来实现节点与路由器连接。由于路由器有多个端口，同一个节点n1与路由器r1的不同端口进行映射就是不同的种群个体。例如，假设路由器r1有5个端口，节点n1与这5端口的映射是5个不同的个体。然而，由于路由器的尺寸远比节点的尺寸小，同一节点映射在同一路由器的不同端口其连接线的长度应该是一样的，所以，可以把它们看作是同一个映射，即节点与路由器的映射，这样，节点n1与路由器r1的映射只需1个个体来表示。

由于遗传算法所有可能的不同个体集合构成了算法的搜索空间，不同个体的数量越多，算法的搜索空间就越大，从而算法的运行时间就越长。此外，一个网络的拓扑结构决定于三个方面：路由器的选择、节点与路由器的连接和路由器与路由器的连接，Leary的方法不仅增加了遗传算法的搜索空间，第三层采用通信交通层也与拓扑的三个方面没有直观的联系。受此启发，我们提出了一种新的三级遗传算法，它的三个层次分别为：路由器选择层、节点与路由器映射层和路由器与路由器映射层。这三个层次不仅直观反映网络拓扑的三个方面，同时也可以有效地减小GA搜索空间，加快仿真速度。

2　改进三级GA的拓扑结构优化技术

网络拓扑优化问题是一个典型的多目标优化问题，它是斯坦纳树的变形，是一个NP难问题[3]。遗传算法GA适合于解这类NP难问题，用GA解NoC拓扑定制问题的流程如图2所示，算法以应用通信特征图ACCG、互连部件特性参数和系统平面布局为输入。算法首先初始化种群个体，计算个体的适应度值，然后不断迭代交叉、变异和选择操作直到满足终止条件为止，并输出最小能耗值。为了有效地应用GA技术，必须定义问题解的染色体有效表示方法，以及选择、交叉及变异的基因操作，这里给出我们的GA算法的相关技术。

图2　GA的流程图

2.1　解染色体串的数据结构

我们的GA技术采用三级层次化的数据结构如图3所示。

图3　层次化个体表示

第一级是路由器选择级别，用来表示在最大数量的路由器中哪些路由器被选择来构成NoC的拓扑结构。第二级的染色体串用来表示哪个节点与哪个路由器相连接，是表示节点与路由器的映射级别。第三级是路由器与路由器的映射级别，用来表示路由器间的相互连接方式，而不同于Leary方法的通信交通量的由路由端口组成的通信路径。

2.1.1路由器选择级(第一级)数据结构

改进的GA技术把路由器选择级别的数据结构表示成一组常量个数的一维二进制数组arstr[maxrouter]，其变量maxrouter是系统中所有可能的最大路由器个数，由于我们假定路由器分配在IP核的四个角落，所以总的最大可用路由器数量是IP核的四倍。arstr数组元素是随机产生的0或者1，第i个元素是1或者0分别表示第i个路由器被选择或者没有被选择来构成网络拓扑，i∈[0..max]内的整数。图3所示的第一层个体的数据结构如图4所示，图中arstr[i]=1表示第i个路由器被选择到网络体系结构中，否则 arstr[i]=0表示未选中。本文中的GA技术保持常数J个arstr个体。所有选择出来的路由器从0开始统一进行编号，为了建立所选择的路由器与原来总的路由器之间的关系，这里我们要定义一个辅助的数据结构routid的一维数组来存储所选路由器在原来总路由器中的编号。

图4　个体染色体的数据结构

2.1.2节点/路由器映射级(第二级)数据结构

第二级个体用染色体nrstr表示节点/路由器映射，整数数组nrstr[nodenum]用来表示节点/路由器的映射，其中nodenum代表ACCG图中IP核的个数。在图3中，节点2，3分别映射到路由器1。由于路由器有多个端口，不同的节点可以映射到同一个路由器，所以，数组nrstr中的元素可以重复，但节点/路由器的映射必须满足一定的合法性条件，这些合法性条件将在下一节中介绍。

2.1.3路由器/路由器映射级别(第三级)数据结构

在第三级别上，我们的GA技术与G.Leary的第三级使用不同的数据结构。我们使用路由器/路由器的映射来决定路由器之间的连接。这里，我们使用二维的二进制矩阵rrstr来表示路由器之间的连接，矩阵rrstr是一个对称矩阵，上三角矩阵元素rrstr[i][j](i

2.2　解表示法的合法性条件

NoC拓扑结构要求满足一些充分必要的合法性条件，下面分别介绍三个级别解表示法的合法性条件。

2.2.1路由器选择的合法性条件

第一级的合法性条件是：

为了保证网络的连通性，避免路由器的选择不当导致成为孤岛，必须满足：

r×p≥n+2×(r-1)

(1)

式中：n为全连通的网络中节点数；r为所选的路由器数；p为每个路由器有端口数。

即：由r个路由器构成一个全连通的网络至少需要用去2×(r-1)个端口。

2.2.2节点/路由器映射级的合法性条件

在第二级别，需满足下列合法性条件：

• 节点与路由器的映射关系是一对一的关系，即一个节点都必须映射到一个路由器，且只能映射给NoC结构中的一个路由器；而路由器与节点的关系是一对多的关系，即一个路由器可以连接到多个节点。

• 如果所选择的路由器数量大于1个，每个路由器至少有一个端口空出来，用于把该路由器与其他路由器相连，以保证网络的连通性。

2.2.3路由器/路由器映射级的合法性条件

本级需满足下列合法性条件：

• 路由器至少必须与另一个路由器相连以保证网络连通性。

• 由于受限于路由器的最大端口数，每个路由器的最大端口数需大于路由器的连接总数。一个路由器的总连接数包含节点与路由器的连接和路由器与路由器的连接。

• 为确保单时钟周期信号的传播，两个相邻接路由器之间的曼哈顿距离需在所允许的通信距离之内。

• 路由器端口的最大带宽限制必须不能违规。

2.3　初始种群的产生和适合度函数

2.3.1初始种群的产生

初始时，改进的GA技术产生J个路由器选择数组arstr，K个节点/路由器映射数组nrstr和L个路由器/路由器映射二维二进制数组rrstr初始种群。对于J个路由器选择级的个体，每个arstr数组都是通过随机地赋值“0”或者“1”给每个数组元素来产生的。如果所产生的染色体数组不符合第一级的合法性，则通过随机地把某个值为“0”的数组元素改变为1，直到满足合法性条件。节点j路由器的染色体nrstr是选择一个节点i，并随机地把它分配给一个选择出来的路由器，把该路由器的编号存储在nrstr[i]中。同样节点/路由器映射必须满足上述的第二级合法性条件。最后，路由器/路由器映射是一个二维对称的二进制数组rrstr，这一级的初始个体是通过随机地赋值“0”或者“1”给矩阵的上三角元素，随后下三角元素赋值为对应上三角元素的值来产生的。如果矩阵元素rrstr[i][j]=1，则意味着路由器i与路由器j间有一条物理链路直接相连，反之，rrstr[i][j]=0则没有直接链路存在。矩阵的主对角元素rrstr[i][i]都被赋值为“0”，表示一个路由器不能通过一条线路连接到自身。矩阵的阶数等于对应的arstr中路由器个数。随机产生的连接矩阵不一定符合第三级的合法性条件，如果违背合法性条件，我们GA调用一个叫adjustment的过程来调整矩阵元素以满足第三级的合法性条件。

2.3.2适应度函数

GA的选择操作是根据适应度函数值来选择最适应的个体来产生下一代种群。我们的GA优化目标是最小化功耗和路由器资源，适应度函数定义如下：

(2)

式中：p是个体所表示的拓扑对所有通信交通所消耗的总能量;r是拓扑中使用的路由器数量;α和β则分别是p和r的权重。一旦个体所对应的拓扑结构临时确定之后，也就是一旦路由器已经选择、节点与路由器的连接和路由器与路由器的连接已经完成，在满足最大带宽限制的前提下，采用Dijkstra最短路径算法，可以对所有通信交通进行路由，因此，每个通信交通的能量消耗能够被计算出来。个体的能耗是ACCG中所有通信交通所消耗能量之和。

对于一个通信交通e从路由器r1流到r2的功耗可以式(3)来计算：

(3)

这里dist(r1，r2)是路由器r1与r2之间的曼哈顿距离。对于某个通信交通，如果两个节点之间没有路径可达，则假定其功耗为无穷大，因此该个体的适应度最小，在选择过程中，该个体就会被淘汰。

2.4　三个级别的遗传基因操作

GA技术要求有选择、交叉和变异三个基因操作。

2.4.1选择操作

根据个体的适应度值从当前种群和新产生的个体中选择指定数量最适应的个体来产生下一代种群，在下一代个体的产生中自动完成。

2.4.2交叉操作

交叉操作是随机地从当前种群中选择两个个体(即双亲)进行交配来产生下一代个体。在我们的GA技术中，我们使用均匀完全交叉操作。

2.4.3变异操作

变异操作随机地对个体中的某些基因执行异向转化。

3　实验结果及讨论

3.1　实验设置

本文以MPEG4[7]，MWD[7]，VOPD[7]，DSP[8]四种多媒体应用标准测试程序来定制不规则拓扑结构，并给出最小的能耗值。所有的处理核的尺寸都是随机生成的，面积大约为1.5×1.5=2.25 mm2，路由器的输入和输出端口的功耗估计分别为328和65.5 nw/Mb/s，而链路的单位功耗为79.6 nW/Mb/s/mm。MPEG4和DSP的应用通信特征图ACCG如图5所示。VOPD，MWD的应用通信特征图如图6所示。

图5　MPEG4[7]，DSP[8]应用通信特征图ACCG

图6　VOPD[7],MWD[7]应用通信特征图ACCG

3.2　实验结果分析

针对上面的标准测试程序，在Windows 7平台上，用Visusal C++6.0进行编程实现，其中遗传算法的各级交叉概率为90%，变异概率为0.5%，各个级别的个体数量均为1 000个，实验的结果如表1所示。本文改进的遗传算法定制NoC拓扑结构时，功耗有一定的改进，虽然相对Leary方法改进不大，平均能耗改进只有3.74%，其主要原因是因为Leary方法已经是较好的优化结果。但是，在仿真时间由309.125秒减少至254.2秒，却有较大的减少，平均提高17.4%，其原因是遗传算法的不同个体的数量越多，算法的搜索空间就越大，从而算法的运行时间就越长。本文的改进方面在遗传算法的搜索空间上有较大的改进，相比Leary方法在搜索空间上有较大的减少，从而减少搜索时间。

表1　实验结果

4　结　语

片上网络(NoC)是将来众核片上系统通信问题的有效解决方案，而特定应用拓扑优化能够充分利用应用的通信特征来定制优化片上网络的拓扑结构。有约束的特定应用片上网络拓扑优化定制是一种NP完全的问题，目前没有有效的优化方法。本文针对Leary[6]等提出了基于三级遗传算法的片上网络体系结构设计中不足进行改进，提出了一种改进的三级遗传算法来优化定制特定应用片上网络拓扑。以MPEG4[7]等四种标准多媒体应用通信特征来测试，实验结果表明本文的方法在仿真时间上有较大的改进，平均提高17.4%。

[1] 郑灵翔. 嵌入式系统设计与应用开发[M]. 北京:北京航空航天大学出版社，2006:1-7.

[2] Hemani A, Jantsch A, Postula A, et al. Network on a Chip: An architecture for billion transistor era[C]// Proceeding of IEEE NorChip Conference, 2000:166-173.

[3] Garey M R, Johnson D S. Computers and intractability: A guide to the theory of NP-completeness[M]. Freeman, 1979:121-130.

[4] Srinivasan K, Chatha K S, Konjevod G. Linear-programming-based techniques for synthesis of Network-on-Chip architectures[J]. IEEE transaction on very large scale integration (VLSI), 2006, 14(4): 407-420.

[5] Murali S. Designing reliable and efficient networks on chips [J]. Lecture Notes in Electrical Engineering, 2009, 34:57-75.

[6] Leary G, Srinivasan K, Mehta K, et al. Design of Network-on-Chip Architectures With a Genetic Algorithm-Based Technique[J]. IEEE Transactions on Very Large Scale Integration Systems, 2009, 17(5):674-687.

[7] Jalabert A, Murali S, Benini L, et al. XpipesCompiler: A tool for instantiating application specific Networks on Chip[C]// Proceedings of Design, Automation and Test in Europe Conference and Exhibition, 2004, 2:884-889.

[8] Murali S, Micheli G D. SUNMAP: A tool for automatic topology selection and generation for NoCs[C]// Proceedings of 41st Design Automation Conference, 2004:914-919.

[9] Zhang Ying, Wu Ning, Ge Fen. Sectional NoC Mapping Scheme Optimized for Testing Time[J]. Lecture Notes in Engineering & Computer Science, 2014, 2213(1):301-314.

[10] Wu J, Dong D, Liao X, et al. Energy-efficient NoC with multi-granularity power optimization[J]. Journal of Supercomputing, 2016, 73(4):1-18.