About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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.