多处理器系统的节点路由方法、控制器及多处理器系统

摘要

本发明提供一种多处理器系统的节点路由方法、控制器及多处理器系统，方法包括：获知多处理器系统内节点之间的可用链路的状态，所述多处理器系统包括第一子网，所述第一子网包括相连的至少两个节点；当所述第一子网中至少有一个链路发生故障时，重新选定所述第一子网中所有节点之间的可用链路，以使所述第一子网中的节点利用所述重新选定的可用链路路由报文；重新选定的可用链路为所述第一子网中，每个节点上除去与故障链路的维度序号相同的链路之后剩余的链路，其中，维度序号为一条链路在两端节点的编号，一条链路在两端节点的编号相同。

权利要求

1.一种多处理器系统的节点路由方法，其特征在于，包括：

获知所述多处理器系统内节点之间的可用链路的状态，所述多处理器系统包括第一子网，所述第一子网包括相连的至少三个节点；

当所述第一子网中至少有一个链路发生故障时，重新选定所述第一子网中所有节点之间的可用链路，以使所述第一子网中的节点利用所述重新选定的可用链路路由报文；所述重新选定的可用链路为所述第一子网中，每个节点上除去与故障链路的维度序号相同的链路之后剩余的链路，其中，维度序号为一条链路在两端节点的编号，所述链路在两端节点的编号相同。

2.根据权利要求1所述的方法，其特征在于，所述获知多处理器系统内节点之间的可用链路的状态，包括：监测得到所述多处理器系统内节点之间的可用链路的状态。

3.根据权利要求1或2所述的方法，其特征在于，所述多处理器系统还包括第二子网，所述第二子网中的链路数量及其维度序号与所述第一子网中的链路数量及维度序号相同，所述第一子网与所述第二子网通过第n+1维的链路相连，其中，n为所述第一子网和第二子网中链路的最大维度；

所述方法还包括：

选定所述第一子网中的节点到所述第二子网的可用链路，以使所述第一子网中的节点将所述报文路由到所述第二子网；所述第一子网中的节点到所述第二子网的可用链路，包括第n+1维的链路及所述第二子网中的可用链路，所述第二子网中的可用链路为所述第二子网中，各节点除去与所述第一子网路由所述报文所使用的链路维度序号相同的链路后，剩余的链路。

4.根据权利要求3所述的方法，其特征在于，所述第n+1维的链路，为所述报文的发送节点与目的节点之间的路由的中间链路。

5.根据权利要求4所述的方法，其特征在于，所述第一子网路由所述报文使用的链路为前n/2维的链路，所述第二子网路由所述报文使用的链路为后n/2维的链路。

6.一种多处理器系统的路由策略控制器，其特征在于，包括：

状态获知模块，用于获知所述多处理器系统内节点之间的可用链路的状态，所述多处理器系统包括第一子网，所述第一子网包括相连的至少三个节点；

链路选定模块，用于当所述第一子网中至少有一个链路发生故障时，重新选定所述第一子网中所有节点之间的可用链路，以使所述第一子网中的节点利用所述重新选定的可用链路路由报文；重新选定的可用链路为所述第一子网中，每个节点上除去与故障链路的维度序号相同的链路之后剩余的链路，其中，维度序号为一条链路在两端节点的编号，一条链路在两端节点的编号相同。

7.根据权利要求6所述的路由策略控制器，其特征在于，所述状态获知模块具体用于监测得到多处理器系统内节点之间的可用链路的状态。

8.根据权利要求6或7所述的路由策略控制器，其特征在于，所述多处理器系统还包括第二子网，所述第二子网中的链路数量及其维度序号与所述第一子网中的链路数量及维度序号相同，所述第一子网与所述第二子网通过第n+1维的链路相连，其中，n为所述第一子网和第二子网中链路的最大维度；

所述装置还包括：

链路选定模块还用于选定所述第一子网中的节点到所述第二子网的可用链路，以使所述第一子网中的节点将所述报文路由到所述第二子网；所述第一子网中的节点到所述第二子网的可用链路，包括第n+1维的链路及所述第二子网中的可用链路，所述第二子网中的可用链路为所述第二子网中，各节点除去与所述第一子网路由所述报文所使用的链路维度序号相同的链路后，剩余的链路。

9.根据权利要求8所述的路由策略控制器，其特征在于，所述第n+1维的链路，为所述报文的发送节点与目的节点之间的路由的中间链路。

10.根据权利要求9所述的路由策略控制器，其特征在于，所述第一子网路由所述报文使用的链路为前n/2维的链路，所述第二子网路由所述报文使用的链路为后n/2维的链路。

11.一种多处理器系统，其特征在于，包括上述权利要求6-10任意一项所述的多处理器系统的路由策略控制器和至少三个节点。

说明书

多处理器系统的节点路由方法、控制器及多处理器系统

技术领域

[0001] 本发明涉及计算机技术，尤其涉及一种多处理器系统的节点路由方法、路由策略控制器及多处理器系统。

背景技术

[0002] 大规模的多处理器系统中，容错是指在部件失效情况下系统内处理器联网运作的能力，容错实现技术往往是以多处理器系统通信性能的大大降低为代价的。

[0003] 通常，多处理器系统内的节点通信时，由路由策略控制器制定路由策略提供给待发送信息的节点，使得待发送信息的节点沿最短路由转发报文。

[0004] 报文在从一个节点发送另一个节点的过程中，在到达目的节点之前通常要经过多个中间节点，由于路由策略控制器制定的路由策略，只允许报文使用最短路由转发，当最短路由中的某一链路发生故障时，报文就以循环的方式互相等待从而发生死锁。这样，包含在死锁配置内的所有报文将永远被阻塞。

发明内容

[0005] 本发明提供一种多处理器系统的节点路由方法、控制器及多处理器系统，用于实现容错路由。

[0006] 本发明的第一个方面是提供一种多处理器系统的节点路由方法，包括：

[0007] 获知多处理器系统内节点之间的可用链路的状态，所述多处理器系统包括第一子网，所述第一子网包括相连的至少两个节点；

[0008] 当所述第一子网中至少有一个链路发生故障时，重新选定所述第一子网中所有节点之间的可用链路，以使所述第一子网中的节点利用所述重新选定的可用链路路由报文；重新选定的可用链路为所述第一子网中，每个节点上除去与故障链路的维度序号相同的链路之后剩余的链路，其中，维度序号为一条链路在两端节点的编号，一条链路在两端节点的编号相同。

[0009] 本发明的另一个方面是提供一种多处理器系统的路由策略控制器，包括：

[0010] 状态获知模块，用于获知多处理器系统内节点之间的可用链路的状态，所述多处理器系统包括第一子网，所述第一子网包括相连的至少两个节点；

[0011] 链路选定模块，用于当所述第一子网中至少有一个链路发生故障时，重新选定所述第一子网中所有节点之间的可用链路，以使所述第一子网中的节点利用所述重新选定的可用链路路由报文；重新选定的可用链路为所述第一子网中，每个节点上除去与故障链路的维度序号相同的链路之后剩余的链路，其中，维度序号为一条链路在两端节点的编号，一条链路在两端节点的编号相同。

[0012] 本发明的又一个方面是提供一种多处理器系统，包括上述多处理器系统的路由策略控制器和至少两个节点。

[0013] 本发明实施例提供的多处理器系统的节点路由方法、控制器及多处理器系统的技术效果是：通过获知多处理器系统内节点之间的可用链路的状态，并当至少有一个链路发生故障时，从每个节点上除去与故障链路的维度序号相同的链路之后剩余的链路中重新选定可用链路，利用重新选定的可用链路重新组织起新的路由，恢复系统通信，实现了容错路由。

附图说明

[0014] 图1为本发明实施例提供的多处理器系统的节点路由方法的流程图；

[0015] 图2为本发明实施例提供的多处理器系统的节点路由方法中多个子网的示意图；

[0016] 图3为本发明实施例一提供的多处理器系统的节点路由方法中的网络连接示意图；

