Мучаем 5576ХС4Т - часть 'h2F - знаковые умножители, тысячи их!
Часть 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 мы довольно подробно рассмотрели умножение беззнаковых целых чисел: как более компактные версии с аккумулятором ограниченной длины (например, 23 бита для умножения 16-битных чисел), так и наиболее честную с 32-битным аккумулятором и округлением банкира. Кстати, даже при использовании аппаратного перемножителя 18×18 бит, которые присутствуют в более новых ПЛИС, часть этого материала будет полезна, поскольку эти перемножители дают 36-битный результат, а округлить его - уже забота разработчика!
Сейчас рассмотрим умножение чисел со знаком - в нём есть свои "подводные камни", по счастью, не очень большие.
Нас будут интересовать числа формата Q2.14 (16 бит, знаковое, с фиксированной точкой, 2 целых бита, остальные - дробные, представимые значения от -2 до 2 - 2-14) и Q1.15 (тоже 16 бит, но представимые числа от -1 до 1 - 2-15).
Именно они - главные кандидаты для представления кватернионов! Также именно Q2.14 можно использовать для генерации множества Мандельброта, ведь стоит одной из компонент комплексного числа превысить диапазон -2 .. +2, как мы можем с уверенностью сказать - дальше последовательность разойдётся.
Всё начинается с обычного умножения целых знаковых чисел, когда два 16-битных числа после умножения "в столбик" дают 32-битное число, и эта операция происходит точно. Интересный момент состоит в том, что нам хватило бы 31 бита для хранения результата - старший бит можно было бы убрать - если бы не один-единственный случай, когда (-32768) * (-32768) = 1073741824,
или, в шестнадцатеричной записи в дополнительном коде: 0x8000 * 0x8000 = 0x4000 0000. В данном случае нулевой старший бит обязателен, чтобы показать, что число положительное. Если бы его не было, мы должны были интерпретировать это число как -1073741824.
И это же - единственный случай, когда при умножении чисел формата Q1.15 случается переполнение - умножая (-1) на (-1), мы получаем 1, которая не представима в данном формате.
Поэтому, в отличие от беззнаковых чисел, где мы брали 16 самых старших бит, в случае Q1.15 мы используем самый старший бит как признак переполнения: он должен совпадать со следующим по старшинству битом, в противном случае наступило переполнение. А на выход мы должны подать либо 16 бит, идущие вслед за старшим, либо можно реализовать механизм "насыщения": в случае переполнения мы получим либо самое большое положительное, либо самое большое отрицательное число, представимое в данном формате. Численные эксперименты показывают, что это вполне подходящий способ для работы с кватернионами. (Надеюсь, дойдём когда-нибудь и до этого - и два здоровенных цикла "Ликбез по кватернионам" и "Мучаем 5576ХС4Т" - сойдутся!)
При использовании формата Q2.14, переполнение случается гораздо чаще: ведь умножая числа в диапазоне от -2 до 2, мы будем получать числа в диапазоне от -4 до 4, и половину новых значений не сможем представить в том же самом формате.
Старший бит нашего аккумулятора будет иметь "вес" (-8): он нужен, чтобы значение +4 было представимо. Следующий бит имеет вес 4, и только следующий за ним: 2 (промежуточный формат: Q4.28) При этом, признаком отсутствия переполнения будет совпадение всех трёх старших битов.
Но для нашего генератора множества Мандельброта нужны ещё более экзотические перемножители!
Мы уже решили, что компоненты комплексного числа будут храниться в формате Q2.14. На некоторой итерации у нас есть числа x, y - действительная и мнимая часть числа Z. Теперь мы хотим посчитать выражение:
x <= x * x - y * y + cx;
y <= 2 * x * y + cy;
(выражение
Z <= Z2 + C в покоординатной записи)
Верхнюю строку можно записать так:
x <= (x - y) * (x + y) + cx;
что довольно хорошо "ложится" на ПЛИС - мы ставим два умножителя, один для x, другой - для y. Они работают синхронно и в какой-то момент дают результат. Сразу на выходе с них стоит два сумматора, один для вычисления x-y, второй - для x+y. Их выходы и поступают на вход первого умножителя. Также его аккумулятор инициализируется не нулём, а значением cx.
Но чтобы при вычислении x-y или x+y не случилось переполнения, нужно сделать эти сумматоры 17-битными. Поэтому и умножитель должен иметь дополнительный разряд. При этом аккумулятор расширять не требуется - мы знаем, что выражение x2 - y2 при значениях x,y в диапазоне от -2 до +2 не превысит своих обычных -4 .. +4, на которые мы и так "заложились".
Также у нас вполне хватает места в аккумуляторе для константы cx - она находится в диапазоне -2 .. +2, поэтому ширины аккумулятора по-прежнему хватит, чтобы посчитать всё выражение без переполнения на любом из этапов. И только получив конечный результат, мы посмотрим, вместился ли он в свой привычный диапазон -2 .. +2. Если не вместился - пора переходить к следующему пикселю!
Нижняя строка:
y <= 2 * x * y + cy;
требует самого обычного умножителя, который посчитает выражение x * y (и оно, как всегда, будет в диапазоне -4 .. +4). Только инициализируем мы его значением cy/2 (т.е константу мы сразу сдвинем вправо на один разряд), это не приведёт к переполнению (у нас в аккумуляторе представимы значения от -8 до 8 - 2-28).
Вся разница в том, что мы должны теперь взять не те 16 бит, что обычно, а ещё на 1 "правее", и поменять правила для определения переполнения. Мы будем считать переполнением значения, не попадающие в диапазон -1 .. +1.
Ну и ещё одно замечание: поскольку два умножителя мы будем запускать всегда синхронно, то нет смысла "засовывать" счётчик состояний в каждый из них: можно один умножитель сделать "ведущим", а второй - "ведомым". Как ни странно, ему может понадобиться лишь два управляющих сигнала: isNegationStep и isRoundingStep, причём второй лишь в случае "округления банкира".
Пора заняться кодом!
Первым делом - умножитель двух 17-битных знаковых чисел формата Q3.14, дающий результат в формате Q2.14. Правильные ответы он будет давать только при условии, что два входных числа - действительно x+y и x-y, где x,y - 16-битные числа формата Q2.14.
Вот его код:
//17-bit signed multiplier-adder
//so far it's designed for Mandelbrot set generator
//for real part: X <= X * X - Y * Y + Cx
//or, to reduce multiplications,
// X <= (X - Y) * (X + Y) + Cx
//we use external adders to get X - Y and X + Y,
//but their result is 17 bit to avoid overflow
//(we could stop the job if overflow is present,
//but that could distort picture at x = -2 or near this point.
//better not risk and do it properly)
//this module doesn't use banker's rounding, but outputs isRoundingStep for its 16-bit 'neighbour' because it has spare 1 clk cycle for it
//it also controls the second multiplier-adder which doesn't contain its own counter
module LeadingMAC17param (input clk, input [15:0] InitVal, input [16:0] B, input [16:0] C, input start,
output [15:0] Q, output ready, output overflow, output isNegationStep, output isRoundingStep);
parameter AccWidth = 32; //for best accuracy
localparam RemainingBits = AccWidth - 19;
//state machine
localparam sIdle = 5'b00000;
//large gap here
localparam sStart = 5'b01110;
localparam sStep2 = 5'b01111;
localparam sStep3 = 5'b10000;
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? (on guided MAC only!)
localparam sFinish = 5'b11111;
wire [4:0] State;
wire IsIdle = (~State[4])&(~State[3]);
assign isNegationStep = (~State[4]) & State[3] & (~State[0]); //little shortcut thanks to large gap
assign isRoundingStep = (State [3:0] == 4'b1101);
lpm_counter counter (
.clock (clk),
.cnt_en (~IsIdle),
.sset (start),
.q (State),
.cout (ready) );
defparam
counter.lpm_direction = "UP",
counter.lpm_port_updown = "PORT_UNUSED",
counter.lpm_type = "LPM_COUNTER",
counter.lpm_width = 5,
counter.lpm_svalue = sStart;
//very simple: we do one step after another. we can have start several pulses long - we stay in one position until it's reset
//data path
reg [16:0] CSR = 1'b0; //shift register for 2nd operand
reg [AccWidth : 0] BSR = 1'b0; //even fuller this time
reg [AccWidth - 1 : 0] Acc = 1'b0; //but here it's needed all right
wire [AccWidth - 1 : 0] ALUout;
//this time we explicitly define our adder
lpm_add_sub ALU ( //very proud name for what we have here, but why not :)
.dataa (Acc),
.datab (BSR[AccWidth - 1 : 0]),
.cin (isNegationStep),
.result (ALUout) );
defparam
ALU.lpm_direction = "ADD",
ALU.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=YES",
ALU.lpm_representation = "UNSIGNED",
ALU.lpm_type = "LPM_ADD_SUB",
ALU.lpm_width = AccWidth;
always @(posedge clk) begin
BSR <= start? ~(B << (AccWidth - 16)) : isNegationStep? {~BSR[AccWidth], ~BSR[AccWidth : 1]} : {BSR[AccWidth], BSR[AccWidth : 1]};
CSR <= start? C : CSR << 1; //no need for extending ones at left
if (start | CSR[16])
Acc <= start? {InitVal[15], InitVal[15], InitVal, 1'b1, {RemainingBits{1'b0}}} : ALUout;
end
assign Q = Acc[AccWidth - 3 : AccWidth - 18];
wire isPositive = (Acc[AccWidth - 1 : AccWidth - 3] == 3'b000);
wire isNegative = (Acc[AccWidth - 1 : AccWidth - 3] == 3'b111);
assign overflow = ~(isPositive | isNegative); //for saturation arithmetic, we may want these isPositive / isNegative explicitly
endmodule
У нас 3 входа, InitValue, B и C. Мы заносим значения во все три, и подаём импульс start. По прошествии 18 тактов, мы получаем ответ, при этом поступает единичка на выход ready. В этот же момент мы можем проверить выход overflow - наличие единицы на нём говорит о переполнении.
Наконец, выходы isNegationStep и isRoundingStep нужны для управления "соседним" умножителем. Мы так решили: именно этому умножителю нужно на один шаг больше, поскольку он работает с 17-битными входами. А его "сосед", перемножающий 16-битные числа, может (если очень пожелает) провести округление банкира - всяко лучше, чем ничего :)
Половину модуля занимает счётчик тактов - штука простая до безобразия. Отсчитывает 18 тактов, в нужные моменты времени выдавая импульсы на ready, isNegationStep и isRoundingStep - вот и всё.
Дальше смотрим на вычислительную часть.
При поступлении сигнала start мы заносим в аккумулятор Acc значение InitVal, с "расширением знака" - самый старший бит InitVal "заполняет собой" старшие 3 бита, чтобы из знакового числа в диапазоне -2 .. +2 получить знаковое число в диапазоне -8 .. +8. А справа от числа InitVal мы заносим "половинку" для того, чтобы простое обрубание младших разрядов приводило к округлению "до ближайшего целого".
Сдвиговый регистр BSR (B Shift Register) в этот раз даже длиннее аккумулятора, занимая 33 бита. Так возникает, поскольку формально у нас входы имеют диапазон от -4 до +4, поэтому когда мы умножаем значение B на самый старший бит C, старший бит должен иметь вес (-16), что выходит за пределы нашего аккумулятора. Мы "знаем заранее", что такого никогда не будет - если в B заносится значение -4, то в C будет ноль, поэтому самый старший бит не подаём на аккумулятор (иначе пришлось бы удлинить и его), но просто выкинуть его тоже нельзя, ведь после сдвига вправо он снова "вернётся в игру".
Кроме того, сейчас именно регистр BSR отвечает за первоначальную инверсию значения B и возвращение его "в норму". Дело в том, что старший бит числа C выражает "знак", поэтому когда он единичный, мы должны не прибавить к аккумулятору значение B, а вычесть его. Чтобы получить это вычитание, нам нужно сделать отрицание всех битов B, а потом ещё прибавить единичку. Единичка прибавится непосредственно в сумматоре (там есть вход cin), а вот отрицание лучше сделать регистром - это не увеличивает требуемое количество ЛЭ.
По сути, у этого регистра 3 режима: параллельная загрузка (с отрицанием всех бит), арифметический сдвиг вправо с отрицанием, и арифметический сдвиг вправо без отрицания. Благодаря тому, что мы не просим регистр просто "хранить своё значение", все эти функции умещаются в 33 ЛЭ, т.е по 1 ЛЭ на каждый бит. Действительно, из 4 входов ГФ, один мы используем для параллельной загрузки, второй - для подачи значения с соседнего бита (для сдвига), и ещё 2 входа - для выбора 1 из 3 режимов работы. Тютелька в тютельку...
Сдвиговый регистр CSR (C Shift Register) - прост до безобразия! Он 17-битный, и он либо осуществляет параллельную загрузку числа C, либо сдвигает своё содержимое влево. О нём и говорить нечего.
В очередной раз нам пришлось поставить сумматор явным образом, чтобы задействовать вход cin (carry in), который мы используем, чтобы превратить сложение в вычитание на первом шаге умножения. (если просто написать ALUout = BSR + Acc + isNegationStep, недалёкий компилятор поставит на этом месте ДВА сумматора, что плохо не только в плане количества ЛЭ, но и удлиняет комбинаторный путь, так что даже на быстром кристалле придётся ограничить рабочую частоту!)
Результаты симуляции приведены в начале поста. Сначала мы попытались посчитать выражение
(-2) * (-2) - 1.
В аккумуляторе появилось правильное значение 3, но оно "не влезло" в выход Q - точнее, там появилась эта самая тройка, но только при беззнаковой записи. Поэтому у нас активировался и выход overflow.
Второй раз мы посчитали выражение
1 * (-3) + 1 = -2.
Всё получилось как надо: хотя промежуточный результат "не лез" в выход (и на некоторое время "загорелся" overflow), к концу работы стало ясно, что ответ попадает в диапазон представимых значений.
Данный модуль занимает 128 логических элементов (ЛЭ), если использовать 32-битный аккумулятор. При другой ширине аккумулятора AccWidth, количество ЛЭ составит 32 + AccWidth * 3.
Теперь рассмотрим умножитель для мнимой части числа - он принимает на вход два 16-битных значения B, C, а также 16-битное значение InitVal, и вычисляет выражение InitVal + 2 * B * C. Пока что он не будет делать округления банкира.
Вот его код:
//multiply-add module for Mandelbrot set
//Q = InitVal + 2 * B * C
//works in Q2.14 format
//needs LeadingMAC module to provide isNegationStep and isRoundingStep
module GuidedMACtimes2 (input clk, input [15:0] InitVal, input [15:0] B, input [15:0] C, input start, input isNegationStep, input isRoundingStep,
output [15:0] Q, output overflow);
parameter AccWidth = 32; //for best accuracy
localparam RemainingBits = AccWidth - 20;
//data path
reg [15:0] CSR = 1'b0; //shift register for 2nd operand
reg [AccWidth - 2 : 0] BSR = 1'b0;
reg [AccWidth - 1 : 0] Acc = 1'b0; //but here it's needed all right
wire [AccWidth - 1 : 0] ALUout;
//this time we explicitly define our adder
lpm_add_sub ALU ( //very proud name for what we have here, but why not :)
.dataa (Acc),
.datab ({BSR[AccWidth - 2], BSR}), //sign extention
.cin (isNegationStep),
.result (ALUout) );
defparam
ALU.lpm_direction = "ADD",
ALU.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=YES",
ALU.lpm_representation = "UNSIGNED",
ALU.lpm_type = "LPM_ADD_SUB",
ALU.lpm_width = AccWidth;
always @(posedge clk) begin
BSR <= start? ~(B << (AccWidth - 17)) : isNegationStep? {~BSR[AccWidth - 2], ~BSR[AccWidth - 2 : 1]} : {BSR[AccWidth - 2], BSR[AccWidth - 2 : 1]};
CSR <= start? C : CSR << 1; //no need for extending ones at left
if (start | CSR[15]) //InitVal is shifted even more this time
Acc <= start? {InitVal[15], InitVal[15], InitVal[15], InitVal, 1'b1, {RemainingBits{1'b0}}} : ALUout;
end
assign Q = Acc[AccWidth - 4 : AccWidth - 19];
wire isPositive = (Acc[AccWidth - 1 : AccWidth - 4] == 4'b0000);
wire isNegative = (Acc[AccWidth - 1 : AccWidth - 4] == 4'b1111);
assign overflow = ~(isPositive | isNegative); //for saturation arithmetic, we may want these isPositive / isNegative explicitly
endmodule
Весь счётчик мы отсюда выкинули, опять пожадничали на размере регистра B (он на 1 бит короче аккумулятора, а на сумматор его старший бит поступает сразу на два соседних входа, для расширения знака). Сдвинули вправо выход (чтобы получалось умножение на 2), и соответственно усложнили условие для переполнения (теперь 4 бита подряд должны совпадать). Также вправо сдвинулось InitVal, а в остальном - всё то же самое.
Вот результат симуляции:
Здесь мы вычисляли выражение
2 * (-0,5) * 0,5 + 1
и получили ответ: 0,5, что уже радостно. По крайней мере, мы не ошиблись со сдвигами. Полной проверки этот модуль ещё не прошёл: это целое искусство устроить хорошую верификацию всего этого дела.
Этот модуль занимает 112 ЛЭ - чуть меньше предыдущего за счёт более коротких регистров (BSR укоротился на 2 бита, CSR - на 1) и отсутствия управляющей логики.
В следующей части мы целиком соберём "вычислитель" для множества Мандельброта.
Часть 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 мы довольно подробно рассмотрели умножение беззнаковых целых чисел: как более компактные версии с аккумулятором ограниченной длины (например, 23 бита для умножения 16-битных чисел), так и наиболее честную с 32-битным аккумулятором и округлением банкира. Кстати, даже при использовании аппаратного перемножителя 18×18 бит, которые присутствуют в более новых ПЛИС, часть этого материала будет полезна, поскольку эти перемножители дают 36-битный результат, а округлить его - уже забота разработчика!
Сейчас рассмотрим умножение чисел со знаком - в нём есть свои "подводные камни", по счастью, не очень большие.
Нас будут интересовать числа формата Q2.14 (16 бит, знаковое, с фиксированной точкой, 2 целых бита, остальные - дробные, представимые значения от -2 до 2 - 2-14) и Q1.15 (тоже 16 бит, но представимые числа от -1 до 1 - 2-15).
Именно они - главные кандидаты для представления кватернионов! Также именно Q2.14 можно использовать для генерации множества Мандельброта, ведь стоит одной из компонент комплексного числа превысить диапазон -2 .. +2, как мы можем с уверенностью сказать - дальше последовательность разойдётся.
Всё начинается с обычного умножения целых знаковых чисел, когда два 16-битных числа после умножения "в столбик" дают 32-битное число, и эта операция происходит точно. Интересный момент состоит в том, что нам хватило бы 31 бита для хранения результата - старший бит можно было бы убрать - если бы не один-единственный случай, когда (-32768) * (-32768) = 1073741824,
или, в шестнадцатеричной записи в дополнительном коде: 0x8000 * 0x8000 = 0x4000 0000. В данном случае нулевой старший бит обязателен, чтобы показать, что число положительное. Если бы его не было, мы должны были интерпретировать это число как -1073741824.
И это же - единственный случай, когда при умножении чисел формата Q1.15 случается переполнение - умножая (-1) на (-1), мы получаем 1, которая не представима в данном формате.
Поэтому, в отличие от беззнаковых чисел, где мы брали 16 самых старших бит, в случае Q1.15 мы используем самый старший бит как признак переполнения: он должен совпадать со следующим по старшинству битом, в противном случае наступило переполнение. А на выход мы должны подать либо 16 бит, идущие вслед за старшим, либо можно реализовать механизм "насыщения": в случае переполнения мы получим либо самое большое положительное, либо самое большое отрицательное число, представимое в данном формате. Численные эксперименты показывают, что это вполне подходящий способ для работы с кватернионами. (Надеюсь, дойдём когда-нибудь и до этого - и два здоровенных цикла "Ликбез по кватернионам" и "Мучаем 5576ХС4Т" - сойдутся!)
При использовании формата Q2.14, переполнение случается гораздо чаще: ведь умножая числа в диапазоне от -2 до 2, мы будем получать числа в диапазоне от -4 до 4, и половину новых значений не сможем представить в том же самом формате.
Старший бит нашего аккумулятора будет иметь "вес" (-8): он нужен, чтобы значение +4 было представимо. Следующий бит имеет вес 4, и только следующий за ним: 2 (промежуточный формат: Q4.28) При этом, признаком отсутствия переполнения будет совпадение всех трёх старших битов.
Но для нашего генератора множества Мандельброта нужны ещё более экзотические перемножители!
Мы уже решили, что компоненты комплексного числа будут храниться в формате Q2.14. На некоторой итерации у нас есть числа x, y - действительная и мнимая часть числа Z. Теперь мы хотим посчитать выражение:
x <= x * x - y * y + cx;
y <= 2 * x * y + cy;
(выражение
Z <= Z2 + C в покоординатной записи)
Верхнюю строку можно записать так:
x <= (x - y) * (x + y) + cx;
что довольно хорошо "ложится" на ПЛИС - мы ставим два умножителя, один для x, другой - для y. Они работают синхронно и в какой-то момент дают результат. Сразу на выходе с них стоит два сумматора, один для вычисления x-y, второй - для x+y. Их выходы и поступают на вход первого умножителя. Также его аккумулятор инициализируется не нулём, а значением cx.
Но чтобы при вычислении x-y или x+y не случилось переполнения, нужно сделать эти сумматоры 17-битными. Поэтому и умножитель должен иметь дополнительный разряд. При этом аккумулятор расширять не требуется - мы знаем, что выражение x2 - y2 при значениях x,y в диапазоне от -2 до +2 не превысит своих обычных -4 .. +4, на которые мы и так "заложились".
Также у нас вполне хватает места в аккумуляторе для константы cx - она находится в диапазоне -2 .. +2, поэтому ширины аккумулятора по-прежнему хватит, чтобы посчитать всё выражение без переполнения на любом из этапов. И только получив конечный результат, мы посмотрим, вместился ли он в свой привычный диапазон -2 .. +2. Если не вместился - пора переходить к следующему пикселю!
Нижняя строка:
y <= 2 * x * y + cy;
требует самого обычного умножителя, который посчитает выражение x * y (и оно, как всегда, будет в диапазоне -4 .. +4). Только инициализируем мы его значением cy/2 (т.е константу мы сразу сдвинем вправо на один разряд), это не приведёт к переполнению (у нас в аккумуляторе представимы значения от -8 до 8 - 2-28).
Вся разница в том, что мы должны теперь взять не те 16 бит, что обычно, а ещё на 1 "правее", и поменять правила для определения переполнения. Мы будем считать переполнением значения, не попадающие в диапазон -1 .. +1.
Ну и ещё одно замечание: поскольку два умножителя мы будем запускать всегда синхронно, то нет смысла "засовывать" счётчик состояний в каждый из них: можно один умножитель сделать "ведущим", а второй - "ведомым". Как ни странно, ему может понадобиться лишь два управляющих сигнала: isNegationStep и isRoundingStep, причём второй лишь в случае "округления банкира".
Пора заняться кодом!
Первым делом - умножитель двух 17-битных знаковых чисел формата Q3.14, дающий результат в формате Q2.14. Правильные ответы он будет давать только при условии, что два входных числа - действительно x+y и x-y, где x,y - 16-битные числа формата Q2.14.
Вот его код:
//17-bit signed multiplier-adder
//so far it's designed for Mandelbrot set generator
//for real part: X <= X * X - Y * Y + Cx
//or, to reduce multiplications,
// X <= (X - Y) * (X + Y) + Cx
//we use external adders to get X - Y and X + Y,
//but their result is 17 bit to avoid overflow
//(we could stop the job if overflow is present,
//but that could distort picture at x = -2 or near this point.
//better not risk and do it properly)
//this module doesn't use banker's rounding, but outputs isRoundingStep for its 16-bit 'neighbour' because it has spare 1 clk cycle for it
//it also controls the second multiplier-adder which doesn't contain its own counter
module LeadingMAC17param (input clk, input [15:0] InitVal, input [16:0] B, input [16:0] C, input start,
output [15:0] Q, output ready, output overflow, output isNegationStep, output isRoundingStep);
parameter AccWidth = 32; //for best accuracy
localparam RemainingBits = AccWidth - 19;
//state machine
localparam sIdle = 5'b00000;
//large gap here
localparam sStart = 5'b01110;
localparam sStep2 = 5'b01111;
localparam sStep3 = 5'b10000;
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? (on guided MAC only!)
localparam sFinish = 5'b11111;
wire [4:0] State;
wire IsIdle = (~State[4])&(~State[3]);
assign isNegationStep = (~State[4]) & State[3] & (~State[0]); //little shortcut thanks to large gap
assign isRoundingStep = (State [3:0] == 4'b1101);
lpm_counter counter (
.clock (clk),
.cnt_en (~IsIdle),
.sset (start),
.q (State),
.cout (ready) );
defparam
counter.lpm_direction = "UP",
counter.lpm_port_updown = "PORT_UNUSED",
counter.lpm_type = "LPM_COUNTER",
counter.lpm_width = 5,
counter.lpm_svalue = sStart;
//very simple: we do one step after another. we can have start several pulses long - we stay in one position until it's reset
//data path
reg [16:0] CSR = 1'b0; //shift register for 2nd operand
reg [AccWidth : 0] BSR = 1'b0; //even fuller this time
reg [AccWidth - 1 : 0] Acc = 1'b0; //but here it's needed all right
wire [AccWidth - 1 : 0] ALUout;
//this time we explicitly define our adder
lpm_add_sub ALU ( //very proud name for what we have here, but why not :)
.dataa (Acc),
.datab (BSR[AccWidth - 1 : 0]),
.cin (isNegationStep),
.result (ALUout) );
defparam
ALU.lpm_direction = "ADD",
ALU.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=YES",
ALU.lpm_representation = "UNSIGNED",
ALU.lpm_type = "LPM_ADD_SUB",
ALU.lpm_width = AccWidth;
always @(posedge clk) begin
BSR <= start? ~(B << (AccWidth - 16)) : isNegationStep? {~BSR[AccWidth], ~BSR[AccWidth : 1]} : {BSR[AccWidth], BSR[AccWidth : 1]};
CSR <= start? C : CSR << 1; //no need for extending ones at left
if (start | CSR[16])
Acc <= start? {InitVal[15], InitVal[15], InitVal, 1'b1, {RemainingBits{1'b0}}} : ALUout;
end
assign Q = Acc[AccWidth - 3 : AccWidth - 18];
wire isPositive = (Acc[AccWidth - 1 : AccWidth - 3] == 3'b000);
wire isNegative = (Acc[AccWidth - 1 : AccWidth - 3] == 3'b111);
assign overflow = ~(isPositive | isNegative); //for saturation arithmetic, we may want these isPositive / isNegative explicitly
endmodule
У нас 3 входа, InitValue, B и C. Мы заносим значения во все три, и подаём импульс start. По прошествии 18 тактов, мы получаем ответ, при этом поступает единичка на выход ready. В этот же момент мы можем проверить выход overflow - наличие единицы на нём говорит о переполнении.
Наконец, выходы isNegationStep и isRoundingStep нужны для управления "соседним" умножителем. Мы так решили: именно этому умножителю нужно на один шаг больше, поскольку он работает с 17-битными входами. А его "сосед", перемножающий 16-битные числа, может (если очень пожелает) провести округление банкира - всяко лучше, чем ничего :)
Половину модуля занимает счётчик тактов - штука простая до безобразия. Отсчитывает 18 тактов, в нужные моменты времени выдавая импульсы на ready, isNegationStep и isRoundingStep - вот и всё.
Дальше смотрим на вычислительную часть.
При поступлении сигнала start мы заносим в аккумулятор Acc значение InitVal, с "расширением знака" - самый старший бит InitVal "заполняет собой" старшие 3 бита, чтобы из знакового числа в диапазоне -2 .. +2 получить знаковое число в диапазоне -8 .. +8. А справа от числа InitVal мы заносим "половинку" для того, чтобы простое обрубание младших разрядов приводило к округлению "до ближайшего целого".
Сдвиговый регистр BSR (B Shift Register) в этот раз даже длиннее аккумулятора, занимая 33 бита. Так возникает, поскольку формально у нас входы имеют диапазон от -4 до +4, поэтому когда мы умножаем значение B на самый старший бит C, старший бит должен иметь вес (-16), что выходит за пределы нашего аккумулятора. Мы "знаем заранее", что такого никогда не будет - если в B заносится значение -4, то в C будет ноль, поэтому самый старший бит не подаём на аккумулятор (иначе пришлось бы удлинить и его), но просто выкинуть его тоже нельзя, ведь после сдвига вправо он снова "вернётся в игру".
Кроме того, сейчас именно регистр BSR отвечает за первоначальную инверсию значения B и возвращение его "в норму". Дело в том, что старший бит числа C выражает "знак", поэтому когда он единичный, мы должны не прибавить к аккумулятору значение B, а вычесть его. Чтобы получить это вычитание, нам нужно сделать отрицание всех битов B, а потом ещё прибавить единичку. Единичка прибавится непосредственно в сумматоре (там есть вход cin), а вот отрицание лучше сделать регистром - это не увеличивает требуемое количество ЛЭ.
По сути, у этого регистра 3 режима: параллельная загрузка (с отрицанием всех бит), арифметический сдвиг вправо с отрицанием, и арифметический сдвиг вправо без отрицания. Благодаря тому, что мы не просим регистр просто "хранить своё значение", все эти функции умещаются в 33 ЛЭ, т.е по 1 ЛЭ на каждый бит. Действительно, из 4 входов ГФ, один мы используем для параллельной загрузки, второй - для подачи значения с соседнего бита (для сдвига), и ещё 2 входа - для выбора 1 из 3 режимов работы. Тютелька в тютельку...
Сдвиговый регистр CSR (C Shift Register) - прост до безобразия! Он 17-битный, и он либо осуществляет параллельную загрузку числа C, либо сдвигает своё содержимое влево. О нём и говорить нечего.
В очередной раз нам пришлось поставить сумматор явным образом, чтобы задействовать вход cin (carry in), который мы используем, чтобы превратить сложение в вычитание на первом шаге умножения. (если просто написать ALUout = BSR + Acc + isNegationStep, недалёкий компилятор поставит на этом месте ДВА сумматора, что плохо не только в плане количества ЛЭ, но и удлиняет комбинаторный путь, так что даже на быстром кристалле придётся ограничить рабочую частоту!)
Результаты симуляции приведены в начале поста. Сначала мы попытались посчитать выражение
(-2) * (-2) - 1.
В аккумуляторе появилось правильное значение 3, но оно "не влезло" в выход Q - точнее, там появилась эта самая тройка, но только при беззнаковой записи. Поэтому у нас активировался и выход overflow.
Второй раз мы посчитали выражение
1 * (-3) + 1 = -2.
Всё получилось как надо: хотя промежуточный результат "не лез" в выход (и на некоторое время "загорелся" overflow), к концу работы стало ясно, что ответ попадает в диапазон представимых значений.
Данный модуль занимает 128 логических элементов (ЛЭ), если использовать 32-битный аккумулятор. При другой ширине аккумулятора AccWidth, количество ЛЭ составит 32 + AccWidth * 3.
Теперь рассмотрим умножитель для мнимой части числа - он принимает на вход два 16-битных значения B, C, а также 16-битное значение InitVal, и вычисляет выражение InitVal + 2 * B * C. Пока что он не будет делать округления банкира.
Вот его код:
//multiply-add module for Mandelbrot set
//Q = InitVal + 2 * B * C
//works in Q2.14 format
//needs LeadingMAC module to provide isNegationStep and isRoundingStep
module GuidedMACtimes2 (input clk, input [15:0] InitVal, input [15:0] B, input [15:0] C, input start, input isNegationStep, input isRoundingStep,
output [15:0] Q, output overflow);
parameter AccWidth = 32; //for best accuracy
localparam RemainingBits = AccWidth - 20;
//data path
reg [15:0] CSR = 1'b0; //shift register for 2nd operand
reg [AccWidth - 2 : 0] BSR = 1'b0;
reg [AccWidth - 1 : 0] Acc = 1'b0; //but here it's needed all right
wire [AccWidth - 1 : 0] ALUout;
//this time we explicitly define our adder
lpm_add_sub ALU ( //very proud name for what we have here, but why not :)
.dataa (Acc),
.datab ({BSR[AccWidth - 2], BSR}), //sign extention
.cin (isNegationStep),
.result (ALUout) );
defparam
ALU.lpm_direction = "ADD",
ALU.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=YES",
ALU.lpm_representation = "UNSIGNED",
ALU.lpm_type = "LPM_ADD_SUB",
ALU.lpm_width = AccWidth;
always @(posedge clk) begin
BSR <= start? ~(B << (AccWidth - 17)) : isNegationStep? {~BSR[AccWidth - 2], ~BSR[AccWidth - 2 : 1]} : {BSR[AccWidth - 2], BSR[AccWidth - 2 : 1]};
CSR <= start? C : CSR << 1; //no need for extending ones at left
if (start | CSR[15]) //InitVal is shifted even more this time
Acc <= start? {InitVal[15], InitVal[15], InitVal[15], InitVal, 1'b1, {RemainingBits{1'b0}}} : ALUout;
end
assign Q = Acc[AccWidth - 4 : AccWidth - 19];
wire isPositive = (Acc[AccWidth - 1 : AccWidth - 4] == 4'b0000);
wire isNegative = (Acc[AccWidth - 1 : AccWidth - 4] == 4'b1111);
assign overflow = ~(isPositive | isNegative); //for saturation arithmetic, we may want these isPositive / isNegative explicitly
endmodule
Весь счётчик мы отсюда выкинули, опять пожадничали на размере регистра B (он на 1 бит короче аккумулятора, а на сумматор его старший бит поступает сразу на два соседних входа, для расширения знака). Сдвинули вправо выход (чтобы получалось умножение на 2), и соответственно усложнили условие для переполнения (теперь 4 бита подряд должны совпадать). Также вправо сдвинулось InitVal, а в остальном - всё то же самое.
Вот результат симуляции:
Здесь мы вычисляли выражение
2 * (-0,5) * 0,5 + 1
и получили ответ: 0,5, что уже радостно. По крайней мере, мы не ошиблись со сдвигами. Полной проверки этот модуль ещё не прошёл: это целое искусство устроить хорошую верификацию всего этого дела.
Этот модуль занимает 112 ЛЭ - чуть меньше предыдущего за счёт более коротких регистров (BSR укоротился на 2 бита, CSR - на 1) и отсутствия управляющей логики.
В следующей части мы целиком соберём "вычислитель" для множества Мандельброта.