Viable architectures for high-performance computing

Existing interprocessor connection networks are often plagued by poor topological properties that result in large memory latencies for distributed shared-memory (DSM) computers or multicomputers. On the other hand, scalable networks with very good topological properties are often impossible to build because of their prohibitively high very large scale integration (VLSI) (e.g. wiring) complexity. Such a network is the generalized hypercube (GH). The GH supports full connectivity of all of its nodes in each dimension and is characterized by outstanding topological properties. Also, low-dimensional GHs have very large bisection widths. We present here the class of highly-overlapping windows (HOWs) networks, which are capable of lower complexity than GHs, comparable performance and better scalability. HOWs are obtained from GHs by uniformly removing edges to produce feasible systems of lower wiring complexity. Resulting systems contain numerous highly-overlapping GHs of smaller size. The GH, the binary hypercube and the mesh all belong to this new class of interconnections. In practical cases, HOWs have higher bisection width than tori with similar node and channel costs. Also, HOWs have a very large degree of fault tolerance. This paper focuses on 2-D HOW systems. We analyze the hardware cost of HOWs, present graph embeddings and communications algorithms for HOWs, carry out performance comparisons with binary hypercubes and GHs and simulate HOWs under heavy communication loads. Our results show the suitability of HOWs for very-high-performance computing.