nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Дорабатываем транслятор QuatCore

Транслятору ассемблера QuatCore пора немножко "поумнеть" - научиться распознавать, когда возникает RAW (Read-After-Write) HAZARD, а также конфликт с одновременным обращением к памяти и на запись, и на чтение.

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


Вижу два варианта действий.

Первый: составить исчерпывающий список, какая команда с какой "не дружит". Наверное, в рантайме именно такой список будет очень эффективен: ведь достаточно булева массива на 65536 записей, то есть в нём приведена вообще любая 16-битная команда QuatCore, составленная из двух "половинок", Dest и Src. И значение для каждой команды: разрешена ли она.

Но "ручками" вписать такой список - это умом поехать можно. Поэтому надо всё-таки заставить компьютер построить такой список самостоятельно.

Полагаю, что надо ввести куда более короткий список "ресурсов", к которым нельзя обращаться одновременно из Src и Dest. Самые основные ресурсы - это регистры Acc,C,X,Y,Z,SP,i,j,k,Inv,PC. Другой важный ресурс - адресная шина памяти.

И тогда для каждой команды нужно ввести перечень ресурсов, которые ей нужны. Скажем, [X+2j+k] занимает регистры X,j,k и адресную шину. Команда j занимает регистр j (ОЧЕНЬ ВНЕЗАПНО), поэтому рядышком они не уживутся.

Выглядит вполне красиво, но тут же возникают исключения из правила. Так, наш замечательный интерлок в АЛУ заставляет вычеркнуть из списка большое сочетаний команд с АЛУ, но не все. Он срабатывает, когда в DestAddr исполняется длительная команда, то есть все команды, за исключением NOP, C и ZAcc. Так что, если у нас при выполнении бок о бок окажутся команды:
ZAcc   Acc

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

Все команды прыжка в конфликтах также не участвуют, так как попросту уничтожают своего "соседа", и конфликтовать становится не с кем. Безусловный прыжок вообще не даёт выполниться команде по SrcAddr. Условный прыжок, если условие не выполнено - позволяет, но тогда он сам совершенно безобиден - даже если это iLOOP/jLOOP/kLOOP, когда из цикла мы вышли, индексный регистр мы не меняем, он остаётся нулевым.

Да и команды вызова процедуры тоже не конфликтуют: если команда в DestAddr и может изменить PC, то это прыжок, а он сделает вызов процедуры недействительным (т.к прыжок относится к текущей команде, а вызов процедуры - к СЛЕДУЮЩЕЙ, поэтому сначала прыгать надо)

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

Злой он потому, что требует достаточно суровых мер и при "аппаратном" исправлении, и ещё более суровых - при "программном". При аппаратной реализации нужен как минимум компаратор двух эффективных адресов. Просто сравнить коды команд нельзя - ведь одна команда может быть [X+i], а другая [Y+k], но указывать они будут на одну и ту же область памяти! Затем красивее всего поставить ышшо один мультиплексор, который скоммутирует вход на выход, сделает ещё один "байпас" (говоря по-русски, шунтирование :) HAZARDы они такие).

А если мы не хотим ставить аппаратную "блокировку"/"шунт", а хотим, чтобы транслятор это дело отсеял, ему пришлось бы очень основательно поумнеть - научиться находить кое-какие инварианты в коде. Где-то он должен обнаружить, что процесс вообще "поставлен на рельсы" - какими бы ни были данные, а количество выполнений каждого цикла и последовательность обращения к памяти известна заранее. Где-то - сообразить, к примеру, что X и Y отличаются более чем на 32, а значит, каким бы ни был i или k, пересечения произойти не может. И как водится, это всегда будут эвристики, и надо лишь надеяться, что моя программа достаточно детерминирована, чтобы они все сработали. А в общем случае задача NP-полная, как водится.

А в нынешнем виде работа для транслятора на удивление халявная. Ему вообще не нужно задумываться о том, в какой последовательности будет выполняться программа "в реальности", как вот здесь вызывается функция, а она затем, возможно, вызывает эту функцию, здесь функция возвращает управление, а здесь мы выпендрились и применили tail call, и т.д. Вместо этого, достаточно просто пройти по всему коду от начала до конца и проверить конфликты. Этого достаточно, поскольку при осуществлении прыжков мы, попав на новый адрес, "начинаем с чистого листа" - лежащие в конвейере неверные команды игнорируются, и каких-то новых конфликтов возникнуть не может. Единственное, мы при таком подходе можем начать ругаться на такие области кода, куда управление вообще не приходит. Ну так не должно их таких быть :) Так что не страшно, если выругаемся. А бояться того, что конец одной процедуры и начало другой процедуры "законфликтуют", хотя так перескочить невозможно - не надо. Кончается процедура командой JMP [--SP], а JMP ни с кем не конфликтует, как мы знаем.

Не выловит ли транслятор "несуществующие" конфликты при вызове процедуры, которых на самом деле нет?
Пусть у нас будет такой код:
[SP++]  CALL0
JMP     [--SP]


кривой код, его наверняка можно было бы заменить на такой:

JMP     func

(тот самый tail call), но можно и другой придумать:

[SP++]  CALL0
Acc     [X+i]


Да, если транслятор этому специально не научить, он увидит здесь конфликт:
....   CALL0
[SP++] [X+i]
Acc    ...

Два обращения к "уникальному" ресурсу - адресной шине памяти. Поэтому да, нужно как-то заставить транслятор здесь сделать "разрыв", иначе будет у нас толпа ложных срабатываний.


Похоже, задача ясна - осталось реализовать.
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 

  • 4 comments