nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Супрематический алгоритм обнаружения на ассемблере готов!

Ладно, прекратим рассматривать два обособленных варианта, обойдёмся без AUP (Acquire UPdate, команда для видеопроцессора, чтобы не добавлять новое задание на обработку, а откорректировать уже отправленное).

Ещё возникла идея, что отказавшись от сравнения яркостей точек (только сравнение с порогом), мы могли бы и не получать яркость как таковую, лишь индикацию, что она выше пороговой. И работай мы исключительно с командой ACQ, это действительно уменьшило бы размер выходного буфера (вместо 8..12 бит на каждую яркость хватило бы 1 бита - "выше или ниже порога") и на пару слов объём кода. Но для TRK (TRacKing) - нахождения яркостного центра с субпиксельной точностью - всё равно эти биты в выходном буфере нужны, поэтому заморачиваться не хочу! Пущай будет как есть, в конце концов нам удалось скрестить ежа с ужом, т.е сумматор яркостей с обнаружителем самого яркого пикселя! (и подправленный вариант)

Нам осталось не так уж много:
- процедура TaskPending,
- слияние двух пятен, либо пятна с точкой справа от него,
- слияние пятна с точкой снизу от него.
- по мелочам: повсюду расставить "флажки" о том что нужно позже выдать задания на обработку, а при добавлении нового пятна записать его координаты (раньше это делала процедура AcqAndUpdate, которая приказала долго жить).

Начнём с первой:

TaskPending proc
		ABS	C
		JNO	[SP]		;вот в чём прелесть стека без инкремента!
		;если дошли до сюда, заказываем отрезки на обработку
AckNoCheck:	Acc	[X+2j+k]
		DIV2S	[X+1]	;теперь в аккмуляторе у нас X - Ceil(D/2)
		ACQ	Acc		;первый отрезок
		ADD	[X+1]	;а вот теперь X + Floor(D/2)
		ACQ	Acc		;второй отрезок
		JMP	[SP]
TaskPending endp	



После долгих и по большей части бессмысленных раздумий, мы решили при вызове нескольких "внутренних" процедур хранить адрес возврата в [SP], но не делать инкремент, что упрощает работу, если вызывать их нужно "по условию", или возврат из процедуры мы делаем по условию, как здесь на второй строке, "JNO [SP]".

При обычной архитектуре, мы могли бы предположить что JNO [--SP] сделает декремент лишь в том случае, когда условие выполняется. Но здесь у нас SrcAddr и DestAddr "сами по себе, свои собственные", причём правая часть, SrcAddr, выполняется тактом ранее. Поэтому декремент происходил бы ВСЕГДА, что не соответствует нашей логике "условный возврат из процедуры". Ну а если "побочного эффекта" в виде декремента у нас не будет - то проблема исчезает сама собой :)

И сразу же таким же способом поменяем ListOp. Так оно было раньше:

ListOp proc			
		ZAcc	RoundZero
		Z	[Y+k]
		SUB	[Y+k]
		[Y+k]	[Z+k]
		JGE	@@OutOfMem									
		[Z+k]	[X+k]
		[X+k]	Z
		NOP	0
		JMP	[--SP]
@@OutOfMem:	[--SP]	Call(OutOfMemory)	;SP возвращается на место, но выпрыгиваем в другое место, на обработку ошибки
ListOp endp


Здесь по той же причине мы не могли сразу же вернуться из процедуры на метку OutOfMemory, а выпрыгивали сначала вниз на @@OutOfMem, а уже там на OutOfMemory, чтобы не "запороть" стек. Если же условится, что [SP] просто локальная переменная, где хранится адрес возврата (такое допустимо, если эти процедуры не вызывают других процедур, в том числе себя рекурсивно - так оно и есть), то одной строкой становится меньше:
ListOp proc			
	ZAcc	RoundZero
	Z	[Y+k]
	SUB	[Y+k]
	[Y+k]	[Z+k]
	JGE	OutOfMemory									
	[Z+k]	[X+k]
	[X+k]	Z
	NOP	0		;избежать Memory hazard (одновременный доступ на чтение и запись)
	JMP	[SP]
ListOp endp	


При добавлении нового пятна мы первым делом вызывали ListOp, после чего "ручками" заносили диаметр точки: D1, а затем вызывали AcqAndUpdate, чтобы поставить координаты пятна и его яркость, и тут же выдать задания на обработку для видеопроцессора:

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


и сразу после этого начиналась процедура AcqAndUpdate. Но теперь её нет, поэтому @@AfterListOp будет идти непосредственно перед @@MidCycle, и должна будет содержать код для установки координат пятна. яркость пока проигнорируем, похоже, что и без неё всё будет работать :) Получается так:

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


Здесь строки стоят ровно в том порядке, чтобы не возникало одновременного чтения из памяти и записи в неё на одном такте. Затем мы вызываем процедуру AcqNoCheck (это другая "точка входа" в TaskPending - пропускаем проверку "флажка"), и возвращаемся в кои-то веки куда положено, на строчку сразу вслед за этой.

Сразу за @@MidCycle у нас шла проверка - может мы нашли "под" ранее найденным пятном более яркую точку, и тогда центр нужно сместить вниз:

	[SP+2j+1]	GPUL		;яркость
	Acc		GPUL
	SUB		[X+4j+k]						
	[SP+1]		GPUH		;пока не забыли - сразу второе слово запрашиваем (коорд точки), чтобы не сбить весь FIFO 
	[SP++]		@@ActPointsStart	;нам по-любому придётся вернуться именно сюда!
	JL		AcqAndUpdate	;отсюда "выпрыгнем" сразу на метку @@ActPointsStart						


Тут нас ждёт упрощение: сравнивать яркость с яркостью пятна мы уже не хотим (даже записывать эту яркость не стали), и прыгать нам никуда не надо, так что не будем в стек заносить адрес возврата. Получится вообще так:
	[SP+2j+1]	GPUL		;яркость
	[SP+1]		GPUH		;пока не забыли - сразу второе слово запрашиваем (коорд точки), чтобы не сбить весь FIFO 


Самый-самый минимум: просто получить все результаты от видеопроцессора!

Далее идёт проверка по Y-координате, "входим ли мы ещё в состав этого пятна", и если да - посылаются задания на обработку, но БЕЗ обновления параметров пятна:
	;ветвь исполнения, если старая точка оказывалась ярче.
	;Нужно сообразить: не пора ли ей на покой, то бишь в список AllPoints?
	;в кои-то веки работаем с Y-координатой!
	Acc		[X+2j+1]	;координата точки (из списка)
	DIV2A		[X+1]		;прибавить половинку её диаметра
	SUB		[SP+1]	;вычесть текущий номер строки
	JGE		AcqNoUpd	;здесь ОБЯЗАН быть именно JGE, т.к флаг знака является одним из "аргументов" для AcqQueue


Комментарии уже устаревшие: когда у нас появились "точки входа" AcqNoUpd и AcqAndUpdate, сохранять флаг знака стало ненужным. Сейчас разница в том, что если условие выполнено, мы должны просто установить C=-32768 (метка что "за нами должок" по заданиям на обработку) - и вернуться в начало цикла. Причём, поскольку в двух случаях из 3, нам нужно выставить эту метку, мы просто поставим её заранее, т.е вот так:

	C		Nil		;по умолчанию ставим метку "за нами должок!"
	[SP+2j+1]	GPUL		;яркость
	[SP+1]	GPUH		;пока не забыли - сразу второе слово запрашиваем (коорд точки), чтобы не сбить весь FIFO 

(это код сразу за @@MidCycle, когда мы убеждаемся, что есть пятно, которое надо обработать).

И теперь в "первом ветвлении" мы сразу уходим в начало цикла по пятнам:
	Acc	[X+2j+1]		;координата точки (из списка)
	DIV2A	[X+1]			;прибавить половинку её диаметра
	SUB	[SP+1]		;вычесть текущий номер строки
	JGE	ActPointsStart

Халява, сэр. Далее, если прыжка не выполнялось, мы приступали к удалению пятна, точнее, переносу его из списка ActivePoints в AllPoints. Но сейчас нужно добавить ещё один вариант: что, если мы лишь на пару строк ушли ниже пятна, и там всё ещё имеем превышение порога обнаружения?

Сейчас в аккумуляторе лежит значение Y + D/2 - y. Нам нужно проверить знак Y + D/2 - y + D1, но это не очень удобно, т.к ADD не меняет флаг знака! Специально я вводил эту асимметрию, полагая, что когда мы проверяем знак, всегда сможем поменять плюсы на минусы, и у непосредственные значения мы можем вводить со знаками как "плюс" так и "минус", поэтому в большинстве ситуаций сможем сами выбирать, нужно ли менять флаг знака, или пусть он хранит предыдущее значение.

Можем ввести ещё одну константу, "-D1" (к сожалению, компилятор у меня туповатый и вычислять "константные выражения" не умеет) и сделать SUB -D1. Но можем и действительно всю эту штуку взять с другим знаком: сначала y - Y - D/2, а затем ещё вычесть D1. Так что многострадальные 4 строки перепишем так, и добавим к ним ещё 5:
	Acc	[SP+1]		;координата точки (из списка)
	DIV2S	[X+1]		;прибавить половинку её диаметра
	SUB	[X+2j+1]	;вычесть текущий номер строки
	JL	ActPointsStart
;возможно, мы ещё не очень далеко ушли от пятна, и как оказывается, пятно здесь продолжается
	SUB	D1
	JL	@@RemoveBlob	;уже далеко, пора его удалять!
	;да, мы ещё близко. Но превышает ли яркость порог?
	Acc	Threshold	;чем выше значение - тем ЧЕРНЕЕ
	SUB	[SP+2j+1]	;поэтому если получится значение меньше нуля - значит точка тусклая, расширять пятно не стоит
	JL	@@RemoveBlob
	;раз оба раза перехода не было, значит пора пятно сдвигать немного вниз!


И вот ровно здесь будет код для обновления Y-координаты пятна ("вниз") и его диаметра. Пока что, в модели мы написали выражения
D' = y - Y + D/2,
Y' = y - D'/2


но здесь их можно существенно упростить. Ведь это по горизонтали нам могли выдать точку отодвинутую на 1..3 пикселя вправо или влево, а здесь - она будет отодвинута НА ОДИН ПИКСЕЛЬ, поскольку мы так обрабатываем, строку за строкой! И нас вполне устраивает прибавить к диаметру ровно единичку, а вот к Y-координате мы собирались прибавлять "полпикселя", и здесь с этим могут быть проблемы, ведь храним мы координату целочисленно. На модели получилось, что достаточно и к одному, и к другому прибавить единичку - и всё будет нормально работать! В конце концов, когда пятно смещается чуть сильнее чем надо вниз, на одну строку дольше мы считаем что находимся "внутри пятна", почему бы и нет.

Вот тут бы нас порадовала команда INC из x86, способная прибавить единицу К ЧЕМУ УГОДНО, даже к значению лежащему в памяти! Но у нас такого нет, поэтому столь простое действие разворачивается аж в 3 строки: загрузить из памяти, прибавить 1, вернуть на место.
Здесь помогло бы, сделай мы некий аналог LEA (Load Effective Address), когда мы можем не только обращаться к памяти командами [X+1], [X+2j+1] и пр, но и просто кидать на шину данных посчитанный адрес, то бишь X+1, X+2j+1 и т.д. Но адресов SrcAddr чего-то маловато, в общем, не буду пока всё напропалую перекраивать ради этого одного места...

Получается вот так:
	;просто прибавим единицу и к диаметру, и к Y-координате
	Acc		[X+2j+1]
	ADD		1
	[X+2j+1]	Acc
	NOP		0
	Acc		[X+1]
	ADD		1
	[X+1]		Acc
	JMP		ActPointsStart


