nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

Монструозное АЛУ QuatCore

Алгоритм сопровождения зафурычил в 16-битных целых числах, так что пора вернуться к верилогу - доделать свой многострадальный процессор QuatCore, он же ℍ-core, в общем, "спецвычислитель", заточенный под наши задачи технического зрения и ориентации в пространстве. В целом, архитектура там проста до безобразия, TTA (Transport-Triggered Architecture), "крупными мазками" процессор давным-давно нарисован и самым ответственным узлом оказалось АЛУ (арифметическо-логическое устройство).

Эх, а как красиво всё начиналось...

Но маленький поросёнок превратился в огромную свинью:


в которой готовы все блоки, кроме самого главного - QuatCoreALUControl. По-моему, это самый сложный блок вообще во всём этом "вычислительном ядре", ведь он должен "дирижировать" всеми прочими показанными здесь блоками и обеспечить выполнение 21 разной команды, некоторые из которых весьма укуренные...


Основные части АЛУ:
- регистр Acc (аккумулятор), модуль QuatCoreALUAcc,
- регистр B (основной входной регистр), модуль QuatCoreALUBreg,
- регистр C (в него заносится второй множитель), модуль QuatCoreALUCreg,
- сумматор с дополнительными функциями, модуль QuatCoreALUadder,
- флаг знака, D-триггер с романтическим названием inst6,
- мультиплексор конечного результата, модуль QuatCoreALUoutput,
- устройство "байпаса" для межрегистровой передачи свыше 16 бит "в пределах АЛУ",
- устройство управления.

Сейчас вкратце расскажем о каждом.

Аккумулятор - регистр, в котором "накапливается" результат. Его ширину можно задать, при моделировании бралась ширина 32 бита, но если сильно "припрёт", можно будет и снизить немного, скорее всего. Все числа здесь считаются имеющими формат 1.15, т.е 1 бит перед запятой и 15 бит после, что даёт диапазон от -1 до 0,999969 для знаковых чисел и от 0 до 1,999969 для беззнаковых. Результатом умножения двух таких 16-битных чисел может стать единица (-1 умножить на -1), которая непредставима в таком формате, поэтому аккумулятор "расширен" влево на 1 бит, представляя числа от -2 до 1,999999999 (в случае 32 бит). Это также позволяет узнавать о переполнении в процессе вычислений, и достаточно легко "насыщать" результат (об этом подробнее, когда про мультиплексор конечного результата).

Модуль весьма прост, на каждый бит уходит всего по одному логическому элементу:

[Spoiler (click to open)]
//mode:
//0xx - idle
//100 - load from D
//101 - clear
//110 - set 1/2lsb (for rounding)
//111 - set 1/2 (for ABSP1D2)

module QuatCoreALUAcc (input clk, input [AccWidth-1:0] D, input [2:0] mode, output reg [AccWidth-1:0] Q=1'b0, output [16:0] Senior17, output [AccWidth-18:0] LSB);

parameter AccWidth = 32;
localparam trailingzeros = AccWidth - 18;

wire ce = mode[2];
wire [1:0] act = mode[1:0];

always @(posedge clk) if (ce)
	Q <= (act == 2'b00)? D :
	     (act == 2'b01)? {AccWidth{1'b0}} :
	     (act == 2'b10)? {18'b0_0000_0000_0000_0000_1, {trailingzeros{1'b0}}}:  //1/2 lsb
						 {18'b0_0100_0000_0000_0000_1, {trailingzeros{1'b0}}}; //just 1/2 
	
assign Senior17 = Q[AccWidth-1:AccWidth-17];
assign LSB = Q[AccWidth-18:0];

endmodule



Делать он умеет не так уж много: либо "стоит на месте" (idle), либо по тактовому фронту "защёлкивает" число из сумматора, либо обнуляется, либо устанавливает одну из 2 констант. Одна из них - "половинка младшего разряда", используется для корректного округления (почему это важно). Другая - число 1/2, используется при вычислении кватерниона поворота вокруг оси X из синуса и косинуса соотв. угла (см. аффинный алгоритм часть 4 - нахождение крена). Почему именно эти 2 - а чтобы добру не пропадать! Сделать параллельную загрузку из шины данных И обнуление в одном ЛЭ нереально (а под 32 лишних вводить жалко), а вот парочка констант влезла. Установить их здесь - наиболее быстро.

Выход немножко дублируется, просто чтобы получилась красивая схема без возни с "расщеплением шины". Полный 32-битный (или сколько там) выход идёт на сумматор, старшие 17 бит идут на мультиплексор результата, а младшие (15 по дефолту) - на регистр B. Если у нас, к примеру, будет команда

Add Acc

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

Регистр B - основной входной регистр, участвующий в КАЖДОЙ операции. И он же - самый "непостоянный". У него в принципе нет состояния "хранить результат" - на каждом такте в него либо загружается значение, либо сдвигается вправо, либо арифметически, либо логически (то есть, со знаком или без). Его ширина - на 1 меньше, чем у регистра Acc. Это позволяет проводить умножение с накоплением (Fused Multiply-Add, FMA), когда предыдущий результат хранится в Acc на полной точности, а к нему прибавляется B*C. Ну и есть возможность загрузить либо старшие 16 бит (когда загрузка идёт из памяти, к примеру), так и полную ширину, если источником является аккумулятор. Вот код модуля:

[Spoiler (click to open)]
//if seniorLoad = 0, then doing shift right
//if seniorLoad = 1, lsbLoad=0, then senior 16 bits are loaded, lower bits are cleared
//if seniorLoad = 1, lsbLoad = 1, then all bits are loaded

module QuatCoreALUBreg (input clk, input[AccWidth-18:0] Dsmall, input [15:0] D, input DoSigned,  input seniorLoad, input lsbLoad,  output [AccWidth-1:0] Q);

parameter AccWidth = 32;
localparam SmallPartWidth = AccWidth - 17;

reg [15:0] largeQ = 1'b0;
reg [SmallPartWidth-1:0] smallQ = 1'b0;
wire seniorBit = DoSigned? largeQ[15] : 1'b0;
assign Q = {seniorBit, largeQ, smallQ};

always @(posedge clk) begin
	largeQ[15] <= seniorLoad? D[15]: DoSigned? largeQ[15]  : 1'b0; //either syn load, or arithmetic shift right, or logical shift right
	largeQ[14:0] <= seniorLoad? D[14:0]: largeQ[15:1];
	smallQ <= seniorLoad? (lsbLoad? Dsmall : {SmallPartWidth{1'b0}}) : {largeQ[0], smallQ[SmallPartWidth-1:1]};
end

endmodule



Снова "простенько и со вкусом" - на каждый бит уходит по одному ЛЭ, плюс ещё один для формирования старшего бита на сумматор.

И сразу обсудим устройство "байпаса", модуль QuatCoreALUEnableBypass. Очень простой модуль, занимающий 1 ЛЭ:

module QuatCoreEnableBypass (input [7:0] SrcAddr, output Q);

assign Q = (SrcAddr[7:5] == 3'b100); //source is within ALU as well

endmodule

опять же, он не проверяет досконально, какой адрес "внутри АЛУ" мы запросили. Если мы запросили регистр C - получится странность - содержимое регистра C, все его 16 бит, мы передадим в регистр B "штатно", а в младшие биты занесём младшие биты регистра Acc... Но для основного применения - всё хорошо.

Сумматор у нас тоже относительно простой - умеет складывать, вычитать и выдавать ещё несколько констант. Вот его код:

[Spoiler (click to open)]
//can add, subtract and also replace input B with some constants. So far we need just 3 of them, maybe come up with smth later.
//in theory we could do as much as 6 of them

module QuatCoreALUadder (input [AccWidth-1:0] A, input [AccWidth-1:0] B, input [2:0] mode, output [AccWidth-1:0] Q, output SignBit);

parameter AccWidth = 32;
localparam trailingZeros = AccWidth - 18;

wire cin = mode[0:0];
wire [1:0] consts = mode[2:1];

wire [AccWidth-1:0] Btmp = 	(consts == 2'b00)? {18'b1_0000_0000_0000_0000_1, {trailingZeros{1'b0}}} : //minus 2 which eventually will become just 2
							(consts == 2'b01)? {18'b0_1100_0000_0000_0000_1, {trailingZeros{1'b0}}} :
							(consts == 2'b10)? {18'b1_0100_0000_0000_0000_1, {trailingZeros{1'b0}}}:
												B;

wire [AccWidth-1:0] Bval = cin? ~Btmp : Btmp;





lpm_add_sub ALU (	.dataa (A), //full acc width
					.datab (Bval), //this one extended as well
					.cin (cin),
					.result (Q[AccWidth-2:0]),
					.cout (Q[AccWidth-1]));
	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;	
		
assign SignBit = Q[AccWidth-1];

endmodule



Опять же, по одному ЛЭ на бит уходит на сумматор, а ещё один - для инвертирования B, если понадобится. Но делать одно лишь инвертирование - как-то слишком расточительно, поэтому и сюда запихали константы. На данный момент - 3 штуки, причём и их самих можно инвертировать. А вообще, можно было бы 6 разных констант вмонстрячить, просто я пока не знаю, нужны ли мне они все. Пока мне нужны 3:
3/2 для нормировки вектора,
-3/2 для поддержания нормы кватерниона,
2 для метода Ньютона нахождения обратной величины.
Так-то и другие константы у нас были: веса для метрик Чебышева и Манхэттенской, преобразование из пикселей в радианы, и ышшо целых 12 коэффициентов для нахождения аффинного преобразования. Но отсюда их извлекать иногда даже сложнее получается, чем из памяти. А вот перечисленные 3 - очень полезно иметь здесь, потому что они категорически не влезают в 16 бит, и если хранить их в памяти, пришлось бы изобретать специальный вариант загрузки, или вообще "генерировать их на ходу", складывая несколько чисел поменьше!

Флаг знака как отдельный регистр нам нужен потому, что нам показалось удобным, если некоторые команды (как SUB, FMS) будут менять его, а другие (DIV2 и ABSP1D2) - НИ В КОЕМ СЛУЧАЕ НЕ ТРОГАТЬ! Тогда один конкретный момент упростился, может и в дальнейшем где-то окажется кстати.

На этой схеме уже видно, что АЛУ "встраивается" в процессор с архитектурой TTA. Мы видим 16-битный вход D, 16-битный выход Q (составляй мы это из отдельных микросхемок, скорее всего сделали бы двунаправленную шину, но ВНУТРИ ПЛИС двунаправленных шин и элементов с высокоимпедансным состоянием НЕТ. Хотя возможно, синтезатор и может сделать вид, что есть, заменив её на мультиплексор, но не хочу с ним бодаться лишний раз) - через них поступают числа, которые мы обрабатываем. Также есть 8-битный вход SrcAddr (адрес источника данных) и DestAddr (адрес получателя данных). Вместе они и образуют одну инструкцию процессора, по сути

MOV DestAddr SrcAddr (переместить данные от источника к получателю).

Для АЛУ, как в качестве источника данных, так и в качестве получателя, выделены адреса 0x80..0x9F, всего по 32 штуки.

Адресов Src пока что используется 3 штуки:
0x80 - Acc (Accumulator, аккумулятор)
0x82 - UAC (Unsigned Acc, беззнаковый акк.)
0x83 - C (регистр C).

В аккумуляторе мы храним результат вычислений, причём исходно там представимы числа от -2 почти до 2. Но мы имеем дело с числами формата 1.15 (1 бит перед запятой и 15 после неё), для которых диапазон представимых чисел от -1 почти до 1 для знаковых, и 0..2 для беззнаковых.

Когда мы обращаемся по адресу 0x80, на шину данных подаётся НАСЫЩЕННЫЙ ЗНАКОВЫЙ ответ. То есть, если в аккумуляторе оказалось число -1,5, то мы получим -1 (т.е 32768, 0x8000), а если было 1,05, то получим примерно 1 (т.е 32767, 0x7FFF), ну а если числа лежали в диапазоне от -1 до 1, то они будут выданы "как есть". "Насыщение" позволяет легко и непринуждённо обращаться с кватернионами, для которых это нормальная ситуация вблизи "нулевого поворота" (кватернион 1+0i+0j+0k), или поворотов на 180 градусов вокруг каждой из 3 осей (0+1i+0j+0k и так далее). Мы не можем записать единицу, только 1-2-15≈0,999969, если бы не было насыщения, то результатом отсечения старшего бита стало бы число -1 вместо +1, что изрядно фатально, когда прочие коэффициенты ненулевые. А так, максимальная ошибка ориентации из-за насыщения составляет менее угловой секунды, что гораздо меньше, чем ошибка 12 угловых секунд, вызванная низкой разрядностью чисел. А сделай мы формат 2.14, получили бы и вовсе ошибку в 24 угловых секунд...

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

И ещё в ходе написания программ оказалось, что в регистре C зачастую значение хранится довольно долго, поэтому в процедуре, которая вызывается из разных мест, неплохо бы уметь сохранять его в стек. Для этого используется адрес 0x82.

Модуль QuatCoreALUoutput как раз коммутирует на выход правильное значение. Вот его код:

[Spoiler (click to open)]
//Only 2 least-sign bits of SrcAddr matter:
//00 - Acc (signed with saturation)
//10 - UAC (unsigned)
//11 - C (to store C register into stack)

module QuatCoreALUoutput (input [7:0] SrcAddr, input [16:0] Acc, input [15:0] C, output [15:0] Q, output isOFLO);

assign isOFLO = (Acc[16] != Acc[15]);

wire [1:0] mode;
//00: Q = -32768
//01: Q = 32767
//10: Q = Acc[15:0]
//11: Q = C

assign mode[1] = SrcAddr[1] | ~isOFLO;
assign mode[0] = SrcAddr[1] & SrcAddr[0] | (~SrcAddr[1]) & (~Acc[15]) & Acc[16]; 

assign Q = (mode == 2'b00)? 16'h8000 :
           (mode == 2'b01)? 16'h7FFF :
           (mode == 2'b10)? Acc [15:0]:
			C;

endmodule

//theoretically, that's 1 LE for isOFLO, 
//                      2 LE for mode,
//                     16 LE for Q
// that is 19 LE...

//but synthesizer came up with 34, crazy bastard.



На его вход поступает 16-битный регистр C и старшие 17 бит регистра Acc. Далее, сравнивая два старших бита, получаем флаг переполнения isOFLO, и по ним же, в сочетании с младшими 2 битами адреса SrcAddr, определяем, что подать на выход.

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

И мы не стали проверять все 8 бит адреса SrcAddr: за первые 3 бита (которые указывают на АЛУ) отвечает мультиплексор QuatCoreSrcMux (см схему), а на следующие 3 нам плевать.

Видно, что если выбран адрес 0x82 (UAC, младшие биты 10), то заведомо mode = 10, и мы выдаём 16 бит с аккумулятора "без изменений". Точно так же, если выбран адрес 0x83 (C, младшие биты 11), то заведомо mode = 11, и мы выдаём регистр C.

А вот в случае адреса 0x80 (Acc), да и 0x81 (сработает точно так же), мы либо выдадим аккумулятор "как есть", либо выдадим правильное "насыщенное" значение.

И самое сложное во всём этом деле - модуль управления QuatCoreALUcontrol. Именно он должен воспринять DestAddr, и если там сидит один из адресов АЛУ, то выполнить соответсвующее действие. Всего мы пока "придумали" 21 команду, которые уже используются в ассемблерном коде. Значение, которое появляется на шине, назовём D (data):
ZACC - обнулить аккумулятор (т.е занести одно из 3 значений, доступных в Acc: 0, 1/2мл.разр или 1/2),
C - загрузить регистр C,
CACC - загрузить в аккумулятор одну из констант: 3/2, -3/2 или 2,
ACC - загрузить в аккумулятор значение D,
ADD - прибавить к ACC значение D,
SUB - вычесть из ACC значение D,
PM - либо прибавить, либо вычесть, в зависимости от флага Inv,
ABS - взять абсолютное значение от D,
DIV2 - поделить D на два, как знаковое число (оно же - арифметический сдвиг вправо),
UDIV2- поделить D на два, как беззнаковое число (логический сдвиг вправо)
MUL - знаковое умножение C на D,
SQR - знаковое возведение D в квадрат,
SQRAD2 - прибавить к аккумулятору D2/2,
SQRSD2 - вычесть из аккумулятора D2/2,
FMA - прибавить к аккумулятору C·D,
FMS - вычесть из аккумулятора C·D,
FMPM - либо прибавить, либо вычесть, в зависимости от флага Inv и регистров i,k,
MULSU - умножить беззнаковое C на знаковое D,
MULU - умножить беззнаковое C на беззнаковое D,
UFMS - беззнаково вычесть из аккумулятора беззнаковые C·D.

Часть из них можно свести к другим, например, вместо

SQR [X]

написать

C [X]
MUL [X]

а вместо

MUL [X]

написать

ZAcc 0
FMA [X]

и так далее, но пока не хочется...

Время выполнения команд - от 1 до 17 тактов. Мы пока решили слегка отойти от философии TTA, где все тайминги-на совести программиста (или, скорее, компилятора), дескать, мы "озадачили" АЛУ, а дальше, пока оно соображает - занимаемся другими делами, зная, что через 16 тактов результат будет готов - и можно его забрать. Как-то так оказалось, что имея одно АЛУ, ничем себя особо не займёшь, пока оно занято! Поэтому введён выход busy, который-таки останавливает процессор, пока мы не получим результат. Это не совсем оптимально в плане быстродействия - можно было бы придумать какие-то ухищрения, чтобы выцарапать сколько-то тактов тут и там, но пока не будем усложнять. Судя по всему, запас по быстродействию у нас имеется, эдак в 300 раз, хотя понятно - чуть-чуть ослабь хватку, сразу всё куда-то утечёт...

Как именно сделать модуль управления - пока не решил. Наиболее "лобовой" подход - ввести микрокод. Выходных воздействий у нас на 12 бит: 3 бита на аккумулятор, ещё 3 на сумматор, 2 на регистр B, 2 на регистр C, и ещё выходы Busy и "защёлкивание" флага знака. Но иногда они получают не заранее заготовленные значения, а достаются либо из шины данных, либо из знака результата (как при взятии модуля), либо по проводу PM (Plus-Minus). Это тоже не проблема - те воздействия, что зависят от внешних данных, "раздваиваются" или даже "учетверяются" в микрокоде, чтобы прописать реакцию на каждое из значений.

Но к микрокоду как-то душа не лежит, кажется, что можно тут всё комбинаторно прописать, надо только дать осмысленные адреса командам, чтобы их биты что-то значили и управляли почти "напрямую". Жаль только, задача это NP-сложная, как водится - можно до посинения ковыряться, вон как декодер для 7-сегментного индикатора вдруг в 2011 году сообразили как сделать!
Tags: ПЛИС, математика, работа, странные девайсы
Subscribe

  • Формулы приведения, что б их... (и atan на ТРЁХ умножениях)

    Формулу арктангенса на 4 умножениях ещё немножко оптимизировал с помощью алгоритма Ремеза: Ошибка уменьшилась с 4,9 до 4,65 угловой секунды, и…

  • Алгоритм Ремеза в экселе

    Вот и до него руки дошли, причина станет ясна в следующем посте. Изучать чужие библиотеки было лениво (в том же BOOSTе сам чёрт ногу сломит), писать…

  • atan на ЧЕТЫРЁХ умножениях

    Мишка такой человек — ему обязательно надо, чтоб от всего была польза. Когда у него бывают лишние деньги, он идёт в магазин и покупает какую-нибудь…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 5 comments