The Pancake-Hypercube Hybrid Network: A promising design feasible for VLSI implementations

摘要

Symmetric graphs, such as the hypercube, the star, and the pancake have been widely used as processor/communication interconnection networks. The hypercube has been recognized as the ideal structure for parallel computing. However, the implementation feasibility of the hypercube remains questionable when it comes to VLSI layout design for a large size cube-based system. The star and pancake networks were proposed recently as attractive alternatives to the popular hypercube for interconnecting processors on a parallel computer. Both the star and the pancake were shown having many desirable properties of the hypercube, and in several important aspects, they are better than the hypercube. Unfortunately, both the star and pancake networks have many serious disadvantages comparing with the hypercube. In this paper, we propose a class of new networks, the pancake-hypercube hybrid network (or PH networks). The PH network is constructed by combining both the hypercube and the pancake graphs so that it remedies several major disadvantages of the hypercube and pancake graph. This new class of networks provide more flexibility in choosing the size, degree, diameter, fault tolerance, and many other properties when designing massively parallel computing structures feasible for VLSI implementations.