ОТВРАТИТЕЛЬНО! Ещё и NOP затесался (чтобы разнести запись в память и чтение из неё), и не знаю, как здесь обойтись без него, никакой возможности переставить эти строки местами! Можно было бы сделать такую вещь:

	;просто прибавим единицу и к диаметру, и к Y-координате
	Acc		[X+2j+1]
	ADD		1
	%CheckHazards off
	Acc		[X+1]
	[X+2j+1]	Acc
	%CheckHazards on
	ADD		1
	[X+1]		Acc
	JMP		ActPointsStart

То есть, у нас тогда совпадает по времени запись нового значения в Acc и чтение старого значения в память. Только вот в нашем АЛУ стоит своя собственная блокировка (interlock) которая задерживает чтение, пока не завершится запись! Так что здесь такой фокус не проходит.

Ну да ладно, не так уж это всё и страшно. Подумаешь, 14 байт на прибавление единички к двум значениям из памяти!

Сразу за этим кодом идёт @@RemoveBlob - перенесение текущего пятна в список AllPoints:

@@RemoveBlob:	X	AllPoints
		[SP]	CALL(ListOp)
		X	Y			;теперь [X] ссылается уже не на обработанную и удалённую точку, а на следующую, так что всё верно
		JMP	@@ResetPending	;ура...					


И поясним, что такое @@ResetPending. В начале цикла по пятнам появилась новая строка:

@@newRow:		[SP+2j]		Acc
			X		ActivePoints	;начинаем цикл по всем активным точкам
						
@@ResetPending:		C		0			;уж явно не 0x8000			
		;даже если список пуст, первую половину цикла мы пройдём, она касается отрезка, предшествующего точке из списка
@@ActPointsStart:	[SP+2j+1]	GPUL			;яркость самой яркой точки на отрезке


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

И остался последний кусочек кода: слияние двух пятен, либо поглощение пятном точки справа от себя

Сначала проверим, нужно ли делать слияние двух пятен:

;обнаруженная точка примыкает к пятну слева от себя. Возможно, потребуется слияние и с пятном справа от себя
;X указывает на пятно слева, Z - на пятно справа 
@@LeftMerge:	Acc	[Z+2j+k]	;взяли X-координату правого пятна
		SUB	[X+2j+k]	;вычитаем X-координату левого
		DIV2S	[Z+1]		;вычитаем радиус правого пятна
		DIV2S	[X+1]		;и радиус левого пятна
		SUB	D1		;и минимально допустимый диаметр пятна
		JL	@@MergeBlobs	;делаем слияние ПЯТЕН


Ничего сложного, обычная арифметика. Далее, код, отвечающий за поглощение пятном точки (он идёт непосредственно после 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 
	[X+1]		Acc		;обновили диаметр левого пятна.
	NOP		0
	;теперь подкорректировать X-координату
	Acc		[SP+1]		;берём координату обнаруженной точки
	DIV2S		[X+1]		;вычитаем половинку диаметра
	[X+2j+k]	Acc
	JMP		@@AckNoCheck	;если слева от нас есть РЕАЛЬНОЕ пятно (фиктивное мы трогать не можем, его X-координата "-32768", условие заведомо не выполнится),
	;значит проверять "есть ли за нами должок" не нужно - точно есть!


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

И наконец, слияние пятен (метка @@MergeBlobs). Сначала левому пятну нужно обновить координаты:
@@MergeBlobs:	Acc		[X+1]
		ADD		[Z+1]
		[X+1]		Acc	;диаметр равен сумме диаметров
		ZAcc		RoundZero
		DIV2A		[X+2j+k]
		DIV2A		[Z+2j+k]
		[X+2j+k]	Acc	;среднее арифметическое от центров точек


Среднее арифметическое сначала хотел найти более очевидным путём:
  Acc   [X+2j+k]
  ADD   [Z+2j+k]
  DIV2  Acc


но тогда снова получался Hazard: на одном и том же такте мы отправляем результат предыдущей работы в [X+1], и тут же пытаемся прочитать [X+2j+k]. А в выбранном варианте такого нет (инициализируем аккумулятор нулём, прибавляем половинку первого значения, и половинку второго значения).

Далее, правое пятно надо УДАЛИТЬ, то есть перенести из списка ActivePoints в список Heap:
	;теперь удаляем правое пятно
	Y		X
	X		Heap
	[SP]		CALL(MergeBlobCase)


Пока так... Вот, что такое MergeBlobCase:

;взять первый элемент из списка 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	


Это очередная "точка входа" в процедуру ListOp, потому что именно здесь у нас Z указывает сразу куда надо (собственно, на удаляемое пятно), и "нехватки памяти" случиться заведомо не может, поскольку мы ВОЗВРАЩАЕМ элемент в Heap, а не берём из него! Экономим аж 5 тактов на этом деле :) Такое вот дело жадность.

И финальный "костыль": чтобы не сбиться в уже обработанных отрезках, мы должны ещё разок пройтись по тому же самому пятну!
Для этого нужно пропустить участок @@MidCycle, где мы переходим к следующему пятну и проверяем, "не пора ли закругляться". Проще всего это сделать, указав правильный адрес возврата, поэтому наш код для удаления пятна чуть изменим:
	;теперь удаляем правое пятно
	Y		X
	X		Heap
	[SP]		@@EndOfCycle
	JMP		MergeBlobCase


Это же решит проблему с "долгом" - мы проверим ещё два отрезка, и ещё один ВСЛЕД за правым пятном (вдруг оно ещё сильнее расширится, или даже сольётся ещё с одним) - и вот когда вся эта завершится, мы наконец-то дадим задание на обработку!

НЕУЖЕЛИ ВСЁ???



Попробуем хотя бы откомпилить всё это безобразие. Старая версия компилится в 206 слов кода (412 байт) и 329 слов данных (658 байт), это "весь проект": выставить тактовую частоту 25 МГц, инициализировать ЖК-экранчик и выдать на него "приветствие", обработать кадр и выдать в удобочитаемом виде результаты этой обработки, а затем передать дамп памяти, и его же передать в случае какого-то из прерываний или нехватки памяти.

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

Компилиться он сходу не захотел, возмутился на команду [Z+2j], которой у нас нет, есть взамен [Z+2j+k] (и мы решили, что k=0 на всём протяжении, также как и j=1). Да, ошибся малость.

Далее ему не понравилась строка
@@MidCycle:	%CheckHazards OFF


ну да, привередливый, поэтому сделал метку всё-таки по самой команде:
		%CheckHazards OFF
@@MidCycle:	X		[X+k]


Потом он не нашёл метку ActPointsStart, и правильно сделал: о собаках-то я и забыл, @@ActPointsStart. Затем не нашёл ProcessFrame::AckNoCheck, и снова был прав, эта метка называлась AcqNoCheck, и была без "собак" (а значит никаких ProcessFrame::). Та же фигня с TaskPending.

И, наконец, оно откомпилилось, выдав ещё 2 Hazard'a (и автоматически их исправив добавлением NOP). Как результат получается 248 слов кода (496 байт) и 297 слов данных (594 байта) Понятно, 64 байта сэкономили в оперативке (за счёт 32 элементов списка обнаруженных пятен, где по слову откусили), но вот код усложнился...

Но есть шанс, что он по крайней мере будет работать :)
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

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

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

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

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

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

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

  • Ковыряемся с сантехникой

    Наконец-то закрыл сколько-нибудь пристойно трубы, подводящие к смесителю, в квартире в Москве: А в воскресенье побывал на даче, там очередная…

  • Мартовское велосипедное

    Продолжаю кататься на работу и с работы на велосипеде, а также в РКК Энергию и на дачу. Хотя на две недели случился перерыв, очередная поломка,…

  • Обнаружение на новом GPU - первые 16 мс

    Закончилась симуляция. UFLO и OFLO ни разу не возникли, что не может не радовать. За это время мы дошли до строки 0x10F = 271. Поглядим дамп памяти:…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 3 comments