A New Fault-Tolerant Routing Algorithm for OTIS-Cube Using Unsafety Vectors

J. Al-Sadi and A.M. Awwad

References

  1. [1] A.M. Awwad, A. Al-Ayyoub, & M. Ould-Khaoua, Efficient routing algorithms on the OTIS-networks, Proc. 3rd Int. Conf. on Information Technology (ACIT’ 2002), University of Qatar—Doha, December 16–19, 138–144.
  2. [2] S. Sahni & C.F. Wang, BPC permutations on the OTIS-mesh optoelectronic computer, mppoi, 130, 4th 1997.
  3. [3] C. Wang & S. Sahni, Basic operations on the OTIS-mesh optoelectronic computer, IEEE Trans. Parallel and Distributed Systems, 9(12), 1998, 1226–1236. doi:10.1109/71.737698
  4. [4] F. Zane, P. Marchand, R. Paturi, & S. Esener, Scalable network architecture using the optical transpose interconnection system (OTIS), Journal of Parallel and Distributed Computing, 60, 2000, 521–538. doi:10.1006/jpdc.2000.1627
  5. [5] S.B. Akers & B. Krishnamurthy, The star graph: An attractive alternative to the n-cube, Proc. Int. Conf. Parallel Processing (ICPP-87), St. Charles, Illinois, 1987, 393–400.
  6. [6] Y. Saad & M.H. Schultz, Topological properties of hypercubes, IEEE Trans. Computers, 37(7), 1988, 867–872. doi:10.1109/12.2234
  7. [7] S. Ranka, J. Wang, & N. Yeh, Embedding meshes on the star graph, Proc. on Supercomputing ’90, New York, November 12–16, 1990, 476–485. doi:10.1109/SUPERC.1990.130058
  8. [8] K. Day & A. Tripathi, Arrangement graphs: A class of generalised star graphs, Information Processing Letters, 42, 1992, 235–241. doi:10.1016/0020-0190(92)90030-Y
  9. [9] G. Marsden, P. Marchand, P. Harvey, & S. Esener, Optical transpose interconnection system architecture, Optics Letters, 18(13), 1993, 1083–1085.
  10. [10] W. Hendrick , O. Kibar, P. Marchand, C. Fan, D. Blerkom, F. McCormick, I. Cokgor, M. Hansen, & S. Esener, Modeling and optimisation of the optical transpose interconnection system, in Optoelectronic Technology Centre, Program Review, Cornell University, Ithaca, NY, 1995.
  11. [11] A. Krishnamoorthy, P. Marchand, F. Kiamilev, & S. Esener, Grain-size considerations for optoelectronic multistage interconnection networks, Applied Optics, 31(26), 1992, 5480– 5507.
  12. [12] K. Day & A. Al-Ayyoub, Topological properties of OTISnetworks, IEEE Trans. on Parallel and Distributed Systems, 13(4), 2002, 359–366. doi:10.1109/71.995816
  13. [13] NCUBE. NCUBE handbook. Technical Report, NCUBE Corporation, Beaverton, Oregon, 1986.
  14. [14] J. Rattler, Concurrent processing: A new direction in scientific computing, Proc. AFIPS Conf., 54, Chicago, IL, 1985, 157– 166.
  15. [15] C.L. Seitz, The cosmic cube, CACM 28, 1985, 22–23.
  16. [16] Silicon Graphics, Origin 200 & Origin 2000, Technical Report, Mountain View, California, 1996.
  17. [17] J. Al-Sadi, K. Day, & M. Ould-Khaoua, Unsafety vectors: A new fault-tolerant routing for the binary n-cube, Journal of Systems Architecture, 47(9), 2002, 783–793. doi:10.1016/S1383-7621(01)00031-5
  18. [18] P.T. Gaughan & S. Yalamanchili, Adaptive routing protocols for hypercube interconnection networks, Computer Journal, 26(5), 1993, 12–24. doi:10.1109/2.211888
  19. [19] M. Ni & P.K. McKinley, A survey of routing techniques in wormhole networks, Computer Journal, 26(2), 1993, 62–76. doi:10.1109/2.191995
  20. [20] Y. Saad & M.H. Schultz, Data communication in hypercubes, Technical Report YALEU/DCS/RR-428, Department of Computer Science, Yale University, New Haven, CT, 1985.
  21. [21] H. Sullivan, T. Bashkow, & D. Klappholz, A large scale, homogeneous, fully distributed parallel machine, Proc. 4th Annual Symp. Computer Architecture, 1977, 105–124. doi:10.1145/633615.810659
  22. [22] M.S. Chen & K.G. Shin, Adaptive fault-tolerant routing in hypercube multicomputers, IEEE Trans. Computers, 39(12), 1990, 1406–1416. doi:10.1109/12.61061
  23. [23] M.-S. Chen & K.G. Shin, Depth-first search approach for faulttolerant routing in hypercube multicomputers, IEEE Trans. Parallel & Distributed System, 1(2), 1990, 152–159. doi:10.1109/71.80143
  24. [24] J.M. Gordon & Q.F. Stout, Hypercube message routing in the presence of faults, Proc. 3rd Conf. Hypercube Concurrent Computers and Applications, Pasadena, 1988, 251–263.
  25. [25] Y. Lan, A fault-tolerant routing algorithm in hypercubes, Proc. Int. Conf. Parallel Processing, Illinois, 1994, pp. III 163–III 166. 250
  26. [26] T.C. Lee & J.P. Hayes, A fault-tolerant communication scheme for hypercube computers, IEEE Trans. Computers, 41(10), 1992, 1242–1256. doi:10.1109/12.166602
  27. [27] S. Sahni & C. Wang, BPC permutations on the OTIS-hypercube optoelectronic computer, Informatica, 22, 1998, 263–269.
  28. [28] C.F. Wang, Algorithms for the OTIS optoelectronic computers, doctoral diss., Department of Computer Science, University of Florida, Gainesville, FL, 1998.
  29. [29] S. Graham & S. Seidel, The cost of broadcasting on star graphs and k-ary hypercubes, IEEE Trans. Computers, 42(6), 1993, 756–759. doi:10.1109/12.277296
  30. [30] H. Linder & C. Harden, An adaptive and fault tolerant wormhole routing strategy for k-ary n-Cubes, IEEE Trans. Computers, 40(1), 1991, 2–12. doi:10.1109/12.67315

Important Links:

Go Back