Today studies on high-performance computer processing mass storage data have been made. Parallel processing technology combining many computers is widely used to make high-performance computing power. The issue for parallel processing technology generally lies midway between designing parallel computers and an effective algorism.
This thesis designs and analyzes the Interconnection Networks connecting Processors in designing parallel computers. There is a network cost in the performance rating scale of the Interconnection Networks. The network cost is a value which multiplies a degree by a diameter. The degree means hardware cost and the diameter means software cost. The degree and the diameter are correlated.
When the degree increases commonly, the diameter decreases in value, but if the degree decreases, the diameter increases in value. This thesis proposes a new interconnection network that approximately reduces the degrees of the pancake graph in half to improve the widely-known network cost of the pancake graph. The Half Pancake graph(HPG) in this thesis has recursive structures and maximally fault tolerance, and the diameter for routing from random node S to node T is 3.5n+4 in the N-dimensional Half Pancake graph HPn.