nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

QuatCore+GPU, строка 10

Строка 9 в изображении оказалась скучной. Надеюсь, что сейчас начнётся "мясо":


Тут мы увидим вставку новой точки посередине списка, а потом перемещение "старых" точек из одного списка в другой.


Обработка этой строки начинается так же, как и предыдущей: входной буфер GPU забит, поэтому QuatCore остановился на отправке двух последних заданий на эту строку (WholeRow и HSync). Вот процесс пошёл:


Всё то же самое: отправили оба задания, прибавили единичку к номеру строки, убедились, что эта строка ещё не последняя и прыгнули в начало цикла по строкам, где номер строки, 0x1A, занесли в [SP+2].

Поехали дальше:


Инициализируем регистр X значением 0x10 - адрес первой точки в списке, "левой фиктивной точки". Запрашиваем первый отрезок у GPU. Получаем интересные результаты: яркость 0xBD9. После инверсии это будет 0x426 = 1062 - это выше порога в 512. Координата: 0x05, всё верно. Прыгать в @@MidCycle в этот раз не будем, пора "оформить" новую точку! Но сначала проверить, не "сливается" ли она с точкой левее или правее себя? Тут впору и листинг привести, давно такого праздника не было, как "добавление новой точки"!

10  B845                          JL      @@MidCycle      ;пятна нет, не торопимся заказывать отрезок
11  EDCD                          Z       X       ;Чтобы в Merge всегда использовать Z, независимо от того, левая или правая точка оказались
12  A041                          i       1
13  80F0          @@checkCycle:   Acc     [SP+1]
14  83EA                          SUB     [Z+2j+k]
15  8480                          ABS     Acc
16  FC80                          [SP]    Acc     ;модуль разности - это и будет новый "диаметр" точки, если сработает слияние
17  8F83                          DIV2S   C       ;не будем мудрить пока что, всё "в лоб"
18  8FE0                          DIV2S   [Z+1]                       
19  B871                          JL      @@DoMerge
1A  EDC8                          Z       [X+k]
1B  A837                          iLOOP   @@checkCycle
1C  DD65                          Y       Heap                                    
1D  F3B6                          CALL    ListOp  ;добавит в X новую, пока что пустую точку.
1E  CDED                          X       Z       ;для дальнейшей работы (после MidCycle)... Чтобы мы не взялись за только что добавленную точку!
1F  E083                          [Z+1]   C       ;гориз. размер точки (будет расти при слияниях, а поначалу D, т.к мы сюда включаем и )                                                                                                                      
20  F3B8                          CALL    AcqQueue
21  B063                          JMP     @@MidCycle  ;пропускаем слияние точек, 


Регистр Z будет указывать на "соседнюю" точку, близость с которой мы хотим проверить. Сначала это будет 0x10, "левая фиктивная точка". i=1, замечательно (из непосредственного значения 0x8001 берутся только младшие 5 бит). Загружаем в аккумулятор только что найденную X-координату обнаруженной точки, 5. Вычитываем X-координату соседней точки, в данном случае "левой фиктивной", это 0x8000 - очень отрицательное значение. Результат "насыщается" до 0x7FFF, и от него берётся модуль, давая всё те же 0x7FFF.

Смотрим дальше:


Теперь мы вычитаем из аккумулятора половинку диаметра каждой из точек. У "новой точки" мы предполагаем диаметр 6, у "левой фиктивной" он и вовсе "отрицательный", те же 0x8000. Результатом всего этого может стать только положительное значение, поэтому условный переход на @@Merge не выполняется.

Теперь помещаем в регистр Z адрес точки справа от только что обнаруженной, это будет 0x15. В кои-то веки это не фиктивная точка, а вполне себе реальная! Прыгаем в начало цикла @@Check.

Снова загружаем X-координату только что обнаруженной точки, 0x05. Вычитаем из неё координату точки справа, 0x0E. Результат: 0xFFF7 = -9.

