Пролистал 2-е издание Hacker’s Delight в поисках занятных задач для лабника по Verilog & FPGA

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

Впервые опубликовано — https://panchul.livejournal.com/583893.html