The performance of multilective VLSI algorithms
Several models for VLSI algorithms have been postulated. The one treated in this paper differs from most others in that it explicitly permits inputs to be read multiple times, that is, algorithms used are multilective. The way in which lower bounds derived for VLSI depend on the number of times and places at which inputs are read are explored. The contribution of this paper is to present methods for treating such multilective algorithms and to apply these methods to a large variety of functions and predicates. Figuring prominently in this work is the planar circuit size of a problem. It is used to derive lower bounds to various area-time products. Also presented here is a method for deriving lower bounds on the area required by multilective algorithms.
- A Separator Theorem for Planar Graphs
- Area-time optimal VLSI networks for multiplying matrices
- Area-time tradeoffs for matrix multiplication and related problems in VLSI models
- Computational Work and Time on Finite Machines
- scientific article; zbMATH DE number 3532851 (Why is no real title available?)
- scientific article; zbMATH DE number 3566175 (Why is no real title available?)
- scientific article; zbMATH DE number 3628386 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- Information transfer and area-time tradeoffs for VLSI multiplication
- Space-Time Trade-Offs for Banded Matrix Problems
- Space-time trade-offs on the FFT algorithm
- The Area-Time Complexity of Binary Multiplication
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
- Two tapes versus one for off-line Turing machines
- Multilevel optimization in VLSICAD
- On the complexity of planar Boolean circuits
- On the power of multiple reads in a chip
- Communication Complexity and Lower Bounds on Multilective Computations
- Lower bounds for planar arithmetic circuits
- Lower bounds for planar arithmetic circuits
- Planar acyclic computation
This page was built for publication: The performance of multilective VLSI algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1069297)
