BLOCK-SWITCH NETWORKS - A COST-EFFECTIVE CLASS OF INTERCONNECTION NETWORK

A new interconnection scheme is proposed for hierarchically constructi ng massively parallel systems, called the Block-Switch Network (BSN). Presented here is method of connecting together a number of identical basic atoms level by level, a basic atom being an arbitrary connected graph. A BSN is characterized by (G, m), where G represents the basic atom and m denotes the number of levels in hierarchical expansion. A p articular choice for G yields a family of hierarchical networks. The t opological properties of the BSN for the general case are investigated , and then the results gained from applying BSN to different basic ato ms are also discussed. The BSN enables us to construct new families of graphs more feasible and cost-effective. It also deserves mentioning that a shortest-path routing algorithm for the BSN is derived by reduc ing the routing problem to the K-best perfect matching problem. In par ticular, we implement fundamental parallel algorithms (descend/ascend) on the BSN(Q(n), m) where Q(n) denotes an n-cube, and demonstrate tha t the performance on the BSN(Q(n),m) is very close to that of the comp arable hypercube.