HoL-Blocking Avoidance Routing Algorithms in Direct Topologies

摘要

Routing is a key parameter in the design of the interconnection network of large parallel computers. Depending on the number of routing options available for each packet, routing algorithms are classified into two different categories: deterministic (one available path) and adaptive (several ones). It is well-known that adaptive routing outperforms deterministic routing. Usually, adaptive routing uses virtual channels to provide routing flexibility and to guarantee deadlock freedom. On the other hand, deterministic routing is simpler and therefore has lower routing delay and does not introduce out-of-order packet delivery. This is why, in this paper, we take the challenge of developing new routing algorithms for direct topologies that exploit virtual channels in an efficient way while still maintaining the good properties of deterministic routing. This is accomplished by tackling one of the main performance degradation contributors of interconnection networks, which is the HoL-blocking effect. To do that, this paper analyzes several simple mechanisms to perform an efficient distribution of packets among virtual channels based on their destination. The resulting deterministic routing mechanisms obtain similar or even better performance than adaptive routing while keeping the simplicity of deterministic routing and guaranteeing in-order delivery of packets by design.