Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.17 No.4, pp.575-594 (July 2001)

Designing Deadlock-Free Turn-Restricted Routing
Algorithms for Irregular Wormhole-Routed Networks

Jenq-Shyan Yang and Chung-Ta King
Department of Information Management
LungHwa Institute of Technology
Taoyuan, Taiwan 333, R.O.C.
E-mail: jsyang@lhit.edu.tw
*Department of Computer Science
National Tsing Hua University
Hsinchu, Taiwan 300, R.O.C.
E-mail: king@cs.nthu.edu.tw

Irregular networks connected by wormhole-routed switches are becoming increasingly popular for building networks of workstations for cost-effective parallel processing. A primary strategy to achieve deadlock-free routing in such networks is to first configure the links in a network into some specific directions, and then prohibit the turns that a message may traverse. A routing algorithm imposes fewer turn prohibitions will have a higher adaptively and thus a higher performance. In general, designing such a routing algorithm requires two basic components: (1) assigning link directions, and (2) determining a link-direction-based routing guideline. In this paper we examine various assignment rules and routing guidelines, from which different heuristics and criteria are proposed to construct a good routing algorithm. Their effectiveness in reducing turn prohibitions is investigated, and in most cases the minimum turn prohibitions can be achieved. For a connected network with N switches and M links, the complexity of finding the set of turn prohibitions using our proposed method is O(N ? M).

Keywords: adaptive routing, deadlock freedom, irregular network, routing algorithm, wormhole routing

Full Text () Retrieve PDF document (200107_03.pdf)

Received February 11, 1999; revised January 14 & May 11, 2000; accepted June 27, 2000.
Communicated by Jean-Lien C. Wu.
* This work was supported in part by the National Science Council, R.O.C., under Grants NSC-86-2213-E-007-043 and NSC-86-2622-E-009-0102.