Article Sidebar

Submitted
Apr 25, 2017
Published
Jun 1, 2005
Download
PDF
Statistic
Read Counter : 335 Download : 238

Main Article Content

Abstract

We obtain the conditional fault-diameter of the square torus interconnection network under the condition of forbidden faulty sets (i.e. assuming that each non-faulty processor has at least one non-faulty neighbor). We show that under this condition, the square torus, whose connectivity is 4, can tolerate up to 5 faulty nodes without becoming disconnected. The conditional node connectivity is, therefore, 6. We also show that the conditional fault-diameter of the square torus is equal to the fault-free diameter plus two. With this result the torus joins a group of interconnection networks (including the hypercube and the star-graph) whose conditional fault-diameter has been shown to be only two units over the fault-free diameter. Two fault-tolerant routing algorithms are discussed based on the proposed vertex disjoint paths construction.

 

 

Keywords

Fault-tolerance forbidden faulty sets torus node connectivity conditional node connectivity conditional fault-diameter fault-tolerant routing.

Article Details

References

  1. CASADO, R., BERMUDEZ, A., DUATO, J., QUILES, F.J., and SANCHEZ, J.L. 2001. A Protocol for Deadlock-Free Dynamic Reconfiguration in High Speed Local Area Networks, IEEE Transactions on Parallel and Distributed Systems, 12(2): 115-132.
  2. CHEN, C.L., and CHIU, G.M. 2001. A Fault-Tolerant Routing Scheme for Meshes with Non Convex Faults," IEEE Transactions on Parallel and Distributed Systems, 12(5): 467-475.
  3. DAY, K., and AL-AYYOUB, A.E. 1997. Fault Diameter of k-ary n-cube Networks, IEEE Trans. on Parallel and Distributed Systems, 8(9): 903-907.
  4. DAY, K., and AL-AYYOUB, A.E. 2001. Adaptive Fault-Tolerant Routing in Star Networks, Journal of Interconnection Networks, 2(2): 213-231.
  5. ESFAHANIAN, A.H. 1989. Generalized Measures of Fault Tolerance with Application to n-Cube Networks, IEEE Transactions on Computers, 38(11): 1586-1591.
  6. GOMEZ, M., DUATO, J., FLICH, J., LOPEZ, P., ROBLES, A., NORDBOTTEN, N., LYSNE, O., and SKEIE, T. 2004. An Efficient Fault-Tolerant Routing Methodology for Meshes and Tori, Computer Architecture Letters, 3, May.
  7. HO, C.T., and STOCKMEYER, L. 2002. A New Approach to Fault-Tolerant Wormhole Routing for Mesh-Connected Parallel Computers, Proceedings of 16th International Parallel and Distributed Processing Symposium, April.
  8. IBM BG/L TEAM, An Overview of BlueGene/L Supercomputer, ACM Supercomputing Conference, 2002.
  9. LATIFI, S. 1993. Combinatorial Analysis of Fault-Diameter of the n-Cube, IEEE Transactions on Computers, 42(1): 27-33.
  10. LATIFI, S., HEGDE, M., and NARAGHI-POUR, M. 1994. Conditional Connectivity Measures for large Multiprocessor Systems, IEEE Trans. on Computers, 43(2): 218-222.
  11. LYSNE, O., PINKSTON, T., and DUATO, J. 2003. A Methodology for Developing Dynamic Network Reconfiguration Processes, Proceedings of the International Conference on Parallel Processing, pp. 77-86.
  12. NORDBOTTEN, N., GOMEZ, M., FLICH, J., LOPEZ, P., ROBLES, A., SKEIE, T., LYSNE, O., and DUSTO, J. 2004. A Fully Adaptive Fault-Tolerant Routing Methodology Based on Intermediate Nodes, Proceedings of the IFIP International Conference on Network and Parallel Computing, pp. 341-356.
  13. PINKSTON, T., PANG, R., and DUATO, J. 2003. Deadlock-Free Dynamic Reconfiguration Schemes for Increased Network Dependability, IEEE Transactions on Parallel and Distributed Systems, Vol. 14(8): 780-794.
  14. ROUSKOV, Y., LATIFI, S., and SRIMANI, P.K. 1996. Conditional Fault Diameter of Star Graph Networks, Journal of Parallel and Distributed Computing, 33: 91-97.
  15. SUH, Y., DAO, B., DUATO, J., and YALAMANCHILI, S. 2000. Software-Based Rerouting for Fault-Tolerant Pipelined Communication, IEEE Transactions on Parallel and Distributed Systems, 11(3): 193-211.
  16. WU, J. 1998. Fault Tolerance Measures for m-Ary n-Dimensional Hypercube Based on Forbidden Faulty Sets, IEEE Transactions on Computers, 47(8): 888-983.
  17. WU, J. 2003. Fault-Tolerant and Deadlock-Free Routing in 2D Meshes Based on Odd-Even Turn Model, IEEE Transactions on Computers, 52, No. 9, September.