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

[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]

Больше чем в два раза, неплохо. Может быть теперь и Xilinx этот код скушает.

Вот твои старые оценки для микро-БЭСМ, для сравнения:
с микрокодом в логике: 15771 LUT, 5166 FF;
с микрокодом в блочной памяти: 9904 LUT, 10 BRAM.

Но это всё вместе, не только АУ.

[spamsink]

Теперь должен, раз комбинационных циклов больше не осталось.

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

[spamsink]

Модуль mesm6_cpu.sv сам по себе синтезируется в 847 LUTs, 475 FFs (что-то многовато), 17 CARRY4 и 90 CLB MUXes. Если ликвидировать uop_rom и заменить на case statement, получается 811 LUTs. Но на него, понятное дело, смотреть еще рано, пока нет прерываний и экстракодов.

Механизм прерываний может быть, например, такой: при возбуждении любого прерывания формируется слово: 15-1рр: М20, 30-16рр - адрес возврата, 47-42рр - режимы, 48р - признак правой команды, остальное - для маски прерываний. С этим словом выполняется как бы ЗП (М17).

ВЫПР, соответственно, будет работать как бы как МОД + РЖ + еще кое-что. Магазинность аналогична МОД.

[vak]

Красиво!
Но куча тестов сломалась:

Test asn_asx - FAIL
Test acx_anx - PASS
Test apx_aux - FAIL
Test stack - PASS
Test ntr_rte - FAIL
Test yta - FAIL
Test e+n_e-n_e+x_e-x - FAIL

И тест АУ не проходит.

[x86128]

Класс!
Я когда увидел конструции в pack/unpack и умножение как $signed * $signed только и изумился: "А что так можно было?!! 😂 😂". Но для RTL модели ведь можно, верно?

А дальше уже когда к железу "как в БЭСМ6" ближе спускаться, можно и убрать.
Я потому скрипт для сложения и сделал, пытаясь разобраться с тем как это было в самой БЭСМ реализовано (хотя и не точно).

Но вот с умножением получился пока затык, читаю книги с теорией и практикой реализации 2's compl умножителей в железе, вижу что в БЭСМ6 алгоритм Бута, но он какой-то модифицированный. Сам алгоритм придумали в 1951 году, поэтому "наши" о нём 100% знали, но улучшили.

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

Постараюсь сделать python скрипт.

[vak]

Ничего страшного, просто лимиты надо подправить.
Времянка-то удлинилась.
Я сделаю.

[vak]

15 индекс-регистров (на самом деле 16) по 15 бит это уже 240 FFs, половина. Аккумулятор и командное слово из памяти - ещё сотня. Ну и остальное по мелочи набегает. Так что 475 триггеров по божески получается.

Не хотелось бы при прерывании трогать стек пользователя, и вообще ходить в память. Мы как-то уже обсуждали на Гитхабе: https://github.com/besm6/mesm6/issues/3#issuecomment-475087151

Есть идея ввести для режима прерываний/экстракодов отдельный набор регистров K[1]...K[15]. В режиме пользователя (после ВЫПР) возможны обращения только к M[1]...M[15]. При переключении в режим прерываний обращения идут к регистрам K[1]...K[15]. Из режима прерываний можно читать-писать регистры пользователя командами ITA/ATI, обращаясь к ним как к регистрам K[17]...K[31].

Преимущества:

Обработчики прерывания имеют отдельный стек, задаваемый регистром K[15].

Не надо упрятывать регистры в стеке. Ускоряется обработка прерываний. Достаточно упрятать сумматор и РМР.

Не нужны дополнительные регистры для сохранения информации о прерывании. Например, прерванный счётчик команд PC прячется в K[1], регистр режимов пользователя - в K[2], исполнительный адрес экстракода - в K[3].

[spamsink]

Если нет приписки, то память всё равно общая, нет смысла возиться с дополнительным полным набором регистров. Ускорять обработку прерываний на несколько команд такой ценой тоже неясно, имеет ли смысл. А вот сделать теневой K[15], действительно, хорошо бы.

[x86128]

Перенесу сюда из темы на гитхаб.

Что делать с текущим К1 при вызове вложенного экстракода?

Можно сделать Экстракоды так чтобы они всегда выталкивали полный текущий PC_next по адресу [K15--], а команда ВЫПР возвращалась на [++K15]. При необходимости, программное выталкивание К2, К3 прописать в "соглашении о программных вызовах".

[spamsink]

Так нужно было! Не зря же System Verilog придумали. $signed уже все должны уметь синтезировать за столько-то лет существования System Verilog.

В БЭСМ-6 хитрость: умножение на 2 разряда делается за полтакта благодаря тому, что есть защелки по обоим фронтам тактового сигнала, поэтому произведение двигается вправо на 4 разряда за такт (в формулах АУ это видно). Но нам спешить особо некуда, можно и по 2 разряда за такт.

Кстати, сейчас флаг sticky правильно отражает необходимость округления для сложения, и сравнение rmr с нулем в STATE_ROUND нужно только для умножения. Когда умножение будет делаться пошагово, можно будет устанавливать sticky по ходу дела.

В скрипте для сложения есть ошибка: округление нужно делать, если в процессе нормализации вправо РМР когда-либо был ненулевым, даже если в конце концов все единицы из него уехали.

[spamsink]

Я пользовался пятничной версией тестов, они все продолжали работать. :) И 12 миллионов тактов всё ещё хватало для двух циклов теста АУ.

[spamsink]

Я всё же за простую и понятную архитектуру, максимально приближенную к БЭСМ-6. Раз мы разрешаем вложенные экстракоды (или прерывания в режиме экстракода), то упрятывание регистров всё равно понадобится, и проще делать его всегда программно, не умножая сущности.

Напомню, что стек в БЭСМ-6 растёт в сторону увеличения адресов, и 15-й регистр указывает на первую свободную ячейку стека. Поэтому push - это присваивание mem[M15++], а pop - это чтение из mem[--M15].

[vak]

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

[spamsink]

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

[spamsink]

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

[spamsink]

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

There are 10 levels of combinational cells

Total LUT area: 52

[vak]

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

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

[vak]

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

[spamsink]

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

[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

[vak]

Дополнительный набор регистров удобно иметь, чтобы не заниматься записью регистров в стек при входе в прерывание, и восстановлением потом. Хотелось бы писать обработчики экстракодов прямо на Паскале, с минимальной обвязкой.

[vak]

Экстракоды внутри экстракодов можно сделать, но по жизни они не особо нужны, ведь всегда можно просто вызвать нужную функцию через VJM, переход с возвратом.

[vak]

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

[spamsink]

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

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

[vak]

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

[spamsink]

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

[x86128]

Хотя вот действительно. Если основной язык для платформы это паскаль, то лучше сделать теневую копию М регистров, как предлагает Сергей, что позволит писать обработчики прерываний на паскале без изменений компилятора. Если будет рантайм, то вызывать всякие печати на экран(терминал), синусы и косинусы через VJM, а не через Э*. Сами же КОПы экстракодов зарезервировать для каких-то инструкций которых нет в БЭСМ6, но будут в системе на чипе МЭСМ6.

Есть мысль, чтобы процессор ходил в память через арбитр как в БЭСМ6, что позволит реализовать подсистемы блочного ввода/вывода с SD-карты, Ethernet (через шилд от ардуины), UART (протокол похожий на SLIP). Обращение к регистрам ввода/вывода сделать через команду УВВ (033), запрет/разрешение прерываний по маске через РЕГ 002.

[x86128]

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

[spamsink]

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

[x86128]

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

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

[vak]

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

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

[vak]

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

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

[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, а разница в количестве лутов, видимо, или из-за деталей реализации умножителя, или из-за того, что они более агрессивно реплицируют именно логику, а не регистры.