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).

In recent years, many systolic algorithms have been proposed as solutions to computationally demanding problems in signal and image processing and other areas. Such algorithms exploit the regularity and parallelism of problems to achieve high performance and low I/O requirements. Since systolic algorithms generally consist of a few types of simple processors, or systolic cells, connected in a regular pattern, they are less expensive to design and implement than more general machines.

We propose a new model of computation for VLSI which is a refinement of previous models and makes the additional assumption that the time for propagating information is linear in the distance. Our approach is motivated by the failure of previous models to allow for realistic asymptotic analysis. While accommodating for basic laws of physics, this model tries to be most general and technology-independent. Thus, from a complexity viewpoint, it is especially suited for deriving lower bounds and trade-offs. We present new results for a number of problems including fan-in, addition, transitive functions, matrix multiplication, and sorting.