Эту фразу из "Макбета" Шекспира автор осмелится перевести как "благодаря зуду на кончиках моих пальцев может появиться что-то очень странное".
Изначально хотелось всего-лишь ознакомиться с Verilog, но, "опасное это дело, выходить за порог: стоит ступить на дорогу и, если дашь волю ногам, неизвестно куда тебя занесет".
Занесло в сторону процессора с собственной архитектурой. Автор давно неровно дышит в сторону стековых процессоров, здесь так же присутствуют раздельные конвейеры для потоков управления/исполнения и расширяемая упаковка кода.
Надеюсь, это окажется кому-то полезным, так же как когда-то автору был полезен игрушечный hoc из книги Кернигана и Пайка "Unix - программное окружение".
Архитектура.
Мотивация почему выбрана именно такая архитектура, описана в предыдущей статье.
Архитектура стековая, безадресная.
Как такового отдельного стека (операндов) не предполагается, это область памяти, на которую указывает пара регистров.
В дальнейшем для работы со стеком операндов планируется небольшой кэш ~ на пару десятков слов.
Стек локальных переменных также расположен в памяти. Имеются ввиду переменные большого размера (массивы), которые нецелесообразно смешивать с операндами (a la amd29k).
Предполагается что оба этих стека расположены в одной области памяти и растут навстречу друг другу, при встрече возникает аппаратная ошибка. Обратный вариант - "спина к спине" тоже возможен. Сейчас непонятно что лучше.
Инструкции упаковываются алгоритмом Vluint7 (описан далее), каждая инструкция представлена опкодом и аргументами. И опкод и аргументы закодированы Vluint7. Это позволит не бояться, что внезапно закончатся опкоды, а также даст возможность плавного перехода с 32-х на 64-х разрядную архитектуру. Опять же, не важно, big это endian или little.
Два младших разряда опкода - число аргументов инструкции, облегчим жизнь декодеру.
Потоки управления и исполнения разделены. Т.е. необходимы два независимых декодера - потока управления и потока исполнения (strands). И два счетчика команд.
Инструкция из потока управления может запустить новый strand, после чего дожидается конца его работы (когда потоку исполнения встретится стоп-инструкция). После возврата, поток управления продолжает работу.
Распаковщик Vluint7
Поток инструкций - это записанные подряд числа, упакованные Vluint7. В этом алгоритме число (не важно, 64-х, 32-х или 16-разрядное) записывается как последовательность байт, в каждом из которых 7 значащих разрядов и один управляющий, по которому можно понять - закончена запись числа или нет. Так, 32-х разрядное значение может потребовать от 1 до 5 байт. Но поскольку идентификаторы инструкций или сдвиги до данных (из которых предположительно состоит код) обычно небольшие числа, такая запись довольно компактна.
Есть два варианта записи - начиная с младших или со старших разрядов. Второй вариант показан на рисунке, но мы будем использовать первый, он представляется чуть более простым в реализации.
Для тестирования модуля распаковки Vluint7 выберем следующие данные:
три числа 0x4b6e, 0x58, 0x1ab1d, в бинарном виде это выглядит так:
Всего получилось уложиться в 7 байтов, они показаны на Фиг.5.2.2
Модуль vluint7 имеет интерфейс:
Здесь:
clk: синхроимпульс
reset: сброс состояния
beg: сигнал к распаковке
addr: адрес начала распаковки
addr_out: адрес на котором закончилась распаковка
rd: сигнал об окончании распаковки
data: распакованные данные
Распаковка начинается с приходом сигнала beg
Всё довольно просто, по окончании чтения памяти, сохраняем текущие 7 разрядов в их позицию, наращиваем адрес чтения, отдаём команду на чтение и наращиваем позицию сдвига данных.
Эмулятор (тут без него не обойтись, в данном случае ModelSim от Altera) демонстрирует нам что распакованы три числа, прочитано 7 байтов памяти.
Синхронное FIFO
Прежде чем приступить к декодеру команд, нам потребуется буфер, куда декодер сможет записывать инструкции и из которого их можно будет вычитывать для исполнения. Дисциплина записи/чтения - очередь. Писатель и читатель работают на одной частоте, поэтому очередь синхронная.
Синхронная очередь - довольно простое устройство - это кольцевой буфер с указателями чтения / записи.
Автор, не мудрствуя лукаво, взял готовый verilog модуль (sync_fifo) и использовал его с минимальными доработками. В силу особенностей реализации он способен работать только с буфером размером в степень двойки, но нас это вполне устроит.
На показана эмуляция работы, чтение идёт со случайными задержками (/tb/rd_en), поэтому буфер время от времени переполняется (/tb/full), при этом приостанавливается запись (/tb/din, /tb/wr_en).
Декодер инструкций.
Для начала следует определиться с инструкциями, их опкодами и аргументами.
Попробуем вычислить выражение (a + 3) * b - c. Для этого требуются следующее:
stop - конец работы, opcode = 0, аргументов нет
varpush - кладём на вершину стека адрес переменной, opcode = 1, один аргумент (адрес)
eval - вычисляем значение переменной, берём адрес с вершины стека и вместо него помещаем значение по адресу, opcode=2, аргументов нет
imdpush - помещаем на вершину стека аргумент - число,
opcode=3, аргумент один (число)pop - удаляем элемент с вершины стека, opcode=4, аргументов нет
i_add - удаляем из стека два элемента, складываем и сумму кладём в стек,
opcode=5, аргументов нетsub - удаляем из стека два элемента, вычитаем и разность кладём в стек,
opcode=6, аргументов нетmul - удаляем из стека два элемента, перемножаем и произведение кладём в стек, opcode=7, аргументов нет
Пусть адрес a=0, b=4, с=8.
Вышеприведённый пример порождает следующий набор инструкций:
Не забываем, что в младшие два разряда opcode помещается число аргументов.
Поскольку все значения адресов и опкодов умещаются в 7 разрядов, упаковка в Vluint7 оказывается тривиальной, содержимое буфера памяти с кодом показано на рисунке.
В сущности, уже всё есть для создания декодера инструкций: мы умеем буферизировать поток опкодов и операндов с помощью очереди, инициализировать и читать (синхронную) память, осталась малость - научиться вычитывать из очереди не просто значения, а именно инструкции - опкод и нужное число аргументов в одной транзакции. Впрочем, это не сложно.
В цикле:
читаем элемент из очереди
ожидание и чтение из очереди делаем несколько итераций - по числу аргументов, которое хранится в двух младших разрядах инструкции
распаковка завершена
отладочная печать распакованных инструкций Запускаем пример в отладчике и получаем заветные слова в консоли отладчика
отладочная печать вышеописанного примера
На сладкое - диаграмма состояния
Что же, пора приступить к созданию калькулятора (вычислителя выражений).
Калькулятор.
После предыдущих экспериментов есть почти всё, что нужно для создания калькулятора. Потребуется лишь стек и стековые инструкции, которые будут с ним работать.
Стек
Стек - это область памяти с дисциплиной записи/чтения LIFO. Мы уже использовали одну область памяти для хранения исполняемого кода (модуль vluint7), теперь модуль памяти придётся параметризовать т.к. изменится размер элемента памяти и размер области а также загрузка данных (для отладки) из разных файлов. Фактически, это означает, что процессор имеет гарвардскую архитектуру, впрочем, на данном этапе это совершенно неважно.
Размер слова в стеке выберем в 32 разряда,
стек будет размером в 256 слов (1К), т.е. ширина адреса - 8 разрядов
начинаться стек будет не с начала области памяти, а с отступа в 16 байт, которые будут использованы под локальные переменные.
область, занятая переменными в формате понимаемом ModelSim всего 4 слова (инициализационный файл), остальное не определено
вершина стека определяется значением регистра executer.stack_top с адресацией в байтах, регистр смотрит на на слово, следующее за последним заполненным (словом)
Инструкции.
Минимальный набор инструкций описан в разделе “декодер инструкций”, разберем реализацию какой-нибудь одной, пусть eval, в ней есть и чтение стека и запись в него.
6'b000010 - это 2, опкод инструкции eval
stack_top - stack_step вычисляем адрес вершины стека и начинаем чтение по этому адресу. Должны вычитать адрес переменной в tmp_data_reg_in
устанавливаем адрес загрузки в tmp_addr и дожидаемся окончания чтения
записываем прочитанное значение переменной и записываем его в вершину стека через регистр tmp_data_reg_out
loc_we (write enabled)- в случае нулевого значения читаем данные иначе пишем
Разберём эту диаграмму
изначально инициализированы первые 4 слова, это переменные a=1 (адрес 0),
b=2 (... 4), c=3 (... 8), d=4 (... 12)инструкция varpush a помещает адрес a (т.е. 0) на вершину стека (адрес 16)
инструкция eval замещает на вершине стека адрес переменной значением (т.е. 1)
imdpush 3 дописывает в стек значение 3
инструкция i_add складывает последние два значения на вершине стека, удаляет их из стека и записывает в стек сумму 3 + 1 => 4
varpush b записывает в стек адрес b т.е. 4
eval замещает на вершине стека адрес переменной значением (т.е. 2)
инструкция mul перемножает два аргумента, удаляет их и записывает произведение 2 * 4 => 8
varpush c записывает в стек адрес с т.е. 8
eval превращает его в 3
инструкция sub вычитает аргументы, удаляет их из стека и записывает разность 8 - 3 => 5
на этот раз переменная d не пригодилась
Результат на вершине стека, (a + 3) * b - c = 5
Итого, имеем работающий вычислитель выражений с двух-стадийным конвейером и базовой арифметикой. Наш следующий шаг - инструкции потока управления и их собственный конвейер.
Поток управления.
До сих пор мы экспериментировали с линейными участками кода, иногда их называют стрендами (strands). Калькулятор из предыдущего раздела (поток исполнения) выполняет такой стренд и останавливается. С точки зрения теории вычислимости, этого достаточно для вычисления примитивно-рекурсивных функций, но универсальные задачи решать не получится.
Согласно теореме Бёма-Якопини, для реализации любого алгоритма нужны три вещи:
выполнение линейных участков кода
ветвления - исполнение одной из двух веток кода в зависимости от значения логического выражения
циклы - выполнение участка кода до тех пор, пока истинно логическое выражение
Теперь займёмся потоком управления. Концепция такова, что инструкции потока управления отделены от инструкций исполнения, декодируются и исполняются самостоятельно.
Исполнение участков линейного кода
Для этого потребуются две инструкции
stop - конец работы, opcode = 0, аргументов нет
exec - opcode = 1, один аргумент - адрес исполняемого линейного участка кода
Пример тот же самый - вычисление (a + 3) * b - c, но теперь исполняемый код предварён двумя инструкциями потока управления - exec [branch]; stop; .
Ветка вычисления выражения расположена начиная с адреса 8, поэтому аргумент команды exec равен 8. В сущности, 8 выбрано для удобства, начать код потока исполнения можно было с любого адреса, начиная с 3.
Реализация потоков управления и исполнения очень похожа, стоит обратить внимание на следующее:
Исполняемый код обоих потоков лежит в одной памяти, обращение к которой может быть независимым, поэтому потребуется т.н. двухпортовая память (dual_port_sync_ram). Эта память устроена в нашем случае точно так же как и однопортовая, но имеет два независимых дешифратора адреса.
Для стека и памяти переменных также использована двухпортовая память.
Декодеры инструкций в обоих потоках совершенно одинаковые
Исполнители потоков отличаются набором инструкций. Идентификаторы (опкоды) инструкций потоков исполнения и управления пересекаются, но это ничему не противоречит, их исполняют разные конвейеры.
При исполнении потоком управления инструкции exec, задаётся стартовый адрес для работы потока исполнения, инициируется начало его работы и происходит ожидание остановки его конвейера.
Собираем пример (test_exec), запускаем в эмуляторе и убеждаемся, что в сегменте данных по адресу 16 появилось заветное значение 5.
Ветвление.
Ветвление - это условная операция, когда ветка кода исполняется только при выполнении некоторого логического условия. Или в зависимости от этого условия происходит выбор из двух веток.
Для поддержки ветвления нам потребуются две новые инструкции в поток управления и одну в поток исполнения
if2 - конец работы, opcode = 2, аргумент один - адрес (в потоке управления) второй (срабатывающей при ложном результате проверки) ветки. Первая (истинная) ветка начинается сразу за данной инструкцией.
goto - безусловный переход, opcode = 3, один аргумент - адрес перехода в потоке управления
gt - целочисленное сравнение, opcode = 8, аргументов нет - числа для сравнения берутся со стека. если число на предпоследней позиции стека больше аргумента на вершине стека, значение на вершине стека замещается единицей, иначе - нулём. При этом предварительно с вершины стека удаляется один из двух аргументов
Рассмотрим на примере.
c = 3; |
должно превратиться в код
По адресам с 0 по 11 расположены инструкции потока управления, с 16 по 28 - потока исполнения.
Переменную C задавали ранее, её адрес равен 8, значение: 3.
На этот раз не требуется почти полностью переписывать тестовый пример (test_exec),
достаточно лишь реализовать новые инструкции (executer_cf.sv + executer_xf.sv) и использовать другой файл (rom_image_ifcode.mem) для определения исполняемого кода. А также добавить механизм сброса FIFO и рестарта декодера.
Компилируем (test_exec), запускаем … работает.
Вот что здесь видно:
первые четыре слова памяти заняты переменными a, b, c, d по порядку, в переменной с лежит значение 3.
регистр TOS имеет значение 0x10 т.е. стек начинается сразу за переменными
в какой-то момент на вершину стека попадает значение 8, TOS становится 0x14, это сработала инструкция push c
далее значение 8 в стеке меняется на 3 - это инструкция eval подменила адрес переменной на её значение
после работает инструкция imdpush 1, которая помещает в стек второй аргумент для сравнения
далее значение на вершине стека меняется на 1, при этом стек уменьшается на одно значение - это отработала инструкция gt, поскольку 3 > 1, значение изменено на логическую единицу
далее уменьшается значение TOS - отработала инструкция if2, которая проверила значение и убрала его со стека
и наконец, на вершину стека попадает значение 0xa - это отработала ветвь, содержащая imdpush 10
Циклы.
В сущности, уже есть всё, чтобы исполнять циклы.
Пример будет такой:
a = 1; |
Это соответствует коду:
Здесь появилась новая инструкция потока исполнения
assign - присвоение значения по адресу, в предпоследней позиции стека лежит адрес, по которому присваивается значение с вершины стека, после чего адрес удаляется, значение остаётся, стек уменьшается на одно значение (присвоенное значение остаётся на вершине стека, далее удаляем его при необходимости инструкцией pop), opcode=9, аргументов нет
В теле цикла (начиная с адреса 23) расположены аж три инструкции varpush a. Это не опечатка и вызвано вот чем:
согласно техзаданию, в начале итерации цикла на вершину стека заносится значение переменной ‘a’, этому соответствует код varpush a; eval;
далее просто varpush a; - этим мы помещаем в стек адрес переменной, по которому далее инструкцией assign будет записано значение
дополнительные varpush a; eval; нужны для вычисления выражения a+1
отметим, что после работы инструкции assign в стеке остаётся вычисленное значение, это нужно для каскадного присваивания (например a=b=c=0;), ежели нам когда-нибудь захочется его сделать.
в отсутствие каскадного присвоения приходится добавлять инструкцию pop. Пожалуй, стоит завести две инструкции assign - со встроенным pop и без, но это уже из области оптимизации, сейчас слишком рано об этом думать.
Компилируем (test_exec), запускаем … работает.
Вот что видно на картинке:
с каждой итерацией стек подрастает на одно значение (до 11), это из-за той самой “записи в стек значения “a”” в начале итерации. Обычно (в программировании) так не делают, можно не уследить за числом итераций и исчерпать стек. Здесь же сделано исключительно для наглядности.
как и раньше, в первых четырёх словах памяти расположены переменные a, b, c, d но в данном случае значение a (по адресу 0) растёт до 11, после чего цикл заканчивается
возня на вершине стека - это как раз вычисление a=a+1;
значение TOS после выхода из цикла - 0x38 (56). Оно складывается из 16 (4 слова с переменными) + 40 (10 слов со значениями “a”).
Функции.
С точки зрения вычислимости, теперь есть всё что нужно для реализации машины Тьюринга, а следовательно и любого алгоритма. Однако с практической точки зрения, именно функции дают возможность создавать осмысленный, структурированный код, который легко писать и поддерживать в эксплуатации.
С точки зрения нашей архитектуры, вызов функции - это в некотором роде исполнение обобщенной инструкции, которая производит определённые программистом действия. Так же как и обычная инструкция, функция может иметь некоторое количество аргументов, передаваемых через стек, результат её работы также помещается на вершину стека после его очистки от аргументов. Функция может иметь локальные переменные, располагаемые на стеке, вызывать другие функции, включая саму себя (рекурсия). Но по выходу из функции стек должен остаться в том же состоянии что был до начала вычисления аргументов функции, плюс результат.
До сих пор мы имели дело только с переменными, расположенными в глобальной памяти, чьи адреса были известны на этапе компиляции. Теперь ситуация изменилась, данные лежат в области стека (и, в случае рекурсии, несколько раз), определить их абсолютные адреса на этапе компиляции невозможно.
Так возникает концепция контекста функции (frame). Введем новый регистр FP в котором станем хранить адрес, с которого начинаются локальные данные функции.
При вызове функции регистр FP указывает на новый контекст, а при возврате из неё возвращается в исходное состояние.
Потребуются две новые инструкции потока управления:
call - вызов функции, opcode=4, аргументов 3
адрес вызываемой функции
размер памяти под аргументы (на данный момент исходим из того, что каждый аргумент занимает в памяти одно слово)
размер памяти для внутренних (стековых) переменных также в словах
ret - возврат из функции, opcode=5, аргументов нет, возвращаемое значение уже лежит на вершине стека
И одна для потока исполнения:
locpush - opcode=10, обращение к локальной переменной или аргументу, аналогично varpush, разница в том что аргументом является не абсолютный адрес, а относительный (от текущего значения регистра FP)
Разберём на примере.
Пусть требуется вызвать функцию вычисления квадратного корня (sqrt). Функция требует один аргумент и для работы ей (предположим) требуется 3 локальные переменные. Исходный код: sqrt (4);
Первым делом компилятор вычисляет аргумент: imdpush 4;
Эта инструкция помещает на вершину стека значение 4.собственно вызов call sqrt 4 12;
в момент вызова из аргументов инструкции известно, что frame в стеке уже длится одно слово, необходимо сдвинуть регистр TOS еще на три слова для размещения локальных данных функции
необходимо сохранить в стеке адрес возврата из функции (в потоке управления) - это будет адрес инструкции, следующей за call. Помещаем адрес на вершину стека. Для этого придётся расширить функционал декодера, теперь он будет хранить в элементе FIFO не только код инструкции или её аргументы, но и адрес исходной памяти, следующий за распакованным элементом
также необходимо сохранить старый указатель FP
и не забудем про указатель TOS
размер фрейма в данном случае составляет 1 + 3 + 1 + 1 + 1, всего 7 слов.
для обращения к параметру функции компилятор использует инструкцию locpush с аргументом - сдвигом относительно FP. В данном случае аргумент один и доступ к нему происходит через locpush 0;
доступ к локальным переменным аналогичен, так обращение ко второй из трёх (слово 32 разряда) выглядит как locpush 8; Отметим, что инструкция locpush заносит в стек адрес, для получения значения пригодится уже знакомая инструкция eval, для изменения переменной - также как и раньше - assign.
для возврата из функции
в потоке исполнения помещаем возвращаемое значение (sqrt(4) => 2) на вершину стека, далее останавливаемся на инструкции stop.
следующая инструкция в потоке управления - ret.
при ее исполнении
запоминаем возвращаемое значение с вершины стека
находим в стеке адрес возврата и также запоминаем
находим в стеке размер фрейма и уменьшаем регистр FP на эту величину.
уменьшаем значение регистра TOS = FP
помещаем возвращаемое значение на вершину стека
переходим по сохранённому адресу возврата
Такая схема вызова функций позволяет нам передавать и переменное число параметров, как, например в семействе printf в C. Мы сохранили указатель в коде чтобы продолжить, старые указатели стека и фрейма. Не исключено, что можно было оформить вызов и покомпактнее, но на данном этапе не до оптимизаций.
Что же, пора приступить к реализации. Проверочным примером будет рекурсивное вычисление факториала:
В коде на С это выглядит так:
int factorial(int i) |
Что соответствует коду (поток управления):
Код потока исполнения:
Компилируем (test_exec),
запускаем, отлаживаем,
запускаем, отлаживаем,
…
работает.
На картинке видно как менялось состояние памяти данных в процессе работы.
первые 4 слова, как и прежде, заняты статическими данными (a,b,c,d)
на левой половине видно создание первого контекста вызова с параметром 6
правая часть начинается с создания последнего контекста с параметром 1 и спуск с постепенным вычислением результата
1
1 2
1 2 * 3
…в конце концов получаем в ячейке с адресом 4 т.е. в самом начале стека искомое значение 0x2d0 => 720 (факториал от 6).
Итоги.
Что достигнуто на данный момент?
Работающая на эмуляторе (конечно, следует добиться работы на ПЛИС) модель процессора с безадресной (стековой) архитектурой.
Память данных и кода разделена, но не потому, что это часть задумки, так оказалось проще. В дальнейшем следует перейти на единый интерфейс памяти. Непонятно, будет ли это обычная динамическая память или работающая на частоте процессора статическая.
Нет кэширования памяти, на данный момент оно не нужно.
Нет кэширования декодированного кода, при переходе каждый раз всё начинается с начала, на данном этапе думать об этом преждевременно
система команд требует переработки, идентификаторы команд присваивались по мере возникновения потребности в них. Но в номере можно закодировать массу полезной информации, например, какие функциональные устройства она использует. Странно было бы не воспользоваться такой возможностью
В системе команд есть только работа с целочисленными данными размером в слово (32 разряда). Было бы несправедливо забыть об остальных. Если более крупные 64 разрядные можно эмулировать (подменять инструкции работы с ними цепочками 32-разрядных инструкций, делающими то же самое), то для 8- и 16- разрядных придётся заводить свои линейки инструкций.
В процессоре нет MMU, на данный момент оно просто не нужно
То же касается работы с плавающей точкой
А вот работа со строковыми данными пригодится, её еще придётся продумать
…
Но самое главное, чего не имеется
Нет никакой среды разработки программ. Писать программы в автокоде трудоёмко и чревато ошибками. И это не приносит никакой радости (если вы, конечно, не потомок Байрона).
Совершенно необходим ассемблер для того, чтобы получать готовый код из мнемонических инструкций. Это не слишком сложная задача.
А также компилятор с языка более-менее высокого уровня. Первым приходит на ум язык С
А обретя С, получаем в своё распоряжение ключи от двери, ведущей в целую вселенную возможностей.
Что-ж, займёмся этим в следующей статье.
PS при написании этой статьи был использован только естественный интеллект
PPS несмотря на огромный стаж разработки, опыт использования автором Verilog - мизерный. Так что, если вы видите "детские" проблемы в коде, это совершенно нормально. Целью было не создание конечного продукта, а подтверждение работоспособности концепции
