Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-26106
Titel: | Efficient algorithms for the constraint generation for integrated circuit layout compaction |
VerfasserIn: | Lengauer, Thomas |
Sprache: | Englisch |
Erscheinungsjahr: | 1983 |
Quelle: | Saarbrücken, 1983 |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
Abstract: | A compactor for VLSI layouts is an essential component in many CAD systems for VLSI design. It reduces the area of a given layout violating any of the design rules dictated by the fabrication process. In many CAD systems for VLSI design the compacter generates a number of linear inequalities from the circuit layout. These so-called constraints restrict the coordinates of the layout components. The resulting inequality system is then solved in some optimum way. The solution of such inequality system can be done efficiently. The generation of the constraints, however, is a problem for which no efficient algorithms have been devised so far. We define the graph problem underlying the constraint generation for VLSI circuit compaction. Furthermore we develop efficient, i.e., O(nlogn) time algorithms for the generation of constraint systems that allow to change the layout topology during the conpaction in order to yield good compaction results, but at the same time are sparse enough to be solved efficiently, i.e., of size O(n). These algorithms are simple enough to be implemented. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-41116 hdl:20.500.11880/26162 http://dx.doi.org/10.22028/D291-26106 |
Schriftenreihe: | Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes |
Band: | 1983/06 |
Datum des Eintrags: | 23-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_1983_06ocr.pdf | 2,88 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.