nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Операции над связанными списками в QuatCore

В "нормальной жизни", добавление нового элемента, удаление элемента и "перецепка" элемента с одного списка на другой кажутся принципиально разными операциями. Мало того, добавление элемента в самое начало списка (в том числе, в пустой список) или куда-то в середину должно, как будто бы, описываться по-разному, если только не призвать тёмные силы языка С, в лице ДВОЙНЫХ УКАЗАТЕЛЕЙ.

А у нас тут всё едино! Ведь добавление нового элемента - это "перецепка" его из списка вакантных элементов, Heap, удаление - возвращение его назад в этот список, так что нам нужна одна-единственная операция: отцепить элемент от первого списка и вставить его во второй.

И неслучайно у меня указатель на следующий элемент стоит В САМОМ НАЧАЛЕ элемента, это позволяет не выделять отдельным случаем работу с началом списка - всё производится единообразно!


Опять возьмём клочок листинга памяти, чтобы понимать, что происходит:
ActivePoints:    10   0x8000
AllPoints:       11   0x8000
Heap:            12   0x0013
Elem0Next:       13   0x0018
Elem0X:          14   ????
Elem0Y:          15   ????
Elem0L:          16   ????
Elem0P:          17   ????
Elem1:           18   0x001D
Elem1[1]:        19   ????
Elem1[2]:        1A   ????
Elem1[3]:        1B   ????
Elem1[4]:        1C   ????
Elem2:           1D   0x0022
Elem2[1]:        1E   ????
Elem2[2]:        1F   ????
Elem2[3]:        20   ????
Elem2[4]:        21   ????


0x8000 - это Null, он же Nil, он же NullPtr, короче, пустой указатель.

Сейчас у нас есть список Heap, содержащий все доступные элементы, и два пустых списка ActivePoints и AllPoints.

Допустим, мы хотим добавить новую точку в список ActivePoints. Список пока что пуст, так что особого выбора, КУДА добавлять, нет. Мы должны передать нашей процедуре значение ActivePoints, например, поместив его в регистр X:

X     ActivePoints


Надо понимать, что теперь X = 0x10, т.е обращения к памяти пока не было, мы просто занесли адрес, по которому хранится указатель на наш список.

Второй аргумент - откуда мы возьмём эту новую точку, это всегда будет Heap. Воспользуемся регистром Y:

Y    Heap


И здесь обращения к памяти не было, просто в регистр Y занесли значение 0x12, где хранится указатель на список "свободных ячеек".

Теперь вызываем нашу процедуру:

CALL ListOp


(как её правильно назвать, не придумал пока)

Как-то так сложилось, что отдельных команд [X], [Y], [Z] в QuatCore нету, обязательно присутствуют какие-то индексные регистры, но это не страшно, быстренько регистр k приравняем к нулю:

k    0

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

Проверим, не сидит ли в [Y] нулевой указатель? Если так, это очень плохо, ведь именно из этого списка мы хотели откусить один элемент, а тут, оказывается, вообще ни одного нет!

               Acc    [Y+k]
               SUB    0
               JL     @@OutOfMemory
               ...
               ...
               ...
               ;конец процедуры
               JMP    [--SP]
@@OutOfMemory: [--SP] Call(OutOfMemory)


Пять строчек, просто насыщенных странностями QuatCore, уж не знаю, баги это или фичи. Просто загрузка значения в аккумулятор не меняет флаг знака, только операции, включающие в себя вычитание: SUB, FMS и пр.

JMP [--SP] - это "штатный" возврат из процедуры, так в нашей Transport Triggered Architecture записывается обычный ret.

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

Хорошо, мы убедились, что указатель ненулевой. Пора заняться делом!

Находим, куда же ведёт этот указатель:
Z   Acc

(до этого мы положили [Y] в Acc, теперь перекладываем ещё и в Z, чтобы не терять такт ещё раз запрашивая из памяти. Если Z нам нужен, можем и его в стек сохранить, об этом потом подумаем)

В нашем сценарии, Z = 0x13, т.е указывает на нулевой элемент Heap:

ActivePoints:    10   0x8000
AllPoints:       11   0x8000
Heap:            12   0x0013
Elem0Next:       13   0x0018
Elem0X:          14   ????
Elem0Y:          15   ????
Elem0L:          16   ????
Elem0P:          17   ????


Именно по этому адресу находится ссылка на следующий элемент, т.е [Z] = 0x18. Здесь может быть и Null/Nil/NullPtr, но нам неважно. Всё что надо - это перекинуть Heap, то бишь, [Y], на этот следующий элемент, тем самым Elem0 окажется вычеркнут из списка свободных элементов:

[Y+k]   [Z+k]

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

ActivePoints:    10   0x8000
AllPoints:       11   0x8000
Heap:            12   0x0018
Elem0Next:       13   0x0018


Да, список Heap мы обновили. Сейчас элемент Elem0 оказался "неприкаянным" - ничто в памяти на него не ссылается, но у нас пока есть регистр Z, который указывает строго на него:
X = 0x10,
Y = 0x12,
Z = 0x13


Теперь переправим связь нулевого элемента - он не должен указывать на "свободные элементы" из списка Heap, а должен встроиться в начало списка ActivePoints. А именно, куда сейчас указывает ActivePoints - туда и должен указывать Elem0. Это также исполняется в одну строку:

[Z+k] [X+k]


И теперь выходит:
ActivePoints:    10   0x8000
AllPoints:       11   0x8000
Heap:            12   0x0018
Elem0Next:       13   0x8000


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

Ну и последняя строка: нужно перенаправить указатель с ActivePoints на новый элемент, адрес которого у нас лежит в регистре Z:

[X+k]  Z


Теперь должно выйти так:
ActivePoints:    10   0x0013
AllPoints:       11   0x8000
Heap:            12   0x0018
Elem0Next:       13   0x8000


Вуаля!

Запишем процедуру целиком:
;взять первый элемент из списка Y и перецепить его в начало списка X
;значения X,Y остаются неизменными,
;k=0, затираем регистр Z, Acc и флаг знака
	ListOp proc
		k	0
		Acc	[Y+k]
		SUB	0
		JL	@@OutOfMemory
		Z	Acc
		[Y+k]	[Z+k]
		[Z+k]	[X+k]
		[X+k]	Z
		JMP	[--SP]
@@OutOfMemory:	[--SP]	Call(OutOfMemory)
	ListOp endp


10 строчек, из них 4 - обработка ошибки (нехватка памяти), ещё одна - возвращение из процедуры. А если условиться, что k=0, и того меньше.

Такая процедура компилируется вполне успешно, но обнаруживается толпа Hazard'ов:

Конфликт (Hazard) между командами k и [Y+k], процедура ListOp, строки:
			k		0
			Acc		[Y+k]
Вставляем NOP

Конфликт (Hazard) между командами Z и [Z+k], процедура ListOp, строки:
			Z		Acc
			[Y+k]		[Z+k]
Вставляем NOP

Конфликт (Hazard) между командами [Y+k] и [X+k], процедура ListOp, строки:
			[Y+k]		[Z+k]
			[Z+k]		[X+k]
Вставляем NOP

Конфликт (Hazard) между командами [X+k] и [--SP], процедура ListOp, строки:
			[X+k]		Z
			JMP		[--SP]
Вставляем NOP


Так что да, пересылки "память-память" у нас разрешены, но когда их слишком много на одном пятачке, они начинают друг другу на пятки наступать, и приходится вставлять "пустые операции" раз за разом. Не знаю, можно ли здесь что-то упростить. По-моему, я делаю присвоения в оптимальном порядке - если попытаться его изменить, то некоторые значения окажутся затёртыми. Ну да ладно, 14 слов результирующего кода - тоже не так уж плохо. 12 слов, если договоримся о k=0 при вызове этой процедуры.

Пара слов, как с помощью этой процедуры реализовать всё остальное.

После того, как список ActivePoints будет содержать один элемент, можно будет вставить второй элемент СЛЕВА от него, для этого надо, как и первый раз, передать
X ActivePoints

Либо можно вставить второй элемент СПРАВА. Скажем, мы шли по этому списку с помощью команды
X [X+k]

и поэтому теперь X = 0x13. Вызови мы процедуру с таким значением X - и она вставит новый элемент СПРАВА. Ей главное, чтобы регистр X содержал указатель, который нужно поменять, чтобы вставить этот элемент. И этот указатель там всегда будет!

Если мы хотим удалить элемент, мы просто меняем местами X и Y, и тогда элемент отцепится от списка ActivePoints и добавится в самое начало списка Heap, что и является удалением. Ну и перецепка - в том же ключе, в кои-то веки вместо Heap мы используем какой-нибудь другой список, и тогда элемент из одного списка будет перенесён в другой.

Понаблюдаем всё это безобразие на симуляции
Вот листинг нашей тестовой программы:
    main proc
00  FD00                      SP      Stack
01  CD01                      X       ActivePoints
02  DD02                      Y       Heap
03  F3B8                      CALL    ListOp
04  8900      OutOfMemory:    NOP     0       
05  B003      @@endless:      JMP     @@endless
    main endp
    ListOp proc
06  A204                  k       0
07  8900      NOP  0 ;AUTOMATICALLY INSERTED BY TRANSLATOR TO PREVENT HAZARD
08  80D8                  Acc     [Y+k]
09  8304                  SUB     0
0A  B805                  JL      @@OutOfMemory
0B  ED80                  Z       Acc
0C  8900      NOP  0 ;AUTOMATICALLY INSERTED BY TRANSLATOR TO PREVENT HAZARD
0D  D8E8                  [Y+k]   [Z+k]
0E  8900      NOP  0 ;AUTOMATICALLY INSERTED BY TRANSLATOR TO PREVENT HAZARD
0F  E8C8                  [Z+k]   [X+k]
10  C8ED                  [X+k]   Z
11  8900      NOP  0 ;AUTOMATICALLY INSERTED BY TRANSLATOR TO PREVENT HAZARD
12  B0FF                  JMP     [--SP]
13  FFB0  @@OutOfMemory:  [--SP]  Call(OutOfMemory)
    ListOp endp


