Theoretical aspects of VLSI pin limitations

Abstract

This paper presents a formal model of the pin requirements of a parallel computer. This model is then used to obtain bounds on the pin requirements of different parallel machines on the tradeoffs between pins and time. Specifically, two new bounds are established on the relationship between pin requirements and the time needed to sort or permute data. This paper also gives new lover bounds on the pin requirements of mesh-connected, cube-connected-cycles, shuffle-exchange, and Ajtai-Komlos-Szemeredi (AKS) computers, and it gives new upper bounds on the pin requirements of shuffle-exchange and AKS computers. All of these bounds are tight to within a constant factor. Finally, the bounds on pin requirements are used to prove a tight lower bound on the time required to implement the AKS sorting algorithm on a shuffle-exchange or cube-connected-cycles computer.