A Model of Computation for VLSI with Related Complexity Results

Bernard Chazelle, Louis Monier

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

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

Original languageEnglish (US)
Pages (from-to)573-588
Number of pages16
JournalJournal of the ACM (JACM)
Volume32
Issue number3
DOIs
StatePublished - Jul 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'A Model of Computation for VLSI with Related Complexity Results'. Together they form a unique fingerprint.

Cite this