均衡路由的方法、网络互连系统、交叉开关装置及芯片

摘要

本文公开均衡路由的方法、网络互连系统、交叉开关装置及芯片。均衡路由的方法包括：N个路由器接收路由请求并缓存在各自的缓存池中；其中，N个路由器的输出端口与M个仲裁器的输入端口交叉连接，形成N*M条路由路径；N≥2；M≥2；在连续N个处理周期内，N个路由器从各自的缓存池中筛选路由请求并发送至对应的仲裁器；其中，不同的路由器筛选的路由请求发送至不同的仲裁器以使任意一个仲裁器在一个处理周期内至多接收到一个路由器发送的路由请求。本文的技术方案能够提高路由转发的效率和网络吞吐量。

说明书

技术领域

本文涉及但不限于集成电路技术领域，尤其涉及一种均衡路由的方法、网络互连系统、交叉开关装置及芯片。

背景技术

随着芯片工艺的不断发展和多核技术的广泛应用，片上的网络互联结构越来越普遍，而且资源占比也在逐渐提高。吞吐量的提升和资源的优化，成为优秀的网络互联结构的设计难点，也是重要的设计指标。

在网络互联结构方案中，路由器将入口的数据按照既定的规则传递到适当的端口。但是仅仅实现路由器的基本功能，难以提升数据吞吐量。因此以基础路由器实现的网络互联结构，远远达不到高通量的要求。

发明内容

第一方面，本公开提供了一种均衡路由的方法，包括：

N个路由器接收路由请求并缓存在各自的缓存池中；其中，N个路由器的输出端口与M个仲裁器的输入端口交叉连接，形成N*M条路由路径；N≥2；M≥2；

在连续N个处理周期内，N个路由器从各自的缓存池中筛选路由请求并发送至对应的仲裁器；其中，不同的路由器筛选的路由请求发送至不同的仲裁器以使任意一个仲裁器在一个处理周期内至多接收到一个路由器发送的路由请求。

第二方面，本公开提供了一种网络互连系统，包括N个路由器和M个仲裁器；N个路由器的输出端口与M个仲裁器的输入端口交叉连接，形成N*M条路由路径；N≥2；M≥2；

N个路由器配置为接收路由请求并缓存在各自的缓存池中，在连续N个处理周期内从各自的缓存池中筛选路由请求并发送至对应的仲裁器；其中，不同的路由器筛选的路由请求发送至不同的仲裁器以使任意一个仲裁器在一个处理周期内至多接收到一个路由器发送的路由请求。

第三方面，本公开提供了一种交叉开关装置，包括N个输入端口、M个输出端口和上述网络互连系统；N个输入端口与N个路由器的输入端口一一连接，M个输出端口与M个仲裁器的输出端口一一连接；N≥2；M≥2。

第四方面，本公开提供了一种芯片，包括上述网络互连系统。

本公开实施例提供的均衡路由的方法，路由器通过设置缓存池可以为之后的路由请求筛选提供选择源。在连续N个处理周期内，N个路由器从各自的缓存池中筛选路由请求并发送至对应的仲裁器，由于不同的路由器筛选的路由请求发送至不同的仲裁器，因此任意一个仲裁器在一个处理周期内至多接收到一个路由器发送的路由请求，路由器通过对路由请求的筛选避免了路由请求在某些仲裁器处拥堵，通过均衡多个仲裁器的输入路由，提高了路由转发的效率和网络吞吐量。

附图说明

附图用来提供对本公开技术方案的理解，并且构成说明书的一部分，与本公开的实施例一起用于解释本公开的技术方案，并不构成对本公开技术方案的限制。

图1为本公开实施例提供的一种均衡路由的方法流程图；

图2为本公开实施例提供的一种网络互连系统的结构示意图；

图3为本公开实施例提供的另一种网络互连系统的结构示意图；

图4为本公开实施例一种交叉开关装置的结构示意图；

图5为本公开实施例另一种交叉开关装置的结构示意图。

具体实施方式

本申请描述了多个实施例，但是该描述是示例性的，而不是限制性的，并且对于本领域的普通技术人员来说显而易见的是，在本申请所描述的实施例包含的范围内可以有更多的实施例和实现方案。尽管在附图中示出了许多可能的特征组合，并在具体实施方式中进行了讨论，但是所公开的特征的许多其它组合方式也是可能的。除非特意加以限制的情况以外，任何实施例的任何特征或元件可以与任何其它实施例中的任何其他特征或元件结合使用，或可以替代任何其它实施例中的任何其他特征或元件。

