nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Quat Core Lite идёт на взлёт

Что нам стоит проц построить? Нарисуем - и прошьём!

Сейчас вожусь - хочу реализовать на ПЛИС простенькое вычислительное ядро, "заточенное" под операции с кватернионами. Если что-то адекватное получится, попробую это дело красиво описать и добавить в "Ликбез по кватернионам". Почему именно ПЛИС - а потому что мне в любом случае надо обрабатывать видеопоток, идущий с фотоприёмной матрицы, да и управляющие сигналы на эту матрицу подавать, тут ПЛИС процессоры положит на лопатки. На нём же хочу реализовать протокольный контроллер МКО (Mil-std 1553), и здесь же, по остаточному принципу - вычислительное ядро, которое будет по увиденному на видео (довольно простая картина - набор ярких точек) решить задачу ориентации в пространстве. Довольно неторопливо, и по моим прикидкам достаточно около 8 000 умножений и столько же сложений в секунду, поэтому супер-мега аппаратные умножители, работающие за один такт мне не нужны. Куда больше в приоритете - не занять все доступные ресурсы в плане логических ячеек (LE) и встроенной памяти.

Не удивлюсь, если именно так лучше всего строить звёздные датчики :)

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

Зато название уже есть: Quat Core, сокращённо от Quaternion Core!

QuatCoreExecutionBlock.png

На схеме - "исполнительное устройство", содержащее в себе 3 регистра, простенькое АЛУ и комбинаторные декодеры команд.



Сверху, примерно в центре композиции - регистр A (аккумулятор). Внезапно - 23-битный.

В каждый такт можно сделать одно из 4 действий:
- не трогать значение аккумулятора, пущай хранится
- занести в него результат работы АЛУ
- "обнулить" до значения 32 (1000002)
- присвоить значение 01100000 00000000 00000002

[Код на verilog]
//аккумулятор для перемножения и сложения 16-битных чисел.
//чтобы все 16 выходных бит были точны, аккумулятор должен иметь дополнительные биты точности
//в зависимости от того, как будет осуществляться сдвиг вправо (будут ли правила округления),
//число бит будет меняться

//судя по всему, 22-23 бит должно хватить
`include "QuatCoreConfig.v"

//в конфиге нас интересует следующее:
//`define AccWidth 23
//`define amIdle		2'b00
//`define amClear		2'b01
//`define amSum			2'b10
//`define amOneAndHalf	2'b11

module Acc(input [`AccWidth - 1 : 0] D,
		input clk,
		input [1:0] mode,
		output reg [`AccWidth - 1 : 0] Q,
		output overflow);

	assign overflow = Q[`AccWidth - 1] ^ Q[`AccWidth - 2];

	always @(posedge clk) begin
		Q <= 	(mode == `amIdle)?  	Q:
			(mode == `amClear)? 	1'b1 << (`AccWidth - 18):
			(mode == `amSum)?	D:
						{3'b011, {`AccWidth - 3{1'b0}}};
	//заносим значение 1.5 - для нормировки. Так просто его сюда не запихнёшь!
	end
endmodule




Первая странность - совершенно нестандартное число бит. Объяснение таково: в памяти я хочу хранить 16-битные значения, т.к память всё-таки реализуется в виде готового блока, где можно адресовать 1, 2, 4, 8 или 16 бит. Именно 16 бит мне вполне хватит для обеспечения нужной точности, и по МКО результаты вычислений передавать удобно.

Хочу, чтобы при вычислениях точность в 16 бит поддерживалась (даже в младшем бите не содержалось бы ошибки), и для этого аккумулятор, в котором накапливается результат от 3-4 умножений 16-битных чисел, должен быть чуточку ширше. Здесь ПЛИС нет дела до круглых чисел - всё равно регистры, как и шины, набираются буквально по битам. Один LE (Logic Element, мне почему-то нравится переводить "логическая ячейка", чтобы не путать с вентилями) - 1 бит памяти.

Вторая странность - на выход подаются 16 бит из этих 23, причём взятые ИЗ СЕРЕДИНЫ. Если вся шина - 22:0, то нас интересует 21:6, т.е верхний бит мы выкидываем.

Оказывается, что при знаковом умножении именно эти 16 бит нам и нужны! Когда мы умножаем два 16-битных числа со знаком, результат ПОЧТИ умещается в 31 бит, лишь одно единственное значение, результат умножения -32768 на -32768, заставляет добавить ещё один, самый старший бит. В итоге мы имеем почти что двукратный запас по диапазону представимых значений, что весьма полезно. Именно это одно значение, не влезающее в 31 бит - в итоге не может быть представлено в заданном нами формате для кватернионов, 1.15 (один бит перед запятой, 15 -после запятой, число со знаком). И это самое важное число - единица!

Просто зашибись - каждый компонент кватерниона может принимать значения от -1 до 1-2-15, то есть единичный кватернион, самый простой, самый очевидный, соответствующий нулевому повороту - выразить нельзя!

Но это не страшно - ведь тому же повороту соответствует кватернион (-1) - вот он ещё как представим! В 23 битах аккумулятора представимы они все, и это не может не радовать. Мы можем спокойненько посчитать кватернион, а если по окончании работы у нас выставится флаг overflow (который в нашей реализации вовсе не утверждает, что результат, лежащий в аккумуляторе, неверен. Всё там хорошо, но в 16 бит выхода уже не влезет), то мы все компоненты помножим на -1 (произведём дополнение, это очень простая операция - инвертировать все биты и прибавить единицу), получив кватернион, выражающий тот же самый поворот, но теперь уже представимый.

Также в аккумулятор нельзя загрузить какое-либо значение из памяти. Можно как будто бы "обнулить", но в действительности записать значение 32. Либо, если вам не нравится 32, то значение 01100000 00000000 00000002.

И в этом есть сермяжная правда. Мы начинаем счет не с нуля, а с 32, чтобы отбрасывание младших разрядов (когда из 23 бит берёшь только 16) соответствовало округлению не "вниз" (в английской терминологии - towards minus infinity, это чтобы не путать с округлением "в сторону нуля", как при целочисленном делении), а "до ближайшего целого". Лишний бит точности на дороге не валяется и ничего нам не стоит - "обнулить" до 32 ничуть не сложнее, чем до нуля.

Второе значение, 01100000 00000000 00000002 - это число 3/2, которое нам необходимо для нормировки векторов и кватернионов. Оно не вмещается в 16-битное представление 1.15, зато вольготно себя чувствует в аккумуляторе. Остаётся вычесть из него половину от суммы квадратов действительной и мнимых частей, чтобы получить нормирующий множитель.

Аккумулятор занимает 25 логических ячеек ПЛИС, из 9984 доступных.

Справа от аккумулятора находится 23-битное АЛУ, весьма примитивное на данный момент.
Умеет всего 3 операции:
C = A+B
C = A-B
C = -A.

[Код на verilog]
//какая-то фигня у нас с АЛУ - либо оно раздувается аж до 115 ЛЭ, либо вываливает warning'и об игнорировании CARRY_SUM. 

//фух, сделали худо-бедно - 69 ЛЭ
//по сути, либо A+B, либо A-B, либо -A 

`include "QuatCoreConfig.v"
//нас в конфиге интересуют следующие строки:
//`define AccWidth 23
//`define AplusB 	2'b00
//`define AminusB	2'b01
//`define minusA	2'b10

module AddC (	input [`AccWidth - 1 : 0] A,
		input [`AccWidth - 1 : 0] B,
		input [1:0] mode,
		output [`AccWidth - 1 : 0] C);


	wire cin, NegA, NegB, ZeroB;
	wire [`AccWidth - 1 : 0] Amod;
	wire [`AccWidth - 1 : 0] Bmod;
	
	assign cin = mode[1] | mode[0];
	assign NegA = mode[0];
	assign NegB = mode[1];
	assign ZeroB = mode[1];
	
	assign Amod = 	NegA? ~A : A;
	assign Bmod = 	ZeroB? 1'b0 :
			NegB? ~B : B;
	

	assign C = Amod + Bmod + cin;

endmodule




Тут вроде всё понятно. Обычно мы обнуляем регистр A (аккумулятор) и начинаем накапливать в нём результат, какие-то числа прибавляя, другие вычитая, для чего нужны первые два режима.
Отрицание же нужно как раз для того, чтобы поменять кватерниону знак, если он вдруг "не помещается".

Довольно странный код вызван тем, что я мучительно пытался впихнуть это АЛУ в наименьшее количество логических ячеек, а Quartus этому противился как мог. В самом простом коде "либо прибавь, либо отними, либо обрати" он не сумел распознать сумматор, как основу, все ячейки настроил в "нормальный режим", и получилось их 115 штук - явный перебор! В том варианте, как сейчас, в последней строке программа наконец-то поняла, что это же обычный сумматор с входным битом переноса, и перевела 23 логических ячейки в режим сумматора, когда одна таблица (LUT) с 4 входами и 1 выходом перенастраивается в две таблицы с 3 входами и 2 выходами - один выход на текущий бит, второй - перенос.

Увы, ещё по 23 лог. ячейки понадобилось, чтобы при необходимости инвертировать вход A и инвертировать, либо занулить вход B, итого 69 штук.

Некоторые танцы с бубном как будто бы заставили упихать АЛУ в 46 логических ячеек, но полезли предупреждения, что выходы Carry-sum у всех 23 бит сумматора игнорируются - каждая логическая ячейка вроде способна выполнить операции, но скоммутировать их не выходит - не хватает проводов!

Ну да ладно, не обеднею.

Ровно в центре композиции сдвиговый регистр B.

Он 23-битный, но загрузить можно только 16 бит, и опять посерединке, с расширением знака (старший бит 22 принимает то же значение, что в бите 21).

3 режима работы:
- хранить значение
- загрузить данные
- осуществить арифметический сдвиг вправо.

[Код на verilog]
//есть мнение, что сдвиговый регистр гораздо лучше подходит для последовательного умножения, чем комбинаторный сдвигатель (barrel shifter)
//экономим толпу LE


`include "QuatCoreConfig.v"
//`define AccWidth 23
//`define bmIdle 		2'b00
//`define bmLoad 		2'b01
//`define bmShift 		2'b10


module ShiftRegister (input [15:0] D, input [1:0] mode, input clk, output reg [`AccWidth - 1 : 0] Q);
 
	always @(posedge clk) begin
		Q <= 	(mode == `bmIdle)? 	Q:
			(mode == `bmLoad)? 	{D[15], D[15:0], {`AccWidth - 17{1'b0}} }:
			(mode == `bmShift)?	{Q[`AccWidth - 1], Q[`AccWidth - 1 : 1]}:
						{`AccWidth{1'bx}};
				
	end
endmodule




Если не использовать сдвиг, то его можно припахать для сложений-вычитаний. Со сдвигом это получается компонент умножителя. Как учили в школе, столбиком. Мы никуда не торопимся, потерпеть 16 тактов - не вопрос.

Занимает всё так же 25 логических ячеек - дешево и сердито.

Ещё ниже - регистр циклического сдвига C.

Опять 3 режима - хранение, загрузка и циклический сдвиг вправо на 1.

Но в этот раз регистр 16-разрядный, а на выход подаётся вообще только старший бит.

Кроме того, внутри сидит счетчик от 15 вниз до 0. Когда загружаешь в регистр новое значение, счетчик сбрасывается в 15, а при каждом сдвиге уменьшает значение на 1. Имеется ещё два выхода. На один подаётся лог "1", когда на счетчике число 15, на второй - когда 1. Почему 1, а не ноль...

[Код на verilog]
//один из регистров сдвигает строго вправо, это первый множитель
//а сюда мы заносим второй множитель. Всё, что нам надо - получать старшие биты, один за другим,
//и при этом не потерять данные - они нам ещё пригодятся!

//в BitArrayRegister мы просто хранили данные и мультиплексировали все 16 бит в 1 выход,
//но циклический сдвиг - более экономичный. Поскольку мы хотим уже 4 таких модулька, то надо экономить!

`include "QuatCoreConfig.v"
//`define AccWidth 23
//`define cmIdle	2'b00
//`define cmLoad	2'b01
//`define cmShift	2'b10


module CircularShiftRegister16(	input [15:0] D,
				input clk,
				input [1:0] mode,
				output Q,
				output isOne,
				output isNeg);

	reg [15:0] dat; //сдвиговый регистр
	reg [3:0] cnt; //счетчик

	assign Q = dat[15];	//выдаём только старший бит
	assign isOne = (cnt == 1'b1);	 //значит, умножение почти завершено - остался один шаг, при котором мы можем уже припахать другие модули
	assign isNeg = (cnt == 4'b1111); //только-только загрузили, и сейчас у нас бит "знака"

	always @(posedge clk) begin
		dat <= 	(mode == `cmIdle)? 	dat:
			(mode == `cmLoad)? 	D:
			(mode == `cmShift)? 	{dat[14:0], dat[15]}:
						{16{1'bx}}; //означает - ставьте что хотите, нам плевать!
		cnt <= 	(mode == `cmIdle)? 	cnt:
			(mode == `cmLoad)? 	4'b1111:
			(mode == `cmShift)? 	cnt - 1'b1:
						{4{1'bx}}; //может хоть счетчик обнулим
	end

endmodule




В этот регистр заносится второй множитель, который мы должны просмотреть бит за битом. Если бит нулевой - надо запретить аккмулятору счет на этом такте, именно этим занимается выход Q. Если смотрим на самый старший бит - нужно сменить знак при умножении, поскольку мы работаем в дополнительном коде, для этого нужен выход isNeg.

На время умножения счетчик инструкций останавливается, а потом его надо запустить вновь, причем команду на запуск надо дать заблаговременно, потому что штука тормознутая. Увы, оперативная память в ПЛИС имеет "защёлку" и на входе, и на выходе, поэтому между запросом нужного адреса и получением данных проходит два такта. Оттого мы и не ждём обнуления счетчика - нам нужно "конвейер" запускать! Не уверен пока, что мне нужно подавать сигнал на запуск именно по единице, скорее всего, ещё раньше. И ещё наблюдение - на последнем шаге умножения мы уже можем загрузить в регистры B, C новые значения - в умножении-то будут ещё использоваться старые!

По завершении цикла умножения содержимое регистра C возвращается в исходное состояние, что может быть полезным.

И остаётся два декодера.
Декодер команд АЛУ (в действительности, связки АЛУ-аккумулятор) ещё и реализует логику умножения знаковых чисел.

На вход исполнительного устройства приходит код операции, один из 8 возможных:
- ничего не делать
- "обнулить" аккумулятор (A = 0)
- сложение (A = A + B)
- вычитание (A = A - B)
- такт умножения с накоплением (A = A + B * C[15])
- такт умножения с накоплением, обратный знак (A = A - B * C[15])
- загрузить значение 1,5 (A = 1.5)
- поменять знак (A = -A)

[Код на verilog]
//дешифратор команд на "АЛУ" (точнее, АЛУ плюс регистр-аккумулятор)

`include "QuatCoreConfig.v"
//`define AccWidth 23

//`define amIdle	2'b00
//`define amClear	2'b01
//`define amSum		2'b10
//`define amOneAndHalf	2'b11

//`define AplusB 	2'b00
//`define AminusB	2'b01
//`define minusA	2'b10

//`define ALUidle	3'b000
//`define ALUclear	3'b001
//`define ALUplus	3'b010
//`define ALUminus	3'b011
//`define ALUmul	3'b100
//`define ALUmulNeg	3'b101
//`define ALUoneAndHalf	3'b110
//`define ALUnegate	3'b111




module ALUOpDecoder(	input [2:0] ALUOpCode,
			input MulInput,
			input MulIsNeg,
			output [1:0] AMode,
			output [1:0] ALUmode);
							
	assign AMode = 	(ALUOpCode == `ALUidle)? 	`amIdle:
			(ALUOpCode == `ALUclear)? 	`amClear:
			(ALUOpCode == `ALUplus)? 	`amSum:
			(ALUOpCode == `ALUminus)? 	`amSum:
			(ALUOpCode == `ALUmul)?		(MulInput? `amSum : `amIdle):
			(ALUOpCode == `ALUmulNeg)? 	(MulInput? `amSum : `amIdle):
			(ALUOpCode == `ALUoneAndHalf)? 	`amOneAndHalf:
							`amSum; //ALUnegate
													
	assign ALUmode =(ALUOpCode == `ALUidle)? 	2'bxx:	//что угодно
			(ALUOpCode == `ALUclear)? 	2'bxx:
			(ALUOpCode == `ALUplus)? 	`AplusB:
			(ALUOpCode == `ALUminus)? 	`AminusB:
			(ALUOpCode == `ALUmul)? 	(MulIsNeg? `AplusB : `AminusB):
			(ALUOpCode == `ALUmulNeg)? 	(MulIsNeg? `AminusB : `AplusB):
			(ALUOpCode == `ALUoneAndHalf)? 	2'bxx:
							`minusA; //ALUnegate
	
endmodule



Всего 4 логических ячеек занимает, тупо по числу выходов.

Ну и второй - декодер инструкций для регистров B, C.

Всего 4 разных режима:
- ничего не делать
- загрузить данные в регистр B
- загрузить данные в регистр C, в это время сдвинув B вправо
- сдвинуть данные одновременно и в B, и в C.

[Код на Verilog]
//декодер команд управления регистрами B,C

`include "QuatCoreConfig.v"


module BCopDecoder(	input [1:0] BCop,
			output [1:0] Bmode,
			output [1:0] Cmode);
					

	assign Bmode = 	(BCop == `bcIdle)?  	`bmIdle:
			(BCop == `bcLoadB)? 	`bmLoad:
						`bmShift; //bcLoadCshiftB, bcShiftBshiftC
										
	assign Cmode =	(BCop == `bcIdle)?		`cmIdle:
			(BCop == `bcLoadB)?		`cmIdle:
			(BCop == `bcLoadCshiftB)?	`cmLoad:
							`cmShift; //bcShiftBshiftC

endmodule




Совсем простой, аж на 3 логических ячейки.

Опять меня душила жаба в плане количества инструкций. Я рассудил так: если уж задействуется регистр C, значит я хочу произвести умножение. Для этого мне нужны оба операнда. Мне без разницы, в каком порядке их загружать. Если они нужны мне в исходном виде, то первой пойдёт инструкция "загрузить C, сдвинуть B", а за ней - "загрузить B".

Зато при нормировке кватерниона, где надо посчитать выражение 3/2 - 1/2 (a2 + x2 + y2 + z2) я поменяю команды местами, и получу деление на два "на халяву".


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



Команды чрезвычайно низкоуровневые пока выходят, их в приличном обществе и кодом не назовут, скорее микрокодом :) На всё про всё ушло 153 логических ячейки, или 1,53% от общего числа.

Теперь уже хочется посложнее - всё-таки 4 параллельных вычислителя, с перекрещиванием входных операндов. Вот тогда получится с минимальными накладными расходами помножить кватернион на кватернион, да ещё и с нормировкой! По сути, выйдет по 16 тактов на выполнение 4 умножения и 4 сложения, то есть очень грубо - по 2 такта на операцию - весьма недурственно! Просто за логические ячейки (за их нехватку) я уже не боюсь, боюсь, что этот "микрокод" заполонит всю доступную память!

Увы, придётся на недельку эту деятельность приостановить и взяться изо всех сил за контроллер МКО. Если успею его реализовать до ближайшего понедельника, в качестве бонуса поеду в командировку в Снежинск, в РФЯЦ им. Забабахина :)


PS. 4 октября - начало космической эры. Ура, товарищи!
Tags: кватернионы-это просто (том 1), математика, работа, странные девайсы
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 

  • 24 comments

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

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

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

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

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

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