scientific article; zbMATH DE number 3905849
[For the entire collection see Zbl 0555.00011.] Very Large Scale Integration (VLSI) is a quickly emerging discipline in Computer Science that also raises many theoretical questions. The concept of a VLSI computation is very much different from the classical concept of a (sequential) computation. A VLSI computation is performed by many switching elements (s.e.'s) that are laid out on the planar chip surface and connected among each other with wires. These s.e.'s can perform computations in parallel. The computation of any s.e. depends on data received over wires from other s.e.'s. Several measures of complexity are of interest in this context: The chip area A, i.e., the area of wires and s.e.'s, the computing time T and the switching energy E. Clearly there exist tradeoffs between A and T. In this paper we survey lower bounds on the combined complexity measure \(AT^ 2\). The lower bounds are proved by accounting for the amount of work necessary just to communicate intermediate results between s.e.'s. In many cases the lower bounds we get are (asymptotically) tight, giving evidence of the fact that communication cost dominates the complexity of many VLSI computations.
- Area-period tradeoffs for multiplication of rectangular matrices
- On problem transformability in VLSI
- scientific article; zbMATH DE number 4181292 (Why is no real title available?)
- scientific article; zbMATH DE number 3847304 (Why is no real title available?)
- scientific article; zbMATH DE number 3859042 (Why is no real title available?)
- scientific article; zbMATH DE number 4205989 (Why is no real title available?)
- scientific article; zbMATH DE number 4135399 (Why is no real title available?)
- Solving Undirected Graph Problems on VLSI
- Optimal Allocation of Area for Single-Chip Computations
- scientific article; zbMATH DE number 3915623 (Why is no real title available?)
- scientific article; zbMATH DE number 3919826 (Why is no real title available?)
- scientific article; zbMATH DE number 3936524 (Why is no real title available?)
- scientific article; zbMATH DE number 3990864 (Why is no real title available?)
- A model of computation for VLSI with related complexity results
- The VLSI Complexity of Selected Graph Problems
- On driving many long wires in a VLSI layout
- scientific article; zbMATH DE number 4043241 (Why is no real title available?)
- scientific article; zbMATH DE number 4051518 (Why is no real title available?)
- scientific article; zbMATH DE number 4061153 (Why is no real title available?)
- scientific article; zbMATH DE number 4102489 (Why is no real title available?)
- scientific article; zbMATH DE number 4108150 (Why is no real title available?)
- scientific article; zbMATH DE number 19782 (Why is no real title available?)
- scientific article; zbMATH DE number 88980 (Why is no real title available?)
- scientific article; zbMATH DE number 2134904 (Why is no real title available?)
- Energy reduction in VLSI computation modules: an information-theoretic approach
- scientific article; zbMATH DE number 3894473 (Why is no real title available?)
- Planar acyclic computation
- Area-time tradeoffs for universal VLSI circuits
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3683537)