nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Мучаем 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. В этот раз - ни строчки верилога - оставим на вкусное!




Сначала немного про округление. Если мы просто "отрежем" старшие 16 бит от полного ответа, то получим округление "вниз", что не есть хорошо. Если предварительно прибавить к 32-битному ответу 0x 0000 8000 (т.е 1/2 от цены того разряда, до которого округляем), а только потом взять старшие 16 бит - то получим округление "до ближайшего целого". Оно не идеально - Кнут предложил бы "округление банкира", когда в точности 0,5 округляется до ближайшего чётного числа - но мне кажется, что в нашем случае это перебор! Такое происходит в среднем 1 раз из 65536, и мы каждый раз округлим вверх, тогда как по "округлению банкира" примерно в половине случаев произойдёт округление "вниз", т.е лишь в 1 случае из 131072 (менее 1/1000 %) результат будет отличаться. Впрочем, можно и реализовать, посмотреть, насколько оно усложнит модуль :)

Но пока что будем считать, что для округления мы попросту инициализировали аккумулятор не нулями, а значением 0x 0000 8000 (это не усложняет модуль ВООБЩЕ, триггеру пофиг, как инициализироваться!), потом стали накапливать в нём результат и, наконец, взяли лишь 16 старших бит - и такой вариант будет для нас эталонным.

Итак: можно ли упростить себе задачу и не считать все 32 бита результата, прежде чем провести округление? Да, можно обойтись 31 битом :) Действительно, младший бит равен единице, если младшие биты обоих операндов равны единице, и никакого переноса из него произойти не может при всём желании! Другими словами, младший бит - это самый угол "параллелограмма", который образуется, когда мы умножаем числа в столбик, поэтому на верхние 16 бит он повлиять не способен. (это не так, если использовать "округление банкира" - тогда и его мы обязаны посчитать!)

А вот если срезать аккумулятор хотя бы до 30 бит, то в 1 случае из 262144 мы будем ошибаться на единичку! Приведём пример подобного поведения для 8-битных чисел. Помножим 255 на 127. Ответ: 32 385 (в hex оно выглядит так: FF * 7F = 7E81). Округлённое до 8 бит значение - 127. Попробуем теперь помножить их "в столбик", но без двух последних разрядов:
        11111111
      x 01111111
        ---------
        11111111 
       11111111      
      11111111      
     11111111         
    11111111         
   11111111        
  11111111        
------------------
0111111001111100    

(цифры, отмеченные красным, не поместились в аккумулятор и были проигнорированы)

Теперь прибавим 0x0080 для правильного округления:
 01111110,01111100
+00000000,10000000
--------------------
 01111110,11111100


Теперь "обрезаем" дробную часть - и получается 126, а вовсе даже не 127, как в прошлый раз!

Так что если мы страдаем перфекционизмом в плане "ни упустить ни доли процента точности, и ни в коем случае не получить статистически смещённый результат", то упростить перемножитель не особенно получится!

Попробуем более прагматичный подход: само по себе округление до 16 бит уже ограничивает нам точность примерно до 0,29 от цены младшего разряда (корень из 1/12 - таково среднекв. значение ошибки, когда мы идеально округлили числа, равномерно распределённые на числовой прямой). Если из-за уменьшенной ширины аккумулятора будет возникать дополнительная ошибка в 0,132 от цены младшего разряда, то полная ошибка возрастёт не более чем на 10% (если они независимы друг от друга - кажется, что так оно и есть. В самом худшем случае 100% корреляции, будет не +10%, а +46%, тоже не так уж фатально, но думаю величина 10% куда ближе к истине!) - это вполне допустимо "для всех практических применений". В конце концов, если хочется существенно повысить точность, то нужно увеличивать число бит в конечном результате, иначе всё равно далеко не уедешь!

