nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

QuatCore: вроде начинаю понимать...

Пожалуй, Transport-Triggered Architecture (TTA) - очень неплохой вариант.

Инструкция процессора ровно одна, грубо говоря MOV. Раз она всего одна, значит, её и указывать не надо. Все команды имеют одинаковую длину - 16 бит - и состоят из двух 8-битных "адресов", Dest и Src, т.е адреса источника и получателя данных.

К этим 2 шинам адреса и двум шинам данных подключаются модули Mem (доступ к оперативной памяти, управление стеком и индексными регистрами), ALU (арифметическо-логическое устройство - сложение, вычитание, умножение с накоплением, а в перспективе и деление, и может что-нибудь более хитрое типа CORDIC), PC (Program Counter), Imm (Immediate), в дальнейшем могут появиться и другие.

К оперативной памяти мы всегда обращаемся косвенно, через регистры X, Y, Z и SP (Stack Pointer). Первые 3, как правило, означают адреса левого операнда, правого операнда и результата (например, при умножении кватернионов). Также есть несколько индексов, по крайней мере, два: i и j, которые тоже можно использовать при доступе к памяти, и также сделать для них автоинкремент.

Процедура для перемножения кватернионов выглядит так:
Procedure QuatMultiply
        Acc 0
loop:   B [Y+i^j]
        FMPM [X+i++]
        JiNZ loop
        [SP+j++] Acc
        JjNZ QuatMultiply
output: [Z+j] [SP+j++]
        JjNZ output
        JMP [--SP]
End procedure

и занимает 18 байт.

Процедура для поворота вектора с помощью кватерниона - вот так:
Procedure RotateVecByQuat
Inv 1
[SP++] PC
JMP QuatMultiply
Inv 0
X Y
Y Z
JMP QuatMultiply
End procedure

и занимает 14 байт.

Процедура для нахождения обратной нормы кватерниона - вот так:
Procedure QuatInvNorm
      Acc 1
loop: B [X+i]
      FMAD2 [X+i++]
      JiNZ loop
      [Z+j] Acc
      JMP [--SP]
End procedure

и занимает 12 байт.


Procedure / End procedure - в команды не транслируются, это по сути namespace, чтобы можно было раз за разом использовать метки наподобие loop, и они друг другу не мешали.

loop: и output: - это метки, само собой, они тоже в команды не транслируются. Также меткой является сам заголовок, например QuatMultiply.

Всё остальное - команды. Каждая команда - это два числа, Dest Src, но чтобы понимать, что тут вообще происходит, всем числам от 0 до 255 присвоены весьма хитрючие имена.

Адреса Dest и адреса Src, кстати говоря, не обязаны совпадать, чаще всего они этого и не делают. К примеру, адреса 0..127 в Src принадлежат офигительно простому модулю Imm (Immediate), который по 124-му адресу выдаст 16-битное число 124, по 0-му адресу выдаст 0, и так далее - так мы можем не усложнять формат команды. Для Dest делать то же самое было бы бессмыссленно, там мы "резервируем" лишь нулевой адрес в качестве /dev/null. Тогда команда, состоящая из всех нулей, будет переправлять /dev/zero в /dev/null - классика, и вполне может сойти за NOP.

Разберём процедуру перемножения кватернионов, строка за строкой.
Аргументы ей передаются просто внутри регистров - в регистре X лежит адрес левого операнда, в регистре Y - правого, в Z - адрес результата, который в нашей реализации может совпадать с X или Y. Адрес возврата был занесён по адресу SP, но тут же к нему прибавили единичку, поэтому сейчас по адресу SP, а также SP+1, SP+2 и т.д. (но без фанатизма!) мы можем хранить локальные переменные.
Сейчас мы ещё предполагаем, что при вызове процедуры будет i=0, j=0, хотя потом можем передумать... Ещё есть интересный 1-битный регистр Inv - если перед вызовом этой процедуры мы выставим Inv=0, то это будет простое умножение кватернионов, а если Inv=1 - то второй операнд будем брать сопряжённым.

