nabbla (nabbla1) wrote,
nabbla
nabbla1

Немножко ускоряем программу обнаружения точек

При симуляции работы всей нашей связки QuatCore+GPU, на 10-й строке ушло чрезвычайно много времени на добавление одной точки и удаление двух других, и мы не успели завершить обработку к началу 11-й строки.

В принципе, это лишь моя недооценка "вычислительной сложности" алгоритма - одна строка "тестового изображения" куда короче реальной, вместо 1024 пикселя всего 32, хотя время обратного хода схожее. А вот "концентрация точек" та же самая - в реальном изображении, в самом сложном случае максимальной дальности, все точки окажутся на малюсеньком пятачке, те самые 32х32 пикселя, а всё остальное - пусто!

Но тем не менее, во время пристального наблюдения за программой возникли идеи, как можно её самую малость ускорить. Если это не шибко нужно "в железе", то ускоренную программу я хотя бы быстрее отлажу методом "пристального взгляда"!

Вкратце: игры со стеком и замена команд Acc на ZAcc.



Игры со стеком
Увы, как только в QuatCore появился конвейер, пусть и очень короткий, осуществление прыжков стало сопровождаться его сбросом и потерей тактов. Эта программа особенно страдает из-за своей разветвлённой структуры. И в двух местах нам встретилась конструкция, которую можно хоть сколько-нибудь ускорить. Первый раз:

CALL		AcqQueue
JMP		@@MidCycle


Второй раз:
@@QueueAnyway:	CALL		AcqQueue						
		JMP		@@ActPointsStart	;завершили цикл					


Выходит, что сначала мы возвращаемся из процедуры с помощью строки
JMP  [--SP]


из-за чего два такта теряется, и только мы прочитали следующую команду, например JMP @@MidCycle - как теряется ещё 2 такта.

Непорядок! Можно сделать так:
[SP++]	@@MidCycle	;после вызова AcqQueue возвращаемся
NOP	CALL(AcqQueue)	;сразу на метку @@MidCycle


и

@@QueueAnyway:	[SP++]	@@ActPointsStart	;после вызова AcqQueue возвращаемся
		NOP	CALL(AcqQueue)		;сразу на метку @@ActPointsStart


Здесь мы вовсю пользуемся дофига низкоуровневой архитектурой TTA (Transport Triggered Architecture), где команда вызова процедуры на самом деле составлялась из двух: первая (по SrcAddr) прыгает куда надо, попутно выдавая на шину данных адрес возврата, т.е текущее значение PC, а вторая, [SP++], помещает значение из шины данных в стек. Сейчас мы "разбиваем" этот вызов на два: адрес возврата помещаем ручками, и это вовсе не PC. А во время прыжка мы содержание шины данных попросту игнорируем с помощью NOP.

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

Увы, на 10-й строке тестового изображения (которая на данный момент оказалась самой ресурсоёмкой) это нам сэкономит ровно 2 такта, как-то немного...

Замена JMP на CALL
По той же логике, мы вообще можем вместо
JMP метка

делать
NOP CALL(метка)


и это также будет экономить такт, если не два, поскольку правая часть команды, SrcAddr обрабатывает тактом раньше, и уже в этот момент происходит прыжок. Но мне бы не хотелось этого делать, поскольку адресов процедур, которые можно так вызвать, всего лишь 16 НА ВСЮ ПРОГРАММУ, тогда как меток может быть 128 разных. Так что пока я бы поэкономил процедуры, 16 это как-то мало. Здесь у нас ListOp и AcqQueue, в алгоритме захвата были SwapPoints, ShiftOrigin и NormSiCo, для процедуры сопровождения появятся RotateVecByQuat и QuatMultiply, а это уже 7, а мы ещё совсем не затрагивали нахождение яркостных центров с субпиксельной точностью, информационный обмен с "бортом", алгоритм захвата на "ближней дистанции". По-моему, игра не стоит свеч.

Замена Acc на ZAcc
Наше АЛУ умеет делать очень интересные вещи: умножение с накоплением без потери точности (аккумулятор может иметь ширину 32 бита, и только по завершении всего накопления округляться до выходных 16 бит), взятие модуля, возведение в квадрат. Но увы, за это приходится расплачиваться: самые простые операции, такие как помещение числа в аккумулятор, сложение и вычитание, выполняются за 3 такта. На первом такте значение только "защёлкивается" в регистр B, затем оно должно разок в нём "сдвинуться вправо", возможно, со сменой знака, а в это время аккумулятор, при необходимости, обнулится, и только на третьем такте будет произведено сложение/вычитание/помещение "как есть" (если акк. обнулился).

Когда мы в двух местах программы проверяем на NULL, это становится невыносимо: сначала 3 такта тратится на загрузку значения, ещё 3 такта на "вычитание нуля", там, где можно было бы обойтись и 1 тактом. Скажем, мы могли бы для одного из адресных регистров ввести "флаг нуля", чтобы стоило лишь в него положить новое значение, и если оно нулевое - сразу это определяем. Может, как-нибудь и введу что-нибудь такое, но это требует опять адреса команд "перетрясти". В принципе, там ещё есть место, один только JMP занимает 8 адресов, да и JL/JGE/JO/JNO занимают по 2 адреса каждый. Ввести какие-нибудь JZZ (Jump if Z is Zero) и JZNZ (Jump if Z is Not Zero) прикольно. Но позже!

А пока вспомним, что в АЛУ есть ещё одна немножко странная команда, выполняющаяся за 1 такт: ZAcc. Она нужна для занесения в аккумулятор констант 3/2, -3/2, -1 и 1/2lsb, которые сложно туда запихать другими способами, ибо обычное 16-битное число АЛУ воспринимает как имеющее диапазон -1..1-2-15. С появлением таблицы QuatCoreImmTable, "-1" стало не таким уж страшным, а "-3/2" нам вообще пока ни разу не пригодилось. А вот 3/2 очень полезная штука для нормализации векторов и кватернионов, да и 1/2lsb, она же RoundZero - тоже "хлеб с маслом", т.к позволяет "автоматом" получить правильно (почти правильно) округлённые значения.

Посмотрим, где можно было бы её применить. Вот одно место:
Acc		0
SUB		[X+k]
JGE		@@FinalRange	;наткнулись на NULL, значит, все точки обработали...						


вот другое:
Acc		[Y+k]
Z		Acc			
SUB		0			
[Y+k]		[Z+k]
JL		@@OutOfMem			


Нужно, чтобы знак результата однозначно указывал: NULL или нормальное значение? Нормальные значения будут иметь диапазон 0..255, а может 0..511, тогда как NULL пока что записывается как 0x8000.

Если заменить Acc 0 на ZAcc RoundZero, то выйдет забавная картина: ноль и любое отрицательное значение будут трактоваться как NULL, а любое положительное - как "нормальное". В принципе, нас это устраивает. В конце концов, мы из своей жадности при обращении со списками сделали условный переход на OutOfMemory одной строкой ниже, чем надо, поэтому если нехватка всё-таки будет, по нулевому адресу-таки что-то запишется.

Аж 2 такта на этом сэкономим, не так хорошо, как 5 тактов (введи мы дополнительные команды JZZ / JZNZ), но хоть что-то...

В одном месте программы получается так:
ZAcc		RoundZero
SUB		[X+k]
JGE		@@FinalRange	;наткнулись на NULL, значит, все точки обработали...						
			

"Безболезненно". Но увы, на самом деле экономится РОВНО ОДИН ТАКТ, поскольку "по соседству" с ZAcc будет выполняться [X+k], эта команда выполняется за 2 такта, поэтому ZAcc один такт вынужден будет "подождать".

Но место "очень популярное", через этот @@MidCycle мы проходим столько раз, сколько активных точек, и ещё +1. То есть, на злополучной 10-й строке мы здесь прошли 4 раза. Зашибись экономия :)

В другом месте, в ListOp, переписываем вот так:
ZAcc		RoundZero
Z		[Y+k]
SUB		[Y+k]
[Y+k]		[Z+k]
JGE		@@OutOfMem									


Тут всё же экономим 2 такта, уже радость. И место также популярное, на 10-й строке мы сюда 3 раза попадали, так что ещё 6 тактов долой!

Увы, нам пришлось заменить JL на JGE, а поскольку у нас флаг знака является своего рода "аргументом" для процедуры AcqQueue, нужно и ещё в нескольких местах сделать перестановки.

В первую очередь, в самом AcqQueue тоже меняем JL на JGE:
	AcqQueue proc	
			i		2	;даже если не нужно обновить точку, не навредит... (это мы Hazard убираем мучительно!)
			JGE		@@queue
			;здесь обновляем точку
	@@updCycle:	[X+2j+i]	[SP+i]
			iLOOP		@@updCycle
	@@queue:	Acc		[X+2j+k]
			DIV2S		[X+1]	;теперь в аккмуляторе у нас X - Ceil(D/2)
			ACQ		Acc		;первый отрезок
			ADD		[X+1]	;а вот теперь X + Floor(D/2)
			ACQ		Acc		;второй отрезок
			JMP		[--SP]
	AcqQueue endp	


при вызове его сразу после добавления новой точки, вот в этом месте:
CALL	ListOp	;добавит в X новую, пока что пустую точку.
;если добрались досюда, значит памяти хватило. X содержит адрес указателя на новую точку, а вот Z содержит адрес самой точки!
;наполним её содержимым!						
X	Z		;для дальнейшей работы (после MidCycle)... Чтобы мы не взялись за только что добавленную точку!
[Z+1]	C		;гориз. размер точки (будет расти при слияниях, а поначалу D, т.к мы сюда включаем и )																														
[SP++]	@@MidCycle		;после вызова AcqQueue возвращаемся
NOP	CALL(AcqQueue)	;сразу на метку @@MidCycle


Так что если уж мы после добавления точки попали в AcqQueue, там мы цикл по инициализации только что добавленнной записи НЕ УПУСТИМ! Всё верно.

Однако мы можем попадать в AcqQueue ещё из двух мест:
		JL	@@NotSoBright	;похоже, на спад пошло. ТУТ ОБЯЗАН СТОЯТЬ ТОЛЬКО JL, если нет - меняем местами операнды!
		;нужно обновить координаты и яркость нашей яркой точки, а заодно и "размер" прибавить					
		;хорошо, "заказываем" два отрезка для этой точки: первый "на поиск", второй "на коррекцию".
@@QueueAnyway:	[SP++]	@@ActPointsStart	;после вызова AcqQueue возвращаемся
		NOP	CALL(AcqQueue)	;сразу на метку @@ActPointsStart						
		;ветвь исполнения, если старая точка оказывалась ярче.
		;Нужно сообразить: не пора ли ей на покой, то бишь в список AllPoints?
		;в кои-то веки работаем с Y-координатой!
@@NotSoBright:	Acc	[SP+2j]	;текущий номер строки
		SUB	[X+2j+1]	;вычитаем Y-координату  ранее обнар. точки. Ответ всегда положительный, т.к считаем по строкам "вверх"
		DIV2S	[X+1]		;ну и размер точки, в кои-то веки уполовиненный
		JL	@@QueueAnyway	;здесь ОБЯЗАН быть именно JL, т.к флаг знака является одним из "аргументов" для AcqQueue


Либо мы не прыгнули на @@NotSoBright и сразу вызвали процедуру AcqQueue. Это значит, что на текущей строке мы увидели точку БОЛЕЕ ЯРКУЮ, чем у нас записано в списке, и НУЖНО ОБНОВИТЬ КООРДИНАТЫ И ЯРКОСТЬ в этой записи. Но раз у нас не выполнился JL, значит внутри AcqQueue выполнится JGE, а нам этого не надо. Следовательно, и здесь нужно JL заменить на JGE, для чего меняем местами операнды для вычитания:
[SP+2j+1]	GPUL		;яркость
Acc		GPUL
SUB		[X+4j+k]						
[SP+1]		GPUH		;пока не забыли - сразу второе слово запрашиваем (коорд точки), чтобы не сбить весь FIFO 
JGE		@@NotSoBright	;похоже, на спад пошло. ТУТ ОБЯЗАН СТОЯТЬ ТОЛЬКО JGE, если нет - меняем местами операнды!


И второй вариант - когда всё-таки прыгнули на @@NotSoBright, и там решили, что ещё не столь далеко отошли от центра пятна, поэтому удалять его из списка ActivePoints ещё рано, поэтому прыгнули на @@QueueAnyway. Это тот самый случай, когда внутри AcqQueue должен выполниться JGE, чтобы не обновлять параметры точки в списке. Поэтому и JL @@QueueAnyway заменяется на JGE @@QueueAnyway, для чего вместо выражения

