nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Мучаем 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), и даже если удаётся - её временнЫе характеристики оказываются ужасными...

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



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


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

Во варианте, показанном на рисунке, мы поделили общий сумматор на слегка неравные части - 9 бит мы обозвали "старшими" и 7 бит - "младшими", благодаря чему на последнем такте у нас перенос заведомо не будет сформирован, и мы не удлинили время выполнения!

К сожалению, здесь же виден и "подводный камень" - до сих пор мы использовали в умножителях два сдвиговых регистра, BSR ("B" shift register) шириной на один бит короче аккумулятора, и CSR ("C" shift register) шириной 16 бит. Младший бит CSR поступает на вход разрешения работы аккумулятора, тогда как сумматор всегда "на всякий случай" находит Acc + BSR. Таким образом, в конце такта мы "защёлкиваем" выражение Acc + BSR * CSR[0], а тем временем BSR сдвигается влево (как показано на рисунке, в нём хранится сдвинутый первый множитель), а CSR - вправо.

При такой реализации мы не сможем прибавить бит переноса строго НА СЛЕДУЮЩЕМ ТАКТЕ. Скорее, он будет добавлен в следующий раз, когда CSR[0] равен единице. Пример обратного показан на рисунке - когда во втором множителе нолик и мы "пропускаем строку", то и бит переноса проходит "мимо" этой строки, до следующей. Поскольку на этих "пропущенных строках" новые биты переноса образоваться не могут, то кажется, что всё в порядке.

Проблема лишь в одном - что, если на последней строке наш сумматор тоже будет "отключён"? Тогда у нас может оказаться бит переноса, который так и не добавили к результату! По счастью, поскольку значение регистров BSR и CSR нам больше не нужно после этого этапа, мы можем их немножко "подкорректировать" на предыдущем шаге. А именно: мы независимо не от чего занесём в CSR[0] единичку, чтобы суммирование произошло. Причём, если CSR[1] = 0 (т.е нижняя строка должна была быть нулевой), мы обнуляем BSR, чтобы ничего другого, кроме переноса, у нас не прибавлялось. По счастью, наши сдвиговые регистры были заметно "недогружены" логикой (они либо загружали значение, либо сдвигались на единичку), так что эта дополнительная функция может быть добавлена без увеличения числа ЛЭ и длины комбинаторных путей.

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

И наконец, когда нам нужен не 32-битный результат, а лишь 16-битный, округлённый до ближайшего целого (округление банкира пока что отставим в сторонку), то, как мы узнали в части 'h23, можно "выкинуть" самый младший бит аккумулятора, поскольку только с него никогда не будет сформирован перенос, т.е он никоим образом не сможет повлиять на финальный результат.

В итоге приходим к следующему модулю:

module CarryDelayUnsignedMult16 (input clk, input [15:0] B, input [15:0] C, input start, output [15:0] Q, output reg finished = 1'b0);

	parameter LatchStart = 0;
	reg rStart = 1'b0;
	wire uStart = (LatchStart == 1)? rStart : start;
	
//state machine
	wire [4:0] State;
	//5'b00000 is Idle
	//5'b10000 is start
	//5'b11101 is when we prepare reg for that "Get ready"
	//5'b11110 is "Get ready for last step!"
	//5'b11111 is "almost finished" state
	wire IsIdle = (~State[4]);
	wire AlmostFinished;
	wire GetReady = (State[3:0] == 4'b1101);
	reg rGetReady = 1'b0;	
	
	lpm_counter	counter (
				.clock (clk),
				.cnt_en (~IsIdle),
				.sset (uStart),
				.q (State),
				.cout (AlmostFinished) );
	defparam
		counter.lpm_direction = "UP",
		counter.lpm_port_updown = "PORT_UNUSED",
		counter.lpm_type = "LPM_COUNTER",
		counter.lpm_width = 5,
		counter.lpm_svalue = 5'b10000;
		

//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 [30 : 0] Acc = 1'b0; //ignoring LSB, because it can't have carry anyway
	
	wire [30 : 0] ALUout;

	//LSB adder, 14 bit long
	wire intCout;
	reg rCout = 1'b0;
	
	lpm_add_sub LSB (	.cin (1'b0),
				.dataa (Acc[13:0]),
				.datab (BSR[14:1]), //lsb of BSR is to shift it correctly, not lose this bit
				.cout (intCout),
				.result (ALUout[13:0]));
	defparam
		LSB.LPM_WIDTH = 14;
	
	//MSB adder, 16 bit long (senior bit of ACC through cout)

	lpm_add_sub MSB (	.cin (rCout),
				.dataa (Acc[29:14]),
				.datab (BSR[30:15]),
				.cout (ALUout[30]),
				.result (ALUout[29:14]));
	defparam
		MSB.LPM_WIDTH = 16;

	always @(posedge clk) begin
		CSR <= uStart? C : rGetReady? 1'b1 : CSR >> 1;
	
		BSR <= uStart? {15'b0, B}: (rGetReady & (~CSR[1]))? 31'b0 : BSR << 1;
		
		if (uStart | CSR[0]) begin
			Acc <= uStart? 31'h00_00_40_00 : ALUout;
			rCout <= uStart? 1'b0 : intCout;
		end
		
		finished <= AlmostFinished;
		rGetReady <= GetReady; //sets CSR and BSR for last step
		rStart <= start;
	end
	
	assign Q = Acc[30 : 15];
endmodule


Параметр LatchStart позволяет "защёлкнуть" импульс start, прежде чем он пойдёт на остальную схему. Это сделано для "верификации" - когда я делаю Vector Waveform File и кидаю на него "одиночный импульс", то симулятор считает, что этот импульс приходит "извне", через входной буфер и через систему интерконнекторов, из-за чего на медленном кристалле задержка выходит совершенно чудовищная - одного этого хватает, чтобы модуль перестал работать!

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

Также видна некоторая "паранойя" - мало того, что выход finished идёт из регистра, так даже сигнал rGetReady формируется по значению счётчика одним тактом ранее и тоже "защёлкивается", чтобы уж наверняка!

Как результат, модуль синтезируется в 121 логический элемент (ЛЭ), что всего лишь на 3 больше, чем модуль CheapUnsignedMult16 с такой же шириной аккумулятора в 31 бит. Наконец, Timing Analyzer показывает максимально допустимую частоту в 80 МГц РОВНО.

Увы, симулятор не согласен, он при выборе медленного кристалла показывает, как в старшие биты иногда не успевают пройти биты, и значения искажаются. Но если запустить его на быстром кристалле, то всё хорошо:


Использованы те же множители для примера, что и в части 'h24, и ответы получаются такие же, как у модуля с 31-битным аккумулятором.

Интересно проследить за промежуточными значениями. Если для упрощения принять, что аккумулятор у нас 32-битный, то при инициализации он принимает значение 0x0000 8000. Мы видим только старшие разряды - это нули. Регистр BSR инициализируется значением 0x0000 FFFF.

Первая строка "умножения в столбик": прибавляем к акк. 0xFFFF и получаем 0x0001 7FFF - и действительно, эту единичку мы видим на осциллограмме. Тем временем BSR сдвигается влево и становится равен 0x0001 FFFE.

Вторая строка: прибавляем 0x0001 FFFE и должны получить 0x0003 7FFD, но мы видим двойку вместо тройки! Да, всё верно - бит переноса сформировался, но пока "застрял" в регистре. Тем временем, BSR снова сдвигается и становится равен 0x0002 FFFC.

И так далее. Наконец, в последней строке, где во втором множителе стоит нолик, мы наблюдаем прибавление единички, что в итоге даёт нам правильный ответ. То есть, наша хитрючая схема для замены BSR на ноль и CSR[0] на единицу, чтобы этот перенос "прошёл" - действительно срабатывает.

Когда мы добавляем данный модуль в схему отправки показаний АЦП (часть 'h25, часть 'h26, ускоренный вариант - часть 'h33), Timing Analyzer не выдаёт нам предупреждений, говорит о тех же самых 80 МГц ровно.

Прошивка в ПЛИС показывает: работает без сбоев! Понятно, это ещё ни о чём не говорит, мы не проверяли её во всех возможных условиях, но пока что любая схема, которая "проходила" Timing Analyzer для кристалла "-3", без проблем работала на этой ПЛИС. Даже если для "-2" проходила - этого уже было достаточно.

Но если вдруг при очередном синтезе мы "не уложимся" в тайминги, или решим: "пусть и симулятор будет показывать правильную работу!", то данный подход позволяет наращивать рабочую частоту, не снижая точности и лишь немножко увеличивая время выполнения!

А именно: вместо разделения сумматора на две части, мы можем с тем же успехом поделить его на 3, 4 и более частей. Каждая из них "запаздывает" с переносом. Важно только помнить, что на последнем шаге, когда мы вносим перенос в одном месте (скажем, в середине числа), он может в свою очередь породить перенос к более старшим разрядам, и он снова будет задержан, поэтому нужно будет провести ещё один шаг, чтобы ввести в ответ этот последний перенос. Поэтому вместо 17 тактов, которые уходят на умножение сейчас (один - на загрузку регистров и обнуление аккумулятора, затем 16 сложений), у нас будет уходить 18 (+5,9%) или 19 (+12%) тактов - не так уж и плохо. "Финт ушами" с последним битом аккумулятора больше не пройдёт.

Если мы поделим сумматор на 3 части, получится такой модуль:
module CarryDelay2UnsignedMult16 (input clk, input [15:0] B, input [15:0] C, input start, output [15:0] Q, output reg finished = 1'b0);

	parameter LatchStart = 0;
	reg rStart = 1'b0;
	wire uStart = (LatchStart == 1)? rStart : start;

//state machine
	wire [4:0] State;
	//5'b00000 is Idle
	//5'b01111 is start
	//5'b11100 and 5'b11101 is where GetReady is active
	//5'b11101 and 5'b11110 is where sGetReady is active
	//5'b11111 is "almost finished" state
	wire IsIdle = (~State[4]) & (~State[3]);
	wire AlmostFinished;
	wire GetReady = (State[3:1] == 3'b110);
	reg rGetReady = 1'b0;	
	
	lpm_counter	counter (
				.clock (clk),
				.cnt_en (~IsIdle),
				.sset (uStart),
				.q (State),
				.cout (AlmostFinished) );
	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 [30 : 0] BSR = 1'b0; //senior is not needed after all
	reg [30 : 0] Acc = 1'b0; //ignoring LSB, because it can't have carry anyway
	
	wire [30 : 0] ALUout;

	//LSB adder, 11 bit long
	wire intCout0;
	reg rCout0 = 1'b0;
	
	lpm_add_sub LSB (	.cin (1'b0),
				.dataa (Acc[10:0]),
				.datab (BSR[11:1]), //lsb of BSR is to shift it correctly, not lose this bit
				.cout (intCout0),
				.result (ALUout[10:0]));
	defparam
		LSB.LPM_WIDTH = 11;
	
	//middle adder, 10 bit long
	wire intCout1;
	reg rCout1 = 1'b0;
	
	lpm_add_sub MID (	.cin (rCout0),
				.dataa (Acc[20:11]),
				.datab (BSR[21:12]),
				.cout (intCout1),
				.result (ALUout[20:11]));
	defparam
		MID.LPM_WIDTH = 10;
						
	//MSB adder, 10 bit long
	lpm_add_sub MSB (	.cin (rCout1),
				.dataa (Acc[30:21]),
				.datab ({1'b0, BSR[30:22]}),
				.cout (),
				.result (ALUout[30:21]));
	defparam
		MSB.LPM_WIDTH = 10;

	always @(posedge clk) begin
		CSR <= uStart? C : rGetReady? 1'b1 : CSR >> 1;
	
		BSR <= uStart? {15'b0, B}: (rGetReady & (~CSR[1]))? 31'b0 : BSR << 1;
		
		if (uStart | CSR[0]) begin
			Acc <= uStart? 31'h00_00_40_00 : ALUout;
			rCout0 <= uStart? 1'b0 : intCout0;
			rCout1 <= uStart? 1'b0 : intCout1;
		end
		
		finished <= AlmostFinished;
		rGetReady <= GetReady; //sets CSR and BSR for last step
		rStart <= start;
	end
	
	assign Q = Acc[30 : 15];
endmodule


симуляция (теперь уже и для "медленного кристалла") показывает те же результаты, к которым, правда, схема приходит чуть-чуть другим путём. Timing Analyzer показывает максимальную частоту 90,91 МГц - уже получше! Этот модуль занимает 124 ЛЭ, т.е ещё на 3 больше в сравнении с предыдущим. В составе схемы передачи показаний АЦП мы получаем максимально допустимую частоту 85,47 МГц, но наш перемножитель больше не является "бутылочным горлышком".

Наконец, прошивка в ПЛИС также показывает нормальную работу.


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

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

Recent Posts from This Journal

  • Огарь крупным планом

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

  • Я создал монстра!

    Вот нормальная счастливая пара разъёмов ОНЦ-БС-1-10/14-Р12-2-В и ОНЦ-БС-1-10/14-В1-2-В: У розетки кроме основного выступа, отмечающего "верх",…

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

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments