Cost-performance tradeoffs for interconnection networks

A major component of a large-scale parallel computer is the interconnection network that connects processors to memories in a shared-memory machine, or processors to processors in a multicomputer. This paper formally studies the relationship between network topology and network performance. Rectangular banyan networks are shown to provide maximum bandwidth/cost ratio for symmetric traffic. For their cost, contracting banyan networks are shown to provide maximum bandwidth up to a constant factor for semisymmetric traffic. For a restricted class of networks, contracting banyan networks are shown to provide exactly maximum bandwidth for semisymmetric traffic. Rectangular banyan networks are shown to provide optimal delay-to-cost tradeoffs for symmetric traffic. It is shown that, in many situations, optimal bandwidth is achieved by using a unique path to route information between each input-output pair.