nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

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

Часть 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, 'h2F, потом мучительно "разгонял" их в частях 'h31, 'h33 и 'h34, а самого очевидного решения в упор не видел.

ВНЕЗАПНО оказывается, что можно сделать 16-битный умножитель на 57 .. 73 ЛЭ, вместо 118 ЛЭ, которые у нас получались в части 'h24, при том, что старшие 16 бит мы получаем ТОЧНО ТАКИЕ же, как при вычислении честного 32-битного результата с последующим округлением до ближайшего целого, и такой умножитель легко и непринуждённо работает на 80 МГц на моей медленной ПЛИС.




Вдолбил себе в голову, что "аккумулятор" должен быть неподвижным, с перспективой на "умножитель с накоплением", который может посчитать выражения вроде a0 + b0c0 + b1c1 + ..., не округляя промежуточные результаты, округлив только ОДИН РАЗ ПОД САМЫЙ КОНЕЦ. (такого рода операции называют FMA - Fused Multiply-Add, тогда как MAC - Multiply-ACcumulate - более широкий термин, допускающий округление промежуточных результатов)

Если же нам это не нужно, а хватит самого обычного умножителя, то самый эффективный способ сделать это - двигать второй множитель вправо, и двигать аккумулятор вправо, тогда как первый множитель "стоит на месте". Тогда для умножения 16-битных чисел нам хватит 16-битного сумматора и 16-битного аккумулятора, при том что ответ будет ТОЧНО ТАКОЙ ЖЕ, как при использовании аккумулятора полной длины (32 бита) и округлении "до ближайшего целого"! За счёт уменьшенного вдвое сумматора, нам не придётся волноваться о задержках распространения - схема будет работать даже на самых медленных ПЛИС.

Действительно, в каждый момент времени мы прибавляем лишь 16-битное число, и результатом этого становится 17-битное число. Но младший бит больше не будет использован в дальнейших вычислениях, так что его можно отбросить сразу же!

Вот обычная запись в столбик.
       010111
     * 101010
 -------------
       000000
      010111 
     000000
    010111
   000000
  010111      
--------------
 001111000110


А делать мы будем так: первый множитель сидит неизменный, назовём его B.
Второй множитель назовём CSR ('C' Shift Register), он на каждом шаге будет сдвигаться вправо.
Аккумулятор назовём Acc (внезапно). Для приведённого примера мы начнём со следующих значений:
B   =  010111,
CSR =  101010,
Acc = 1000000;


Единица в старшем разряде нужна для округления "до ближайшего целого".

Пошёл первый шаг умножения. Смотрим на младший разряд CSR, т.е CSR[0]. Раз он нулевой, то мы просто сдвигаем аккумулятор вправо. Также мы всегда сдвигаем CSR вправо. Получаем:
B   =  010111,
CSR =  010101,
Acc = 0100000;


Теперь CSR[0] = 1, поэтому мы складываем B и Acc, сдвинутый вправо на единичку. И конечно, сдвигаем вправо CSR:
B   =  010111,
CSR =  001010,
Acc =  010000 +
       010111 =
    = 0100111;


CSR[0] = 0, поэтому просто сдвигаем вправо CSR и Acc:
B   =  010111,
CSR =  000101,
Acc = 0010011;


CSR[0] = 1, поэтому сдвигаем вправо CSR и складываем B с аккумулятором, сдвинутым вправо:
B   =  010111,
CSR =  000010,
Acc =  001001 +
       010111 = 
      0100000;


CSR[0] = 0, просто сдвигаем вправо CSR и Acc:
B   =  010111,
CSR =  000001,
Acc = 0010000;


И последний бит: CSR[0] = 1, сдвигаем вправо CSR и складываем B с аккумулятором, сдвинутым вправо:
B   =  010111,
CSR =  000000,
Acc =  001000 +
       010111 = 
      0011111;


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

Ответ: 001111. Всё верно, точный (12-битный) результат умножения: 001111000110, и при округлении он даст именно 001111.

Наконец, приведём код модуля:
module SimplestMul16unsign (input clk, input start, input [15:0] B, input [15:0] C,
			    output finished, output [15:0] Q);

parameter LatchB = 1; //if B keeps valid value through full cycle, we can drop input latch, saving 16 LE

//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] Breg = 1'b0;
always @(posedge clk) if (start)
	Breg <= B;
wire [15:0] Bval = (LatchB == 1)? Breg : B;

reg [15:0] CSR = 1'b0; //'C' shift register
always @(posedge clk)
	CSR <= start? C : CSR >> 1;

reg [16:0] Acc = 1'b0; //shifting accumulator

wire [16:0] ALUout;

lpm_add_sub ALU (
		.dataa (Acc[16:1]), //shifted it right
		.datab (Bval),
		.cin (1'b0),
		.result (ALUout[15:0]),
		.cout (ALUout[16]));
defparam
        ALU.lpm_direction = "ADD",
        ALU.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=NO",
	ALU.lpm_representation = "UNSIGNED",
	ALU.lpm_type = "LPM_ADD_SUB",
	ALU.lpm_width = 16;		
							
always @(posedge clk)
	Acc <= start? 17'h1_00_00 : CSR[0]? ALUout : Acc >> 1;

assign Q = Acc[16:1];

endmodule

Что интересно, мы определили 17-битный аккумулятор, но умный синтезатор сам понял, что на младший бит "никто не претендует", и удаляет его без тени сомнения.

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

В таком случае, и регистр Breg будет "выброшен на помойку" хитрым синтезатором.

В итоге, мы получаем 57 логических элементов (ЛЭ), если LatchB = 0, и 73 ЛЭ, если LatchB = 1.

Никто не мешает нам реализовать данный умножитель с "округлением банкира" (сейчас у нас округление до ближайшего целого). Для этого надо инициализировать аккумулятор не единицей в старшем разряде (17'h1_00_00), а нулём и всеми остальными единицами (17'h0_FF_FF), а затем отслеживать, все ли "уходящие в небытие" младшие разряды аккумулятора единичные, написав нечто вроде:
  LsbAreOnes <= start? 1'b1 : LsbAreOnes & Acc[0];

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

На скриншоте в начале поста показаны результаты симуляции - мы получаем те же ответы, что и раньше на умножителе с 31-битным аккумулятором. Но если "старый" умножитель по окончании работы держал ответ на выходе неизменным, то здесь правильный ответ хранится в течении ровно одного такта, пока finished = 1.

Если при "неподвижном" аккумуляторе финишный результат сохранялся "автоматом", пока мы не начнём следующие вычисления (регистр CSR заполнялся нулями, и результат больше не менялся), то здесь он продолжит сдвигаться вправо, пока не станет нулевым. И остановить его мы не можем - не хватает входов, ведь на один вход ГФ (LUT) мы подаём значение с соседнего регистра (провести обычный сдвиг вправо, если CSR[0]=0), на второй - значение с сумматора (если CSR[0]=1), на третий - сигнал с CSR[0], чтобы выбрать между первыми двумя, и на четвёртый - сигнал обнуления, чтобы правильно инициализировать аккумулятор. Можно, правда, сделать сброс асинхронным, а лишний выход применить, чтобы заставить аккумулятор хранить финальное значение. А вот сделать параллельную загрузку для операции Acc = A + B * C мы уже не сможем при всём желании, для этого нужно ДВА лишних входа!

Но для конкретной задачи, просто посчитать произведение, это весьма недурственный модуль! Простой как кирпич, компактный и быстрый.


Наверное, я всех уже задолбал перемножителями (тем более, что сейчас уже трудно найти ПЛИС, в которой не было бы аппаратных перемножителей), но в следующей части расскажу об одном элегантном решении - УРАВНОВЕШЕННОМ ЧЕТВЕРИЧНОМ умножителе, который при таком же количестве ЛЭ (может, чуточку больше) осуществляет умножение за вдвое меньшее количество тактов!

А потом возьмёмся, наконец, за картинки...
Tags: ПЛИС, математика, работа, странные девайсы
Subscribe

  • Так есть ли толк в ковариационной матрице?

    Задался этим вопросом применительно к своему прибору чуть более 2 недель назад. Рыл носом землю с попеременным успехом ( раз, два, три, четыре),…

  • Big Data, чтоб их ... (4)

    Наконец-то стряхнул пыль с компьютерной модели сближения, добавил в неё код, чтобы мы могли определить интересующие нас точки, и выписать…

  • Потёмкинская деревня - 2

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 3 comments