Petit déjeuner avec Charles Weatherly, auteur du livre culte Etudes for Programmers

Le petit déjeuner avec Charles Weatherly, auteur du livre culte Etudes for Programmers, a duré quatre heures. À la fin, la serveuse nous a demandé dans un restaurant de Palo Alto, en disant qu'il y avait une longue file d'attente au restaurant, et nous étions assis ici à partir de huit heures du matin. Pendant ce temps, nous avons discuté de beaucoup de choses intéressantes: le travail de Charles au Livermore Laboratory et Oracle, la programmation orientée objet et fonctionnelle, les compilateurs et les langages de description du matériel, les signets aux processeurs, l'inefficacité du réseau neuronal et le Prolog oublié sans raison, la visite de Charles en Russie, le traitement de texte avec une machine d'état dans le coprocesseur matériel et la création de jeux vidéo sur FPGA par des écoliers.



Le contenu de quatre heures avec Charles Weatherly suffit pour une cinquantaine d'articles sur Habré, je vais donc énumérer principalement des sujets, après quoi je donnerai quelques détails sur trois d'entre eux:

1. Programmation orientée objet et fonctionnelle. Affectation unique, valeurs de fonction, se débarrasser des mutations, se débarrasser du timing.
2. Structures de données et algorithmes de compilation. Muchnik SSA et le livre sur les optimisations. Bob Morgan (Compass) optimisant les compilateurs. Compilateurs vectoriels et Randy Allen (mon collègue Wave et collègue Charles sur d'autres sociétés).
3. L'évolution de l'analyseur Yacc, des internes du langage Ada (DIANA) et de l'interface VHDL dans Synopsys.
4. Grammaires attributives et sans succès, à mon avis, leur utilisation dans le manuel de formation MIPT sur la théorie de la mise en œuvre des langages de programmation (TRNP).
5. Langage de programmation JOVIAL et standardisation Ada. Langage IDL.
6. Programmation au Livermore Computing Laboratory pour physiciens et chimistes sur les CDC 7600 et Cray-1. Livermore Fortran est une extension de Fortran-77 avec des structures et une allocation dynamique de mémoire. L'utilisation de microfiches, y compris pour la recherche et la production automatiques d'animations. Harry Nelson Et comment le Rubik's Cube est entré dans le laboratoire avant d'être connu.
7. Clone soviétique Cray-1 Electronics SS BIS. Le compilateur Fortran dans IPM et le compilateur C sur lesquels nous avons travaillé au MIPT.
8. Reverse engineering d'un générateur de nombres aléatoires dans Synopsys VCS. Générateur congruentiel avec décalage de registre. LSFR.
9. L'inefficacité du réseau neuronal et le langage Prolog oublié sans raison.
10. Application des méthodes de Prolog pour l'analyse statique du texte du programme.
11. Y compris l'analyse du code du processeur écrit en Verilog ou VHDL afin d'y trouver des signets. Un signet dispersé dans différentes parties de la description du processeur au niveau du transfert de registre. Trouver du code "redondant" qui fait quelque chose en dehors de la spécification. Par exemple, une machine à états finis qui attend une phrase clé, du texte dans des registres visibles par le programmeur, après quoi le processeur passe en mode privilégié.
12. Méthodes d'analyse de code hybride - exécution dynamique avec investigation statique subséquente de l'espace d'état à partir d'un certain point d'exécution.
13. Liste des Hakmem du MIT.
14. La plupart des programmeurs dans la vie n'utilisent que cinq algorithmes - tri rapide, recherche binaire, hachage, insertion de liste et autre chose (insertion d'arbre binaire AVL?).
15. L'histoire d'Unix troff chez Bell Labs.
16. Le travail de Charles Wazerell dans Oracle sur SQL.
17. Les instructions définies par l'utilisateur constituent un bon exemple d'utilisation d'un coprocesseur matériel pour MIPS CorExtend / UDI. Ajout d'instructions au processeur pour une analyse lexicale rapide, avec une machine d'état à l'intérieur du coprocesseur et maintien de l'état entre les instructions individuelles. Contexte depuis IBM / 360 traduire le test et CDC STAR.
18. Utiliser un coprocesseur matériel pour pré-nettoyer le flux de données avant de lui appliquer des algorithmes d'apprentissage automatique.
19. Game Rogue, Scientific American aux États-Unis et en URSS.
20. École d'été de jeunes programmeurs à Novossibirsk et moustiques (selon mes souvenirs et les histoires de mes collègues Charles Weatherly)
21. Comment Charles a passé 36 heures à Moscou et deux semaines à Saint-Pétersbourg. L'Hermitage. Dans les universités de Saint-Pétersbourg, il n'a pas donné de cours.
22. Il a suggéré à Charles d'aller à une école d'été au MIET / Zelenograd en juillet ou ailleurs à l'automne (Université d'État de Moscou? MIPT? ITMO?).
23. Éducation pour les écoliers et les jeunes étudiants. La nécessité de quitter le modèle (par exemple, la programmation séquentielle) et l'apprentissage de Verilog sur le FPGA comme moyen de quitter un tel modèle.
24. L'utilisation de microcircuits avec un faible degré d'intégration avant les exercices sur le FPGA, pour qu'un écolier ou un étudiant comprenne intuitivement que le code sur Verilog est une description d'un circuit électronique, et non un programme (une chaîne d'instructions).
25. Un exemple pour RTL sur le FPGA pour l’école d’été de MIET / Zelenograd en juillet est une machine à états finis à auto-apprentissage qui calcule les tendances de l’adversaire dans le jeu des «ciseaux à papier de pierre».
26. Un autre exemple est la compétition des machines à états finis (animaux) qui déplacent un joueur vers un but sur une carte (globe). Les objets sur la carte ont une «odeur» - positive (nourriture) ou négative (électricité qui peut frapper). Conception d'une carte en FPGA, sortie et sprite d'un lecteur sur VGA à l'aide du module de génération de scan.

Ici, nous avons examiné les récents différends sur Habré concernant la POO. Charles fait campagne pour la programmation orientée objet et la programmation fonctionnelle, le cas échéant. J'ai montré à Charles un exemple que j'ai vu dans deux projets d' une conception de classe infructueuse pour représenter les nœuds d'un arbre d'analyse et des optimisations sur cet arbre , après quoi Charles a dit que bien sûr les algorithmes de transformation d'arbre ne devaient pas être dispersés en petites classes de cette manière, mais à la place, l'arbre d'analyse devait être ajouter rapidement un graphique de flux de contrôle, sur lequel utiliser des transformations pilotées par table basées sur une affectation unique statique, à quelques exceptions près. Charles m'a éclairé sur la vectorisation de Muchnik, Bob Morgan et Randy Allen:



Ensuite, j'ai dit à Charles que, après-demain, nous organiserions un séminaire à Las Vegas lors d'une conférence sur l'automatisation de la conception électronique , et j'avais besoin de ses conseils sur un bon exemple de coprocesseur basé sur le protocole CorExtend / UDI - User Defined Instructions. Ce protocole est utilisé dans les cœurs MIPS. CorExtend / UDI vous permet d'incorporer un bloc dans le processeur qui décode et exécute des instructions supplémentaires au système principal d'instructions qui peuvent être déterminées par le concepteur du système sur une puce. Le bloc peut être synthétisé et devenir une partie du microcircuit ou être configuré dans le FPGA / FPGA.

Des instructions supplémentaires se déplacent le long du pipeline du processeur avec les principales. Ils reçoivent des données de registres généraux visibles par le programmeur et peuvent renvoyer le résultat au registre. Ces instructions peuvent également enregistrer un état dans le coprocesseur. Ils peuvent être supprimés par des exceptions si une exception se produit, par exemple, dans le pipeline suivant cette instruction:



Après-demain, dans une présentation au séminaire, je vais utiliser un exemple avec une simple instruction de convolution pour un réseau de neurones. Mais l'accélération obtenue dans ce cas n'est pas impressionnante - seulement deux fois. Est-il possible de faire un meilleur exemple?

Charles a immédiatement trouvé un bien meilleur exemple: l'analyse lexicale matérielle. Une machine d'état peut être placée dans le coprocesseur, qui déterminera les nombres, les identifiants et les commentaires dans le flux de texte. Il économisera en stockant l'état entre les commandes individuelles qui transmettent le texte des registres à la machine. Le résultat de l'analyse en cours (texte balisé) sera également renvoyé au registre.

Charles m'a également raconté l'histoire des instructions pour analyser le texte depuis IBM / 360 traduire test et CDC STAR. Il m'a également dit qu'un tel coprocesseur peut être utilisé pour l'apprentissage automatique, pour le pré-nettoyage du flux de données avant de lui appliquer des algorithmes d'apprentissage automatique.



Ensuite, j'ai expliqué à Charles Saga comment un groupe d'ingénieurs et d'enseignants a traduit et mis en œuvre dans diverses universités russes le manuel de David Harris et Sarah Harris "Circuit numérique et architecture d'un ordinateur" (voir les articles sur Habr. 1 , 2 , 3). Maintenant, avec les efforts combinés de MIET, RUSNANO, des professeurs de MEPhI et d'autres universités, nous prévoyons une école d'été au MIET où des écoliers avancés projettent des jeux vidéo sur le FPGA avec sortie sur un écran graphique (section Entre physique et programmation ). Pour cela, les idées du livre Designing Video Game Hardware in Verilog de Steven Hugg, 15 décembre 2018 sont utilisées:



Les jeux peuvent être développés à la fois sous la forme de machines à états finis purement matériels, ou en combinaison de graphiques matériels sur FPGA avec des programmes sur un processeur simple core schoolMIPS, qui est décrit dans les articles de Stanislav Zhelnio sur Habr et le wiki sur schoolMIPS sur GitHub . Sur les FPGA, vous pouvez tout simplement générer un scan pour VGA , afficher une carte à partir de la mémoire et déplacer des sprites avec des chiffres:



Charles a suggéré, en plus des jeux avec des tanks et des courses, de faire une compétition d'automates finis (animaux) qui amènent le joueur au but sur la carte (globe). Les objets sur la carte ont une «odeur» - positive (nourriture) ou négative (électricité qui peut frapper). Les élèves peuvent écrire sur des machines finies sur un veril qui voient l'environnement, les incorporer dans du code qui dessine des graphiques et prend en charge la carte, puis rivaliser avec les mieux lotis:



Pour générer des éléments de comportement pseudo-aléatoire, vous pouvez utiliser des blocs matériels LFSR:



Finalement, Charles a laissé deux autographes - pour les lecteurs russes (j'ai emprunté un livre russe à Sergey Vakulenko ) et les lecteurs de notre société Wave Computing, à la bibliothèque interne de laquelle j'ai emprunté un livre original en anglais: