Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-26096
Titel: | The communication complexity of VLSI circuits |
VerfasserIn: | Lengauer, Thomas |
Sprache: | Englisch |
Erscheinungsjahr: | 1982 |
Quelle: | Saarbrücken, 1983 |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
Abstract: | Very Large Scale Integration (VLSI) is a quickly emerging discipline in Computer Science that also raises many theoretical questions. The concept of a VLSI computation is very much different from classical concepts of a (sequential) computation. A VLSI computation is performed by many switching elements {s.e.'s) that are laid out on the planar chip surface and connected among each other with wires. These s.e.'s can perform computations in parallel. The computation of any s.e. depends on data received over wires from other s.e.'s. Several measures of complexity are of interest in this context: The chip area A, i.e., the area of wires and s.e.'s, the computing time T and the switching energy E. Clearly there exist tradeoffs between A and T. In this paper we survey lower bounds on the combined complexity measure AT2. The lower bounds are proved by accounting for the amount of work necessary just to communicate intermediate results between s.e.'s. In many cases the lower bounds we get are {asymptotically) tight, giving evidence for the fact that communication cost dominates the complexity of many VLSI computations. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-40731 hdl:20.500.11880/26152 http://dx.doi.org/10.22028/D291-26096 |
Schriftenreihe: | Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes |
Band: | 1982/14 |
Datum des Eintrags: | 3-Aug-2011 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
fb14_1982_14.pdf | 8,34 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.