The Fat-Stack and Universal Routing in Interconnection Networks

This paper shows that a novel network called the fat-stack is universally efficient when adequate capacity distribution is provided and is suitable for use as an interconnection network in parallel computers. The fat-stack resembles the fat-tree and the fat-pyramid in hardware structure, but it has its unique strengths. It is a construct of an atomic subnetwork unit consisting of one ring and one or more upward links to its upper subnetwork. This simple structure entails easy wirability. The network also uses less wires. More importantly, it has the capability to scale up to represent a large-scale distributed network. Our routing analysis shows that the fat-stack incurs certain unsurmountable delay when wires have uniform unit capacity assignment. But doubling capacity up the network forms a universal network. Our universality proof shows that a fat-stack variant with increased links and of area θ(A) can simulate any competing network of area A with 0(log A) overhead independent of wire delay. The universality result implies that the augmented fat-stack of a given size is nearly the best routing network of that size. The augmented fat-stack is the minimal universal network for an O(log A) overhead in terms of hardware usage. Actual simulations show that the performance of the augmented fat-stack approaches that of the fat-pyramid and is far higher than that of the fat-tree.