Мучаем 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 ЛЭ. Последний результат меня очень сильно удивил - мне казалось, что накладные расходы будут очень велики, так поначалу и было, пока к концу дня меня не осенило :) Скорее всего, изобрёл очередной велосипед, но всё равно приятно!
Начнём с более простого варианта.
Интерфейс у перемножителя в любом случае будет один и тот же, благодаря чему можно будет один легко заменить на другой, в случае чего:
module CheapUnsignedMult16 (input clk,
input start,
input [15:0] B,
input [15:0] C,
output finished,
output [15:0] Q);
Как всегда, подаём на B и C числа, которые хотим перемножить, и в то же время - единичку на start. К следующему такту они "защёлкнутся" - и начнётся умножение.
В конце концов на Q зафиксируется результат работы и будет оставаться там, пока мы снова не запустим перемножитель. В первый такт, когда данные на выходе становятся правильными, появляется единичка на выходе finished.
Кроме того, можно начать умножение новой пары чисел, не закончив предыдущего - старые значения будут "выкинуты", а новые будут посчитаны корректно.
Далее, вводим параметр - ширину аккумулятора:
parameter AccWidth = 23;
Собственно, все варианты с "упрощённым округлением" будут достигаться с помощью этого модуля, надо лишь варьировать параметр. Модуль корректно синтезируется, если задавать значения от 17 и выше (при 16 или меньше всё скорее всего накроется медным тазом, но это в любом случае нафиг не надо!). Больше 31 задавать можно, но бессмысленно - результат от этого уже не станет точнее.
Поставим наш счётчик - как ни странно, он фактически "отрезан" от остальной схемы и просто-напросто отсчитывает 17 тактов, чтобы вовремя подать сигнал finished.
wire [4:0] State;
//5'b00000 is Idle
//5'b01111 is start
//5'b11111 is finished state
wire IsIdle = (~State[4])&(~State[3]);
lpm_counter counter (
.clock (clk),
.cnt_en (~IsIdle),
.sset (start),
.q (State),
.cout (finished) );
defparam
counter.lpm_direction = "UP",
counter.lpm_port_updown = "PORT_UNUSED",
counter.lpm_type = "LPM_COUNTER",
counter.lpm_width = 5,
counter.lpm_svalue = 5'b01111;
Как обычно, мы не влезли в 4-битный счётчик, поэтому поставили 5-битный. Проверить, что мы в "режиме ожидания" очень легко благодаря огромной "прорехе" в наших состояниях - из 32 задействовано лишь 18.
Окончание работы появляется на выводе переноса cout (Carry Out) счётчика. Счёт разрешён везде, кроме режима ожидания, а при подаче импульса start мы перепрыгиваем в состояние 01111, и уже оттуда начинаем "шагать" к финишу.
Далее рассмотрим наше "вычислительное устройство", оно описывается на удивление компактно:
//data path
reg [15:0] CSR = 1'b0; //shift register for 2nd operand
reg [AccWidth - 2 : 0] BSR = 1'b0; //senior is not needed after all
reg [AccWidth - 1 : 0] Acc = 1'b0; //but here it's needed all right
always @(posedge clk) begin
CSR <= start? C : CSR << 1;
BSR <= start? B << (AccWidth - 17) : BSR >> 1;
Acc <= start? 1'b1 << (AccWidth - 17) : CSR[15]? Acc + BSR : Acc;
end
assign Q = Acc[AccWidth - 1: AccWidth - 16];
Итак, мы вводим 16-битный регистр CSR (C Shift Register) - в начале работы в него заносится второй операнд и начинает на каждом шаге сдвигаться на единичку влево. Старший разряд мы используем, чтобы решить: прибавлять ли к аккумулятору очередное значение сдвигового регистра BSR, или не надо. Таким образом мы "умножаем очередную строку" на текущий бит второго операнда. По окончании работы регистр "сам собой" окажется нулевым, поэтому значение на выходе меняться перестанет.
Первый операнд мы помещаем в сдвиговый регистр BSR (B Shift Register), его ширина на единицу меньше ширины аккумулятора, поскольку в процессе работы в аккумуляторе может произойти перенос, и только таким образом у нас появится старший бит. После начала работы мы на каждом такте осуществляем сдвиг вправо на единичку. Опять же, по окончанию работы этот регистр автоматически "очистится" и будет оставаться нулевым, пока мы не запустим умножение по-новой.
И наконец, у нас есть аккумулятор Acc шириной (внезапно!) AccWidth. В начале работы мы сразу же заносим в него половинку младшего разряда, чтобы "не терять времени попусту". Затем на каждом шагу он либо будет хранить своё значение, либо будет прибавлять BSR. К концу работы нам достаточно будет взять старшие 16 бит этого аккумулятора - это и будет ответ, округлённый "до ближайшего целого".
Запишем код модуля целиком:
module CheapUnsignedMult16 (input clk, input start, input [15:0] B, input [15:0] C, output finished, output [15:0] Q);
parameter AccWidth = 23; //pretty decent performance (rms error = 0.108 of LSB, increases overall error from rounding to 16 bit just by 10%)
//it MUST be greater than 16, otherwise it doesn't synthesize properly (and you surely don't want such an ACC which discards one bit just to begin with!)
//state machine
wire [4:0] State;
//5'b00000 is Idle
//5'b01110 is start
//5'b11111 is finished state
wire IsIdle = (~State[4])&(~State[3]);
lpm_counter counter (
.clock (clk),
.cnt_en (~IsIdle),
.sset (start),
.q (State),
.cout (finished) );
defparam
counter.lpm_direction = "UP",
counter.lpm_port_updown = "PORT_UNUSED",
counter.lpm_type = "LPM_COUNTER",
counter.lpm_width = 5,
counter.lpm_svalue = 5'b01111;
//data path
reg [15:0] CSR = 1'b0; //shift register for 2nd operand
reg [AccWidth - 2 : 0] BSR = 1'b0; //senior is not needed after all
reg [AccWidth - 1 : 0] Acc = 1'b0; //but here it's needed all right
always @(posedge clk) begin
CSR <= start? C : CSR << 1;
BSR <= start? B << (AccWidth - 17) : BSR >> 1;
Acc <= start? 1'b1 << (AccWidth - 17) : CSR[15]? Acc + BSR : Acc;
end
assign Q = Acc[AccWidth - 1: AccWidth - 16];
endmodule
Покажем результаты симуляции:
Первый раз мы подаём на вход числа FFFF и 7FFF. Результатом точного умножения стало бы 7FFE 8001, после добавления 8000 (для округления до ближайшего целого) мы получаем 7FFF 0001, и отбрасывая младшие биты, должны были бы получить 7FFF. Но как видно на рисунке, данный перемножитель, используя аккумулятор в 23 бита, ошибается в итоге на единичку - его ответ 7FFE. Это и есть один из тех довольно-таки редких случаев (1 раз из 85), когда эта ошибка происходит.
Второй раз мы умножаем 8000 на 0001. Результатом точного умножения становится 0000 8000 (неожиданность!), т.е ровно одна вторая, если мы принимаем младшие 16 бит за дробную часть. По правилу округления банкира, мы бы получили ноль (поскольку ближайшие целые числа - ноль и один, и мы выбираем чётное). Но по нашему более простому правилу, мы прибавляем 8000, получая 0001 0000, и отсекая дробную часть, получаем единицу! Именно это происходит в нашем модуле.
Просто поменяв параметр, поставив его равным AccWidth = 31, мы получаем второй вариант умножителя - он получает совершенно точный ответ (хоть и использует на 1 бит меньше), если точным считать результат округления "до ближайшего целого". Вот результаты симуляции:
На первом примере мы теперь получаем 7FFF - это правильный ответ. На втором - снова получаем единицу, и это тоже правильный ответ при заданном правиле округления. Всё работает :)
Теперь напишем модуль умножителя, который использует "округление банкира".
Заголовок, как мы и говорили, отличается только именем:
module BankerRoundingMultiplier (input clk, input [15:0] B, input [15:0] C, input start, output [15:0] Q, output finished);
В этот раз счётчик всё-таки немножко управляет работой схемы - он указывает, когда провести округление. Так что в кои-то веки мы можем гордо назвать его командоаппаратом :). Вот он:
//state machine
localparam sIdle = 5'b00000;
//large gap here
localparam sStart = 5'b01110;
localparam sRounding = 5'b11101; //Acc still didn't reach result, but ALUout has it already, so we decide: do we need to add 1/2?
localparam sFinish = 5'b11111;
wire [4:0] State;
wire IsIdle = (~State[4])&(~State[3]);
wire IsRoundingStep = (State[3:0] == 4'b1101);
lpm_counter counter (
.clock (clk),
.cnt_en (~IsIdle),
.sset (start),
.q (State),
.cout (finished) );
defparam
counter.lpm_direction = "UP",
counter.lpm_port_updown = "PORT_UNUSED",
counter.lpm_type = "LPM_COUNTER",
counter.lpm_width = 5,
counter.lpm_svalue = sStart;
Мы стартуем на одно состояние раньше в сравнении с прошлым модулем, поскольку ещё один такт уйдёт на округление.
Шагом округления мы назвали шаг за 2 такта до финиша - именно к концу этого шага на выходе АЛУ сформируется результат умножения двух чисел (но в аккумулятор он "защёлкнется" лишь к следующему такту!), и мы можем сразу же решить, какое новое значение занести в регистр BSR - ноль или единицу. К следующему такту (11110) это значение появляется в регистре BSR, и ещё один такт занимает прибавление этого значения к аккумулятору. Поскольку состояния 01110 у нас нет (при старте мы перескакиваем с 00000 сразу на 011101), то для проверки, что мы действительно находимся на шаге округления, достаточно лишь младших 4 бит счётчика.
Теперь рассмотрим "вычислительный модуль", он и здесь достаточно прост, как это ни странно:
//data path
reg [15:0] CSR = 1'b0; //shift register for 2nd operand
reg [30:0] BSR = 1'b0; //senior is not needed after all
reg [31:0] Acc = 1'b0; //but here it's needed all right
wire [31:0] ALUout = Acc + BSR;
always @(posedge clk) begin
BSR <= start? {B, 15'b0} : IsRoundingStep? {30'b0, ALUout[16]} : BSR >> 1;
CSR <= start? C : {CSR[14:0], 1'b1};
Acc <= start? 32'h00007FFF : CSR[15]? ALUout : Acc;
end
assign Q = Acc[31:16];
Как и раньше, у нас есть 16-битный регистр CSR для второго операнда, но логика его работы самую малость поменялась. Теперь он не просто осуществляет сдвиг влево на единичку, но и заносит единицу в младший разряд. Таким образом, когда все 16 бит данных выйдут за его пределы, он заполнится сплошными единицами, и продолжит оставаться в таком состоянии до следующей операции умножения. Благодаря этому, ещё один такт после окончания умножения он "позволит" аккумулятору обновить своё значение - а это может нам понадобиться (в 1 случае из 131072) для округления!
Регистр BSR у нас в этот раз строго 31-битный, в начале работы в него заносится значение первого операнда, и затем на каждом шаге производится сдвиг вправо. Но когда остаётся два такта до финиша, мы заносим в него либо единицу, либо ноль (чаще всего). На следующем такте это значение "защёлкивается" в регистре, и ещё через такт оно оказывается прибавленным к аккумулятору. Заметим, что старшие 15 бит аккумулятора и так к этому моменту должны получаться нулевыми, а вот в младших 16 разрядах всё ещё может лежать "что угодно", поэтому мы и должны так "грубо" его целиком переписать!
Наш аккумулятор самых честных правил - 32-битный. При начале умножения мы заносим в него значение 0x7FFF - то есть на единицу меньше, чем раньше. По сути, поведение для дробных частей от 0 до 0x7FFF никак не изменилось - в этом случае будет округление вниз. При дробных частях от 0x8001 до 0xFFFF будет округление вверх - как и раньше. А вот наше любимое значение 0x8000 раньше округлялось вверх, а теперь будет округляться вниз. Если только не прибавить в конце ещё ровно единичку!
И тут мы делаем финт ушами! Мы просто берём и помещаем в младший бит регистра BSR 16-й бит с выхода АЛУ (сумматора)! Мотивация такова. Лишь в одном случае добавление единицы к самому младшему разряду аккумулятора может повлиять на результат (прибавить единицу к младшему разряду выхода) - если там уже лежит 0xFFFF. А это происходит только в одном случае - если в результате умножения мы получили 1/2 в дробной части. Поэтому остаётся лишь проверить - чётное ли у нас число в "целой части"? Если в 16-м бите с выхода АЛУ лежит ноль - значит число уже чётное, т.е округлять надо "вниз", а для этого надо просто оставить всё "как есть". Если же там единица, значит нужно округлять вверх. В итоге, такое вот простое дополнение обеспечивает нам выполнение задачи.
И дополнительный бонус: даже если мы занесём единицу в регистр BSR на этапе округления, к следующему такту она будет сдвинута вправо и исчезнет (будет вытеснена), давая нулевой регистр. Таким он и будет оставаться, пока мы не начнём новое умножение. Поэтому, хоть работа сумматора разрешена (регистр CSR продолжает выдавать нам единицы!), на выходе умножителя по-прежнему будет держаться правильный ответ! Кроме того, в таком "установившемся режиме" во всём модуле (это касается всех вариантов, рассмотренных здесь) не будет совершаться изменения логических уровней где бы то ни было, а это означает практически нулевое энергопотребление.
Запишем код модуля целиком:
//the most accurate one. But in order to get this accuracy, we need 32 bit accumulator and 32 bit SR
//also, one additional step of banker's rounding is implemented.
module BankerRoundingMultiplier (input clk, input [15:0] B, input [15:0] C, input start, output [15:0] Q, output finished);
//state machine
localparam sIdle = 5'b00000;
//large gap here
localparam sStart = 5'b01110;
localparam sRounding = 5'b11101; //Acc still didn't reach result, but ALUout has it already, so we decide: do we need to add 1/2?
localparam sFinish = 5'b11111;
wire [4:0] State;
wire IsIdle = (~State[4])&(~State[3]);
wire IsRoundingStep = (State[3:0] == 4'b1101);
lpm_counter counter (
.clock (clk),
.cnt_en (~IsIdle),
.sset (start),
.q (State),
.cout (finished) );
defparam
counter.lpm_direction = "UP",
counter.lpm_port_updown = "PORT_UNUSED",
counter.lpm_type = "LPM_COUNTER",
counter.lpm_width = 5,
counter.lpm_svalue = sStart;
//data path
reg [15:0] CSR = 1'b0; //shift register for 2nd operand
reg [30:0] BSR = 1'b0; //senior is not needed after all
reg [31:0] Acc = 1'b0; //but here it's needed all right
wire [31:0] ALUout = Acc + BSR;
always @(posedge clk) begin
BSR <= start? {B, 15'b0} : IsRoundingStep? {30'b0, ALUout[16]} : BSR >> 1;
CSR <= start? C : {CSR[14:0], 1'b1};
Acc <= start? 32'h00007FFF : CSR[15]? ALUout : Acc;
end
assign Q = Acc[31:16];
endmodule
Вот, собственно и всё. Как ни странно, этот код вовсе не так страшен, как мне казалось поначалу. По сравнению с вариантом "простого округления" и 31-битным аккумулятором, у нас добавляется всего 4 ЛЭ, или 3,3% (!!!).
Покажем результаты симуляции для тех же чисел, что и для других модулей:
В кои-то веки 1/2 округлилась до нуля. В начале поста показано умножение 0x8000 на 0x0003, что даёт нам 1,5, и они округляются вверх, до 2.
Какой из них применять на практике? Будете смеяться, но в данном случае я рекомендую самый сложный из них - потому что жадность до ЛЭ - ничто по сравнению с жадностью до получения максимально возможной точности при той разрядности, с которой мы работаем! Ну а если совсем будет не хватать места внутри ПЛИС - мы знаем, где можно выкинуть 28 ЛЭ.
Часть 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 ЛЭ. Последний результат меня очень сильно удивил - мне казалось, что накладные расходы будут очень велики, так поначалу и было, пока к концу дня меня не осенило :) Скорее всего, изобрёл очередной велосипед, но всё равно приятно!
Начнём с более простого варианта.
Интерфейс у перемножителя в любом случае будет один и тот же, благодаря чему можно будет один легко заменить на другой, в случае чего:
module CheapUnsignedMult16 (input clk,
input start,
input [15:0] B,
input [15:0] C,
output finished,
output [15:0] Q);
Как всегда, подаём на B и C числа, которые хотим перемножить, и в то же время - единичку на start. К следующему такту они "защёлкнутся" - и начнётся умножение.
В конце концов на Q зафиксируется результат работы и будет оставаться там, пока мы снова не запустим перемножитель. В первый такт, когда данные на выходе становятся правильными, появляется единичка на выходе finished.
Кроме того, можно начать умножение новой пары чисел, не закончив предыдущего - старые значения будут "выкинуты", а новые будут посчитаны корректно.
Далее, вводим параметр - ширину аккумулятора:
parameter AccWidth = 23;
Собственно, все варианты с "упрощённым округлением" будут достигаться с помощью этого модуля, надо лишь варьировать параметр. Модуль корректно синтезируется, если задавать значения от 17 и выше (при 16 или меньше всё скорее всего накроется медным тазом, но это в любом случае нафиг не надо!). Больше 31 задавать можно, но бессмысленно - результат от этого уже не станет точнее.
Поставим наш счётчик - как ни странно, он фактически "отрезан" от остальной схемы и просто-напросто отсчитывает 17 тактов, чтобы вовремя подать сигнал finished.
wire [4:0] State;
//5'b00000 is Idle
//5'b01111 is start
//5'b11111 is finished state
wire IsIdle = (~State[4])&(~State[3]);
lpm_counter counter (
.clock (clk),
.cnt_en (~IsIdle),
.sset (start),
.q (State),
.cout (finished) );
defparam
counter.lpm_direction = "UP",
counter.lpm_port_updown = "PORT_UNUSED",
counter.lpm_type = "LPM_COUNTER",
counter.lpm_width = 5,
counter.lpm_svalue = 5'b01111;
Как обычно, мы не влезли в 4-битный счётчик, поэтому поставили 5-битный. Проверить, что мы в "режиме ожидания" очень легко благодаря огромной "прорехе" в наших состояниях - из 32 задействовано лишь 18.
Окончание работы появляется на выводе переноса cout (Carry Out) счётчика. Счёт разрешён везде, кроме режима ожидания, а при подаче импульса start мы перепрыгиваем в состояние 01111, и уже оттуда начинаем "шагать" к финишу.
Далее рассмотрим наше "вычислительное устройство", оно описывается на удивление компактно:
//data path
reg [15:0] CSR = 1'b0; //shift register for 2nd operand
reg [AccWidth - 2 : 0] BSR = 1'b0; //senior is not needed after all
reg [AccWidth - 1 : 0] Acc = 1'b0; //but here it's needed all right
always @(posedge clk) begin
CSR <= start? C : CSR << 1;
BSR <= start? B << (AccWidth - 17) : BSR >> 1;
Acc <= start? 1'b1 << (AccWidth - 17) : CSR[15]? Acc + BSR : Acc;
end
assign Q = Acc[AccWidth - 1: AccWidth - 16];
Итак, мы вводим 16-битный регистр CSR (C Shift Register) - в начале работы в него заносится второй операнд и начинает на каждом шаге сдвигаться на единичку влево. Старший разряд мы используем, чтобы решить: прибавлять ли к аккумулятору очередное значение сдвигового регистра BSR, или не надо. Таким образом мы "умножаем очередную строку" на текущий бит второго операнда. По окончании работы регистр "сам собой" окажется нулевым, поэтому значение на выходе меняться перестанет.
Первый операнд мы помещаем в сдвиговый регистр BSR (B Shift Register), его ширина на единицу меньше ширины аккумулятора, поскольку в процессе работы в аккумуляторе может произойти перенос, и только таким образом у нас появится старший бит. После начала работы мы на каждом такте осуществляем сдвиг вправо на единичку. Опять же, по окончанию работы этот регистр автоматически "очистится" и будет оставаться нулевым, пока мы не запустим умножение по-новой.
И наконец, у нас есть аккумулятор Acc шириной (внезапно!) AccWidth. В начале работы мы сразу же заносим в него половинку младшего разряда, чтобы "не терять времени попусту". Затем на каждом шагу он либо будет хранить своё значение, либо будет прибавлять BSR. К концу работы нам достаточно будет взять старшие 16 бит этого аккумулятора - это и будет ответ, округлённый "до ближайшего целого".
Запишем код модуля целиком:
module CheapUnsignedMult16 (input clk, input start, input [15:0] B, input [15:0] C, output finished, output [15:0] Q);
parameter AccWidth = 23; //pretty decent performance (rms error = 0.108 of LSB, increases overall error from rounding to 16 bit just by 10%)
//it MUST be greater than 16, otherwise it doesn't synthesize properly (and you surely don't want such an ACC which discards one bit just to begin with!)
//state machine
wire [4:0] State;
//5'b00000 is Idle
//5'b01110 is start
//5'b11111 is finished state
wire IsIdle = (~State[4])&(~State[3]);
lpm_counter counter (
.clock (clk),
.cnt_en (~IsIdle),
.sset (start),
.q (State),
.cout (finished) );
defparam
counter.lpm_direction = "UP",
counter.lpm_port_updown = "PORT_UNUSED",
counter.lpm_type = "LPM_COUNTER",
counter.lpm_width = 5,
counter.lpm_svalue = 5'b01111;
//data path
reg [15:0] CSR = 1'b0; //shift register for 2nd operand
reg [AccWidth - 2 : 0] BSR = 1'b0; //senior is not needed after all
reg [AccWidth - 1 : 0] Acc = 1'b0; //but here it's needed all right
always @(posedge clk) begin
CSR <= start? C : CSR << 1;
BSR <= start? B << (AccWidth - 17) : BSR >> 1;
Acc <= start? 1'b1 << (AccWidth - 17) : CSR[15]? Acc + BSR : Acc;
end
assign Q = Acc[AccWidth - 1: AccWidth - 16];
endmodule
Покажем результаты симуляции:
Первый раз мы подаём на вход числа FFFF и 7FFF. Результатом точного умножения стало бы 7FFE 8001, после добавления 8000 (для округления до ближайшего целого) мы получаем 7FFF 0001, и отбрасывая младшие биты, должны были бы получить 7FFF. Но как видно на рисунке, данный перемножитель, используя аккумулятор в 23 бита, ошибается в итоге на единичку - его ответ 7FFE. Это и есть один из тех довольно-таки редких случаев (1 раз из 85), когда эта ошибка происходит.
Второй раз мы умножаем 8000 на 0001. Результатом точного умножения становится 0000 8000 (неожиданность!), т.е ровно одна вторая, если мы принимаем младшие 16 бит за дробную часть. По правилу округления банкира, мы бы получили ноль (поскольку ближайшие целые числа - ноль и один, и мы выбираем чётное). Но по нашему более простому правилу, мы прибавляем 8000, получая 0001 0000, и отсекая дробную часть, получаем единицу! Именно это происходит в нашем модуле.
Просто поменяв параметр, поставив его равным AccWidth = 31, мы получаем второй вариант умножителя - он получает совершенно точный ответ (хоть и использует на 1 бит меньше), если точным считать результат округления "до ближайшего целого". Вот результаты симуляции:
На первом примере мы теперь получаем 7FFF - это правильный ответ. На втором - снова получаем единицу, и это тоже правильный ответ при заданном правиле округления. Всё работает :)
Теперь напишем модуль умножителя, который использует "округление банкира".
Заголовок, как мы и говорили, отличается только именем:
module BankerRoundingMultiplier (input clk, input [15:0] B, input [15:0] C, input start, output [15:0] Q, output finished);
В этот раз счётчик всё-таки немножко управляет работой схемы - он указывает, когда провести округление. Так что в кои-то веки мы можем гордо назвать его командоаппаратом :). Вот он:
//state machine
localparam sIdle = 5'b00000;
//large gap here
localparam sStart = 5'b01110;
localparam sRounding = 5'b11101; //Acc still didn't reach result, but ALUout has it already, so we decide: do we need to add 1/2?
localparam sFinish = 5'b11111;
wire [4:0] State;
wire IsIdle = (~State[4])&(~State[3]);
wire IsRoundingStep = (State[3:0] == 4'b1101);
lpm_counter counter (
.clock (clk),
.cnt_en (~IsIdle),
.sset (start),
.q (State),
.cout (finished) );
defparam
counter.lpm_direction = "UP",
counter.lpm_port_updown = "PORT_UNUSED",
counter.lpm_type = "LPM_COUNTER",
counter.lpm_width = 5,
counter.lpm_svalue = sStart;
Мы стартуем на одно состояние раньше в сравнении с прошлым модулем, поскольку ещё один такт уйдёт на округление.
Шагом округления мы назвали шаг за 2 такта до финиша - именно к концу этого шага на выходе АЛУ сформируется результат умножения двух чисел (но в аккумулятор он "защёлкнется" лишь к следующему такту!), и мы можем сразу же решить, какое новое значение занести в регистр BSR - ноль или единицу. К следующему такту (11110) это значение появляется в регистре BSR, и ещё один такт занимает прибавление этого значения к аккумулятору. Поскольку состояния 01110 у нас нет (при старте мы перескакиваем с 00000 сразу на 011101), то для проверки, что мы действительно находимся на шаге округления, достаточно лишь младших 4 бит счётчика.
Теперь рассмотрим "вычислительный модуль", он и здесь достаточно прост, как это ни странно:
//data path
reg [15:0] CSR = 1'b0; //shift register for 2nd operand
reg [30:0] BSR = 1'b0; //senior is not needed after all
reg [31:0] Acc = 1'b0; //but here it's needed all right
wire [31:0] ALUout = Acc + BSR;
always @(posedge clk) begin
BSR <= start? {B, 15'b0} : IsRoundingStep? {30'b0, ALUout[16]} : BSR >> 1;
CSR <= start? C : {CSR[14:0], 1'b1};
Acc <= start? 32'h00007FFF : CSR[15]? ALUout : Acc;
end
assign Q = Acc[31:16];
Как и раньше, у нас есть 16-битный регистр CSR для второго операнда, но логика его работы самую малость поменялась. Теперь он не просто осуществляет сдвиг влево на единичку, но и заносит единицу в младший разряд. Таким образом, когда все 16 бит данных выйдут за его пределы, он заполнится сплошными единицами, и продолжит оставаться в таком состоянии до следующей операции умножения. Благодаря этому, ещё один такт после окончания умножения он "позволит" аккумулятору обновить своё значение - а это может нам понадобиться (в 1 случае из 131072) для округления!
Регистр BSR у нас в этот раз строго 31-битный, в начале работы в него заносится значение первого операнда, и затем на каждом шаге производится сдвиг вправо. Но когда остаётся два такта до финиша, мы заносим в него либо единицу, либо ноль (чаще всего). На следующем такте это значение "защёлкивается" в регистре, и ещё через такт оно оказывается прибавленным к аккумулятору. Заметим, что старшие 15 бит аккумулятора и так к этому моменту должны получаться нулевыми, а вот в младших 16 разрядах всё ещё может лежать "что угодно", поэтому мы и должны так "грубо" его целиком переписать!
Наш аккумулятор самых честных правил - 32-битный. При начале умножения мы заносим в него значение 0x7FFF - то есть на единицу меньше, чем раньше. По сути, поведение для дробных частей от 0 до 0x7FFF никак не изменилось - в этом случае будет округление вниз. При дробных частях от 0x8001 до 0xFFFF будет округление вверх - как и раньше. А вот наше любимое значение 0x8000 раньше округлялось вверх, а теперь будет округляться вниз. Если только не прибавить в конце ещё ровно единичку!
И тут мы делаем финт ушами! Мы просто берём и помещаем в младший бит регистра BSR 16-й бит с выхода АЛУ (сумматора)! Мотивация такова. Лишь в одном случае добавление единицы к самому младшему разряду аккумулятора может повлиять на результат (прибавить единицу к младшему разряду выхода) - если там уже лежит 0xFFFF. А это происходит только в одном случае - если в результате умножения мы получили 1/2 в дробной части. Поэтому остаётся лишь проверить - чётное ли у нас число в "целой части"? Если в 16-м бите с выхода АЛУ лежит ноль - значит число уже чётное, т.е округлять надо "вниз", а для этого надо просто оставить всё "как есть". Если же там единица, значит нужно округлять вверх. В итоге, такое вот простое дополнение обеспечивает нам выполнение задачи.
И дополнительный бонус: даже если мы занесём единицу в регистр BSR на этапе округления, к следующему такту она будет сдвинута вправо и исчезнет (будет вытеснена), давая нулевой регистр. Таким он и будет оставаться, пока мы не начнём новое умножение. Поэтому, хоть работа сумматора разрешена (регистр CSR продолжает выдавать нам единицы!), на выходе умножителя по-прежнему будет держаться правильный ответ! Кроме того, в таком "установившемся режиме" во всём модуле (это касается всех вариантов, рассмотренных здесь) не будет совершаться изменения логических уровней где бы то ни было, а это означает практически нулевое энергопотребление.
Запишем код модуля целиком:
//the most accurate one. But in order to get this accuracy, we need 32 bit accumulator and 32 bit SR
//also, one additional step of banker's rounding is implemented.
module BankerRoundingMultiplier (input clk, input [15:0] B, input [15:0] C, input start, output [15:0] Q, output finished);
//state machine
localparam sIdle = 5'b00000;
//large gap here
localparam sStart = 5'b01110;
localparam sRounding = 5'b11101; //Acc still didn't reach result, but ALUout has it already, so we decide: do we need to add 1/2?
localparam sFinish = 5'b11111;
wire [4:0] State;
wire IsIdle = (~State[4])&(~State[3]);
wire IsRoundingStep = (State[3:0] == 4'b1101);
lpm_counter counter (
.clock (clk),
.cnt_en (~IsIdle),
.sset (start),
.q (State),
.cout (finished) );
defparam
counter.lpm_direction = "UP",
counter.lpm_port_updown = "PORT_UNUSED",
counter.lpm_type = "LPM_COUNTER",
counter.lpm_width = 5,
counter.lpm_svalue = sStart;
//data path
reg [15:0] CSR = 1'b0; //shift register for 2nd operand
reg [30:0] BSR = 1'b0; //senior is not needed after all
reg [31:0] Acc = 1'b0; //but here it's needed all right
wire [31:0] ALUout = Acc + BSR;
always @(posedge clk) begin
BSR <= start? {B, 15'b0} : IsRoundingStep? {30'b0, ALUout[16]} : BSR >> 1;
CSR <= start? C : {CSR[14:0], 1'b1};
Acc <= start? 32'h00007FFF : CSR[15]? ALUout : Acc;
end
assign Q = Acc[31:16];
endmodule
Вот, собственно и всё. Как ни странно, этот код вовсе не так страшен, как мне казалось поначалу. По сравнению с вариантом "простого округления" и 31-битным аккумулятором, у нас добавляется всего 4 ЛЭ, или 3,3% (!!!).
Покажем результаты симуляции для тех же чисел, что и для других модулей:
В кои-то веки 1/2 округлилась до нуля. В начале поста показано умножение 0x8000 на 0x0003, что даёт нам 1,5, и они округляются вверх, до 2.
Какой из них применять на практике? Будете смеяться, но в данном случае я рекомендую самый сложный из них - потому что жадность до ЛЭ - ничто по сравнению с жадностью до получения максимально возможной точности при той разрядности, с которой мы работаем! Ну а если совсем будет не хватать места внутри ПЛИС - мы знаем, где можно выкинуть 28 ЛЭ.