一种基于NoC多核同构系统的负载判断方法的任务迁移方法

摘要

一种基于NoC多核同构系统的负载判断方法的任务迁移方法，它涉及一种基于NoC多核同构系统的负载判断方法的任务迁移方法。本发明要解决在NoC多核同构系统中任务迁移过程中任务迁移颠簸、系统运行时间开销大和迁移通信距离开销大的问题。本发明的任务迁移方法：根据基于NoC多核同构系统的负载判断方法获取重载节点列表、轻载节点列表；对节点列表中节点个数分析和获得权重矩阵；计算重载节点列表中每个节点的n步长区域，满足终止条件，得到候选轻载节点矩阵和步长矩阵；获取加权后的步长矩阵；计算得到迁移通信距离最小化的配对组合；进行任务迁移。

说明书

技术领域

本发明涉及一种基于NoC多核同构系统的负载判断方法的任务迁移方法，是申请日为2014年3月28日、申请号为2014101205282的《一种基于NoC多核同构系统的负载判断方法和基于此方法的任务迁移方法》分案申请。

背景技术

随着芯片上集成的晶体管数量越来越多，在片上多核系统中集成的核数也越来越多，从几个增加到几十个、几百个甚至几千个，开始由多核进入到了众核时代。然而，虽然多核系统或众核系统带来了处理能力上的提高，但是当多核系统中各个运算核上分配的负载多少不一致时，就会导致各个核上的功耗和温度不一样，产生热点，严重时会烧毁芯片进而使整个芯片报废，所以多核系统或众核系统面临着由于负载分布不均匀等原因而产生的功耗和热量分布方面的挑战。

无论是为了平衡系统的任务分布以降低功耗或者均衡系统的热量分布，还是为了容错的目的，一种有效的解决方法就是任务迁移。目前，任务迁移的方法已经运用到了嵌入式系统的设计和多核片上系统中，用以解决以上挑战引起的可靠性问题。但是，任务迁移解决产生的功耗和热量问题的同时，也面临着任务迁移颠簸、额外迁移通信开销等诸多问题。任务迁移颠簸是指，当重载节点把其上多余的任务迁移到轻载节点上去后导致自身变成轻载节点或者不仅使自身变成轻载节点同时还使为目的节点的轻载节点变成重载节点，这就会导致迁移出去的任务量有可能又被再次迁移，这种现象就称为任务迁移颠簸。

因此，本领域的技术人员有必要去研究任务迁移过程中所引起的这些问题，从而提出行之有效的手段用以解决在任务迁移过程中任务迁移颠簸、系统运行时间开销大和迁移通信距离开销大的问题。

发明内容

本发明是为了解决在NoC多核同构系统中任务迁移过程中任务迁移颠簸、系统运行时间开销大和迁移通信距离开销大的问题，而提供了一种基于NoC多核同构系统的负载判断方法的任务迁移方法。

本发明基于NoC多核同构系统的负载判断方法为，迁移的任务量ΔLoad满足下式，即可进行节点上的任务迁移：

其中，ΔLoad是从节点号为i的重载节点迁移到节点号为j的轻载节点的迁移的任务量；

Load_i是节点号为i的重载节点上的负载量；

Load_j是节点号为j的轻载节点上的负载量；

m是节点号为i的重载节点和节点号为j的轻载节点之间的总步长数；

v是NoC多核同构系统节点的运算速度；

t_router是单位数据通过路由器的平均时间；

t_link是单位数据通过数据链路的平均时间。

本发明的一种基于NoC多核同构系统的负载判断方法的任务迁移方法，按下述方法实现：

步骤一、获取重载节点列表、轻载节点列表

根据负载判断方法得到NoC多核同构系统中主控节点的重载节点列表、轻载节点列表；

步骤二、节点列表中节点个数分析和获得权重矩阵

a、对步骤一中得到的重载节点列表和轻载节点列表中所含有的节点的个数进行判断，根据重载节点列表中重载节点的个数和轻载节点列表中轻载节点的个数的比较可以分为三种情况：

①、重载节点列表中节点的个数大于轻载节点列表中节点的个数；

②、重载节点列表中节点的个数等于轻载节点列表中节点的个数；

③、重载节点列表中节点的个数小于轻载节点列表中节点的个数；

⑴、若主控节点的查询模块对节点列表中节点个数分析的情况为①时，则将重载节点列表中的节点和轻载节点列表中的节点整体交换，即将原轻载节点列表中的轻载节点作为分析后得到的重载节点列表中的重载节点，将原重载节点列表中的重载节点作为分析后得到的轻载节点列表中的轻载节点；

⑵、若主控节点的查询模块对节点列表中节点个数分析的情况为②或③，则重载节点列表中的重载节点直接作为分析后得到的重载节点列表中的重载节点，轻载节点列表中的轻载节点直接作为分析后得到的轻载节点列表中的轻载节点；

b、依据NoC多核同构系统中从节点运行的任务的相关性，得到权重矩阵；

步骤b中所述的任务的相关性是指不同从节点上任务之间数据通信频繁程度，所述的数据通信频繁程度越强，权重矩阵中的权重值越大；其中，所述的数据通信频繁程度越强，权重矩阵中的权重值越大；当数据通信频繁程度为0时，即不存在数据通信，则权重值为1，当数据通信频繁程度不为0时，即存在数据通信则权重值都大于1；

步骤三、获得候选轻载节点矩阵和步长矩阵

对步骤二得到的重载节点列表中的每一个重载节点求其n步长区域，n从1开始，直到满足终止条件为止，得到候选轻载节点矩阵和步长矩阵；

其中，所述的终止条件为：重载节点列表中每一个重载节点在其n步长区域内都至少有一个与之对应的候选轻载节点，若存在多个重载节点只有一个候选轻载节点与之对应的情况，则必须保证此候选轻载节点被其重载节点所独有；

所述的候选轻载节点矩阵的大小为row×column；所述的步长矩阵的大小为row×column；所述的row为步骤二中分析后得到的重载节点列表中重载节点的个数，所述的column为步骤二中分析后得到的轻载节点列表中轻载节点的个数；

步骤四、获取加权后的步长矩阵

采用步骤二得到的权重矩阵通过点乘的方式给步骤三得到的步长矩阵加权，得到加权后的步长矩阵；

其中，所述的加权后的步长矩阵的矩阵大小为row×column；所述的rowg为步骤二中分析后得到的重载节点列表中重载节点的个数，所述的column为步骤二中分析后得到的轻载节点列表中轻载节点的个数；

所述的加权后的步长矩阵的第i行存储的是步骤二得到的重载节点列表中节点号为i的重载节点到与之对应的每个候选轻载节点加权后的步长；

步骤五、计算得到迁移通信距离最小化的配对组合

由步骤三得到的候选轻载节点矩阵可得到候选轻载节点组合，在依据步骤四得到的加权后的步长矩阵可得到与候选轻载节点组合相对应的加权后的步长组合，在通过加权后的步长组合可得到任务迁移通信距离的总步长，从得到的所有任务的任务迁移的总步长中选取步长数最小的任务迁移的总步长，从而可以得到轻载节点组合，进而得到迁移通信距离最小化的重载节点和轻载节点的配对组合；

步骤六、任务迁移

NoC多核同构系统依据步骤五得到的迁移通信距离最小化的重载节点和轻载节点的配对组合进行任务迁移，即完成基于NoC多核同构系统的负载判断方法的任务迁移方法。

本发明中的NoC是指Network on Chip，中文名称为片上网络。

本发明针对系统任务迁移问题，先提出了一种能够抗任务迁移颠簸和减少系统运行时间开销的负载判断方法，然后基于此方法提出了一种能够抗任务迁移颠簸、减少系统运行时间开销和迁移通信开销的任务迁移方法。

本发明的具体实现为：具体实现分为两部分，首先提出负载判断方法，然后基于此方法提出一种任务迁移方法。对于负载判断方法是依据NoC多核同构系统的系统环境信息如系统的任务分布情况、核的执行速度、片上网络的规模以及路由器和数据链路等通信网络传输数据的能力而建立起来的。然后系统根据负载判断方法对系统中所有的节点进行负载判断，判断其为重载节点、轻载节点和适载节点三种中的一种。然后由任务迁移方法求解重载节点列表中每个节点的步长区域，接着，由每个节点步长区域中的轻载节点组成候选轻载节点矩阵，同时由步长区域的步长数组成步长矩阵并且用权重矩阵对其加权，如果满足终止条件则从加权后的步长矩阵中找出通信开销最小的那组配对组合的位置。最后从候选轻载节点矩阵中的相同位置找出相应的具有最小通信开销的轻载节点组合。终止条件为：重载节点列表中每一个重载节点在其n步长区域内都至少有一个与之对应的候选轻载节点，若存在多个重载节点只有一个候选轻载节点与之对应的情况，则必须保证此候选轻载节点被其重载节点所独有。

本发明的优点：

1、本发明提出的负载判断方法能够很好的区分NoC系统中各节点上的负载情况，并且能够抗任务迁移颠簸；

2、对于本发明提出的基于NoC多核同构系统的负载判断方法的任务迁移方法，能够减少系统任务迁移的总迁移通信开销；

3、本发明基于负载判断方法的任务迁移方法能使迁移后整个系统的执行时间减少，与现有的方法，对于同时处理同一个任务相比，时间上减少了24％。

附图说明

图1为具体实施方式二所述的NoC多核同构系统模型示意图；

图2为网络规模为5×5的片上多核同构系统的步长区域示意图；

图3为具体实施方式二所述的一种基于NoC多核同构系统的负载判断方法的任务迁移方法流程图示意图。

具体实施方式

具体实施方式一：本实施方式中一种基于NoC多核同构系统的负载判断方法为负载判断方法为迁移的任务量ΔLoad满足下式，即可进行节点上的任务迁移：

其中，ΔLoad是从节点号为i的重载节点迁移到节点号为j的轻载节点的迁移的任务量；

Load_i是节点号为i的重载节点上的负载量；

Load_j是节点号为j的轻载节点上的负载量；

m是节点号为i的重载节点和节点号为j的轻载节点之间的总步长数；

v是系统中核的运算速度；

t_router是单位数据通过路由器的平均时间；

t_link是单位数据通过数据链路的平均时间。

本实施方式中ΔLoad的单位为KB，Load_i的单位为KB，Load_j的单位为KB，v的单位为KB/s，t_router的单位为s，t_link的单位为s。

本实施方式中基于NoC多核同构系统的负载判断方法通过求出NoC多核同构系统的平均负载和一个偏移量ΔLoad能够很简单地判断一个节点是重载节点、轻载节点还是适载节点，并且只要每次迁移的任务量不超过2ΔLoad，就能够保证不会出现任务迁移颠簸。

本实施方中基于NoC多核同构系统的负载判断方法可以保证整个系统抗任务迁移颠簸和任务迁移后系统运行时间更短。

本实施方式中基于NoC多核同构系统的负载判断方法是基于抗任务迁移颠簸和任务迁移后系统运行时间更短提出的，通过以下证明：

证明1：抗任务颠簸的证明

对于M×N网络的NoC多核同构系统，首先根据整个系统的负载量与节点数，能够得到整个系统的平均负载：

其中，所述的Load_all表示NoC多核同构系统的总负载；所述的Load_ave表示NoC多核同构系统的平均负载；所述的n表示NoC多核同构系统的节点个数；

接着，假设一个负载阈值ΔLoad，给出下面三个不等式及重载节点、轻载节点和适载节点的定义：

Load>Load_ave+ΔLoad(2)

Load<Load_ave-ΔLoad(3)

Load_ave-ΔLoad≤Load≤Load_ave+ΔLoad(4)

重载节点：当本地节点上负载Load满足(2)式时，此节点就为重载节点；

轻载节点：当本地节点上负载Load满足(3)式时，此节点就为轻载节点；

适载节点：当本地节点上负载Load满足(4)式时，此节点就为适载节点；

在(2)式两边同时减去2ΔLoad有：

Load-2ΔLoad>Load_ave-ΔLoad(5)

在(3)式两边同时加上2ΔLoad有：

Load+2ΔLoad<Load_ave+ΔLoad(6)

由(5)式得出，当重载节点上迁移掉2ΔLoad负载后其为非轻载节点，由(6)式可以得出，当轻载节点上迁移来2ΔLoad负载后其为非重载节点。也即上面(5)式和(6)式说明只要迁移的任务量不超过2ΔLoad，则绝对不会出现任务迁移颠簸，所以为了抗任务迁移颠簸，每次迁移的任务量不要超过2ΔLoad。对于建立负载判断方法而言，ΔLoad的获取至关重要。

证明2：任务迁移后系统运行时间更少

以任务迁移后系统运行时间更少为导向给出获取ΔLoad的推导证明。在M×N网络的NoC多核同构系统中假设节点号为i号的节点为重载节点，节点号为j号节点为轻载节点，i≠j且i，j∈[1,M×N]。由重载节点的定义以及(2)式，可设重载节点上的负载量为：

Load_i＝K_i+ΔLoad，K_i>Load_ave(7)

同理，由轻载节点的定义以及(3)式，可设轻载节点上的负载量为：

Load_j＝K_j-ΔLoad，K_j<Load_ave(8)

(7)式和(8)式中的K_i和K_j分别为比平均负载大和比平均负载小的负载量，目的在于把(2)式和(3)式两不等式变成等式形式。如果重载节点上的负载量很大，迁出一个ΔLoad后其依然为重载节点，则这次迁移过后其根据自身的监测模块监测到本地节点依然为重载节点时，依然会把本地节点的节点号发送到主控节点的重载节点列表中去，所以只要每次监测到其为重载节点则就会一直迁移，直到其变成适载节点为止。同理，对于轻载节点，若迁进一个ΔLoad后其依然为轻载节点，则这次迁移过后其根据自身的检测模块监测到本地节点依然为轻载节点时依然会把本地节点的节点号发送到主控节点的轻载节点列表中去，所以只要每次监测到其为轻载节点则就会一直迁移，直到其变成适载节点为止。所以在此我们设每一次从重载节点i往轻载节点j只迁移ΔLoad；

则负载ΔLoad在重载节点i上执行完所需要的时间为

t_i＝t_执行i+t_等待i，

其中，所述的t_执行i为节点i单独执行负载ΔLoad所需时间；

t_等待i为节点i单独执行负载K_i所需时间，也即执行负载ΔLoad之前其所需要等待的时间；

在轻载节点j上执行完所需要的时间为

t_j＝t_执行j+t_等待j；

t执行j为节点j单独执行负载ΔLoad所需时间，t_等待j为j号轻载节点单独执行负载K_j-ΔLoad所需时间，也即执行负载ΔLoad之前其所需要等待的时间。

设t迁移ij为负载ΔLoad从重载节点i迁移到轻载节点j的迁移时间开销。则如果满足下述(9)式，则意味着迁移之后比迁移之前在时间开销上减少了。

t_i>t_迁移ij+t_j(9)

把t_i和t_j表达式带入(9)中得：

t_执行i+t_等待i>t_迁移ij+t_执行j+t_等待j(10)

由于是同构多核系统，所以每一个核(节点)的运算速度一样。因此，对于执行相同的负载ΔLoad，其执行时间也相等，即t_执行i＝t_执行j。所以(10)式化简得：

t_等待i>t_迁移ij+t_等待j(11)

设每个核的执行速度为v，则有：

通过(12)式和(13)式可以计算出t_等待i和t_等待j，接下来只要能够通过某种方式求的t_迁移ij，则就可以确定ΔLoad。

t_迁移ij不仅跟通信网络(链路和路由器)有关，还与通信距离有关。通信距离由节点之间的曼哈顿距离表示。此处定义数据走过一个路由器和一条链路为一步长通信距离。设一单位数据通过一链路所需时间为t_link，通过一路由器所需时间为t_router。不考虑网络拥塞情况，并且t_link和t_router可以由系统信息统计分析得到。所以单位数据的一步长通信距离时间开销为：

t_hop＝t_router+t_link(14)

设m为任务迁移的源节点i到目的节点j的步长数，则从重载节点i迁移ΔLoad负载到轻载节点j的迁移时间开销为：

t_迁移ij＝m×ΔLoad×t_hop＝m×ΔLoad×(t_router+t_link)(15)

把(12)、(13)和(15)代入(11)中得：

由(16)式可以得出：

由(7)式和(8)式可得：

K_i-K_j＝(Load_i-ΔLoad)-(Load_j+ΔLoad)

＝Load_i-Load_j-2ΔLoad(18)

将(18)代入(17)中可得：

至此就求得了ΔLoad的取值条件，只要满足(19)式的ΔLoad就能保证任务迁移之后系统运行的时间比迁移之前少，并且不会出现任务迁移颠簸。

具体实施方式二：结合图3，本实施方式中一种基于NoC多核同构系统的负载判断方法的任务迁移方法，按下述方法实现：

步骤一、获取重载节点列表、轻载节点列表

根据负载判断方法得到NoC多核同构系统中主控节点的重载节点列表、轻载节点列表；

步骤二、节点列表中节点个数分析和获得权重矩阵

a、对步骤一中得到的重载节点列表和轻载节点列表中所含有的节点的个数进行判断，根据重载节点列表中重载节点的个数和轻载节点列表中轻载节点的个数的比较可以分为三种情况：

①、重载节点列表中节点的个数大于轻载节点列表中节点的个数；

②、重载节点列表中节点的个数等于轻载节点列表中节点的个数；

③、重载节点列表中节点的个数小于轻载节点列表中节点的个数；

⑴、若主控节点的查询模块对节点列表中节点个数分析的情况为①时，则将重载节点列表中的节点和轻载节点列表中的节点整体交换，即将原轻载节点列表中的轻载节点作为分析后得到的重载节点列表中的重载节点，将原重载节点列表中的重载节点作为分析后得到的轻载节点列表中的轻载节点；

⑵、若主控节点的查询模块对节点列表中节点个数分析的情况为②或③，则重载节点列表中的重载节点直接作为分析后得到的重载节点列表中的重载节点，轻载节点列表中的轻载节点直接作为分析后得到的轻载节点列表中的轻载节点；

b、依据NoC多核同构系统中从节点运行的任务的相关性，得到权重矩阵；

步骤b中所述的任务的相关性是指不同从节点上任务之间数据通信频繁程度，所述的数据通信频繁程度越强，权重矩阵中的权重值越大；其中，所述的数据通信频繁程度越强，权重矩阵中的权重值越大；当数据通信频繁程度为0时，即不存在数据通信，则权重值为1，当数据通信频繁程度不为0时，即存在数据通信则权重值都大于1；

步骤三、获得候选轻载节点矩阵和步长矩阵

对步骤二得到的重载节点列表中的每一个重载节点求其n步长区域，n从1开始，直到满足终止条件为止，得到候选轻载节点矩阵和步长矩阵；

其中，所述的终止条件为：重载节点列表中每一个重载节点在其n步长区域内都至少有一个与之对应的候选轻载节点，若存在多个重载节点只有一个候选轻载节点与之对应的情况，则必须保证此候选轻载节点被其重载节点所独有；

所述的候选轻载节点矩阵的大小为row×column；所述的步长矩阵的大小为row×column；所述的row为步骤二中分析后得到的重载节点列表中重载节点的个数，所述的column为步骤二中分析后得到的轻载节点列表中轻载节点的个数；

步骤四、获取加权后的步长矩阵

采用步骤二得到的权重矩阵通过点乘的方式给步骤三得到的步长矩阵加权，得到加权后的步长矩阵；

其中，所述的加权后的步长矩阵的矩阵大小为row×column；所述的row为步骤二中分析后得到的重载节点列表中重载节点的个数，所述的column为步骤二中分析后得到的轻载节点列表中轻载节点的个数；

所述的加权后的步长矩阵的第i行存储的是步骤二得到的重载节点列表中节点号为i的重载节点到与之对应的每个候选轻载节点加权后的步长；

步骤五、计算得到迁移通信距离最小化的配对组合

由步骤三得到的候选轻载节点矩阵可得到候选轻载节点组合，在依据步骤四得到的加权后的步长矩阵可得到与候选轻载节点组合相对应的加权后的步长组合，在通过加权后的步长组合可得到任务迁移通信距离的总步长，从得到的所有任务的任务迁移的总步长中选取步长数最小的任务迁移的总步长，从而可以得到轻载节点组合，进而得到迁移通信距离最小化的重载节点和轻载节点的配对组合；

步骤六、任务迁移

NoC多核同构系统依据步骤五得到的迁移通信距离最小化的重载节点和轻载节点的配对组合进行任务迁移，即完成基于NoC多核同构系统的负载判断方法的任务迁移方法。

本实施方式中的NoC多核同构系统模型，如图1所示。从图1中可以看出此系统模型节点之间采用的是主从模式，一个节点作为管理节点即图中的主控节点，其他节点作为运算节点也即从节点。整个NoC多核同构系统由主控节点和从节点两大部分组成。主控节点中由轻载节点列表、重载节点列表、查询模块和迁移模块组成。重载节点列表和轻载节点列表记录着整个系统节点的负载情况，若某一节点为重载节点，则就把其编号也即节点号发送给主控节点，存于重载节点列表中，若某一节点为轻载节点，则就把其编号发送给主控节点，存于轻载节点列表中，适载节点不发送；当查询模块查询到重载节点列表和轻载节点列表同时不为空时，则反馈信息给迁移模块，由迁移模块进行任务迁移计算，得出在此重载节点和轻载节点的情况下最优迁移配对关系进行任务迁移。最后把已经进行过迁移的重载节点和轻载节点从相应的列表中删除。

从节点由负载监测模块、工作任务表和迁移任务表三部分组成。负载监测模块负责监测本地节点的负载信息，当根据负载判断方法监测到本地节点负载过重时就把负载过重部分的任务存于迁移任务表中并且把本地节点的节点号发送给主控节点，然后存于主控节点重载节点列表中，而工作任务表存储将在本地节点上执行的任务；当监测到本地节点负载过轻时就把本地节点的节点号发送给主控节点，然后存于主控节点轻载节点列表中。

当轻载节点列表和重载节点列表都得到后，然后运用本实施例提出一种基于NoC多核同构系统的负载判断方法的任务迁移方法就可以为重载节点从整个系统角度找出通信开销最小的目的轻载节点。接着，把得到的具有最小通信开销的配对组合发给每一个从节点。最后，从节点就可以依据这些配对组合进行任务迁移。

本实施方式中步骤三中终止条件的意义在于：在保证最小通信开销配对存在的条件下使得计算量最少。

本实施例中把分析后得到的重载节点列表中的节点统称为重载节点，把轻载节点列表中的节点统称为轻载节点。

具体实施方式三：本实施方式与具体实施方式二的不同之处是，步骤一中所述的负载判断方法为迁移的任务量ΔLoad满足下式，即可进行节点上的任务迁移：

其中，ΔLoad是从节点号为i的重载节点迁移到节点号为j的轻载节点的迁移的任务量；

Load_i是节点号为i的重载节点上的负载量；

Load_j是节点号为j的轻载节点上的负载量；

m是节点号为i的重载节点和节点号为j的轻载节点之间的步长总数；

v是系统中核的运算速度；

t_router是单位数据通过路由器的平均时间；

t_link是单位数据通过数据链路的平均时间。

本实施方式中ΔLoad的单位为KB，Load_i的单位为KB，Load_j的单位为KB，v的单位为KB/s，t_router的单位为s，t_link的单位为s。其他与具体实施方式二相同。

具体实施方式四：本实施方式与具体实施方式二或三的不同之处是，步骤二b中所述的权重矩阵的矩阵大小为row×column；其中，所述的row为步骤二中分析后得到的重载节点列表中重载节点的个数，所述的column为步骤二中分析后得到的轻载节点列表中轻载节点的个数。其他与具体实施方式二或三相同。

具体实施方式五：本实施方式与具体实施方式二至四之一的不同之处是，步骤三中所述的步长区域的计算：计算步骤二分析后得到的重载节点列表中每个节点的n步长区域，方法如下：

选取节点号为i的重载节点，则节点号为i的重载节点的一步长节点号为i±1和i±N，而节点号为i±1和i±N的节点形成了节点号为i的重载节点的一步长区域；

节点号为i的重载节点的二步长节点号为一步长区域中的一步长节点号±1和一步长节点号±N，而节点号为一步长节点号±1和一步长节点号±N的节点形成了节点号为i的重载节点的二步长区域；

依次类推，节点号为i的重载节点的n步长区域由n-1步长区域中n-1步长节点号±1和n-1步长节点号±N的节点形成；

其中，步骤三中所述的n≥2；

N是网络规模为M×N的片上多核同构系统的列数，M是网络规模为M×N片上多核同构系统的行数。

在本实施方式中：

a、当节点号为i的重载节点处于网络规模为M×N片上多核同构系统的网络左边界上时，此时节点号为i的重载节点的步长区域由存在的节点组成，所述的存在的节点的节点号为i+1，i±N；

b、当节点号为i的重载节点处于网络规模为M×N片上多核同构系统的网络右边界上时，此时节点号为i的重载节点的步长区域由存在的节点组成，所述的存在的节点的节点号为i-1，i±N；

c、当节点号为i的重载节点处于网络规模为M×N片上多核同构系统的网络上边界上时，此时节点号为i的重载节点的步长区域由存在的节点组成，所述的存在的节点的节点号为i±1，i+N；

d、当节点号为i的重载节点处于网络规模为M×N片上多核同构系统的网络下边界上时，此时节点号为i的重载节点的步长区域由存在的节点组成，所述的存在的节点的节点号为i±1，i-N；

e、当节点号为i的重载节点处于网络规模为M×N片上多核同构系统的网络左边界的上顶点时，此时节点号为i的重载节点的步长区域由存在的节点组成，所述的存在的节点的节点号为i+1，i+N；

f、当节点号为i的重载节点处于网络规模为M×N片上多核同构系统的网络左边界的下顶点时，此时节点号为i的重载节点的步长区域由存在的节点组成，所述的存在的节点的节点号为i+1，i-N；

g、当节点号为i的重载节点处于网络规模为M×N片上多核同构系统的网络右边界的上顶点时，此时节点号为i的重载节点的步长区域由存在的节点组成，所述的存在的节点的节点号为i-1，i+N；

h、当节点号为i的重载节点处于网络规模为M×N片上多核同构系统的网络右边界的下顶点时，此时节点号为i的重载节点的步长区域由存在的节点组成，所述的存在的节点的节点号为i-1，i-N。其他与具体实施方式二至四之一相同。

具体实施方式六：本实施方式与具体实施方式二至五之一的不同之处是，步骤三中所述的候选轻载节点矩阵的第i行用以存储步骤二中分析后得到的重载节点列表中节点号为i的重载节点，以及在满足终止条件时，与之对应的所有候选轻载节点的节点号。其他与具体实施方式二至五之一相同。

具体实施方式七：本实施方式与具体实施方式二至六之一的不同之处是，步骤二中分析后得到的重载节点列表中重载节点在其n步长区域中包含的轻载节点组成；其中，所述的轻载节点为步骤二中所述的分析后得到的轻载节点列表中的轻载节点。其他与具体实施方式二至六之一相同。

具体实施方式八：本实施方式与具体实施方式二至七之一的不同之处是，步骤三中所述的步长矩阵的第i行第j列用以存储步骤二中得到的重载节点列表中节点号为i的重载节点到与候选轻载节点矩阵中第i行第j列的轻载节点的步长数。其他与具体实施方式二至七之一相同。