January 15th, 2018

2017

Пролистал 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 первого издания, но не второго, часть моих находок именно из второго издания):

Collapse )

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

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