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, Efficientrouting algorithms on the OTIS-networks, Proc. 3rd Int.Conf. on Information Technology (ACIT’ 2002), University ofQatar—Doha, December 16–19, 138–144.
  2. [2] S. Sahni & C.F. Wang, BPC permutations on the OTIS-meshoptoelectronic computer, mppoi, 130, 4th 1997.
  3. [3] C. Wang & S. Sahni, Basic operations on the OTIS-meshoptoelectronic computer, IEEE Trans. Parallel and DistributedSystems, 9(12), 1998, 1226–1236. doi:10.1109/71.737698
  4. [4] F. Zane, P. Marchand, R. Paturi, & S. Esener, Scalable networkarchitecture 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 attractivealternative 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 stargraph, Proc. on Supercomputing ’90, New York, November12–16, 1990, 476–485. doi:10.1109/SUPERC.1990.130058
  8. [8] K. Day & A. Tripathi, Arrangement graphs: A class ofgeneralised 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, Opticaltranspose 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 andoptimisation of the optical transpose interconnection system,in Optoelectronic Technology Centre, Program Review, CornellUniversity, Ithaca, NY, 1995.
  11. [11] A. Krishnamoorthy, P. Marchand, F. Kiamilev, & S. Esener,Grain-size considerations for optoelectronic multistage inter-connection networks, Applied Optics, 31(26), 1992, 5480– 5507.
  12. [12] K. Day & A. Al-Ayyoub, Topological properties of OTIS-networks, 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 Cor-poration, Beaverton, Oregon, 1986.
  14. [14] J. Rattler, Concurrent processing: A new direction in scientificcomputing, 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: Anew fault-tolerant routing for the binary n-cube, Journal ofSystems Architecture, 47(9), 2002, 783–793. doi:10.1016/S1383-7621(01)00031-5
  18. [18] P.T. Gaughan & S. Yalamanchili, Adaptive routing protocolsfor 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 inwormhole 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 Com-puter Science, Yale University, New Haven, CT, 1985.
  21. [21] H. Sullivan, T. Bashkow, & D. Klappholz, A large scale,homogeneous, fully distributed parallel machine, Proc. 4thAnnual Symp. Computer Architecture, 1977, 105–124. doi:10.1145/633615.810659
  22. [22] M.S. Chen & K.G. Shin, Adaptive fault-tolerant routing inhypercube 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 fault-tolerant 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 inthe presence of faults, Proc. 3rd Conf. Hypercube ConcurrentComputers 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–III166.250
  26. [26] T.C. Lee & J.P. Hayes, A fault-tolerant communication schemefor 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-hypercubeoptoelectronic computer, Informatica, 22, 1998, 263–269.
  28. [28] C.F. Wang, Algorithms for the OTIS optoelectronic computers,doctoral diss., Department of Computer Science, University ofFlorida, Gainesville, FL, 1998.
  29. [29] S. Graham & S. Seidel, The cost of broadcasting on star graphsand 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 tolerantwormhole routing strategy for k-ary n-Cubes, IEEE Trans.Computers, 40(1), 1991, 2–12. doi:10.1109/12.67315

Important Links:

Go Back