Designing Routing Algorithms Based on Turn Model for Irregular Networks
Gongxuan Zhang · Mini-micro Systems · 2005
Irregular networks connected by wormhole-routed switches are becoming increasingly popular for building networks of workstations for cost-effective parallel processing. Networks using wormhole routing techniques are particularly vulnerable to deadlock. The irregularity makes routing and deadlock avoidance on such systems quite complicated. This paper proposes a general methodology to design deadlock-free routing algorithms based on turn model, and extends link directions to obtain several routing strategies, in the end determines two new routing algorithms. By simulations it is showed that the up-first routing algorithm and down-last routing algorithm achieve higher performance, in terms of delay, than other algorithms, such as the spanning tree and up*/down* routing algorithms.