Avoiding routing deadlocks is an important component of interconnection networks that prevents the network from progressing due to cyclical dependency within the networks. For large-scale systems using high-radix topologies that leverage non-minimal adaptive routing, virtual channels(VCs) are generally used to avoid routing deadlock. However, VCs can be costly for large-scale networks due to the deep buffers. In this work, we propose both routing algorithms and flow controls -- Restricted Intermediate-node Non-minimal Routing (RINR) algorithm and opportunistic flow control (OFC), which both exploit the low-diameter characteristics of high-radix networks while still maximizing path diversity within the topology. We will refer these algorithms as BoomGATE. We analyze the occurrence of routing deadlock in fully-connected topologies due to the non-minimal routes, and propose to restrict the non-minimal routes to guarantee deadlock freedom without any additional VCs. We also propose an algorithm to ensure path diversity that is able to load-balanced across all nodes in the network. However, since path diversity is restricted with the RINR algorithm, we propose opportunistic flow control (OFC) to complement the path diversity limitation of RINR. OFC is the flow control method to allow the "illegal routes" if and only if sufficient buffer can be guaranteed to ensure cyclical dependency does not occur. We propose both a static and dynamic OFC implementation. We evaluate the performance of BoomGATE and demonstrate that there is minimal performance loss compared to global adaptive routing, while achieving 50% reduction of the amount of buffers.
라우팅 교착상태를 피하는 것은 네트워크 내의 주기적 종속성으로 인해 네트워크가 진행되지 못하게하는 상호 연결 네트워크의 중요한 구성 요소이다. 비최소적응형 라우팅을 활용하는 높은 기수의 라우터들로 구성된 토폴로지가있는 대규모 시스템의 경우 가상 교착 상태를 방지하기 위해 가상 채널(VCs)이 일반적으로 사용된다. 그러나 대규모 네트워크의 가상채널은 깊은 버퍼로 인하여 많은 비용이 들어갈 수 있어 사용이 제한 될 수 있다. 본 논문에서는 대규모 네트워크에서 교착 상태 방지를위한 높은 반경의 네트워크의 낮은 직경 특성은 토폴로지 내에서 경로 다양성을 최대화하는 제한된 중간 노드 비 최소 라우팅 (RINR) 알고리즘, 그리고 흐름 제어 기술로 기회 흐름 제어 (OFC)로 구성된 BoomGATE를 제안한다. 완벽하게 연결된 토폴로지에서 라우팅 교착 상태가 비최소 경로로 인하여 발생하는 방식을 식별하고, 추가 가상 채널없이 교착상태 방지를 보장하기 위해 비최소 라우팅을 제한 하여 시스템의 모든 노드에서 경로 다양성이 로드-밸런싱되도록하는 알고리즘을 제안한다. 그러나 경로 다양성이 RINR 알고리즘으로 제한되므로 이를 보완하기 위해 주기적 종속성이 발생하지 않도록 충분한 버퍼를 보장 할 수있는 경우에만 "불법 경로"가 허용되는 정적 및 동적 OFC(기회 흐름 제어)를 제안한다. 우리는 BoomGATE의 성능을 평가하고 글로벌 적응 형 라우팅에 비해 최소의 성능 손실이 있음을 보여 주면서 필요한 버퍼의 양을 50% 감소시켰다.
