Development of Routing Algorithms for Interconnection Networks based on Cayley Graphs

点击翻译按钮获取中文摘要

Research results are summarized as follows:- Algorithm for node-to-set disjoint paths problem in Transposition graphs,- Algorithm for node-to-set disjoint paths problem in Bubble-sort graphs,- Algorithm for node-to-node disjoint paths problem in Bi-rotator graphs,- Algorithm for node-to-set disjoint paths problem in Bi-rotator graphs,- Algorithm for node-to-node disjoint paths problem in Burnt Pancake graphs- Proposal of Incomplete Pancake graphs and Algorithm for node-to-node disjoint paths problem in them,- Proposal of Incomplete Rotator graphs and Algorithm for node-to-node disjoint paths problem in them,- Algorithm for node-to-set disjoint paths problem in Pancake graphs,- Algorithm for set-to-set disjoint paths problem in Pancake graphs,- Algorithm for Hamiltonian cycles and Hamiltonian paths in faulty Burnt Pancake graphs,- Computation of diameters of 14- to 17-Pancake graphs, and- Proposal of (n, k)-Pancake graphs and their performance evaluation.In this study, we aimed to develop algorithms that retain the functions to send messages even if some faults occur on internal nodes and/or links with several Cayley graphs including new topologies, and we have attained our goals. These results may be small contributions compared to the whole research activities with respect to the massively parallel systems. However, selection of topologies is the most important issue in the design and implementation of the massively parallel systems. Therefore, we are convinced that these results have great meaning as foundation of the future researches.