Отчет с завтрака с Чарльзом Уэзереллом, автором культовой книги «Этюды для программистов». ООП, ПЛИС, компиляторы, Россия, Оракл.

Завтрак с Чарльзом Уэзереллом, автором культовой книги «Этюды для программистов», затянулся на четыре часа. В конце-концов официантка попросила нас из ресторана в Пало-Альто, сказав что в ресторан большая очередь, а мы тут с восьми утра заседаем. За это время мы обсудили массу интересных вещий: работу Чарльза в Ливерморской лаборатории и Оракле, объектно-ориентированное и функциональное программирование, компиляторы и языки описания аппаратуры, закладки в процессоры, неэффективность нейронных сетей и незаслуженно забытый Пролог, посещение Чарльзом России, обработка текста конечным автоматом в аппаратном сопроцессоре и создание школьниками видеоигр на ПЛИС.

Содержания четырех часов с Чарльзом Уэзереллом хватит для пятидесяти статей на Хабре, поэтому перечислю в основном темы, после чего приведу некоторые детали про три из них:

  1. Объектно-ориентированное и функциональное программирование. Single assignment, function values, get rid of mutations, get rid of timing.
  2. Структуры данных и алгоритмы компиляторов. Muchnik SSA и книга по оптимизациям. Bob Morgan (Compass) building optimizing compilers. Векторизирующие компиляторы и Randy Allen (мой коллега по Wave и коллега Чарльза про другим компаниям).
  3. Эволюция парсера Yacc, внутренних представлений языка Ada (DIANA) и фронтенда VHDL в Synopsys.
  4. Атрибутивные грамматики и неудачное, на мой взгляд, использование их в методичке МФТИ по Теории Реализации Языков Программирования (ТРЯП).
  5. Язык программирования JOVIAL и стандартизация Ады. Язык IDL.
  6. Программирование в ливерморской лаборатории вычислений для физиков и химиков на CDC 7600 и Cray-1. Ливерморский Фортран — расширение Fortran-77 со структурами и днамическим выделением памяти. Использование микрофишей в том числе для автоматического поиска и изготовления анимаций. Harry Nelson. И как в лабораторию попал кубик Рубика до того, как он стал известен.
  7. Советский клон Cray-1 Электроника СС БИС. Компилятор Фортрана в ИПМ и компилятор Си, над которым мы работали в МФТИ.
  8. Реверс-инжиниринг генератора случайных чисел в Synopsys VCS. Congruential generator with register shift. LSFR.
  9. Неэффективность нейросетей и незаслуженно забытый язык Prolog.
  10. Применение методов из Пролога для статического анализа текста программ.
  11. В том числе анализ кода процессора, написанного на Verilog или VHDL с целью отыскания в нем закладок. Закладка, разбросанная по разным частям описания процессора на уровне регистровых передач. Нахождение «лишнего» кода, который делает что-то вне спецификации. Например конечный автомат, который ждет ключевой фразы, текст в видимых программисту регистрах, после чего переводит процессор в привилегированный режим.
  12. Гибридные методы анализа кода — динамическое выполнение с последующим статическим исследованием пространства состояний из некоей точки выполнения.
  13. Список Hakmem из MIT.
  14. Большинство программистов в жизни используют только пять алгоритмов — quick sort, binary search, hashing, list insertion, и еще чего-то (AVL binary tree insertion?).
  15. История Unix troff в Bell Labs.
  16. Работа Чарльза Уэзерелла в Оракле над SQL.
  17. Хороший пример использования аппаратного сопроцессора для MIPS CorExtend / UDI — User Defined Instructions. Добавление в процессор команд для быстрого лексического анализа, с конечным автоматом внутри сопроцессора и сохранением состояния между индивидуальными командами. История вопроса со времен IBM/360 translate test и CDC STAR.
  18. Использование аппаратного сопроцессора для предварительной очистки потока данных перед применением к нему алгоритмов машинного обучения.
  19. Игра Rogue, Scientific American в штатах и СССР.
  20. Летняя Школа Юных Программистов в Новосибирске и комары в ней (по моим воспоминаниям и рассказов коллег Чарльза Уэзерелла)
  21. Как Чарльз провел 36 часов в Москве и две недели в Питере. Эрмитаж. В питерских вузах он лекции не читал.
  22. Предложил Чарльзу съездить на летнюю школу в МИЭТ / Зеленоград в июле или еще куда-нибудь осенью (МГУ? МФТИ? ИТМО?).
  23. Обучение школьников и младших студентов. Необходимость выйти из шаблона (например последовательного программирования) и изучение Verilog на ПЛИС как один из способов выхода из такого шаблона.
  24. Использование микросхем малой степени интеграции перед упражнениями на ПЛИС, чтобы школьник или студент интуитивно понял, что код на Verilog — это описание электронной схемы, а не программы (цепочки инструкций).
  25. Пример для RTL на FPGA для летней школе в МИЭТ / Зеленоград в июле — самообучающийся конечный автомат, которые вычисляет тенденции оппонента в игре «камень ножницы бумага».
  26. Другой пример — соревнование конечных автоматов (зверьков), которые перемещают игрока к цели по карте (глобусу). Объекты на карте имеют «запах» — положительный (еда) или отрицательный (электричество которое может ударить). Конструирование карты в ПЛИС, вывод и спрайта игрока на VGA с помощью модуля генерации развертки.

