Research on Configurable PC Clusters Capable of Distributed Inter-Node Communication

提出了一种先进的互连网络--HCABL-TREE，用于构建能够在较小网络直径内进行分布式节点间通信的大型PC集群。通过使用作为环形、完全或二维环形网格连接图互连的处理节点的小子阵列，可以构建基本的ABL树。这些节点被连接到具有根据节点间距离为3的节点着色模式的集线器类型的交换机的树形结构网络，使得子阵列中的任何节点及其邻居被连接到树的叶级中提供的不同交换机。为了构建非常大的PC集群，可以将ABL-树扩展为h级肝细胞癌ABL-树。在该网络中，ABL树被用作h层分层完全连通图的组成部分，而交换机通常被用作每个分层层的互连。利用子阵中源节点的邻居节点作为与目的节点颜色相同的中继节点，通过叶级交换机以分布式方式实现节点间的并行通信。该网络通过图形嵌入法将网络中的处理节点配置为任意纵横比的正方形环形网格连接阵列。提出了一种新的多路由分布式路由算法，在定义嵌入图的路径的同时，以节点不相交的方式绕过阵列中繁忙或故障的节点，路径中的拥塞和扩张很小。最终报告提出了一种基于循环图、容错配置、多路由分布式路由、PC集群原型、节点间通信性能评估和实用并行处理等方法来构建HCABL树。

An advanced interconnection network called HCC ABL-tree is proposed for constructing large PC clusters capable of distributed inter-node communication within a small diameter of the network. A basic ABL-tree can be constructed by using small subarrays of the processing nodes interconnected as a ring-, completely-, or two-dimensional toroidal mesh-connected graph. These nodes are connected to a tree-structured network with switches of a hub type according to a node-coloring pattern with an inter-node distance of three so that any node and its neighbors in the subarray are connected to a different switch provided in the leaf level of the tree. To construct very large PC clusters, the ABL-tree can be expanded as an h-level HCC ABL-tree. In this network, the ABL-trees are used as the component of an h-level hierarchical completely-connected graph and the switches are commonly used as interconnections in every hierarchical level. Parallel inter-node communication can be achieved via the switches in the leaf level in a distributed manner while using a neighboring node of the source node in the subarray as relay node whose color is the same as that of the destination node. The proposed network can configure the processing nodes in it as a square toroidal mesh-connected array with any aspect ratio by graph-embedding. A newly proposed multiplex distributed routing algorithm can define the paths of the embedded graph while bypassing busy or faulty nodes in the array in a node-disjoint manner with a small congestion and dilation in the paths. The final report includes a new construction method for HCC ABL-trees by using circulant graphs, fault-tolerant configuring, multiplex distributed routing, prototype PC clusters, and performance evaluation of inter-node communication and practical parallel processing.