?

Log in

No account? Create an account
Пролистал 2-е издание Hacker's Delight в поисках занятных задач для лабника по Verilog & FPGA - Юрий Панчул [entries|archive|friends|userinfo]
Money can buy bandwidth. Latency requires bribing God.

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Пролистал 2-е издание Hacker's Delight в поисках занятных задач для лабника по Verilog & FPGA [Jan. 15th, 2018|02:03 am]
Yuri Panchul
Hacker's Delight - чрезвычайно занятная книжка, назначение которой народ совершенно не понимает. Хотя разумеется не весь народ. Например у нас в офисе MIPS эту книжку любят - когда я забыл ее где-то (наверное в туалете), ее заметил мой коллега, начал ее читать, зачитался, и я нашел книжку только через неделю, после того, как разослал емейл по всему офису.

Но почитайте комменты к первому и второму изданию этой книжки на Озоне:


Отзыв 1: "Очередной опус из серии "Как облапошить компилятор" -- классика стиля программистов на С. Собственно, ничего другого по C и программистами на C и не написано. Это не алгоритмические трюки -- это трюки с плохим языком программирования. На практике малополезно и методически вредно".

Отзыв 2: "Ничего не могу сказать против этой книги, но она явно предназначена для узкого круга специалистов. Например, для тех, кто хочет ускорить на десять процессорных тактов операцию деления за счет снижения переносимости и полной нечитабельности кода.
В наш век большинство программистов пишут на таких языках как C# или JavaScript, поэтому виртуальная машина или интерпретатор съест всю выгоду описанных хакерских трюков, а поддерживать код становится трудно".



Это отрицательные отзывы. Но даже люди, которые написали положительные отзывы, эту книжку тоже не понимают. Они думают, что это чтобы улучшить программирование на Си для высокопроизводительных приложений. Это тоже не совсем верно.

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

1. Пишет компиляторы.

2. Пишет стандартные библиотеки программ на Си и ассемблере.

3. Работает над компьютерной архитектурой: анализирует смеси инструкций в приложениях и придумывает, какие инструкции добавить в систему команд процессора.

4. Занимается хардверной реализацией микроархитектуры процессоров, а также специализированных вычислительных блоков, на уровне регистровых передач.

(У нас в компании есть четыре соответствующих отдела, где такие знания нужны).

Так вот. Я пролистал книжку Hacker's Delight ( https://doc.lagout.org/security/Hackers%20Delight.pdf ), чтобы найти в ней какие-нибудь занятные алгоритмы и трюки, на основе которых можно было бы сделать задачки для лабника по разработке аппаратных блоков на уровне регистровых передач, с использованием языка описания аппаратуры Verilog и с реализацией на программируемых логических интегральных схемах ПЛИС / FPGA.

Зачем нужны именно задачки на основе примеров и идей из Hacker's Delight? Чтобы добавить что-нибудь новое, яркое, а не повторять одни и те же унылые упражнения из tutorials от Xilinx, Altera и учебников 25-летней давности.

И вот что я выудил из пролистывания Hacker's Delight (второго издания - это важно - в интернете можно отыскать PDF первого издания, но не второго, часть моих находок именно из второго издания):




1. Выключение самой правой из единичек в последовательности битов можно сделать как помощью кучи if-ов в комбинационном always-блоке, так и через выражение "n & (n - 1)". Студент может сравнить, во что синтезируется одно и другое представление, какие у них будут параметры по количеству логических элементов и задержкам (для измерения последнего нужно будет зажать комбинационную схему между двух регистров и напустить на это static timing analysis):







2. Оказывается, существует "русская декомпозиция" функции от трех булевских аргументов в исключающее-или от двух функций, у каждой из которых два булевских аргумента. Можно дать студентам задания написать такие декомпозиции, после чего с помощью симуляции и синтеза на FPGA плате продемонстрировать их эквивалентность. Заодно можно упомянуть им, что так же можно сделать и формальную верификацию:









