nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Сортировка против часовой стрелки на быстром QuatCore

Куй железо, пока горячо! Надо поскорее отладить весь аффинный алгоритм на "разогнанном" QuatCore. Первую часть проверили, заработала (программа и транслятор были не виноваты, это я в сам процессор влез "грязными руками", в одном месте поменял, в другом забыл. Теперь всё нормально). Пора за вторую из 5 браться, за сортировку оставшихся точек, приняв самую отдалённую за начало координат.

Применив очередной финт ушами, удалось не только избежать очередного NOP, но и укоротить программу в этом месте на 2 команды, с 26 до 24 команд (-8%).


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

Мы перемещали начало координат в самую отдалённую из точек, а потом надо было вернуть координаты на место. Нам казалось очень элегантным применение регистра Inv и команды PM (Plus Minus), но в этом месте можно сделать ещё элегантнее.

Надо ОТРАЗИТЬ точки относительно самой отдалённой из точек, т.е вместо

Fx1нов = Fx1исх - Fx0,
Fy1нов = Fy1исх - Fy0
(и точно также для точек 2, 3)

напишем

Fx1нов = Fx0 - Fx1исх,
Fy1нов = Fy0 - Fy1исх

Особого влияния на сортировку это не окажет, зато обратное преобразование совпадает с исходным:

Fx0 - Fx1нов = Fx0 - Fx0 + Fx1исх = Fx1исх,
Fy0 - Fy1нов = Fy0 - Fy0 + Fy1исх = Fy1исх

Таким образом, вместо строк

Inv  1
CALL ShiftOrigin
...
сортировка
...
Inv 0
CALL ShiftOrigin


получаем просто-напросто:
CALL ShiftOrigin
...
сортировка
...
CALL ShiftOrigin

Две команды сэкономили :)

Взглянем на старый код ShiftOrigin:

ShiftOrigin proc
	;надо из всех точек вычесть коорд. наиболее отдалённой (с индексом 0)
	;кроме неё самой, разумеется
				k		1
@@k_loop:			i		2	;как всегда, чтобы Y и X
@@i_loop:			Acc		[X+2i+k]
				PM		[Y+k]
				[X+2i+k]	Acc
				iLOOP		@@i_loop
				kLOOP		@@k_loop
				JMP		[--SP]
ShiftOrigin endp


Там кроется очередной Hazard: только мы объявили i=2, как тут же должны обратиться к [X+2i+k]. А поскольку чтение из [X+2i+k] совпадает по времени с записью в i, произойдёт ошибка, нужен NOP, чтобы её избежать.

А вот если сделать зеркальное отражение вместо этого, получаем такой код:

ShiftOrigin proc
	;надо из всех точек вычесть коорд. наиболее отдалённой (с индексом 0)
	;кроме неё самой, разумеется
				k		1
@@k_loop:			i		2	;как всегда, чтобы Y и X
@@i_loop:			Acc		[Y+k]
				SUB		[X+2i+k]
				[X+2i+k]	Acc
				iLOOP		@@i_loop
				kLOOP		@@k_loop
				JMP		[--SP]
ShiftOrigin endp


К тому времени, как мы обратимся к i, оно уже будет записано!

Мелочь, а приятно.

Ну и приведём код процедуры SortCCW:
		;состояние регистров к данному моменту:
		;X = Y =Z = Points2D
		;i = индекс наиболее отдалённой точки
		;j=k=0
		;Inv неизвестен
		;C = [Fx0]
		;Acc = разность полусумм квадратов (не понадобится)
		SortCCW		proc
		;Далее: нужно расставить оставшиеся точки против часовой стрелки
		;Первый шаг к этому: переместить начало координат в МДД3, который сейчас по нулевому индексу
				X		Fx1	;чтобы индекс от 2 до 0 соотв. точкам (Fx1,Fy1) ... (Fx3, Fy3)
				Z		Fx2	;чтобы иметь сдвинутую на 1 адресацию
		;потом вернём как ни в чём не бывало, у нас фикс. точка, все правила арифм. соблюдаются						
				CALL		ShiftOrigin
		;вот теперь пора сортировать!
				j		1
				i		1
		;Делаем "сдвинутую" адресацию [Fx2 + j], т.е j=1 указывает на 3-ю точку, j=0 - на 2-ю.
		;но при этом, i = 1 указывает на 2-ю, i=0 - на 1-ю
		;а нулевую пока вообще не рассматриваем - она на своём месте!
		;хотим на позицию j+2 поставить "самую большую", для этого надо выбрать между j+1,...1
		;здесь заведомо k=0, так что X+2i / X+2j не нужны!
		@@loop:		C		[Z+2j+k]
				MUL		[X+2i+1]
				C		[Z+2j+1]
				FMS		[X+2i+k]	;нахождение "векторного произведения"
				JL		@@skip
		;меняем местами, как обычно, точки с коорд. i и с коорд. j
				CALL 		SwapPoints
		@@skip:		iLOOP		@@loop
				jLOOP		@@loop
					
				CALL		ShiftOrigin		
				;а теперь ещё надо два последних поменять местами, для совместимости с алг. сопровождения
				;здесь i=j=k=0
				X		Fx3
				CALL		SwapPoints
		SortCCW		endp


Последние 2 строчки нужны, потому что в на дальней дистанции мы работаем с 4 точками: Мишени Дальней Дистанции 1-3 (МДД1-МДД3) и Мишень Ближней Дистанции (МБД). Эта самая МБД на самом деле состоит из 8 уголковых отражателей, но на дальней дистанции они все сливаются в одно пятно. А на ближней дистанции нужно заменить МБД на 8 точек.

Поэтому моя идея: расположить точки в памяти следующим образом:

МБД1
МБД2
МБД3
...
МБД8
МДД3
МДД1
МДД2
МБД (общее пятно)

и просто расставлять границы массива, рассматривая либо 11 точек от начала, либо 4 точки от конца. А после сортировки против часовой стрелки у нас получалось

МДД3
МДД1
МБД
МДД2

Вот мы и меняем местами два последних.

Транслятор говорит, что новых Hazard'ов не появилось. На самом деле, он вообще ни одного Hazard'а не находит, т.к старые я всё-таки ручками исправил, чтобы получить 0 warning'ов.

И ещё в конце процедуры main выведем все 8 координат куда-то "наружу":

			k		7
			X		Points2D
			NOP		0
	@@loop:		OUT		[X+k]
			kLOOP		@@loop


Может, повезёт, и не придётся всю программу отлаживать?

Запускаем, и сразу отматываем в конец. Ищем DestAddr=0, это те самые OUT, где мы должны иметь на шине данных координаты всех точек после всех сортировок.


Напомним, изначально у нас были точки:
(53;-7) - МБД
(480;-30) - МДД1,
(-539;-302) - МДД2,
(400;-997) - МДД3.

(они здесь "отсортированы по кординате Y, т.е как мы получали изображение строку за строкой - так и регистрировали точки)

А теперь получилось:
(400; -997) - МДД3
(480; -30) - МДД1
(-539; -302) - МДД2
(53; -7) - МБД.

УРРА! Первая радость: преобразование координат прошло как надо, все числа вернулись к исходным. То есть, с ShiftOrigin мы действительно не перемудрили. Ну и второе: точки расставлены ровно в том порядке, в котором мы и хотели.

Время выполнения (вывод "на экран" не считаем): 62,64 мкс. Одна строка телевизионного сигнала :)

Всего программа занимает 64 слова, или 128 байт. По сравнению с первой рабочей версией (которая запускалась на "медленном" QuatCore) мы даже ужались: тогда 63 слова занимал код без "вывода на экран", а у нас 64 слова вместе с "выводом на экран", который занимает 5 слов.

На "медленном" QuatCore мы доходили до этой точки за 335 мкс, т.е убыстрение в 5,3 раза. Почти не изменилось с прошлых измерений!
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

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

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

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

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

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

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 1 comment