nabbla (nabbla1) wrote,
nabbla
nabbla1

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

После того, как матрицу аффинного преобразования "скорректировали" по крену, она должна содержать в себе масштаб и ракурсы. На ракурсы нам наплевать, всё равно в аффинном приближении мы не можем найти "знак" этих ракурсов - видим лишь что картинка ужимается вдоль какой-то оси, а вращение в какую сторону привело к этому - понятия не имеем, но и арккосинус искать вблизи единичных значений - это ОЧЕНЬ неблагодарное занятие!

Вот код для нахождения масштаба:
;Состояние регистров к этому моменту:
;X=AfTransf,
;Y=QuatY,
;Z=Matrix,
;i=j=k=Inv=0,
;C=Acc=Txx
FindScale	proc
;1. Вычисляем величины |X-Z| (т.е |Txx - Tyy| ) и |2Y| (например, |Txy+Tyx|, хотя можно 2|Txy| или 2 |Tyx| )
;важно, что в данный момент Inv=0
		[SP]		0	;манхэттенская метрика, сумма модулей (метрика городских кварталов)
		[SP+1]	0	;чебышевская, максимум от модулей 
		;текущее значение будем хранить в регистре C - дешево и сердито!
		i	1
		j	3					
@@loop:		Acc	[X+i]	;+Tyx (i=1), -Tyy (i=0)
		PM	[X+i^j]	;Txy (i=1), Txx (i=0)   ;поменяли местами чтобы проверить модуль
		ABS	Acc		;|Txy+Tyx| (i=1), |Txx-Tyy| (i=0)
		C	Acc		;сохранили это значение
		ADD	[SP]	
		[SP]	Acc	;обновили манхэттенскую
		Acc	C
		SUB	[SP+1]
		JL	@@skipCheb ;лучше подошел бы JGE и поменять местами C и [SP+1]. Разница при нуле-на 1 больше операций.
		[SP+1]	C	;обновили Чебышевскую	
@@skipCheb:	Inv	1		;так что на следующей итерации будет "-"
		iLOOP	@@loop
	;теперь в [SP] лежит манхэттенская метрика, а в [SP+1] - чебышевская
	;осталось посчитать выражение целиком - сумму Txx+Tyy с весом 1/2, а эти - с весами 0,332 и 0,168
	;или сначала всё сложить - а потом поделить пополам...
	;можно, если ввести команду UDIV2 - беззнаковое деление
	;по сути, SHR1 
	
	;кстати, у нас до сих пор j=3 :)
	;i=k=0
		Acc	[X+i]	;добавили Txx
		ADD	[X+i^j]	;и Tyy
	;теперь наши метрики берём с весами	
		C	[SP]
		FMA	11010	;ManhW
		C	[SP+1]
		FMA	21758	;ChebW
				
	;ага, сделали
	;продемонстрируем результат
		JO	@@endLoop
@@shl1:		ADD	Acc
		j++	0
		JNO	@@shl1		
	;ага, сделали
@@endLoop:	[SP+1]	Acc			;финт ушами: заносим значение 32767, ибо нефиг! (другими способами его сложно раздобыть)
		DIV2	UAC ;получается отрицательное значение от -16384 до -1 (число -1 при "делении на 2" так и останется -1)
		SUB	[SP+1] ;вычитает 32767, что даст отрицательное значение от -49151 до -32766. Но в UAC отобразится от 16385 до 32768.
	;если теперь найти обратную величину, это должно получиться в диапазоне 32768..65532
	;а если мы вычтем ещё половинку, может выйти от 16384 до 32768, и диапазон 32768..65536.
	;так что ну её нахрен, эту половинку?
	;или можем уже на этапе Ньютона этот случай проверить.
		DIV2S	1 ;это для нужд округления. 					
		[SP]	UAC							
		OUT	j	;для отладки
FindScale	endp


Чуть вспомним, что тут вообще происходит - и попробуем запустить...


Вспомнить очень поможет эта запись: аффинный алгоритм, нахождение масштаба

Запустили на старом АЛУ, начало выполнения этой процедуры: T=192,24 мкс, окончание: 198,8 мкс, т.е выполняется и так довольно быстро, за 164 такта. Результатами становится "мантисса", помещаемая в [SP], сейчас это 0x6D4B = 27979, и "экспонента", лежащая в регистре j. Как видно, мы чисто для отладки добавили "OUT j", и там отобразилось число 9. Если 32768 поделить на "мантиссу" (наш аналог "взятия обратной величины"), а потом помножить на 2j-1, получим 299,818006361914 - это измеренная дальность в метрах!

Посмотрим, что здесь можно улучшить при новом АЛУ. Экономим один такт на PM, т.к выполнение накладывается на предыдущую команду, Acc. Потом приходится ждать окончания работы АЛУ, чтобы от результата взять модуль. А только мы взяли модуль - сразу хотим положить результат в регистр C, так что опять ждём. Прибавили значение - и снова ждём. Разве что потом, на цепочке "Acc - SUB" ещё один такт выхватываем, и снова ждём результата для условного перехода JL.

Разве что мы можем перенести "Inv 0" между арифметическими командами, а ещё обнулить две компоненты кватерниона ([Y] и [Y+1]) именно в этом цикле:

		[SP]	0	;манхэттенская метрика, сумма модулей (метрика городских кварталов)
		[SP+1]	0	;чебышевская, максимум от модулей 
		;текущее значение будем хранить в регистре C - дешево и сердито!
		i	1
		j	3					
@@loop:		Acc	[X+i]	;+Tyx (i=1), -Tyy (i=0)
		PM	[X+i^j]	;Txy (i=1), Txx (i=0)   ;поменяли местами чтобы проверить модуль
		Inv	1		;уже можно! Так что на следующей итерации будет "-"
		[Y+i]	0		;очистим две компоненты кватерниона
		ABS	Acc		;|Txy+Tyx| (i=1), |Txx-Tyy| (i=0)
		C	Acc		;сохранили это значение
		ADD	[SP]	
		[SP]	Acc	;обновили манхэттенскую
		Acc	C
		SUB	[SP+1]
		JL	@@skipCheb ;лучше подошел бы JGE и поменять местами C и [SP+1]. Разница при нуле-на 1 больше операций.
		[SP+1]	C	;обновили Чебышевскую					
@@skipCheb:	iLOOP	@@loop


Если не ошибся, где-то 8 тактов на этом всё выигрывается.

В итоге, у нас есть две метрики, которые мы хотим взять с определёнными весами, что даст неплохое приближение к Эвклидовой метрике, и ещё два значения прибавляем:

;кстати, у нас до сих пор j=3 :)
;i=k=0
	Acc	[X+i]	;добавили Txx
	ADD	[X+i^j]	;и Tyy
;теперь наши метрики берём с весами	
	C	[SP]
	FMA	11010	;ManhW
	C	[SP+1]
	FMA	21758	;ChebW


Наложатся друг на друга Acc и ADD, затем на последнем такте ADD может выполниться C, затем на последнем такте FMA выполнится второй C, ожидаю 3 такта экономии, итого к этому моменту 11 тактов.

Потом мы начинаем удваивать значение в аккумуляторе, пока не случится переполнения. На каждом удвоении прибавляем единичку к "экспоненте":

	JO	@@endLoop
@@shl1:	ADD	Acc
	j++	0
	JNO	@@shl1		


Один такт экономится на каждой итерации, т.к j++ теперь выполняется одновременно с АЛУ, но уже к следующей команде нужно знать ответ. Сейчас у нас будет 6 итераций, так что в общей сложности к этому моменту ожидаем 17 тактов.

А под конец - какая-то хрень:
@@endLoop:	[SP+1]	Acc			;финт ушами: заносим значение 32767, ибо нефиг! (другими способами его сложно раздобыть)
		DIV2	UAC ;получается отрицательное значение от -16384 до -1 (число -1 при "делении на 2" так и останется -1)
		SUB	[SP+1] ;вычитает 32767, что даст отрицательное значение от -49151 до -32766. Но в UAC отобразится от 16385 до 32768.
;если теперь найти обратную величину, это должно получиться в диапазоне 32768..65532
;а если мы вычтем ещё половинку, может выйти от 16384 до 32768, и диапазон 32768..65536.
;так что ну её нахрен, эту половинку?
;или можем уже на этапе Ньютона этот случай проверить.
		DIV2S	1 ;это для нужд округления. 					
		[SP]	UAC							
		OUT	j	;для отладки


Мы за число 32767 "хватались", пока не было таблицы непосредственных значений (ImmTable) и мы могли использовать лишь непосредственные значения -64..+63. Сейчас всё упростилось: ставишь "SUB 32767" - И ВСЁ. Так что одну строку удаляем безжалостно :)

Да и отладочную строку "OUT j" мы уберём - там чуть дальше значение j используется, можно будет глянуть.

Итого, минус 2 строки и минус три такта за счёт наложение команд АЛУ друг на друга. Всего ожидаем экономии в 20 тактов.

Ну давайте проверим... Программа "похудела" со 199 слов кода до 196, это весь аффинный алгоритм + две процедуры для работы с кватернионами (умножение кватернионов и поворот вектора с помощью кватерниона).


Всё выполнилось как надо, и на 20 тактов быстрее, снова "как в аптеке". Сейчас мы в позиции T=187,84 мкс, а раньше до этого места добирались к 198,8 мкс, 5,5% выигрываем в общей сложности. Да, год назад у нас куда более серьёзная была заявка, когда с 4 МГц ускорили до 25 МГц :) Сейчас уже объедки с барского стола.

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments