一种片上网络应用的广度优先贪心映射方法

摘要

本发明涉及一种片上网络应用的广度优先贪心映射方法，通过同时考虑片上网络应用中任务的拓扑结构以及应用映射区域的结构，快速高效地生成应用映射方案，用于降低片上网络的内部拥堵。该方法包括：首任务映射步骤，根据首任务后继任务的数量与片上网络节点的出度选择映射首任务的节点，节点的所述出度定义为该节点可用邻居节点的数量；后继任务映射步骤，以广度优先贪心方式对依次选择映射后继任务的节点。与现有技术相比，本发明所得的结果与穷举算法较为接近，并且本方法的时间复杂度处于低多项式级别。

说明书

技术领域

本发明涉及片上网络应用的映射方法，尤其是涉及一种片上网络应用的广度优先贪心映射方法。

背景技术

片上网络(NoC)作为一种多核的片上通信系统，拥有优秀的空间可伸缩性和并行通信能力。在片上网络中，各个核将它们的信息分成几个包，并通过芯片网络上的通道与路由进行传输。通过这种方式，片上网络的通信不会受到总线系统上大的传输延时与吞吐量限制的影响。即使在网络上有很多个核相连，片上网络也能够并发的处理单任务应用或者多应用任务。

在片上网络中，应用映射，即将应用的任务分配到各个片上网络节点是最重要的问题之一。具体来说，是将应用的各个任务映射到相应的节点上。然后，当应用的第一个任务执行完毕之后，会将一些数据包传输给它的直接后继任务。一旦后继任务获得这些数据包之后，它们就会开始运行。整个过程一直循环到所有任务执行完毕。在这个过程中，总的通信量(与能源消耗成正比)可以认为是一个数据包的数量以及数据包的传播路径长度的函数，后者主要取决于映射。一旦映射不适当，内部包传输时相互阻塞或传输路径过长都会导致片上网络严重的内部阻塞。片上网络中多个应用并行执行是很常见的。这种情况下，不正确的映射会导致严重的外部拥堵，即一些任务会映射到互不相连的节点上，令映射区域碎片化，这时包的传输需要穿过其他应用所在的区域，导致不同的应用之间相互阻塞。应用映射区域的碎片化如图1中App3的映射区域所示。一旦内部阻塞或者外部阻塞发生，会导致传输路径会变长或者包之间相互阻塞，此时应用的执行时间与总能量消耗都会增大，片上网络的性能会大大降低。

CoNA是Mohammad等人在“Smart Hill Climbing for Agile Dynamic Mapping inMany-Core Systems”(M.Fattah et al.,DAC'2013,Austin,TX,USA.pp.39:1-39:6.)中提出的一种智能登山算法，在该算法中，首先选择一个拥有所需数量邻居节点的节点，然后使用启发式爬山算法来搜索一片连续的映射区域。这样就避免了区域的碎片化并降低了外部拥堵，此外，该算法优先选择方形的区域用来映射，这是因为在这种情况下平均传输量非常小，同时优先选择位于边界的节点进行映射。CoNA将含六个任务的App3映射至片上网络如图2所示。但是，在获得了连续的映射区域之后，这种方法无法解决内部拥堵的问题。一方面，当CoNA在进行映射时，它总是会将第一个任务映射到中心节点，然后根据曼哈顿距离将后续的任务映射到剩余的节点上。在这个过程中，它忽略了映射区域的结构，它错过了进一步减少内部拥堵的机会，另外一方面，映射区域也有是不规则的结构，如图3中的App6所示，以中心开始映射的方法忽略了映射区域的结构，这会加剧内部拥堵。

片上网络在运行应用时，应用的内部拥堵对于片上网络的整体性能影响很大。因此，需要提出一种新的片上网络应用映射方法。

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种高效、快速的片上网络应用的广度优先贪心映射方法。

本发明的目的可以通过以下技术方案来实现：

一种片上网络应用的广度优先贪心映射方法，包括：

首任务映射步骤，根据首任务后继任务的数量与片上网络节点的出度选择映射首任务的节点，节点的所述出度定义为该节点可用邻居节点的数量；

后继任务映射步骤，以广度优先贪心方式对依次选择映射后继任务的节点。

所述首任务映射步骤中，具有以下情况：

a)当存在节点满足出度等于首任务后继任务的数量时，选择该节点作为映射首任务的节点；

b)当所有节点的出度都小于首任务后继任务的数量时，选择出度最大的节点作为映射首任务的节点；

c)当所有节点的出度都大于首任务后继任务的数量时，选择出度最小的节点作为映射首任务的节点。

当满足情况a)、b)或c)的节点个数大于1时，先选择处在边界或角落的节点作为映射首任务的节点。

所述后继任务映射步骤中，以广度优先方式，根据任务拓扑结构，依次对每层的各任务以贪心方式实现映射，即每次以流入数据量最大的任务作为当前任务，先选择与该当前任务的前驱任务所在节点的曼哈顿距离最小的节点进行映射，直至所有任务映射完毕。

所述后继任务映射步骤具体包括以下步骤：

101)对于同层任务，通过广度优先搜索算法按照流入数据量大小进行排序，形成一队列；

102)队列根据任务流入数据量的大小，由大到小依次将任务输出；

103)对于输出的当前任务，判断该当前任务是否仅有一个前驱任务，若是，则执行步骤104)，若否，则执行步骤105)；

104)选择与所述前驱任务所在节点的曼哈顿距离最小的节点进行映射，执行步骤106)；

105)遍历所有前驱任务所在节点的可用邻居节点，选择数据传输量最小的一个节点进行映射，执行步骤106)；

106)对映射节点的邻居节点的出度进行更新；

107)判断队列是否为空，若是，则执行步骤108)，若否，则返回步骤102)；

108)重复步骤101)-107)，实现对所有层任务的映射。

所述步骤104)中，当曼哈顿距离最小的节点大于1个时，选择其中节点出度与当前任务的直接后继任务数目最接近的节点进行映射。

所述曼哈顿距离人计算公式为：

MD(ni,nj)＝|j_x-i_x|+|j_y-i_y|

其中，MD(n_i,n_j)为节点i到节点j的曼哈顿距离，i_x、i_y为节点i的X、Y坐标，j_x、j_y为节点j的X、Y坐标。

该方法的时间复杂度的最大级数小于等于2。

与现有技术相比，本发明具有以下优点：

1.本应用映射方法考虑了任务的拓扑结构与映射区域的结构。不论任务的拓扑结构如何，不论片上网络的映射区域是方形还是不规则图形，本映射方法都能够根据相关信息高效地计算出应用映射方案，可以有效地降低片上网络数据传输时的内部拥堵，效率高。

2.本发明在首任务映射时，对于不同的后继任务数量选择不同的映射节点，且优先选择在边界或角落的节点，可以一定程度上避免映射区域的碎片化从而导致数据的传输距离增加。

3.本发明在进行后继任务映射时，采用广度优先贪心方式进行，逐层处理，不同层之间流入数据大的任务就不会相互影响。

4.本应用映射方法的时间复杂度低，其最大级数不超过2，处于低多项式级别。相较于穷举算法，虽然穷举算法能够计算出最优解，但其时间复杂度为O(|n！|)，n代表一个应用的任务数，当n足够大时，穷举算法寻找最优解所消耗的时间甚至比最坏映射方案下应用的执行时间要长，本应用映射方法消耗的时间要远远低于穷举算法，但最终映射方案的能耗与应用的映射时间都与穷举算法较为接近。

5.和现有学术论文中的方法相比，本映射方法能够降低22％-44％的能耗以及16％-57％的应用执行时间。

附图说明

图1为应用在片上网络的一种映射示意图；

图2为应用在片上网络的第二种映射示意图；

图3为应用在片上网络的第三种映射示意图；

图4为一个6个任务的应用的拓扑结构示意图；

图5为以CoNA方法与穷举方法将图4应用映射至2*3区域之后的对比图；

图6为本发明广度优先贪心映射方法的流程示意图；

图7为本发明首任务映射详细流程示意图；

图8为本发明后继任务映射详细流程示意图；

图9为本映射方法在实例中的施行示意图；

图10为在方形映射区域上的AWMD测试结果图；

图11为在方形映射区域上的LPWMD测试结果图；

图12为在不规则映射区域上的AWMD测试结果图；

图13为在不规则映射区域上的LPWMD测试结果图；

图14是本映射方法、穷举方法、CoNA方法时间消耗的对比图。

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。本实施例以本发明技术方案为前提进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

一、相关定义与相关指标

1.相关定义

内部拥堵与外部拥堵：片上网络中，数据包在传输过程中相互阻塞或传输路径过长都会导致片上网络严重的内部拥堵；片上网络往往会并行运行多个应用，这些应用中的一些任务会映射到互不相连的节点上，令映射区域碎片化，这时数据包的传输需要穿过其他应用所在的区域，令不同的应用之间相互阻塞，导致片上网络的外部拥堵。

片上网络中的应用：首先，一个包含数个任务的应用可以由一个边加权有向图来表示，每个节点代表一个任务，一个节点到另一个节点的有向边代表两个任务间包的传输，边的权重代表包的数量。AG<T,W>描述了一个应用，每一个顶点t_i∈T代表一个任务，w_i,j∈W代表任务i到任务j的包数量。一个含6个任务的应用的拓扑结构如图4所示，当任务6获得了任务4和任务5的数据包，代表应用结束。

映射区域与曼哈顿距离：映射区域可以描述为NG<N,λ>，n_i∈N代表一个节点i，λ_i∈λ代表节点i的出度。其中，λ_i的出度是指节点i在X或Y坐标系上可用的邻居节点。一旦一个任务映射到这个节点上，该节点的邻居节点的出度减一。在NG<N,λ>中，曼哈顿距离(ManhattanDistance,MD)表示通信距离，MD的计算方法如公式(1)所示。举例来说，MD(n_i,n_j)代表数据包从节点i到节点j所需经过的最小通道数量，它等于节点i与节点j在X,Y坐标上距离的绝对值之和。

MD(n_i,n_j)＝|j_x-i_x|+|j_y-i_y|>

2.相关指标

为了衡量映射方法对片上网络应用执行的影响，通过下列两个指标进行评价：

平均加权曼哈顿距离(Average Weighted Manhattan Distance,AWMD)：AWMD描述了内部包的传输状态，等于所有的传输总量除以所有包的数量，传输总量等于包的数量w_i,j乘上对应的曼哈顿距离MD(n_i,n_j)。AWMD算方法如公式(2)所示：

以图4中应用为例，图5展示了以CoNA方法与穷举方法将该应用映射至2*3的区域时，两种方法的区别。其中，以CoNA方法进行映射，其AWMD为85/62＝1.37，以穷举方法获得最优解之后，其AWMD为1。

最长权值曼哈顿距离(Longest Path Weighted Manhattan Distance,LPWMD)：假设包从一个节点逐个传输到另一个节点，LPWMD等于w_max(i,j)乘以对应的MD_max(n_i,n_j)，其中w_max指的是关键路径上包的数量，MD_max指的是传输距离。为了计算LPWMD，需要在任务图上找出关键路径，并用w与MD的乘积替代边的权重。LPWMD的计算方法如公式(3)所示：

LPWMD＝∑w_max(i,j)×MD_max(n_i,n_j)(3)

以图3中CoNA映射方法为例，该方案下，关键路径为1-2(12＝12*1)，2-4(20＝10*2)，5-6(26＝13*2)。其LPWMD为58。

二、本发明方法

如图6所示，本发明的片上网络应用的广度优先贪心映射方法，包括：首任务映射步骤，根据首任务后继任务的数量与片上网络节点的出度选择映射首任务的节点，节点的所述出度定义为该节点可用邻居节点的数量；后继任务映射步骤，以广度优先贪心方式对依次选择映射后继任务的节点。

1.首任务的映射

第一个任务在整个映射过程中起到了重要的作用，它决定了后继任务的通信量。首任务映射的流程如图7所示，首任务步骤用于选择最佳的节点来映射第一个任务。在这个过程中，需要同时考虑任务的拓扑结构与映射区域的结构来进行选择。首先，当一些节点的出度等于首任务后继任务的数量时，如果仅有一个这样的节点，那么该节点会被选择用来映射第一个任务；第二，如果所有节点的出度都小于首任务的后继任务数量，这时会选择出度最大的节点来映射首任务；第三，如果所有节点中最小的出度大于任务的后继任务数量，则选择拥有最小出度的节点来映射首任务；第四，在以上条件之外，处在边界或角落的节点会被优先选择，这样可以一定程度上避免映射区域的碎片化从而导致数据的传输距离增加。

2.后继任务的映射

以广度优先的贪心方法来进行后继任务的映射。首先，如果该任务的流入数据量最大，则优先将任务映射到与其前驱任务所在节点曼哈顿距离最小的节点上，流入数据量第二大的任务同样按照这个方法进行映射，整个过程持续直到所有的任务映射完毕。这样，整体的传输量就可以减少，因为大的数据传输都在相邻节点之间进行。第二，整个过程根据任务的拓扑结构，以广度优先的方式进行，即每一次都对同层的任务进行处理，并将它们按照上述的贪心方式进行映射。这样，不同层之间流入数据大的任务就不会相互影响。

具体过程如图8所示。首先，通过广度优先搜索算法对同层的任务按照流入数据量大小进行排序；第二，任务在经过排序之后被放入一个队列中；第三，队列会根据任务流入数据量的大小输出依次任务；第四，一旦一个任务被输出之后，就开始为该任务寻找合适的节点。当任务有且仅有一个前驱任务时，MD最小的节点会被选择用于映射任务，需要补充的是，如果MD最小的节点不止一个，则会选择节点出度与当前任务的直接后继任务数目最接近的节点用于映射任务。当一个任务拥有两个或以上的前驱任务时，会尝试所有可用的邻居节点并计算它们的数据传输量，选择其中数据传输量最小的一个作为局部最优节点；第五，将任务映射到节点上时，需要将其相应邻居节点的出度进行修改；第六，当队列为空时，说明该层的任务已经映射完毕，此时开始映射下层的任务；第七，整个过程持续直到所有层的任务都映射完毕后结束。

按照本映射方法将图4的6任务应用实例映射到一个2*3的方形映射区域的过程如图9所示。

三.实验结果及分析

计算了不同情况下的AWMD、LPWMD以及本映射算法的时间消耗，并与CoNA算法以及穷举方法进行了对比。

本实施例随机选择5、6、9、12任务数的应用并根据文献“Task graph generator(TGG)”([Online].Available at:http://sourceforge.net/projects/taskgraphgen/)生成不同的任务拓扑图。假设节点数量和任务数量相同并且映射区域是连续的，映射区域分为方形区域与不规则区域并通过算法随机生成不同形状的区域。这样，就可以根据任务的拓扑结构与映射区域的不同来衡量本方法的实际性能。

1.方形区域上的AWMD与LPWD

方形的映射区域是最理想的一种情况，因此先在该情况下评估映射方法的性能。首先，如图10所示，蓝色，红色，绿色柱形分别描述了穷举方法、本映射方法以及CoNA方法的AWMD在不同任务拓扑结构与映射区域下的平均值，即平均的能耗。CoNA的柱形比其他柱形要高出许多，这是因为CoNA忽视了任务的拓扑结构，且没有尝试去寻找优化方案。这种情况下，不合适的映射方案增大了数据的传输路径，并带来了更大的能耗。本映射方法的柱形与穷举算法的柱形较为接近，在一些情况下甚至相同，与CoNA相比，本映射方法降低了29-44％的AWMD，这是因为本映射方法根据任务的拓扑结构，给输入数据量大的任务高的优先级，并将其映射到与其前驱任务所在节点相近的节点上。所有的任务都以贪心的方式进行映射，这样大的数据量从短的路径上进行传输，降低了整体的功耗。

其次，图11中LPWMD代表应用的执行时间。在这种情况下，本映射方法的柱形高度仍和穷举方法的较为接近，与CoNA对应的柱形仍然较高，这是因为本映射方法并未寻找合适的映射机制，一旦选择了合适的映射机制，就能大大降低内部拥堵，令每个前驱任务快速将其数据包传输给它的后继任务，加速整个应用的执行。

2.不规则区域上的AWMD与LPWMD

本映射方法是一种NoC上通用的映射方法，本方法在映射区域不规则的情形下同样适用。首先，各种方法在不规则映射区域下的AWMD如图12所示。由于不考虑映射区域的信息，CoNA方法的AWMD较高，在图12中，CoNA的AWMD要比作为穷举方法多出22％-32％。本映射方法能够在不规则区域上寻找合适映射方案，这使其AWMD与穷举法较为接近。不管映射区域是否规则，本映射方法增加的都不多，这是因为本映射方法考虑了映射区域的信息。本映射方法优先选择边界上的节点进行首任务的映射并按照广度优先的原则根据节点之间曼哈顿距离的增加逐层映射任务。其次，图13显示了应用的执行时间，即LPWMD。本映射方法降低了在不规则区域中数据传输的内部拥堵，并减少了应用的执行时间。在图13中，和CoNA相比，本映射方法降低了约16％-42％的应用执行时间。

3.时间消耗

本映射方法是一种较为合适的应用映射算法，因为它的时间复杂度较低，最大级数不超过2，对NP-hard问题，穷举算法总是能找到最优解，但其时间复杂度为O(|n！|)，n代表一个应用的任务数，当n足够大时，穷举方法寻找最优解所消耗的时间甚至比最坏映射方案下应用的执行时间要长。最后，CoNA的时间复杂度与本映射方法相同，但由于其不考虑任务的拓扑结构与映射区域，并不能进一步减少AWMD和LPWMD。

图14中展示了三种方法的时间消耗。首先，CoNA消耗最少的时间，因为其不考虑任务的拓扑以及映射区域的结构；第二，在任务数量少的时候，穷举方法消耗的时间可以接受，但当任务数增多时，其消耗的时间增长迅速，举例而言，当应用有9个任务时，其消耗的时间达到11000ms，当任务数为12时其甚至消耗数小时来计算最优解；第三，本映射方法消耗的时间比CoNA稍多一些，但随着任务数量的增加，其消耗时间增加十分平稳。综上所述，本映射方法可以高效迅速计算出映射方案并能够降低内部拥堵。

以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术人员无需创造性劳动就可以根据本发明的构思作出诸多修改和变化。因此，凡本技术领域中技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。