Shortcut Allocation for Tree-based Routing in Irregular Interconnection Networks

H.-C. Chi, W.-J. Wu, and C.-M. Wu (Taiwan)


Interconnection networks, routing algorithms, switches,multiprocessors, irregular networks.


Interconnection networks for multiprocessor systems with irregular topologies are typically more incrementally scalable than those with regular topologies. Based on constructing a spanning tree, a cost-effective routing scheme called TRAIN for irregular interconnection networks has been developed. In TRAIN, those links not belonging to the spanning tree are used as shortcuts to improve network performance. TRAIN requires no routing table in the switch for the network, and it is deadlock-free. In this paper, we propose several strategies for shortcut allocation for the spanning tree in the network. To evaluate their performance impact, both analysis for unloaded networks and simulation for loaded networks have been performed. Our results show that different strategies for shortcut allocation have significant impact on the network performance.

Important Links:

Go Back