本发明提出一种基于离散蝙蝠算法的片上网络映射方法，初始化并生成蝙蝠种群；计算每个蝙蝠个体的适应值，找出种群中的最佳个体；根据当前迭代次数来更新脉冲发射率；对于蝙蝠个体产生新的解；判断rand(0,1)是否大于脉冲发射率，大于时对当前最佳个体进行局部搜索，产生新的解x′i；计算新的解x′i的适应值，并由新的解x′i的适应值计算响度Ai；当新的解x′i的适应值小于个体当前的适应值，且rand(0,1)大于响度Ai，则用新的解x′i更新当前个体的位置；当新解x′i的适应值比种群最佳个体x*的适应值小，则令新解x′i为种群中的最佳个体；遍历整个蝙蝠种群，若运行迭代次数到达预设最大值，搜索停止，输出种群的最佳个体及其适应值。实验结果表明，本发明能够获得更优的映射结果。
1.一种基于离散蝙蝠算法的片上网络映射方法，其特征在于，包括如下步骤：步骤1：初始化算法的参数，生成初始的蝙蝠种群，所述参数包括：蝙蝠数量，算法迭代次数，最大频率Qmax和最小频率Qmin，脉冲发射率的最大值Rmax和最小值Rmin；
步骤2：计算每个蝙蝠个体的适应值，并找出种群中的最佳个体x*；
步骤3：根据当前迭代次数来更新脉冲发射率Ri(t)；
步骤5：判断rand(0,1)是否大于脉冲发射率Ri，如果是，对当前最佳个体进行局部搜索，产生新的解xi′；
步骤6：计算新的解xi′的适应值，并根据新的解xi′的适应值来计算响度Ai；
步骤7：如果新的解xi′的适应值小于个体i当前的适应值，且rand(0,1)大于响度Ai，则用新的解xi′来更新当前个体i的位置；
步骤8：如果新的解xi′的适应值比种群最佳个体x*的适应值小，则令新的解xi′为种群中的最佳个体；
步骤9：重复步骤4-8直至遍历整个蝙蝠种群，若运行迭代次数到达预设最大值，搜索停止，输出种群的最佳个体及其适应值；否则增加当前代数，跳回到步骤3；
初始的蝙蝠种群的一部分个体随机产生，另一部分个体通过种群初始化算法产生；种群初始化算法的具体步骤如下：(11)选择具有最大通信量的通信链路；
(12)若通信链路上的两个节点都没映射，则选择一节点映射到拓扑图中的任一个无节点映射的位置A，另一节点映射到与位置A最相邻，即曼哈顿距离最小且无节点映射的位置B；否则跳到(13)；
(13)若通信链路上其中一个节点已映射，则另一节点映射在拓扑图中最相邻，即曼哈顿距离最小的无节点映射位置；否则跳到(14)；
(14)若通信链路上两个节点都已映射，直接跳到(15)；
(15)若所有IP核都已映射到拓扑图中，则输出结果；否则在核任务图中去除该通信链路，并跳到(11)。
2.根据权利要求1所述的基于离散蝙蝠算法的片上网络映射方法，其特征在于,每个蝙蝠个体是采用下面的方式进行表示的：蝙蝠的位置为：x＝(x1,x2,…,xd)，其中，x1,x2,…,xd为自然数1,2,…,d的一个全排序，而d是实际问题中IP核的个数，x的每个分量表示IP核在拓扑结构上放置的位置。
3.根据权利要求1所述的基于离散蝙蝠算法的片上网络映射方法，其特征在于，步骤2中的每个蝙蝠个体适应值是通过下面的式子计算产生的：其中，C代表核任务图中IP核集合，任意一个顶点ci∈C代表一个待映射的IP核，wij代表IP核ci、cj的核间通信数据量，map(ci)指每个蝙蝠个体中IP核ci在拓扑结构上映射的位置，hopcount(a,b)代表拓扑结构图中节点a，b的曼哈顿距离。
4.根据权利要求1所述的基于离散蝙蝠算法的片上网络映射方法，其特征在于，步骤3中脉冲发射率的更新采用下面的公式：其中Rmax和Rmin分别为设定的脉冲发射率的最大值和最小值，tmax为蝙蝠迭代的最大代数，t为当前的代数。
5.根据权利要求1所述的基于离散蝙蝠算法的片上网络映射方法，其特征在于，步骤4中对于蝙蝠个体i，产生新的解xi′采用下面的实现方式为：给出下面的定义：
(22)蝙蝠位置和速度的加法运算实现了蝙蝠位置的移动，使蝙蝠到达一个新的位置；
蝙蝠新的位置为原来的位置通过速度的置换序列来改变；
(23)蝙蝠位置和位置相减得到的是速度，即置换序列；
(24)蝙蝠的速度和速度相加得到的是速度，为两个速度置换序列的并集；
(25)蝙蝠的速度乘以系数β的结果仍是速度；令β＝a+b，a为β的整数部分，b为β的小数部分；a的结果为原来置换序列的a次重复，bv的结果为原来置换序列的截断，最后新的速度βv为得到的两个置换序列av和bv的并集；
在d维空间中，蝙蝠个体i在第t次迭代时的位置 速度 更新公式为：fri＝frmin+(frmax-frmin)β
其中β∈[0,1]是来自均匀分布的随机向量，x*是在蝙蝠种群中的最佳个体；
对于蝙蝠个体i，新的解xi′是根据定义(21)-(25)以及更新公式产生的。
6.根据权利要求1所述的基于离散蝙蝠算法的片上网络映射方法，其特征在于步骤5中，对当前最佳个体进行局部搜索是按照下面的步骤进行的；
(31)在拓扑结构图中选择一个节点，记为Node1；
(32)找出选择的节点所映射的IP核，记为IP1；
(33)随机选择节点在拓扑图中的一个相邻节点，并且找出其对应的IP核，分别记为Node2和IP2；
(34)随机选择IP1在通信任务图中有通信的IP核，记为IP3，并找出其在拓扑结构图中对应的节点位置，记为Node3；
(35)将IP2映射到Node3，将IP3映射到Node2，完成局部搜索。
7.根据权利要求1所述的基于离散蝙蝠算法的片上网络映射方法，其特征在于，步骤6中，根据新的解xi′的适应值来计算响度Ai采用下面的公式：Ai＝(fiti-fitbst)/(fitmax-fitbst)其中fiti是新的解xi′的适应值，fitbst为当前种群最好的适应值，fitmax为当前种群的最大适应值。
一种基于离散蝙蝠算法的片上网络映射方法
技术领域
[0001] 本发明涉及片上网络技术领域，尤其涉及一种基于离散蝙蝠算法的片上网络映射方法。
背景技术
[0002] 随着半导体工艺技术的高速发展，集成电路工艺已经进入了纳米时代，集成电路上的晶体管资源越来越多，单个芯片上的晶体管数量可以多达几十亿个。先进的半导体工艺和片上集成度的不断提高，使得单个芯片上可以集成众多功能模块，从而构成一个片上系统(System-on-Chip，SoC)。但随着人们对芯片功能需求的提高和半导体工艺技术的不断进步，片上系统的复杂度越来越高，片上系统也由单核处理器向多核处理器发展，基于总线结构的片上系统在多核处理器通信问题上面临着严峻的挑战，主要体现在带宽、吞吐量限制，可拓展性，可重用性，信号完整性，时钟同步和功耗等方面。
[0003] 为了解决上述问题，研究人员将计算机网络技术移植到芯片设计中，采用路由和分组交换技术作为片上通信技术，提出了片上网络(Network-on-chip，NoC)的概念。片上网络是片上系统发展的一个重要方向，它从体系结构上解决了总线结构面临的各种问题。
[0004] 卡内基梅隆大学的Ogras U.Y.等人曾提出了片上网络设计空间的概念，并将片上网络研究归纳为三大类关键问题：基础架构、通讯机制和映射优化。映射优化是指给定核通信任务图和拓扑结构的基础上，确定每个处理单元(IP核)在片上网络拓扑结构中所放的位置，以满足特定的设计要求，如使得能耗，延时等性能达到最优。映射优化是线性规划问题，是典型的NP-hard问题，该问题的搜索空间随系统规模呈阶乘增长。
发明内容
[0005] 本发明提出了一种基于离散蝙蝠算法的片上网络映射方法，旨在针对于具体的片上网络映射问题能够获得更优的映射结果。
[0006] 为实现上述目的，本发明的技术方案为：
[0007] 一种基于离散蝙蝠算法的片上网络映射方法，包括以下步骤：
[0008] 步骤1：初始化算法的参数，生成初始的蝙蝠种群，所述参数包括：蝙蝠数量，算法迭代次数，最大频率Qmax和最小频率Qmin，脉冲发射率的最大值Rmax和最小值Rmin；
[0009] 步骤2：计算每个蝙蝠个体的适应值，并找出种群中的最佳个体x*；
[0010] 步骤3：根据当前迭代次数来更新脉冲发射率Ri(t)；
[0011] 步骤4：对于蝙蝠个体i，产生新的解xi′；
[0012] 步骤5：判断rand(0,1)是否大于脉冲发射率Ri，如果是，对当前最佳个体进行局部搜索，产生新的解xi′；
[0013] 步骤6：计算新的解xi′的适应值，并根据新的解xi′的适应值来计算响度Ai；
[0014] 步骤7：如果新的解xi′的适应值小于个体i当前的适应值，且rand(0,1)大于响度Ai，则用新的解xi′来更新当前个体i的位置；
[0015] 步骤8：如果新的解xi′的适应值比种群最佳个体x*的适应值小，则令新的解xi′为种群中的最佳个体；
[0016] 步骤9：重复步骤4-8直至遍历整个蝙蝠种群，若运行迭代次数到达预设最大值，搜索停止，输出种群的最佳个体及其适应值；否则增加当前代数，跳回到步骤3。
[0017] 在上述的片上网络映射方法中，每个蝙蝠个体是通过下面的方式进行表示的：
[0018] 蝙蝠的位置为：x＝(x1,x2,…,xd)。其中，x1,x2,…,xd为自然数1,2,…,d的一个全排序，而d是实际问题中IP核的个数。x的每个分量表示IP核在拓扑结构上放置的位置，若x2＝7，则表示IP核2放置在拓扑结构中节点7的位置。
[0019] 步骤1中的初始的蝙蝠种群通过下面的方式产生：
[0020] 初始的蝙蝠种群的一部分个体随机产生，另一部分个体通过种群初始化算法产生。种群初始化算法是本发明基于片上网络映射问题提出的使得初始种群个体具有更好的适应度值的算法。其本质是使得具有较大通信量的通信链路上的两个处理单元(IP核)尽量相邻。其具体步骤如下：
[0021] (11)选择具有最大通信量的通信链路；
[0022] (12)若通信链路上的两个节点都没映射，则选择一节点映射到拓扑图中的任一个无节点映射的位置A，另一节点映射到与位置A最相邻，即曼哈顿距离最小且无节点映射的位置B；否则跳到(13)；
[0023] (13)若通信链路上其中一个节点已映射，则另一节点映射在拓扑图中最相邻，即曼哈顿距离最小的无节点映射位置；否则跳到(14)；
[0024] (14)若通信链路上两个节点都已映射，直接跳到(15)；
[0025] (15)若所有IP核都已映射到拓扑图中，则输出结果；否则在核任务图中去除该通信链路，并跳到(11)。
[0026] 步骤2中的每个蝙蝠个体适应值是通过下面的式子计算产生的：
[0027]
[0028] 其中，C代表核任务图中IP核集合，任意一个顶点ci∈C代表一个待映射的IP核，wij代表IP核ci、cj的核间通信数据量，map(ci)指每个蝙蝠个体中IP核ci在拓扑结构上映射的位置，hopcount(a,b)代表拓扑结构图中节点a，b的曼哈顿距离。
[0029] 步骤3中脉冲发射率的更新采用下面的公式：
[0030]
[0031] 其中Rmax和Rmin分别为设定的脉冲发射率的最大值和最小值，tmax为蝙蝠迭代的最大代数，t为当前的代数。
[0032] 步骤4中对于蝙蝠个体i，产生新的解xi′采用下面的方式：
[0033] 首先，给出下面的定义：
[0034] 给出下面的定义：
[0035] (21)用置换序列来表示蝙蝠的速度；如v＝{(1,3),(2,5)}可表示蝙蝠的速度；
[0036] (22)蝙蝠位置和速度的加法运算实现了蝙蝠位置的移动，使蝙蝠到达一个新的位置；蝙蝠新的位置为原来的位置通过速度的置换序列来改变；如：
[0037] v＝(2,3,4,1,5),v＝{(1,3),(2,5)}，则新的位置为：x＝(5,1,4,3,2)；
[0038] (23)蝙蝠位置和位置相减得到的是速度，即置换序列；如：x1＝(2,3,4,1,5)，x2＝(5,1,4,3,2)，,则v＝x1-x2＝{(5,2),(1,3)}；
[0039] (24)蝙蝠的速度和速度相加得到的是速度，为两个速度置换序列的并集；如：v1＝{(1,3),(2,5)},v2＝{(2,4)}，则v＝v1+v2＝{(1,3),(2,5),(2,4)}；
[0040] (25)蝙蝠的速度乘以系数β的结果仍是速度；令β＝a+b，a为β的整数部分，b为β的小数部分；av的结果为原来置换序列的a次重复，bv的结果为原来置换序列的截断，如b＝0.7，v＝{(1,3),(2,5),(4,6)}，速度的置换序列个数为3，而3×0.7＝2.1，取整后为2，则速度bv＝{(1,3),(2,5)}。最后新的速度βv为得到的两个置换序列av和bv的并集[0041] 在d维空间中，蝙蝠个体i在第t次迭代时的位置 速度 更新公式为：
[0042] fri＝frmin+(frmax-frmin)β
[0043]
[0044]
[0045] 其中β∈[0,1]是来自均匀分布的随机向量，x*是在蝙蝠种群中的最佳个体；
[0046] 对于蝙蝠个体i，新的解xi′是根据定义(21)-(25)以及更新公式产生的。
[0047] 步骤5中，对当前最佳个体进行局部搜索是按照下面的步骤进行的；
[0048] (31)在拓扑结构图中选择一个节点，记为Node1；
[0049] (32)找出选择的节点所映射的IP核，记为IP1；
[0050] (33)随机选择节点在拓扑图中的一个相邻节点，并且找出其对应的IP核，分别记为Node2和IP2；
[0051] (34)随机选择IP1在通信任务图中有通信的IP核，记为IP3，并找出其在拓扑结构图中对应的节点位置，记为Node3；
[0052] (35)将IP2映射到Node3，将IP3映射到Node2，完成局部搜索。
[0053] 步骤6中，根据新的解xi′的适应值来计算响度Ai采用下面的公式：
[0054] Ai＝(fiti-fitbst)/(fitmax-fitbst)
[0055] 其中fiti是新的解xi′的适应值，fitbst为当前种群中最好的适应度值，fitmax为当前种群的最大适应度值。
[0056] 与现有技术相比，本发明的有益技术效果体现在：
[0057] 1.标准的蝙蝠算法是连续的优化算法，采用的是连续的实值编码方式，无法用于离散的问题，而本发明在标准的蝙蝠算法上进行改进，针对片上网络映射问题，提出了离散蝙蝠算法；
[0058] 2.本发明在初始化阶段针对片上网络映射问题提出了种群初始化算法，使得初始种群个体具有更好的适应度值，同时，初始的蝙蝠种群的一部分个体随机产生，保持了种群的多样性，使得算法能更快地收敛，但又不会陷入局部最优；
[0059] 3.实验结果表明，本发明提出的基于离散蝙蝠算法的片上网络映射方法与其他映射方法相比，具有更好的性能，能够找到更好地映射解。
附图说明
[0060] 图1是本发明基本流程图；
[0061] 图2是VOPD核通信任务图；
[0062] 图3是MPEG-4核通信任务图；
[0063] 图4是PIP核通信任务图。
具体实施方式
[0064] 附图仅用于示例性说明，不能理解为对本专利的限制；为了更好说明本实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；
[0065] 下面结合附图和实施例对本发明的技术方案做进一步的说明。
[0066] 给出两个定义：
[0067] 定义1：核任务图G(C，E)，为有向非循环加权图集合。集合中的任意一个顶点ci∈C代表一个待映射的IP核，任意一条边eij∈E代表IP核ci、cj间的通信数据流，每条边的权重wij代表核间通信数据量， 表示顶点ci、cj间的通信带宽要求。
[0068] 定义2：NoC拓扑结构图M(T，L)，为有向图。图中顶点ti∈T代表可分配的NoC节点，边lij∈L代表连接ti，tj间的通信链路。 表示通信节点ti到通信节点tj的能提供的最大通信带宽。
[0069] 本发明以通信代价函数为目标函数，基于以上两个定义，片上网络映射问题求解可归纳为：在最小路由路径下找到映射函数map()，使得该函数的映射解满足目标式(1)和约束条件(2)-(5)。
[0070]
[0071]
[0072]
[0073] size(G)≤size(M) (4)
[0074]
[0075] 其中，hopcount(a，b)表示拓扑结构图中节点a，b的曼哈顿距离。
[0076] 如图1所示，本发明的具体实现步骤如下：
[0077] 步骤1：初始化算法的参数以及生成初始的蝙蝠种群。
[0078] 在本实施例中，令蝙蝠数量为100，算法迭代次数为100，最大频率Qmax为4，最小频率Qmin为0，脉冲发射率的最大值Rmax为0.9，最小值Rmin为0.1。
[0079] 初始的蝙蝠种群的一部分个体随机产生，另一部分个体通过种群初始化算法产生。其具体步骤如下：
[0080] (11)选择具有最大通信量的通信链路；
[0081] (12)若通信链路上的两个节点都没映射，则选择一节点映射到拓扑图中的任一没节点映射的位置，另一节点映射到与之最相邻(曼哈顿距离最小)的没节点映射位置；否则跳到(13)；
[0082] (13)若通信链路上其中一个节点已映射，则另一节点映射在拓扑图中最相邻(曼哈顿距离最小)的没节点映射位置；否则跳到(14)；
[0083] (14)若通信链路上两个节点都已映射，直接跳到(15)；
[0084] (15)若所有处理单元(IP核)都已映射到拓扑图中，则输出结果；否则在核任务图中去除该通信链路，并跳到(11)；
[0085] 步骤2：计算每个蝙蝠个体的适应值，并找出种群中的最佳个体x*。
[0086] 每个个体适应值是通过下面的式子计算产生的：
[0087]
[0088] 其中，map(ci)指每个个体中IP核ci在拓扑结构上映射的位置。
[0089] 在本实施例中，当前种群中的最佳个体x*为：x*＝[1 2 6 7 3 4 8 12 15 16 14 10 9 5 13 11]，其适应度值(目标函数值)为4151。
[0090] 步骤3：根据当前迭代次数来更新脉冲发射率Ri；
[0091] 脉冲发射率的更新采用下面的公式：
[0092]
[0093] 其中Rmax和Rmin分别为设定的脉冲发射率的最大值和最小值，tmax为蝙蝠迭代的最大代数，t为当前的代数。
[0094] 从步骤1可知，脉冲发射率的最大值Rmax为0.9，最小值Rmin为0.1，蝙蝠迭代的最大代数tmax为100，而当前代数t为1，则代入上式计算可得脉冲发射率Ri＝0.1。
[0095] 步骤4：对于蝙蝠个体i，产生新的解xi′；
[0096] 下面以当前蝙蝠种群的第一个个体为例，进行说明。
[0097] 当前蝙蝠个体1为：x1＝[1 2 6 7 4 8 12 16 11 15 14 10 9 5 13 3]。
[0098] 在d维空间中，蝙蝠i在第t次迭代时的位置 速度 更新公式为：
[0099] fri＝frmin+(frmax-frmin)β
[0100]
[0101]
[0102] 其中β∈[0,1]是来自均匀分布的随机向量，x*是在蝙蝠种群中的最优解。
[0103] 在本实例中，β＝0.12，则计算得fr1＝0.48。从步骤2可得种群中的最佳个体x*为：x*＝[1 2 6 7 3 4 8 12 15 16 14 10 9 5 13 11]。
[0104] 则
[0105]
[0106] 步骤5：判断rand(0,1)是否大于脉冲发射率Ri，如果是，对当前最佳个体进行局部搜索，产生新的解xi′；
[0107] 在本实施例中，rand＝0.7，比脉冲发射率Ri大，需要对当前最优个体进行局部搜索。对当前最佳个体进行局部搜索是按照下面的步骤进行的；
[0108] (21)在拓扑结构图中选择一个节点，记为Node1；
[0109] (22)找出选择的节点所映射的IP核，记为IP1；
[0110] (23)随机选择节点在拓扑图中的一个相邻节点，并且找出其对应的IP核，分别记为Node2和IP2；
[0111] (24)随机选择IP1在通信任务图中有通信的IP核，记为IP3，并找出其在拓扑结构图中对应的节点位置，记为Node3；
[0112] (25)将IP2映射到Node3，将IP3映射到Node2，完成局部搜索。
[0113] 完成局部搜索后，新的解x′1＝[1 7 6 2 3 4 8 12 15 16 14 10 9 5 13 11]。
[0114] 步骤6：计算新的解xi′的适应值，并根据新的解xi′的适应值来计算响度Ai；
[0115] 新的解x′1的适应值f(xi′)＝4389。响度Ai的计算采用下面的公式：
[0116] Ai＝(fiti-fitbst)/(fitmax-fitbst)
[0117] 其中fiti是新的解xi′的适应值，fitbst为当前种群最好的适应度值，fitmax为当前种群的最大适应度值。
[0118] 在本实施例中，当前fit1＝4389，fitbst＝4151，fitmax＝5863，计算得Ai＝0.139。
[0119] 步骤7：如果新的解xi′的适应值小于个体i当前的适应值，且rand(0,1)大于响度Ai，则用新的解xi′来更新当前个体i的位置；
[0120] 当前，新的解xi′的适应值为4389，个体i当前的适应值为4454，rand＝0.64，rand大于响度Ai，满足新的解xi′的适应值小于个体i当前的适应值，且rand大于响度Ai的条件，用新的解xi′来更新当前个体i的位置，即令x1＝[1 7 6 2 3 4 8 12 15 16 14 10 9 5 13 11]。
[0121] 步骤8：如果新的解xi′的适应值比种群最佳个体x*的适应值小，则令新的解xi′为种群中的最佳个体；
[0122] 当前，新的解xi′的适应值为4389，种群最佳个体x*的适应值为4151，不满足条件。
[0123] 步骤9：重复步骤4-8直至遍历整个蝙蝠种群，若运行迭代次数到达预设最大值，搜索停止，输出种群的最佳个体及其适应值；否则增加当前代数，跳回到步骤3。
[0124] 迭代结束后，得到的种群的最佳个体为x*＝[9 13 14 15 11 10 6 5 2 1 3 7 8 12 4 16]，其适应值(目标函数)为4119。
[0125] 表1是本发明与NMAP算法、GMAP算法、LMAP算法、CGMAP算法、ACO算法和KL_Mesh算法分别在VOPD、MPEG-4和PIP上进行映射后得到的最优通信代价的对比表。
[0126] 表1
[0127]
[0128] 显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。
