BLAM: a high-performance routing algorithm for virtual cut-through networks

High performance, freedom from deadlocks, and freedom from livelocks are desirable properties of interconnection networks. Unfortunately, these can be conflicting goals because networks may either devote or under-utilize resources to avoid deadlocks and livelocks. These resources could otherwise be used to improve performance. For example, a minimal adaptive routing algorithm may forgo some routing options to ensure livelock-freedom but this hurts performance at high loads. In contrast, chaotic routing achieves higher performance as it allows full-routing flexibility including misroutes (hops that take a packet farther from its destination) and it is deadlock-free. Unfortunately, Chaotic routing only provides probabilistic guarantees of livelock-freedom. In this paper we propose a new routing algorithm called BLAM (bypass buffers with limited adaptive lazy misroutes) which achieves Chaos-like performance, but guarantees freedom from both deadlocks and livelocks. BLAM achieves Chaos-like performance by allowing packets to be "lazily" misrouted outside the minimal rectangle. Lazy misrouting is critical to BLAM\´s performance because eager misrouting can misroute unnecessarily, thereby degrading performance. To avoid deadlocks, BLAM uses a logically separate deadlock-free network (like minimal, adaptive routing), virtual cut-through, and the packet exchange protocol (like Chaos). To avoid livelocks, unlike Chaos, BLAM limits the number of times a packet is misrouted to a predefined threshold. Beyond the threshold, stalled packets are routed by the deadlock-free network to their destinations. Simulations show that our BLAM implementation sustains high throughput at heavy loads for a variety of network configurations and communication patterns.