Также компилятор объявляет итоговую ширину различных шин:
- 8 бит адрес RAM, она же ОЗУ, она же сегмент данных,
- 5 бит адрес ROM, она же ПЗУ, она же сегмент кода,
- 4 бита ширина данных для относительного прыжка

И генерится два файла QuatCoreCallTable.v и QuatCoreImmTable.v. Всё это добро копируем в папку с проектом для ПЛИС, запускаем синтез и получаем 503 ЛЭ. Фиттер застрял на 7,5 минут, после чего грязно выругался. 5-битные шины ему страшно не нравятся! Ладно, сделаем и адрес ROM 8 бит, мне не жалко :) Теперь выходит 511 ЛЭ - не такая уж большая разница, видно, что реверсивный счётчик в качестве старших бит PC делает своё дело! Теперь весь синтез за 8,5 минут всё-таки завершился, и Timing Analyzer доволен, макс. частота 26,95 МГц, нормально.

Что же, запускаем симуляцию! В кои-то веки всё выполнение умещается на одном скриншоте:


В шину данных загоняем значение Stack = 0xB3. К следующему такту оно заносится в регистр SP - замечательно.
Затем X = 0x10 (ActivePoints), Y = 0x12 (Heap), и вызываем процедуру ListOp.

Дальше может показаться странным, что мы продолжаем раз за разом тащить на шину данных значение Stack = 0xB3. Такова уж особенность оптимизирующего компилятора - он понял, что команде NOP можно подсунуть вообще что угодно в качестве "аргумента", и он берёт первое попавшееся значение. Подходит - замечательно!

А вот чтобы на шину данных поступил 0, внезапно нужен SrcAddr = 4 :) Это конечно полный беспредел, и в скором времени мы всё-таки поставим эффективный алгоритм формирования таблицы непосредственных значений QuatCoreImmTable... Но по крайней мере, всё работает корректно, хоть и поперёк здравого смысла! А именно, мы занесли нолик в регистр k, хотя я уверен, там и был нолик с самого начала.

Затем следует NOP, чтобы в k успел записаться нолик, прежде чем мы запросим [Y+k]. Всё срабатывает как надо, на шину поступает значение 0x13, т.е нулевой элемент в списке Heap. Заносим его в аккумулятор, вычитаем ноль, чтобы получить флаг знака, и знак явно положительный, поскольку прыжок в @@OutOfMemory не совершается.

То же самое значение из аккумулятора заносится в регистр Z, это 0x13.

Только что дошло: я могу поменять местами строки
JL @@OutOfMemory
Z  Acc

и тогда одним Hazard'ом и одним лишним NOP'ом станет меньше! Интересно, сложно ли будет обучить компилятор reordering'у? Надо бы когда-нибудь, пущай делает за меня грязную работу.


Теперь значение [Z] заносится в [Y]. И значение это 0x18, то есть следующий элемент в списке Heap. Всё верно.

Опять следует NOP, а потом значение [X] заносится в [Z]. И значение это 0x8000, то бишь Null, он же Nil, он же NullPtr, в общем вы поняли.

Теперь значение Z заносится в [X], и это значение 0x13, что в общем-то логично. Радостно, что здесь NOP не вставили, ибо компилятор умный и понимает, что запись ПО АДРЕСУ [Z] НИКОИМ ОБРАЗОМ НЕ ИЗМЕНЯЕТ САМО ЗНАЧЕНИЕ Z, а значит, эти операции друг другу не мешают!

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

Можно ещё напоследок, для очистки совести попросить у Quartus'а содержание оперативной памяти ПОСЛЕ ЗАВЕРШЕНИЯ СИМУЛЯЦИИ:


ШИКАРНО: всё как мы предполагали. По адресу ActivePoints = 0x10 у нас указатель на 0x13, по адресу 0x13 в свою очередь 0x8000, то есть пустой указатель. Это и есть список из одного элемента. Тем временем по адресу Heap = 0x12 у нас указатель на 0x18, где, в свою очередь указатель на 0x1D, а оттуда на 0x22, в общем, это длиннющий список "свободных элементов".


Я вполне доволен: на QuatCore можно компактно реализовать такую структуру данных, хоть и проектировался он конкретно под вектора, матрицы и кватернионы. Ну, может быть не помешал бы флажок, позволяющий сразу распознать нулевой указатель в регистре базового адреса (X/Y/Z), хотя бы даже в одном из них, но и так неплохо вышло.
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

  • А всё-таки есть польза от ковариаций

    Вчера опробовал "сценарий", когда варьируем дальность от 1 метра до 11 метров. Получилось, что грамотное усреднение - это взять с огромными весами…

  • Так есть ли толк в ковариационной матрице?

    Задался этим вопросом применительно к своему прибору чуть более 2 недель назад. Рыл носом землю с попеременным успехом ( раз, два, три, четыре),…

  • Big Data, чтоб их ... (4)

    Наконец-то стряхнул пыль с компьютерной модели сближения, добавил в неё код, чтобы мы могли определить интересующие нас точки, и выписать…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments