(A) hierarchical hypercube network for parallel computers and a fault-tolerant routing algorithm in hypercube computers

Abstract

Major topics of this thesis are concentrated on two issues: (1) Optimal routing algorithms of the hierarchical cubic network (HCN) and a hierarchical hypercube network (HHN) based on the extension of HCN and (2) Fault-tolerant routing algorithm and distributed fault-free subcube identification algorithms in a faulty hypercube. The hypercube topology has many advantages. However, it is not suitable for very large-scale parallel computers due to rapid increase of links. So, we need interconnection networks which have the smaller node degree and hold many advantages of the hypercube. The HCN proposed by Ghose and Desai is a network with these desirable properties. The HCN has the smaller diameter regardless of the smaller node degree. The performance of parallel algorithms with regular pattern of communications is identical to their performance on a hypercube. We propose the optimal routing algorithm in the HCN and show that the diameter of HCN(n, n) which consists of $2^{2n}$ nodes is $n+\lceil (n+1)/3 \rceil + 1$ while its node degree is only n+1. Incomplete HCN``s are also discussed. We also propose the hierarchical hypercube network (HHN), which is a multiple level extension of the HCN, and deal with the routing algorithm, broadcasting algorithm, and some properties. The HHN has a smaller number of links than the comparable hypercube. In particular, the HHN network with $2^K$ nodes can be constructed with the node degree about $2\surd\overline{K}$ while the node degree of the comparable hypercube is K . Due its smaller node degree, the HHN is an interconnection network suitable for constructing large scale parallel computers. Regardless of its smaller node degree, many parallel algorithms can be executed in HHN with the same time complexity as in hypercube and a hypercube can emulate the comparable hypercube in O(1) time. Thus, HHN is a good alternative to the popular hypercube network for large scale parallel systems. As the second topic, fault-tolerant metho...