Fault-Tolerant Routing Algorithms for Hypercube Interconnection Networks

スポンサーリンク

概要

• 論文の詳細を見る

• Many reseachers have used hypercube interconnection networks for their good properties to construct many parallel processing systems. However, as the number of procossors increases, the probability of occurrences of faulty nodes also increases. Hence, for hyoercube interconnection cetworks which have faulty nodes, several efficient dynamic routing algorithms have been proposed which allow each node to hold status information of its neighbor nodes. In this paper, we propose an improved version of the algorithm proposed by Chiu and Wu by introducing the notion of full reachability. A fully reachable node is a node that can reach all nonfaulty nodes which have Hamming distance l from the node via paths of lengh l. In addition, we further improve the algorithm by classifying the possibilities of detours with respect to each Hamming distance between current and target nodes. We propose an initialization procedure whichmakes use of an equivalent condition to perform this classification efficiently. Moreover, we conduct a simulation to measure the improvement ratio and to compare our algorithms with others. The simulation results show that the algorithms are effective when they are applied to low-dimensional hypercube interconnection networks.

• 社団法人電子情報通信学会の論文
• 2001-01-01

著者

• Kaneko Keiichi

  Faculty Of Technology Tokyo University Of Agriculture And Technology

• ITO Hideo

  Faculty of Engineering, Chiba University

• Ito Hideo

  Faculty Of Engineering Chiba University

関連論文

• Internally-Disjoint Paths Problem in Bi-Rotator Graphs(Dependable Computing)
• Node-to-Set Disjoint Paths Problem in Pancake Graphs(Special Issue on Parallel and Distributed Computing, Applications and technologies)
• Node-Disjoint Paths Algorithm in a Transposition Graph(Algorithm Theory)
• X-Tolerant Test Data Compression for SOC with Enhanced Diagnosis Capability(Dependable Computing)
• A Learning Algorithm for Fault Tolerant Feedforward Neural Networks
• A Learning Algorithm for Fault Tolerant Feedforward Neural Networks (Special Issue on Fault-Tolerant Computing)
• Output Smoothing: A learning Algorithm for Fault Tolerant Neural Networks
• An Algorithm for Node-Disjoint Paths in Pancake Graphs
• Hybrid Pattern BIST for Low-Cost Core Testing Using Embedded FPGA Core(Dependable Computing)
• Minimum Feedback Node Sets in Trivalent Cayley Graphs(Special Issue on Parallel and Distributed Computing, Applications and technologies)
• Scan Design for Two-Pattern Test without Extra Latches(Dependable Computing)
• Fault-Tolerant Routing Algorithms for Hypercube Interconnection Networks
• An Algorithm for Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs(Dependable Communication)(Dependable Computing)
• FPGAs Complete Fault Diagnosis Based on Binary Tree BIST Method
• FPGAs Complete Fault Diagnosis Based on Binary Tree BIST Method
• Escape and Restoration Routing : Suspensive Deadlock Recovery in Interconnection Networks
• Low-Cost IP Core Test Using Tri-Template-Based Codes
• On the Activation Function and Fault Tolerance in Feedforward Neural Networks
• Deterministic Delay Fault BIST Using Adjacency Test Pattern Generation(Dependable Computing)
• Proposal of Testable Multi-Context FPGA Architecture(Dependable Computing)
• Redundant Design for Wallace Multiplier(Dependable Computing)

もっと見る 閉じる

スポンサーリンク