Ycur - Ypoint - D/2

надо посчитать

Ypoint + D/2 - Ycur

Почему бы и нет, сделаем:
@@NotSoBright:	Acc	[X+2j+1]	;координата точки (из списка)
		DIV2A	[X+1]		;прибавить половинку её диаметра
		SUB	[SP+2j]		;вычесть текущий номер строки
		JGE	@@QueueAnyway	;здесь ОБЯЗАН быть именно JGE, т.к флаг знака является одним из "аргументов" для AcqQueue


Вот теперь, вроде, всё!

Loop unrolling
Ну и самый эффективный здесь подход: развернуть циклы, когда мы заранее знаем, сколько раз они выполнятся. С коротенькими циклами мы явно злоупотребляем! Например, как вам такое нравится (в AcqQueue, обновление параметров точки в списке, несколько команд для краткости убрали):

		i		2
@@updCycle:	[X+2j+i]	[SP+i]
		iLOOP		@@updCycle


ТРИ СТРОКИ, ЧТОБЫ ПРИСВОИТЬ ТРИ ЗНАЧЕНИЯ! Один такт на i=2, затем по 2 такта на само присвоение, и по 1 такту на выполнение iLOOP (независимо от того, был ли переход), и ещё "штрафные" 2 такта при прыжке, коих здесь происходит 2. Итого, 14 тактов. Казалось бы, напишем вот так:
[X+4j+k]	[SP+2j+k]
[X+2j+1]	[SP+1]
[X+2j+k]	[SP]


Те же три строки, но всего 6 тактов. Вот только компилятор обнаружит Hazard - одновременное использование памяти на чтение и запись - и вставит туда 3 NOP'а, так что и объём кода возрастёт, и выигрыш во многом уйдёт. Похожая история и в других местах. Так что пока оставляем как есть.


Компиляция ПРОШЛА КРИВО!
На строчках
[SP++]  @@ActPointsStart

компилятор, во-первых, не сообразил, что нам на самом деле достаточно младших 7 бит, а остальные могут быть произвольными. И действительно, нужен какой-то новый синтаксис, чтобы объяснить ему это. Ведь "на два шага вперёд" он думать не может - это реально очень сложно, вывести, что значение из стека будет применено для прыжка, и более ни для чего! А так-то у нас в память все 16 бит поступают.

Но это ладно, QuatCoreImmTable.v получилась пожирнее чем прежде, с этим можно было бы смириться.

Хуже другое: каким-то макаром наши метки превратились в ОТНОСИТЕЛЬНЫЕ АДРЕСА! Точнее, я примерно представляю, в чём дело. У нас каждая команда имеет "тип данных", который ей нужен, и там 3 варианта: AbsJump, RelJump и Numeric. И похоже, до сих пор я метки использовал непосредственно на прыжки - и всё срабатывало как надо. Наверное, для AbsJump я давал абсолютный адрес, а ДЛЯ ВСЕГО ОСТАЛЬНОГО - относительный.

По логике вещей, мы имеем право запихать в стек (и вообще куда-нибудь в память) и относительный адрес, и написать потом
JL   [--SP]


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

Ладно, сейчас поеду домой на велике, подышу свежим воздухом, может, придёт в голову какая светлая мысль...


Поздравьте: я в очередной раз всё сломал.

PS. Но хоть разобрался, почему Git конкретно эту ассемблерную программу, VideoProcessing.asm счёл "бинарным файлом" и не хотел мне показывать, какие строки поменялись, "differs" и всё тут. Потому что он каким-то макаром был в Unicode-16, а Git её не понимает, для него текст - это только однобайтовые символы. Переправил в обычную кодировку - теперь показывает, и то радость.
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

  • Лестница для самых жадных

    В эти выходные побывал на даче, после 3-недельной "самоизоляции". Забавно, как будто зима началась! Особенно грязные галоши остались на улице, в…

  • Возвращаемся к макету

    Очень давно макетом видеоизмерителя параметров сближения не занимался: сначала "громко думал" по поводу измерения его положения на аппарате, а потом…

  • Минутка живописи

    В процессе разгребания содержимого квартиры (после нескольких ремонтов) дошёл, наконец, и до картин. В кои-то веки их повесил. Куда их вешать -…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments