nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Тестируем захват ближ. дист. на "сбалансированном" QuatCore (2)

В прошлый раз обнаружили, что нужно "протянуть" в модуль QuatCoreMem не только шины PreDestAddr и PreDestStall, но ещё и PipeStall, так что эти PreDestAddr будут "защёлкиваться" в DestAddr и прочие регистры только при условии PipeStall = 0. Исправляется элементарно, было так:
always @(posedge clk) begin
	MemWrite <= DestSquareBrac & isDest;
	RegWrite <= (~DestSquareBrac) & isDest;
	DestCountSP <= isDest & PreDestAddr[5] & PreDestAddr[4] & PreDestAddr[1] & PreDestAddr[0];
	DestAddr <= PreDestAddr[5:0];
end


а стало так:
always @(posedge clk) if (~PipeStall) begin
	MemWrite <= DestSquareBrac & isDest;
	RegWrite <= (~DestSquareBrac) & isDest;
	DestCountSP <= isDest & PreDestAddr[5] & PreDestAddr[4] & PreDestAddr[1] & PreDestAddr[0];
	DestAddr <= PreDestAddr[5:0];
end


Как ни странно, размер проекта даже уменьшился, раньше он синтезировался в 541 ЛЭ, из которых 204 регистра, а теперь - в 536 ЛЭ, из которых 198 регистров. Оно и ясно, Quartus понял, что 6-битный DestAddr здесь - это в точности те же регистры, что и младшие 6 бит DestAddr в QuatCoreCodeROM, и лишние выкинул.

Запускаем симуляцию, и картинка сразу обнадёживает:



Снова выпишем листинг программы:

00  FD00              SP          Stack
Find2Points proc
01  CD01              X           Points2D    ;используется с индексом i, чтобы выбрать точки 0..6
02  ED02              Z           Fx1     ;используется с индексом j, чтобы выбрать точки 1..7
03  A103              j           6       ;в дальнейшем будет выбор между 5 и 6 (если рассматривать 7 найденных точек вместо 8)
04  F001              [SP+1]      0       ;обнуляем. А "Y" (индексы) можно не обнулять, заведомо будут занесены на первой же итерации     
05  A0A1  @@j_loop:   i           j       ;сравниваем точку под индексом j+1 со всеми остальными, чей индекс меньше j+1
06  A204  @@i_loop:   k           1
07  FC01              [SP]        0       ;сравниваем с точкой i. Начинаем считать квадрат расстояния
08  8900              NOP         0 ;AUTOMATICALLY INSERTED BY TRANSLATOR TO PREVENT HAZARD
09  80EA  @@k_loop:   Acc         [Z+2j+k]    ;это Fy[j+1], если k=1, или Fx[j+1], если k=0
0A  83C9              SUB         [X+2i+k]    ;это Fy[i], если k=1, или Fx[i], если k=0
0B  9C80              SQRD2       Acc     ;разность возвести в квадрат
0C  82FC              ADD         [SP]
0D  FC80              [SP]        Acc
0E  AA05              kLOOP       @@k_loop
0F  83F0              SUB         [SP+1]  ;сравниваем с самой большим квадратом дистанции на данный момент
10  B806              JL          @@skip  ;меньше, не интересно
11  F0FC              [SP+1]      [SP]        ;программисты на ассемблерах x86, AVR и ARM должны завидовать, что у нас такое можно!
12  DDA4              Y           ijk     ;и такому
13  A803  @@skip:     iLOOP       @@i_loop
14  A907              jLOOP       @@j_loop
15  A7DD              ijk         Y
16  A000              i           7
17  FCB0              [SP]        Call(SwapPoints)
18  A7DD              ijk         Y
19  A107              j           5
1A  FCB0              [SP]        Call(SwapPoints)
Find2Points endp
1B  B008  endless:    JMP endless
SwapPoints  proc
1C  A204              k           1
1D  8900              NOP         0   ;хотим избежать warning'ов
1E  8AEA  @@swap:     C           [Z+2j+k]
1F  EAC9              [Z+2j+k]    [X+2i+k]
20  C983              [X+2i+k]    C
21  AA09              kLOOP       @@swap
22  B0FC              JMP         [SP]
SwapPoints  endp    


Да, теперь во время ожидания прыжка на шине данных лежит адрес для прыжка, 0x13. Но раз уж прыжка не произошло, начинает выполняться следующая строка, в [SP+1] заносится квадрат расстояния между точками 7 и 6, 0x241A (см первую часть)

Далее, в регистр Y у нас заносится значение 0x00C6. Это регистры i,j,k, Inv, "упакованные" в 16 бит. Выразим это в двоичном виде:
0000 0000 1100 0110 или:

Inv    k      i    j
0    00000 00110 00110


Да, всё верно, i=j=6, тем самым мы закодировали пару точек, которые на текущий момент считаем наиболее отдалёнными друг от друга.

Далее идёт iLOOP, мы уменьшаем i на единичку, до 5, и прыгаем в начало внутреннего цикла.

Что ж, выглядит неплохо. Давайте попробуем сразу посмотреть результаты после окончания этих 3 вложенных циклов. Внутренний цикл (две итерации по k) выполняется примерно за 3 мкс. Всего он должен посчитаться 8*7/2 = 28 раз, чтобы посчитать квадраты расстояний между каждой возможной парой точек. Так что через 3*28 = 84 мкс должно всё завершиться. Вот оно:


По логике, мы должны были на последней итерации посчитать квадрат расстояния между точками 0 и 1:
Fx0:        00    14528
Fy0:        01    -2944
Fx1:        02    -14016
Fy1:        03    -7872


И он должен получиться равен ( (14528-(-14016))^2+(-2944-(-7872))^2 ) / 2 / 32768 = 12802,8125, округлится до 12803 = 0x3203. Да, видим на скриншоте это значение.

Далее это значение сравнивается с текущим максимумом, 0x5301, понимаем, что максимум обновлять не стоит, поэтому пропускаем две команды (прыгаем на @@skip), на iLOOP и jLOOP также не делаем прыжков, и выходим на команду "ijk Y". Видим на шине данных значение 4, это значит i=0, j=4, или точки с индексами 0 и 5. Те, что на этом рисунке мы назвали 1 и 6, не знаю уж почему:

MarkedPointsAtBeginning.png

Но это неверно! Самыми отдалёнными должны были стать 3 и 6 на картинке, или индексы 2 и 5 у нас в списке!

Посчитаем ручками квадрат расстояния между этими точками. Вот список всех точек:
Fx0:        00    14528
Fy0:        01    -2944
Fx1:        02    -14016
Fy1:        03    -7872
Fx2:        04    29376
Fy2:        05    -11456
Fx3:        06    22720
Fy3:        07    -13568
Fx4:        08    -18752
Fy4:        09    -20736
Fx5:        0A   -25664
Fy5:        0B   -20800
Fx6:        0C   14848
Fy6:        0D   -23488
Fx7:        0E   -9408
Fy7:        0F   -27648


Выходит ( (29376-(-25664))^2 + (-11456-(-20800))^2 ) / 2 / 32768 = 47557 = 0xB9C5.

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

Оказалось, проблема ещё проще: переполнение при вычитании!
У нас получилось -25664 - 29376 = -55040. Это значение ещё способно вмещаться в аккумулятор, в нём сверху дополнительный бит. Но при передаче его на вход АЛУ, этот "верхний" бит положить уже некуда, и значение "насыщается" до -32768. В итоге сумма квадратов получается существенно меньше, чем должна была быть - и по другим точкам удаётся получить результаты повыше. Из-за этого самыми отдалёнными были признаны 0 и 5:

( (14528-(-25664))^2 + (-2944-(-20800))^2 ) / 2 / 32768 = 29514,0625.

Сразу тревожно стало за алгоритм дальней дистанции - там у нас похожие вычисления идут, даже более зверские, сумма квадратов дальностей от каждой точки до всех остальных! Кажется, что ничего плохого случиться не должно, там ровно одна точка очень хорошо отдалена от остальных, и пущай даже при нахождении суммы дальностей до неё начнётся такое переполнение, благодаря насыщаемой арифметики мы всё равно поймём, что она наиболее отдалена, и поставим её куда надо. Правда, потом ещё начнём её координаты вычитать из координат всех остальных (ShiftOrigin), чтобы правильно их расположить против часовой стрелки, там тоже насыщение может случиться, тогда мы вообще эти координаты "потеряем". Надо будет посмотреть. Вообще, такая ситуация, когда мишень занимает буквально ВЕСЬ ЭКРАН - вырожденная, не должно такого в реальности случаться! Успокаивает, что во всех таких случаях мы не будем выдавать заведомо ошибочные данные. Да, аффинный алгоритм (алг. захвата) может что-то и посчитать, своё "нулевое приближение", но он его передаст на алгоритм сопровождения, и тот на ошибочных данных незамедлительно "сорвётся", не сможет сопоставить "виртуальные точки" (его представление, где на экране должны быть расположены мишени) с реальными. Поэтому просто не выдадим никаких, и придётся перейти на какой-то другой прибор или на ручное управление. Записал эту проблему себе в список "недоделок", потом погляжу...

А пока надо "разделаться" с переполнением на ближней дистанции. Пожалуй, самое простое - заменить строки
@@k_loop:	Acc	[Z+2j+k]	;это Fy[j+1], если k=1, или Fx[j+1], если k=0
		SUB	[X+2i+k]	;это Fy[i], если k=1, или Fx[i], если k=0


на

@@k_loop:       DIV2	[Z+2j+k]	;это Fy[j+1], если k=1, или Fx[j+1], если k=0
		DIV2S	[X+2i+k]	;это Fy[i], если k=1, или Fx[i], если k=0


То есть не просто значение заносится в аккумулятор, но и делится на 2. И не просто вычитается значение, а вычитается значение, делёное на 2. После возведения в квадрат ответы будут получаться и вовсе в 4 раза меньше, т.е вместо 47557 будет 11889. Ну и ладно, нам эти числа сами по себе не нужны с огромной точностью, только лишь для сравнения.

Давайте попробуем этот исправленный вариант:


В этот раз всё верно. Тот самый максимум 11889 = 0x2E71 мы и получили, и затем в ijk занесли значение 0x0044. Я поначалу очень расстроился, "прочитав" это как i=4, j=4, что очевидно неверно. Опять начал всё проверять и перепроверять, искать, где же закралась ошибка. Оказалось, никакой ошибки, просто регистры у нас 5-битные, и нужно эти 0x0044 расписать в двоичном виде:
0000 0000 0100 0100, или

Inv    k      i       j
0    00000  00010   00100 


То есть, i=2, j=4, что соответствует индексам 2 и 5, как и должно быть.

Наконец, посмотрим содержимое оперативной памяти по окончании работы программы:


Нас интересуют 4 последних значения на первой строке. Имеем по сути:
Fx6 = 0x72C0 = 29376  (раньше это был Fx2)
Fy6 = 0xD340 = -11456 (раньше это был Fy2)
Fx7 = 0x9BC0 = -25664 (раньше это был Fx5)
Fy7 = 0xAEC0 = -20800 (раньше это был Fy5)



Отлично! Две самые отдалённые точки действительно были перенесены в конец массива, как и было задумано. Ну и процессор, похоже, не "испортился" от нашего вмешательства, работает корректно. И команду ijk проверили - пашет, очень удобно бывает. Только её работу "на глаз" оценивать неудобно, с толку сбивают 5-битные регистры.
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 

  • 0 comments