Critique and an Appraisal of VLSI Models of Computation

摘要

The central question in the design and analysis of algorithms is the definition of the model of computation to be adopted. Indeed, performance becomes meaningful only in relation to a given model. This model is normally the simplified abstraction of a class of real or imaginary machines; for example, the RAM or Random-Access-Machine, is the model of practically the totality of existing (Von Neumann type) processors. The model of computation is the simplest possible, compatibly with the requirement of being realistic. In other words, while a model aims at capturing the essential traits of a system or technology, its simplicity is what enables theoretical appraisals of performance. In this paper the author evaluate various proposed VLSI models of computation. While there is consensus on the appraisal of chip area, controversy remains with regard to computation time. Thus they have analyzed in detail the propagation of signals on dispersive lines. The results are expressed in terms of a dimensional parameters characteristic of any given fabrication technology. The conclusion is that both current and projected silicon technologies fall within the realm of the capacitive model, where a dispersive line can be replaced by a capacitance proportional to its length.