Оптимизации АЛУ

[spamsink]

После переписывания дорогих команд сборки, разборки и сдвига в многотактный вид и исправления нормализации вправо инвертированных мантисс (прибавлять младший бит инверсии можно по ходу нормализации, и в окончательном суммировании РМРу участвовать больше не нужно) всё стало гораздо компактнее:

There are 31 levels of combinational cells
2-input LUTs: 309
3-input LUTs: 231
4-input LUTs: 228
5-input LUTs: 375
6-input LUTs: 726
Total LUT area: 1869
State : 204
(FF) : 204
CARRY4 : 132
DSP : 6

Коммит будет сегодня вечером.

Comments

[vak]

Печально мне стало смотреть, как операция сдвига тратит десятки тактов. Переделал на сдвиг на четыре бита за такт. Медленную версию можно включить дефайном SLOW_SHIFT. Можешь глянуть, насколько больше лутов синтезируется?

[spamsink]

Стало 2183. Ну ужас, но не ужас-ужас-ужас. ©

[spamsink]

Примерно во сколько LUT/FF оно всё в общей сложности должно синтезироваться, если мы хотим уместиться в маленькой платке?

[vak]

То есть четырёхбитный сдвиг увеличивает размер АУ на 17%. Ну может и ничего, учитывая популярность сдвигов в софте.

На маленькой платке 7680 лутов с флипфлопами. Вроде мы укладываемся.

[vak]

На плате DE10-Lite с чипом Altera Max10 аж 50 тысяч логических элементов (лутов с флипфлопами). Если разводить свою плату для МЭСМ-6, имеет смысл ставить Max10. Уместимся в 8K логических элементов - будет дешевле.

Вот наличие и цена Max10 (25 штук) в корпусе QFT144 на mouser.com в зависимости от количества логических элементов:

10M08 - $13.97
10M16 - $27.29
10M25 - $31.61
10M40 - $43.39
10M50 - $48.46

[spamsink]

Вот сколько стоит CLZ сам по себе:

There are 10 levels of combinational cells

Total LUT area: 52

[vak]

Десять уровней это плохо, на частоте скажется. Имеет смысл переделать на потактовую обработку.

[spamsink]

Чтобы 10 уровней стали критичны, нам еще работать и работать. Пока ведь критический путь - 31.

[vak]

Интересно, где же такой длинный путь набежал.

[spamsink]

В clz, вестимо. Если я его заменяю на что-то попроще, например, XOR 8 групп по 6 бит, то критический путь уменьшается на 3.

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

[vak]

Давай clz тоже на такты разобъём.
Скажем, четыре разряда на такт.

[spamsink]

Не надо. Достаточно одного дополнительного такта: отделить определение номера единицы и числа единиц от сложения.

[x86128]

Подскажите, а из какой книги черпать вот эти вот хитро оптимизированные алгоритмы?

[spamsink]

Какие именно? По количеству логических уровней в АУ БЭСМ-6 всё оптимизировано куда лучше, чем у нас сейчас, оттуда мы идеи и берем.

[x86128]

Да я имел ввиду чтото наподобие такого https://www.amazon.com/Implementation-Arithmetic-Functions-Electrical-Engineering/dp/9401784388

Либо общая теория без привязки к FPGA или ASIC есть на примете.

[vak]

Неплохая книжка. Надо такую добыть.

Ещё вот это могу посоветовать, но она для более серьёзных случаев: https://www.amazon.com/Digital-Arithmetic-Kaufmann-Computer-Architecture/dp/1558607986/

[vak]

Сделал: ввёл дополнительное состояние STATE_ADD_B. Теперь ACX и ANX выполняются за три такта. Стало ли лучше?

Кстати, Altera не умеет синтезировать $countones().

[spamsink]

Я до обеда сделал то же самое практически идентично, с той лишь видимой на глаз разницей (кроме имен переменных и порядка состояний), что

wire [47:0] a_mux = (state == STATE_IDLE) ? a : acc;

Мой вариант - 2307 LUTs, 23 levels; твой - 2302 LUTs, 24 levels. Если твой вариант так исправить, становится 23 уровня, но 2319 LUTs. Разница - в нумерации состояний и их последовательности в операторе case; видимо, это артефакты синтеза для эмуляции, потому что он ради эквивалентности с софтверной симуляцией не переводит регистр состояния в 1-hot вид.

Synplicity для Spartan7 с максимумом оптимизации за разумное время (72 секунды) делает

Register bits not including I/Os: 312 of 14600 (2%)
Block Multipliers: 9 of 80 (11%)
Total LUTs: 2897 (19%)

И обещает частоту 121.6 MHz.

$countones в нашем случае пишется как

function [5:0] countones(input [47:0] a);
countones = '0;
for (int i = 0; i < 48; ++i) countones += a[i];
endfunction

и с ней синтезируется в те же зайцы.

[spamsink]

А включил SLOW_SHIFT - стало 130 MHz, 2267 LUTs, регистры стало ненужно сильно размножать, вышло 266. И критический путь теперь проходит через tmp в STATE_DIVIDING из-за условия ABS(tmp) < 1'b1 << 39 перед сложением-вычитанием.

[vak]

Получается, слегка ускоренный сдвиг требует 40 лутов и 46 регистров. Ну и пусть, не жалко.

120 мегагерц это неплохо. Я надеялся получить в районе сотни.

Я поправлю a_mux как у тебя, и добавлю функцию countones().

[vak]

Переименовал tmp в rail.
Не так глаз режет.

[spamsink]

Я не понял, почему именно rail. Рельсом обычно называют VCC или GND.

Согласно Synplify, количество уровней CARRY4 практически не играет роли, потому что задержка по переносу чуть не на порядок меньше, чем задержка в лутах, особенно если они большие, и между лутами.

Текущий вариант (со ещё чуть-чуть оптимизированной арифметикой)
default (2781 LUTs):

Clock Name (clock_name)	Req Freq (req_freq)	Est Freq (est_freq)	Slack (slack)
mesm6_alu|clk	        121.9 MHz	        127.4 MHz	        0.353

SLOW_SHIFT (2310 LUTs):

Clock Name (clock_name)	Req Freq (req_freq)	Est Freq (est_freq)	Slack (slack)
mesm6_alu|clk	        128.7 MHz	        131.0 MHz	         0.136

Так что логика для 8 вариантов быстрого сдвига оказывается на критическом пути, который Synplify пытался раздербанить, потратил 470 лутов, но так успеха и не достиг.

[vak]

В арифмометрах рельсой называли планку, по которой плашки с цифрами туда-сюда ездили.

Мне кажется, ускорение сдвигов того стоит.

[spamsink]

Пока, похоже, действительно стоит, если верить вольфрамальфе.

Когда релизнем, вот будет детишкам развлечение анализировать производительность и оптимизировать! Можно даже какую-нибудь сумму денег в качестве призов не пожалеть за максимальную производительность на Whetstone, Dhrystone и пр. Жаль, что мы до 50-летия БЭСМ-6 это не придумали.

[vak]

А как тебе вольфрамальфа помогает это видеть?

Теперь к 60-летию. :)

[spamsink]

Пусть программа в с быстрыми сдвигами тратит X тактов на все команды, кроме сдвигов, плюс Y тактов - сдвиги. Тогда с медленными сдвигами это будет X+4Y тактов. Условие равенства скоростей:

(X+4Y)/131 == (X+Y)/127.4

достигается при количестве тактов на (быстрые) сдвиги около 1%, что на невычислительной задаче вполне реально.

[vak]

Ну ты серьёзно к делу подходишь! :)

Глянем тест АУ, благо имеется файл трассировки. Всего выполнено 1178071 машинных команд, из них 78169 сдвигов. Это 6.6%, немало. Сдвиг вообще довольно популярная операция была, насколько мне подсказывает память и интуиция.

[vak]

Может быть тест АУ слишком специальная задача. Посчитаем количество сдвигов в тесте hello.pas. Всего команд 1063, из них 53 сдвига, то есть 4.0%.

[spamsink]

Ну вот; т.е. пока команд сдвига больше 1%, то тактов на них тратится больше 1% и подавно.
В каком-нибудь перемножении матриц на фортране сдвигов, считай, почти не было, но это не наш профиль. :)

С еще некоторыми оптимизациями в АУ, Synplify смог сделать, при запрошенных 140 МГц, 135.5 для быстрых сдвигов, и 139.8 для медленных.

[vak]

Умеет ли он синтезировать для семейства Altera Max 10? Интересно бы скорость прикинуть.

https://www.intel.com/content/www/us/en/products/programmable/fpga/max-10.html

У Max10конфигурационная память прямо на основном кристалле, поэтому он несколько удобнее по жизни.

[spamsink]

Наверное, умеет, но внутренняя лицензия показывает в меню только Synopsys и Xilinx.

[vak]

Синтезировал на скорую руку АУ через Altera Quartus для Max10. Получается 123-135 МГц (при 85°C-0°C соответственно).

Размер логики:
Total combinational functions: 3290
Dedicated logic registers: 211

[spamsink]

Частота, считай, практически та же, что и у Xilinx, а разница в количестве лутов, видимо, или из-за деталей реализации умножителя, или из-за того, что они более агрессивно реплицируют именно логику, а не регистры.