VLSI Performance Comparison of Banyan and Crossbar Communications Networks

Abstract

The performance characteristics of banyan and crossbar communications networks are compared in a VLSI environment, where it is assumed that the entire network resides on a single VLSI chip and operates in a circuit switched mode. A high-level model of the space (area) and time (delay) requirements for these networks is developed and relative performance comparisons are made based on a space-time product measure. The results differ significantly from those obtained with more traditional analyses which are usually based on switch aggregate comparisons and SSI-based delay calculations. The analysis presented shows that the area required by both networks grows as 0(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ). Time delay grows as 0(N) for the crossbar, and approximately 0[ N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a</sup> (log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> N) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ] for the banyan where 0 < a < 1. This contrasts with traditional results which yield 0(N log N) and 0(log N) switch and delay growth for banyan networks.