Вот мы разбирали недавние споры на Хабре про ООП. Чарльз агитирует и за ООП, и за функциональное программирование, где оно применимо. Я показал Чарльзу увиденный мною в двух проектах пример неудачного дизайна классов для представления узлов дерева синтаксического разбора и оптимизаций на этом дереве, после чего Чарльз сказал, что конечно же алгоритмы транформации дерева разбрасывать по мелким классам таком образом не стоит, а вместо этого дерево разбора нужно быстро перекинуть в control flow graph, на котором использовать table driven transformations на основе static single assignment, с небольшим количеством исключений. Чарльз просветил меня про работы Мучника, Боба Моргана и Рэнди Аллена по векторизации:

Потом я рассказал Чарльзу, что послезавтра послезавтра мы в компании будем проводить семинар в Лас-Вегасе на конференции автоматизации проектирования электроники, и мне нужен его совет по хорошему примеру сопроцессора на основе протокола CorExtend / UDI — User Defined Instructions. Это протокол используется в ядрах MIPS. CorExtend/UDI позволяет встроить в процессор блок, который декодирует и выполняет дополнительные к основной системе команд инструкции, которые может определить разработчик системы на кристалле. Блок может быть синтезирован и стать частью микросхемы или быть сконфигурирован в ПЛИС/FPGA.

Дополнительные инструкции двигаются по конвейеру процессора вместе с основными. Они получают данные из видимых программистом регистров общего назначения и могут вернуть результат в регистр. Эти инструкции также могут сохранять в сопроцессоре некое состояние. Их можно убить исключениями, если исключение произойдет например в следующей за данной инструкцией в конвейере:

Послезавтра в презентации на семинаре я собираюсь использовать пример с инструкцией простой конволюции для нейросети. Но достигаемое при этом ускорение не впечатляет — всего в два раза. Нельзя ли сделать пример получше?

Чарльз тут же придумал гораздо более удачный пример: аппаратный лексический анализ. В сопроцессор можно поместить конечный автомат, который будет определять числа, идентификаторы и комментарии в потоке текста. Он будет сохранять сохранением состояния между индивидуальными командами, которые передают текст из регистров в автомат. Результат текущего анализа (размеченный текст) будет возвращаться тоже в регистр.

Чарльз также рассказал мне историю вопроса инструкций для парсирования текста со времен IBM/360 translate test и CDC STAR. Еще он сказал мне, что такой сопроцессор можно использовать для машинного обучения, для предварительной очистки потока данных перед применением к нему алгоритмов машинного обучения.

Потом я рассказал Чарльзу сагу, как группа инженеров и преподавателей перевела и внедрила в различных российских вузах учебник Дэвида Харриса и Сары Харрис «Цифровая схемотехника и архитектура компьютера» (см. посты на Хабре 1, 2, 3). Сейчас объединенными усилиями МИЭТ, РОСНАНО, преподавателей МИФИ и других вузов мы планируем летнюю школу в МИЭТ на которой продвинутые школьники проектируют на ПЛИС видеоигры с выводом на графический экран (секция Между физикой и программированием). Для того используются идеи из книжки Designing Video Game Hardware in Verilog by Steven Hugg, December 15, 2018:

Игры можно разрабатывать как в виде чисто аппаратных конечных автоматов, так и в комбинации аппаратной графики на ПЛИС с программами на простом процессорном ядре schoolMIPS, которое описано в см. постах Станислава Жельнио на Хабре и wiki по schoolMIPS на GitHub. На ПЛИС можно довольно просто сделать генерацию развертки для VGA, выводить на экран карту из памяти и движущиеся спрайты c фигурками:

Чарльз предложил помимо игр с танчиками и гонками сделать соревнование конечных автоматов (зверьков), которые перемещают игрока к цели по карте (глобусу). Объекты на карте имеют «запах» — положительный (еда) или отрицательный (электричество которое может ударить). Школьники могут писать на верилоге конечные автоматы, которые видят окружение, встраивать их в код, который делает вывод графики и поддерживает карту, после чего соревноваться, у кого такой код лучше:

Для генерации элементов псевдослучайного поведения можно использовать аппаратные блоки LFSR:

Под конец Чарльз оставил два автографа — для русских читателей (русскую книгу я одолжил у Сергея Вакуленко) и читателей в нашей компании Wave Computing, из внутренней библиотеки которой я одолжил исходную книгу на английском: