Informatik - Fachberichte BB{1d 3: Rechnernetze und Datenfernverarbeitung. Fachtagung der Band 25: Programmiersprachen und Programmierentwicklung. GI tl,nd NTG 1976. Herausgegeben von D. Haupt und H. Petersen. 6. Fachtagung, Darmstadt, 1980. Herausgegeben von H.-J. VI, 309 Seiten. 1976. Hoffmann. VI, 236 Seiten. 1980. Band 4: Computer Architecture. Workshop of the Gesellschaft fUr Band 26: F. Gaffal, Datenverarbeitung im Hochschulbereich der Informatik 1975. Edited by W. Hiindler. VIII, 382 pages. 1976. USA. Stand und Entwicklungstendenzen. IX, 199 Seiten. 1980. Band 5: GI - 6. Jahrestagung. Proceedings 1976. Herausgegeben Band 27: GI-NTG Fachtagung, Struktur und Betrieb von Rechen von E. J. Neuhold. (vergriffen) systemen. Kiel, Miirz 1980. Herausgegeben von G. Zimmermann. IX, 286 Seiten. 1980. Band 6: B. Schmidt, GPSS-FORTRAN, Version II. EinfUhrung in die Simulation diskreter Systeme mit Hille eines FORTRAN-Pro Band 28: Online-Systeme im Finanz- und Rechnungswesen. grammpaketes, 2. Auflage. XIII, 535 Seiten. 1978. Anwendergespriich, Berlin, April 1980. Herausgegeben von P. Stahlknecht. X, 547 Seiten, 1980. Band 7: GMR-GI-GfK. Fachtagung Prozessrechner 1977. He rausgegeben von G. Schmidt. (vergriffen) Band 29: Erzeugung und Analyse von Bildern und Strukturen. DGaO - DAGM Tagung, Essen, Mai 1980. Herausgegeben von Band 8: Digitale Bildverarbeitung/Digital Image Processing. Gil S. J. Poppl und H. Platzer. VII, 215 Seiten. 1980. NTG Fachtagung, Munchen, Miirz 1977. Herausgegeben von H.-H. Nagel. (vergriffen) Band 30: Textverarbeitung und Informatik. Fachtagung der GI, Band 9: Modelle fUr Rechensysteme. Workshop 1977. Heraus Bayreuth, Mai 1980. Herausgegeben von P. R. Wossidlo. VIII, gegeben von P. P. Spies. VI, 297 Seiten. 1977. 362 Seiten. 1980. Band 10: GI - 7. Jahrestagung. Proceedings 1977. Herausgegeben Band 31: Firmware Engineering. Seminar veranstaltet von der von H. J. Schneider. IX, 214 Seiten. 1977. gemeinsamen Fachgruppe "Mikroprogrammierung" des GI Fach ausschusses 3/4 und des NTG-Fachausschusses 6 vom 12. - 14. Band 11: Methoden der Informatik fUr RechnerunterstUtztes Ent Miirz 1980 in Berlin. Herausgegeben von W. K. Giloi. VII, 289 Seiten. werfen und Konstruieren, GI-Fachtagung, Munchen, 1977. Heraus 1980. gegeben von R. Gnatz und K. Samelson. VIII, 327 Seiten. 1977. Band 32: M. Kuhn, CAD Arbeitssituation. Untersuchungen zu den Band 12: Programmiersprachen. 5. Fachtagung der GI, Braun Auswirkungen von CAD sowie zur menschengerechten Gestaltung schweig, 1978. Herausgegeben von K. Alber. VI, 179 Seiten. 1978. von CAD-Systemen. VII, 215 Seiten. 1980. Band 13: W. Steinmuller, L. Ermer, W. Schimmel: Datenschutz bei Band 33: GI - 10. Jahrestagung. Herausgegeben von R. Wilhelm. riskanten Systemen. Eine Konzeption entwickelt am Beispiel eines XV, 563 Seiten. 1980. medizinischen Informationssystems. X, 244 Seiten. 1978. Band 14: Datenbanken in Rechnernetzen mit Kleinrechnern. Fach Band 34: CAD-Fachgespriich. GI -10. Jahrestagung. Heraus tagung der GI, Karlsruhe, 1978. Herausgegeben von W. Stucky und gegeben von R. Wilhelm. VI, 184 Seiten. 1980. E. Holler. (vergriffen) Band 35: B. Buchberger, F. Lichtenberger: Mathematik fUr Infor Band 15: Organisation von Rechenzentren. Workshop der Gesell matiker I. Die Methode der Mathematik. XI, 315 Seiten. 1980. schaft fur Informatik, Gottingen, 1977. Herausgegeben von D. Wall. X, 310 Seiten. 1978. Band 36: The Use of Formal Specification of Software. Berlin, Juni 1979. Edited by H. K. Berg and W. K. Giloi. V, 388 pages. 1980. Band 16: GI - 8. Jahrestagung, Proceedings 1978. Herausgegeben von S. Schindler und W. K. Giloi. VI, 394 Seiten. 1978. Band 37: Entwicklungstendenzen wissenschaftlicher Rechen zentren. Kolloquium, Gottingen, Juni 1980. Herausgegeben von Band 17: Bildverarbeitung und Mustererkennung. DAGM Sympo D. Wall. VII, 163 Seiten. 1980. sium, Oberpfaffenhofen, 1978. Herausgegeben von E. Triendl. XIII, 385 Seiten. 1978. Band 38: Datenverarbeitung im Marketing. Herausgegeben von R. Thome. VIII, 377 pages. 1981. Band 18: Virtuelle Maschinen. Nachbildung und Verviellachung maschinenorientierter Schnittstellen. GI-Arbeitsseminar. Munchen Band 39: Fachtagung ProzeBrechner 1981. Munchen, Miirz 1981. 1979. Herausgegeben von H. J. Siegert. X, 230 Seiten. 1979. Herausgegeben von R. Baumann. XVI, 476 Seiten. 19l!1. Band 19: GI-9. Jahrestagung. Herausgegeben von K. H. Bohling Band 40: Kommunikation in verteilten Systemen. Herausgegeben und P. P. Spies. (vergriffen) von S. Schindler und J.C.w. Schroder. IX, 459 Seiten. 1981. Band 20: Angewandte Szenenanalyse. DAGM Symposium, Karls Band 41: Messung, Modellierung und Bewertung von Rechen ruhe 1979. Herausgegeben von J. P. Foith. XIII, 362 Seiten. 1979. systemen. GI-NTG Fachtagung. Julich, Februar 1981. Heraus Band 21: Formale Modelle fUr Informationssysteme. Fachtagung gegeben von B. Mertens. VIII, 368 Seiten. 1981. der GI, Tutzing 1979. Herausgegeben von H. C. Mayr und B. E. Meyer. VI, 265 Seiten. 1979. Band 42: W. Kilian, Personalinformationssysteme in deutschen GroBunternehmen. XV, 352 Seiten. 1981. Band 22: Kommunikation in verteilten Systemen. Workshop der Gesellschaft fUr Informatik e. V. . Herausgegeben von S. Schindler Band 43: G. Goos, Werkzeuge der Programmiertechnik. GI-Arbeits und J. C. W. Schroder. VIII, 338 Seiten. 1979. tagung. Proceedings, Karlsruhe, Miirz 1981. VI, 262 Seiten. 1981. Band 23: K.-H. Hauer, Portable Methodenmonitoren. Dialogsysteme Band 44: Organisation informationstechnik-geschOtzter offentlicher zur Steuerung von Methodenbanken: Softwaretechnischer Aufbau Verwaltungen. Fachtagung, Speyer, Oktober 1980. Herausgegeben und Effizienzanalyse. XI, 209 Seiten. 1980. von H. Reinermann, H. Fiedler, K. Grimmer und K. Lenk. 1981. Band 24: N. Ryska, S. Herda, Kryptographische Verfahren in der Band 45: R. Marty, PISA - A Programming System for Interactive Datenverarbeitung. V, 401 Seiten. 1980. Production of Application Software. VII, 297 Seiten. 1981. Informatik-Fachberichte Herausgegeben von W. Brauer im Auftrag der Gesellschaft fOr Informatik (GI) 89 Fachgesprache auf der 14. GI-Jahrestagung Braunschweig, 1.-2. Oktober 1984 Herausgegeben von H.-D. Ehrich Spri nger -Verlag Berlin Heidelberg New York Tokyo 1984 Herausgeber Hans-Dieter Ehrich Institut fUr Theoretische und Praktische Informatik Technische Universitat Braunschweig Postfach 3329,3300 Braunschweig CR Subject Classifications (1982): F.2.2, 1.2.9, 1.3.3, 1.6.3, J.2, J.6, J.7 CIP-Kurztitelaufnahme der Deutschen Bibliothek. Gesellschaft fOr Informatik: Fachgesprache auf der 14. GI-Jahrestagung: Braunschweig, 1.-2. Oktober 1984 / hrsg. von H.-D. Ehrich:-Berlin; Heidelberg; New York; Tokyo: Springer, 1984. (Informatik-Fachberichte; 89) ISBN-13: 978-3-540-13862-4 e-ISBN-13: 978-3-642-70087-3 001: 10.1007/978-3-642-70087-3 NE: Ehrich, Hans-Dieter [Hrsg.); Fachgesprache auf der vierzehnten GI-Jahres tagung; GT This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Further, storage or utilization of the described programms on data processing installations is forbidden without the written permission of the author. Under § 54 of the German Copyright law where copies are made for other than private use, a fee is payable to "Verwertungsgesellschaft Wort", Munich. © by Springer-Verlag Berlin Heidelberg 1984 2145/3140-543210 VORWORT Dieser Band enthalt die schriftlichen Beitrage zu den Fachgesprachen, die wahrend der 14. Jahrestagung der Gesellschaft fUr Informatik in Braunschweig veranstaltet wurden. Die Beitrage zum Hauptprogramm werden in einem gleichzeitig in derselben Reihe erscheinenden separaten Ta gungsband verbffentlicht. Die 14. Jahrestagung der Gesellschaft fUr Informatik steht unter dem Leitthema "Informatik und Ingenieurwissenschaften" Daran orientieren sich auch die hier verbffentlichten Fachgesprache. Der FachausschuB 4.2 der GI, "RechnergestUtztes Entwerfen und Projektieren", ist mit zwei Fachgesprachen vertreten: "Produktdefinierende Daten" (Ko ordinator: R.Gnatz) und "Methoden der Evaluierung und EinfUhrung von CAD-Systemen" (Koordinator: J.Encarnacao). Der FachausschuB 1.1, "Grund lagen der Informatik", behandelt aktuelle "Grundlagen der GroBtintegra tion (VLSI)" (Koordinator: K.Mehlhorn), und die Fachgruppe "Robotik" im FachausschuB 1.2, "KUnstliche Intelligenz und Mustererkennung", be schaftigt sich in ihrem Fachgesprach mit dem Thema "Industrieroboter und KUnstliche Intelligenz" (Koordinator: G.Hirzinger). Den Koordinatoren, Mitveranstaltern und Mitgliedern der ProgrammausschUs se der einzelnen Fachgesprache danke ich herzlich fUr ihre MUhe bei de ren Planung, Organisation und DurchfUhrung. Braunschweig, Jul i 1984 H.-D. Ehrich INHALTSUBERSICHT Seite Fachgesprach: Grundlagen der GroBtintegration (VLSI) Fachgesprach: Industrieroboter und KUnstliche Intelligenz 91 Fachgesprach: Produktdefinierende Daten 157 Fachgesprach: Methoden der Evaluierung und EinfUhrung von CAD-Systemen 261 Fachgesprach Grundlagen der GroBtintegration (VLSI) Koordination: K. Mehlhorn (SaarbrOcken) Fachgesprach: Grundlagen der GroBtintegration (VLSI) Vorwort Dieses Fachgesprach behandelt die Grundlagen des Entwurfs hochinte grierter Schaltkreise. Insbesondere werden die Themen - Entwurfssysteme (Hotz, Lengauer) - Simulation (Rammig) - Geometrische Probleme beim VLSI- Entwurf (Ottmann) - VLSI- gerechte Algorithmen (Schroder) - Testen (Mucha) - Verdrahtung (Lauther, Mehlhorn) behandelt. Diese Themen sind von groBer praktischer Bedeutung. Die Beitrage zeigen, daB gerade im Bereich des VLSI- Entwurfs Arbeiten mit direkter praktischer Anwendung und Arbeiten mit mehr grundsatzlicher Fragestellung sehr nahe beieinander liegen und sich gegenseitig be fruchten. Es ist daher angebracht, daB der FA Grundlagen der Informatik dieses Fachgesprach veranstaltet. Ich habe fur dieses Fachgesprach ein Format gewahlt, das vom ublichen abweicht. Alle Vortrage sind eingeladen. Ich habe die Autoren so aus gesucht, daB die wesentlichen Problemkreise abgedeckt sind; ich habe es allerdings den einzelnen Autoren uberlassen, wie sie ihren Bereich aus fullen. Das Fachgesprach ist also kein Tutorium. Ich hoffe -und die Sichtung der eingegangenen Beitrage macht mich sehr zuversichtlich- daB das gewahlte Format zu einem erfolgreichen Fachgesprach fuhren wird. (Kurt Mehlhorn) Organisator des Fachge sprachs Grundlagen des VLSI- Entwurfs INHALTSVERZEICHNIS Seite Th. Lengauer 5 Algorithmische Spezifikation von symbolischen Layouts integrierter Schaltkreise G. Hotz 17 Ober die logisch-topologische Entwurfsebene bei der Konstruktion groBer integrierter Schaltkreise F.J. Rammig 28 Simulation digitaler Systeme auf verschiedenen Abstraktions ebenen J. ~lucha 37 Testprobleme bei hochstintegrierten Schaltungen H. Schroder 47 VLSI-Realisierungen von Sortieralgorithmen Th. Ottmann 58 Geometrische Probleme beim VLSI-Design U. Lauther 69 Anwendung von Plane-sweep Verfahren bei der Layout erzeugung integrierter Schaltungen K. Mehlhorn 79 Ober Verdrahtungsalgorithmen Algorithmische Spezifikation von symbolischen Layouts integrierter Schaltkreise Thomas Lengauer Fachbereich 10 Universitat des Saarlandes D-6600 SaarbrUcken Zusammenfassung: Wir geben einen Uberblick tiber die Zielsetzungen bei der Entwicklung des HILL Systems (Hierarchical Layout Language). Das System ermoglicht den Einsatz machtiger algorithmischer Hilfsmittel wie Rekursion und Parametrisierung zur Spezifikation von symbolischen Lay outs integrierter Schaltkreise. Gegenwartig erlaubt das System neben diversen Moglichkeiten der UberprUfung von Layouts deren Kompaktierung in die vom Hersteller geforderten Maskendaten, sowie die funktionale Simulation auf dem Schalterniveau. Durch den Einsatz des Systems wird der ProzeB des Entwurfs regularer Layouts so stark abgekUrzt, daB es moglich wird, verschiedene Varianten eines Schaltkreisentwurfs durch zuspielen. Dabei gewinnt der Designer durch die Spezifikation auf symbolischer Ebene eine gewisse Unabhangigkeit von den Entwurfsregeln des Fabrikationsprozesses. Diese Unabhangigkeit erhoht sowohl die Effektivitat des Designers als auch die Robustheit des Layouts gegen tiber Xnderungen im FabrikationsprozeB. 6 1. EinfUhrung Die rasante Entwicklung auf dem Gebiet der Fabrikationsprozesse fUr integrierte Schaltkreise ermoglicht es, immer komplexere Strukturen auf Silizium zu bringen. Schaltkreise mit mehreren 100.000 Transistoren sind keine Seltenheit mehr. Die Ausnutzung dieser technologischen Mog lichkeiten stellt eine groBe Herausforderung an den Schaltkreisdesigner dar. Die Bewaltigung der Komplexitat der Schaltung ist nur mit Hilfe von starker Strukturierung des Schaltkreises moglich. Beim hierarchischen Schaltkreisentwurf werden aus den primitiven Bau steinen (Transistoren, Drahte, Gatter o.a.) Teilschaltkreise konstru iert, die dann im weiteren Entwurf oft in vielen Kopien verwendet wer den. So ergibt sich eine Hierarchie von Teilschaltkreisen, die man sich als einen Baum vorstellen kann. Jeder Knoten des Baumes reprasentiert eine Kopie eines Teilschaltkreises. Die Sohne eines Knotens reprasentie ren die Kopien von Teilschaltkreisen, die zum Entwurf des Teilschalt kreises verwendet wurden, den der Knoten reprasentiert. Die Wurzel re prasentiert den gesamten Schaltkreis; die Blatter des Baumes stellen jene Teilschaltkreise dar, die keine weiteren Teilschaltkreise enthalten, sondern vollstandig aus primitiven Bausteinen bestehen. Durch hierarchischen Schaltkreisentwurf laBt sich der Entwurfsaufwand stark reduzieren, da u.U. hochkomplizierte Teilschaltkreise durch ein facpes Kopieren mehrmals verwendet werden konnen. So wird nur ein Bruch teil der Schaltung tatsachlich explizit entworfen. Der Uberwiegende Teil der Schaltung wird durch Replikation generiert. Da die auf Silizium basierenden Technologien einen planaren Charakter haben, kommt hier dem Entwurf der planaren Einbettung des Schaltkreises (Layout) groBe Bedeutung zu. Das Layout legt die geometrische Anordnung der Schaltkreiselemente auf dem Silizium fest. Es wird in den soge nannten Maskendaten codiert, die die Fabrikation des Schaltkreises steuern. Auch Layouts lassen sich hierarchisch entwerfen. Das Layout eines Teil schaltkreises nennt man "Zelle". Meistens werden Zellen als rechteckig angenommen. An ihrem Rand liegen Kontaktpunkte, sog. Pins, mit denen die Zelle an die Schaltkreiselemente in ihrer Umgebung angeschlossen werden kann. (vgl. Abbildung 1) [Abbildung 1] Hierarchischer Entwurf auf der Ebene der Maskendaten wird vielerorts durch CAD Normen (z.B. CrF [Me83]) und Systeme (z.B. [LUCIFER, Electric,