Optimal Routing Algorithms for a Class of Cylindrical Banyan Multicomputers

✍ Scribed by N.S. Woo; B. Naylor

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 538 KB
• Volume: 23
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1994.1135

✦ Synopsis

The cylindrical banyan network is a variation of the classical banyan network in two ways: (1) each node is a processor with a switch, and (2) every pair of nodes at the two ends is merged. We present a routing algorithm for the cylindrical banyan network, and show it is optimal in terms of the path length. We also show that for the cylindrical banyan network containing (L) levels with (2^{L}) processors at each level (i.e., containing (L 2^{L}) processors in total), the worst case path length between any two nodes is (1.5 L). We discuss a generalization of the cylindrical banyan network and an optimal routing algorithm for it. Our routing algorithms are distributed, and so can be executed locally at each processor. O 1994 Academic Press, Inc.