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

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

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.