Смотрим дальше:


Да, взятие по модулю даёт ответ 9, после чего мы вычитаем половинку от диаметров двух точек. Обе точки, мы так считаем, имеют диаметр 6. Что-то мне подсказывает, что 9-3-3=3, ответ положительный, так что на @@Merge мы снова не попадаем, и это правильно, точки действительно разнесены.

Дальше мы по чём зря заносим в регистр Z тот же самый 0x15 - и выходим из цикла.

Теперь мы готовимся к добавлению новой точки в список ActivePoints.

Y=Heap=0x13. Напомним: процедура ListOp отцепляет точку, на которую показывает указатель, расположенный по адресу Y, и прицепляет её сразу за узлом, на который указывает регистр X. В данном случае мы "отцепляем" точку из списка Heap, т.е списка "свободных элементов".

В процедуре ListOp мы загружаем значение указателя, лежащего по адресу Y, в аккумулятор и в регистр Z. Это значение 0x1F. Приведём старую картинку:
MemoryMap.png

Всё верно, Heap после того, как от него "отцепили" два элемента, стал указывать на 0x1F. Чтобы убедиться, что это не NULL, вычитаем ноль (операция вычитания выставляет флаг знака).

Смотрим дальше:


[Y] = [Z] : теперь Heap указывает на 0x24, т.е "откусили" из этого списка ещё один элемент.
Не перешли на @@OutOfMemory, поскольку список Heap ещё не опустел. Хорошо.
[Z] = [X] : новый элемент теперь указывает не на 0x24 (формируя список Heap), а на 0x15, т.е на нашу "первую точку".
[X] = Z : точка левее нас теперь указывает не на 0x15, а на новый элемент, 0x1F.

На этом процедура успешно завершается. А будь у нас обычный массив - пришлось бы сдвигать вправо 2 элемента по 4 записи в каждом (X,Y-кординаты, яркость и диаметр), а то и 3, если с "правым фиктивным". Так всё-таки эффективнее.

Присваиваем X = Z = 0x1F, чтобы не взяться за только что добавленную точку. Ведь GPU нам выдаёт отрезки в соответствии со "старым" списком!.

Теперь надо заполнить все значения для только что добавленной точки. Диаметр заносим сразу: 6. Для остального запускаем процедуру AcqQueue.

Да, в кои-то веки в ней выполняется цикл @@updCycle. С его помощью мы помещаем яркость точки, 0xBD9, затем Y-координату, 0x0A,


и наконец X-координату, 0x05.

После этого "озадачиваем" GPU новыми отрезками, 5 - (6/2) = 2 - это первый, 5 + (6/2) = 8 - это второй. Сейчас во входном буфере находилось всего одно "задание", HSync (оно ещё выполняется), а стало 3. Тем временем, в выходном буфере нас дожидаются результаты по 4 отрезкам.

Опять с большими спотыканиями возвращаемся сначала из процедуры, а потом на метку @@MidCycle. Здесь можно было такой же финт ушами провернуть, вместо

CALL  AcqQueue
JMP   @@MidCycle


сделать

[SP++] @@MidCycle
NOP    CALL(AcqQueue)


т.е ручками сформировать адрес возврата для процедуры, а "реальный" адрес возврата выкинуть. Два такта сэкономим видимо.


Смотрим дальше:


Кстати, здесь прыжок всё-таки заметен, на PC=0x23 мы застреваем на лишний такт. Это как раз оно!

Начинается @@MidCycle. Адрес текущей точки, 0x1F, мы на всякий случай заносим в регистр Y, вдруг придётся следующую точку удалять. В регистр X заносим адрес следующей точки, 0x15, это наша самая первая обнаруженная точка. Затем из обнулённого аккумулятора вычитаем адрес точки, следующей за этой, это 0x1A. Раз это не NULL, значит, пора уточнить координаты текущей точки, с адресом 0x15.

В аккумулятор заносим яркость текущей точки (из списка), 0x39A, после чего запрашиваем параметры отрезка у GPU. Получаем 0xFFF (нулевая яркость) и координату 0.

Смотрим дальше:


Здесь мы "скрытно" прыгнули на @@NotSoBright, после чего проверяем Y-координату. Взяли номер текущей строки, 0x0A. Вычитаем Y-координату нашей точки из списка, 0x07. Затем ещё вычитаем половину диаметра (6) этой точки, что должно нам дать ноль. Приведём листинг этого дела:

2F  80FE          @@NotSoBright:  Acc     [SP+2j] ;текущий номер строки
30  83C2                          SUB     [X+2j+1]    ;вычитаем Y-координату  ранее обнар. точки. Ответ всегда положительный, т.к считаем по строкам "вверх"
31  8FC0                          DIV2S   [X+1]       ;ну и размер точки, в кои-то веки уполовиненный
32  B84F                          JL      @@QueueAnyway   ;здесь ОБЯЗАН быть именно JL, т.к флаг знака является одним из "аргументов" для AcqQueue
33  CD45                          X       AllPoints
34  F3B6                          CALL    ListOp
35  CDDD                          X       Y       ;теперь [X] ссылается уже не на обработанную и удалённую точку, а на следующую, так что всё верно
36  B019                          JMP     @@ActPointsStart    ;ура...                 


Впервые за всё время симуляции у нас не сработал переход на @@QueueAnyway, что означает: точку пора удалять из списка ActivePoints!

Начинаются строчки, которые мы ни разу ещё не проверяли...

X = AllPoints = 0x11. Всё верно. А в регистре Y у нас "предусмотрительно" лежит адрес предыдущей точки в списке, 0x1F.
С такими "вводными" вызываем процедуру ListOp.

В ней значение, лежащее по адресу [Y], помещается в аккумулятор, это 0x15, та самая точка, которую нам бы переместить в AllPoints.

Смотрим дальше:


Проверяем, что в [Y] не NULL. Эта проверка избыточна: по логике работы программы, здесь никогда не будет NULL, не зря же стоят левая и правая фиктивные точки. Так что такты теряем (из своей жадности, не захотели делать специализированные процедуры, сделали взамен ровно одну), рано или поздно это нам может аукнуться.

То же самое значение [Y] заносится в регистр Z.

[Y] = [Z] = 0x1A. То есть, наша точка с адресом 0x1F (добавленная прямо на этой строке) указывала на следующую, 0x15, а теперь будет указывать сразу на 0x1A. Тем самым, точка уже "выскочила" из списка ActivePoints.

[Z] = [X] = 0x8000. То есть, точка, которую мы "выцепили" из ActivePoints будет дальше ссылатся туда, куда ссылался AllPoints, на NULL. Так что из пустого списка у нас получается список из одного элемента.

[X] = Z = 0x15. AllPoints ссылался на NULL, теперь ссылается на нашу точку.

Всё хорошо :)

Изобразим, как теперь выглядит память:


Да, теперь здесь три списка: Heap, ActivePoints и AllPoints.

По возвращению из процедуры присваиваем X = Y = 0x1F, т.е он ссылается на точку, которая предшествовала удалённой. После этого мы прыгаем в начало цикла по обработке точек из списка, @ActPointsStart.

Похоже, у нас дефицит времени: через 41 такт сбросится выходной буфер GPU, а нам ещё 3 отрезка надо успеть обработать! Причём во втором тоже сейчас начнётся веселье... Ну да ладно, сейчас посмотрим, потом будем думать.

Запрашиваем самый короткий отрезок в 1 пиксель и получаем результат: яркость 0xFFF (нулевая) и координата 0.


Разумеется, здесь мы точку не добавляем, переходим сразу в @@MidCycle. Сейчас внимательно: в регистр Y заносится 0x1F (адрес точки, которую обнаружили на этой строке), а в X после этого заносится 0x1A, это точка справа сверху. Затем проверяем, что у этой точки ссылка не нулевая (т.е она не "фиктивная"), после чего наконец-то принимаемся за следующий отрезок, по "уточнению координат пятна". Запрашиваем у GPU результаты, получаем яркость 0xFFF (нулевая) и координату 0. Сравнение с предыдущей яркостью, 0x6BD, тогда явно было поярче.


Прыгнули на @@NotSoBright, после чего начали проверять Y-координату. Ровно такие вычисления уже были, и окончились точно так же: точку пора удалить!

Снова присваиваем X=AllPoints=0x11, а чуть ранее поставили Y=0x1F, и вызываем ListOp. Было так:

X=AllPoints: 11 0015
  
Elem1:       1A 0012

Y=Elem2:     1F 001A




Сейчас первым делом Z = Acc = [Y] = 0x1A. Проверяем, что это не NULL - так и есть :)
Затем [Y] = [Z] = 0x12. То есть, по адресу 0x1F переправили значение на 0x12, но только сохранив исходное значение в рег. Z:
X=AllPoints: 11 0015
Z=Elem1:     1A 0012
Y=Elem2:     1F 0012

Так что если раньше Elem2 указывал на Elem1, а тот в свою очередь на 0x12, то теперь Elem2 указывает на 0x12 напрямую, и Elem1 мы "выкинули" из этого списка.

Затем [Z] = [X] = 0x15.
X=AllPoints: 11 0015
Z=Elem1:     1A 0015
Y=Elem2:     1F 0012

Так что Elem1 больше не ссылается на продолжение своего старого списка, ActivePoints, а ссылается на 0x15.

Наконец, [X] = Z = 1A:
X=AllPoints: 11 001A
Z=Elem1:     1A 0015
Y=Elem2:     1F 0012

Так что теперь первым элементом AllPoints является Elem1, а уже он ссылается на более старый Elem0 (0x15). Сойдёт. Получается, что наш AllPoints работает как стек: последним вошёл - первым к тебе обратятся. По-моему, особой разницы нет.

Неплохо.

Вернувшись из процедуры, мы присваиваем X = Y = 0x1F, потому как к началу цикла @@ActPointsStart регистр X должен указывать на точку СЛЕВА от обрабатываемого отрезка. А таковой (и вообще единственной) осталась точка с адресом 0x1F, та, которую мы добавили только на этой строке.

Прыгаем в начало цикла - и запрашиваем последний отрезок на этой строке. Вот только когда мы вернулись из процедуры ListOp, уже исполнилось "задание" HSync, и обнулило выходной буфер GPU... Дальше всё пойдёт под откос
Самое смешное, что нам не хватило 8 тактов (!), чтобы успеть вытащить все точки из выходного буфера!


"Покрытие кода" составило 99%: мы увидели в действии все строки кода, кроме одной-единственной, сидящей по метке @@DoMerge.

В целом, работает, но несколько медленнее, чем я предполагал, на удивление много "накладных расходов". В принципе, в нашей "тестовой картинке" слишком короткие строки, всего 281 такт на каждую. Поставь мы нормальные 1024 пикселя, а потом ещё свыше 200 тактов обратный ход - и у нас бы всё сработало. Но эта картинка - далеко не самое сложное, что нам может попасться. Сложнее всего мне представляется обработать нечто такое:


Найдётся там строчка, особенно если мы под особо неудачным креном будем лететь, когда единовременно придётся удалить около 6 точек, и в то же самое время добавить ещё несколько. Тут мы с удалением двух точек и добавлением третьей застряли на все 281 такта. В принципе, 1024 такта (плюс обратный ход) нам за глаза, но самую малость всё равно хочу ускориться. Больно видеть, как мы бессмыссленно тратим такты.
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

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

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

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

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

  • 3 comments