Acc 0 - мы обнуляем аккумулятор. В него нельзя занести какое угодно значение, можно лишь обнулить (хотя в реальности в него заносится "половина младшего бита", чтобы отсекание 15 бит результата приводило к округлению "до ближайшего целого"), а можно занести значение "-3/2" для нормировки кватернионов. Т.е когда адресом получателя является Acc, мы из шины данных возьмём лишь младший бит. Если он нулевой - обнулим, если единичный - занесём "-3/2". Возможно, занести в него произвольное 16-битное значение тоже было бы удобно - посмотрим. Если понадобится - сделаем.

B [Y+i^j] - заносим на один из входов АЛУ (его входы B и C) число, лежащие по адресу Y+i^j, т.е берётся исключающее ИЛИ от регистров i, j (их ширина скорее всего будет 5 бит - этого хватит для моих задач, хотя это легко поменять). Это довольно экзотическая адресация, но для работы с кватернионами она очень хороша, почему бы не отдать под неё один из 255 адресов :)
Число "защёлкивается" на входе АЛУ, но больше пока ничего не происходит.

FMPM [X+i++] - мы заносим на второй вход АЛУ (вход C) число, лежащие по адресу X+i, и запускаем умножение с накоплением (Fused Multiply) с использованием флага PM (Plus-Minus), который "жестко" привязан к регистрам i,j и регистру Inv (Inverse). Это позволяет "автоматом" выбрать правильный знак каждого множителя - когда мы умножаем два кватерниона, нам нужны знаки:
+ - - -
+ + + -
+ - + +
+ + - +

Номер строки определяется регистром j, номер столбца - регистром i. Если нам нужно умножить кватернион на сопряжённый, то не нужно ему специально менять знаки, достаточно поставить Inv=1, и тогда мы воспользуемся транспонированной таблицей знаков (i с j поменяются местами).

То есть, у нас несколько адресов для регистра C - так называемых "подадресов" - они позволяют выбрать режим работы АЛУ.

JiNZ loop - если i не равно нулю, мы "прыгаем" на метку loop. Здесь мы обращаемся к модулю PC, который также имеет набор адресов, которые все в итоге заносят новое значение в регистр PC (program counter), но могут делать это при выполнении определённых условий. Чтобы это заработало, модуль PC должен иметь дополнительные соединения с модулем Mem (получать флаги, что i нулевой, j нулевой) и с модулем ALU (флаги отрицательного значения и переполнения), но по счастью они не сильно усложнят нам процессор. loop должен превратиться нашим "ассемблером" в непосредственное значение, которое модуль PC скорее всего будет трактовать как относительный адрес, -64 .. +63 - должно хватить на первых порах. Для "длинных прыжков" мы на самом деле можем модернизировать модуль Imm, чтобы он не просто "насквозь" перегонял 7 бит шины адреса на шину данных, но и мог хранить сколько-то самых "ходовых" констант. Можно будет даже автоматизировать этот процесс.

Где-то в глубине модуля Mem мы ещё поставим конфигурационный регистр, который заставит i, j инкрементироваться не просто так, а "по модулю", в нашем случае - по модулю 4. Поэтому, произведя все 4 умножения, приходящиеся на одну компоненту, мы выходим из внутреннего цикла и двигаемся дальше.

[SP+j++] Acc - мы заносим результат вычислений в стек. Сразу по адресу Z мы боимся, потому что он может совпадать с адресом одного из операндов, и тогда мы его "запорем".

JjNZ QuatMultiply - прыжок в самое начало процедуры, если j не равно нулю.

[Z+j] [SP+j++] - а тут мы уже переносим ответ из стека на окончательный адрес.

JjNZ output - этой строкой мы организуем цикл на 4 итерации для предыдущей строки.

И наконец,
JMP [--SP] - этой строке можно было бы дать мнемоническое имя ret: сначала мы вычитаем единичку из указателя стека, извлекаем из него адрес возврата и прыгаем именно на него.

В процедуре поворота вектора с помощью кватерниона мы наблюдаем, как вызываются функции.

Изначально, по адресу X лежит исходный вектор (как кватернион с произвольной скалярной/действительной частью), по адресу Y - кватернион, адрес Z - куда надо запихать преобразованный вектор. Z может совпадать с X.

Inv 1 - заносим единичку в регистр Inv (Inversion), чтобы выполнить правую часть выражения

в смысле, чтобы кватернион был сопряжённым.

[SP++] PC - заносим в стек адрес текущей инструкции + 2 (именно такое значение нам должен выдавать PC), т.е адрес возврата.

JMP QuatMultiply - переход на процедуру умножения кватернионов. Эти две строки вместе и образуют вызов. Возможно, мы могли дать им мнемоническое имя CALL QuatMultiply, хотя это не вполне в духе ассемблера, мы эдак забудем, как оно там работает внутри.

Inv 0 - для следующей операции нам сопряжённый кватернион не нужен.

X Y - в адресный регистр X заносим значение Y, т.е наш кватернион (он теперь является левым операндом)
Y Z - в адресный регистр Y заносим значение Z, т.е промежуточное выражение уже лежит по финальному адресу (после первого вызова QuatMultiply), его-то мы и обновим.

Теперь мы могли бы "честно" вызвать QuatMultiply ещё раз, но вместо этого делаем обычный прыжок:
JMP QuatMultiply - теперь процедура QuatMultiply вернётся сразу же туда, откуда была вызвана RotateVecByQuat, сэкономив нам две строки кода, одну позицию в стеке и немножко времени. В общем, старый добрый Tail Call.

Сейчас пока что я предполагаю, что при переходе конвейер будет опустошаться, т.е сразу же после того, как мы положили в PC новое значение, мы начинаем работать с нового места. Можно этого и не делать - эти программы удлинятся на 1-2 команды, мы чуть перекомпонуем цикл, чтобы сразу за командой прыжка сделать ещё что-нибудь полезное (прыжок происходит не сразу, процессор "по инерции" успевает выполнить ещё несколько команд). Скорее всего, особенной разницы не будет.

Видимо, в скором времени попробую написать на этом ассемблере остальные математические процедуры, которые мне нужны: сортировка точек "по часовой стрелке", умножение вектора на матрицу, обращение симметричной матрицы 6х6 "на месте" через LDL-разложение, а ещё разложение матрицы 2х2 общего вида на поворот, масштаб и "ракурс" и нахождение кватерниона крена из матрицы поворота 2х2. Тогда станет понятнее, сколько нам нужно регистров, какие ещё нужны варианты адресации (что-нибудь типа [X + i + j*8] скорее всего), и всё в этом духе. И тогда уже напишу транслятор, эмулятор, и только под конец - реализую на ПЛИС. Глядишь, к концу лета всё получится...
Tags: ПЛИС, кватернионы-это просто (том 1), работа, странные девайсы
Subscribe

  • Лестница для самых жадных

    В эти выходные побывал на даче, после 3-недельной "самоизоляции". Забавно, как будто зима началась! Особенно грязные галоши остались на улице, в…

  • Возвращаемся к макету

    Очень давно макетом видеоизмерителя параметров сближения не занимался: сначала "громко думал" по поводу измерения его положения на аппарате, а потом…

  • Минутка живописи

    В процессе разгребания содержимого квартиры (после нескольких ремонтов) дошёл, наконец, и до картин. В кои-то веки их повесил. Куда их вешать -…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 11 comments

  • Лестница для самых жадных

    В эти выходные побывал на даче, после 3-недельной "самоизоляции". Забавно, как будто зима началась! Особенно грязные галоши остались на улице, в…

  • Возвращаемся к макету

    Очень давно макетом видеоизмерителя параметров сближения не занимался: сначала "громко думал" по поводу измерения его положения на аппарате, а потом…

  • Минутка живописи

    В процессе разгребания содержимого квартиры (после нескольких ремонтов) дошёл, наконец, и до картин. В кои-то веки их повесил. Куда их вешать -…