基于改进量子遗传算法的片上网络多目标映射技术

张保岗 韩国栋 汤先拓

(信息工程大学 河南 郑州 450002)

0 引 言

片上系统(System on Chip，SoC)随着超大规模集成电路的快速发展也在不断改进，内部总线结构的通信系统早已经不能满足需要，片上网络[2](Network on Chip，NoC)逐渐成为SoC内部通信系统的主流设计[1]。随着单位芯片上处理单元(Processing elements，PE)集成数量越来越多，在快速高效低时延和稳定性上对NoC的要求也越来越高，能耗、低时延和稳定性也逐渐成为限制芯片发展的重要因素。NoC发展迅速，极大地推进了芯片的发展，其能耗和时延是SoC研究设计最重要的指标。片上网络映射作为NoC设计的重要一维，其低功耗和低时延的优化设计实现影响着整个片上网络性能表现[3]。

如何在系统条件约束下，在现有NoC拓扑结构和路由的基础上，将任务节点按照一定规则有效地映射到片上网络各个处理单元上，尽可能减少总的信息交互功耗并在较低的时延内实现是NoC技术研究的一个热点。随着芯片PE数量的增加，需要处理的应用越来越多也越复杂，传统的遍历比较穷举求最优解的方法早已经不适合，目前智能启发式算法在该领域逐步展现其优越性和实用性，也是近年来NoC映射技术研究的热点。

1 相关工作

基于启发式算法的NoC映射技术有很多，在低功耗和多目标方面的相关研究成果也有很多，如文献[4]提出一种基于混合量子遗传算法的新型片上低功耗映射方法，结合自适应旋转角度调整策略，量子比特交叉变异操作和群体突变思想，并在每次迭代中选择具有一定概率的初始解，以防止算法停滞。文献[5]利用任务节点通信量大小划分优先级，得到若干较优初始解集；利用离散粒子群算法的快速搜索能力迅速靠近最优解；利用遗传操作中的选择和变异防止算法掉入局部较优解陷阱，以较少的迭代次数完成最优解的寻找。文献[6]结合了禁忌搜索，主要优化离散粒子群，用禁忌列表防止群粒子重复搜索，使得NoC的总体通信延迟和能耗最小化。文献[7]提出一种优化快速最近邻启发算法ONMAP，最小化NoC通信消耗并可以映射实时嵌入式应用程序，某种程度上实现了动态映射效果。文献[8]提出了一种新的基于遗传的超启发式算法作为核心算法，由于该算法可以在映射过程中自动选择合适的算子，因此可以显著提高收敛速度并表现出优异的稳定性，用于共同优化片上网络的能耗和通信延迟。

上述有关研究成果对NoC低功耗低时延等多目标映射方面有很大的推进作用，但依然有可优化的空间，大多算法都是在通信带宽满足需要不会出现拥堵现象的情况下实现的。随着人们对任务功能需求的提高，NoC部分节点链路很可能会出现拥堵。本文在考虑拥堵的情况下设计多目标评估模型，在充分理解量子遗传算法(Quantum Genetic Algorithm，QGA)优缺点的基础上[9]，结合应用任务和2D Mesh拓扑结构NoC的特点，设计一种改进的量子遗传算法(Modified Quantum Genetic Algorithm，MQGA)来实现NoC低功耗低时延等多目标映射。

2 问题定义和模型描述

2.1 问题定义

定义1应用任务图(Application Task Graph，ATG)如图1(a)所示，它是一个带通信权重的有向图。该应用有8个任务节点，有10条相关链路，含有数字的圆圈代表相应的任务节点ti，从任务节点ti到tj的通信量记为Vti,t2，图中Vt1,t2=40，方向从t1到t2。

定义2结构特征图(Architecture Characteristic Graph，ARCG)如图1(b)所示，是由各个带处理单元的交换节点相互连接，可以实现双向通信的有向图。图1(b)为典型的3×3的Mesh拓扑结构，含有数字的圆圈代表相关交换节点si，每个交换节点都有一个处理单元pi与之对应。两个处理单元pi、pj之间的曼哈顿距离为Mpi,pj，对于Mesh结构一般为两个资源节点所经历最少交换节点数减1。

(a) 应用任务图ATG (b) 结构特征图ARCG图1 映射流程图

2.2 NoC映射

片上网络映射就是将给定的ATG，按一定的顺序分配到ARCG中，任务节点与处理单元一一对应，为处理单元通过NoC完成相应的处理任务做准备。映射结果要正确执行，需要保证结构特征图的处理节点数量大于任务图中的任务节点数，即：

Size(ATG)≤Size(ARCG)

(1)

任务节点数量为m的ATG要映射到n×n的2D Mesh上，需要满足m≤n2。m个任务节点参与映射就有n2！/(n2-m)！个映射结果，合理的映射结果可以更好地利用现有处理资源来完成相应的应用任务，比如快速、低功耗等。如何找到一个较好的低功耗低时延映射结果是本文所要解决的主要问题。

2.3 功耗模型

片上网络功耗模型中单位比特数据在两个相邻处理单元之间传递消耗的能量Ebit为：

Ebit=ESbit+EBbit+EWbit+ELbit

(2)

式中：ESbit为单位比特在交换节点的能量消耗；EBbit、EWbit为单位比特在缓存区和处理单元与相应交换节点之间链路消耗的能量；ELbit是单位比特在两个处理单元之间链路传输消耗的能量。由于EBbit、EWbit远远小于ESbit和ELbit，所以公式可以简化为：

Ebit=ESbit+ELbit

(3)

因此，单位比特从处理单元pi到pj所消耗的能量为：

(4)

对于n×n规则2D Mesh拓扑结构的NoC来说，令N=n×n，则任务节点数为m的任务图映射到结构特征图后所消耗的总能耗ENoC为：

(5)

由功耗模型可知，任务节点映射到的处理节点不同，最终完成任务需要消耗的能耗也不尽相同。由式(4)-式(5)可知，要减少片上网络的总功耗，关键在于降低映射结果的总通信权重的曼哈顿距离。

2.4 时延模型

映射后处理应用程序所需时间如下[5]：

(6)

式中：TL、TS分别为单位比特数据在无阻塞情况下，流经单位链路和单个交换节点所需要的时间；TW为链路有阻塞时的总时间延迟。从式(6)可看出，映射完成后NoC的时间消耗一方面与总的通信曼哈顿距离有关，另一方面受传递路径阻塞延迟TW的影响。阻塞出现一般为某些链路和交换节点可以提供的带宽不能满足需要。为减少阻塞，需要通信链路负载均衡，故TW可以用链路平均负载方差来衡量：

(7)

式中：Fi,Fj为链路i、j的负载量；L为NoC总链路数(两个相邻交换节点之间的链路为一个单位链路)，且FNoC越大TW亦越大。NoC的总延时和负载方差之间的关系为：

TW=FNoC×b

(8)

式中：b视为某一常数。

2.5 多目标优化模型

由线性加权和法得多目标优化函数为:

min{a×TNoC×c+(1-a)×ENoC}

(9)

式中：a为线性加权系数，取0～1之间任一实数，为1时只考虑时延；为0时只考虑能耗。c为某个常数，为了更好地与ENoC融合便于进行量化比较，c值可以设为通信带宽。通过NoC映射的功耗和时耗公式可以看到，TNoC在无阻塞时的时间消耗和能耗成正比，执行一个应用能耗越低则耗时也较短；有阻塞时时间消耗就和能耗成反比。所以，要想获得时间能耗等的多目标优化，就需要负载均衡防止拥塞的情况下尽可能降低功耗，通过负载均衡也可以减少NoC通信热点的出现，提高通信可靠性稳定性。

3 基于改进量子遗传算法的映射技术

量子遗传算法具有适应性强、种群规模小、种群多样性、强大的全局搜索能力以及具备较强的勘探能力等特点，在很多领域得到广泛的应用。

3.1 解结构

如图1中ARCG结构是一个典型的3×3 Mesh的NoC，本文只考虑2D Mesh结构的NoC，n×n的Mesh结构有n2个处理单元，每个处理单元在NoC中位置不同，分别有2、3、4条物理链路将各个处理单元连接起来，实现相互之间的通信。对于量子遗传算法，每个种群个体都代表一个映射结果。

将2D Mesh中的处理单元从左到右、从上至下进行升序排序，如图2所示，从P1到P9，每个处理单元都有一个唯一的数字编号，对于图中3×3 Mesh结构的，最大编号为9。将图1中的任务节点映射到该NoC中，由于任务节点数量为6，则有9!/(9-8)!=362 880个映射结果，其中映射结果a、b对应映射位置信息Pa={1,4,5,2,3,7,8,9}、Pb={1,5,9,2,3,7,4,6}为两个有效的映射结果即有效解，只要对应位置信息为8个不大于9的不相同整数，都是一个有效解。

(a) 映射a (b) 映射b (c) 映射结果图2 映射结果图

3.2 初始解构造

遗传算法和量子遗传算法的初始解集大多是随机产生的，当种群规模比较大时进化效率很低，为了提高收敛速度，结合NoC的结构特点，按照相关链路数量和通信量大小双重标准对任务节点优先排序，优先级高的优先选择映射位置，构建一个较优初始解集，将大大提升种群进化效率。

构建较优初始解集步骤如下：

1) 统计各个任务节点相关链路数量RLnum和相关通信总量:

(10)

以图1中ATG为例，优先级定级如表1所示。

表1 任务节点优先级定级

2) 优先考虑任务节点相关链路数量，数量越多，优先级越高；数量相同时，考虑任务节点相关通信总量，通信总量越高的优先级越高。

3) 优先级高的优先在对应的ARCG中选择合适的位置放置，再放置与它相关的任务节点，相关任务节点有多个时优先级越高的优先放置。

4) 剩余少量节点可以随机放置，产生初始解集。

如图3所示，以图1中的ATG和ARCG为例，任务节点3有4个相关链路，则最先映射，对应ARCG中位置5刚好有4个相关物理链路，则任务节点3放置在位置5；与任务节点3有关系的任务节点2、4、5、7按照表1中的优先级放置，则依次放置节点4、7、2、5；最后考虑第三梯队的放置，优先放置与任务节点4相关的链路，其中3、5已经确定位置，则就近放置1即可，其他同理放置，直至所有任务节点全部放置在ARCG中。由于放置任务节点4时有4个位置可以选择，任务节点4确定后任务节点3有3个位置可以选择，进而产生很多可能的较优解。

图3 较优初始解集构造

以上是对于3×3 Mesh的NoC，如果是4×4 Mesh，第一个任务节点就有4个映射位置可供选择，8个任务节点放置到16个映射位置中，结构冗余很大，一般随机确定第一个任务节点的位置，然后按照上述方法构造较优初始解集。如果初始解集需求较大时可以通过变更第一个任务节点位置来获取更多的较优初始解。

3.3 量子遗传算法原理

量子遗传算法利用量子多态特性，用概率幅对染色体进行编码，然后通过量子旋转门调整概率幅进化种群来寻找最优解，具体可在文献[9]中了解相关原理。

QGA引入量子比特，一个量子比特是两个基态的任一线性组合如下：

|φ〉=α|0〉+β|1〉

(11)

式中:α、β为两个基态|0〉、|1〉对应的概率幅，表示量子态|φ〉被观察为基态的相应概率，且满足：

(12)

一对复数定义一个量子位，用概率幅对染色体进行编码，则长度为m的量子染色体可表示为：

(13)

QGA通过量子旋转门实现种群的进化，即替代原遗传算法的选择、交叉、变异操作，使得遗传算法的进化实现更简单。量子旋转门更新方式为：

(14)

3.4 改进量子遗传算法的实现

QGA具有全局搜索能力强、收敛速度快、个体数目少易于进化计算且不容易陷入“早熟”陷阱等优点。不同于变异操作，量子变异操作通过选择改变变异位的概率幅，利用量子纠缠特性，只需要采用单点变异就能防止遗传早熟现象出现。QGA改进策略(MQGA)如图4所示。

图4 MQGA策略图

MQGA流程如下：

1) 初始化总群Q(t)，结合Mesh拓扑结构特点采用前面讲到的新方法生成初始种群Q(t0)，含有N个量子编码的染色体。

2) 对Q(t0)进行一次测量并进行适应度评估，得到该种群的最优个体解Bgtj(t0)，并做好相应记录。

3) 判断计算过程是否满足结束条件，满足则退出，否则继续计算。

4) 量子旋转门操作得到下一代种群Q(t1)。

5) 对Q(t1)种群进行一次适应度计算，得到最优个体解Bgtj(t1)，并做好相应记录。

6) 返回步骤3)进行下一次迭代。

4 实 验

4.1 实验环境

1) 仿真平台。实验在Linux环境下用C++完成映射算法程序等相关源代码的编写，采用2D NoC仿真软件Noxim作为仿真软件，在Ubuntu 16.04操作系统下实现。硬件环境采用CPU为第八代Intel Core i7-8550U，最高睿频4.0 GHz，内存16 GB DDR4双通道的微型计算机。

2) ARCG拓扑结构和路由选择。2D Mesh拓扑结构结构规则、实现容易、布线简单、便于拓展，是常用的NoC拓扑结构，对于映射算法研究非常合适。该实验选用2D Mesh拓扑结构，根据实验需要有4×4、5×5、6×6三种规模的Mesh拓扑。路由算法采用容易理解和实现的XY路由算法，也是NoC主流路由算法。

3) 应用任务图的选择。为了体现QGA算法对各种实际应用的有效性，并便于与同类算法作对比分析，实验采用典型的实际应用任务图VOPD、MPEG-4、263Enc、263Dec[13]。4种应用任务图结构不同，任务节点数和通信总量也不尽相同，详细特征属性见表2。

表2 应用任务属性

4) 实验结果计算方式。由于芯片生产工艺的不同，不同芯片的Mesh结构相邻处理单元之间传递信息的能耗和时延也不相同。为了便于评估映射结果的功耗和时延，考虑到Mesh结构的规则对称性，实验计算时将相邻两个处理单元之间的距离视为一个曼哈顿距离M，每M通信传递消耗1个能量单元，时延时间按式(9)进行同一量化。由于智能算法有一定的随机性，为确保实验结果准确性，每种应用任务图在同一规模的Mesh结构特征图下分别运行10次，然后取10次结果的平均值。

4.2 多目标线性加权系数a的选取

a的选择主要由链路带宽的高低和处理任务通信量的大小等决定。以4×4规模的NoC为例，由于VOPD、MPEG-4通信量比263Enc尤其是263Dec大很多倍，对前两个可能会出现拥堵的带宽在运行263Enc、263Dec时不会发生拥堵。所以实验时链路带宽根据处理任务通信量的多少进行变化，保证存在一定拥堵的可能性，该实验取平均链路负载的5倍。VOPD、MPEG-4链路带宽相近，可放在同一图中对比，在不同a取值下的实验结果如图5所示。

(a) VOPD与MPEG-4

(b) 263Dec

(c) 263Enc图5 4×4不同应用MQGA能耗随a值变化图

通过4种应用能耗曲线可以看出，在不考虑时延时能耗都会偏高，在过于考虑时延时反而造成能耗的大量提升，在实验设定的带宽下，a值取0.3附近时效果比较好，能耗相对较低。

VOPD在不同规模的Mesh结构随a值变化对比图如图6所示。随着NoC结构规模的扩大，处理应用能耗整体会有不少提升，因为规模变大后，链路带宽降低，拥堵更严重；a值的调节在前期比较显著，最低能耗的a值会减小，说明NoC规模越大，a值的合理取值应该越小。

图6 VOPD不同规模MQGA能耗随a值变化图

4.3 能耗对比

对比不同算法时设置a值为0.3，在4×4规模的Mesh结构下，与GA[10]、AGA[11]、DPSOGA[5]、HQGA[4]4种算法作对比。为了同框便于直观显示，以4种应用任务映射结果能耗对另外4种算法的能耗降低百分比如图7所示。

图7 能耗降低条形图

可以看出，MQGA在相同运行环境下比GA、AGA有更大的提升,相比较新的DPSOGA和HQGA也有不少提升，说明MQGA搜索精度更精确。例如对VOPD应用来说，MQGA比早期的GA提升25.4%，比AGA提升10.4%，比近两年的DPSOGA也提升4.1%，即使同样采用量子编码的HQGA也有提升了1.6%；对263Dec应用时候提升更多，即使对比较新的DPSOGA也提升了13.2%，比HQGA提升了5.8%。

4.4 收敛速度对比

MQGA在具有较快收敛特性的QGA基础上，结合NoC应用映射特点，进一步优化初始解集，使得MQGA收敛速度更快。在同一环境平台下5种算法处理VOPD应用任务能耗随遗传迭代次数收敛情况如图8所示。MQGA的收敛速度是最快的，最早的GA迭代到收敛需要150次左右，同样情况下MQGA 30次迭代就可以达到收敛，而且收敛精度远远高于GA。对于同样适用较优初始解集的DPSOGA，MQGA的初始解集质量更高，收敛速度也更快。对于同样改进QGA的HQGA，由于初始解集更优秀，收敛速度大大提升，收敛精度也有提高。可以看出，GA结合量子编码会很大程度地提升收敛速度。

图8 5种算法收敛走势图

5 结 语

本文在考虑拥堵的情况下利用线性加权和负载均衡的办法设计了NoC多目标映射评估模型，不仅可以实现低功耗低时延，也同时提高了系统稳定性和可靠性，结合NoC映射特点改进了量子遗传算法。实验结果表明，MQGA在相关算法比较中效果显著，大大提升了NoC映射算法的收敛速度，并进一步提升了搜索精度。算法实现时量子遗传编码比较复杂，编码解码速度慢，后续研究可以围绕编码问题进一步优化。随着应用任务越来越复杂，片上网络规模的扩大，较优初始解集的产生也需要合适的算法方可更好实现。