Seit den 1990er Jahren hat es mich überrascht, dass das Design der gesamten globalen digitalen Mikroelektronik von zwei Büros in Kalifornien gesteuert wird, die 10 Minuten voneinander entfernt sind - Synopsys und Cadence. Zu dieser Zeit wurde ein Viertel der Welt des Designs in Japan hergestellt (das chinesische Festland befand sich damals in einem primitiven Zustand), und all diese Sony, Hitachi, Fujitsu und andere Giganten verneigten sich vor Amerika und zahlten unzählige Millionen Dollar für die Programme, die japanische Designer damals verwendeten. Jetzt geht es weiter mit Samsung, Huawei und sogar mit russischen Büros, die Mikrochips für den Weltraum entwerfen.
Das russische Land hat es geschafft, Yandex gegenüber Google zu vergrößern. Warum also nicht versuchen, einige Programme zum Entwerfen von Mikrochips zu erstellen? Sie können klein anfangen: um Wettbewerbe und Hackathons für die Entwicklung von Designautomatisierungsalgorithmen (Electronic Design Automation - EDA) bekannt zu machen. Diese Algorithmen sind insofern praktisch, als sie viele Schwierigkeitsgrade haben: Ein Schüler kann über das Wochenende das einfachste Place & Route-Programm schreiben, aber ein fortgeschrittenes Programm erfordert jahrzehntelange Arbeit für Hunderte von Menschen und Milliarden von Dollar in Forschung und Entwicklung.
Jetzt veranstalten sie in Innopolis bei Kasan eine
Veranstaltung für Studenten im Format "zwei Wochen Training + Hackathon". Eines der Themen war die traditionelle EDA-Aufgabe - Platzieren und Verfolgen eines Diagramms einer elektronischen Schaltung in Reihen von Standardzellen. Es wird interessant sein zu sehen, was ein kleines Team von Programmierern mit einem grundlegenden Verständnis von C ++ / Java / Python, Methoden zum Parsen von Text, Diagrammalgorithmen und Fähigkeiten zur Visualisierung von Datenstrukturen mithilfe der GUI in kurzer Zeit implementieren kann.
Also - die Erklärung des Problems:
Die Aufgabe besteht aus drei Unteraufgaben, mit denen sich verschiedene Schüler befassen können:
- Analysieren der Textdarstellung eines digitalen Schaltungsgraphen.
- Platzieren eines Diagramms in den Reihen der Standardzellen der Mikroschaltung und Verbinden dieser Zellen mit Spuren (Verfolgung).
- Visualisierung der Ergebnisse - Anzeige der Schaltungsspuren und Verbindungen auf dem Bildschirm.
Die Eingabe in das Programm ist eine Textdatei in einer sehr begrenzten Teilmenge der Verilog-Hardwarebeschreibungssprache. Diese Datei beschreibt die Ein- und Ausgänge für die Schaltung (Eingang, Ausgang), die internen Verbindungen (Kabel) und enthält eine Liste der logischen Elemente im Format "Typ Instanzname (Liste der Verbindungen)". Die Datei kann in C / C ++ mit Lex + Yacc oder ähnlichen Programmen analysiert werden.
Das Ergebnis des Parsens des Textes sollte eine grafische Darstellung der Elemente im Speicher sein. Diese Ansicht wird vom Platzierungs- und Verfolgungsalgorithmus verwendet, der dann von einer anderen Struktur erstellt wird. Wenn genügend Teilnehmer im Hackathon-Team sind, kann das Ergebnis der ersten Analyse während des Hackathons als zusätzliche Aufgabe visualisiert werden. Ungefähr in diesem Sinne, wenn auch nicht so schön:
Wenn während des Hackathons nicht genügend Teilnehmer anwesend sind, sollte die Visualisierung des nicht platzierten Zwischengraphen für später belassen werden, und während des Hackathons sollte nur die endgültige Platzierung auf dem Bildschirm angezeigt werden.
Im Allgemeinen kann die Aufgabe des Parsens mit mehreren Komplexitätsebenen gestellt werden:
- In den einfachsten Fällen sind alle Knoten des Diagramms logische Elemente mit zwei Eingaben UND und ODER sowie NICHT-Elemente mit einer Eingabe. Bei der endgültigen Platzierung werden sie von Standardzellen gleicher Breite realisiert.
- Wenn genügend Zeit für den Hackathon vorhanden ist, kann die Aufgabe kompliziert sein:
- Einführung von Zellen mit drei und vier Eingängen AND3, OR4 usw.;
- Erweitern Sie den Satz von Knotentypen, indem Sie NAND, XOR, D-Flip-Flops (D-Flip-Flop) mit verschiedenen Optionen (Zurücksetzen, Aktivieren) usw. hinzufügen.
- Erstellen Sie eine zusätzliche Textdatei, in der Sie die Breite und andere Parameter der Zellen festlegen können.
- Nach dem Hackathon kann die Aufgabe an die reale Welt gebunden werden, und es werden nicht die abstrakten UND- und ODER-Analysen analysiert, sondern die Datei im gleichen Format, sondern Zellen aus realen Bibliotheken von Standard-ASIC-Zellen mit 28, 14 oder 7 Nanometern, die EDA-Entwicklern und Fabrikdesignern zur Verfügung gestellt werden Typ TSMC (Taiwan Semiconductor Manufacturing Company).
Was ist eine Standardzelle? Dies ist eine Standardhöhenzelle für eine bestimmte ASIC-Bibliothek, dh eine primitive Bibliothek zur Herstellung einer Mikroschaltung in einer Fabrik unter Verwendung einer Technologie. ASIC - Anwendungsspezifische integrierte Schaltung. Heute sind die meisten Chips, beispielsweise in Smartphones, ASICs. Die Zellen in der ASIC-Bibliothek haben eine Standardhöhe, so dass sie bequem in Reihen angeordnet werden können, um sie mit Strom zu versorgen und Trace-Algorithmen zu vereinfachen. Verschiedene Zellen in der Bibliothek können nicht nur Grundelemente wie UND und ODER implementieren, sondern auch komplexere Konstruktionen - Multiplexer, Latches, Kombinationen von zwei oder drei Logikelementen (UND-ODER) usw.
Zellen auf dem Mikrokreislauf reihen sich in Reihen aneinander (Folie aus
Charles Dancheks Vorlesungen ):
Zwischen den Zeilen befinden sich Kanäle (Routing-Kanäle), in denen Verbindungen verlaufen. Die Breite der Kanäle kann geändert werden, wenn sich in den Verbindungen eine Überlastung bildet. In den Zeilen können Sie Lücken zwischen den Zellen schließen:
Für einen Hackathon kann die Aufgabe auf das Niveau eines kugelförmigen Pferdes im Vakuum vereinfacht werden:
- Zelltypen begrenzen. Für den Anfang können Sie im Allgemeinen nur ein Diagramm des NAND mit zwei Eingängen platzieren.
- Betrachten Sie alle Zellen als gleich breit.
- Ignorieren Sie alle Aspekte der physischen Natur der Zellen, einschließlich der Signalverzögerung und des Stromverbrauchs.
Hier bedeutet „ignorieren“, dass Sie in der Trainingsübung die Zellphysik bei der Beurteilung der Qualität der Platzierung und Verfolgung nicht berücksichtigen können. Zunächst reicht es aus, nur die Geometrie zu berücksichtigen, um beispielsweise die Gesamtlänge der Fugen und die Anzahl der Schichten, auf denen die Fugen hergestellt werden, zu minimieren. Die Notwendigkeit einer neuen Schicht entsteht, wenn es unmöglich ist, zwei Leiter zu platzieren, ohne sie zu kreuzen.
Beim Hackathon reicht es aus, Standardzellen als „Black Boxes“ zu betrachten und wie in den obigen Abbildungen auf dem Bildschirm anzuzeigen. Oder mit Bildern logischer Elemente, wie auf einer Folie aus
Igor Markovs Vorlesungen :
Wenn Sie jedoch mit den Innenseiten der Zellen anzeigen, sind die Bilder dekorativer. Eine Folie aus den
Vorträgen von Charles Danchek :
Ein weiteres Bild aus dem Internet mit der Platzierung und Verfolgung + Bild der Innenseiten der Zellen:
Aber wie kann man Zellen in Zeilen platzieren, Kanäle zwischen Zeilen erweitern und verengen, Verbindungen herstellen, neue Ebenen einführen, die Optimalität der Ergebnisse bewerten und Optionen sortieren? Nun, dies sind rein algorithmische und Programmieraufgaben. In Innopolis lehren sie dies wahrscheinlich, daher werde ich meine Gedanken oder Gedanken nicht auf dem Baum verbreiten. Als erste Inspiration für die Rückverfolgung können Sie die alte Methode der Wellenverfolgung verwenden, die
im dritten Teil des Kurses für Schüler von RUSNANO beschrieben wird . Diese Methode ist zwar nicht für in Zellen angeordnete Standardzellen, sondern für einen weniger geordneten Fall mit einer kleinen Anzahl von Komponenten:
2.10. Wie es geht: Wave-Tracing-Algorithmus.
Einer der klassischen Algorithmen, die von frühen Trace-Programmen verwendet wurden, war das Wave-Tracing, das 1961 in einem Artikel von Chester Lee, einem Forscher bei Bell Labs, beschrieben wurde. Im Englischen wird der Lee-Algorithmus als "Labyrinth-Routing" bezeichnet, was wörtlich übersetzt "Labyrinth-Verfolgung" bedeutet. Dieser Name beruht auf der Tatsache, dass zusätzlich zu Programmen zum Entwerfen von Elektronik der Lee-Algorithmus in Spielprogrammen verwendet wurde, um den kürzesten Weg im Labyrinth zu finden.
Der Lee-Algorithmus repräsentiert die Blöcke, die verbunden werden müssen, in Form von Figuren auf einer begrenzten Ebene, die mit "in the box" markiert sind. Um den kürzesten Weg von der Ausgabe eines Blocks zur Ausgabe eines anderen Blocks zu finden, verwendet der Lee-Algorithmus zwei Durchgänge:
- Der erste Durchgang wird Wellenausbreitung genannt. Wir markieren alle „Zellen“ oder eine Zelle am ersten Ausgang mit einer Einheit. Danach markieren wir für jede mit der Nummer N gekennzeichnete Zelle alle benachbarten freien, nicht markierten Zellen mit der Nummer N + 1. Wiederholen Sie das Markup, bis wir entweder den Abschluss des zweiten Blocks erreichen oder keine Möglichkeit mehr besteht, die „Welle“ zu verbreiten.
- Der zweite Durchgang wird als "Wiederherstellung des Pfades" bezeichnet. Wenn die Zelle im zweiten Block markiert ist, wählen wir unter ihren Nachbarn eine Zelle aus, die mit 1 weniger als die Nummer in der aktuellen Zelle markiert ist. Fügen Sie dem Pfad eine benachbarte Zelle hinzu, gehen Sie hinein und beginnen Sie, die Nachbarn zu betrachten, die mit 1 weniger markiert sind. Wir wiederholen dies, bis wir zum Abschluss des ersten Blocks kommen.
Zuerst wurde der Lee-Algorithmus in Programmen zum Entwerfen von Leiterplatten verwendet, dann wurde er zum Entwerfen von Mikroschaltungen verwendet. Als jedoch die Größe der Mikroschaltungen zunahm, war es unmöglich, den Lee-Algorithmus in seiner ursprünglichen Form anzuwenden, da er viel Speicher zum Speichern des Datenarrays sowie viel Zeit für zahlreiche Durchgänge durch dieses Array benötigt. Trotz der Tatsache, dass moderne automatische Verfolgungsprogramme andere Algorithmen verwenden, bleibt der Lee-Algorithmus eine hervorragende Übung für diejenigen, die kürzlich die Programmierung beherrschen und selbst ein kleines Verfolgungsprogramm schreiben möchten.
Für ernstere Algorithmen können Sie
in den Materialien von Igor Markov nach Ideen suchen. Aber das Beste wäre, kreativ zu sein - was ist, wenn Sie sich etwas einfallen lassen, das Tausende von mathematisch versierten algorithmischen Programmierern nicht jeden Morgen auf den Autobahnen 101, 880 und 237 in den Büros von Synopsys und Cadence auf Staus stoßen in den Städten San Jose, Sunnyvale und Mountain View, Kalifornien.
Referenzen (von einfach bis komplex):
- Einführungsvorträge zu den Grundlagen des digitalen Designs in Innopolis: 1 , 2 .
- Einführungskurs in digitale Elektronik und EDA für fortgeschrittene Schüler des Typs Olympiade. Von RUSNANO: 1 , 2 , 3 .
- Lehrbuch Harris & Harris .
- Folien von Vorträgen von Charles Danchek .
- Kurs von Igor Markov von der University of Michigan . Er las diesen Kurs an der Moskauer Staatsuniversität.
Ich
drücke meine Hoffnung aus, dass die
Initiative von Innopolis in algorithmischen Wettbewerben erweitert wird. Der EDA-Bereich ist mathematisch interessant und gut bezahlt. Synopsys eröffnete eine Niederlassung in Armenien und wurde dort zu einem der führenden Arbeitgeber:
„Heute ist Synopsys mit mehr als 650 Mitarbeitern (darunter mehr als 600 Ingenieuren) einer der größten IT-Arbeitgeber in Armenien.“ Ich stelle fest, dass Russland größer als Armenien ist und wahrscheinlich eine eigene Synopsie erstellen kann. Letztendlich gibt es in Russland viele Programmierer, auch Mathematiker, und die derzeitige Marktkapitalisierung von Synopsys + Cadence entspricht in etwa den Kosten der Olympischen Spiele in Sotschi.