Recently, the development of Compute Express Link (CXL) has enabled heterogeneous computing with a large number of components, and it is important to make sure that communication will not be the system's bottleneck. Fat-tree is a popular option thanks to its high path diversity; however, the routing algorithm must be carefully designed to fully exploit the path diversity to provide high throughput. Different routing algorithms have been proposed, with many based on randomization when selecting an output port, including many adaptive routing schemes. While they can successfully balance the traffic, they suffer from instantaneous contention and their performances are limited. On the other hand, Deterministic routing has performance trade-offs for different traffics, while it works best in balanced traffic, it performs poorly for permutation traffic. In this work, we propose a novel routing algorithm that leverages the use of hashing and adaptive routing to deterministically and adaptively distribute packets across the network with minimal collision. Our evaluation shows that our proposal outperforms other routing algorithms in most configurations and evaluation metrics. Specifically, it can provide up to 30\% runtime improvement compared to Random and Adaptive Routing, and even matches the optimal performance of Deterministic in Uniform Random traffic. In addition, we also evaluated the impacts of communicating with large message sizes and the impacts of different packet sizes on performance.
최근 CXL(Compute Express Link)의 개발로 다수의 구성 요소를 갖춘 이기종 컴퓨팅이 가능해졌으며, 통신이 시스템의 병목 현상이 되지 않도록 하는 것이 중요합니다. Fat-tree는 높은 경로 다양성 덕분에 널리 사용되는 옵션이지만, 높은 처리량을 제공하려면 경로 다양성을 완전히 활용하도록 라우팅 알고리즘을 신중하게 설계해야 합니다. 다양한 라우팅 알고리즘이 제안되었으며, 이중 많은 라우팅 체계는 출력 포트 무작위 선택을 기반으로 하며 이는 적응형 타우팅 알고리즘 또한 그렇습니다. 이는 트래픽을 성공적으로 분산 할 수 있지만 순간적 혼잡에 취약하며 성능또한 제한적입니다. 반면에 결정론적 라우팅은 다른 트래픽 하에 성능이 상이하며, 이로인해 분산된 트래픽에서 최적 성능을 보이는 반면 치환 트래픽에서는 성능이 떨어집니다. 본 연구에서는 해싱 및 적응형 라우팅의 사용을 활용하여 충돌을 최소화하면서 네트워크 전체에 패킷을 결정적이며 적응적으로 분산시키는 새로운 라우팅 알고리듬을 제안합니다. 우리가 평가한 바로는 이 라우팅 알고리즘은 대부분의 구성 및 평가 지표에서 다른 라우팅 알고리즘을 상회하는 모습을 보여줍니다. 특히, 랜덤 및 적응형 라우팅에 비해 최대 30\%의 런타임 성능 향상을 제공할 수 있으며, 균등분포 트래픽에서 또한 결정론적 알고리즘의 성능과 일치합니다. 추가로 큰 메시지 크기와 통신할 때의 영향과 다양한 패킷 크기가 성능에 미치는 영향도 평가했습니다.
