nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Транслятор QuatCore: более "умное" составление таблицы вызова процедур

А давайте сделаю, давно руки чешутся. До этого меня останавливало, что на этом можно выиграть считаные ЛЭ, что на фоне даже 500 не так уж серьёзно. Но теперь вижу: может они и считаные, и на 4 МГц они погоды не делали. А уже на 25 МГц добавление лишнего комбинаторного слоя заставляет fitter напрячься, поставить эти модули "поближе", а другие тогда получаются подальше - и уже начинаем не укладываться в тайминги.

Так что определённый смысл всё равно есть.


Когда транслятор получает очередную строку ассемблерного кода, и находит выражение вида
CALL foo

он сразу заменяет такую строку на
[SP++] CALL0


(но уже в машинных кодах, т.е F3B0)
а метку foo заносит в список CallTableNames. Там просто лежат имена процедур, отсортированные в алфавитном порядке. Если количество записей превысит 16, транслятор грязно ругается - таким манером можно вызвать лишь 16 процедур. Должно хватить для наших задач...

Кроме того, каждая такая строка заносится в список FixUps, где указывается метка и номер строки.

Когда весь код был прочитан, и составлена огромный список меток Labels[], мы проверяем каждую метку из CallTableNames. Она должна найтись в Labels[], причём являться меткой КОДА, а не меткой данных или литералом (всякие EQU). Если так, всё хорошо, мы заполняем CallTable[] реальными адресами.

И затем проходимся по всем FixUps, и заменяем CALL0 уже на правильную команду, от CALL0 до CALLF. Раньше у меня вообще оставалась "прореха" в команде, скорее всего нолик, но тогда не срабатывал обнаружитель Hazard'ов, ведь ему нужно НА ЛЕТУ понять, вставлять ли NOP. Так он уже знает, что "здесь у нас вызов процедуры", а какая именно процедура вызывается - не так уж важно.

Нам нужен дополнительный этап, преобразующий CallTable. Сейчас мы заполняем её тупо в алфавитном порядке имён процедур, и затем индекс этой таблицы превращается в команду, CALL0..CALLF, а по её значениям генерируется verilog-файл.

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

0x0D = 0000 1101
0x74 = 0111 0100
0x6C = 0110 1100
0x65 = 0110 0101


Их может быть любое количество от 0 до 16. И разрядность может быть разной. Учитывая, что внутренней памяти в ПЛИС 5576ХС4Т всего 12 килобайт, а адресация у нас по 16-битным словам, и на программный код хочется выделить не более половины этой памяти, вряд ли разрядность превысит 12 бит.

Начинаем от самого старшего разряда. Подсчитываем количество "нулей" и количество "единиц", а также выписываем в виде числа "сверху вниз". Для последнего, 7-го разряда (нумерация с нуля) получается 4 "нуля" и ни одной единицы, и число 00002=0. Если получаются все нули или все единицы - мы делаем соответствующую пометку, и этот разряд из дальнейшего рассмотрения вычёркиваем. По сути, для него уже можно сформировать строку для модуля QuatCoreCallTable.v:

assign addr[7] = 1'b0;


Принимаемся за 6-й разряд, получается 1 ноль и 3 единицы, и число 01112=7. Случай не тривиальный (не все нули и не все единицы) и ровно такой у нас в более старших разрядах не попадался (для этого ищем и там "семёрку", для быстрого сравнения такие числа и вводим). Пока что все адреса у нас сидят в одной "группе", xxxx (т.е пока ни один разряд для номера команды не определён). Пока доступно 8 команд, у которых первый бит - нолик (0xxx) и ещё 8, у которых первый бит - единичка (1xxx). А у нас по 6-му разряду получился один ноль и 3 единицы, и то, и другое меньше 8, что означает: можем сопоставить старший разряд номера команды с 6-м разрядом адреса. Тем самым, мы решили:

Процедура с адресом 0x0D будет вызываться командой с номером 0xxx (старший бит известен, остальные пока нет),
процедуры с адресами 0x74, 0x6C, 0x65 будут вызываться командами с номерами 1xxx.


То есть, поделили все адреса на 2 группы. В первой группе, 0xxx, будет 4 команды вида 00xx и 4 команды вида 01xx. То же самое для второй. И сразу можем записать строчку верилога:

assign addr[6] = SrcAddr[3];


Принимаемся за 5-й разряд, получается 1 ноль и 3 единицы, и число 01112=7. Но мы уже встречали число 7, конкретно в 6-м разряде, поэтому делаем соответсвующую пометку, которая также превратится в строчку на верилоге:

assign addr[5] = addr[6];


(или можно assign addr[5] = SrcAddr[3], как удобнее будет).

Принимаемся за 4-й разряд. Для него составляется число 01002=4, такого ещё не было. Общее число нулей и единиц не так уж важно, тут правильнее посчитать нули и единицы для 1-й группы (0xxx) и для 2-й группы (1xxx). Получаем 1 нуль и ни одной единицы для 1-й группы (из "доступных" 4 и 4) и 2 нуля и 1 единицу для 2-й группы (из "доступных" 4 и 4). Всё влезает, значит, мы можем сопоставить 4-й разряд адреса с 2-м разрядом номера команды:

assign addr[4] = SrcAddr[2];


И теперь адреса распределяются по 4 группам:

Процедура с адресом 0x0D будет вызываться командой с номером 00xx,
Ни одна процедура не вызывается командой с номером 01xx,
Процедуры с адресами 0x6C, 0x65 будут вызываться командами с номерами 10xx,
Процедура с адресом 0x74 будет вызываться командой с номером 11xx.


И теперь в каждой группе доступны по 2 команды с ноликом в 1-м разряде и по 2 команды с единичкой.

Принимаемся за 3-й разряд. Для него составляется число 10102 = 9, такого раньше не было. Считаем количество ноликов и единиц в каждой из 4 групп:

0,1 в 00xx,
0,0 в 01xx,
1,1 в 10xx,
1,0 в 11xx


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

assign addr[3] = SrcAddr[1];


И наши адреса распределяются по 8 группам:

000x: ни одной,
001x: 0x0D,
010x: ни одной,
011x: ни одной,
100x: 0x65,
101x: 0x6C,
110x: 0x74,
111x: ни одной


На удивление удачно!
Далее идёт разряд 2, там все единицы:
assign addr[2] = 1'b1;


И разряд 1, там все нули:
assign addr[1] = 1'b0;


И, наконец, разряд 0. Для него составляется число 10012 = 9, девятки ещё не было. Подсчитываем нолики и единички для 8 групп:

0,0 в 000x,
0,1 в 001x,
0,0 в 010x,
0,0 в 011x,
0,1 в 100x,
1,0 в 101x,
1,0 в 110x,
0,0 в 111x.


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

assign addr[0] = SrcAddr[0];


и групп становится 16, они и являются ответом для транслятора, какие команды использовать для вызова каждой из этой процедур.

Осталось это безобразие запрограммировать...


Продолжение следует...
Tags: ПЛИС, математика, программки, работа, странные девайсы
Subscribe

  • Так ли страшно 0,99969 вместо 1?

    В размышлениях о DMA, о возможных последствиях "смешивания" старых и новых значений при выдаче целевой информации, опять выполз вопрос: насколько…

  • Как продлить агонию велотрансмиссии на 1500+ км

    Последний раз о велосипедных делах отчитывался в середине мая, когда прошёл год "велопробегом по коронавирусу". Уже тогда я "жаловался", что…

  • DMA для QuatCore

    Вот фрагмент схемы нашего "процессорного ядра" QuatCore: Справа сверху "притаилась" оперативная память. На той ПЛИС, что у меня есть сейчас…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments