nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

QuatCore: пересылки "память-память"

Это у меня больная тема. Поначалу, пока только писал ассемблерный код, не до конца представляя, как он будет осуществляться "в железе", я допускал, что и источником данных, и получателем, может стать память. И "философия" TTA (Transport-Triggered Architecture) просит максимальной "ортогональности", когда две половинки команды, Src и Dest, максимально независимы друг от друга и могут выступать в произвольных комбинациях.

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

Теперь же, когда вроде бы успешно "разогнал" этот процессор с 4 МГц до 25 МГц за счёт введения конвейера на 3 ступени, вдруг понял, что в качестве бесплатного бонуса, пересылки "память-память" стали доступны!

Присвоить одну локальную переменную другой - пожалуйста:
[SP+1]  [SP]


Поменять два значения в памяти местами - пожалуйста:
     C           [Z+2j+k]
     [Z+2j+k]    [X+2i+k]
     [X+2i+k]    C


Да хоть даже скопировать область памяти:
        i      31
@@loop: [Z+i]  [X+i]
        iLOOP @@loop


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


Здесь это очень просто - нужно лишь сдвинуть левый столбец вниз на одну строку. В первом случае мы имеем такой "контекст":
	JL	@@skip
	[SP+1]	[SP]
	X	j


Сдвигаем левый столбец:
  ....    @@skip
  JL      [SP]
  [SP+1]  j
  X       ...

И мы видим: СНАЧАЛА происходит выборка [SP], а запись в [SP+1] идёт после этого, поэтому одного формирователя эффективного адреса вполне достаточно. При этом другие команды тоже не страдают.

Посмотрим, как два значения в памяти меняются местами в некотором контексте:

SwapPoints	proc
		k		1
@@swap:		C		[Z+2j+k]
		[Z+2j+k]	[X+2i+k]
		[X+2i+k]	C
		kLOOP		@@swap
		JMP		[--SP]
SwapPoints	endp	


Тут и вовсе можно изобразить весь процесс целиком:
  DestDiscard  1
  k            [Z+2j+k]
  C            [X+2i+k]
  [Z+2j+k]     C
  [X+2i+k]     -5
  kLOOP        [--SP]
  JMP          SrcDiscard


DestDiscard / SrcDiscard означает, что какая бы команда здесь ни находилась, выполнена она не будет.

Как видно, и здесь все обращения к памяти были очень красиво распиханы ровно по одному на строку!

Так бывает не всегда, конечно. Если мы попытаемся провести несколько пересылок "память-память" подряд, вроде такого:
  [SP+1] [SP++]
  [SP+1] [SP++]

(сместить два значения "вперёд")

то оно при выполнении превратится в такое:
  ...     [SP++]
  [SP+1]  [SP++]
  [SP+1]  ...

И конфликт явно присутствует.

А вот если пересылка производится в цикле, то такого не случится:
        i      31
@@loop: [Z+i]  [X+i]
        iLOOP  @@loop


И за это надо поблагодарить "нерасторопность" наших прыжков, съедающих по 2 команды. Выглядит примерно так:
  ...           31
  i             [X+i]
  [Z+i]         -3
  iLOOP         SrcDiscard0
  DestDiscard0  SrcDiscard1
  DestDiscard1  [X+i]
  [Z+i]         -3
  iLOOP         SrcDiscard0 
  ...


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

         i     31
@@loop:  C     [X+i]
         [Z+i] C
         iLOOP @@loop

На выполнение каждой итерации уходило 3 такта, на частоте не более 6 МГц.

Сейчас на выполнение каждой итерации уходит 5 тактов на частоте в 25 МГц. Даже здесь ускорение в 2,5 раза.

Давайте глянем на симуляции, всё тот же многострадальный FindMDD3 (поиск самой отдалённой точки). В прошлый раз мы очень подробно анализировали выполнение двух вложенных циклов: прошли все итерации внутреннего и вышли на вторую итерацию "среднего".

Дальше давайте в пол-глаза. У нас есть 4 точки:
F0 (53;-7),
F1 (480;-30),
F2 (-539;-302),
F3 (400; -997)

В прошлый раз мы отследили, как было найдено выражение

(-997-(-997))2+(-997-(-302))2+(-997-(-30))2+(-997-(-7))2

и ещё делённое на 65536, если воспринимать их как целые числа. Если делить в самый последний момент, получается 36,594, что стоило бы округлить до 37. Но мы округляли отдельные части, и получили суммарно 36, или 0x24. Сойдёт...

Теперь нужно ещё досчитать сумму квадратов дальностей точки F3 до всех остальных, для чего посчитать
(400-(-539))2+(400-480)2+(400-53)2

и также делённое на 65536. Должно получиться 15,389, или, если округлять каждое слагаемое независимо, то 13 + 0 + 2 = 15 - то же самое. В результате, по окончании двух внутренних циклов (при итерации внешнего цикла j=3) мы должны получить 36+15=51 = 0x33.

И именно тогда мы должны "вырваться" на PC=0x17, до которого до сих пор дойти "не могли". Так что перемотаем "осциллограмму" до этого знаменательного момента:


Всё верно: заносим в [SP] обновлённое значение 0x33. Затем следует iLOOP - переход не происходит. Затем kLOOP - и снова перехода не происходит. Причём здесь на выполнение уходит 2 такта, поскольку столько нужно для выборки [SP+1].Если переход выполняется, мы забраковываем "полукоманду" [SP+1], поэтому она нас не тормозит :) А здесь она полноценно выполняется.

Далее мы вычитаем из аккумулятора значение [SP+1] - "текущий максимум суммы квадратов расстояний некоторой точки до всех остальных", оно было нулевым. И тем временем заносим на шину данных единичку, это величина относительного прыжка, если хотим пропустить обновление максимума. Раньше это была тройка, но PC у нас идёт с опережением в два шага, и транслятор это учёл :)

По JL (Jump if LESS) перехода не последовало, поскольку текущее значение [SP] (и оно же лежало с Acc) оказалось выше максимума, и вычитание [SP+1] дало положительное значение. Тем временем, заносим в шину данных значение [SP].

На следующем шаге заносим [SP], уже помещённое на шину данных, в [SP+1], т.е обновляем максимум. Вот она, пересылка память-память! И в то же время, на шину данных помещаем значение регистра j, тройку.

Далее, тройку (индекс точки, которая максимально отдалена от остальных) заносим в регистр X, а попутно кладём в шину данных значение -16 - это величина прыжка для цикла по j.

Наступает jLOOP - у нас j=3, так что нужно делать прыжок. Команду по SrcAddr объявляем недействительной, меняем PC на 0x0B. Ещё разок приведём листинг процедуры FindMDD3:

        FindMDD3    proc
08  DD18                  Y       Points2D
09  F000                  [SP+1]  0   ;максимальная отдалённость, инициализируем нулём
0A  A103                  j       3
0B  A201      @@j_loop:   k       1   ;также от 0 до 3, чтобы все расстояния просуммировать
0C  FC00                  [SP]    0   ;здесь будет храниться текущая сумма
0D  A003      @@k_loop:   i       3   ;от 0 до 1, т.е значения X и Y
0E  80DA      @@i_loop:   Acc     [Y+2j+k]    ;загрузили одно значение
0F  83D9                  SUB     [Y+2i+k]    ;вычитаем второе
10  9C80                  SQRD2   Acc         ;возводим в квадрат
11  82FC                  ADD     [SP]        ;прибавляем к пред. значению
12  FC80                  [SP]    Acc
13  A879                  iLOOP   @@i_loop
14  AA77                  kLOOP   @@k_loop
15  83F0                  SUB     [SP+1]  ;можно и "пожертвовать" значением в Acc,
16  B001                  JL      @@skip
17  F0FC                  [SP+1]  [SP]    ;двухпортовая память-это зашибись!
18  CDA1                  X       j
19  A970      @@skip:     jLOOP   @@j_loop
1A  A0CD                  i       X
1B  CD18                  X       Points2D
1C  ED18                  Z       Points2D
1D  F3B1                  CALL    SwapPoints  ;потёрли текущую сумму (лежала в [SP])-и хрен с ней
        FindMDD3    endp


Как видно, прыгнули мы ровно туда, куда заказывали :)

И затем началась очередная итерация, теперь ищем сумму квадратов дальностей от F2 до всех остальных точек, то есть

(-302-(-997))2+(-302-(-302))2+(-302-(-30))2+(-302-(-7))2+(-539-400)2+(-539-(-539))2+(-539-480)2+(-539-53)2

Должно получиться значение 44=0x2C. Смотрим, что там "на самом деле":


Вышло 0x2B, опять из-за преждевременного округления ошиблись на единичку. Действительно, получается

7,37+1,12+1,32+13,45+15,84+5,34 = 44,44, но:
7+1+1+13+16+5 = 43 = 0x2B.

Ничего страшного.

Данное значение меньше ранее найденного 51, поэтому "обновлять максимум" мы не должны, должны перепрыгнуть через две строки. Но на осциллограмме мы этого прыжка не наблюдаем - PC растёт монотонно, как и в прошлый раз!

Я уже настроился залезть глубоко в отладку, проверять, почему прыжок не осуществился, но пригляделся повнимательнее - всё правильно! Дело в том, что прыгнуть приказано было НА ЕДИНИЦУ, т.е заменить PC к следующему такту на PC+1. И почему мы этого не увидели ?!

О прыжке могут сказать SrcDiscard=1, возникший на 2 такта и задержанный относительно него DestDiscard=1. То есть, мы наткнулись на интересный частный случай, где PC ведёт себя как ни в чём не бывало, а две команды на конвейере "отменяются", и получается ровно то, что нам надо.

Да, мы отменили выборку из [SP], о чём свидетельствует выполнение в 1 такт, а не в два. Затем отменили запись результата в [SP+1] (обновление максимума) и отменили запись регистра j в X (обновление индекса точки, для которой достигнут максимум). А вот значение (-16) для прыжка по jLOOP мы уже заносим, и jLOOP исполняем. Теперь становится j=1, и поехали дальше.

Вот мы проверили две ветви исполнения, всё работает как надо. Поэтому дальше пробежим ещё быстрее - и посмотрим выход уже из внешнего цикла. У нас так и должно остаться X=3, [SP+1]=0x33, т.е самая дальняя точка - под индексом 3.

До сих пор PC у нас доходил до 0x1B, поэтому когда мы увидим 0x1C - это будет окончание всех трёх вложенных циклов. Вот оно:


Действительно, по [SP+1] так и сохранилось 0x33, и на последней итерации обновлять максимум тоже не стали. jLOOP также не вызвал перехода, а тем временем на шину данных отправили содержание регистра X, это тройка. Так что действительно, F3 наиболее отдалённая.

Затем это значение, 3, занесли в регистр i. В регистры X и Z занесли Points2D-адрес начала массива точек. И затем вызываем процедуру SwapPoints. Её вызов тоже "замаскирован" - PC монотонно увеличивается, но команду выхода из процедуры, JMP [--SP] мы в итоге "вычеркнули" из исполнения, и попали аккурат в процедуру.

В процедуре мы присвоили k=1. Затем обратились по адресу [Z+2j+k], и опять словили RAW HAZARD. Мы в итоге взяли значение со СТАРЫМ значением k=0, по адресу 0x18 вместо 0x19, т.е это вышел F0x вместо F0y. Обидно, надо добавить NOP:

SwapPoints  proc
1F  A201              k           1
20  8900              NOP         0
21  8AEA  @@swap:     C           [Z+2j+k]
22  EAC9              [Z+2j+k]    [X+2i+k]
23  C983              [X+2i+k]    C
24  AA7B              kLOOP       @@swap
25  B8FF              JMP         [--SP]
SwapPoints  endp


И ещё одна ошибка обнаружилась в самом процессоре. Когда в качестве источника данных выступает [--SP], стек декрементируется ДВАЖДЫ. Мы корректно ввели взаимосвязи, позволяющие одному модулю заблокировать "соседей", когда это необходимо, но здесь нужно было лишь САМООГРАНИЧЕНИЕ. Заменяем строчку

assign CountSP = ((isDest & DestAddr[5] & DestAddr[4] & DestAddr[1] & DestAddr[0]) | (isSource & SrcAddr[5] & SrcAddr[4] & SrcAddr[1] & SrcAddr[0]));


на строчку

assign CountSP = ((isDest & DestAddr[5] & DestAddr[4] & DestAddr[1] & DestAddr[0]) | (~fetching & isSource & SrcAddr[5] & SrcAddr[4] & SrcAddr[1] & SrcAddr[0]));


и всё должно наладиться. Сейчас проверим:


По крайней мере, здесь работает.

Итак, k=1, затем пропускаем одну команду (NOP 0) и загружаем значение по адресу 0x19, там лежит число F0y=-7=0xFFF9. Это значение заносим в регистр C, а тем временем загружаем значение по адресу 0x1F, там лежит число F3y=-997=0xFC1B.

Данное значение, -997, заносим по адресу 0x19, тем временем на шину данных кладём значение из регистра C, -7.

И наконец, заносим значение -7 по адресу 0x1F (ПОМЕНЯЛИ ИХ МЕСТАМИ, как и задумывалось), тем временем на шину данных заносим число -5, для прыжка.

Далее, проверяем, что k больше нуля, и делаем прыжок на смещение в -5.
Пропустив две случайно затесавшиеся команды, выполняем вторую итерацию, при k=0. Теперь берём значение по адресу 0x18, это F0x=53=0x35, помещаем его в регистр C, тем временем берём значение по адресу 0x1E, это F3x=400=0x0190, его заносим по адресу 0x18, а значение из регистра C - в 0x1E. Второй обмен провели корректно.

Теперь осталось вернуться из двух процедур. Запрашиваем [--SP] на предмет адреса возврата - и получаем число 0x1E, всё верно, это возврат в процедуру FindMDD3. Затем снова запрашиваем [--SP] и получаем число 4 - это возврат в процедуру main, аккурат в бесконечный цикл.

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


Ура: мы выполнили программу от начала до конца, всё сработало как надо в конечном итоге.

Теперь опять не знаю, за что хвататься. Всё надо:
- подрихтовать транслятор, чтобы громко ругался на RAW HAZARD, а то до сих пор не научился сам "на глазок" эти ситуации распознавать в коде, обнаруживаю только на симуляции,
- доработать весь алгоритм захвата, чтобы он смог выполняться на нашем "разогнанном процессоре",
- продолжить работу с видео, ведь наконец-то ОБРАБОТЧИК ВИДЕО и ПРОЦЕССОР РАБОТАЮТ НА ОДНОЙ ТАКТОВОЙ ЧАСТОТЕ!
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 

  • 0 comments