nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Алг. ближней дистанции, сортировка "слева направо"

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



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


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

;содержание регистров на этот момент
;X = Points2D (начало массива найденных точек)
;Y содержит индексы самых отдалённых точек (уже потеряло актуальность)
;Z = Fx1 (сдвинуто на 1 точку отн. X)
;k=0
;j=5
;i - индекс одной из самых отдалённых точек (потеряло актуальность)
;[SP] указывает на первую строку SortByProjection (адрес возврата, когда вызывали SwapPoints последний раз)
;[SP+1] содержит 1/8 квадрата расстояния между двумя самыми дальними точками (потеряло актуальность)
SortByProjection proc


Регистры X и Z нам очень даже подходят: во время сортировки тоже очень удобно иметь эту сдвижку на 1 элемент, чтобы пройти по "нижнему треугольнику" матрицы, т.е сравнить всех со всеми, но только по одному разу, и не сравнивать элемент с самим собой.

Но прежде чем начать сортировку, нужно построить вектор из точки 6 в точку 7. Его длина не так уж важна, главное только направление. Что-то мне подсказывает, что его нужно "уполовинить", чтобы ещё и здесь переполнение заведомо не словить.

К сожалению, чтобы "достать" эти две точки, нам никак не хватит j=5. С его помощью можно обратиться к 5-й и 6-й точке, но никак не к 7-й. Ладно, придётся ещё регистр i задействовать, что ж поделать. Выходит вот так:

;увы, через j=5 мы до точки 7 не дотягиваемся.
		i		7
;нужно временное хранилище под вектор, соединяющий точки 6 и 7. Пусть это будет a11 и a12 (пока они не нужны, и понадобятся нескоро)
		Y		a11
;вариант "напрямую" (без цикла)
		; DIV2		[X+2i+1]
		; DIV2S		[Z+2j+1]
		; [Y+1]		Acc
		; NOP		0		;избежать Hazard по одновременному чтению и записи в память
		; DIV2		[X+2i+k]
		; DIV2S		[Z+2j+k]
		; [Y+k]		Acc
;выходит 7 команд

;вариант с циклом
		k		1
@@Dif:		DIV2		[X+2i+k]
		DIV2S		[Z+2j+k]
		[Y+k]		Acc
		kLOOP		@@Dif
;выходит 5 команд, всяко лучше. 


Как видно, имеет смысл вводить цикл даже на 2 итерации, потому как иначе всё равно приходится NOP вставлять (или компилятор сам вставит).

Правда, k=1 надо перенести повыше, иначе RAW Hazard на первой строчке цикла (выборка памяти [X+2i+k] происходит в то же время, что и защёлкивание значения 1 в "k", поэтому возьмём старое значение, 0). Тогда и i=7 надо оставить снаружи цикла, а вот "Y a11" можно поместить вовнутрь, из жадности (сэкономится аж 1 такт):
	k		1
;увы, через j=5 мы до точки 7 не дотягиваемся.
	i		7		
@@Dif:	DIV2		[X+2j+k]
;нужно временное хранилище под вектор, соединяющий точки 6 и 7. Пусть это будет a11 и a12 (пока они не нужны, и понадобятся нескоро)
	Y		a11
	DIV2S		[Z+2i+k]
	[Y+k]		Acc
	kLOOP		@@Dif


Хорошо, вектор у нас есть. Далее, мы могли бы сразу найти скалярное произведение каждой точки с этим вектором, и использовать эти числа как "ключи" для сортировки, с вычислительной точки зрения это самое быстрое. Ведь у нас самая долгая операция - это умножение (нет в моей ПЛИС аппаратного умножителя), сделаем 12 умножений (по 2 на каждую точку) - и дальше останется только вычитание, чтобы сравнивать ключи. Но неудобно: нужно вслед за каждой точкой ещё и этот ключ таскать, и как-то хитро ко всему этому обращаться. Наверное, проще будет брать разность между точками, помножать её скалярно на наш вектор - и сразу же реагировать на знак результата, тогда ничего хранить не придётся. Но алгоритм сортировки я хочу самый простой, например "простым выбором", там ожидается 6*5/2 = 15 сравнений: сначала делаем 5 сравнений, чтобы найти самую крайнюю точку, переносим её в хвост. Затем 4 сравнения из оставшихся, и снова переносим в хвост. Затем 3, и 2, и 1, итого 15. Так что вместо 12 умножений получим целых 30, зато "накладных расходов" поменьше, и код попроще :)

Такой вот шаг вперёд и два назад: долго и мучительно ускоряем сам QuatCore с 4 до 25 МГц, потом отдельно берёмся за АЛУ и ускоряем его, а потом вдруг рраз - и выбираем заведомо неэффективные алгоритмы. Никакого противоречия нет: быстрый QuatCore с быстрым АЛУ нам нужен при обработке изображения в реальном времени, а эти все алгоритмы на фоне - вообще ни о чём, ну потеряем чуть менее 13 микросекунд на этой сортировке, ОДИН РАЗ ЗА КАДР, жалко что ли? Если потом останется лишняя память - можно будет чуть всё это дело ускорить, чисто для красоты.

Спустя ещё некоторое время, решил ещё сильнее пожадничать по части размера кода (уж очень хотелось бы, чтобы весь код + оперативная память уместились в 5 килобайт, тогда я в ХС6Т влезу, а это зверь по части радстойкости, и напряжения удобные!)

В общем, получается такая вот хреновина:
;теперь начинаем сортировать. Более компактный, но более медленный код, где скалярные произведения считаются "на лету", вместо того чтобы посчитать заранее
		j		4
		[SP]		@@loopEnd	;чтобы сделать условный вызов процедуры и вернуться из неё куда надо		
@@j_loop:	i		j
		;Делаем "сдвинутую" адресацию [Fx1 + 2j + k], т.е j=4..0 пробежит индексы от 5 до 1 
		;но при этом, i = 4..0 пробежит индексы от 4 до 0. 
		;хотим в индекс j+1 поставить "самую большую", для этого надо выбрать между j+1,...0

;вариант без цикла по k (то есть, k=0 всегда)
;самый топорный (с разворачиванием разности в отдельные умножения и накопление в акк)
@@i_loop:	C		[Y+k]
		MUL		[Z+2j+k]
		FMS		[X+2i+k]
		C		[Y+1]
		FMA		[Z+2j+1]
		FMS		[X+2i+1]
;6 команд, под конец проверяем знак. Но 4 умножения вместо 2. 		
		JGE		SwapPoints
@@loopEnd:	iLOOP		@@i_loop
		jLOOP		@@j_loop


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

(xj+1 - xi)*vx + (yj+1 - yi)*vy

поставив его эквивалент с раскрытыми скобками:

xj+1*vx - xi*vx + yj+1*vy - yi*vy

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

Вот весь код целиком:
;содержание регистров на этот момент
;X = Points2D (начало массива найденных точек)
;Y содержит индексы самых отдалённых точек (уже потеряло актуальность)
;Z = Fx1 (сдвинуто на 1 точку отн. X)
;k=0
;j=5
;i - индекс одной из самых отдалённых точек (потеряло актуальность)
;[SP] указывает на первую строку SortByProjection (адрес возврата, когда вызывали SwapPoints последний развернуться)
;[SP+1] содержит 1/8 квадрата расстояния между двумя самыми дальними точками (потеряло актуальность)
SortByProjection proc
		k		1
;увы, через j=5 мы до точки 7 не дотягиваемся.
		i		7		
@@Dif:		DIV2		[X+2j+k]
;нужно временное хранилище под вектор, соединяющий точки 6 и 7. Пусть это будет a11 и a12 (пока они не нужны, и понадобятся нескоро)
		Y		a11
		DIV2S		[Z+2i+k]
		[Y+k]		Acc
		kLOOP		@@Dif

;теперь начинаем сортировать. Более компактный, но более медленный код, где скалярные произведения считаются "на лету", вместо того чтобы посчитать заранее
		j		4
		[SP]		@@loopEnd	;чтобы сделать условный вызов процедуры и вернуться из неё куда надо		
@@j_loop:	i		j
		;Делаем "сдвинутую" адресацию [Fx1 + 2j + k], т.е j=4..0 пробежит индексы от 5 до 1 
		;но при этом, i = 4..0 пробежит индексы от 4 до 0. 
		;хотим в индекс j+1 поставить "самую большую", для этого надо выбрать между j+1,...0

;вариант без цикла по k (то есть, k=0 всегда)
;самый топорный (с разворачиванием разности в отдельные умножения и накопление в акк)
@@i_loop:	C		[Y+k]
		MUL		[Z+2j+k]
		FMS		[X+2i+k]
		C		[Y+1]
		FMA		[Z+2j+1]
		FMS		[X+2i+1]
;6 команд, под конец проверяем знак. Но 4 умножения вместо 2. 		
		JGE		SwapPoints
@@loopEnd:	iLOOP		@@i_loop
		jLOOP		@@j_loop
SortByProjection endp



Вся программа "алгоритма захвата ближней дистанции" сейчас занимает 54 слова кода (108 байт), из которых 9 слов будут "общими" с алгоритмом дальней дистанции, 25 слов - "поиск двух наиболее отдалённыхточек" и 19 слов - наша "сегодняшняя" сортировка. Сейчас попробуем всё это запустить...
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

  • Тестируем atan1 на QuatCore

    Пора уже перебираться на "железо" потихоньку. Решил начать с самого первого алгоритма, поскольку он уже был написан на ассемблере. В программу внёс…

  • Формулы приведения, что б их... (и atan на ТРЁХ умножениях)

    Формулу арктангенса на 4 умножениях ещё немножко оптимизировал с помощью алгоритма Ремеза: Ошибка уменьшилась с 4,9 до 4,65 угловой секунды, и…

  • Алгоритм Ремеза в экселе

    Вот и до него руки дошли, причина станет ясна в следующем посте. Изучать чужие библиотеки было лениво (в том же BOOSTе сам чёрт ногу сломит), писать…

  • atan на ЧЕТЫРЁХ умножениях

    Мишка такой человек — ему обязательно надо, чтоб от всего была польза. Когда у него бывают лишние деньги, он идёт в магазин и покупает какую-нибудь…

  • Ай да Пафнутий Львович!

    Решил ещё немного поковыряться со своим арктангенсом. Хотел применить алгоритм Ремеза, но начал с узлов Чебышёва. И для начала со своего "линейного…

  • atan(y/x) на двух умножениях!

    Чего-то никак меня не отпустит эта тема, всё кажется, что есть очень простой и эффективный метод, надо только его найти! Сейчас вот такое…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments