Bisectional fault-tolerant communication architecture for supercomputer systems

A highly versatile communication architecture, the bisectional interconnection network, is proposed. These networks possess many attractive features such as small internode distances, ability to do self-routing which is easily extendible to failure conditions, and the capability of maximal fault tolerance. The proposed architecture allows optimal implementation of various logical configurations. Furthermore, the authors propose the use of a combinatorial structure, called the symmetric balanced incomplete block design (SBIBD), to partition these networks. This important property of partitioning allows the system´s expansion with fault tolerance and is utilized to describe two semidistributed fault-diagnostic strategies which require remarkably low overhead and at the same time identify a large number of faulty nodes. Furthermore, based on SBIBDs, a unique approach for making the diagnostic scheme itself fault tolerant is proposed