本申请包括并设想了与本领域普通技术人员已知的特征和元件的组合。本申请已经公开的实施例、特征和元件也可以与任何常规特征或元件组合，以形成由所附权利要求限定的独特的发明方案。任何实施例的任何特征或元件也可以与来自其它发明方案的特征或元件组合，以形成另一个由所附权利要求限定的独特的发明方案。因此，应当理解，在本申请中示出和/或讨论的任何特征可以单独地或以任何适当的组合来实现。因此，除了根据所附权利要求及其等同替换所做的限制以外，实施例不受其它限制。此外，可以在所附权利要求的保护范围内进行各种修改和改变。

如图1所示，本公开实施例提供了一种均衡路由的方法，包括：

步骤S10，N个路由器接收路由请求并缓存在各自的缓存池中；其中，N个路由器的输出端口与M个仲裁器的输入端口交叉连接，形成N*M条路由路径；N≥2；M≥2；

步骤S20，在连续N个处理周期内，N个路由器从各自的缓存池中筛选路由请求并发送至对应的仲裁器；其中，不同的路由器筛选的路由请求发送至不同的仲裁器以使任意一个仲裁器在一个处理周期内至多接收到一个路由器发送的路由请求。

路由器一般具有一个或多个输入端口，多个输出端口，作用是按照既定规则将数据传递到适当的输出端口。仲裁器一般具有多个输入端口，一个或多个输出端口，作用是将多个输入端口到达的数据按照既定规则传递到适当的输出端口。现有技术中，每个路由器独立地接收路由请求并发送至仲裁器，由于多个路由器连接至相同的一组仲裁器，因此任意一个仲裁器可能在同一时刻接收到不同的路由器发送的路由请求，由于仲裁器一次只能处理一个路由请求，得不到处理的路由请求会使得仲裁器拥堵，而另一些仲裁器可能由于收不到路由请求而处于空闲，影响了网络的吞吐量。假设路由器的输入端口一直有路由请求到达，路由器的输出端口一直不拥堵。最差的情况是，在某一时刻，N个路由器都路由到同一个仲裁器，此时整个网络互联结构的效率是1/M。最好的情况是，在某一时刻，N个路由器恰好有M个请求路由到M个仲裁器，此时整个网络互联结构的效率是100%。综上，传统的网络互联结构的效率是1/M~100%的区间，且效率不稳定。若截取一个足够长的时间段，该网络互联结构的效率曲线会趋于正态分布，平均效率为(1/M + 1)/2。

上述实施例提供的均衡路由的方法，路由器通过设置缓存池可以为之后的路由请求筛选提供选择源。在连续N个处理周期内，N个路由器从各自的缓存池中筛选路由请求并发送至对应的仲裁器，由于不同的路由器筛选的路由请求发送至不同的仲裁器，因此任意一个仲裁器在一个处理周期内至多接收到一个路由器发送的路由请求，路由器通过对路由请求的筛选避免了路由请求在某些仲裁器处拥堵，通过均衡多个仲裁器的输入路由，提高了路由转发的效率和网络吞吐量。

在一些示例性的实施方式中，N个路由器从各自的缓存池中筛选路由请求并发送至对应的仲裁器，包括：

N个路由器进行排序：

在第1个处理周期内，第1个路由器从缓存池中任意选择一个路由请求并发送至对应的仲裁器，将M个仲裁器在第1个处理周期内的使用情况信息发送至第2个路由器；

在第i个处理周期内，第i个路由器从第i-1个路由器获取M个仲裁器在前i-1个处理周期内的使用情况信息，根据所述使用情况信息确定缓存池中将被屏蔽的路由请求和未被屏蔽的路由请求，将未被屏蔽的路由请求加入候选路由请求集合；如果候选路由请求集合非空，则从所述候选路由请求集合中任意选择一个未被屏蔽的路由请求并发送至对应的仲裁器；当i

其中，将被屏蔽的路由请求是指路由至前i-1个处理周期内已被使用的仲裁器的路由请求，未被屏蔽的路由请求是指路由至前i-1个处理周期内未被使用的仲裁器的路由请求。

在一些示例性的实施方式中， N个路由器从各自的缓存池中筛选路由请求并发送至对应的仲裁器，还可以包括：

在第i个处理周期内，当i=N时将M个仲裁器在N个处理周期内的使用情况信息发送至第1个路由器。最后一个路由器将信息发送给第一个路由器，可以使得多个路由器的动作一致。第1个路由器接收到第N个路由器发送的信息后可以不做处理。

在一些示例性的实施方式中，N个路由器进行排序，包括：

如果N个处理周期不是第一轮的处理周期，则上轮排序后的第k个路由器作为本轮排序的第k+1个路由器，上轮排序后的第N个路由器作为本轮排序的第1个路由器；1≤k≤N-1；或者

如果N个处理周期不是第一轮的处理周期，则上轮排序后的第i个路由器作为本轮排序的第i-1个路由器，上轮排序后的第1个路由器作为本轮排序的第N个路由器；2≤i≤N；

其中，每N个处理周期构成一轮。

通过一轮一轮的排序，每个路由器都可以有机会优先筛选路由请求，使多个路由器公平转发路由请求，这种公平有利于整个网络互联结构区域平衡。

在一些示例性的实施方式中，N个路由器进行排序，包括：

如果N个处理周期是第一轮处理周期，则N个路由器按照预设的顺序进行排序。

在一些示例性的实施方式中，N个路由器之间通过通信接口首尾相连成环状结构，任意一个路由器包括一个输入接口和一个输出接口，所述环状结构上的任意一个路由器通过输入接口连接上一级路由器的输出接口，通过输出接口连接下一级路由器的输入接口。

假设有5个路由器R1、R2、R3、R4和R5首尾连接成环状接口，R1的输出接口与R2的输入接口连接，R2的输出接口与R3的输入接口连接，R3的输出接口与R4的输入接口连接，R4的输出接口与R5的输入接口连接，R5的输出接口与R1的输入接口连接。

第一次排序时，5个路由器中的任意一个路由器可以作为排序后的首个路由器，假设第一次排序R1作为首个路由器，第一次排序为R1、R2、R3、R4和R5。

第一次排序后每一次排序可以使首个路由器在环状结构上顺序后移一个位置或前移一个位置，也即第二次排序时，可以按照R2、R3、R4、R5、R1的顺序排序，或者按照R5、R1、R2、R3、R4的顺序排序。

在一些示例性的实施方式中，M个仲裁器的使用情况信息记录在仲裁器掩码中；

其中，所述仲裁器掩码是二进制序列，所述仲裁器掩码中的M位与M个仲裁器一一对应，任意一个二进制位的数值指示该二进制位对应的仲裁器是否已被使用。

在一些示例性的实施方式中，第i个路由器将M个仲裁器在前i个处理周期内的使用情况信息发送至第i+1个路由器，包括：

当i=1时，第1个路由器先重新设置仲裁器掩码的所有位，重新设置后的仲裁器掩码指示所有的仲裁器均未被使用，当第1个路由器从缓存池中任意选择一个路由请求并发送至对应的仲裁器后，第1个路由器将仲裁器掩码中第1个路由器使用的仲裁器对应的二进制位的数值进行修改以指示对应的仲裁器已被使用，第1个路由器将修改后的仲裁器掩码发送至第2个路由器；

当2≤i≤N-1时，如果候选路由请求集合非空，则第i个路由器修改接收到的第i-1个路由器发送的仲裁器掩码，将所述接收到的仲裁器掩码中第i个路由器使用的仲裁器对应的二进制位的数值进行修改以指示对应的仲裁器已被使用；第i个路由器将修改后的仲裁器掩码发送至第i+1个路由器；如果候选路由请求集合为空，则保持接收到的第i-1个路由器发送的仲裁器掩码不变；第i个路由器将接收到的仲裁器掩码发送至第i+1个路由器。

在一些示例性的实施方式中，当仲裁器掩码中的二进制位的数值为“0”时，代表该二进制位对应的仲裁器未被使用，当仲裁器掩码中的二进制位的数值为“1”时，代表该二进制位对应的仲裁器已被使用。

假设5个路由器（R1、R2、R3、R4、R5）与5个仲裁器（Z1、Z2、Z3、Z4、Z5）交叉连接。排序后路由器的顺序为：R1、R2、R3、R4、R5，路由器R1是首个路由器，路由器R5是最后一个路由器。仲裁器掩码是5位二进制序列a5a4a3a2a1，二进制位a5对应仲裁器Z5，二进制位a4对应仲裁器Z4，二进制位a3对应仲裁器Z3，二进制位a2对应仲裁器Z2，二进制位a1对应仲裁器Z1。

在第一个处理周期内，首个路由器R1从缓存池中任意选择一个路由请求发送至仲裁器，假设路由器R1使用了仲裁器Z5，则将仲裁器掩码中的二进制位a5的数值设置为“1”，路由器R1修改后的仲裁器掩码为10000，路由器R1将修改后的仲裁器掩码（10000）发送给第二个路由器R2。

在第二个处理周期内，第二个路由器R2接收到仲裁器掩码（10000），获知5个仲裁器中的仲裁器Z5已被使用，因此从缓存池中筛选路由请求时，将路由至被使用的仲裁器Z5的路由请求作为被屏蔽的路由请求，将路由至未被使用的仲裁器Z1、Z2、Z3、Z4的路由请求作为未被屏蔽的路由请求，将未被屏蔽的路由请求加入候选路由请求集合，假设候选路由请求集合非空，则从所述候选路由请求集合中任意选择一个未被屏蔽的路由请求并发送至对应的仲裁器。假设路由器R2使用了仲裁器Z3，则将仲裁器掩码中的二进制位a3的数值设置为“1”，路由器R2修改后的仲裁器掩码为10100，路由器R2将修改后的仲裁器掩码（10100）发送给第三个路由器R3。

在第三个处理周期内，第三个路由器R3接收到仲裁器掩码（10100），获知5个仲裁器中的仲裁器Z5和Z3已被使用，因此从缓存池中筛选路由请求时，将路由至被使用的仲裁器Z5和Z3的路由请求作为被屏蔽的路由请求，将路由至未被使用的仲裁器Z1、Z2、Z4的路由请求作为未被屏蔽的路由请求，将未被屏蔽的路由请求加入候选路由请求集合，假设候选路由请求集合为空，则保持接收到的仲裁器掩码不变，路由器R3将接收到的仲裁器掩码（10100）发送给第四个路由器R4。

在第四个处理周期内，第四个路由器R4接收到仲裁器掩码（10100），获知5个仲裁器中的仲裁器Z5和Z3已被使用，因此从缓存池中筛选路由请求时，将路由至被使用的仲裁器Z5和Z3的路由请求作为被屏蔽的路由请求，将路由至未被使用的仲裁器Z1、Z2、Z4的路由请求作为未被屏蔽的路由请求，将未被屏蔽的路由请求加入候选路由请求集合，假设候选路由请求集合非空，则从所述候选路由请求集合中任意选择一个未被屏蔽的路由请求并发送至对应的仲裁器。假设路由器R4使用了仲裁器Z2，则将仲裁器掩码中的二进制位a2的数值设置为“1”，路由器R4修改后的仲裁器掩码为10110，路由器R4将修改后的仲裁器掩码（10110）发送给第五个路由器R5。

在第五个处理周期内，第五个路由器R5接收到仲裁器掩码（10110），获知5个仲裁器中的仲裁器Z2、Z5和Z3已被使用，因此从缓存池中筛选路由请求时，将路由至被使用的仲裁器Z5、Z3和Z2的路由请求作为被屏蔽的路由请求，将路由至未被使用的仲裁器Z1和Z4的路由请求作为未被屏蔽的路由请求，将未被屏蔽的路由请求加入候选路由请求集合，假设候选路由请求集合非空，则从所述候选路由请求集合中任意选择一个未被屏蔽的路由请求并发送至对应的仲裁器。假设路由器R5使用了仲裁器Z1，则将仲裁器掩码中的二进制位a1的数值设置为“1”，路由器R5修改后的仲裁器掩码为10111，路由器R5可以将修改后的仲裁器掩码（10111）发送给第一个路由器R1，路由器R5也可以不发送修改后的仲裁器掩码（10111）。

如图2所示，本公开实施例提供了一种网络互连系统，包括N个路由器和M个仲裁器；N个路由器的输出端口与M个仲裁器的输入端口交叉连接，形成N*M条路由路径；

N个路由器配置为接收路由请求并缓存在各自的缓存池中，在连续N个处理周期内从各自的缓存池中筛选路由请求并发送至对应的仲裁器；其中，不同的路由器筛选的路由请求发送至不同的仲裁器以使任意一个仲裁器在一个处理周期内至多接收到一个路由器发送的路由请求。

上述实施例提供的网络互连系统包括N个路由器和M个仲裁器，每个路由器通过设置缓存池将接收到的路由请求缓存在缓存池中以为之后的路由请求筛选提供选择源。在连续N个处理周期内，N个路由器从各自的缓存池中筛选路由请求并发送至对应的仲裁器，由于不同的路由器筛选的路由请求发送至不同的仲裁器，因此任意一个仲裁器在一个处理周期内至多接收到一个路由器发送的路由请求，路由器通过对路由请求的筛选避免了路由请求在某些仲裁器处拥堵，通过均衡多个仲裁器的输入路由，提高了路由转发的效率和网络吞吐量。

如图3所示，在一些示例性的实施方式中，路由器包括：缓存模块和路由筛选模块；

N个路由器的缓存模块，配置为接收路由请求并缓存在各自的缓存池中；

N个路由器的路由筛选模块，配置为从各自的缓存池中筛选路由请求并发送至对应的仲裁器；其中，不同的路由器筛选的路由请求发送至不同的仲裁器以使任意一个仲裁器在一个处理周期内至多接收到一个路由器发送的路由请求。

在一些示例性的实施方式中，N个路由器的路由筛选模块，配置为采用以下方式从各自的缓存池中筛选路由请求并发送至对应的仲裁器：

N个路由器进行排序：

在第1个处理周期内，第1个路由器的路由筛选模块从缓存池中任意选择一个路由请求并发送至对应的仲裁器，将M个仲裁器在第1个处理周期内的使用情况信息发送至第2个路由器；

在第i个处理周期内，第i个路由器的路由筛选模块从第i-1个路由器的的路由筛选模块获取M个仲裁器在前i-1个处理周期内的使用情况信息，根据所述使用情况信息确定缓存池中将被屏蔽的路由请求和未被屏蔽的路由请求，将未被屏蔽的路由请求加入候选路由请求集合；如果候选路由请求集合非空，则从所述候选路由请求集合中任意选择一个未被屏蔽的路由请求并发送至对应的仲裁器；当i

其中，将被屏蔽的路由请求是指路由至前i-1个处理周期内已被使用的仲裁器的路由请求，未被屏蔽的路由请求是指路由至前i-1个处理周期内未被使用的仲裁器的路由请求。

在一些示例性的实施方式中，N个路由器的路由筛选模块，配置为采用以下方式对N个路由器进行排序：

如果N个处理周期不是第一轮的处理周期，则上轮排序后的第k个路由器作为本轮排序的第k+1个路由器，上轮排序后的第N个路由器作为本轮排序的第1个路由器；1≤k≤N-1；或者

如果N个处理周期不是第一轮的处理周期，则上轮排序后的第i个路由器作为本轮排序的第i-1个路由器，上轮排序后的第1个路由器作为本轮排序的第N个路由器；2≤i≤N；其中，每N个处理周期构成一轮。

在一些示例性的实施方式中，M个仲裁器的使用情况信息记录在仲裁器掩码中；

其中，所述仲裁器掩码是二进制序列，所述仲裁器掩码中的M位与M个仲裁器一一对应，任意一个二进制位的数值指示该二进制位对应的仲裁器是否已被使用。

在一些示例性的实施方式中，第i个路由器的路由筛选模块，配置为采用以下方式将M个仲裁器在前i个处理周期内的使用情况信息发送至第i+1个路由器：

当i=1时，第1个路由器的路由筛选模块先重新设置仲裁器掩码的所有位，重新设置后的仲裁器掩码指示所有的仲裁器均未被使用，当第1个路由器的路由筛选模块从缓存池中任意选择一个路由请求并发送至对应的仲裁器后，第1个路由器的路由筛选模块将仲裁器掩码中第1个路由器使用的仲裁器对应的二进制位的数值进行修改以指示对应的仲裁器已被使用，第1个路由器的路由筛选模块将修改后的仲裁器掩码发送至第2个路由器；

当2≤i≤N-1时，如果候选路由请求集合非空，则第i个路由器的路由筛选模块修改接收到的第i-1个路由器的路由筛选模块发送的仲裁器掩码，将所述接收到的仲裁器掩码中第i个路由器使用的仲裁器对应的二进制位的数值进行修改以指示对应的仲裁器已被使用；第i个路由器的路由筛选模块将修改后的仲裁器掩码发送至第i+1个路由器的路由筛选模块；如果候选路由请求集合为空，则第i个路由器的路由筛选模块保持接收到的第i-1个路由器的路由筛选模块发送的仲裁器掩码不变；第i个路由器的路由筛选模块将接收到的仲裁器掩码发送至第i+1个路由器。

在一些示例性的实施方式中，N个路由器之间通过通信接口首尾相连成环状结构，任意一个路由器包括一个输入接口和一个输出接口，所述环状结构上的任意一个路由器通过输入接口连接上一级路由器的输出接口，通过输出接口连接下一级路由器的输入接口。

如图4和图5所示，本公开实施例提供了一种交叉开关装置，包括N个输入端口、M个输出端口和上述网络互连系统；N个输入端口与网络互连系统中的N个路由器的输入端口一一连接，M个输出端口与网络互连系统中的M个仲裁器的输出端口一一连接。

在集成电路领域，随着芯片工艺的不断发展，片上多核、多内存的设计越来越多，因此起到互联作用的交叉开关的使用也越来越多。交叉开关具有多个输入端口和多个输出端口，实现多个输入端口与多个输出端口的网络互联功能。一个高效的交叉开关结构，对整个系统的性能提升起到至关重要的作用。本申请实施例提供的交叉开关装置，在路由器中增加了缓存功能和路由筛选功能，均衡了仲裁器的输入路由，从而提高了路由转发的效率和网络吞吐量。

以1个16x16的交叉开关结构为例，假设16个输入端口持续有请求到达，16个输出端口一直不会拥堵，对现有技术中的交叉开关装置和本申请实施例的交叉开关装置进行转发效率的对比。

现有技术中的交叉开关，如果16个路由器恰好输出路由请求到同一个仲裁器，此时交叉开关效率为6.25%，出现概率是

本申请实施例提供的交叉开关装置，假设每个路由器可成功筛选出路由请求的概率逐级降低，第i级路由器可成功筛选出路由请求的概率为

比较两种交叉开关结构在相同效率时的出现概率值，显然后者（本申请实施例）优于前者（现有技术）。后者还可以通过改变路由器的优先筛选权利优化负载均衡的效果，有利于效率的提升和效率的稳定。

本公开实施例还提供了一种芯片，包括上述网络互连系统。

本公开实施例还提供了一种芯片，包括上述交叉开关装置。

本领域普通技术人员可以理解，上文中所公开的装置中的功能模块/单元可以被实施为软件、固件、硬件及其适当的组合。在硬件实施方式中，在以上描述中提及的功能模块/单元之间的划分不一定对应于物理组件的划分；例如，一个物理组件可以具有多个功能，或者一个功能或步骤可以由若干物理组件合作执行。某些组件或所有组件可以被实施为由处理器，如数字信号处理器或微处理器执行的软件，或者被实施为硬件，或者被实施为集成电路，如专用集成电路。这样的软件可以分布在计算机可读介质上，计算机可读介质可以包括计算机存储介质（或非暂时性介质）和通信介质（或暂时性介质）。如本领域普通技术人员公知的，术语计算机存储介质包括在用于存储信息（诸如计算机可读指令、数据结构、程序模块或其他数据）的任何方法或技术中实施的易失性和非易失性、可移除和不可移除介质。计算机存储介质包括但不限于RAM、ROM、EEPROM、闪存或其他存储器技术、CD-ROM、数字多功能盘（DVD）或其他光盘存储、磁盒、磁带、磁盘存储或其他磁存储装置、或者可以用于存储期望的信息并且可以被计算机访问的任何其他的介质。此外，本领域普通技术人员公知的是，通信介质通常包含计算机可读指令、数据结构、程序模块或者诸如载波或其他传输机制之类的调制数据信号中的其他数据，并且可包括任何信息递送介质。