3. Элегантный способ подсчитать количество единичек в слове. Опять же, студенты могут сравнить решение "в лоб" с вот таким быстрым решением:







4. Алгоритм нахождения LRU (least recently used) - отличный способ связать вводный курс цифровой схемотехники с последующим курсом микроархитектуры процессора. Он используется для определения, какую строку нужно вытолкнуть из многосекционного кэша:













5. Вычислитель для особого случая деления на константу 3. Студент может сравнить с устройством деления для общего случая:





6. Извлечение целочисленного квадратного корня. Студент может сравнить комбинационную, последовательностную и конвейерную реализации. Я написал код этого примера и выложил его на https://github.com/MIPSfpga/digital-design-lab-manual/tree/master/lab_10/src/lab_10_2_isqrt/old_yuri_panchul_example. Вообще для каждого упражнения в этом списке нужно написать полностью несколько вариантов решения с анализом и сравнениями (количество логических элементов и максимальная тактовая частота для каждой хардверной реализации и различных размерах данных). Потом эту задачу (без решения) стоит давать студентам для упражнения. Чтобы не было списывания, делать вариации (например одна реализация - behavioral synthesizable RTL, другая - structural):









7. То же, но для кубического корня:







8. Gray code и gray counter - пример последовательностной логики, с привязкой к использованию в асинхронном FIFO между блоками схемы, работающими с тактовыми сигналами разной частоты (clock domain crossing - см. статью Clock Domain Crossing (CDC) Design & Verification Techniques Using SystemVerilog by Clifford E. Cummings):





















9. CRC: отличный пример последовательностной схемы с LFSR, привязка к вузовской математике, привязка к построению надежных чипов для космоса и (в последнее время) автомобильного рынка:









10. Error-correcting codes: продолжение темы CRC для продвинутых студентов, возможная тема для курсового проекта:





11. Хардверный вычислитель для элегантной кривой Пеано-Гильберта, которая извивается, покрывая все пространство. Может быть упражнение для лабы с арифметическими блоками.














Какие идеи для упражнений и студенческих проектов вам понравились?

1. Быстрое выключение самой правой из единичек в последовательности битов
1(3.6%)
2. "Русская декомпозиция" функции от трех булевских аргументов в исключающее-или от двух функций двух переменных
2(7.1%)
3. Быстрый подсчет количества единичек в слове
3(10.7%)
4. Нахождение LRU (least recently used), используется для работы многосекционного кэша
3(10.7%)
5. Вычислитель для особого случая деления на константу 3
3(10.7%)
6. Извлечение целочисленного квадратного корня
3(10.7%)
7. Извлечение целочисленного кубического корня
2(7.1%)
8. Gray code и gray counter, с привязкой к асинхронному FIFO и clock domain crossing
2(7.1%)
9. CRC: пример последовательностной схемы с LFSR, привязка к математике и к надежным чипам для космоса и автомобилей
3(10.7%)
10. Error-correcting codes: продолжение темы CRC для продвинутых студентов, возможная тема для курсового проекта
4(14.3%)
11. Хардверный вычислитель для кривой Пеано-Гильберта, которая извивается, покрывая все пространство
1(3.6%)
12. У меня другое предложение (привести в комментариях)
1(3.6%)
LinkReply

Comments:
[User Picture]From: ardelfi
2018-01-15 10:35 am (UTC)
12. Любое упражнение лучше привязать к осмысленной задаче. Оно может от этого ничуть не измениться по форме, но решать осмысленную задачу может быть интересно с большей вероятностью чем бессмысленную. Например, ECC:
В чип попала частица и флипнула один бит. Так вот, дети, забудьте об этом -- старые добрые времена кончились до вашего рождения. В чип попала частица и флипнула 50 бит в самых разных его местах -- вот теперь мы вернулись в реальность. Придумайте архитектуру и схему для коррекции 50 флипнутых бит в гигабитном чипе, и одного дохлого чипа из восьми в байте.
Эта задача может занять день или неделю, но её интересно решать, и стандартных решений для неё нет, а найденное решение не раз в жизни пригодится.

Edited at 2018-01-15 10:37 am (UTC)
(Reply) (Thread)
[User Picture]From: andrey_yurin
2018-01-15 11:12 am (UTC)
Вот, кстати, да. Неистово плюсую к задачам подобного типа. Не знаю кому как, но у меня "классика" типа вычисления синуса из розового слона вызывает тоску. Ну т.е. понятно, что в рабочем процессе это неизбежно. Равно как и вычислительная математика с православным учебником в виде Демидовича-Марона. Но вот когда мне пытались донести HDL-кодирование и теорию автоматов в её классическом виде я вообще не понимал что это и для чего нужно. Как раз из-за оторванности всего этого от практики.
(Reply) (Parent) (Thread)
[User Picture]From: panchul
2018-01-15 05:09 pm (UTC)
Вот этот пост именно для того, чтобы вы написали список тривиальных, но при этом интересных примеров тех же конечных автоматов, которые можно засунуть во вводный курс HDL вместо одного и того же кочующего из методички в методичку семафора и подобных упражнений.
(Reply) (Parent) (Thread)
[User Picture]From: andrey_yurin
2018-01-15 05:23 pm (UTC)
Ну над примерами - это подумать надо. Я в своё время VHDL учил сразу на рабочих проектах. Т.е. это было что-то типа:

Берём готовую IP-функцию DDR контроллера, разбираемся что у неё с портами, осиливаем общий синтаксис HDL, вникаем в саму суть паралельного исполнения кода, вникаем чем сигнал отличается от переменной, навешиваем к этой DDR памяти приёмник данных, вывод на монитор и вот оно что-то заработало.

Что такое автоматы Мили и Мура я - если честно - даже сейчас без википедии не вспомню толком. Вот как-то оно не пригождалось вот вообще. На начальных порах всегда хватало case - ветвления, if...else, работы с памятью и ещё пары таких же подобных вещей.

А вот потом, когда всё это было закреплено и осилено - вот тогда уже начиналось заглубление в теорию. И рождались фразы типа: "ух ты, а ведь вот это вот case-ветвление вот этот вот автомат описывает. Ууууу..."

В принципе я парней натаскивал на работу именно такой системой. За год парни разгонялись до уровня поделок, которые уже приносили определённый профит.

А так из примеров что на ум приходит... Ну тут надо мозгой пораскинуть и вспомнить себя 10 лет назад. Что мне тогда интересно было. Парни кто помоложе - они всякие гаджеты собирать любят типа спинеров со свистелками и мигалками. Датчики всякие и тому подобное.
(Reply) (Parent) (Thread)
[User Picture]From: panchul
2018-01-15 05:07 pm (UTC)
Как исследовательский проект - да. Во вводном курсе нужно начинать с тривиальных вещей. Другое дело, что эта вводность и тривиальность не обязана быть такой унылой, как в tutorials и методичка, которые используются последние 25 лет.
(Reply) (Parent) (Thread)
[User Picture]From: panchul
2018-01-15 06:08 pm (UTC)
Переформулируйте вашу задачу в виде, в котором ее можно вставить в лабник для использования в большом количестве вузов с тысячами студентов, чтобы время ее решения для как минимум 10% студентов вписывалось в семестр.
(Reply) (Parent) (Thread)
From: realurix
2018-01-15 07:34 pm (UTC)
А самому слабо сформулировать? Есть теория, кстати математическая, строгая, плотных упаковок. Коды с восстановлением ошибок основаны именно на ней. А вот диагностика работы одного триггера - это задача для построения схем асинхронной синхронизации. Лучше предложить решение этой задачки - простенько и со вкусом. И, кстати, асинхронность снижает энергопотребление раза в 3-4, ибо затраты энергии идут только там, где производится работа по изменению информации, а не в целом по всей больнице. Если в городе завёлся еретик, то в городе не закрывают все церкви. В синхронном режиме закроют все.
(Reply) (Parent) (Thread)
[User Picture]From: ardelfi
2018-01-15 09:28 pm (UTC)
За семестр небезнадёжный студент успеет при такой формулировке. Но если угодно сухой прозы, попробую высушить, и даже подчеркну на что смотреть сонному студенту.
В космический аппарат прилетает не менее одного галактического иона в секунду, что при контакте с конструкциями создаёт нейтронный поток. Память контупера аппарата построена по архитектуре 1Гбит×8. Попадание одного нейтрона в чип памяти флипает до 50 бит. Отказ одного чипа повреждает один бит в каждом байте памяти.

Задача: обеспечить работу памяти без сбоев в потоке галактических ионов при отказе одного чипа на протяжении не менее одной секунды.


Edited at 2018-01-15 09:29 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: panchul
2018-01-15 11:20 pm (UTC)
Типа memory controller с троированием написать? Речь идет про уровень register transfer level.
(Reply) (Parent) (Thread)
[User Picture]From: ardelfi
2018-01-16 12:03 am (UTC)
Я понял ваш контекст сразу, и в этом контексте написал задачу. Студент пишет решение на HDL, синтезирует в FPGA и в тестбенче с инжекцией флипов, а также сбоя целого чипа, показывает как оно работает.

Конечно не троирование. Это шаблонное решение для проблемы из восьмидесятых годов прошлого века, когда транзисторы в чипах были больше микрона, и одна частица давала один флип. Радиус "зоны поражения" частицы имеет порядок 100нм, вторичные эффекты (там каскад частиц) выходят далеко за эту зону, потому и получаются десятки флипов от одного нейтрона. Сейчас проблема одиночного сбоя, решаемая троированием, стала лишь одной из подобных проблем, и самой простой.

У студента есть гигабитный чип (модель) и условная FPGA для всего остального. Сколько он чипов использует (8+1, 8+2 или ещё как) -- это часть задачи. При 8+1 задача не решается -- один чип дохнет, и остаётся 8 без возможности коррекции. Дальше есть выбор кодов от простейшего Хамминга до Рида-Соломона и подобного. Но и это не даёт возможности нагуглить решение, что заставит студента напрячь мозг -- иначе зачем он вообще пришёл? :) Также должен быть в какой-то форме скраббинг -- теневой процесс патрулирования памяти и автоматической коррекции ошибок, что напоминает рефреш для динамической памяти. Всё это должно быть спрятано в условной FPGA между памятью и процессором. Для процессора же это всё должно быть незаметно, будто память идеальная и ничего плохого с ней случиться не может. Получается что компоненты (перечисленные) для решения есть, а готового решения нет -- студенту и нужно его придумать. За семестр вполне получится, и в результате студент ощутит что он таки что-то может кроме получения оценок.
(Reply) (Parent) (Thread)
[User Picture]From: panchul
2018-01-16 12:28 am (UTC)
Понял. Спасибо, я об этом подумаю.
(Reply) (Parent) (Thread)
[User Picture]From: ardelfi
2018-01-16 12:52 am (UTC)
И ещё вариант попроще. SEC-DED есть готовый, а коррекции двух ошибок готовой нет. Это можно сделать (если не ошибаюсь) в 144-битной архитектуре памяти с 128 битами данных и остальным на коррекцию. Это позволяет корректировать двойные ошибки при всех функциональных чипах, или одну ошибку при одном дохлом чипе. Однако вариант не совсем уж простой: нужно память подключить к 144 линиям, а процессор будет обращаться по своим 32, потому FPGA должна считывать из памяти блоки, а процессору отдавать фрагменты, и наоборот. Кстати, это реально полезная и нужная штука: 8+1 чипов по 16 бит шириной, но FPGA ещё придётся транспонировать ширину в длину при обращениях к памяти, иначе коррекция не получится. :)

Edited at 2018-01-16 12:54 am (UTC)
(Reply) (Parent) (Thread)