一种基于人工势场法的异构众核任务调度的路由机制

技术领域

本发明涉及一种基于人工势场法的异构众核任务调度的路由机制，属于信 息技术领域。

背景技术

随着多核技术向众核技术的过度，不仅计算节点逐渐增多(上百或上千个)， 处理器的复杂度也在不断增强。为了不断提高处理器芯片的性能，同时不打破 摩尔定律的相关规定，半导开发商将越来越多的处理单元放到同一块处理器芯 片上。其中，包括内核和各种共享资源等。因此，异构众核结构的研究将会成 为未来的焦点。在这样的背景下，对异构众核下任务调度问题进行分析具有重 要的意义，在异构众核结构中，一般会包含有众多相同的处理核(普核)，同时 包含具有特定能力(加速器/访存)的处理核(异核)。当异核作为共享资源的 时候，会收到从多个普核发送来的任务请求。因此，互连网络需要按照节点距 离、处理能力、阻塞情况等动态分配异核的处理资源给特定的普核的任务请求， 从而实现动态任务的合理调度和负载均衡，提高处理的性能。

2012年Hanmin Park和Kiyoung Choi在NOCS会议上发表论文 Position-Based Weighted Round-Robin Arbitration for Equality of Service  in Many-Core Network-on-Chips，文章中认为源节点与共享节点进行通信的概 率取决于该源节点所处的位置。其调度方式如下所示：图1为一个局部网络， 图2为一个router(路由器)的具体端口。该任务调度中认定router中每个端 口被允许通信的概率取决于该节点所处的位置。因此，当每个源节点的位置确 定之后，其对应router中的三个端口的概率也确定了。即该节点访问某些共享 节点的概率被确定了。这种任务调度方法，没有充分考虑共享节点的任务处理 能力，一旦源节点访问了一个忙碌的共享节点，会导致网络的拥塞。可见，在 异构众核结构中，该任务调度算法并没有能达到共享资源的平衡使用。

发明内容

本发明要解决的技术问题是：为克服上述问题，提供一种动态平衡调度任 务的基于人工势场法的异构众核任务调度的路由机制。

本发明解决其技术问题所采用的技术方案是：

一种基于人工势场法的异构众核任务调度的路由机制，包括以下步骤：

S1：将每个共享处理核作为一个引力源建立引力场；

S2：通过势力场传播逻辑单元计算，得出普通处理核在所述引力场中东南 西北四个方向分别实时受到的合力；

S3：将所述普通处理核分别受到的合力进行对比，沿着合力较大的方向进 行路由。

优选地，所述步骤S1具体包括：根据所述共享处理核的参数确定其引力源 大小，规定所述引力场中力的传播方向的规律，并建立所述引力场中力的传播 衰减规则。

优选地，所述步骤S2具体包括：所述普通处理核或共享处理核受到的北南 西东方向的力分别记为iF_N、iF_S、iF_W、iF_E，其分别对应的衰减系数依次为δ_N、δ_S、 δ_W、δ_E，所述普通处理核或共享处理核传递出的北南西东方向力分别记为oF_N、 oF_S、oF_W、oF_E，通过所述势力场传播逻辑单元进行计算得出：

向南合力oF_S＝N+iF_W+iF_N+iF_E-δ_W-δ_N-δ_E-σ，衰减系数δ_s＝δ_NATIVE+δ_W+δ_N+δ_E；

向北合力oF_N＝N+iF_W+iF_S+iF_E-δ_W-δ_S-δ_E-σ,衰减系数δ_N＝δ_NATIVE+δ_W+δ_S+δ_E；

向东合力oF_E＝N+iF_W-δ_W-σ，衰减系数δ_E＝δ_NATIVE+δ_W；

向西合力oF_W＝N+iF_E-δ_E-σ，衰减系数δ_W＝δ_NATIVE+δ_E；

其中，当计算共享处理核时，N为该共享处理核引力源引力大小，N对应的 衰减系数为δ_NATIVE，当计算普通处理核时，N＝0；当路由器虚通道缓冲正常时σ为 0，当路由器虚通道缓冲较慢时产生额外衰减数值σ。

优选地，所述步骤S3具体包括：如果所述普通处理核只受一个力，则根据 该力的方向进行路由,同时将该力的反方向屏蔽；如果所述普通处理核受到多 个力的吸引，则选择合力最大的方向进行路由，当合力最大的方向有多个引力 源时，则再需要进行下一阶段路由，同时将合力最大方向的反方向屏蔽。

优选地，当所述普通处理核其中一个方向的力的屏蔽码被标记上，则认为 该方向的力为0，不再参与路由。

优选地，所述共享处理核的参数包括所述共享处理核的处理能力和缓冲区 的空满情况。

优选地，所述“力的传播方向的规律”具体为：力先在X维度上传递，然 后在Y维度上传递。

优选地，所述“引力场中力的传播衰减规则”具体为：在NOC中力每传播 过一个普通处理核或共享处理核就衰减一次，如果在经过一个普通处理核或共 享处理核时路由器缓冲区使用率超过阈值，则额外衰减一个数值，力的大小如 果衰减到最小值，则不再衰减。

一种采用了以上所述的基于人工势场法的异构众核任务调度的路由机制的 异构众核处理器。

本发明的有益效果是：(1)本发明所述一种基于人工势场法的异构众核任务 调度的路由机制，使得在任务调度的过程中可以根据所有共享处理核的处理负 载程度变换，来调节普通处理核的请求数据包的调度，将任务优先调度给处理 负载比较小的共享处理核，使得共享处理核的任务负载比较均衡，从而实现动 态任务的合理调度和负载均衡，提高处理的性能，减小阻塞情况。

(2)本发明在所述普通处理核其中一个方向的力的屏蔽码被标记上，则认 为该方向的力为0，不再参与路由，籍此可以防止因为力场动态变化导致普通处 理核的请求数据包在NOC中无效地来回颠簸而始终无法到达目的地，防止抖动 的产生。

附图说明

下面结合附图和实施例对本发明进一步说明。

图1是现有技术中一个局部网络的结构示意图；

图2是现有技术中一个路由器端口的结构示意图；

图3是本发明所述路由机制的流程图；

图4是本发明所述势力场传播逻辑单元的结构示意图；

图5是本发明一个实施例的受力分析图；

图6是本发明另一个实施例的受力分析图；

图7是本发明另一个实施例的受力分析图。

具体实施方式

现在结合附图对本发明作进一步详细的说明。这些附图均为简化的示意图， 仅以示意方式说明本发明的基本结构，因此其仅显示与本发明有关的构成。

下面提供本发明所述一种基于人工势场法的异构众核任务调度的路由机制 的具体实施方式。

实施例1

本发明所述一种基于人工势场法的异构众核任务调度的路由机制，本机制 主要应用于异构众核结构中，NOC(Network-on-Chip，片上网络)互联网络动 态分配普通处理核(普核)如何选择共享处理核(异核)，如图3所示，其包括 以下步骤：

S1：本发明引入人工势场法，将每个共享处理核作为一个引力源建立引力 场，所述引力场中，共享处理核和普通处理核呈阵列均匀分部，其之间连线构 成网格状框架，所以所述引力场中可能存在多个引力源，所述引力源吸引其他 普通处理核访问；

S2：所述引力场中每个所述普通处理核受到四周引力源的吸引，当其中一 个普通处理核有数据包需要处理时，由于作为引力源的共享处理核的处理能力 会实时变换，当共享处理核处理能力降低其引力就会减小，因此需要通过势力 场传播逻辑单元计算出普通处理核在东南西北四个方向分别实时受到的合力；

S3：然后再将该普通处理核四个方向分别受到的合力进行对比大小，沿着 合力较大的方向进行路由，具体的为步骤S2中计算出的合力结果由所述势力场 传播逻辑单元信号反馈给本地路由器，本地路由器在着合力较大的方向进行路 由，因此本发明使得在任务调度的过程中可以根据所有共享处理核的处理负载 程度变换，来调节普通处理核的请求数据包的调度，将任务优先调度给处理负 载比较小的共享处理核，使得共享处理核的任务负载比较均衡，从而实现动态 任务的合理调度和负载均衡，提高处理的性能，减小阻塞情况，并防止了路由 抖动的产生。

实施例2

在实施例1所述所述一种基于人工势场法的异构众核任务调度的路由机制 的基础上，所述步骤S1具体包括：根据所述共享处理核的参数确定其引力源大 小，规定所述引力场中力的传播方向的规律，并建立所述引力场中力的传播衰 减规则。

如图4所示，所述步骤S2具体包括：优选的所述共享处理核在所述引力场 中向东南西北四个方向发射力场数据包，力的传递在本实施例中通过力场数据 包的传递来表现的，所述普通处理核或其他共享处理核都会接收所述力场数据 包并继续发送，所述普通处理核或共享处理核接收到的力场数据包中的北南西 东力记为iF_N、iF_S、iF_W、iF_E，其分别对应的衰减系数依次为δ_N、δ_S、δ_W、δ_E， 衰减系数采用现有技术，根据力场进行设定，所述普通处理核或共享处理核传 递出的力场数据包中的北南西东力记为oF_N、oF_S、oF_W、oF_E，通过所述势力场传 播逻辑单元进行计算得出：

向南合力oF_S＝N+iF_W+iF_N+iF_E-δ_W-δ_N-δ_E-σ，衰减系数δ_s＝δ_NATIVE+δ_W+δ_N+δ_E；

向北合力oF_N＝N+iF_W+iF_S+iF_E-δ_W-δ_S-δ_E-σ,衰减系数δ_N＝δ_NATIVE+δ_W+δ_S+δ_E；

向东合力oF_E＝N+iF_W-δ_W-σ，衰减系数δ_E＝δ_NATIVE+δ_W；

向西合力oF_W＝N+iF_E-δ_E-σ，衰减系数δ_W＝δ_NATIVE+δ_E；

其中，当计算共享处理核时，N为该共享处理核引力源引力大小，N对应的 衰减系数为δ_NATIVE，当计算普通处理核时，N＝0。

下面以最简单位于一个共享处理核东侧的普通处理核为例进行计算。

所述普通处理核N收到来自共享处理核M的输入iFw，如图5所示。其他三 个方向iFe，iFs，iFn均为0。因为它不是引力源，所以N＝0。

该普通处理核N输出的力计算如下：

oFe＝iFw-δw；

oFs＝iFw-δw；

oFn＝iFw-δw；

oFw＝0(该核右边无共享核，所以这个方向拉力为0)；

对应的衰减系数：

δe＝δw

δs＝δw

δn＝δw

δw＝0

这类普通处理核和共享处理核在同一水平线上，除了继续传递水平输入的 力场数据包，还会上下传播oFn和oFs的力场数据包。

下面再以位于一个共享处理核南面(下面)的普通处理核为例，如图6所 示：

该普通处理核L接收到该共享处理核K的输入iFn，其他三个方向iFe，iFs， iFw均为0。因为它不是力源，所以N＝0。

该普通处理核L输出的力为：

oFs＝iFn-δn(力由北向南传递)。

oFw＝0；

oFn＝0；

oFe＝0；

对应的衰减系数：

δs＝δn；

δw＝0；

δn＝0；

δe＝0；

因此可以看出受垂直方向(即南北方向)的力的普通处理核只传递垂直方 向的力。

而所述引力场中有多个引力源时，其实就是单个引力源的线性叠加。

此外，若路由器虚通道缓冲较慢，则需要额为衰减一定数值σ，虚通道缓冲 正常时σ为0；具体虚通道缓冲较慢时，它可以根据不通情况进行设置，具体如 下：

(1)σ为固定值，当缓冲区半满状态时，σ＝1；

(2)σ值根据缓冲区的情况线性变化。比如半满时σ为1，全满时σ为2；

(3)σ可以根据距离来调节。在距离共享处理核有3跳时，设σ＝0，3跳 到10跳之间，σ＝1，10跳以外，σ＝2；依此规律，离共享核越近，阻力就很 小，离共享核越远，阻力就越大。

所述步骤S3具体包括：如果所述普通处理核只受一个力，则根据该力的方 向进行路由，同时，将移动方向的反方向屏蔽；如果所述普通处理核受到多个 力的吸引，则选择多个方向中合力最大的方向进行路由，如果合力最大的方向 有多个引力源，则再需要进行下一阶段路由，同时，将移动方向的反方向屏蔽， 此种情况下，此合力有由多个引力源作用的，其移动方向上有多个引力源，因 此需要先沿此合力方向移动，在合力方向与多个引力源所在的线的交叉点时， 再进行阶段路由，也就是第二次路由，由此阶段路由再次判断朝此多个引力源 中哪一个引力源进行路由，当然如果第二次路由的移动方向的合力还是由多个 引力源组成的，那将依照以上规律进行第三次路由，根据具体情况而定，也有 可能进行第四次、第五次、第N次，都依照以上规律。

如果所述普通处理核其中一个方向的力的屏蔽码被标记上，则认为该方向 的力为0，不再参与路由决策，籍此可以防止因为力场动态变化导致普通处理核 的请求数据包在NOC中无效地来回颠簸而始终无法到达目的地。

所述共享处理核参数包括所述共享处理核的处理能力和缓冲区的空满情 况，N表示引力源大小，所以其受共享处理核参数影响，具体比如共享处理核 具有两路处理能力，每路有缓冲区5个buffer，则可以设引力源的引力大小为 2*5＝10。当来到一个事务，储存在缓冲区中。比如缓冲区中有四个事务待处理， 则认为引力的大小降为6。若十个缓冲全部填满，则认为共享核已经不具备处理 能力，则可以认为N＝0。

实施例3

在以上实施例所述的一种基于人工势场法的异构众核任务调度的路由机制 的基础上，提供一个具体的实施例，如图7所示，图中有四个共享处理核，其 作为四个引力源，分别为引力源A、B、C、D，其大小都为10，优选的本实施例 中，所述“力的传播方向的规律”具体为：力先在X维度上传递，然后在Y维 度上传递，所以只有在有引力源的一行，才有左或者右的力，否则只有上下两 个方向有拉力，力场的建立是先x轴再y轴，那么路由包的进行方向就是先y 轴，后x轴方向。

优选的所述“引力场中力的传播衰减规则”具体为：在NOC中力每传播过 一个普通处理核或共享处理核就衰减一次，如果在经过一个普通处理核或共享 处理核时路由器缓冲区使用率超过阈值，则额外衰减一个数值。力的大小如果 衰减到规定的最小值，则不再衰减，以上所述阈值、衰减的数值和最小值都是 根据NOC中核的数目、NOC路由器的缓冲大小和所述共享处理核的处理能力来具 体设定。

在以上的规律和原则下，通过实施例2中的公式计算，得出图7中作为普 通处理核的节点E的四个引力源的合力分别为F_a＝3，F_b＝4，F_c＝9，F_d＝3，设所有 的力衰减系数为1，每跳一次(即力经过一个处理核)就减1，若A点本身力为 6，则跳到E点要3跳，每次衰减1，所以有F_a＝3。

即当E需要访问共享资源时，会沿着合力较大的方向到达共享处理核C。

下面提供一个解释阶段路由的实施例，在图7的基础上假设F_a＝6，F_b＝7，F_c＝9， F_d＝3则普通处理核受到的向上的合力F_a+F_b为13大于F_c＝9，则普通处理核的请 求数据包先从E点出发，当决定向上(向北)走时，就将向下(即向南)方向 的力通过掩码进行屏蔽，因此，之后就会只受到向上的拉力，只会向上路由， 不会再返回向下。当沿纵向到达到与AB平行时，需要再做一次路由，如果B点 力大，就需要朝B点前进，同时，将运动方向反方向的掩码位也设置为1，从而 只会受B点引力拉动，直达B点后结束。分阶段路由可以根据力场情况，动态 调整路由方向。但这种方法容易引起数据包来回颠簸，所以增加了掩码机制(即 上述将路由方向的反方向进行屏蔽)。

实施例4

一种异构众核处理器，其采用了以上实施例所述的基于人工势场法的异构 众核任务调度的路由机制。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计 算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结 合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包 含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、 CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品 的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/ 或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或 方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式 处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机 或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流 程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备 以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的 指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流 程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使 得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处 理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个 流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基 本创造性概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要 求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。