A model of computation for VLSI with related complexity results

Bernard Chazelle; Louis Monier

doi:10.1145/800076.802485

A model of computation for VLSI with related complexity results

Bernard Chazelle, Louis Monier

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

34 Scopus citations

Abstract

We propose a new model of compulation for VLSI which is a refinement of previous models and makes the additional assumption that the lime 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.

Original language	English (US)
Title of host publication	Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981
Publisher	Association for Computing Machinery
Pages	318-325
Number of pages	8
ISBN (Print)	0897910419
DOIs	https://doi.org/10.1145/800076.802485
State	Published - May 11 1981
Externally published	Yes
Event	13th Annual ACM Symposium on Theory of Computing, STOC 1981 - Milwaukee, United States Duration: Jun 11 1981 → Jun 13 1981

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Other

Other	13th Annual ACM Symposium on Theory of Computing, STOC 1981
Country/Territory	United States
City	Milwaukee
Period	6/11/81 → 6/13/81

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/800076.802485

Cite this

@inproceedings{0e47a492d7084840aab2384d33bc7f90,

title = "A model of computation for VLSI with related complexity results",

abstract = "We propose a new model of compulation for VLSI which is a refinement of previous models and makes the additional assumption that the lime 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.",

author = "Bernard Chazelle and Louis Monier",

note = "Publisher Copyright: {\textcopyright} 1981 ACM.; 13th Annual ACM Symposium on Theory of Computing, STOC 1981 ; Conference date: 11-06-1981 Through 13-06-1981",

year = "1981",

month = may,

day = "11",

doi = "10.1145/800076.802485",

language = "English (US)",

isbn = "0897910419",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "318--325",

booktitle = "Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981",

}

Chazelle, B & Monier, L 1981, A model of computation for VLSI with related complexity results. in Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 318-325, 13th Annual ACM Symposium on Theory of Computing, STOC 1981, Milwaukee, United States, 6/11/81. https://doi.org/10.1145/800076.802485

A model of computation for VLSI with related complexity results. / Chazelle, Bernard; Monier, Louis.
Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981. Association for Computing Machinery, 1981. p. 318-325 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A model of computation for VLSI with related complexity results

AU - Chazelle, Bernard

AU - Monier, Louis

PY - 1981/5/11

Y1 - 1981/5/11

N2 - We propose a new model of compulation for VLSI which is a refinement of previous models and makes the additional assumption that the lime 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.

AB - We propose a new model of compulation for VLSI which is a refinement of previous models and makes the additional assumption that the lime 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.

UR - http://www.scopus.com/inward/record.url?scp=84976862424&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976862424&partnerID=8YFLogxK

U2 - 10.1145/800076.802485

DO - 10.1145/800076.802485

M3 - Conference contribution

AN - SCOPUS:84976862424

SN - 0897910419

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 318

EP - 325

BT - Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981

PB - Association for Computing Machinery

T2 - 13th Annual ACM Symposium on Theory of Computing, STOC 1981

Y2 - 11 June 1981 through 13 June 1981

ER -

A model of computation for VLSI with related complexity results

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this