一种面向Dragonfly网络几乎最小路径自适应路由方法及装置

本发明涉及超级计算机高性能互连网络，尤其涉及一种面向dragonfly网络几乎最小路径自适应路由方法及装置。

背景技术：

1、dragonfly网络是一种高基数、低直径的网络拓扑结构，已被部署在当前全球排名前列的百亿亿次超级计算机中，包括frontier、el capitan、aurora和jupiter等。dragonfly网络由多个路由器组（group）构成，每个组内包含若干路由器，组内路由器之间通过局部信道（local channel）全连接，组间通过全局信道（global channel）互连，每对组之间至少有一条全局链路。如图2所示，在dragonfly网络中，数据包从源节点到目的节点的最小路径至多需要3跳，包括1次源组内的局部跳、1次全局跳和1次目的组内的局部跳；非最小路径（valiant路由）则将数据包先路由到一个随机选择的中间组，再从中间组路由到目的组，至多需要6跳和2次全局信道。如图4所示，在随机排列流量模式下，对最小路径碰撞进行静态分析表明，仅源组局部信道碰撞、仅目的组局部信道碰撞以及源组和目的组的局部信道均碰撞但全局信道无碰撞这三种类型的碰撞，平均约占所有碰撞路径的34.9%，理想情况下应通过仅增加局部跳的“几乎最小路径”进行负载均衡，而非使用6跳的全局非最小路径。

2、现有dragonfly网络的自适应路由算法分为源自适应路由算法和增量自适应路由算法两大类。源自适应路由算法包括ugal、pb、ugal_ph、ugal-le、dgb和piar等，其中ugal通过将队列长度与路径跳数进行代价耦合实现最小路径与非最小路径的统一比较，pb通过捎带机制传递组内全局信道的拥塞位图，dgb基于全局拥塞信息捎带实现精确感知，piar利用更短的全局非最小路径进行优化；增量自适应路由算法包括par和ofar等，其中par允许源路由器确定为全局最小路由的数据包在到达源组内与目的组直接相连的路由器时切换为全局非最小路由，ofar在par的基础上进一步允许数据包在到达目的组后进行组内非最小路由。然而，现有自适应路由算法存在以下三方面技术缺陷：第一，在仅存在局部信道拥塞而非全局信道拥塞的场景下，源自适应路由算法仍然将数据包路由到全局非最小路径上，导致不必要的6跳路由和额外的全局带宽消耗；第二，par的最长路径需要5个虚通道、ofar的最长路径需要6个虚通道，而实际大规模互连系统通常仅实现4个路由虚通道，引入哈密顿逃逸环或转弯模型则会牺牲路径多样性或形成新的瓶颈；第三，par无法利用任何几乎最小路径，ofar仅能利用在目的组内进行非最小路由的几乎最小路径，无法充分利用源组内进行非最小路由以及双端均进行非最小路由的几乎最小路径，导致约占碰撞路径34.9%的局部信道拥塞场景下大量全局信道带宽浪费和较高的网络延迟。

技术实现思路

1、本发明所要解决的技术问题在于，提供一种面向dragonfly网络几乎最小路径自适应路由方法及装置，在不增加虚通道资源、不引入哈密顿逃逸环或转弯模型的前提下，首次定义并充分利用源组非最小、目的组非最小和双端非最小三种类型的几乎最小路径，通过限制性增量自适应路由机制有效缓解局部信道拥塞，提升网络吞吐量并降低通信延迟。

2、为了解决上述技术问题，本发明实施例第一方面公开了一种面向dragonfly网络几乎最小路径自适应路由方法，所述方法包括：

3、s1，获取dragonfly网络拓扑参数信息、路由器实时状态信息集和待路由数据包信息；

4、s2，对所述dragonfly网络拓扑参数信息进行解析处理，得到候选路径信息集；

5、s3，对所述路由器实时状态信息集和所述dragonfly网络拓扑参数信息进行拥塞感知处理，得到全局信道拥塞位图信息集；

6、s4，对所述待路由数据包信息、所述候选路径信息集和所述全局信道拥塞位图信息集进行全局自适应路由决策处理，得到全局路由标记信息；

7、s5，对所述全局路由标记信息、所述候选路径信息集、所述路由器实时状态信息集、所述待路由数据包信息和所述dragonfly网络拓扑参数信息进行局部增量自适应路由决策处理，得到目标路由路径信息。

8、作为一种可选的实施方式，在本发明实施例第一方面中，所述对所述dragonfly网络拓扑参数信息进行解析处理，得到候选路径信息集，包括：

9、s21，对所述dragonfly网络拓扑参数信息进行最小路径生成处理，得到最小路径信息；

10、s22，对所述dragonfly网络拓扑参数信息进行非最小路径生成处理，得到非最小路径信息；

11、s23，对所述dragonfly网络拓扑参数信息进行几乎最小路径生成处理，得到几乎最小路径信息集；

12、s24，对所述最小路径信息、所述非最小路径信息和所述几乎最小路径信息集进行合并处理，得到候选路径信息集。

13、作为一种可选的实施方式，在本发明实施例第一方面中，所述对所述dragonfly网络拓扑参数信息进行几乎最小路径生成处理，得到几乎最小路径信息集，包括：

14、s231，对所述dragonfly网络拓扑参数信息进行源组非最小路径生成处理，得到源组非最小路径信息；

15、s232，对所述dragonfly网络拓扑参数信息进行目的组非最小路径生成处理，得到目的组非最小路径信息；

16、s233，对所述dragonfly网络拓扑参数信息进行双端非最小路径生成处理，得到双端非最小路径信息；

17、s234，对所述源组非最小路径信息、所述目的组非最小路径信息和所述双端非最小路径信息进行合并处理，得到几乎最小路径信息集。

18、作为一种可选的实施方式，在本发明实施例第一方面中，所述对所述路由器实时状态信息集和所述dragonfly网络拓扑参数信息进行拥塞感知处理，得到全局信道拥塞位图信息集，包括：

19、s31，对所述路由器实时状态信息集中每个路由器实时状态信息和所述dragonfly网络拓扑参数信息进行滑动窗口初始化处理，得到滑动窗口缓冲区信息集；

20、s32，对所述滑动窗口缓冲区信息集进行统计处理，得到滑动窗口统计量信息集；

21、s33，对所述路由器实时状态信息集中全局信道队列长度信息集和所述滑动窗口统计量信息集进行处理，得到全局信道拥塞判定结果信息集；

22、s34，对所述全局信道拥塞判定结果信息集进行位图编码处理，得到路由器全局信道拥塞位图信息集；

23、s35，对所述路由器全局信道拥塞位图信息集进行捎带传播处理，得到全局信道拥塞位图信息集。

24、作为一种可选的实施方式，在本发明实施例第一方面中，所述对所述路由器实时状态信息集中全局信道队列长度信息集和所述滑动窗口统计量信息集进行处理，得到全局信道拥塞判定结果信息集，包括：

25、利用滑动窗口拥塞检测模型，对所述路由器实时状态信息集中全局信道队列长度信息集和所述滑动窗口统计量信息集进行处理，得到全局信道拥塞判定结果信息集；

26、其中，所述滑动窗口拥塞检测模型为：

27、；

28、式中，为所述全局信道队列长度信息集中第i条全局信道的队列长度值，所述全局信道队列长度信息集包括若干个全局信道队列长度值；为所述滑动窗口统计量信息集中第i条全局信道的滑动窗口统计量值，用于记录路由器在最近的全局信道往返延迟2l内发往第i条全局信道的flit数量，所述滑动窗口统计量信息集包括若干个滑动窗口统计量值；i的取值范围为1至h，h为每个路由器的全局端口数，t为拥塞阈值；所述全局信道拥塞判定结果信息集包括若干个全局信道拥塞判定结果信息，每个所述全局信道拥塞判定结果信息的取值为拥塞状态或非拥塞状态；当成立时，判定第i条全局信道的所述全局信道拥塞判定结果信息为拥塞状态，否则判定为非拥塞状态。

29、作为一种可选的实施方式，在本发明实施例第一方面中，所述对所述路由器全局信道拥塞位图信息集进行捎带传播处理，得到全局信道拥塞位图信息集，包括：

30、s351，对所述路由器全局信道拥塞位图信息集中任一全局信道拥塞位图信息进行打包处理，得到该全局信道拥塞位图信息对应的拥塞位图捎带载荷信息；

31、s352，对该全局信道拥塞位图信息对应的所述拥塞位图捎带载荷信息和待发送的局部信道数据包进行附加处理，得到该全局信道拥塞位图信息对应的捎带数据包信息；

32、s353，对该全局信道拥塞位图信息对应的所述捎带数据包信息进行接收解析处理，得到该全局信道拥塞位图信息对应的接收路由器更新后的全局信道拥塞位图信息；

33、s354，对所有所述全局信道拥塞位图信息对应的所述接收路由器更新后的全局信道拥塞位图信息进行合并处理，得到全局信道拥塞位图信息集。

34、作为一种可选的实施方式，在本发明实施例第一方面中，所述对所述待路由数据包信息、所述候选路径信息集和所述全局信道拥塞位图信息集进行全局自适应路由决策处理，得到全局路由标记信息，包括：

35、s41，对所述全局信道拥塞位图信息集和所述待路由数据包信息进行查询处理，得到源路由器全局信道拥塞位图信息；

36、s42，对所述候选路径信息集和所述待路由数据包信息进行索引提取处理，得到最小路径全局信道索引集合信息和非最小路径全局信道索引集合信息；

37、s43，对所述源路由器全局信道拥塞位图信息、所述最小路径全局信道索引集合信息和所述非最小路径全局信道索引集合信息进行计算处理，得到全局非最小路由代价指示量值；

38、s44，对所述全局非最小路由代价指示量值进行标记处理，得到全局路由标记信息。

39、作为一种可选的实施方式，在本发明实施例第一方面中，所述对所述全局路由标记信息、所述候选路径信息集、所述路由器实时状态信息集、所述待路由数据包信息和所述dragonfly网络拓扑参数信息进行局部增量自适应路由决策处理，得到目标路由路径信息，包括：

40、s51，判断所述全局路由标记信息是否为全局最小路由，得到第一判断结果；

41、当所述第一判断结果为否时，对所述待路由数据包按所述候选路径信息集中所述非最小路径信息进行转发处理，得到目标路由路径信息；

42、当所述第一判断结果为是时，执行s52；

43、s52，对所述路由器实时状态信息集中当前中间路由器对应的路由器实时状态信息中所述局部信道队列长度信息集和所述候选路径信息集进行查询处理，得到局部最小路径下一跳队列长度信息和局部非最小路径下一跳队列长度信息；

44、s53，对所述局部最小路径下一跳队列长度信息、所述局部非最小路径下一跳队列长度信息和所述dragonfly网络拓扑参数信息中的局部信道单向延迟l进行计算处理，得到局部非最小路由触发指示量值；

45、s54，判断所述局部非最小路由触发指示量值是否等于1，得到第二判断结果；

46、当所述第二判断结果为是时，对所述待路由数据包进行局部绕行处理，得到所述目标路由路径信息；

47、当所述第二判断结果为否时，对所述待路由数据包按所述候选路径信息集中的所述最小路径信息的下一跳进行转发处理，得到所述目标路由路径信息。

48、作为一种可选的实施方式，在本发明实施例第一方面中，所述对所述路由器实时状态信息集中当前中间路由器对应的路由器实时状态信息中所述局部信道队列长度信息集和所述候选路径信息集进行查询处理，得到局部最小路径下一跳队列长度信息和局部非最小路径下一跳队列长度信息，包括：

49、s521，对所述局部信道队列长度信息集中所述候选路径信息集中的最小路径信息下一跳对应的局部信道进行队列查询处理，得到局部最小路径下一跳队列长度信息；

50、s522，对所述局部信道队列长度信息集中局部非最小路径下一跳对应的局部信道进行队列查询处理，得到局部非最小路径下一跳队列长度信息。

51、作为一种可选的实施方式，在本发明实施例第一方面中，所述对所述待路由数据包进行局部绕行处理，得到所述目标路由路径信息，包括：

52、s541，当当前中间路由器位于源组内时，对所述待路由数据包进行源组内随机路由器绕行处理，得到所述目标路由路径信息；

53、s542，当当前中间路由器位于目的组内时，对所述待路由数据包进行目的组内随机路由器绕行处理，得到所述目标路由路径信息。

54、与现有技术相比，本发明实施例具有以下有益效果：

55、本发明实施例中，获取dragonfly网络拓扑参数信息、路由器实时状态信息集和待路由数据包信息；对所述dragonfly网络拓扑参数信息进行解析处理，得到候选路径信息集；对所述路由器实时状态信息集和所述dragonfly网络拓扑参数信息进行拥塞感知处理，得到全局信道拥塞位图信息集；对所述待路由数据包信息、所述候选路径信息集和所述全局信道拥塞位图信息集进行全局自适应路由决策处理，得到全局路由标记信息；对所述全局路由标记信息、所述候选路径信息集、所述路由器实时状态信息集、所述待路由数据包信息和所述dragonfly网络拓扑参数信息进行局部增量自适应路由决策处理，得到目标路由路径信息。可见，本技术通过将候选路径信息集划分为最小路径、非最小路径和包含三种子型的几乎最小路径，结合滑动窗口与捎带位图的全局信道拥塞感知机制，并在源路由器一次性确定全局路由策略后，仅对全局最小路由的数据包允许执行组内局部增量绕行，能够在仅使用4个虚通道的条件下保证无死锁，充分利用所有类型的几乎最小路径绕过局部信道拥塞，在合成流量负载和典型高性能计算通信负载下相比可实际部署的源自适应路由算法平均吞吐量提升13.6%至51.8%，同时缓冲区开销与带宽开销均显著低于现有最优算法。