nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Испытания новой АЛУ, нахождение крена

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

;состояние регистров к этому моменту
;X = AffineMat (константная матрица 3х4, чтобы посчитать преобр)
;Y = Points2D
;Z = Matrix (матрица 2х2 и вектор 1х2, пока не AfTransf)
;i=j=k=0
;Inv неизвестен
;C, Acc - пофиг наверное
FindRoll	proc
	;нам понадобятся [Z]+[Z+3] и [Z+1]-[Z+2]
		Y		QuatY 	;в этом кватернионе построим,используя Y/Z значения как временные
					;(потом они занулятся)
					;а можно Y вместо X, если надо
		i		1
		j		3
@@sico:		Acc		[Z+i]
		Inv		i
		PM		[Z+i^j]
		[Y+i]		Acc
		iLOOP		@@sico
	
;теперь наших друзей надо отнормировать, причём динамический диапазон очень велик
;максимум 13 итераций, давайте столько и делать...
;здесь у нас появляется беззнаковое число, без него получалось бы очень грустно	

		CALL NormSiCo

;здесь у нас i=j=k=Inv=0
	
;теперь синус-косинус превращаем в кватернион, то есть в синус-косинус половинного угла
;если co>0, то
;QuatX = (1+abs(co))/2,
;QuatY = si/2
;в противном случае
;QuatX = si/2,
;QuatY = (1+abs(co))/2
	
;сейчас X = AffineMat (матрица 3х4, уже неактуальна)
;Y = QuatY (компоненты co / si),
;Z = Matrix (матрица 2х2 и вектор 1х2, к ним ещё вернёмся)
;i=j=k=Inv=0
					
		ABS		[Y+k]			
		DIV2		Acc
		ADD		16384

	;флаг S (sign) сейчас показывает знак co, что для нас очень полезно
		JGE		@@skip
		i		1		;выходит i=S
@@skip:		X		QuatA
		[X+i]		Acc
		j		1
		DIV2		[Y+1]
		Y		QuatA
		[X+i^j]		Acc		;по сути, Y+(~S)
		CALL		NormSiCo	;подготовили первые 2 компонента кватерниона
					
	;сейчас X=Y=QuatA (2 компоненты кватерниона),
	;Z = Matrix
	;теперь помножаем две матрицы, одна в явном виде - Matrix (Z)
	;вторая - задана неявно, в виде co / si (в QuatY)
	;результат идет в AfTransf
	;здесь i=1, k неизвестен, j=0, Inv=0
		Y		QuatY
		X		AfTransf	;сюда результат складируем
		i		1	;номер строки результата, и строки co/si
@@i_loop:	k		1	;номер столбца результата, и столбца AfTransf
@@k_loop:	j		1	;номер столбца co/si и строки AfTransf
		ZAcc		RoundZero	;обнулить до 1/2 мл. разр
@@j_loop:	C		[Y+i^j]	
		FMPM		[Z+2j+k]
		jLOOP		@@j_loop
		[X+2i+k]	Acc
		kLOOP		@@k_loop
		iLOOP		@@i_loop

	;здесь у нас i=j=k=0
	;теперь у нас должна получиться матрица, включающая в себя масштаб и ракурс (ужатие вдоль некоторой оси), но не крен...
	;ещё кватернион подчистим - по Y,Z может лежать всякий мусор
		[Y+k]		0
		[Y+1]		0
	FindRoll	endp


Как обычно, сначала прикинем, как можно этот код "оптимизировать" под новое АЛУ, не увеличивая его размера, и сравним выполнение на старом и новом АЛУ.



В самом начале нам нужно посчитать два выражения:
[Y]   = [Z]   + [Z+3] (сложить два элемента по главной диагонали матрицы),
[Y+1] = [Z+1] - [Z+2] (оставшиеся два элемента: вычесть один из другого)

Первая компонента будет пропорциональна косинусу, вторая - синусу. И останется этот вектор отнормировать.

Выполнить такие выражения в цикле нелегко, но мы всё-таки умудрились :) Чтобы изменить знак операции, применили регистр Inv и команду PM (Plus-Minus), а чтобы подобрать правильный индекс второго операнда, выставили j=3 и применили укуренную адресацию [Z+i^j].

Но не факт, что здесь был смысл. Как мы "обнаружили" в раз, два, три, четыре, пять, "произвольная адресация" вполне возможна. Там мы решили, что будет k=0, j=1. Что радостно, перед началом процедуры FindRoll мы точно знаем, что i=j=k=0 - это всё были индексы при умножении матриц, и все они дошли до нуля. Так что k=0 ставить не надо. Так что можно в кои-то веки "развернуть цикл":

Y     QuatY
j     1
Acc   [Z+k]
ADD   [Z+2j+1]
[Y+k] Acc
Acc   [Z+1]
SUB   [Z+2j+k]
[Y+1] Acc


Строк осталось как будто столько же: 8. Но увы, тут возникает Hazard, одновременное чтение из памяти [Z+1] и запись в [Y+k], поэтому компилятор всунет туда NOP. Именно этим обычно и оканчивается у нас Loop Unrolling: перегрузкой шины памяти. Так что всё-таки оставим цикл.

АЛУ выполняет команду Acc три такта. На первом из них параллельно мы загружаем регистр i на шину данных. На втором, запихиваем значение i в регистр Inv и начинаем выборку [Z+i^j]. На третьем, выборка [Z+i^j] завершается, и к команде PM АЛУ уже возвращается в состояние sIdle, т.е в кои-то веки не АЛУ нас тормозит!

А вот выполнения команды PM мы вынуждены дождаться, т.к результат сразу же пытаемся упихать в [Y+i]. Можем чуть подсластить пилюлю, перенеся "Y QuatY" аккурат перед "[Y+i] Acc", сэкономим один такт.

В целом, ожидаем экономии 5 тактов, что для этого небольшого куска довольно неплохо. В общем, как-то так:

	i	1
	j	3
@@sico:	Acc	[Z+i]
	Inv	i
	PM	[Z+i^j]
	Y	QuatY 	;в этом кватернионе построим,используя Y/Z значения как временные
			;(потом они занулятся)				
	[Y+i]	Acc
	iLOOP	@@sico


Далее вызывается процедура NormSiCo:

;по адресу Y лежит два числа, двухмерный вектор
;нужно его отнормировать.
;необходимо, чтобы i=0. 
;после завершения процедуры, i=j=0, значения в Acc и C меняются
NormSiCo 	proc
		j	12 ;если "передавать" j как аргумент, то можно регулировать число итераций
;при первом вызове нужно 13 итераций, при втором хватило бы и 6 итераций,
;но мы пока пытаемся оптимизировать по памяти кода, а не по быстродействию
;по быстродействию запас в 300 раз пока что...
@@norm:		ZAcc	ThreeHalf		;выставить 3/2
		SQRSD2	[Y+1]
		SQRSD2	[Y+i]	;вычесть половину от квадрата 
		;теперь на содержимое аккумулятора надо домножить Si и Co
		i	1
		C	UAC
@@inmult:	MULSU	[Y+i]	;умножение знакового B на беззнак. C
		[Y+i]	Acc		;вернули на место!
		iLOOP	@@inmult		
		jLOOP	@@norm
		JMP	[--SP]
NormSiCo	endp


Тут мы помещаем в аккумулятор "специальное" значение 3/2 (выполняется за 1 такт), затем вычитаем половинку квадрата от первого числа, "косинуса". Тут же переходим на вторую команду, вычесть половинку квадрата от второго числа, "синуса", и начинаем ждать выполнения первой, 18 тактов. На последнем, 19-м, начинает выполняться вторая команда, и выполнение пока продолжается. Мы успеваем присвоить i=1, а вот на UAC честно ждём окончания работы. Логично, никуда не денешься.

У меня такое ощущение, что здесь мы выигрываем ровно 1 такт на каждой итерации, больно всё неудачно: сразу после вычисления мы запрашиваем результат, а последующие прыжки по циклам и выборки из памяти отдельно отжирают такты. Итого, ожидаю 13 тактов (по числу итераций) при первом вызове NormSiCo и столько же на втором. Итого, на текущий момент, 31 такт.

Далее начинаем вычислять кватернион
	ABS	[Y+k]			
	DIV2	Acc
	ADD	16384
	JGE	@@skip
	i	1		;выходит i=S
@@skip:	X	QuatA
	[X+i]	Acc
	j	1
	DIV2	[Y+1]
	Y	QuatA
	[X+i^j]	Acc			;по сути, Y+(~S)
	CALL	NormSiCo	;подготовили первые 2 компонента кватерниона

На первой строке никакого выигрыша, т.к всё равно честно ждём окончания работы на второй. А вот ADD запускается тактом раньше, и третий свой такт "делит" с JGE. К тому времени, как мы запрашиваем Acc, давным-давно всё сделано. Т.е экономия 2 такта на "ADD".

Далее, DIV2 делит один такт со следующей командой, "Y", но потом ещё на два такта застреваем, когда запрашивается Acc. Но их тут отыграть непросто: DIV2 должен идти после "[X+i] Acc", чтобы не потерять ранее вычисленное значение, но не может идти непосредственно под ним, т.к будет одновременное чтение и запись в память.

Похоже, здесь 4 такта ещё выцарапывается, итого 35 тактов :)

И наконец, умножение матрицы на "виртуальную" матрицу поворота.

Виртуальная - потому что в явном виде мы её так и не записали, формируем "на ходу" с помощью инструкций FMPM и адресации [Y+i^j]:

		Y		QuatY
		X		AfTransf	;сюда результат складируем
		i		1		;номер строки результата, и строки co/si
@@i_loop:	k		1		;номер столбца результата, и столбца AfTransf
@@k_loop:	j		1		;номер столбца co/si и строки AfTransf
		ZAcc		RoundZero	;обнулить до 1/2 мл. разр
@@j_loop:	C		[Y+i^j]	
		FMPM		[Z+2j+k]
		jLOOP		@@j_loop
		[X+2i+k]	Acc
		kLOOP		@@k_loop
		iLOOP		@@i_loop


Тут всё неплохо: команды во внутреннем цикле выполняются 8 раз. 4 раза из них, когда происходит прыжок по jLOOP, на выполнение уходит 18 тактов (FMPM) вместо 24, как мы уже выяснили в прошлый раз, что даёт экономию в 24 такта. И ещё традиционно можно выиграть один такт, если регистр X (сейчас он выступает как адрес для РЕЗУЛЬТАТОВ) инициализировать сразу после внутреннего цикла:
		Y		QuatY
		i		1		;номер строки результата, и строки co/si
@@i_loop:	k		1		;номер столбца результата, и столбца AfTransf
@@k_loop:	j		1		;номер столбца co/si и строки AfTransf
		ZAcc		RoundZero	;обнулить до 1/2 мл. разр
@@j_loop:	C		[Y+i^j]	
		FMPM		[Z+2j+k]
		jLOOP		@@j_loop
		X		AfTransf	;сюда результат складируем
		[X+2i+k]	Acc
		kLOOP		@@k_loop
		iLOOP		@@i_loop


Итак, в общей сложности ожидаем 60 тактов экономии.

Запустим это дело на старом АЛУ. Начинается выполнение на T=86,43 мкс, заканчивается на 192,24 мкс. Выполняется 105,81 мкс, или 2645 тактов, больше, чем все предыдущие этапы вместе взятые! Причём добавлением 1 строки можно это время снизить сразу эдак на четверть (задать вдвое меньше итераций на втором вызове NormSiCo, т.к известно что сойдётся быстрее), но мы очень жадные :) А уж если нормировку сделать поумнее (сначала отмасштабировать обычными двоичными сдвигами, и лишь потом добить методом Ньютона), то вообще халява. Но мы никуда не спешим на самом деле :) По ТЗ, задержка измерений не должна превысить 200 мс.

А теперь на новом АЛУ. Начинается выполнение на T=78,6 мкс. Поначалу всё хорошо, находим те же "синус и косинус", что и раньше: -1 и 872. Запускаем нормировку - и там просто КОМБО, две ошибки подряд!

Вот первая:


это в двух строчках,
A3  94D4  @@inmult:   MULSU       [Y+i]   ;уможение знакового B на беззнак. C
A4  D480              [Y+i]       Acc     ;вернули на место!


Команда умножения MULSU (MULtiply Signed-Unsigned) и Acc (получить результат на шину данных) выполняются одновременно. По логике, мы должны остановиться и всё сосчитать, но на деле выполнение происходит за 1 такт, из-за чего на шину выдаётся СТАРОЕ значение из акк, примерно 3/2. Это полнейший криминал!

Почему так случилось - мне понятно. У нас Busy = ~isIdle, только вот состояние меняется по фронту тактовой частоты, а на первом такте у нас пока остаётся sIdle. И ровно сейчас нам так "повезло", что АЛУ был свободен. Тут явно нужна ещё "комбинаторная добавка".

А чуть позже возникла и ещё одна ошибка. На скриншоте выше видно, что на следующей паре "MULSU - Acc" сначала высветилось SrcStall, т.е АЛУ вовсю доделывает предыдущее умножение. И вот он это доделал, сразу же, не возвращаясь в sIdle, взялся за следующее умножение, благодаря чему теперь пошло DestStall - вот сейчас мы ЖДЁМ результата. По логике вещей, сейчас результат должен быть верным, умножение 872 на 3/2, т.е 1308 = 0x51C. А что же у нас на деле:


Вместо 1308 вышло 654 = 0x28E, ровно вдвое меньше. То есть, регистр C к началу следующего умножения не успел циклически сдвинуться в исходное состояние.

Ещё раз глянем на код, управляющий регистром C:
//Cmode=0x - idle
//	10 - shift
//	11 - load
wire LoadCCommand = isOurAddr & DestAddr[3] & (((~DestAddr[4])&(~DestAddr[2])&DestAddr[1])|(DestAddr[4]&DestAddr[2]));
assign Cmode[1] = (isIdle | isAdd | finished)? LoadCCommand : isMult;								
assign Cmode[0] = (~isMult) | (finished & LoadCCommand);


В этот раз проблема в старшем бите, Cmode[1]. Когда LoadCCommand = 1 (т.е нас ожидает команда, которая загружает новое значение в регистр C), всё работает правильно, мы последний сдвиг заменяем на загрузку.

А вот если LoadCCommand = 0, то на последнем такте умножения возникает проблема, вместо сдвига (10) мы просто ничего не делаем (00).

Получается, что конкретно при finished = 1, Cmode[1] всегда должно быть единичкой. То есть, вот так:

//Cmode=0x - idle
//	10 - shift
//	11 - load
wire LoadCCommand = isOurAddr & DestAddr[3] & (((~DestAddr[4])&(~DestAddr[2])&DestAddr[1])|(DestAddr[4]&DestAddr[2]));
assign Cmode[1] = finished | ((isIdle | isAdd)? LoadCCommand : isMult);								
assign Cmode[0] = (~isMult) | (finished & LoadCCommand);


Забавный код :) Давайте отсинтезируем и посмотрим, что из этого вышло. Во-первых, модуль PipelineALUcontrol, когда-то мы радостно вернулись к 42 ЛЭ, а сейчас он занимает 45 ЛЭ, обидно. Ну и смотрим, ушла ли ошибка:


Теперь правильно! И теперь ещё первую ошибку надо исправить. По-моему, вот так:
assign Busy = (~isIdle) | isOurAddr;


Сейчас глянем:


Да, всё в порядке. Выполняется безошибочно, и заканчивается выполнение на T=182,08 мкс.

Итого, данная процедура выполняется 103,48 мкс, или 2587 тактов, на 58 тактов меньше. Похоже на правду. В этой процедуре получили улучшение всего лишь 2%, а всего от начала выполнения: 5%. Да, бывает и так.


Что ж, целых две ошибки обнаружили - обе исправили. Выполнение самую чуточку ускорилось, и то хлеб.

Следующая часть: измерение масштаба.
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

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

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

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

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

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

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

  • Ковыряемся с сантехникой

    Наконец-то закрыл сколько-нибудь пристойно трубы, подводящие к смесителю, в квартире в Москве: А в воскресенье побывал на даче, там очередная…

  • Мартовское велосипедное

    Продолжаю кататься на работу и с работы на велосипеде, а также в РКК Энергию и на дачу. Хотя на две недели случился перерыв, очередная поломка,…

  • Обнаружение на новом GPU - первые 16 мс

    Закончилась симуляция. UFLO и OFLO ни разу не возникли, что не может не радовать. За это время мы дошли до строки 0x10F = 271. Поглядим дамп памяти:…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments