More Web Proxy on the site http://driver.im/

research-article

Depth-First Search Approach for Fault-Tolerant Routing in Hypercube Multicomputers

Authors:

K. G. ShinAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 1, Issue 2

Pages 152 - 159

https://doi.org/10.1109/71.80143

Published: 01 April 1990 Publication History

Abstract

Using depth-first search, the authors develop and analyze the performance of a routing scheme for hypercube multicomputers in the presence of an arbitrary number of faulty components. They derive an exact expression for the probability of routing messages byway of optimal paths (of length equal to the Hamming distance between the corresponding pair of nodes) from the source node to an obstructed node. The obstructed node is defined as the first node encountered by the message that finds no optimal path to the destination node. It is noted that the probability of routing messages over an optimal path between any two nodes is a special case of the present results and can be obtained by replacing the obstructed node with the destination node. Numerical examples are given to illustrate the results, and they show that, in the presence of component failures, depth-first search routing can route a message to its destination by means of an optimal path with a very high probability.

References

[1]

{1} Y. Saad and M. H. Schultz, "Topological properties of hypercubes," IEEE Trans. Comput. , vol. C-37, pp. 867-872, July 1988.

[2]

{2} F. Ercal, J. Ramanujam, and P. Sadayappan, "Task allocation onto a hypercube by recursive mincut bipartitioning," in Proc. 3rd Conf. Hypercube Concurrent Comput. Appl. , Jan. 19-20, 1988, pp. 210-221.

[3]

{3} M.-S. Chen and K. G. Shin, "Processor allocation in an n -cube multiprocessor using gray codes," IEEE Trans. Comput. , vol. C-36, pp. 1396-1407, Dec. 1987.

[4]

{4} M.-S. Chen and K. G. Shin, "On relaxed squashed embedding of graphs into a hypercube," SIAM J. Comput. , vol. 18, pp. 1226-1244, Dec. 1989.

Digital Library

[5]

{5} T. N. Mudge and T. S. Abdel-Rahman, "Vision algorithms for hypercube machines," J. Parallel Distributed Comput. , vol. 4, pp. 79-94, 1987.

Digital Library

[6]

{6} T. F. Chan and Y. Saad, "Multigrid algorithms on the hypercube multiprocessors," IEEE Trans. Comput. , vol. C-35, pp. 969-977, Nov. 1986.

[7]

{7} C. Aykanat, F. Ozguner, F. Ercal, and P. Sadayappan, "Iterative algorithms for solution of large sparse systems of linear equations on hypercubes," IEEE Trans. Comput. , vol. C-37, pp. 1554-1568, Dec. 1988.

[8]

{8} C. L. Seitz, "The cosmic cube," Commun. Assoc. Comp. Mach. , vol. 28, no. 1, pp. 22-33, Jan. 1985.

Digital Library

[9]

{9} NCUBE Corp., "NCUBE/ten: An overview," Beaverton, OR, Nov. 1985.

[10]

{10} Intel Corp., Intel iPSC System Overview , Jan. 1986.

[11]

{11} S. L. Johnson and C. T. Ho, "Optimum broadcasting and personalized communication in hypercubes," IEEE Trans. Comput. , vol. C-38, pp.1249-1268, Sept. 1989.

[12]

{12} M.-S. Chen and K. G. Shin, "On hypercube fault-tolerant routing using global information," in Proc. Fourth Conf. Hypercube Concurrent Comput. Appl. , Mar. 6-8, 1989.

[13]

{13} C. K. Kim and D. A. Reed, "Adaptive packet routing in a hypercube," in Proc. 3rd Conf. Hypercube Concurrent Comput. Appl. , Jan. 19-20, 1988, pp. 625-630.

[14]

{14} J. G. Kuhl and S. M. Reddy, "Distributed fault tolerance for large multiprocessor systems," in Proc. 7th Annu. Int. Symp. Comput. Architecture , May 1980, pp. 23-30.

Digital Library

[15]

{15} T. C. Lee and J. P. Hayes, "Routing and broadcasting in faulty hypercube computers," in Proc. 3rd Conf. Hypercube Concurrent Appl. , Jan. 19-20, 1988, pp. 346-354.

[16]

{16} P. Ramanathan and K. G. Shin, "Reliable broadcast in hypercube multicomputers," IEEE Trans. Comput. , vol. C-37, pp. 1654-1656, Dec. 1988.

[17]

{17} J. R. Armstrong and F. G. Gray, "Fault diagnosis in a Boolean n - cube array of multiprocessors," IEEE Trans. Comput. , vol. C-30, pp. 587-590, Aug. 1981.

[18]

{18} M.-S. Chen and K. G. Shin, "Message routing in an injured hypercube," in Proc. 3rd Conf. Hypercube Concurrent Comput. Appl. , Jan. 19-20, 1988, pp. 312-317.

[19]

{19} J. M. Gordon and Q, F. Stout, "Hypercube message routing in the presence of faults," in Proc. 3rd Conf. Hypercube Comput. Appl. , Jan. 19-20, 1988, pp. 318-327.

[20]

{20} E.Chow, H. S. Madan, J. C. Peterson, D. Grunwald, and D. Reed, "Hyperswitch network for the hypercube computer," in Proc. 15th Annu. Int. Symp. Comput. Architecture, May 30-June 2, 1988, pp. 90-99.

[21]

{21} T. Y. Feng, "A survey of interconnection networks," IEEE Comput. , pp. 12-27, Dec. 1981.

Digital Library

[22]

{22} M.-S. Chen, K. G. Shin, and D. D. Kandlur, "Addressing, routing, and broadcasting in hexagonal mesh multiprocessors," IEEE Trans. Comput. , vol. C-39, pp. 10-18, Jan. 1990.

[23]

{23} F. Harary, Graph Theory . Reading, MA: Addison-Wesley, 1969.

[24]

{24} E. N. Gilbert, "Gray codes and paths on the n-cube," Bell Syst. Tech. J. , vol. 37, pp. 263-267, 1973.

[25]

{25} D. E. Knuth, The Art of Computer Programming , Vol. 3. Reading, MA: Addison-Wesley, 1973.

[26]

{26} A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms . Reading, MA: Addison-Wesley, 1974.

Digital Library

[27]

{27} C. L. Liu, Introduction of Combinatorial Mathematics . New York: McGraw-Hill, 1968.

Cited By

Otake KMouri KKaneko K(2018)Fault-tolerant Routing Methods in Crossed CubesProceedings of the 10th International Conference on Advances in Information Technology10.1145/3291280.3291782(1-8)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1145/3291280.3291782
Habibian HPatooghy A(2017)Fault-tolerant routing methodology for hypercube and cube-connected cycles interconnection networksThe Journal of Supercomputing10.1007/s11227-017-2033-773:10(4560-4579)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s11227-017-2033-7
Tsai TChen YTan J(2016)Optimal Edge Congestion of Exchanged HypercubesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2014.238728427:1(250-262)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1109/TPDS.2014.2387284
Show More Cited By

Depth-First Search Approach for Fault-Tolerant Routing in Hypercube Multicomputers
1. Networks
  1. Network protocols
    1. Network layer protocols
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Adaptive Fault-Tolerant Routing in Hypercube Multicomputers

A connected hypercube with faulty links and/or nodes is called an injured hypercube. A distributed adaptive fault-tolerant routing scheme is proposed for an injured hypercube in which each node is required to know only the condition of its own links. ...
Fault-tolerant routing strategy using routing capability in hypercube multicomputers
ICPADS '96: Proceedings of the 1996 International Conference on Parallel and Distributed Systems

This paper addresses fault-tolerant routing which is concerned with finding feasible minimum paths in a faulty hypercube. The concept of routing capability, which is defined with respect to the entire spectrum of distance, is proposed to assist routing ...
Fault tolerant routing in toroidal networks
PAS '95: Proceedings of the First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis

We give an O(r/sup 2/) time algorithm for constructing a fault-free routing path of optimal length between any true non-fault nodes of an r-dimensional torus with 2r-1 faulty nodes. We show that the Rabin diameter of a r-dimensional torus is its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 1, Issue 2

April 1990

129 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © Copyright © 1990 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 April 1990

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Otake KMouri KKaneko K(2018)Fault-tolerant Routing Methods in Crossed CubesProceedings of the 10th International Conference on Advances in Information Technology10.1145/3291280.3291782(1-8)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1145/3291280.3291782
Habibian HPatooghy A(2017)Fault-tolerant routing methodology for hypercube and cube-connected cycles interconnection networksThe Journal of Supercomputing10.1007/s11227-017-2033-773:10(4560-4579)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s11227-017-2033-7
Tsai TChen YTan J(2016)Optimal Edge Congestion of Exchanged HypercubesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2014.238728427:1(250-262)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1109/TPDS.2014.2387284
Azizi SSafaei FRoozikhar M(2015)A fault-tolerant routing algorithm in HyperX topology based on unsafety vectorsThe Journal of Supercomputing10.1007/s11227-014-1355-y71:4(1224-1248)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s11227-014-1355-y
Abd-El-Barr MGebali F(2014)Reliability analysis and fault tolerance for hypercube multi-computer networksInformation Sciences: an International Journal10.1016/j.ins.2013.10.031276:C(295-318)Online publication date: 20-Aug-2014
https://dl.acm.org/doi/10.1016/j.ins.2013.10.031
Hongmei L(2007)A performance guaranteed new algorithm for fault-tolerant routing in folded cubesProceedings of the 1st annual international conference on Frontiers in algorithmics10.5555/1776166.1776188(236-243)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.5555/1776166.1776188
Hongmei L(2007)A New Fault-Tolerant Routing Algorithm for m-ary n-cube Multi-computers and Its Performance AnalysisProceedings of the 7th international conference on Computational Science, Part I: ICCS 200710.1007/978-3-540-72584-8_86(648-651)Online publication date: 27-May-2007
https://dl.acm.org/doi/10.1007/978-3-540-72584-8_86
Xiang D(2006)Fault-tolerant routing in hypercubes using partial path set-upFuture Generation Computer Systems10.1016/j.future.2006.02.00422:7(812-819)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.1016/j.future.2006.02.004
Loh PHsu WPan Y(2005)The Exchanged HypercubeIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2005.11316:9(866-874)Online publication date: 1-Sep-2005
https://dl.acm.org/doi/10.1109/TPDS.2005.113
Safaei FKhonsari AFathy MOuld-Khaoua M(2005)Performance Modelling and Analysis of Pipelined Circuit Switching in Hypercubes with FaultsProceedings of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region10.1109/HPCASIA.2005.77Online publication date: 30-Nov-2005
https://dl.acm.org/doi/10.1109/HPCASIA.2005.77
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents