Theoretical Aspects of VLSI Pin Limitations
Author:
- Robert CypherRCRobert Cypher
- 1 April 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 22 (2) , 356-378
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 and 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 lower bounds on the pin requirements of mesh-connected, cube-connected-cycles, shuffle-exchange, and Ajtai–Komlós–Szemerédi (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.Keywords
This publication has 24 references indexed in Scilit:
- Compressions and isoperimetric inequalitiesJournal of Combinatorial Theory, Series A, 1991
- An Isoperimetric Inequality on the Discrete TorusSIAM Journal on Discrete Mathematics, 1990
- Interconnection networks: Physical design andperformance analysisJournal of Parallel and Distributed Computing, 1986
- Tight Bounds on the Complexity of Parallel SortingIEEE Transactions on Computers, 1985
- Evaluation of cube and data manipulator networksJournal of Parallel and Distributed Computing, 1985
- The VLSI optimality of the aks sorting networkInformation Processing Letters, 1985
- Sorting inc logn parallel stepsCombinatorica, 1983
- Pin Limitations and Partitioning of VLSI Interconnection NetworksIEEE Transactions on Computers, 1982
- A Self-Routing Benes Network and Parallel Permutation AlgorithmsIEEE Transactions on Computers, 1981
- A note on the edges of the n-cubeDiscrete Mathematics, 1976