Pin Limitations and Partitioning of VLSI Interconnection Networks

Multiple processor interconnection networks can be characterized as having N´ inputs and N´ outputs, each being B´ bits wide. A major implementation constraint of large networks in the VLSI environment is the number of pins available on a chip, Np. Construction of large networks requires partitioning of the N´ * N´ * B´ network into a collection of N * N switch modules with each input and output port being B (B ≤ B´) bits wide. If each module corresponds to a single chip, then a large network can be implemented by interconnecting the chips in a particular manner. This correspondence presents a methodology for selecting the optimum values of N and B given values of N´, B´, Np, and the number of control lines per port. Models for both banyan and crossbar networks are developed and arrangements yielding minimum: 1) number of chips, 2) average delay through the network, and 3) product of number of chips and delay, are presented.