Как пересечь пропасть от физики к программированию и насолить Алексу Экслеру

[panchul]

Господа! Во время наших похождений с Аммосовым и его Рыжей Студенткой по Калифорнии (ссылки ссылка 1, ссылка 2, ссылка 3) мы неоднократно обсуждали, чему сейчас учат на физтехе. К сожалению, оправдались мои самые страшные подозрения - на физтехе до сих пор учат физике.

Показания Юрия Аммосова и Рыжей Студентки независимо подтвердил Сергей Вакуленко ramlamyammambam, продемонстрировав мне современное расписание физтеховского факультета компьютерщиков, то бишь ФУПМ, по ссылке из фейсбука. Это расписание почти не отличается от того, что, насколько я помню, было 20 лет назад:




При виде этого расписания у меня в глазах помутнело, но меня спас от расстройства чувств все тот же Вакуленко, поделившись, что наш общий знакомый Александр Тормасов http://tormasov.com (Chief Scientist в Parallels) читает на физтехе крутые курсы программирования, и следовательно там не сплошная физика.


Нет, я совершенно не против того, чтобы 2% студентов МФТИ учили только физику, математическую физику и объем математики, необходимый и достаточный для поддержки физики, после чего уезжали в Великобританию и получали там Нобелевскую Премию за графен, после чего делали дурацкие заявления, что якобы изобретение графена моментально обнуляет все существующие силиконовые технологии.

Но а что делать остальным 98% физтехам, которых привлекли в юном возрасте в Долгопрудный рассказами о том, какое элитарное физико-ТЕХНИЧЕСКОЕ образование они смогут приобрести? Продолжать закрывать колоссальные дыры в физтеховском образовании - самообразованием, как это приходилось делать 25 лет назад? Например в то время ФУПМ некоторыми людьми позиционировался как факультет для подготовки хмм, произнесем это постыдное слово, программистов. Эта де-факто ошибочная точка зрения подкреплялась например тем, что базами ФУПМ-а была кафедра Поспелова по экспертным системам в ВЦ АН, Институт Проблем Кибернетики с группой написания компиляторов для векторного суперкомпьютера Электроника СС БИС и другие программистские места. Ну и чему учили на ФУПМе? Физике, математической физике и объему математики, необходимого и достаточного для поддержки физики, плюс мааленький курсик по дискретному анализу и полстранички LR(k) алгоритма в курсе "Теория и реализация языков программирования", который не содержал и 5% материала, который учили по компиляторам студенты Стенфорда и Беркли (dataflow analysis, register coloring и т.д.). Кое-что учили на базах (теория графов, RTOS, базы данных), но не совсем в систематизированном виде.

В результате у студентов-компьютерщиков с ФУПМа образовывалось в мозгу два островка понимания мира - физика и выученное самостоятельно программирование на Си. Между этими островками находился абсолютный вакуум, в котором иногда пролетали астероиды самостоятельно выученного ассемблера, популярных статей про векторые суперкомпьютеры в русском переводе журнала "Electronics" и подобные случайные вещи. Небольшим архипелагом стояла Студенческая Лаборатория Компьютеризации под лидеством почившего Олега Бацукова в Лабораторном Корпусе, но это был скорее тоже развернутый вариант коллективного самообразования.


Только спустя 20 лет Сергей Вакуленко ramlamyammambam дал мне разумное объяснение почему это было устроенно именно так. Согласно Вакуленко, на физтехе был крен в сторону матфизики, потому что стране были нужны программисты, которые были бы способны решать задачи типа расчета нагревания боеголовки при прохождении её через атмосферу. But seriously, folks. Прошло 25 лет, и к национальной задаче России бомбануть Америку прибавилась другая национальная задача - догнать и перегнать iPhone. И если россияне действительно хотят без дураков решить последнюю задачу, то им нужна другая программа физтеха - программа, в которой для компьютерщиков с самого первого курса была бы возможность пощупать весь спектр технологий между физикой и программированием на Си - logic design, FPGAs, logic synthesis, place and route, static timing analysis, computer architecture, pipelining, microcontrollers, embedded system design, RTOSes и другие.

Проблема непонимания студентами, что происходит между физикой и языками высокого уровня несколько лет назад встала и в американских университетах, но по другой причине - в качестве источника проблемы называют широкое распостранение языка программирования Java. Для преодоления непонимания изобрели противоядие - так называемый курс "From Nand to Tetris", основанный на работах Noam Nisan and Shimon Schocken. Например стенфордская версия курса описывается так:


CS 116: From Nand to Tetris

Imagine starting with nothing more than a vast supply of Nand gates, and then building, step by step, a general purpose computer that can run Tetris, or any other game that you fancy. That's precisely what we'll do in this course. In the process, you will learn how to construct a simple hardware platform, and how to develop an assembler, a virtual machine, a compiler for a simple Java-like language, and a basic operating system. Open to undergraduate and graduate students of all levels. Prerequisites: programming experience (Introduction to CS or equivalent).

Слайды к одному из подобных курсов - http://www1.idc.ac.il/tecs/course/talk.pdf

К сожалению, даже если на физтехе такой курс скопируют, я не уверен, что он будет очень эффективным. Ибо, как сказал поэт "физтехи, физтехи, физтехи - за ночь просекали кванты". Иными словами, люди будут учить такой курс в ночь перед экзаменом, через два дня после сдачи у них в мозгу спутается HDL и ассемблер, а через месяц они забудут, о чем вообще шла речь. Чтобы идеи такого курса впитались на уровне интуиции, ИМХО гораздо лучше ввести эти концепции с помощью серии простых лаб, которые бы имели наглядный результат - сделанную руками схему или игрушку с микроконтроллером. Такое знание не выветрится. Также это труднее списать. При этом, лабы не должны требовать обширной теоретической базы - подготовится к ним в принципе мог бы даже восьмиклассник.

Я предлагаю для лаб примерно следущую последовательность (это набросок для блога, а не окончательный проект):

Внимание! Это лабы для программистов первого-второго курса, а не для товарищей с ФРТК (электронщиков). Электронщикам это же нужно вводить в гораздо бОльших количествах, медленно и печально.

1. Сборка простых электронных схем на основе микросхем малой степени интеграции
   
   • Знакомство с концепциями логического элемента (gate), D-триггера (D-flip-flop) и синхросигнала
   • Макетная плата (breadboard), батарейка, лампочки (LED), проводочки, микросхема генерации синхросигнала (555 Timer), CMOS микросхемы серии 4000, 7-сегментный дисплейчик
   • Лаба - сборка на макетной плате всяких счетчиков и бегающих огоньков
2. Дизайн цифровой логики на языке SystemVerilog с реализацией на платах ПЛИС (FPGA) от Xilinx или Altera
   
   • Знакомство с языком SystemVerilog и его конструкциями - модуль, порты, сигналы, always-blocks, continuous assignments, blocking и non-blocking assignments
   • Знакомство с концепциями моделирования (HDL simulation), логического синтеза, place-and-route, static timing analysis
   • Знакомство с бесплатным/дешевым софтвером Xilinx ISE WebPACK, Altera Quartus II, Aldec HDL, ModelSim-Altera Starter Edition
   • Знакомство с FPGA платами - Xilinx Basys 2, Xilinx Nexys 2, Altera DE0, Altera DE1
   • Лаба - переписать на верилог, засинтезировать и загрузить на плату дизайнов счетчиков и бегающих огоньков из первой лабы
3. Конечные автоматы и дизайн с адресуемой памятью
   
   • Знакомство с концепцией конечного автомата (state machine)
   • Знакомство с устройствами ввода на плате - клавишами и кнопками, и как их debounce
   • Знакомство с концепцией адресуемой памяти и интерфейса шины
   • Лаба - конечный автомат, принимающий от переключателей команды чтения и записи в память всяких последовательностей
4. Что такое процессор?
   
   • Знакомство с концепциями комбинационной и секвенциальная логики (combinational and sequential logic)
   • Лаба - простейший процессор, выполняющий команды в один длинный цикл. Дискуссия о максимальной тактовой частоте.
   • Концепция конвейера
   • Лаба - конвейерный процессор с 3-5 стадий и без interlocks - hazards компенсируются nop-ами
   • Концепция stalls и forwarding
   • Лаба - конвейерный процессор с stalls и forwarding
5. Программирование на голом железе и зачатие операционной системы
   
   • Лаба - знакомство с платой chipKit32 / PIC32 / MIPS и программирование её на С с помощью Arduino-подобного GUI. Кнопочки, лампочки, дисплейчик, IO Shield.
   • Введение в ассемблер на примере MIPS
   • Лаба - загрузка в память программок на ассемблере
   • Концепция простейшей многозадачной операционной системы
   • Лаба - своя игрушечная многозадачная ОС, которая бутится, ставит обработку прерывания по таймеру, в котором переключает задачи по схеме round-robin.

Теперь займемся шоппингом. Я перечислю платы и книги, которые с моей личной точки зрения могут быть полезны для такого курса. Для сборка простых электронных схем на основе микросхем малой степени интеграции пригодится набор tron.ix 2 от компании Gibson Sales Systems - http://www.gssteched.com/TRONIX2.html. В принципе, этот набор состоит из деталек, которые можно купить в любом магазине радиодеталек типа Radio Shack или Fry's Electronics, но Гэри Гибсон подобрал эти детальки любовно и написал простую практичную книжку с картинками, как их собирать на макетной плате. В числе деталек генератор синхросигнала (555 Timer IC) и CMOS микросхемы серии 4000. Справа - картинка с примером такой микросхемы - 4011 с четырьмя NAND гейтами. В книжке также на пальцах объясняется теория (гейты и флип-флопы). Строго говоря, эту книжку и набор можно использовать не только в физтехе, но и в детском саду для одаренных детей, и в этом её прелесть. Все вместе стоит $49.


Содержание книжки и список схем, которые можно построить из набора:

Table of Contents

1 .Digital vs Analog
2. Digital Terminology
3. Solderless Circuit Board Assembly
4. LED Logic Indicator Circuit
5. 'AND' Logic Gate with discrete components
6. 'OR' Logic Gate with discrete components
7. 'NOT' and 'YES' Logic Circuits
8. 'NOR' Logic Gate
9. 'NAND' Logic Gate
10. 2 'NAND' Logic Gate Clock
11. 'NAND' Logic Gate Timer
12. 2 'NAND' Logic Gate Memory Circuit
13. 555 Timer IC and formulas
14. Binary Counter Circuit (MOD16)
15. Decade Counter Circuit (MOD10)
16.2,4,8,16 Divider Circuit
17. Digital Readout LED display
18. Digital Readout Decoder Chip
19. Digital Counter with 7-Segment Display
20. Digital UP-DOWN Counter
21. 8-Output Multiplexer Circuit
22. Digital 'Chasing Lights' Circuit
23. Visual 'Logic Probe' Circuit
24. 'Touch-Activated' Pulse Generator
25. 555 Pulse Train Generator
26. Yes/No Decision Maker Circuit
27. Yes/No/Maybe Circuit
28. Stop-Action Timing Circuit
29. Digital 'Touch-Activated' Switch
30. Digital 'Stepping Touch-Activated' Switch
31. Digital 'Light-Activated' Counter Circuit
32. 'Winning Number' Generator
33. Digital Dice Circuit
34. Introduction to Flip-Flops
35. 'D' Flip-Flop circuits
36. 'J-K' Flip-Flops

37. Schmidt Trigger

38. Shift Registers

39. OP AMP Circuits


Раскрытая книжка:




Детальки в наборе:



Пример схемы, собранной на макетной плате: 555 таймер, счетчик, декодер из BCD в 7-сегментный дисплей, 7-сегментный дисплей:







Следущим номером нашей программы являются платы ПЛИС / FPGA (программируемые логические интегральные схемы или Field Programmable Gate Arrays). Это чрезвычайно занятные монстры, которые очень удивляют тех, кто с ними сталкивается впервые. Я с ними впервые столкнулся в 1996 году, но сейчас прохожу курс для освежения знаний по этому вопросу в University of California Santa Cruz Extension in Silicon Valley. Удивительность их заключается в том, что они позволяют создавать "меняющееся железо", причем не с помощью программной эмуляции или там виртуализации, а более прямым и "железным" способом.

В самом простом варианте FPGA состоит из матрицы однородных ячеек, в функцию каждой из которых можно поменять с помощью мультиплексоров, подсоединенных к битикам конфигурационной памяти. Одна ячейка может стать гейтом AND с четырьмя вводами и одним выводом, другая - однобитным регистром и т.д. Загрузил в конфигурационную память последовательность битов из памяти - и в FPGA образуется заданная электронная схема, которая может быть процессором, контроллером дисплея и т.д. Справа - схема простейшего блока FPGA, в который входит look-up table (LUT) и flip-flopю Правда в этой схеме не показаны мультиплексоры, которые меняют функцию ячейки, и соединения с конфигурационной памятью.

По-сути, FPGA может заменить мешок микросхем и проводков из первой лабы, причем соединения задаются конфигурационной памятью. На FPGA можно строить не-фон-неймановские процессоры, делать сто параллельных сложений за один цикл и вообще реализовать массу вещей без процессора. Конечно в FPGA можно запрограммировать и процессор, создать собственную версию процессора для каждого программиста.






FPGA настолько впечатляют народ, что находятся люди, которые считают, что FPGA-ев не бывает, а разговоры о них - это "бредовые фразы" людей, "употребляющих тяжелые наркотики". К сожалению, к таким неверующим Фомам относится и известный обозреватель пользовательских качеств гаджетов и российский специалист по Голливуду Алекс Экслер exler ( http://exler.ru ):


exler: "Степа придумал, цитирую по передаче, как микропроцессор перенести в память путем программирования. Честное слово! Поскольку эту бредовую фразу повторял и наставник Степы, ошибки никакой нет. "

"Скоро будут совсем новые компьютеры, сказал наставник детишек. Каждый программист будет делать процессор под себя... Вообще людей, употребляющих тяжелые наркотики, нельзя допускать до работы с детьми."

Тем не менее, товарищ Экслер, единороги, то бишь FPGA-и бывают и платы с которыми могут играть школьнеги, выглядят так:




http://digilentinc.com/Products/Detail.cfm?NavPath=2,400,790&Prod=BASYS2

На этой плате используется метод ввода информации рычажками, который тоже возмущает Экслера, и, что самое ужасное, плата спроектирована не в Ангарске, Лапотная Россия, а в Сан-Хосе, Калифорния, в той же Калифорнии, где находится любимый Экслером Голливуд:


exler: Нажимаешь один рычажок - вводится единичка. Нажимаешь другой - вводится двоечка. Думаете, кто-то из нас долбанулся? Нет! Тут все дело в том, что все работает без микропроцесоора, который есть у любой современной клавиатуры!

Кстати, в клавиатурах действительно есть микрокопроцессоры / микроконтроллеры - Intel 8048 или Intel 8051. Так что я не понимаю, над чем тут ухмыляется Экслер. Например википедия пишет The original IBM PC keyboard used an 8048 as its internal microcontroller

Вообще, Экслер иногда напоминает Радулову в штанах, которая тоже не хочет, чтобы россияне посмели строить собственную электронику, но Радулова по крайней мере не берется рассуждать о несуществовании возможности "каждый программист будет делать процессор под себя". Впрочем что Экслер, что Радулова будет всегда ругать мальчика Степана Большедворского из Ангарска, только по разным причинам - Радулова будет упирать на то, что Степан не моет посуду и не дарит суженой романтические бриллианты во время ужина при свечах.

Да, но продолжим про FPGA-платы. Плата выше стоит для студентов $49, но есть более навороченная плата Nexys 2 за $99, в которую входят дополнительные микросхемы внешней к FPGA памяти (несколько мегабайт cellular RAM и Flash). Т.е. если на Basys2 сделать игрушечный процессор, то к нему можно будет присобачить всего несколько десятков килобайт памяти внутри самого FPGA-я, в то время как на Nexys 2 программист может не только запрограммировать в конфигурационную память FPGA-я собственный процессор, но и гонять на нем Линукс (!), хотя и довольно медленно.


Более навороченная плата для школьников из Ангарска - Nexys 2:

На Nexys 2 есть лого Интела, но лого стоит не на процессоре (которого там нет), а на Flash-памяти:

http://digilentinc.com/Products/Detail.cfm?NavPath=2,400,789&Prod=NEXYS2





Для курсов, построенных на основе плат Basys 2 или Nexys 2 на Xilinx Spartan 3E FPGA есть очень на мой взгляд удачная книжка, которая начинается с базовых гейтов, а заканчивается, как подсоединить к FPGA монитор VGA и рисовать хардвером на нем картинки. Про подсоединение к клавиатуре и мышке там тоже есть. Вообще после того, как студент пройдет данную книжку (которая содержит существенно больше информации, чем предлагаемый мною курс), он может в принципе сделать не-фон-нейманновский компьютер без процессора (whatever the definition is) и троллировать им Экслера. Впрочем, Экслер все равно скринит у себя в блоге коментарии, так что полноценного троллирования не получится.

Вот как выглядит эта книжка:

http://digilentinc.com/Products/Detail.cfm?NavPath=2,729,746&Prod=LBE-DD



Table of Contents:
1. Introduction
2. Basic Logic Gates
3. Boolean Algebra and Logic Equations
4. Implementing Digital Circuits
5. Combinational Logic
6. Arithmetic Circuits
7. Sequential Logic
8. Finite State Machines
9. Datapaths and Control Units
10. Integrating the Datapath and Control Unit
11. Memory
12. VGA Controller
13. PS/2 Port
Appendix A - Aldec Active-HDL Tutorial
Appendix B - Number Systems
Appendix C - Making a Turnkey System
Appendix D - VHDL/Verilog Quick Reference Guide

Free student edition of Active-HDL simulator is available from Aldec Inc (www.aldec.com). To synthesize your design to a Spartan3E FPGA, you will need to download the Free ISE WebPACK from Xilinx Inc.(www.xilinx.com)


Кроме плат с микросхемами Xilinx, для обучения студентов можно использовать платы с микросхемами их конкурентов - Altera:

http://www.altera.com/education/univ/materials/boards/unv-dev-edu-boards.html

http://www.altera.com/education/univ/images/boards/de0.jpg

$59-$79



http://www.altera.com/education/univ/images/boards/de1.jpg

$125 Price in quantities ≥ 30 $99




На FPGA можно реализовать собственный игрушечный процессор на Verilog-е, используя в качестве учебника по тому, как это сделать, одну из следующих книг.
Учебники по компьютерной архитектуре с привязкой простейшего конвейерного процессора к коду на Verilog-е:

Computer Organization and Design, Fourth Edition: The Hardware/Software Interface
David A. Patterson, John L. Hennessy

Digital Design and Computer Architecture
David Harris, Sarah Harris




Для предлагаемого мною курса я strongly recommend Harris & Harris (в Patterson & Hennessy слишком много воды и не-essential штучек).


Теперь перейдем к третьей фазе - обучение студентов и старших школьников использованию микроконтроллеров, программированию на голом железе и зачатию операционных систем. Про Arduino-совместимые платы на основе микроконтроллеров PIC32 я уже писал - http://panchul.livejournal.com/172831.html

Эти платы позволяют использовать сначала дружественный GUI на подсоединенном к плате компьютере и программировать на плате простые фокусы на урезанном C, когда к плате присоединяются лампочки, моторчики, дальномерки и программка их в цикле опрашивает и управляет (при этом никаких прерываний или многозадачности). Эта простота снимает психологический барьер для студентов, которые никогда в жизни не видели встроенные системы (embedded systems).

Но одновременно с помощью некоторых фокусов в эту плату можно загрузить и полноценный имидж, сгенерированный с помощью обычной GNU toolchain и содержащий собственный boot code и обработчики прерываний на ассемблере - иными словами, эту плату можно использовать и для введения в программирование на голом железе. В частности можно сделать игрушечную многозадачную ОС, которая бутится, ставит обработку прерывания по таймеру, в котором переключает задачи по схеме round-robin. Я сделал такой multitasker после 9 класса на Летней Школе Юных Программистов в Новосибирске летом 1986 года для процессора Z80. Было очень круто.


Вот самая простая плата за $26:

http://digilentinc.com/Products/Detail.cfm?NavPath=2,892,893&Prod=CHIPKIT-UNO32




Вот плата покруче, которую можно подсоединить к сети:

$49.50

http://digilentinc.com/Data/Products/CHIPKIT-MAX32/chipKIT-Max32-obl-500.jpg




Вот вспомогательная плата с кучей устройств ввода-вывода - лампочек, кнопочек:

$37.99

http://digilentinc.com/Products/Detail.cfm?NavPath=2,892,936&Prod=CHIPKIT-BASIC-IO-SHIELD




Вот роботы, которые построили студенты и школьники в Китае и Румынии на основе микроконтроллеров PIC32:

http://www.mips.com/blog/?p=80