An advanced interconnection network called "HCC-ABL-tree (hierarchical completely-connected tree by additional bypass linking)" is proposed for constructing large PC clusters capable of distributed inter-node communication by using Ethernet switches with a small number of I/O-ports. A basic one-level CC-ABL-tree can be constructed by using small subarrays of processing nodes (PCs) providing interconnections with the complete connection scheme, and by connecting the nodes to a tree-structured bypass network with switches with a height of two so that every node of the subarray is allocated to a different second-level switch. A two- or three-level HCC-ABL-tree can be constructed by using the trees with one less number of levels as the components by connecting them to each other with the complete-connection scheme by using the second-level switches of the bypass network as the hierarchical interconnections. The maximum number of processing nodes in a cluster can be increased exponentially by increasing the number of hierarchical levels. The network diameter is two for a one-level tree, three for a two-level tree, and seven for a three-level tree. The proposed network can configure the processing nodes in the cluster as a square-mesh-connected array with any aspect ratio by graph embedding, where a newly proposed distributed routing algorithm can define the paths with no duplicated use of a link. This manner of configuring can also be achieved even when busy or faulty nodes exist in the cluster, while bypassing these nodes in a node-disjoint manner with a small congestion and dilation in the paths.

An advanced spare-connection scheme for k-out-of-n redundancy called "generalized additional bypass linking" is proposed for constructing fault-tolerant massively parallel computers with series-connected, mesh-connected, or tree-connected processing element (PE) arrays. This scheme uses bypass links with wired OR connections to selectively connect the primary PEs to a spare PE in parallel. These bypass links are allocated to the primary PEs by node-coloring of a graph with a minimum inter-node distance of three in order to minimize the number of bypass links (i.e., the chromatic number). The main advantage of this scheme is that it can be used for constructing various k-out-of-n configurations capable of enhanced PE-to-PE communication and broadcast while still achieving strong fault tolerance for these PEs and links. In particular, it enables the construction of optimal r-strongly-fault-tolerant configurations capable of direct k-out-of-n selections by providing r spare PEs and r extra connections per PE for any kind of array when node-coloring with a distance of three is used. This simple spare-circuit structure enhances fault tolerance more than conventional schemes do. The node-coloring patterns were constructed using new node-coloring algorithms and the chromatic numbers were evaluated theoretically. Enhanced PE-to-PE communication and broadcast were achieved by using new fault-tolerant routing algorithms based on the properties of the node-coloring patterns with four or five message transmission steps being optimal configurations with any size array.