На графике в начале поста мы видим: чтобы среднеквадратичная ошибка составила не более 0,132 от ц.м.р, нам хватит аккумулятора шириной в 23 бита. При этом среднее значение ошибки ("постоянное смещение") составляет -0,0117 от ц.м.р, т.е всегда, если происходит ошибка, мы получаем значение на единицу меньше, чем надо, и происходит так 1 раз из 85.

Кажется, что всё хорошо, 23 бит вполне достаточно. Но хочется проверить ещё одну вещь - а не нарушаются ли у нас фундаментальные законы, такие как коммутативность умножения? Когда мы смотрим на умножение в столбик, и на то, как мы начинаем "обрубать" младшие биты, уверенность в коммутативности немножко пропадает...

Особенно после прочтения книги The End of Error: Unum Computing Джона Густафсона, где он приводит пример суперкомпьютера Cray-1, у которого для экономии "железа" упростили аппаратный перемножитель 64-битных чисел с плавающей точкой (48 бит мантиссы) настолько, что коммутативность умножения перестала соблюдаться, A×B≠B×A !

Надо отдать должное Сеймуру: данная особенность работы была хорошо документирована в руководстве по эксплуатации:




Что интересно, в дальнейшем этот суперкомпьютер всё-таки заставили соблюдать коммутативность, причём сделали это весьма своеобразным способом: прежде чем приступить к умножению, два операнда A, B сравнивали, и если A > B, меняли их местами!

Поковыряемся немножко "ручками" - попробуем найти произведение чисел 23 и 42, условно "отрезав" последние 4 разряда.
23 = 0101112,
42 = 1010102,

       010111
     * 101010
 -------------
      010111  
    010111   
  010111      
--------------
 001111000110,



       101010
    *  010111
-------------
       101010
      101010
     101010
   101010
--------------
 001111000110


Области, которые обрезаются (выделены красным), кажутся не особенно похожими друг на друга, но дают один и тот же результат в обеих случаях. А если записать умножение целиком, включая нулевые строки, то потихоньку становится понятно - цифры там одни и те же, только немножко в другом порядке:

       010111
     * 101010
 -------------
       000000
      010111  
     000000
    010111   
   000000
  010111      
--------------
 001111000110,



       101010
    *  010111
-------------
       101010
      101010
     101010
    000000
   101010
--------------
 001111000110


И это не совпадение. Если взять множители B = ....b3b2b1b0 и C = ....c3c2c1c0, то "обрезаемый" угол будет выглядеть так при умножении B на C:

и вот так при умножении C на B:


И так будет каждый раз, когда мы будем срезать "ровно", по вертикали!

То есть, главной ошибкой в CRAY-1 было не то, что они "пожадничали", а в том что сделали это слишком уж неаккуратно, вместо того, чтобы отпилить лишний кусок строго по уровню, они вырвали ломоть вообще непонятно как. До сих пор не вполне понимаю, чем это обусловлено, но видать были у них на то причины.

Получается, что приближённое умножение у нас всегда будет коммутировать, какую бы ширину аккумулятора мы не брали. Так что я всерьёз рассматриваю возможность немножечко сэкономить и применить 23-битный аккумулятор для перемножения 16-битных чисел. Впрочем, сделаем и наиболее "честную" реализацию, вплоть до округления банкира. Пока места хватает - пусть живёт :) Если же совсем всё заполним - начнём срезать углы, буквально.


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

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

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

  • Огари разговаривают

    Сегодня по пути на работу встретил огарей прямо в Лосином острове, на берегу Яузы. Эти были на удивление бесстрашны, занимались своими делами, не…

  • Мартовское велосипедное

    Продолжаю кататься на работу и с работы на велосипеде, а также в РКК Энергию и на дачу. Хотя на две недели случился перерыв, очередная поломка,…

  • Очень запоздало о лыжах

    Давненько (с 16 февраля) не писал о лыжах, хотя каждую неделю катался. Первый раз - на Гремячий и назад, с разведкой нового пути к маленькому…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 4 comments