Rechnergestützter Entwurf mikroelektronischer Schaltungen

Die Veranstaltung findet im Sommersemester statt.

Termine: immer Montags ab 13:45 Uhr in Raum 1332

Zuschnitt: 6 CP, 2V+1Ü, 3 SWS

This CAD Algorithm course is aimed at graduate students and serious seniors who want broad exposure to the physical design automation, optimization techniques and data structures inside modern VLSI design tools. Because of the increasingly high complexity of modern chip design, CAD tools become vital for delivering high VLSI system performance. Many of the leading edge CAD algorithms are built upon optimization techniques which will be introduced in this course. The applications of these techniques will be described through realistic VLSI CAD problems, especially VLSI physical design automation algorithms. Physical design automation related issues for the current state of the art will familiarize students with existing techniques in VLSI design. Students will understand the relationships between optimization techniques and various constraints posed by VLSI fabrication and design technology. Critical performance related parameters and their importance in CAD tools will be introduced. The key goals of this course are to prepare students for design and development of CAD tools and for research in physical design automation of VLSI systems.Moreover, the algorithms discussed can be applied to many other contemporary digital design problems with o ly little adaptation.

It's not a circuits class--although we will mention circuits a few times. It's not a digital design class or VLSI design class, in the sense that we'd design a system or a chip. Visit our VHDL course instead for this. Instead, we analyze and design algorithms (aka software) as used in CAD tools.

Our research group explores design optimization algorithms for the next-level design tools.

Beim Entwurf integrierter Schaltungen wird ausgehend von einer strukturellen Beschreibung (Gatternetzliste) das Layout als Fabrikationsvorlage generiert. Dieser Ablauf gliedert sich in mehrere Schritte, für deren Automatisierung entsprechende Algorithmen im CAD-System eingesetzt werden, die auf einer internen Repräsentation aller entwurfsrelevanten Daten arbeiten.

Aufbauend auf den theoretischen Grundlagen werden, jeweils dem Entwurfsablauf folgend, die Methoden und Algorithmen diskutiert, die die Basis für aktuelle industrielle CAD-Systeme für den Chipentwurf bilden. Damit wird ein tiefergehendes Verständnis für deren Funktionsweise sowie auftretende Einschränkungen und Probleme gefördert und ein zielgerichteter Einsatz dieser Tools ermöglicht. Das Verständnis der Algorithmen wird über Beispiele und Übungsaufgaben (in den Übungen und zum Selbststudium) unterstützt.

Die Vorlesung umfasst folgende Themengebiete:

• Entwurfsstile
• Abstraktionsebenen
• Physikalischer Entwurf
• Graphentheorie und Datenstrukturen
• Partitionierung
• Floorplanning und Platzierung
• Verdrahtung
• Simulation auf verschiedenen Abstraktionsebenen
• Fehlermodellierung und -simulation   

Die Methoden bei der Synthese von Gatternetzlisten, der sogenannten High-Level Synthese, werden in der Vorlesung "Synthese und Optimierung..." ausführlich behandelt. Über die Zieltechnologie FPGA (field-programmable gate array) können  Sie mehr in der Vorlesung "Rekonfigurierbare Strukturen" erfahren!

Die Vorlesung richtet sich an Master-StudentInnen der Informatik, Elektrotechnik und Mechatronik mit Interesse an technischer Informatik bzw. mit Interesse an modernen Hardware-Entwurfsverfahren.

Lernziele: Die/der Lernende kann

• Ablauf und Ziele des physikalischen Entwurfs skizzieren,
• vorgegebene bzw. bekannte Algorithmen erklären,
• Teilalgorithmen zu einem Gesamtablauf kombinieren,
• Implementierungen gegebener Algorithmen vergleichen,
• Implementierungen von Algorithmen entwickeln,
• Platzierungs- und Verdrahtungsergebnisse qualitativ beurteilen,
• Simulationsverfahren erklären und klassifizieren.

In der Vorlesung werden zudem Pseudocode-Formulierungen von Algorithmen verwendet. Sie sollen Pseudocode verstehen und auch schrittweise nachvollziehen lernen. Auch die Nachimplementierung von Algorithmen in einer Programmiersprache soll geübt werden.

Zur Vorlesung wird eine umfangreiche Sammlung an Unterlagen bereitgestellt.

Literatur: In der Vorlesung werden folgende Lehrbücher verwendet

• Sabih H. Gerez: Algorithms for VLSI Design Automation, John Wiley & Sons; Auflage: 1. Auflage (9. November 1998), ISBN: 0471984892 

• Naveed A. Sherwani: Algorithms for VLSI Physical Design Automation, Springer, Berlin; Auflage: 3. Auflage. (1. Januar 1999), ISBN: 0792383931 
• Michael J. S. Smith: Application-Specific Integrated Circuits, Addison-Wesley Longman, Amsterdam (6. August 1997), ISBN: 0201500221 
• Jens Lienig: Layoutsynthese elektronischer Schaltungen - Grundlegende Algorithmen für die Entwurfsautomatisierung, Springer, Berlin; Auflage: 1 (März 2006), ISBN: 3540296271

• Thomas Lengauer: Combinatorial Algorithms for Integrated Circuit Layout, Teubner Verlag; Auflage: 1 (1990), ISBN: 3519021102 

Zum Themenbereich Graphentheorie und Algorithmen:

• Robert Sedgewick, Kevin Wayne:Algorithms, Addison Wesley Pub Co Inc; Auflage: 0004 (23. Juli 2010), ISBN: 032157351X 

• Reinhard Diestel: Graphentheorie, Springer, Berlin; Auflage: 3., neu bearb. und erw. A. (2. März 2006), ISBN: 3540213910 

• Volker Turau:Algorithmische Graphentheorie, Oldenbourg; Auflage: 3., überarbeitete Auflage. (21. Oktober 2009), ISBN: 348659057X 

• George T. Heineman, Gary Pollice, Stanley Selkow (Autoren), Mary Treseler (Herausgeber): Algorithms in a Nutshell: A Dektop Quick Reference, O'Reilly Media; Auflage: 1 (21. Oktober 2008), ISBN: 059651624X 

 Weiterhin interessant sind:

• Rainer Brück: Entwurfswerkzeuge für VLSI-Layout, Hanser Fachbuchverlag (1993), ISBN: 3446174893 

• Bing Lu, S. Sapatnekar, Ding-Zhu Du (Herausgeber): Layout Optimization in VLSI Design, Springer, Berlin; Auflage: 1 (1. Januar 2001), ISBN: 1402000898

Der Leistungsnachweis wird in Form einer mündlichen Prüfung erbracht. Die genauen Modalitäten werden in der Veranstaltung bekannt gegeben.