Region-Based Routing Mechanism

A. Mejia, M. Palesi, J. Flich, S. Kumar, P. López, R. Holsmark, and J. Duato. "Region-Based Routing: A Mechanism to Support Efficient Routing Algorithms in NoCs." IEEE Transactions on Very Large Scale Integration Systems (TVLSI), 17(3):356–369, March 2009.

The O1TURN and GOAL algorithms assume regular topologies, but the region-based routing mechanism seeks to efficiently enable routing on irregular topologies. The irregularity may be due to heterogeneous terminals or link failures in a regular topology. Such irregularity is often handled with routing tables at each network router, but this approach is expensive in an on-chip context. Essentially, the region-based routing mechanism provides a more compact encoding of routing tables suitable for on-chip networks. Region-based routing is a mechanism that can be applied to a variety of routing algorithms. In this paper, the authors use two of their own routing algorithms: segment-based routing and application-specific routing. Application-specific routing is relatively straight-forward, but students may want to skim the related IPDPS'06 paper on segment-based routing. However, students should focus more on the actual region-based routing mechanism as opposed to these two routing algorithms. Can the region-based routing mechanism be used with the O1TURN or GOAL algorithms? In Section 3.C, the authors describe a complicated algorithm for calculating the regions. How does the complexity of this algorithm impact using the region-based mechanism for fault-tolerance? Region-based routing is one way to limit the size of a routing table, but are there any other simpler techniques that can achieve a similar effect?