A model of computation for VLSI with related complexity results
- 1 July 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 32 (3) , 573-588
- https://doi.org/10.1145/3828.3834
Abstract
A new model of computation for VLSI, based on the assumption that time for propagating information is at least linear in the distance, is proposed. While accommodating for basic laws of physics, the model is designed to be general and technology independent. Thus, from a complexity viewpoint, it is especially suited for deriving lower bounds and trade-offs. New results for a number of problems, including fan-in, transitive functions, matrix multiplication, and sorting are presented. As regards upper bounds, it must be noted that, because of communication costs, the model clearly favors regular and pipelined architectures (e.g., systolic arrays).Keywords
This publication has 8 references indexed in Scilit:
- Fourier Transforms in VLSIIEEE Transactions on Computers, 1983
- Three-Dimensional VLSIJournal of the ACM, 1983
- Area—Time Optimal VLSI Circuits for ConvolutionIEEE Transactions on Computers, 1983
- A Combinatorial Limit to the Computing Power of VLSI CircuitsIEEE Transactions on Computers, 1983
- A critique of network speed in VLSI models of computationIEEE Journal of Solid-State Circuits, 1982
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- On the Area Required by VLSI CircuitsPublished by Springer Nature ,1981
- From Electron Mobility to Logical Structure: A View of Integrated CircuitsACM Computing Surveys, 1980