The performance of multilective VLSI algorithms

摘要

Chip area and computation time are the resource parameters of greatest importance in VLSI algorithms. Chip area is used for computation, storage, and for communication, the role of the latter being special to VLSI. 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. This measure consolidates in one place several algorithmic and geometric issues that are usually dealt with separately in most analyses of VLSI algorithms. 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.