A Method and Apparatus for Congestion Aware Routing in a Computer Interconnection Network

Introduction

On-chip design constraints require networks on chips (NOCs) to employ simple deterministic routing algorithms, such as dimension order routing (DOR), in which messages follow a fixed path from the source to the destination, traversing the dimensions in a predefined order. However, such algorithms have been shown to exhibit poor load balance under typical workloads, impacting the performance of these networks.

Adaptive routing is a well-known technique, successfully employed in multi-chip interconnection networks to improve network performance. Performance in these networks can be improved by routing along pockets of congestion and by better traffic distribution among the links, to avoid congestion. The key design point for any adaptive router is the algorithm, which selects the output channel for a message.

Recognizing the importance of achieving and maintaining global balance under all workloads, our inventors have proposed the Regional Congestion Awareness approach.

Benefits:

• Leads to increased network throughput. This improvement comes at no cycle time penalty and limited area and power heads.
• Improves the performance of adaptively routed networks through more informed path selection.
  

Features:

• Uses a low-bandwidth dedicated status network for propagation of congestion status information, combined with intelligent aggregation of local and incoming congestion updates at each network node.
• Makes use of congestion information from different network regions to improve route selection, unlike the current techniques for adaptive routing that rely solely on local congestion status information to inform their per-hop routing decisions.
  

Market Potential/Applications: Computer interconnection networks

Contact:

University of Texas,
Austin, USA
Website : www.otc.utexas.edu