Category: финансы

Category was added automatically. Read all entries about "финансы".

Мучаем 5576ХС4Т - часть 'h34 - ускоренные перемножители

Часть 0 - покупаем, паяем, ставим драйвера и софт
Часть 1 - что это вообще за зверь?
Часть 2 - наша первая схема!
Часть 3 - кнопочки и лампочки
Часть 4 - делитель частоты
Часть 5 - подавление дребезга кнопки
Часть 6 - заканчиваем кнопочки и лампочки
Часть 7 - счетчики и жаба
Часть 8 - передатчик UART
Часть 9 - Hello, wolf!
Часть 'hA - приёмник UART
Часть 'hB - UART и жаба
Часть 'hC - полудуплексный UART.
Часть 'hD - МКО (МКИО, Mil-Std 1553) для бедных, введение.
Часть 'hE - приёмопередатчик МКО "из подручных материалов" (в процессе)
Часть 'hF - модуль передатчика МКО
Часть 'h10 - передатчик сообщений МКО
Часть 'h20 - работа с АЦП ADC124s051
Часть 'h21 - преобразование двоичного кода в двоично-десятичный (BCD)
Часть 'h22 - Bin2Bcd с последовательной выдачей данных
Часть 'h23 - перемножитель беззнаковых чисел с округлением
Часть 'h24 - перемножитель беззнаковых чисел, реализация
Часть 'h25 - передаём показания АЦП на компьютер
Часть 'h26 - работа над ошибками (быстрый UART)
Часть 'h27 - PNG и коды коррекции ошибок CRC32
Часть 'h28 - передатчик изображения PNG
Часть 'h29 - принимаем с ПЛИС изображение PNG
Часть 'h2A - ZLIB и коды коррекции ошибок Adler32
Часть 'h2B - ускоряем Adler32
Часть 'h2C - формирователь потока Zlib
Часть 'h2D - передаём сгенерированное PNG-изображение
Часть 'h2E - делим отрезок на равные части
Часть 'h2F - знаковые умножители, тысячи их!
Часть 'h30 - вычислитель множества Мандельброта
Часть 'h31 - ускоренные сумматоры
Часть 'h32 - ускоренные счётчики (делаем часы)
Часть 'h33 - ускоряем ВСЁ
Часть 'h34 - ускоренные перемножители
Часть 'h35 - умножители совсем просто
Часть 'h36 - уравновешенный четверичный умножитель


В части 'h31 мы разобрались, что делать, если обычная запись
assign C = A + B;


вызывает critical warning - timing requirements not met, при использовании довольно "длинных" (32 бит) чисел на медленных (speed grade "-3") кристаллах, если при всём при том мы надеемся работать на относительно высоких частотах.

А именно, мы предложили применить Carry Select Adder (сумматор с выбором переноса) - довольно уродское решение, но единственное из всех "ускоренных схем", которое действительно даёт выигрыш на ПЛИС.

Когда мы попытались реализовать умножитель, основанный на данном сумматоре (часть 'h33), обнаружилось, что даже 32-битный аккумулятор не получается, и нам приходится уменьшить его ширину до 28 бит. Кроме того, пришлось сделать вход сброса асинхронным, что немножко нервирует. И можно было забыть о входе синхронной загрузки, который позволил бы превратить умножитель в умножитель-накопитель (MAC, Multiply-ACcumulate).

Совсем всё плохо стало при реализации "генератора множества Мандельброта", где два умножителя-накопителя должны стоять "рядышком", а вслед за ними стоят два сумматора, вычисляющие X+Y и X-Y (см. часть 'h30). как оказалось, когда в ограниченном объёме (чтобы не удлинять пути) нужно разместить 8 сумматоров по 16 бит каждый, компоновщик (Place&Route) начинает сходить с ума - иногда ему вообще не удаётся разместить схему (no fit), и даже если удаётся - её временнЫе характеристики оказываются ужасными...

На самом деле, "ускоренные" (способные работать на высокой тактовой частоте) перемножители реализуются гораздо проще - практически "бесплатно", т.е за повышенную тактовую частоту нам не нужно расплачиваться ни увеличенным количеством ЛЭ, ни увеличенным количеством тактов! (разве что совсем чуть-чуть)



Просто не нужно зацикливаться на осуществлении сложения ЗА ОДИН ТАКТ - и внезапно всё получится.
Collapse )

Подобным образом можно реализовать и знаковые умножители.

Напомним, что на современных ПЛИС (в том числе отечественных, серии 5578ТС) есть аппаратные перемножители 18х18, осуществляющие операцию всего за один такт. Описываемый здесь материал предназначен для тех, кому нужно реализовать хоть сколько-нибудь быстрое умножение на более старых ПЛИС. Впрочем, кое-какие "хитрости", описанные здесь, пригодятся и для новых ПЛИС. Например, как "бесплатно" сделать округление "до ближайшего целого", или и вовсе "округление банкира". Слишком уж многие просто отрубают младшие биты, и сразу же на этом теряют точность вдвое!

Мучаем 5576ХС4Т - часть 'h2F - знаковые умножители, тысячи их!

Часть 0 - покупаем, паяем, ставим драйвера и софт
Часть 1 - что это вообще за зверь?
Часть 2 - наша первая схема!
Часть 3 - кнопочки и лампочки
Часть 4 - делитель частоты
Часть 5 - подавление дребезга кнопки
Часть 6 - заканчиваем кнопочки и лампочки
Часть 7 - счетчики и жаба
Часть 8 - передатчик UART
Часть 9 - Hello, wolf!
Часть 'hA - приёмник UART
Часть 'hB - UART и жаба
Часть 'hC - полудуплексный UART.
Часть 'hD - МКО (МКИО, Mil-Std 1553) для бедных, введение.
Часть 'hE - приёмопередатчик МКО "из подручных материалов" (в процессе)
Часть 'hF - модуль передатчика МКО
Часть 'h10 - передатчик сообщений МКО
Часть 'h20 - работа с АЦП ADC124s051
Часть 'h21 - преобразование двоичного кода в двоично-десятичный (BCD)
Часть 'h22 - Bin2Bcd с последовательной выдачей данных
Часть 'h23 - перемножитель беззнаковых чисел с округлением
Часть 'h24 - перемножитель беззнаковых чисел, реализация
Часть 'h25 - передаём показания АЦП на компьютер
Часть 'h26 - работа над ошибками (быстрый UART)
Часть 'h27 - PNG и коды коррекции ошибок CRC32
Часть 'h28 - передатчик изображения PNG
Часть 'h29 - принимаем с ПЛИС изображение PNG
Часть 'h2A - ZLIB и коды коррекции ошибок Adler32
Часть 'h2B - ускоряем Adler32
Часть 'h2C - формирователь потока Zlib
Часть 'h2D - передаём сгенерированное PNG-изображение
Часть 'h2E - делим отрезок на равные части
Часть 'h2F - знаковые умножители, тысячи их!
Часть 'h30 - вычислитель множества Мандельброта
Часть 'h31 - ускоренные сумматоры
Часть 'h32 - ускоренные счётчики (делаем часы)
Часть 'h33 - ускоряем ВСЁ
Часть 'h34 - ускоренные перемножители
Часть 'h35 - умножители совсем просто
Часть 'h36 - уравновешенный четверичный умножитель


В частях 'h23 - 'h24 мы довольно подробно рассмотрели умножение беззнаковых целых чисел: как более компактные версии с аккумулятором ограниченной длины (например, 23 бита для умножения 16-битных чисел), так и наиболее честную с 32-битным аккумулятором и округлением банкира. Кстати, даже при использовании аппаратного перемножителя 18×18 бит, которые присутствуют в более новых ПЛИС, часть этого материала будет полезна, поскольку эти перемножители дают 36-битный результат, а округлить его - уже забота разработчика!

Сейчас рассмотрим умножение чисел со знаком - в нём есть свои "подводные камни", по счастью, не очень большие.



Collapse )

В следующей части мы целиком соберём "вычислитель" для множества Мандельброта.

Мучаем 5576ХС4Т - часть 'h24 - перемножитель беззнаковых чисел, реализация

Часть 0 - покупаем, паяем, ставим драйвера и софт
Часть 1 - что это вообще за зверь?
Часть 2 - наша первая схема!
Часть 3 - кнопочки и лампочки
Часть 4 - делитель частоты
Часть 5 - подавление дребезга кнопки
Часть 6 - заканчиваем кнопочки и лампочки
Часть 7 - счетчики и жаба
Часть 8 - передатчик UART
Часть 9 - Hello, wolf!
Часть 'hA - приёмник UART
Часть 'hB - UART и жаба
Часть 'hC - полудуплексный UART.
Часть 'hD - МКО (МКИО, Mil-Std 1553) для бедных, введение.
Часть 'hE - приёмопередатчик МКО "из подручных материалов" (в процессе)
Часть 'hF - модуль передатчика МКО
Часть 'h10 - передатчик сообщений МКО
Часть 'h20 - работа с АЦП ADC124s051
Часть 'h21 - преобразование двоичного кода в двоично-десятичный (BCD)
Часть 'h22 - Bin2Bcd с последовательной выдачей данных
Часть 'h23 - перемножитель беззнаковых чисел с округлением
Часть 'h24 - перемножитель беззнаковых чисел, реализация
Часть 'h25 - передаём показания АЦП на компьютер
Часть 'h26 - работа над ошибками (быстрый UART)
Часть 'h27 - PNG и коды коррекции ошибок CRC32
Часть 'h28 - передатчик изображения PNG
Часть 'h29 - принимаем с ПЛИС изображение PNG
Часть 'h2A - ZLIB и коды коррекции ошибок Adler32
Часть 'h2B - ускоряем Adler32
Часть 'h2C - формирователь потока Zlib
Часть 'h2D - передаём сгенерированное PNG-изображение
Часть 'h2E - делим отрезок на равные части
Часть 'h2F - знаковые умножители, тысячи их!
Часть 'h30 - вычислитель множества Мандельброта
Часть 'h31 - ускоренные сумматоры
Часть 'h32 - ускоренные счётчики (делаем часы)
Часть 'h33 - ускоряем ВСЁ
Часть 'h34 - ускоренные перемножители
Часть 'h35 - умножители совсем просто
Часть 'h36 - уравновешенный четверичный умножитель


В прошлой части мы обсуждали умножение двух 16-битных чисел без знака, с последующим округлением 32-битного результата до 16 бит. Оказалось, что если мы хотим провести "округление банкира" (именно его следует применять согласно IEEE 754), то ничего не остаётся, как "честно" получить 32-битный результат и округлять его, сэкономить на ширине аккумулятора не получится!

Если нас устраивает обычное округление "до ближайшего целого", которое дробную часть 0,5 (в точности) всегда округляет до единицы, то можно обойтись 31 битами в аккумуляторе - последний бит нам погоды не сделает. Только тогда наши 16 бит будут посчитаны "безошибочно".

Наконец, если потребовать, чтобы среднеквадратичная ошибка после округления возросла не более чем на 10% по сравнению с "эталонным методом", то нам хватит 23-битного аккумулятора.

Реализуем все 3 варианта, чтобы посмотреть - "а стоит ли игра свеч?".

Нарушая интригу, скажу: вариант с 23-битным аккумулятором занимает 94 ЛЭ и выполняется за 17 тактов, вариант с 31-битным аккумулятором - 118 (и выполняется столько же), а самый точный 32-битный вариант с округлением банкира выполняется на один такт дольше и занимает 122 ЛЭ. Последний результат меня очень сильно удивил - мне казалось, что накладные расходы будут очень велики, так поначалу и было, пока к концу дня меня не осенило :) Скорее всего, изобрёл очередной велосипед, но всё равно приятно!


Collapse )

Какой из них применять на практике? Будете смеяться, но в данном случае я рекомендую самый сложный из них - потому что жадность до ЛЭ - ничто по сравнению с жадностью до получения максимально возможной точности при той разрядности, с которой мы работаем! Ну а если совсем будет не хватать места внутри ПЛИС - мы знаем, где можно выкинуть 28 ЛЭ.

Мучаем 5576ХС4Т - часть 'h23 - перемножитель беззнаковых чисел с округлением

Часть 0 - покупаем, паяем, ставим драйвера и софт
Часть 1 - что это вообще за зверь?
Часть 2 - наша первая схема!
Часть 3 - кнопочки и лампочки
Часть 4 - делитель частоты
Часть 5 - подавление дребезга кнопки
Часть 6 - заканчиваем кнопочки и лампочки
Часть 7 - счетчики и жаба
Часть 8 - передатчик UART
Часть 9 - Hello, wolf!
Часть 'hA - приёмник UART
Часть 'hB - UART и жаба
Часть 'hC - полудуплексный UART.
Часть 'hD - МКО (МКИО, Mil-Std 1553) для бедных, введение.
Часть 'hE - приёмопередатчик МКО "из подручных материалов" (в процессе)
Часть 'hF - модуль передатчика МКО
Часть 'h10 - передатчик сообщений МКО
Часть 'h20 - работа с АЦП ADC124s051
Часть 'h21 - преобразование двоичного кода в двоично-десятичный (BCD)
Часть 'h22 - Bin2Bcd с последовательной выдачей данных
Часть 'h23 - перемножитель беззнаковых чисел с округлением
Часть 'h24 - перемножитель беззнаковых чисел, реализация
Часть 'h25 - передаём показания АЦП на компьютер
Часть 'h26 - работа над ошибками (быстрый UART)
Часть 'h27 - PNG и коды коррекции ошибок CRC32
Часть 'h28 - передатчик изображения PNG
Часть 'h29 - принимаем с ПЛИС изображение PNG
Часть 'h2A - ZLIB и коды коррекции ошибок Adler32
Часть 'h2B - ускоряем Adler32
Часть 'h2C - формирователь потока Zlib
Часть 'h2D - передаём сгенерированное PNG-изображение
Часть 'h2E - делим отрезок на равные части
Часть 'h2F - знаковые умножители, тысячи их!
Часть 'h30 - вычислитель множества Мандельброта
Часть 'h31 - ускоренные сумматоры
Часть 'h32 - ускоренные счётчики (делаем часы)
Часть 'h33 - ускоряем ВСЁ
Часть 'h34 - ускоренные перемножители
Часть 'h35 - умножители совсем просто
Часть 'h36 - уравновешенный четверичный умножитель


Немножко поразмышляем по поводу умножения целых чисел. Понятно, что если мы умножаем два 16-битных числа и заносим результат в 32 бита, то ответ получается ТОЧНЫЙ. Это попросту "умножение в столбик", там неоткуда возникнуть ошибке!

Но что, если нам нужен только 16-битный результат, округлённый до ближайшего целого? Можно ли для этого не считать все 32 бита и по прежнему получить все 16 бит ТОЧНЫМИ (ровно такими же, как при получении 32-битного ответа и последующем округлении)?

Ответ был для меня немного неожиданным, хотя задним числом - очевидным :) Под катом - жуткий брутфорс всех возможных умножений 16-битных чисел, а также про некоммутативное умножение Cray-1. В этот раз - ни строчки верилога - оставим на вкусное!



Collapse )

Poll #2091773 Округление чисел в ПЛИС

Как бы вы реализовывали округление?

"Вниз" (простое отсекание ненужных бит)
1(33.3%)
"До ближайшего целого" (прибавить 0,5, затем отсечь)
1(33.3%)
"Округление банкира" (специально рассмотреть случай 0,5 в дробной части)
1(33.3%)