Das Frühstück mit Charles Weatherly, Autor des Kultbuchs Etudes for Programmers, dauerte vier Stunden. Am Ende fragte uns die Kellnerin aus einem Restaurant in Palo Alto, dass es im Restaurant eine lange Schlange gebe und wir ab acht Uhr morgens hier saßen. Während dieser Zeit diskutierten wir viele interessante Dinge: Charles 'Arbeit im Livermore Laboratory und Oracle, objektorientierte und funktionale Programmierung, Compiler und Hardwarebeschreibungssprachen, Lesezeichen für Prozessoren, Ineffizienz neuronaler Netze und der unverdient vergessene Prolog, Charles' Besuch in Russland, Textverarbeitung mit einer Zustandsmaschine im Hardware-Coprozessor und der Erstellung von Videospielen auf FPGAs durch Schulkinder.
Der Inhalt von vier Stunden mit Charles Weatherly reicht für fünfzig Artikel über Habré, daher werde ich hauptsächlich Themen auflisten, woraufhin ich einige Details zu drei davon geben werde:
- Objektorientierte und funktionale Programmierung. Einzelne Zuordnung, Funktionswerte, Mutationen loswerden, Timing loswerden.
- Datenstrukturen und Compiler-Algorithmen. Muchnik SSA und das Buch über Optimierungen. Bob Morgan (Compass) erstellt optimierende Compiler. Vectoring-Compiler und Randy Allen (mein Wave-Kollege und Charles-Kollege über andere Unternehmen).
- Die Entwicklung des Yacc-Parsers, der Ada-Interna (DIANA) und des VHDL-Frontends in Synopsys.
- Attributive Grammatiken und meiner Meinung nach erfolglose Verwendung im MIPT-Schulungshandbuch zur Theorie der Implementierung von Programmiersprachen (TRNP).
- JOVIAL Programmiersprache und Ada Standardisierung. IDL-Sprache.
- Programmierung im Livermore Computing Laboratory für Physiker und Chemiker auf CDC 7600 und Cray-1. Livermore Fortran ist eine Erweiterung von Fortran-77 mit Strukturen und dynamischer Speicherzuordnung. Verwendung von Mikrofiches, auch zur automatischen Suche und Produktion von Animationen. Harry Nelson Und wie der Zauberwürfel ins Labor kam, bevor er bekannt wurde.
- Sowjetischer Klon Cray-1 Electronics SS BIS. Der Fortran-Compiler in IPM und der C-Compiler, an dem wir bei MIPT gearbeitet haben.
- Reverse Engineering eines Zufallszahlengenerators in Synopsys VCS. Kongruentgenerator mit Registerverschiebung. LSFR.
- Ineffizienz des neuronalen Netzes und die unverdient vergessene Prolog-Sprache.
- Anwendung von Methoden aus Prolog zur statischen Analyse von Programmtexten.
- Einschließlich der Analyse des in Verilog oder VHDL geschriebenen Prozessorcodes, um darin Lesezeichen zu finden. Ein Lesezeichen, das in verschiedenen Teilen der Prozessorbeschreibung auf Registerübertragungsebene verstreut ist. Suchen nach "redundantem" Code, der etwas außerhalb der Spezifikation tut. Zum Beispiel eine Finite-State-Maschine, die auf eine Schlüsselphrase wartet, Text in Registern, die für den Programmierer sichtbar sind, wonach der Prozessor in den privilegierten Modus wechselt.
- Hybride Code-Analysemethoden - dynamische Ausführung mit anschließender statischer Untersuchung des Zustandsraums ab einem bestimmten Ausführungspunkt.
- Liste von Hakmem vom MIT.
- Die meisten Programmierer im Leben verwenden nur fünf Algorithmen - schnelle Sortierung, binäre Suche, Hashing, Einfügen von Listen und etwas anderes (Einfügen von AVL-Binärbäumen?).
- Die Geschichte von Unix Troff bei Bell Labs.
- Charles Wazerells Arbeit in Oracle on SQL.
- Ein gutes Beispiel für die Verwendung eines Hardware-Coprozessors für MIPS CorExtend / UDI sind benutzerdefinierte Anweisungen. Hinzufügen von Anweisungen zum Prozessor für eine schnelle lexikalische Analyse mit einer Zustandsmaschine im Coprozessor und Beibehalten des Zustands zwischen einzelnen Anweisungen. Hintergrund seit IBM / 360-Übersetzungstest und CDC STAR.
- Verwenden eines Hardware-Coprozessors zum Vorbereinigen des Datenstroms, bevor Algorithmen für maschinelles Lernen angewendet werden.
- Game Rogue, wissenschaftlicher Amerikaner in den Staaten und der UdSSR.
- Sommerschule junger Programmierer in Nowosibirsk und Mücken darin (nach meinen Erinnerungen und Geschichten von Kollegen Charles Weatherly)
- Wie Charles 36 Stunden in Moskau und zwei Wochen in St. Petersburg verbrachte. Die Eremitage. An den Universitäten von St. Petersburg hielt er keine Vorlesungen.
- Er schlug Charles vor, im Juli oder im Herbst an eine andere Sommerschule in MIET / Zelenograd zu gehen (Moskauer Staatsuniversität? MIPT? ITMO?).
- Bildung für Schüler und jüngere Schüler. Die Notwendigkeit, die Vorlage zu beenden (z. B. sequentielle Programmierung) und Verilog auf dem FPGA zu lernen, ist eine Möglichkeit, eine solche Vorlage zu beenden.
- Die Verwendung von Mikroschaltungen mit einem geringen Integrationsgrad vor Übungen auf dem FPGA, damit ein Schulkind oder Schüler intuitiv versteht, dass der Code auf Verilog eine Beschreibung einer elektronischen Schaltung und kein Programm (eine Anweisungskette) ist.
- Ein Beispiel für RTL auf dem FPGA für die Sommerschule in MIET / Zelenograd im Juli ist eine selbstlernende Finite-State-Maschine, die die Trends des Gegners im Spiel „Steinpapierschere“ berechnet.
- Ein weiteres Beispiel ist die Konkurrenz endlicher Zustandsmaschinen (Tiere), die einen Spieler zu einem Ziel auf einer Karte (Globus) bewegen. Objekte auf der Karte haben einen „Geruch“ - positiv (Lebensmittel) oder negativ (Strom, der zuschlagen kann). Entwerfen einer Karte in FPGA, Ausgabe und Sprite eines Players auf VGA mithilfe des Scan-Generierungsmoduls.
Hier haben wir die jüngsten Streitigkeiten über HOPé über OOP untersucht. Charles setzt sich gegebenenfalls für OOP und funktionale Programmierung ein. Ich habe Charles
ein Beispiel gezeigt, das ich in zwei Projekten mit
erfolglosem Klassendesign zur Darstellung von Knoten eines Analysebaums und Optimierungen in diesem Baum gesehen habe . Danach sagte Charles, dass Baumtransformationsalgorithmen natürlich nicht auf diese Weise in kleine Klassen verstreut werden sollten, sondern der Analysebaum Mit wenigen Ausnahmen können Sie schnell ein Kontrollflussdiagramm einfügen, in dem tabellengesteuerte Transformationen basierend auf statischer Einzelzuweisung verwendet werden können. Charles hat mich über die Vektorisierung von Muchnik, Bob Morgan und Randy Allen aufgeklärt:
Dann sagte ich Charles, dass wir übermorgen ein
Seminar in Las Vegas auf einer Konferenz zur Automatisierung des Elektronikdesigns abhalten würden, und ich brauchte seinen Rat zu einem guten Beispiel eines Co-Prozessors, der auf dem CorExtend / UDI-Protokoll basiert - Benutzerdefinierte Anweisungen. Dieses Protokoll wird in MIPS-Kernen verwendet. Mit CorExtend / UDI können Sie einen Block in den Prozessor einbetten, der zusätzliche Anweisungen zum Hauptsystem von Anweisungen decodiert und ausführt, die vom Systemdesigner auf einem Chip bestimmt werden können. Der Block kann synthetisiert werden und Teil der Mikroschaltung werden oder im FPGA / FPGA konfiguriert werden.
Zusätzliche Anweisungen werden zusammen mit den Hauptanweisungen entlang der Prozessor-Pipeline verschoben. Sie empfangen Daten aus allgemeinen Registern, die für den Programmierer sichtbar sind, und können das Ergebnis an das Register zurückgeben. Diese Anweisungen können auch einen bestimmten Status im Coprozessor speichern. Sie können durch Ausnahmen gelöscht werden, wenn eine Ausnahme auftritt, z. B. in der Pipeline, die dieser Anweisung folgt:
Übermorgen werde ich in einer
Präsentation auf dem Seminar ein Beispiel mit einer einfachen Faltungsanweisung für ein neuronales Netzwerk verwenden. Die in diesem Fall erreichte Beschleunigung ist jedoch nicht beeindruckend - nur zweimal. Ist es möglich, ein besseres Beispiel zu geben?
Charles fand sofort ein viel besseres Beispiel: die lexikalische Hardware-Analyse. Im Coprozessor kann eine Zustandsmaschine platziert werden, die die Nummern, Bezeichner und Kommentare im Textstrom ermittelt. Es wird gespeichert, indem der Status zwischen einzelnen Befehlen gespeichert wird, die Text von Registern an die Maschine übertragen. Das Ergebnis der aktuellen Analyse (markierter Text) wird ebenfalls in das Register zurückgegeben.
Charles erzählte mir auch die Geschichte der Anweisungen zum Parsen von Text seit IBM / 360-Übersetzungstest und CDC STAR. Er sagte mir auch, dass ein solcher Coprozessor zum maschinellen Lernen verwendet werden kann, um den Datenstrom vorab zu bereinigen, bevor Algorithmen für maschinelles Lernen angewendet werden.
Dann erzählte ich Charles Saga, wie eine Gruppe von Ingenieuren und Lehrern an verschiedenen russischen Universitäten das
Lehrbuch von David Harris und Sarah Harris „Digitale Schaltkreise und Architektur eines Computers“ übersetzt und implementiert hat (siehe Beiträge zu Habr.
1 ,
2 ,
3). Mit den gemeinsamen Anstrengungen von MIET, RUSNANO, Lehrern von MEPhI und anderen Universitäten planen wir jetzt eine Sommerschule am MIET, in der fortgeschrittene Schüler Videospiele auf dem FPGA mit Ausgabe auf einem grafischen Bildschirm projizieren (Abschnitt
Zwischen Physik und Programmierung ). Hierzu werden Ideen aus dem Buch Designing Video Game Hardware in Verilog von Steven Hugg vom 15. Dezember 2018 verwendet:
Spiele können sowohl in Form von Hardware-Finite-State-Maschinen als auch in Kombination von Hardwaregrafiken auf FPGAs mit Programmen auf dem einfachen Prozessorkern schoolMIPS entwickelt werden, die in den
Beiträgen von Stanislav Zhelnio auf Habr und im
Wiki auf schoolMIPS auf GitHub beschrieben werden . Auf FPGAs können Sie ganz einfach
einen Scan für VGA erstellen, eine Karte aus dem Speicher anzeigen und Sprites mit Zahlen verschieben:
Charles schlug vor, zusätzlich zu Spielen mit Panzern und Rennen einen Wettbewerb aus endlichen Automaten (Tieren) zu veranstalten, die den Spieler zum Ziel auf der Karte (Globus) bewegen. Objekte auf der Karte haben einen „Geruch“ - positiv (Lebensmittel) oder negativ (Strom, der zuschlagen kann). Die Schüler können endliche Maschinen auf Veril schreiben, die die Umgebung sehen, sie in Code einbetten, der Grafiken zeichnet und die Karte unterstützt, und dann mit denjenigen konkurrieren, denen es besser geht:
Um Elemente mit pseudozufälligem Verhalten zu generieren, können Sie LFSR-Hardwareblöcke verwenden:
Am Ende hinterließ Charles zwei Autogramme - für russische Leser (ich habe ein russisches Buch von
Sergey Vakulenko ausgeliehen ) und Leser unserer Firma Wave Computing, aus deren interner Bibliothek ich ein Originalbuch in englischer Sprache ausgeliehen habe:
