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