[0017] 图4为本发明实施例一提供的多处理器系统的节点路由方法中链路故障后的可用链路示意图；

[0018] 图5为本发明实施例二提供的多处理器系统的节点路由方法中的网络连接示意图；

[0019] 图6为本发明实施例二提供的多处理器系统的节点路由方法中链路故障后的可用链路示意图；

[0020] 图7为本发明实施例提供的多处理器系统的路由策略控制器的结构示意图；

[0021] 图8为本发明实施例提供的多处理器系统的结构示意图。

具体实施方式

[0022] 图1为本发明实施例提供的多处理器系统的节点路由方法的流程图。本实施例中路由策略控制器为执行主体，如图1所示，该方法包括：

[0023] 步骤11、获知多处理器系统内节点之间的可用链路的状态，该多处理器系统包括第一子网，该第一子网包括相连的至少两个节点。

[0024] 如路由策略控制器可监测得到多处理器系统内节点之间的可用链路的状态。或者多处理器系统内节点之间的可用链路的状态由专门的模块进行监控，路由策略控制器通过该专门的模块获知多处理器系统内节点之间的可用链路的状态，如正常、故障等。其中，一个节点可包括两个CPU。

[0025] 步骤12、当该第一子网中至少有一个链路发生故障时，重新选定该第一子网中所有节点之间的可用链路，以使该第一子网中的节点利用该重新选定的可用链路路由报文；重新选定的可用链路为该第一子网中，每个节点上除去与故障链路的维度序号相同的链路之后剩余的链路，其中，维度序号为一条链路在两端节点的编号，一条链路在两端节点的编号相同。

[0026] 上述步骤11、步骤12可由路由策略控制器执行。

[0027] 其中，该多处理器系统还可包括第二子网，所述第二子网中的链路数量及其维度序号与所述第一子网中的链路数量及维度序号相同，该第一子网与该第二子网通过第n+1维的链路相连，其中，n为该第一子网和第二子网中链路的最大维度；当第一子网与该第二子网之间只有一个n+1维的链路时，第一子网的节点均通过该条第n+1维的链路与第二子网相连；当第一子网与该第二子网之间有n个第n+1维的链路时，第一子网的每个节点分别均通过一条n+1维的链路与第二子网相连。相应地，本发明实施例提供的多处理器系统的节点路由方法还可包括：

[0028] 选定该第一子网中的节点到该第二子网的可用链路，以使该第一子网中的节点将该报文路由到该第二子网；该第一子网中的节点到该第二子网的可用链路，包括第n+1维的链路及该第二子网中的可用链路，该第二子网中的可用链路为该第二子网中，各节点除去与该第一子网路由该报文所使用的链路维度序号相同的链路后，剩余的链路。

[0029] 优选地，第n+1维的链路，为该报文的发送节点与目的节点之间的路由的中间链路，以进一步提高容错能力。从发送节点经过一些中间节点，再到达目的节点有多跳，通常大于等于3跳，这些中间节点的链路就称为中间链路。

[0030] 优选地，该第一子网路由该报文使用的链路为前n/2维的链路，该第二子网路由该报文使用的链路为后n/2维的链路，以进一步提高容错能力。

[0031] 如图2所示，本实施例中，多处理器系统可包括子网A和子网B。

[0032] 假设子网A、子网B均是n维网络，即有n个维度，两个子网之间通过第n+1维，即维度Dn+1，也即维度序号为n+1的链路连接。子网A、子网B分别具有维度D1，D2…Dn，Dn+1，如果维度Dn+1的所有链路，即维度序号为n+1的链路，也即第n+1维链路全部断开，则两个子网不可互相通信。

[0033] 任何一个维度如维度Dn+1，即维度序号为n+1的链路，也即第n+1维链路上发生链路损坏，但只要保持相同维度下的任一根链路可用，就可以构造无死锁容错路由。

[0034] 要构造无死锁容错路由，维度为Dn+1的链路，即维度序号为n+1的链路，也即第n+1维链路必须位于维度编号路由的中间。其中，维度编号路由即用链路的维度来表示路由。如D1→D2→…Dn→Dn+1，即表示从维度序号为1的链路到维度序号为n+1的链路组成的路由。

[0035] 如果按照n+1维的维度编号路由方式构造路由表，则维度为Dn+1的链路不可以位于维度编号路由的最后一维，因为在最后一步有的点仅通过维度为Dn+1的链路不可达，也就是说维度编号路由D1→D2→…Dn→Dn+1的方式不可行。同理由于链路是双向的，维度为Dn+1的链路也不可以位于维度编号路由的第一维，因为在第一步后有的点仅通过维度为Dn+1的链路不可达。也就是说维度编号路由Dn+1→D1→D2→…Dn的方式不可行。

[0036] 较优的方式是将每个子网的n个维度分成两个n/2维度，将Dn+1维置于维度编号路由的中间D1→D2→…Dn/2→Dn+1→Dn/2+1→Dn，也就是在A网络中只利用前n/2维度路由，在B网络中只利用后n/2维度通信，相互之间剔除维度相同的链路，也即维度序号相同的链路。这样，就很容易构建容错的无死锁路由。

[0037] 本发明实施例提供的多处理器系统的节点路由方法通过探索和制定一套容易实现的无死锁可容错的路由机制，确保了容错机系统互联架构的高可靠性，解决了处理器系统中，如果不对内部网络的路由算法和路由机制进行设置，很容易形成死锁的问题，尤其是在网络上出现某单节点或多节点断路的情况下，无死锁的路由算法可能非常复杂和多变的问题。

[0038] 实施例一

[0039] 以具有8节点网络的多处理器系统为例对本发明实施例提供的方法做进一步详细说明。

[0040] 其中，8节点网络的维度数量可以是1~7中的任意一个，维度的数量不同，网络结构及路由步长也所有不同，如下表所示。

[0041]维度 构成的网络形式 网络可用路由的最大步长
1维 1D总线 7
2维 2D环网 4
3维 3D立方体 3
4维 超3D 2
5维 超3D 2
6维 超3D 2
7维 全互联 1

[0042] 以7个维度的8节点网络为例，8节点网络所属多处理器系统中的路由策略控制器将网络中的每个节点上链路进行编号，得到维度序号。

[0043] 如图3所示，该子网均包括0、1、2、3、4、5、6、7共8个节点，在该子网中每个节点均与其他7个节点相连，可以认为每个节点在所在的子网内部有有7个维度，得到每个节点的维度序号为[X，Y，Z，J，K，L，M]。路由策略控制器对每个节点的维度进行编号，得到每个节点的维度序号为[X，Y，Z，J，K，L，M]，从图3可以看出，维度序号也即一条链路在两端节点的编号，且一条链路在两端节点的编号相同。如节点7的第J个维度与节点3的第J个维度属于同一条链路，即节点7与节点3之间的链路。

[0044] 当该网络中的某一或某些链路故障时，路由策略控制器重新选定所有节点之间的可用链路，重新选定的可用链路为每个节点上除去与故障链路的维度序号相同的链路之后剩余的链路。

[0045] 其中，链路故障的信息可由路由策略控制器实时监控获知，也可通过其他方式提供给路由策略控制器。

[0046] 假设节点7上维度序号为Y、Z、J所在的三条链路损坏，则路由策略控制器认为其他所有节点上维度序号为Y、Z、J所在的三条链路均不可用，仅将剩余维度序号的链路作为可用链路。如图4所示，每个节点可用链路剩下了维度序号为X、K、L、M的链路，路由策略控制器制定新的路由时，仅选择使用维度序号为X、K、L、M的链路中的链路，能构成最大步长为2的无死锁路由。

[0047] 并且，对于任意3条以内数量的链路故障，根据上述方法在最坏情况如发生故障的3条链路刚好分别属于3个不同的维度，且最多也只能属于3个不同的路由维度的情况下，每个节点剩余的链路仍然至少可以构成一个4维超3D网络。假设剩余的4个维度的维度序号为X、Y、Z、J，则仍能够根据X→Y→Z→J的维度序号方式构成最大步长为2的无死锁路由。对于任意4条链路故障，根据上述方法在最坏情况下，仍然能构成3D立方体网，做出最大步长为3的无死锁维序路由；对于任意5条链路故障，根据上述方法在最坏情况下，仍然能构成2D环网，做出最大步长为4的无死锁维序路由。

[0048] 实施例二

[0049] 以具有16节点多维网络的多处理器系统为例，对本发明实施例提供的方法做进一步详细说明。

[0050] 如图5所示，本实施例中，多处理器系统包括第一子网和第二子网。

[0051] 其中，第一子网为左边节点0~节点7连接成的网络，第二子网为右边节点0~节点7连接成的网络。且每个子网内部均为7维网络，即第一子网与第二子网中每个节点都具有维度序号为X、Y、Z、J、K、L、M的7条链路与其他节点相连，也可以说每个节点的维度为[X，Y，Z，J，K，L，M]。第一子网与第二子网通过维度序号为I的链路相连，其中维度序号为I的链路即上述第n+1维链路，本实施例中，每个子网的最大维度数据为7，所以第n+1维链路即为第8维链路。

[0052] 本实施例中，第一子网中的路由方法、第二子网中的路由方法与图1所示实施例及上述实施例一提供的方法相同。此外，第一子网中路由时的可用链路的维度序号与第二子网路由时链路维度序号不同。也就是说，将报文从第一子网路由到第二子网时，先制定第一子网的路由策略，再制定第二子网的路由策略。制定第二子网中的路由策略时，在第二子网中剔除第一子网中已经用到的维度序号相同的链路。反过来，将报文从第二子网路由到第一子网时，先制定第二子网的路由策略，再制定第一子网的路由策略。制定第二子网中的路由策略时，在第一子网中剔除第二子网中已经用到的维度序号相同的链路。

[0053] 如图6所示，第一子网的可用链路为维度序号为X、Z、K、M，或者说第一子网用到的维度为X、Z、K、M，第二子网的可用链路为维度序号为Y、J、L，或者说第二子网用到的维度为Y、J、L。

[0054] 并且，第一子网与第二子网之间采用任意一个维度序号为I的链路相连，第一子网与第二子网通过维度序号为I的链路相连，其中维度序号为I的链路即上述第n+1维链路，本实施例中，每个子网的最大维度数据为7，所以第n+1维链路即为第8维链路。共有8个维度序号为I的链路可用。维度序号为I的链路在制定的第一子网到第二子网或第二子网到第一子网的路由中，属于中间链路。其中，第一子网到第二子网或第二子网到第一子网的路由由路由策略控制器制定。从发送节点经过一些中间节点，再到达目的节点有多跳，通常大于等于3跳，这些中间节点的链路就称为中间链路。

[0055] 如假设维度序号为I的链路中有任意7根链路损坏，只要有1根维度序号为I的链路完好，则至少可以根据上述路由方法得到无死锁路由：X→Z→K→M→I→Y→J→L。

[0056] 采用上述较优的方式路由时，由于每个子网有7个维度，7维不可以整除2，因此第一子网分成一个4维网络和一个3维网络，其中3维网络被剔除，如图6所示，剩余4维网络，即维度序号为X、Z、K、M的链路，剩下的4维网络的最大步长是3。第二子网分成一个3维网络和一个4维网络，其中4维网络被剔除，如图6所示，剩余3维网络，即维度序号为Y、J、L的链路，剩下的3维网络的最大步长是2，再加上第I维的1步，整个容错路由最大步长为6（正常情况下是3）。

[0057] 本发明实施例中，不仅遵循避免环路、多个虚拟通道等机制来避免死锁问题，而且针对容错机当前互联架构设计，提出针对性的带容错的路由机制，能更好地解决链路断路、以及避免死锁问题。

[0058] 本发明实施例提供的方法可以类推到其他网络中，用于构造可容错的无死锁路由，可以保证在多条链路断开的情况下，仍然能够根据已有的算法快速算出全系统的无死锁路由。

[0059] 本领域普通技术人员可以理解：实现上述各方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成。前述的程序可以存储于一计算机可读取存储介质中。该程序在执行时，执行包括上述各方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

[0060] 图7为本发明实施例提供的多处理器系统的路由策略控制器的结构示意图该装置包括：状态获知模块71及链路选定模块72。

[0061] 状态获知模块71用于获知多处理器系统内节点之间的可用链路的状态，该多处理器系统包括第一子网，该第一子网包括相连的至少两个节点。如该状态获知模块71可具体用于监测得到多处理器系统内节点之间的可用链路的状态。

[0062] 链路选定模块72用于当该第一子网中至少有一个链路发生故障时，重新选定该第一子网中所有节点之间的可用链路，以使该第一子网中的节点利用该重新选定的可用链路路由报文；重新选定的可用链路为该第一子网中，每个节点上除去与故障链路的维度序号相同的链路之后剩余的链路，其中，维度序号为一条链路在两端节点的编号，一条链路在两端节点的编号相同。

[0063] 该多处理器系统还包括第二子网，所述第二子网中的链路数量及其维度序号与所述第一子网中的链路数量及维度序号相同，该第一子网与该第二子网通过第n+1维的链路相连，其中，n为该第一子网和第二子网中链路的最大维度；

[0064] 可选地，该链路选定模块还用于选定该第一子网中的节点到该第二子网的可用链路，以使该第一子网中的节点将该报文路由到该第二子网；该第一子网中的节点到该第二子网的可用链路，包括第n+1维的链路及该第二子网中的可用链路，该第二子网中的可用链路为该第二子网中，各节点除去与该第一子网路由该报文所使用的链路维度序号相同的链路后，剩余的链路。

[0065] 其中，第n+1维的链路为该报文的发送节点与目的节点之间的路由的中间链路。从发送节点经过一些中间节点，再到达目的节点有多跳，通常大于等于3跳，这些中间节点的链路就称为中间链路。

[0066] 该第一子网路由该报文使用的链路为前n/2维的链路，该第二子网路由该报文使用的链路为后n/2维的链路。

[0067] 图8为本发明实施例提供的多处理器系统的结构示意图。如图8所示，多处理器系统包括路由策略控制器81和至少两个节点82。路由策略控制器81可为上述实施例提供的任意一种多处理器系统的路由策略控制器。节点82与路由策略控制器81相连，路由策略控制器81为节点82提供可用链路，以保证多处理器系统中的节点82能够根据路由策略控制器81提供的可用链路路由报文，而避免环状死锁。

[0068] 通过以上的实施方式的描述，所属领域的技术人员可以清楚地了解到本发明可以用硬件实现，或软件实现，或固件实现，或它们的组合方式来实现。当使用软件实现时，可以将上述功能存储在计算机可读介质中或作为计算机可读介质上的一个或多个指令或代码进行传输。计算机可读介质包括计算机存储介质和通信介质，其中通信介质包括便于从一个地方向另一个地方传送计算机程序的任何介质。存储介质可以是计算机能够存取的任何可用介质。以此为例但不限于：计算机可读介质可以包括RAM、ROM、EEPROM、CD-ROM或其他光盘存储、磁盘存储介质或者其他磁存储设备、或者能够用于携带或存储具有指令或数据结构形式的期望的程序代码并能够由计算机存取的任何其他介质。此外。任何连接可以适当的成为计算机可读介质。例如，如果软件是使用同轴电缆、光纤光缆、双绞线、数字用户线（DSL）或者诸如红外线、无线电和微波之类的无线技术从网站、服务器或者其他远程源传输的，那么同轴电缆、光纤光缆、双绞线、DSL或者诸如红外线、无线和微波之类的无线技术包括在所属介质的定影中。如本发明所使用的，盘（Disk）和碟（disc）包括压缩光碟（CD）、激光碟、光碟、数字通用光碟（DVD）、软盘和蓝光光碟，其中盘通常磁性的复制数据，而碟则用激光来光学的复制数据。上面的组合也应当包括在计算机可读介质的保护范围之内。

[0069] 最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。