A Fault-Tolerant Optimal Message Routing Methodology for Cube-Connected-Cycles Parallel Computers

Gene Eu Jan ； Cheng-Hung Li ； Yung-Yuan Chen ； Shao-Wei Leu

《Journal of Marine Science and Technology》 21卷5期 (2013/10) Pp. 605-610

https://doi.org/10.6119/JMST-013-0522-2

並列摘要

A cube-connected-cycles (CCC) is a regular graph, suitable for constructing the interconnection network of parallel or multi-node computer systems. The CCC network possesses the features of symmetry, regularity, fault tolerance, and fixed degree of the network. Message delivery through an interconnection network sometimes fails due to processing node and/or link faults or simply because some processors are too busy to handle message transfer. To make a CCC-based parallel computer more resilient to node/link faults, this paper proposes an optimal routing method that guarantees to find a shortest path between the source and the destination nodes within a faulty CCC-based network if such a path exists. The proposed method is based on the concepts of radiation and backtracking and is able to find the shortest path with little impact on the network traffic load. The time complexity of our routing methodology is O (log N), where N is the number of nodes in the CCC architecture.

並列關鍵字

cube-connected-cycles ； parallel computer ； interconnection network ； backtracking ； radiation

參考文獻

Dandamudi, S. P., Hierarchical Hypercube Multicomputer Interconnection Networks, Ellis Horwood (1991).

Fang, J.-F., Lee, C.-M., Yen, E.-Y., Chen, R.-X., and Feng, Y.-C., “Novel broadcasting schemes on cube-connected cycles,” IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp.629-632 (2005).

Gaughan, P. T. and Yalamanchili, S., “Adaptive routing protocols for hypercube interconnection networks,” IEEE Computer, Vol. 26, No. 5, pp. 12-23 (1993).

Hwang, K., Advanced Computer Architecture; Parallelism, Scalability, Programmability, McGraw-Hill (1993).

Jang, J. E., “An optimal fault-tolerant broadcasting algorithm for a cube-connected cycles multiprocessor,” International Conference on Databases, Parallel Architectures and Their Application, pp. 206-215 (1990).