nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Жуткая адресация QuatCore

У меня продолжаются "душевные терзания". Остался один модуль, QuatCoreMem, в котором содержится 4 регистра для работы с памятью: X, Y, Z, SP. Их ширина совпадает с шириной шины адреса ОЗУ, пока что вообще 8 бит, если совсем прижмёт - станет 9 бит.

По изначальной идее, каждый из них играл совершенно определённую роль: каждый раз, когда мы производим операцию над двумя объектами, будь то умножение кватернионов, поворот вектора с помощью кватерниона, умножение матриц и пр. - X должен указывать на первый (левый) операнд, Y - на второй (правый), а Z - на результат. SP - это Stack Pointer, как полагается, отвечает за стек.

И чтобы программа имела компактные размеры и не тратила больше половины времени на "перекладывание из порожнего в пустое" (cat /dev/zero > /dev/null), мне хотелось ввести все необходимые режимы адресации, чтобы адрес каждого операнда и результата вычислялся прямо "на ходу" как раз в модуле Mem.

Пока писал программу - ни в чём себе не отказывал - нужно обратиться как-то хитро - добавлял соответсвующий адрес - "потом реализую". Вот пришла пора реализовывать, я выписал все варианты - и схватился за голову. Их вроде бы не так много - 21 адрес для SRC и 20 адресов для DEST, при том, что и на то, и на другое доступно 64 адреса. Но сколько-нибудь логичная система тут отсутствует напрочь!!!


Вот какие получились адреса SRC:

X (взять значение из регистра X),
Y,
Z,
(SP внезапно не нужен - мы как один раз стек инициализировали, так только взад-вперёд его и гоняем через [--SP] / [SP++])

[X+8k+i],
[X+4j+k],
[X+2i+k],
[X+2j+k],
[X+2i+1],
[X+i],
[X+i^k],
[X+8i+k],

[Y+2k+i],
[Y+2k+j],
[Y+k],

[Z+2j+k],
[Z+2j+1],

[SP],
[SP+1],
[SP+2],
[--SP],
[SP+i]


Тут мы видим, что Z появляется очень редко, поскольку почти всегда является "получателем", а не источником данных. Чаще всего используется X, значительно реже Y.

С Dest ситуация чуть другая:

X,
Y,
Z,
SP (задействуется ровно ОДИН РАЗ при старте программы),
[X],
[X+2i+k],

[Y+k],
[Y+S],
[Y+~S],
[Y+i],

[Z+i],
[Z+2j+k],
[Z+2j+i],
[Z+8i+k],

[SP],
[SP+1],
[SP+2],
[SP+i],
[SP++],
[SP+2i+j].

В "периодическую таблицу" оно лезть категорически не хочет, разве что в очень большую!

С точки зрения реализации, нам нужно как минимум 3 мультиплексора и 2 сумматора, чтобы выбрать 3 слагаемых и сложить их между собой, получив "эффективный адрес". Затем подать его на ОЗУ и получить необходимые данные.

Одно слагаемое вроде бы логично - выбираем 1 из 4 "базовых регистра", X, Y, Z, SP. И в общем-то даже у нас хватает адресов, чтобы, к примеру, два младших бита "зарезервировать" ровно под выбор базового регистра.

Два других выбираются из очень широкого списка... Как минимум, это i, 2i, 8i, j, 2j, 4j, k, 2k, 8,k, а ещё великое и ужасное i^k (искл. ИЛИ, оказывается просто необходимым для умножения комплексных чисел, дуальных чисел, кватернионов и векторного умножения), укуренное S и ~S (флаг знака или его инверсия). Чтобы просто выбрать одно слагаемое из этого списка, нам нужно 4 бита! А это всё, что у нас есть - 2 бита адреса уходит на выбор модуля QuatCoreMEM, ещё 2 - на выбор базового регистра, и 4 остаётся.

Видимо, нужен более научный подход. Я вижу свою ошибку в том, что решил обязательно использовать индексные регистры так, как это записывается в математике чаще всего: i,j означают строку и столбец элемента матрицы, а k является "немым индексом", по которому делается суммирование. Желание придерживаться этой системы привело, вероятно, к появлению кучи избыточных вариантов адресации, которых можно было избежать, если в нужных местах менять эти регистры местами, благо они пока что все одинаковые.

Попробуем разобраться, сколько РАЗЛИЧНЫХ комбинаций индексов нам в действительности нужно, для чего снова пробежимся по всем этапам алгоритмов захвата и сопровождения.

Поиск наиболее отдалённой точки

Здесь у нас 3 вложенных цикла. Исходные данные - набор из 4 точек, их координаты идут в памяти так:
 X0 Y0 X1 Y1 X2 Y2 X3 Y3


Внутренний цикл - от 0 до 1, выбирает либо координату X, либо координату Y.
Следующие 2 цикла - от 0 до 3, выбирают одну из 4 точек.
Как результат, имеем адресацию
2i+k
и
2j+k.
Лишь одной из них обойтись нельзя, если только непрерывно внутри циклов их местами не переставлять. Пусть будут обе.

Запомним это.

Для стека очень удобно иметь несколько вариантов непосредственной адресации, [SP], [SP+1], [SP+2], [SP+3] - пусть будет.

Далее, при перестановке двух точек местами, та же самая адресация
2i+k
и
2j+k
очень удобна.

Далее начинается сортировка точек против часовой стрелки.

И начинается она с задачи сдвинуть все точки на одно и то же смещение. Концептуально задача ничем не отличается от перестановки двух точек местами, так что те же самые смещения,
2i+k
и
2j+k
подойдут. Мы тогда по неопытности применили просто +k, но там всего лишь одинарный цикл, поэтому один индекс пустует и как правило "автоматом" оказывается нулевым.

Далее, идёт сама сортировка методом "простого выбора", причём, чтобы жизнь мёдом не казалась, "оператором упорядочения" служит результат векторного умножения.

И опять я применил целую толпу разных индексов:
C   [Z+2j+k]
MUL [X+2i+1]
C   [Z+2j+1]
FMS [X+2i+k]


ну точнее, два новых, с единичкой вместо k. Наш "коронный номер" с искл. ИЛИ здесь, увы, плохо вписывается: назови мы это комплексными числами (и вычислением действительной части произведения первого числа на сопряжённое второе) или векторами (и вычислением век. произведения), но каждый раз нам как бы нужен ещё один цикл, который вырождается до 1 итерации. Так что ладно, пущай будет.

Т.е, первое слагаемое: это всегда базовый регистр.
Второе слагаемое пока что: либо 2i, либо 2j.
Третье слагаемое: либо k, либо 1.

Пока всё хорошо :)

Нахождение матрицы преобразования

Тут мы имеем матрицу 3х4, которая умножается на матрицу 4х2 (наши 4 точки по сути), и получается матрица 3х2, выражающая аффинное преобразование.

Мы взяли индексы
4j+k,
2k+i и
2j+i.

Попробуем поменять k и i местами. Выйдет:
4j + i,
2i + k,
2j + k.
Ага, так немного лучше, но разумеется, новые слагаемые обязаны были появиться. Сейчас выходит примерно так:

Второе слагаемое: либо 4j, либо 2i, либо 2j,
третье слагаемое: либо k, либо 1, либо i.

Пока устраивает, выбор каждого из них умещается в 2 бита :)

Нахождение крена

Тут мы встретили индексы
i,
i^k,
причём j=0, поэтому мы вполне могли бы поставить
2j+i,
2j+i^k,
и получить то же самое.
Третье слагаемое теперь: либо k, либо 1, либо i, либо i^k.
Пока держимся...

Затем начинается процедура нормировки, там мы уже начали брать себя в руки, с индексами
2j+k
то, что доктор прописал.

А затем началась жесть в лице индексов S (бит знака) и ~S (его инверсия). Уже не влезает, если только мы хотим сохранить какую-никакую "ортогональность".
Причём в этом месте у нас уже j=i=k=0. Так что предлагается заменить эти индексы на
2j+i и
2j+i^k,
затем присвоить k=1, и через JL или JGE перепрыгнуть через строку
i 1
(присвоение i=1)

тогда в одном случае получим индексы 0, 1, а во втором - 1, 0.
Такое решение удлиняет код на 3 слова (6 байт), но похоже, это нас устроит, через 256 уже проскочили, а до 512 пока далеко :)

Так что пока мы много не потеряли, и новых вариантов индексации не появилось.

Затем идёт умножение матрицы 2х2 на "матрицу 2х2", которая на самом деле генерируется на лету из синуса и косинуса. Применяются индексы
i^k,
2k+j и
2i+j.

И мы крепко влипли - на первом выражении j не обязан равняться нулю, поэтому теперь в первый индекс мы обязаны добавить вариант с нулём и с 2k, а во второе - j.

Итого, имеем:
первый индекс - 4i, либо 2i, либо 2j, либо 2k, либо 0,
второй индекс - k, либо 1, либо i, либо i^k, либо j.

Т.е одним махом добавилось ещё 3 варианта. От нуля мы никуда не денемся, и это вообще правильно, вещь полезная. От замены i на k в выражении выше ничего не меняется. От замены k на j мы получаем:
i^j,
2j+k,
2i+k.
Т.е всего одно новое выражение, i^j. Пущай будет:

первый индекс - 4i, либо 2i, либо 2j, либо 0,
второй индекс - k, либо i, либо 1, либо i^k, либо i^j.

Это уже плохо - на совсем ортогональную систему места не хватает. Но по-прежнему есть выход: до сих пор на самом деле регистры X,Y,Z были равноправными. Совсем специализировать их я не хочу, но можно сделать, что в зависимости от базового регистра, второй индекс тоже будет выбираться чуть по-разному. Как-то так для начала:

первый индекс - 4i, либо 2i, либо 2j, либо 0,
второй индекс - k, либо i, либо 1, либо i^k (рег. X, Z), либо i^j (рег. Y).

По логике нашей работы, оператор XOR всегда нужен только в ОДНОМ операнде из трёх, в противном случае мы просто неверно определили переменные, по которым суммируем. Поэтому задачу всегда получится выполнить.

Затем нужно результирующую матрицу скопировать со стека - это халява, к этому моменту все 3 индекса нулевые, а цикл одинарный - уж как-нибудь справимся :)

Нахождение масштаба
здесь мы применяем индексы
i и
i^k.
Теперь, добавив нолик в первый индекс, мы можем так их и оставить, всё отлично.

Финал аффинного алгоритма (нахождение вектора)
В начале вообще циклов с индексами нет, идёт цикл до переполнения - халява сэр!

Затем - одиночный цикл по i - это хорошо.

Перемножение кватернионов
Эта штука определённо пригодится в алгоритме сопровождения. Там мы применяем индексы
i^k (для базового регистра X)
i,
k
отлично - это всё у нас есть.

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

Работа с симм. матрицей 6х6
Увы, все эти алгоритмы я ещё не переписал в QuatCore ассемблер. Очевидно, что нам понадобится либо индекс наподобие 8i, либо функция TreugNum(i) =i*(i+1)/2, определённая для i от 0 до 5. Это требует всего 4 ЛЭ, уж как-нибудь вместим, зато можно забыть о впихивании других полезных данных в верхнем треугольнике. Да, это забавно, но, скажем, чистить матрицу придётся очень аккуратно - одним-единственнымм циклом этого не сделаешь, т.к можно стереть кучу всего интересного.

Весь вопрос - сколько разных индексов мы можем захотеть в качестве аргумента TreugNum?

В процедуре UUT-разложения хватит одного аргумента, j, хотя красивее было бы также задействовать ещё один (экономится целое 1 слово, 2 байта). Пока остановимся на одном.
К нему должен прибавляться иногда i, иногда k, так что заносим данный варант в 1-й индекс. Теперь и там становится тесно, придётся также вводить условие на применённый регистр. Для единообразия, это снова будет Y, как явствует из старого списка инструкций, 4j использовалось только для рег. X.

Пусть будет как-то так:
первый индекс - 4i (рег. X, Z), либо Treug(j) (рег. Y), либо 2i, либо 2j, либо 0,
второй индекс - k, либо i, либо 1, либо i^k (рег. X, Z), либо i^j (рег. Y).

Пока справляемся...

При нахождении решения системы линейных уравнений с помощью прямой и обратной подстановки такого набора индексов также должно хватить, хоть и немного "со скрипом". Там нам понадобятся:
Treug(j)+k, (внут. цикл по j, внеш. цикл по k)
j,
Treug(j)+j (когда вышли из внут. цикла)

Это всё осуществимо с помощью варианта i^j при i=0. Нормально.

Составление матрицы 6x6
ну и ещё один кусочек алгоритма, который пока хуже всего проработан. Мы сначала получаем матрицу M (2х6) и вектор H (2х1). При этом у нас есть текущее значение матрицы J (6х6) и вектора K (6x1). Мы должны посчитать выражения

J += MT * M,
K += MT * H

причём J имеет "треугольную" адресацию, и строить произведение матрицы 2х6 на транспонированную нам хочется "на лету", как и произведение матрицы на вектор.

Похоже, и здесь нам улыбается удача. Достаточно индексов:
Treug[j]+i,
2j+k,
2i+k,
j (но в этом месте i=0, так что можно поставить i^j),
k.

Просто отлично.


Фух, по-моему решение найдено...
64 адреса делится почти "ортогонально", 3 раза на 4 части:

старшие 2 бита указывают "базовый регистр": X, Y, Z, SP,
средние 2 бита указывают первый индексный регистр:
4i (рег. X, Z), либо Treug(j) (рег. Y), либо 2i, либо 2j, либо 0,
младшие 2 бита указывают второй индексный регистр:
k, либо i, либо 1, либо i^k (рег. X, Z), либо i^j (рег. Y).

И если ещё бросить так понравившийся нам вариант непосредственной передачи из памяти в память, попросив всегда использовать промежуточный регистр, то мы сможем обойтись всего одним узлом формирования эффективного адреса, должно получиться весьма и весьма компактно. Скоро узнаем...

UPD. Ах да, ещё забыл команды для инициализации этих регистров и PUSH/POP для стека. Вот думаю, может сами регистры тоже перетащить в QuatCorePC, там вроде были ещё свободные места...
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