nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Мучаем 5576ХС4Т - часть 'h36 - уравновешенный четверичный умножитель

Часть 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 - уравновешенный четверичный умножитель

Рассмотрим решение, позволяющее почти что "бесплатно" сократить необходимое для умножения число тактов почти что вдвое.

Можно сказать, что мы преобразуем второй множитель из двоичной системы в уравновешенную четверичную, и затем делаем умножение по 1 четверичному разряду (т.е. по двум двоичным разрядам) за раз!

Уравновешенная четверичная система не сравнится по своей элегантности с уравновешенной троичной (надеюсь когда-нибудь всё-таки убедить мир, что БПФ должно быть именно таким), она немножко "перекошена", поскольку использует цифры 1 (минус единица), 0, 1 и 2, но тоже, как оказывается, может пригодиться!




Итак, представим второй множитель для начала в обычной четверичной системе. Это просто: нужно сгруппировать по два двоичных разряда, они и дадут искомые цифры:
002 = 04,
012 = 14,
102 = 24,
112 = 34.


К примеру,
14110 = 100011012 = (10) (00) (11) (01)2 = 20314.


Мы могли бы проводить умножение двоичного числа на четверичное, прибавляя к аккумулятору либо 0, либо B, либо 2*B (сдвиг влево), либо 3*B (сдвиг влево + исходное), в зависимости от цифры в младшем разряде второго множителя, и таким образом обрабатывая по две "строки" за раз.

Увы, необходимость "иметь наготове" значение 3*B портит нам жизнь: для его вычисления нам требуется ещё один сумматор, а потом ещё и придётся каким-то образом мультиплексировать 3 значения в один регистр, для чего нужна ещё прорва ЛЭ (два входа указывают, какой из 4 вариантов выбрать. Затем ещё нужно 3 входа - исходное, сдвинутое, а также их сумму. Итого 5, значит нужно объединять по 2 ЛЭ в каждом бите через цепи каскадирования).

Но если вместо цифр 0, 1, 2, 3 использовать цифры 1 (минус единица), 0, 1 и 2, то внезапно всё встаёт на свои места!

Умножение на -1 - это очень просто - мы лишь должны инвертировать биты (заменить ноль на единицу и наоборот) и потом использовать вход cin (carry in) сумматора, чтобы дополнительно прибавить единичку.

Разберёмся для начала, как преобразовать число в четверичной записи в уравновешенную четверичную запись.

К счастью, мы не сильно торопимся: достаточно преобразовывать по одному четверичному разряду (2 двоичным) за один такт, начиная с младшего.

Мы будем использовать регистр, хранящий перенос с младших разрядов. Он инициализируется нулём.

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

Числа 0, 1, 2 мы оставляем без изменений (т.е 002, 012, 102).
Когда мы видим число 3, мы превращаем его в 11, т.е в текущем разряде будет стоять "минус единица", и мы делаем перенос в следующий разряд.
Действительно,
114 = 1 * 4 + (-1) * 1 = 3


В двоичном представлении, эта "минус единица" по прежнему будет записываться как 11, т.е фактически мы не меняем этот разряд, лишь вводим бит переноса.

Наконец, число 4 (т.е 112 в текущем разряде, плюс перенос с младших разрядов) мы превращаем в 104, что логично.

Преобразуем число
14110 = 100011012 = (10) (00) (11) (01)2 = 20314.

в уравновешенную четверичную систему счисления.

Начинаем с младшего разряда: "1". Переноса у нас пока нет, поэтому оставляем единицу как есть. Пока результат: 20314.

Приступаем к следующему разряду: "3". Переноса снова нет, тройку мы преобразуем в 11, то есть текущие 2 бита мы не меняем и устанавливаем бит переноса. Результат: 20114 + cin.

Следующий разряд: "0". Прибавляем к нему бит переноса, получаем 1. Записываем единицу, и бит переноса: 0. Результат: 21114.

Наконец, последний разряд 2. Переноса нет, поэтому оставляем двойку "как есть".

Окончательный результат: 21114.

Иногда у нас может появиться старший разряд, под него надо зарезервировать место, точнее, такт вычислений, с местом в сдвиговом регистре проблем нет :)

Напишем код, реализующий данную процедуру:
reg [15:0] CSR = 1'b0; //'C' shift register with correction (quaternary into balanced quaternary)
reg carryBit = 1'b0;

always @(posedge clk) begin
	CSR[0] <= start? C[0] : CSR[2]^carryBit;
	CSR[1] <= start? C[1] : CSR[3]^(CSR[2] & carryBit);
	carryBit <= start? C[0]&C[1] : CSR[3] & (CSR[2] | carryBit);
	CSR[15:2] <= start? C[15:2] : {2'b0, CSR[15:4]};
end

wire DoNegation = CSR[1] & CSR[0];


То есть, у нас уже был сдвиговый регистр CSR для второго множителя, нам надо было лишь подправить логику работы младших двух бит, ну и сделать сдвиг на 2 вправо на каждом шаге вместо привычного нам сдвига на единицу. Бит переноса с младших разрядов мы вынуждены сформировать ещё в процессе загрузки исходного множителя C, чтобы не терять ещё один такт. Тут это делается просто - если младшие два бита оба единичные ("тройка"), перенос сформируется.

Вот как он работает (мы временно подсоединили выход регистра CSR к выходу умножителя Q, а провод DoNegate, требующий обратить знак числа - к выходу finished):


Для примера мы взяли число 0xF20D, посмотрим, как эта штука "переварится".
0xF20D = 1111 0010 0000 1101

Как только значение "защёлкнулось" в регистре, установилось значение DoNegate = 0 - действительно, мы сейчас изучаем младшие два бита, 01 = 14 - положительное число.

К следующему такту мы получаем значение
0x3C83 = 0011 1100 1000 0011

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

На этом шаге "зажигается" DoNegate, потому что 11 - это наше обозначение для минус единицы.

К следующему такту мы получаем значение
0x0F21 = 0000 1111 0010 0001

К следующему разряду (00) мы прибавили бит переноса, получив 01. Остальная часть - обычный сдвиговый регистр.

Далее идут довольно скучные шаги - просто сдвиги:
0x03C8 = 0000 0011 1100 1000,
0x00F2 = 0000 0000 1111 0010,
0x003C = 0000 0000 0011 1100,
0x000F = 0000 0000 0000 1111


К этому шагу у нас снова появился DoNegate = 1, поскольку в младшем разряде "минус единица", а также возникает бит переноса.

К следующему такту:
0x0000 = 0000 0000 0000 0000

к старшим двум единицам прибавился бит переноса, из-за чего они "перевернулись" до нуля. Кажется, что на этом работа завершена, но самое главное не утерять наш последний перенос. Он ещё не был включён в регистр CSR, а ждёт своего часа в регистре carryBit.

Жизненно важно сделать и ещё один такт:
0x0001 = 0000 0000 0000 0001

во время преобразования в уравновешенную четверичную форму у нас образовался ещё один разряд.

И на этом - всё, дальше заведомо будут идти лишь нули.

Мы обнаруживаем, что весь процесс сдвигов занял 9 тактов, что логично - в общем случае у нас получается именно 9 "уравновешенных четверичных" разрядов. Данный "кусочек" модуля перемножителя занимает 19 ЛЭ - всего на 3 больше, чем самый простой 16-битный сдвиговый регистр. Дополнительные 3 ЛЭ нужны для формирования и хранения бита переноса, и реализации логики CSR[1], где в 4 входа мы слегка не влезли (используются сигналы start, C[1], CSR[2], CSR[3], carryBit). Максимально допустимая частота (точнее, величина, обратная к задержки распространения сигнала от выхода регистра ко входу) - свыше 167 МГц, что и понятно - это вам не длинный сумматор с распространением переноса через все разряды!

Далее, нам нужно подготовить первый множитель для суммирования. Удобнее всего хранить "исходное" значение (а если нам гарантируют, что на входе B значение не будет меняться - то и хранить не надо), и на каждом шаге преобразовывать его и заносить в рабочий регистр Bwork. Это позволит сделать умножители, способные работать на весьма высокой тактовой частоте благодаря тому, что мы не пытаемся и выбрать одно из 4 значений, и просуммировать его с аккумулятором за один такт, в одном длинном комбинаторном пути.

Здесь необходимо обратить внимание на ширину регистра. Если исходный множитель имеет ширину 16 бит, то один лишний бит нам надо добавить, чтобы можно было сделать сдвиг влево на один. Затем, когда это значение прибавится к текущему значению аккумулятора, у нас может образоваться ещё один разряд. И ещё один мы добавим, чтобы можно было представлять отрицательные числа - итого 19 бит...

Приведём код:
parameter LatchB = 0; //if B keeps valid value through full cycle, we can drop input latch, saving 16 LE

reg [15:0] Breg = 1'b0;
always @(posedge clk) if (start)
	Breg <= B;
wire [15:0] Bval = (LatchB == 1)? Breg : B;

reg [18:0] Bwork = 1'b0;
reg rDoNegation = 1'b0;

always @(posedge clk) begin
	Bwork <= 	(CSR[1:0] == 2'b00)? 19'b0 :		 //zero (mul by 0)
			(CSR[1:0] == 2'b01)? {3'b000, Bval}  : //leave as is (mul by 1)
			(CSR[1:0] == 2'b10)? {2'b00, Bval, 1'b0}  : //multiply by 2
					     {3'b111, ~Bval} ; //negate (mul by -1), still +1 pending
	rDoNegation <= DoNegation;	//so it appears the same time as Bwork 
end


Мы опять добавили параметр LatchB - защёлкивать ли вход B - на дальнейшую работу это не влияет. И далее мы видим, как в регистр Bwork будет заноситься одно из 4 значений:


Увы, тут создаётся ещё одна задержка, но уж что поделать... А чтобы бит DoNegate, заставляющий сумматор прибавить ещё единичку, чтобы окончить взятие отрицательного числа (в дополнительном коде, чтобы сменить знак, мы должны инвертировать все биты, а потом ещё прибавить 1. К примеру, для числа 00 мы инвертируем биты, получая FF, потом прибавляем единицу, снова получая 00, поэтому 0 = -0. Для числа 01 мы инвертируем биты получая FE, затем прибавляем единицу, получая FF - для знакового байта это и есть "-1"), сработал в нужный момент, мы его тоже прогоняем через регистр,

Далее остаётся "прикрутить" аккумулятор, который должен просуммировать все значения Bwork. Он должен быть знаковым, поскольку у нас может накапливаться как большое отрицательное значение (подряд идущие "минус единицы"), так и большое положительное (подряд идущие двойки). По сути, он должен занимать те же 19 бит, а вот перенос нам не нужен - мы заранее знаем, что уместимся.

Вот код аккумулятора и сумматора:

reg z_start = 1'b0;
always @(posedge clk)
	z_start <= start; //this one controls Acc reset, need 1 clk delay
	
reg [18:0] Acc = 1'b0; //shifting accumulator

wire [18:0] ALUout;

lpm_add_sub ALU (
				.dataa ({Acc[18], Acc[18], Acc[18:2]}), //arithmetic shift right by 2
				.datab (Bwork),
				.cin (rDoNegation),
				.result (ALUout));
	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 = 19;		
							
always @(posedge clk)
	Acc <= z_start? 19'h2_00_00 : ALUout;

assign Q = Acc[15:0];


Нам пришлось задержать сброс сумматора на один такт, поскольку только после этого регистр Bwork "выходит на режим", до этого на его выходе может быть любой мусор.

Кроме того, мы ВНЕЗАПНО решили проигнорировать верхние 3 бита аккумулятора - это связано с одним дополнительным тактом (вдруг в процессе преобразования в уравн. четверич. появился ещё один разряд), который заставляет сдвинуть наш правильный ответ на 2 бита вправо. А ещё один бит и вовсе оказывается лишним - мы точно знаем, что к концу работы ответ должен получиться положительным, поэтому "бит знака" точно будет нулевым.

Наконец, приведём код всего модуля целиком - мы разобрали его весь, кроме счётчика тактов, который нужен для формирования сигнала finished. (Там всё просто: отсчитываем 11 тактов)

module BalQuatMUL16unsign (input clk, input start, input [15:0] B, input [15:0] C,
							output finished, output [15:0] Q);
							
parameter LatchB = 0; //if B keeps valid value through full cycle, we can drop input latch, saving 16 LE

//state machine
  wire [3:0] State;
  //4'b0000 is Idle
  //4'b0101 is start
  //4'b1111 is finished state (11th clock)
  wire IsIdle = (~State[3])&(~State[2]);
	
  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 = 4,
    counter.lpm_svalue = 4'b0101;


reg [15:0] CSR = 1'b0; //'C' shift register with correction (quaternary into balanced quaternary)
reg carryBit = 1'b0;

always @(posedge clk) begin
	CSR[0] <= start? C[0] : CSR[2]^carryBit;
	CSR[1] <= start? C[1] : CSR[3]^(CSR[2] & carryBit);
	carryBit <= start? C[0]&C[1] : CSR[3] & (CSR[2] | carryBit);
	CSR[15:2] <= start? C[15:2] : {2'b0, CSR[15:4]};
end

wire DoNegation = CSR[1] & CSR[0];

reg [15:0] Breg = 1'b0;
always @(posedge clk) if (start)
	Breg <= B;
wire [15:0] Bval = (LatchB == 1)? Breg : B;

reg [18:0] Bwork = 1'b0;
reg rDoNegation = 1'b0;

always @(posedge clk) begin
	Bwork <= 	(CSR[1:0] == 2'b00)? 19'b0 :		 //zero (mul by 0)
			(CSR[1:0] == 2'b01)? {3'b000, Bval}  : //leave as is (mul by 1)
			(CSR[1:0] == 2'b10)? {2'b00, Bval, 1'b0}  : //multiply by 2
					     {3'b111, ~Bval} ; //negate (mul by -1), still +1 pending
	rDoNegation <= DoNegation;						//so it appears the same time as Bwork 
end

reg z_start = 1'b0;
always @(posedge clk)
	z_start <= start; //this one controls Acc reset, need 1 clk delay
	
reg [18:0] Acc = 1'b0; //shifting accumulator

wire [18:0] ALUout;

lpm_add_sub ALU (
		.dataa ({Acc[18], Acc[18], Acc[18:2]}), //arithmetic shift right by 2
		.datab (Bwork),
		.cin (rDoNegation),
		.result (ALUout));
	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 = 19;		
							
always @(posedge clk)
	Acc <= z_start? 19'h2_00_00 : ALUout;

assign Q = Acc[15:0];
							
endmodule


Честно говоря, "на бумаге" оно выглядело красивее, чем "в железе".

Обычный последовательный умножитель получал результат за 17 тактов, этот - за 11 тактов, это всё же не в 2 раза, а лишь в 1,55. Да, умножение 32-битных чисел займёт вместо 33 тактов лишь 19, это уже ближе к двойке, но всё равно не она. Один такт съелся из-за возможного уширения второго множителя во время преобразования в ур. четв. запись, ещё один такт - потому что нужно подготовить очередное слагаемое, одно из 4 возможных.

Данный модуль (без защёлкивания множителя B) занимает 85 ЛЭ - в те же 1,5 раза больше, чем самый простой 16-битный умножитель. Правда, если мы всё-таки защёлкиваем B, это будет 101 ЛЭ против 73 ЛЭ - разница в 1,38 раза. При увеличении ширины множителей (скажем, при реализации 32-битного умножителя) разница становится не так заметна.

А поскольку вместо 16-битного сумматора нам пришлось поставить 19-битный, мы опять завалили Timing Analysis для своего любимого 5576ХС4Т, получив допустимую частоту 76 МГц при требуемой 80 МГц. С этим скорее всего можно побороться так или иначе, хоть бы даже "выбором переноса" (у нас сейчас на удивление свободный аккумулятор - использует всего 2 входа из 4!), или опять распилив сумматор на две части, с задержкой переноса между частями на один такт.

Не знаю только - надо ли?


UPD. Подозреваю, что по-настоящему "засиять" этот алгоритм должен при работе со знаковыми числами, поскольку умножение на (-1) больше не приведёт к расширению диапазона чисел, и поскольку в "простом" алгоритме тоже придётся вводить регистр, умеющий иногда инвертировать своё содержимое, чтобы правильно отработать последнюю строку. Впрочем, не проверял.

В ближайшее время займёмся оцифровкой изображений и их передачей на компьютер...
Tags: ПЛИС, математика, работа, странные девайсы, уравновешенное троичное БПФ
Subscribe

  • Нахождение двух самых отдалённых точек

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

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments