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

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Thottethodi, M; Lebeck, AR; Mukherjee, SS

Published Date

  • January 1, 2003

Published In

  • Proceedings International Parallel and Distributed Processing Symposium, Ipdps 2003

International Standard Book Number 10 (ISBN-10)

  • 0769519261

International Standard Book Number 13 (ISBN-13)

  • 9780769519265

Digital Object Identifier (DOI)

  • 10.1109/IPDPS.2003.1213133

Citation Source

  • Scopus