Load balanced deadlock-free deterministic routing of arbitrary networks

ABSTRACT

This paper provides efficient algorithms to deadlock-free route arbitrary multiprocessor interconnection networks as follows: 1. An algorithm is derived for fixed directory routing on an arbitrary network topology such that messages will be routed via one of the shortest routes whilst maintaining an even distribution of traffic over the network (assuming that messages are generated and absorbed in an even manner, or two-phase random routing is used). 2. An algorithm is presented which will evenly map virtual links onto the routed network so that it will be deadlock-free using the minimum number of buffer classes per physical link, thus maximising the buffer size per virtual link.

REFERENCES

• 1: J. Allwright. "Graph theory on a transputer network". In Proc. 3rd T~ansputer/Occam Int. Conf., pages 161-179, Japan, 1990.
• 2: P. R. Bell and K. Jabbour. "Review of point-topoint network routing algorithms". IEEE Commun. Mag., 24(1):34-38, Jan 1986.
• 3: J. C. Bermond, C. Delorme, and G. FarM. "Large graphs with given degree and diameter, II'. Journal of Corabinaforial Theory, 36B:32-48, 1984.
• 4: W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 5: N. G. De Bruijn. "A combinatorial problem". Koninklijke Netherlands: Academe Van Wetenschappen, Proc., 49(20):758-764, 1946.
• 6: M. Debbage, M. Hill, and D. Nicole. Virtual Channel Router Version ~.0 User Guide. Dept. of Electronics and Computer Science, University of Southampton, UK, June 1991.
• 7: J. Briat et al. "PARX: A parallel operating system for transputer based machines". In Applying Transputer Based Parallel Machines - Proc. occam User Group Technical Meetin9 (OUGIO), pages 114-142, Apt 1989.
• 8: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 9: D. Gelernter. "A dag-based algorithm for prevention of store-and-forward deadlock in packet networks". IEEE Trans. Comput., 30(10):709-715, Oct 1981.
• 10: K. D. Gunther. "Prevention of deadlocks in packetswitched data transport systems". IEEE Trans. Commun., COM-29(4):512-524, Apr 1981.
• 11: CORPORATE INMOS Limited, Transputer reference manual, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1988
• 12: P. Kermani and L. Kleinrock. "Virtual cutthrough: a new computer communication switching technique". Comput. Networks, 3(12):267-286, 1979.
• 13: V. P. Kumar and S. M. Reddy. "A class of graphs for fault-tolerant processor interconnections". In Proc. g th Int. Conf. Distributed Comput. Syst., pages 448-460, San Francisco, CA, May 1984.
• 14: Charles Richard Lang, Jr., The extension of object-oriented languages to a homogeneous, concurrent architecture, 1982
• 15: P. M. Merlin and P. :I. Schweitzer. "Deadlock avoidance in store-and-forward networks ~ I: store-and-forward deadlock". IEEE Trans. Commun., COM-28(3):345-354, Mar 1980.
• 16: F. P. Preparata and J. E. Vuillemin. "The cubeconnected cycles: a versatile network for parallel computation". In Proc. 20th IEEE Syrup. Foundations Comput. Sci., pages 140-147.
• 17: D. J. Pritchard. "Topologies and routing strategies for transputer networks". May 1991. interim thesis, University of Liverpool, UK.
• 18: M. R. Samatham , D. K. Pradhan, The de Bruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI, IEEE Transactions on Computers, v.38 n.4, p.567-581, April 1989 [doi>10.1109/12.21149 ]
• 19: A. Segall. "The modeling of adaptive routing in data-communications networks". IEEE Trans. Commun., COM-25(1):85-95, Jan 1977.
• 20: C. L. Seitz et al. Wormhole chip project report. Winter 1985.
• 21: H. S. Stone. "Parallel processing with the perfect shuflte'. IEEE Trans. Comput., 30(2):153-161, Feb 1971.
• 22: R. M. Storwick. "Improved construction techniques for (d,k) graphs". IEEE Trans. Compu~., 19(12):1214-1216, Dec 1970.
• 23: Herbert Sullivan , T R Bashkow, A large scale, homogeneous, fully distributed parallel machine, I, Proceedings of the 4th annual symposium on Computer architecture, p.105-117, March 23-25, 1977
• 24: Mike Surridge. "ECCL : A general communications harness and configuration language". In Proc. ~nd Int. Conf. on Applications of Transput. ers, Southampton, UK, July 1990.
• 25: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 26: Sam Toueg , Jeffrey D. Ullman, Deadlock-free packet switching networks, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.89-98, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804402]
• 27: L. G. Valiant. "Optimality of a two-phase strategy for routing in interconnection networks". IEEE Trans. Comput., 32(9):861-863, Sept 1983.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Measurement, Performance, Theory