nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Тест сортировки "слева направо"

Пора нашу программу проверить, хотя бы на симуляции.

Сразу же обнаружил ошибку, при вычислении вектора нужны были индексы 6 и 7, а я перепутал X с Z, и получились 5 и 8, зашибись.


Пока всё хорошо.


Вставим "дамп памяти" по результатам первого этапа (поиска двух наиболее отдалённых точек):
wf06.png

Наши точки - на верхней строке, последовательно: x0, y0, x1, y1, и так далее до x7, y7.

И кусок листинга кода:
SortByProjection proc
1B  A204              k       1
1C  A000              i       7       
1D  8CCA  @@Dif:      DIV2    [X+2j+k]
1E  DD08              Y       a11
1F  8FE9              DIV2S   [Z+2i+k]
20  D880              [Y+k]   Acc
21  AA09              kLOOP   @@Dif
22  A10A              j       4
23  FC0B              [SP]    @@loopEnd   ;чтобы сделать условный вызов процедуры и вернуться из неё куда надо        
24  A0A1  @@j_loop:   i       j
25  8AD8  @@i_loop:   C       [Y+k]
26  90EA              MUL     [Z+2j+k]
27  93C9              FMS     [X+2i+k]
28  8AD0              C       [Y+1]
29  92E2              FMA     [Z+2j+1]
2A  93C1              FMS     [X+2i+1]
2B  BC0C              JGE     SwapPoints
2C  A80D  @@loopEnd:  iLOOP   @@i_loop
2D  A90A              jLOOP   @@j_loop
SortByProjection endp


Ну и наблюдаем, что взяли Y6 = 0xD340 = -11456, вычитаем Y7 = 0xAEC0 = -20800, причём всё делим на два, чтобы переполнения не было, и должны получить Vy = 4672 = 0x1240, его и получаем.

То же самое по горизонтали: взяли X6 = 0x72C0 = 29376 (одно из самых больших положительных значений), вычитаем X7 = 0x9BC0 = -25664 (одно из самых больших отрицательных), результат делится пополам, и должны получить Vx = 27520 = 0x6B80, так и есть.

Вектор нашли, уже хорошо.
Далее некоторая инициализация - и начинаем сортировку. В регистр C (второй операнд для умножения) запихали Vx, затем умножили его на X5 = 0xDB40 = -9408, а потом из результата вычитаем Vx*X4, где X4 = 0xB6C0 = -18752.

По логике, должны получить 27520 * (-9408 + 18752) / 32768 = 7847,5, что при нашем округлении "до ближайшего целого" (прибавить 0,5 и отрезать дробную часть) должно дать 7848 = 0x1EA8.

Глянем на следующем слайде:


Ах да, мы же скалярное произведение считаем. С одной координатой разобрались, за другую взялись. В регистр C положили Vy, к акк. прибавили Vy*Y5, где Y5 = 0x9400 = -27648, вычитаем Vy*Y4, где Y4 = 0xAF00 = -20736 . Должно было выйти 7847,5 + 4672 * (-27648 + 20736)/32768 = 6862 ровно.

Ответ мы на шине так и не увидим, т.к смотрим мы лишь на флаг знака, с помощью команды JGE. Очевидно, прыжок должен выполниться, и мы видим, что он выполняется.

Выглядит неплохо. С индексами как будто бы не напутали, значения берутся ожидаемые.

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

Да, заканчивается где-то к 150-й микросекунде. То есть, около 60 мкс уходит на всю сортировку. Если это поделить на 15 итераций, выйдет по 4 мкс на итерацию, это 100 тактов. На каждое умножение идёт 18 тактов, их там 4, выходит 72 такта, но ещё "накладные расходы", в том числе вызов процедуры SwapPoints, где ещё небольшой цикл.

И смотрим дамп памяти по окончании работы:


Можно заметить, что координата X для этих 6 точек идёт практически по нисходящей, только точки 1 и 2 в обратном порядке. Изобразим это на рисунке:




Отлично! Если бы мы просто сортировали по компоненте X, то точки 1 и 2 вышли бы в другом порядке. Но если мысленно провести линию между крайними точками и расположить точки вдоль неё, то получим ровно тот результат, что дал алгоритм.

Пока не будем заморачиваться со случаем 7 точек вместо 8 (чуть позже доделаем), а в первую очередь сделаем выделение центральных точек. Поскольку они вынесены вперёд, то при различных ракурсах они могут очень основательно "гулять" относительно остальных!
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

Recent Posts from This Journal

  • Тестируем 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 

  • 3 comments