The fat-stack and universal routing in interconnection networks

摘要

This paper shows that a novel network called the fat-stack is universally efficient and is suitable for use as an interconnection network in parallel computers. A requirement for the fat-stack to be universal is that link capacities double up the levels of the network. The fat-stack resembles the fat-tree and the fat-pyramid in hardware structure, but it has unique strengths. It is a construct of an atomic subnetwork unit consisting of one ring and one or more upward links to an upper subnetwork. This simple structure entails easy wirability. The network also uses fewer wires. More importantly, it has the capability to scale up to represent a large-scale distributed network. We developed efficient routing algorithms specific to the fat-stack. Our universality proof shows that a fat-stack variant with increased links and of area G(A) can simulate any competing network of area A with O(log A) overhead independently 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. (c) 2006 Elsevier Inc. All rights reserved.