Algorithmen im Chip-Entwurf
- Bereich
- Computer Microsystems
- Fachrichtung
- Technische Informatik, Elektrotechnik/Datentechnik
- Art
- IV4 oder V2
- Dozent
- Andreas Koch
- Voraussetzungen
- Grundkenntnisse des Entwurfs digitaler Schaltungen (z.B. Technische Grundlagen der Informatik I+II), Algorithmen und Datenstrukturen, Java
- Inhalt
- Praktische Einführung in Algorithmen und Datenstrukturen verschiedener CAD-Werkzeuge für den Chip-Entwurf. Dabei werden zunächst allgemein anwendbare Optimierungsverfahren und Graph-Algorithmen vorgestellt. Anschließend wird ihr Einsatz zur Lösung spezieller Probleme auf verschiedenen Ebenen des Chip-Entwurfs diskutiert, z.B. Plazierung und Verdrahtung. Parallel zur Vorlesung werden am Beispiel einer einfachen FPGA-Architektur ausgewählte Verfahren praktisch in Java implementiert und untersucht. Dabei werden eine Reihe von kleineren gefolgt von einer komplexeren Aufgabe bearbeitet.
- Literatur
- Sabih Gerez, ``Algorithms for VLSI Design Automation'', Ausgewählte wissenschaftliche Arbeiten
- Credits
- 6.0 durch erfolgreiches Absolvieren des praktischen Teils (Aufgaben, Kolloquien, Vorträge), 3.0 bei Beschränkung auf die Vorlesung
- Ort
- S2|02, C120
- Zeit
- Di, 11:40-13:20 Uhr; Fr 9:50-11:30; Kolloquien nach Abgaben Donnerstag nachmittags
- Anmeldung
- Für diese Veranstaltung ist unbedingt eine Anmeldung über das WebReg-System erforderlich (jetzt eröffnet).
- Prüfung
- Für den Modus 2 SWS (3.0 CP) findet die Prüfung vorlesungsbegleitend in Form von zwei Teilklausuren statt. Diese werden geschrieben am Do, 30.11.06 von 17:15-18:00 Uhr in S2 06 | 030 und am Do, 08.02.07 von 18:15-19:00 Uhr in S3 11 | 08. Im 4SWS-Modus (6.0 CP) wird die Prüfungsleistung durch das erfolgreiche Bearbeiten der Programmieraufgaben, sowie der erfolgreichen Beteiligung an den Kolloquien und Vorträgen erbracht. Bitte stellen Sie sicher, dass Sie, falls in Ihrem Studiengang erforderlich, bei der entsprechenden Stelle zur Prüfung angemeldet sind. Das WebReg ist dafür nicht ausreichend! Wichtig: Eine solche Anmeldung ist ggf. auch für den klausurfreien 4SWS-Modus erforderlich (z.B. für den Informatik-Bachelor im Zentralen Prüfungssekretariat)!
Vorlesungsfolien
1. Vorlesung: Probleme, Werkzeuge und GraphenSchwarz-Weiß Farbig 2. Vorlesung: Kompaktierung und Schaltungsdarstellungen
Schwarz-Weiß Farbig Kick-Off zu den praktischen Arbeiten
Schwarz-Weiß Farbig 3. Vorlesung: Timing-Analyse und Heuristiken
Schwarz-Weiß Farbig 4. Vorlesung: Längenmaße und Platzierung
Schwarz-Weiß Farbig 5. Vorlesung: Längenmaße und VPR-Platzierung
Schwarz-Weiß Farbig 6. Vorlesung: Allgemeine Platzierungstechniken, Partitionierung und Timing-Pfade
Schwarz-Weiß Farbig 7. Vorlesung: Exakte Optimierungsverfahren
Schwarz-Weiß Farbig 8. Vorlesung: Verdrahtung 1
Schwarz-Weiß Farbig 9. Vorlesung: Realer FPGA-Router
Schwarz-Weiß Farbig Beispiel 1 Beispiel 2 Beispiel 3 10. Vorlesung: Kanalverdrahtung und globale Verdrahtung (verbessert)
Schwarz-Weiß Farbig 11. Vorlesung: Verbesserungen
Schwarz-Weiß Farbig 12. Vorlesung: Floorplanning
Schwarz-Weiß Farbig
Aufgaben für praktische Programmierarbeiten
Aufgabe 1: SchaltungsanalyseAufgabe 2: Schaltungsplatzierung
Aufgabe 3: Schaltungsverdrahtung
Aufgabe 4: Verbesserungen
Materialsammlung für praktische Arbeiten
LeitfadenProgrammierrichtlinien
Korrekturfaktoren für Verdrahtungslängen
Eingabedateien für Testschaltungen
Minimaler SatzVollständiger Satz
Ausgewählte wissenschaftliche Veröffentlichungen als Hintergrundmaterial
Korrekturfaktoren für VerdrahtungslängePlatzierung 1
Platzierung 2
Inkrementelle Pfadlängenberechnung
Verdrahtung 1
Verdrahtung 2
Verdrahtung 3
Abschätzung der Verdrahtungsdichte 1
Abschätzung der Verdrahtungsdichte 2
Floorplanning