nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

Алг. обнаружения под новый АЛУ

Возвращаемся к нашим баранам, к алгоритму обнаружения ярких пятен на изображении В РЕАЛЬНОМ ВРЕМЕНИ. Когда последний раз его мучали на симуляции (на уменьшенном изображении всего с одним пятном), он тупо не успел обработать данные и вовремя не отправил задания видеопроцессору. Проблема в том, что начни обрабатывать настоящую мишень на минимальной дальности 0,5 метра и при самом неудачном ракурсе, когда 4 пятна встанут в ряд - и времени там не хватит точно также.

Поэтому ещё на 2 недели отвлёкся - дорабатывал АЛУ и потом отлаживал его. И теперь, прежде чем испытать алгоритм обнаружения, хочу "оптимизировать" его под новый АЛУ, переставить местами команды (где это допустимо) так, чтобы процессор максимально "распараллеливался" - пока АЛУ думает о своём, остальной процессор может шуровать в памяти, общаться с видеопроцессором и т.д.

Почему бы не отладить старую версию для начала - а потому что оптимизировать уже не захочется, "работает - не лезь!" А раз уж она всё равно не работает (на реальном железе тоже какая-то фигня происходит) - то сначала доработаем, а потом будем приводить в чувства!


Весь этот алгоритм у нас лежит в файле ProcessFrame.asm ("обработка кадра").

Инициализацию перед началом цикла по строкам мы особенно трогать не будем:
ProcessFrame proc			
		j		1	;отныне и во веки веков!	
		;ждём кадрового синхроимпульса
		ACQ		VSync		;"застревает" до тех пор, пока кадровый импульс не придёт
		;пропускаем "пустые строки" вверху изображения (нужно только для аналоговой камеры, в цифровой такой фигни нет вроде бы...)
		k		TopRows	;TopRows должны быть определены в основном файле												
@@topRows:	ACQ		HSync
		kLOOP		@@topRows
		;теперь k=0, пусть так и остаётся, наши [X+k], [Y+k], [Z+k] будут означать [X],[Y],[Z], очень надо для списков
				
		;теперь начинаются информативные строки изображения, сейчас их 720, позже может стать 1024. 
		[SP+2j]		-1		;в [SP+2] храним номер строки.				
		JMP		@@FinalRange	;чтобы СНАЧАЛА отправить запрос, а потом уже смотреть результат


Тут АЛУ и не работает вовсе! И в целом, "не горит". Входной буфер видеопроцессора забит заданиями "обнаружить синхроимпульс" (сначала кадровый, потом строчные - отсчитать бесполезные строки вверху кадра), и пока он это делает, мы уже успеем выйти на "стартовую черту" где остановимся и будем ждать ответа.

Дальше, самая верхушка цикла по строкам, где мы обновляем номер текущей строки, устанавливаем указатель на самый первый элемент списка обнаруженных пятен (это левое фиктивное пятно), сбрасываем флажок в регистре C, указывающий что нам нужно выдать задание видеопроцессору - и начинаем цикл по обнаруженным пятнам:
			;НАЧАЛО ЦИКЛА ПО СТРОКАМ
@@newRow:		[SP+2j]		Acc
			X		ActivePoints	;начинаем цикл по всем активным точкам
				
@@ResetPending:		C		0			;уж явно не 0x8000			
;даже если список пуст, первую половину цикла мы пройдём, она касается отрезка, предшествующего точке из списка
@@ActPointsStart:	[SP+2j+1]	GPUL			;яркость самой яркой точки на отрезке
			[SP+1]		GPUH			;соотв. координата
			Acc		Threshold		;поставили задом наперёд, чтобы избежать Hazard'а	
			SUB		[SP+2j+1]		;вычитаем порог, положит. значение свидетельствует о новом найденном "пятне"						
			[SP]		@@MidCycle
			JL		TaskPending	;пятна нет, не торопимся заказывать отрезок


Начало неплохое: по завершении цикла мы загружаем номер строки, лежащий в [SP+2], в аккумулятор, вычитаем 719, прибавляем 720 и если знак "-", прыгаем в начало цикла. Так вот, если всё-таки доработать сигнал Sbusy (АЛУ занято операцией, которая меняет знак S), то во время прыжка будет доделываться сложение, и здесь результат будет положен назад в [SP+2].

Дальше всё относительно удачно: пока в аккумулятор заносится Threshold, начинается выборка [SP+2j+1], останавливая команду на 1 такт. Потом как раз на третьем такте без задержки начинает выполняться SUB. Он не мешает нам попутно занести адрес возврата в [SP] (идёт второй такт SUB), и потом ждём один такт на JL, чтобы узнать результат этого вычитания и принять решение. Итого, вся эта часть от @@ActPointsStart до JL должна выполняться за 9 тактов.

Но можно лучше:
@@ActPointsStart:	Acc		GPUL
			[SP+2j+1]	GPUL
			SUB		Threshold
			[SP+1]		GPUH
			[SP]		@@MidCycle
			JGE		TaskPending	


Первым тактом (если "выпрыгнули" сюда на @@ActPointsStart) будет запрошен GPUL. Вторым: начнётся команда Acc. Третьим: GPUL будет занесён в [SP+2j+1]=[SP+3]. Четвёртым: начнётся вычитание (оно наложится на третий такт Acc). Пятым: GPUH занесён в [SP+1] (в это время второй такт вычитания), шестым: в [SP] занесён адрес возврата (это третий такт вычитания), и к JL уже готов результат, так что всего 7 тактов. На старом АЛУ и старой программе: 11 тактов.

Следующий кусочек:
;первым делом, проверяем, не сливается ли с пятном слева			
Acc	[X+2j+k]
DIV2A	D1
DIV2A	[X+1]
SUB	[SP+1]
Z	[X+k]
JGE	@@LeftMerge


Тут ничего не трогаем, просто умиляемся. Раньше тут уходило 3+4+4+3+1+1 = 12 тактов, теперь на 4 такта меньше за счёт "наложения" команд.

Следующий кусочек:
;если дошли досюда, значит с пятном слева не сливаемся, надо проверить теперь на пятно справа						
Acc	[Z+2j+k]
SUB	[SP+1]
DIV2S	D1p1
DIV2S	[Z+1]
JL	@@RightMerge
	
;если попали сюда, значит слияния не было, и точку всё-таки надо добавить!
;но сначала проверим, нет ли у нас "долга" за предыдущую точку?
[SP]	@@NewBlob


Тоже особо ничего не сделаешь, ну и не надо. Было 11 тактов до JL, теперь 8 - подсократилось.

Следующий кусочек:
	;по сути, процедура, хотя вызываем мы её, укладывая адрес возврата в [SP], БЕЗ ИНКРЕМЕНТА
	;в регистре С лежит некий флаг, подсказывающий, нужно ли нам выдавать задания на обработку отрезков,
	;которые мы не выдали сразу в страхе, что произойдёт слияние пятен, и надо будет дать несколько другое задание,
	;а команды AUP у нас нет
	;Регистр X указывает на то самое пятно, по которому надо выдать задания
	;самый быстрый способ ветвиться по содержанию C - это заносить туда либо -32768, либо любое другое значение
	;брать ABS и смотреть на переполнение
	;пусть -32768 будет означать "выполняй!"
	TaskPending proc
		ABS	C
		JNO	[SP]		;вот в чём прелесть стека без инкремента!
		;если дошли до сюда, заказываем отрезки на обработку
AcqNoCheck:	Acc	[X+2j+k]
AcqAfterMerge:	DIV2S	[X+1]	;теперь в аккумуляторе у нас X - Ceil(D/2)
		DIV2A	1	;чтобы всё-таки было X-Floor(D/2)
		ACQ	Acc		;первый отрезок
		ADD	[X+1]	;а вот теперь X + Floor(D/2)
		ACQ	Acc		;второй отрезок
		JMP	[SP]
	TaskPending endp	


И тут особо ничего не сделаешь, но выигрыш есть, аж в 2 такта.

Следующий кусочек:
				;[SP+2j+1]=[SP+3] указывает яркость этой точки, [SP+2j]=[SP+2]: Y-координату, [SP+1]: X-координата
				;а куда вставить, указывает рег. X
				;в Acc содержится модуль разности между правой точкой и текущей, за вычетом двух радиусов
	@@NewBlob:		Y	Heap									
				[SP]	@@AfterListOp
				NOP	0			;на следующей строке ListOp нам нужен и Y уже готовый, и доступ к памяти, так что Hazard по-любому будет какой-то...
				
				;добавит в X новую, пока что пустую точку.
				
						
;взять первый элемент из списка Y и перецепить его в начало списка X
;значения X,Y остаются неизменными,
;при вызове должно быть k=0, затираем регистр Z, Acc и флаг знака
;адрес возврата хранится в стеке, как положено
	ListOp proc			
		Z	[Y+k]
		ABS	[Y+k]
MergeBlobCase:	[Y+k]	[Z+k]
		JO	OutOfMemory									
		[Z+k]	[X+k]
		[X+k]	Z
		NOP	0		;избежать Memory hazard (одновременный доступ на чтение и запись)
		JMP	[SP]
	ListOp endp	


Тут мало чего можно сделать, очень плотная работа с памятью, для АЛУ всего одна команда ABS. Один такт будет экономиться за счёт того, что АЛУ и команда "[Y+k]" будут выполняться одновременно.

Следующий кусочек:
;обнаруженная точка примыкает к пятну слева от себя. Возможно, потребуется слияние и с пятном справа от себя
;X указывает на пятно слева, Z - на пятно справа 
@@LeftMerge:	Acc		[Z+2j+k]		;взяли X-координату правого пятна
		SUB		[X+2j+k]		;вычитаем X-координату левого
		DIV2S		[Z+1]			;вычитаем радиус правого пятна
		DIV2S		[X+1]			;и радиус левого пятна
		SUB		D1p1			;и минимально допустимый диаметр пятна
		JL		@@MergeBlobs	;делаем слияние ПЯТЕН
		;если дошли до этого места, значит пятна сливать не нужно, достаточно лишь уточнить параметры левого пятна
		;увы, аккумулятор совсем другим набит, нужно "с нуля" начинать
		Acc		[SP+1]	;Acc = x, т.е координата обнаруженной точки
		SUB		[X+2j+k]	;вычитаем X, т.е Acc = x - X - разность между обнаруженной точкой и центром левого пятна
		DIV2A		[X+1]		;прибавили D/2, получаем Acc = x-X+D/2 
		ADD		1
		[X+1]		Acc		;обновили диаметр левого пятна.
		Acc		1
		;теперь подкорректировать X-координату
		ADD		[SP+1]	;берём координату обнаруженной точки
		DIV2S		[X+1]		;вычитаем половинку диаметра
		[X+2j+k]	Acc
		JMP		AcqAfterMerge	;если слева от нас есть РЕАЛЬНОЕ пятно (фиктивное мы трогать не можем, его X-координата "-32768", условие заведомо не выполнится),
		;значит проверять "есть ли за нами должок" не нужно - точно есть!	


Удивительно дурацкий код, не вижу, как его можно улучшить. Но на новом АЛУ он довольно хорошо ускорится: на 4 такта до JL, и ещё на 5 тактов после.

Следующий кусок:
@@MergeBlobs:	Acc		[X+1]
		ADD		[Z+1]
		[X+1]		Acc	;диаметр равен сумме диаметров
		ZAcc		RoundZero
		DIV2A		[X+2j+k]
		DIV2A		[Z+2j+k]
		[X+2j+k]	Acc	;среднее арифметическое от центров точек
		;теперь удаляем правое пятно
		Y		X
		X		Heap
		[SP]		CALL(MergeBlobCase)
		X		Y
		JMP		@@EndOfCycle


Вот здесь можно чуть улучшить. "Y X" можно запихнуть сразу после DIV2S, чтобы выполнялось "нахаляву". Ведь Y здесь не используется, и X всё это время не меняется. Остальное трогать нельзя. Получится так:
@@MergeBlobs:	Acc		[X+1]
		ADD		[Z+1]
		[X+1]		Acc	;диаметр равен сумме диаметров
		ZAcc		RoundZero
		DIV2A		[X+2j+k]
		DIV2A		[Z+2j+k]
		Y		X
		[X+2j+k]	Acc	;среднее арифметическое от центров точек
		;теперь удаляем правое пятно
		X		Heap
		[SP]		CALL(MergeBlobCase)
		X		Y
		JMP		@@EndOfCycle


На новом АЛУ этот код выполнится на 4 такта быстрее.

Ещё кусок:
@@RightMerge:	ADD		[Z+1]	;в аккумуляторе лежало x-X-D/2-D1/2. Теперь прибавили D, получили x-X+D/2-D1/2
		DIV2A		D1p2	;прибавили D1/2, получили x-X+D/2 - новый диаметр пятна
		[Z+1]		Acc	;ага, записали.
		;теперь подкорректировать X-координату
		DIV2		Acc
		ADD		[SP+1]
		SUB		1
		[Z+2j+k]	Acc
;а теперь с чистой совестью отправляем задание на обработку точки
		JMP		TaskPending


Должно выполняться на 3 такта быстрее. Что тут улучшать - не знаю.

Дальше начинается "работа со списками":
		;если добрались досюда, значит памяти хватило. X содержит адрес указателя на новую точку, а вот Z содержит адрес самой точки!
		;наполним её содержимым!						
		;на первую строку всегда попадаем в результате прыжка!
@@AfterListOp:	[Z+2j+k]	[SP+1]	;X-координата точки
		X		Z		;для дальнейшей работы (после MidCycle)... Чтобы мы не взялись за только что добавленную точку!
		[Z+2j+1]	[SP+2j]
		[Z+1]		D1		;гориз. размер точки (будет расти при слияниях, а поначалу D, т.к мы сюда включаем и )
		;и теперь ещё нужно выдать задания на обработку, СРАЗУ.
		[SP]		CALL(AcqNoCheck)

;теперь надо посмотреть - а есть ли точка? Или мы уже прошли последний отрезок между точками?
;но у нас в конце списка правая фиктивная точка - её надо игнорировать!			
;улучшенный вариант:
		%CheckHazards OFF
@@MidCycle:	X		[X+k]
		Y		X
		%CheckHazards ON
		ABS		[X+k]
		JO		@@FinalRange


Тут ничего не улучшается: команда АЛУ ровно одна, и переместить её куда-то не удастся. Ну и ладно...

;запрашиваем отрезок, где ожидаем точку. Первой придёт яркость, как всегда
@@EndOfCycle:	[SP+2j+1]	GPUL			;яркость
		[SP+1]		GPUH			;пока не забыли - сразу второе слово запрашиваем (коорд точки), чтобы не сбить весь FIFO 
		C		Nil			;по умолчанию ставим метку "за нами должок!"				
	;входит ли этот отрезок в уже найденное пятно?
		Acc		[X+2j+1]
		DIV2A		[X+1]
		SUB		[SP+2j+k]
		JGE		@@ActPointsStart

	;возможно, мы ещё не очень далеко ушли от пятна, и как оказывается, пятно здесь продолжается
		SUB		nD1
		JL		@@RemoveBlob

	;да, мы ещё близко. Но превышает ли яркость порог?
		Acc		Threshold		;чем выше значение - тем ЧЕРНЕЕ
		SUB		[SP+2j+1]		;поэтому если получится значение меньше нуля - значит точка тусклая, расширять пятно не стоит
		JL		@@RemoveBlob
	;раз оба раза перехода не было, значит пора пятно сдвигать немного вниз!
	;просто прибавим единицу и к диаметру, и к Y-координате
		Acc		[X+2j+1]
		ADD		1
		[X+2j+1]	Acc
		NOP		0
		Acc		[X+1]
		ADD		1
		[X+1]		Acc
		JMP		@@ActPointsStart


Разворачиваем "бешеную деятельность" по оси Y. На новой АЛУ выполняется немножко лучше, экономится по несколько тактов тут и там. Не шибко много, т.к очень часто расставлены условные переходы, которые останавливаются и ждут, когда АЛУ досчитает.

Ну и остатки с барского стола:
;пора эту точку перетаскивать в другой список... 
@@RemoveBlob:	X	AllPoints
		[SP]	CALL(ListOp)
		X	Y			;теперь [X] ссылается уже не на обработанную и удалённую точку, а на предыдущую, так что всё верно
		JMP	@@ResetPending	;ура...					
;до PixelsProcessed проскрипели, теперь последний участок запросить на обработку, и синхроимпульс для кучи
				
; ------------------------------------------ Через эту линию код не идёт (только перепрыгивает) ------------------------------------------------------------------												
				
@@FinalRange:	ACQ	WholeRow
		ACQ	HSync
		Acc	[SP+2j]
		SUB	ImgHeight
		ADD	ImgHeightP1
				
;на @@NewRow мы переопределим и Y, и X, и [SP], так что можно...
;это приготовления уже к transfer, но чтобы избежать хазарда, пришлось сюда перенести. Вообще, это нам сжирает лишних 3600 тактов = 144 мкс. 
		Y	ActivePoints	;это заведомо фиктивная, и указывает либо на другую фиктивную, то ли на реальную
		X	AllPoints
		Y	[Y+k]			;это уже может быть реальная точка, а может быть правой фиктивной
		[SP]	@@Transfer																				
				
		JL	@@newRow
		;усё, отстрелялись...
			


@@Transfer:	ABS	[Y+k]
		JL	ListOp		;если [Y+k]=NULL, значит пора закругляться							
				
ProcessFrame endp


Тут немножко строки перемешаем, чтобы распараллелить работу:
@@FinalRange:	ACQ	WholeRow
		ACQ	HSync
		Acc	[SP+2j]
				
		Y	ActivePoints	;это заведомо фиктивная, и указывает либо на другую фиктивную, то ли на реальную
								
		SUB	ImgHeight
		X	AllPoints											
				
		ADD	ImgHeightP1		
		;на @@NewRow мы переопределим и Y, и X, и [SP], так что можно...
		;это приготовления уже к transfer, но чтобы избежать хазарда, пришлось сюда перенести. Вообще, это нам сжирает лишних 3600 тактов = 144 мкс. 
		Y	[Y+k]			;это уже может быть реальная точка, а может быть правой фиктивной				
		[SP]	@@Transfer																				
				
		JL	@@newRow
		;усё, отстрелялись...
			
@@Transfer:	ABS	[Y+k]
		JL	ListOp		;если [Y+k]=NULL, значит пора закругляться	


То, что в комментарии мы писали, как код, засунутый внутрь цикла ради экономии в 1 слово кода, сжирает за весь кадр 3600 тактов - уже неправда. Ничего он не сжирает!


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

Recent Posts from This Journal

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

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

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

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: 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 

  • 0 comments