nabbla (nabbla1) wrote,
nabbla
nabbla1

Быстрый QuatCore: финал аффинного алгоритма

Крен посчитан, масштаб посчитан, осталось за малым - посчитать вектор параллельного переноса. Он же, но в сферических координатах - это дальность и "активные углы", тангаж и курс.

Для этого нужно найти величину, обратную к масштабу (по методу Ньютона), а затем домножить на неё двумерный вектор параллельного переноса, который мы нашли вместе с матрицей 2х2.

Мы это уже делали раз для гипотетического процессора, второй раз (раз, два) - для медленного. Могли бы просто "перекомпилить" под быстрый, но транслятор пока что справляется лишь с задачей выдать КОРРЕКТНЫЙ код, за что ему спасибо. Но самостоятельно оптимизировать его он пока не умеет. Вообще, можно было бы ввести эвристики, когда он обнаруживает команды, которые можно "безболезненно" поменять местами, и если это позволяет избавиться от Hazard - он так и сделает. Но, может, позже. А пока ручками поковыряемся.


Вот наш старый код:
	;состояние регистров:
	;X=AfTransf
	;Y=QuatY
	;Z=MetricW
	;i=k=0
	;j=Exp
	;Inv=1
	;Acc=Scale
	;C = 2*Acc (побоч эффект DIV2S)
	FindVector	proc
				k		3
				Z		ZeroInv
				C		[Z+i]	;наше нулевое приближение к обр. величине
		@@Newton:	Acc		0		;занести двойку
				UFMS		[SP]	;Acc = 2 - a * x
				MULU		UAC		;Acc = Acc * x = x * (2- a*x), т.е итерация метода Ньютона
				C		UAC
				kLOOP		@@Newton			
	;золотой ключик почти у нас в кармане
	;если на входе было 16384, то правильный результат 65536 не влезет в 16 бит, сократившись до нуля. 
	;это мы должны заметить по переполнению, только вот не соображу, оно должно ПОЯВИТЬСЯ, или исчезнуть?
				JGE		@@SkipOflo
				j++		0 			;раз не вмещается в мантиссу, значит добавим экспоненту, а в мантиссу нужно 32768 теперь.Ща найдём...
				ZAcc		MinusOne 	;вместо бесхозной минус двойки
		@@SkipOflo:	Z		Exp
				[Z+i]		j		
				Y		Tx
				[Y+i]		UAC
	;и ещё осталось найти Ty, Tz
				Y		Rx
				Z		Ty
				i		1
		@@Vec:		MULSU		[Y+i]
				[Z+i]		Acc
				iLOOP		@@Vec
	;ну вот и закончена 1-я часть марлезонского балета
	FindVector	endp


"Правила хорошего тона" в программировании просит инициализировать значения непосредственно перед применением, чтобы тому "счастливчику", который взглянет на этот код, не держать в голове, что вон тогда, 10 строк назад, мы выставили Z=ZeroInv. Но увы, такой код порождает Hazard'ы, так что приходится менять строки местами, инициализировать чуть загодя.

Так что меняем местами первые две строки,
				k		3
				Z		ZeroInv


Метод Ньютона не трогаем - хорошо, что в АЛУ поставили интерлок (блокировку), иначе тут повсюду стояли бы NOPы, очень много таких мест, где АЛУ напрямую использует значение из аккумулятора, перенаправляя его в регистры B,C.

Три строки, проверяющих переполнение (можно было бы их убрать, не сделай мы округление в прошлой процедуре), тоже в порядке.

Далее, 4 строки - помещаем экспоненту и мантиссу в память. Странно, зачем я разные регистры под это подрядил. Пусть Z указывает на Exp, т.е у меня в памяти они так лежат:

Exp	dw	?	;отдельно экспонента
Tx	dw	?	;Tx отдельно
Ty	Int16	?	;другие значения
Tz	Int16	?

QuatA	Int16	?	;кватернион взаимной ориентации
QuatX	Int16	?
QuatY	Int16	?
QuatZ	Int16	?


Это, по сути, вся информация, которая и нужна от нашего алгоритма. Пусть Z указывает в начало. А вот Y "запрягать" особого смысла нет. Сделаем так: строку

	Z		Exp

перенесём ещё перед проверкой на переполнение.

Затем, после проверки:
		@@SkipOflo:	[Z+i]		j						
				[Z+1]		UAC


Далее, мы умножаем двумерный вектор параллельного переноса на величину, обратную масштабу. Опять у нас цикл на 2 итерации, который легко избегается:

				Y		Rx
				X		Ty
				MULSU		[Y+i]
				[X+i]		Acc
				MULSU		[Y+1]
				[X+1]		Acc


Количество команд осталось тем же.

Правда, затем идёт возврат из процедуры AffineAlgorithm, и там возникает Hazard по обращению к памяти.

А знаете, что: давайте уберём вызов процедуры AffineAlgorithm, ни к чему он! Всунем прямо в main, но точно так же оставляя AffineAlgorithm proc / AffineAlgorithm endp. И сэкономим ещё 2 команды :)

Вот переработанный код FindVector:
	FindVector	proc
				Z		ZeroInv
				k		3
				C		[Z+i]	;наше нулевое приближение к обр. величине
		@@Newton:	Acc		0		;занести двойку
				UFMS		[SP]	;Acc = 2 - a * x
				MULU		UAC		;Acc = Acc * x = x * (2- a*x), т.е итерация метода Ньютона
				C		UAC
				kLOOP		@@Newton			
	;золотой ключик почти у нас в кармане
	;если на входе было 16384, то правильный результат 65536 не влезет в 16 бит, сократившись до нуля. 
	;это мы должны заметить по переполнению, только вот не соображу, оно должно ПОЯВИТЬСЯ, или исчезнуть?
				Z		Exp	
				JGE		@@SkipOflo
				j++		0 			;раз не вмещается в мантиссу, значит добавим экспоненту, а в мантиссу нужно 32768 теперь.Ща найдём...
				ZAcc		MinusOne 	;вместо бесхозной минус двойки
		@@SkipOflo:	[Z+i]		j						
				[Z+1]		UAC
	;и ещё осталось найти Ty, Tz
				Y		Rx
				X		Ty
				MULSU		[Y+i]
				[X+i]		Acc
				MULSU		[Y+1]
				[X+1]		Acc
	;ну вот и закончена 1-я часть марлезонского балета
	FindVector	endp	


Попробуем откомпилировать.
Выскакивает ошибка:


В принципе, я её ожидал. И готово решение, заменяем

@@endless:  JMP  @@endless


на

@@endless:  JNO  @@endless


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

Теперь бдительный транслятор находит следующее:

Конфликт (Hazard) между командами [X+i] и [Y+1], процедура FindVector, строки:
				[X+i]		Acc
				MULSU		[Y+1]
Вставляем NOP


Хорошо всё-таки, что реализовал это дело, у меня взгляд замыливается, а у него - нет :)

Ну да, приятно бывает цикл "развернуть", но тогда начинаем слишком резво к памяти обращаться. "Свернём"-ка его обратно:
				i		1
				Y		Rx
				X		Ty
		@@vector:	MULSU		[Y+i]
				[X+i]		Acc
				iLOOP		@@vector


Да, теперь Hazard'ов не возникает:

Загружаем файл конфигурации транслятора
Файл конфигурации прочитан, готовы к работе
Обрабатываем файл OurProgramForFastCPU.asm
Пытаемся оптимизировать таблицу вызова процедур
NormSiCo    = 00A2 
ShiftOrigin = 009A 
SwapPoints  = 0093 

Бит 7 адреса
Всегда единица...
Бит 6 адреса
Всегда ноль...
Бит 5 адреса
не повторяет предыдущих (сигнатура 4)
Сопоставление его биту SrcAddr[3] прошло успешно
Бит 4 адреса
не повторяет предыдущих (сигнатура 3)
Сопоставление его биту SrcAddr[2] прошло успешно
Бит 3 адреса
не повторяет предыдущих (сигнатура 2)
Сопоставление его биту SrcAddr[1] прошло успешно
Бит 2 адреса
Всегда ноль...
Бит 1 адреса
Всегда единица...
Бит 0 адреса
не повторяет предыдущих (сигнатура 1)
Сопоставление его биту SrcAddr[0] прошло успешно
Компиляция завершена успешно

Ширина адреса сегмента кода (и регистра PC):           8   
Ширина адреса сегмента данных (и регистров X,Y,Z,SP):  8   
Количество инициализированных слов данных:             189 
Количество инициализированных слов кода:               173 
Количество адресов процедур:                           3   

Адреса процедур:
NormSiCo    = 00A2(поле Src = B8) 
ShiftOrigin = 009A(поле Src = B6) 
SwapPoints  = 0093(поле Src = B5) 


И в очередной раз удаётся построить QuatCoreCallTable без единого ЛЭ. Кстати, подумал немного - это всё-таки везение. Очень легко придумать 4 адреса по 8 бит, для которых понадобится 4 ЛЭ, как ни расставляй:

0000_0001
0001_1110
0110_0110
1010_1010

Вот и всё: ни один разряд не является всегда нулём или всегда единицей, ни один не повторяется.

Запускаем синтез.
Fitter серьёзно задумался, но всё сделал, предельная частота в этот раз 25,32 МГц. Ладно, сойдёт пока, для сельской местности.

Запускаем симуляцию



Получился кватернион 32767 - 1i + 0j + 0k - то же самое, что и раньше.
И вектор (38377; -26 ; 2) / 32768 * 2(9-1) метров.

Точнее, пока мы представляем Y,Z с вдвое большим масштабом, но потом страшно неудобно получается вектора поворачивать, когда масштабы по разным осям не совпадают! Не знаю пока, что с этим делать. В простейшем случае - всё к одному масштабу привести, но, может быть, чуть позже.


Ура, работает. На всё про всё 209 мкс, вместо старых 1,15 мс - улучшение в 5,5 раз. И что самое удивительное, размер программы при этом уменьшили со 182 слов кода до 173.

Отступать некуда - пора повторно подружить QuatCore со своей периферией, а потом подключать камеру :) Собственно, всё ковыряние с ускорением вызвано было нежеланием использовать две тактовые частоты, 25 МГц под видео и 4 МГц для процессора, и нагромождать хитрые цепи синхронизации между двумя (crossing clock domains). Эта эпопея началась 12 марта, чуть больше месяца назад. Конечно, я надеялся, что управлюсь за недельку-другую, но ладно, и так нормально.
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

Recent Posts from This Journal

  • Так ли страшно 0,99969 вместо 1?

    В размышлениях о DMA, о возможных последствиях "смешивания" старых и новых значений при выдаче целевой информации, опять выполз вопрос: насколько…

  • Как продлить агонию велотрансмиссии на 1500+ км

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

  • DMA для QuatCore

    Вот фрагмент схемы нашего "процессорного ядра" QuatCore: Справа сверху "притаилась" оперативная память. На той ПЛИС, что у меня есть сейчас…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 2 comments