Simplifying Congestion Management
August 22, 2013, Hot Interconnects Symposium, San Jose, CA—Maria Garcia from the University of Spain and IBM described the techniques and tools to establish efficient dragonfly networks with simple congestion management.
Dragonfly networks are hierarchical direct networks in a modified star configuration. This organization permits both local and global combinations of traffic while allowing for full connectivity. Routing from any node to any other takes a minimum of 3 hops, but these routes saturate under adversarial traffic conditions. Adaptive nonminimal
routing can be used to avoid such congestion.
One way to load balance is to change the routing to use up to 5 hops over multiple local links versus a single global link. Managing the congestion through these escape subnets allows for a better use of resources at the cost of latency and higher routing complexity.
One problem is that when a distance-based deadlock avoidance mechanism is employed, more Virtual Channels (VCs) are required, which increases design complexity and cost.
On-the-Fly Adaptive Routing (OFAR) is a routing technique that decouples VCs from deadlock avoidance, making local and global misrouting affordable. However, the severity of congestion with OFAR is higher, as it relies on an escape sub-network with low bisection bandwidth. Additionally, OFAR allows for unlimited misroutings on the escape sub-network, leading to unbounded paths in the network and long latencies.
As an alternative, OFAR-CM is a variant of OFAR combined with a simple congestion management (CM) mechanism which only relies on local information, specifically the credit count of the output ports in the local router. The escape congestion management (ECM) and base congestion management (BCM) techniques offer practical tools to avoid very long routes and their related latencies.
With simple escape sub-networks such as a Hamiltonian ring or a tree, OFAR outperforms former proposals with distance-based deadlock avoidance. Additionally, although long paths are allowed in theory, in practice packets arrive at their destination in a small number of hops. Altogether, OFAR-CM constitutes the first practicable mechanism to the date that supports both local and global mis-routing in Dragonfly networks.
