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

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.