Экономия ошибок

С. Зефиров, А. Сафронов, В. Шабанов, Е. Мельников

Аннотация: В статье рассказывается об опыте использования встроенных проблемно-ориентированных языков применительно к моделированию аппаратуры с процессорными ядрами. Главным соображением, давшим старт работам, было желание защититься от рисков, связанных с внесением изменений в будущем. Описана выбранная авторами декомпозиция предметной области (описание команд процессорных ядер различных архитектур). Рассмотрено применение «управляемого типами дизайна» (type-driven design).


The article discusses the use of domain-specific embedded languages in hardware modelling. Authors share their experience in reducing the risks related to the ever-changing requirements via clever decomposition of the subject domain, the use of the specialized DSL and type-driven design.



Обсуждение статьи ведётся в LiveJournal.

1  Введение

В компании «ПРОСОФТ», где работает коллектив авторов, разрабатывается система моделирования цифровой аппаратуры для разработки встраиваемой техники. Среди возможностей, предоставляемых системой — моделирование цифровой аппаратуры и процессорных ядер.

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

Спектр процессорных ядер на рынке чрезвычайно широк, от восьмибитных ядер микроконтроллеров младших классов до 128-битных IBM Cell Broadband Engine. Поскольку поддержать все существующие процессоры практически невозможно, надо попробовать сделать так, чтобы добавление нового класса процессорных ядер было как можно более быстрым и безошибочным.

Само по себе процессорное ядро не очень интересно, интересна возможность его работы в составе какой-либо системы, например, разрабатываемой (или уже существующей) системы на кристалле. Для разработчика разумно использовать модель системы в целом, поскольку так проще контролировать поведение частей системы. Одна часть модели системы, куда будет входить процессорное ядро, может быть создана с помощью языка описания аппаратуры, а другая часть — с помощью редакторов схем. Отсюда возникает требование к гибкости подключения модели ядра к «внешней среде». Такое подключение производится с помощью внешней шины, по которой происходит обмен информацией с другими компонентами системы. Протоколов, по которым могут работать шины, несколько: например, AMBA [2], Wishbone [12] и CoreConnect [5]. Желательно иметь возможность быстро переключаться между различными протоколами, выбирая их под текущие нужды.

Ещё одна степень свободы появляется, если мы хотим получить точность моделирования ценой снижения скорости, и наоборот. Простой пример: за сколько тактов надо выполнять умножение — за один, или как в документации?

Скорость создания программы, в нашем случае модели ядра процессора, зависит от числа ошибок и сложности их исправления. Существенным источником ошибок является необходимость моделировать большое число команд (зачастую более сотни), и это не считая ещё «дополнительных степеней свободы» — дополнительных возможностей применения модели. Контроль за соблюдением правильности выполнения каждой отдельной команды и возможными вариантами общения с шиной хотелось бы поручить формальным средствам. Это подводит нас к необходимости иметь язык описания моделей процессоров. Язык может быть внешним, со своим синтаксисом и обычным циклом обработки (лексический разбор, синтаксический разбор, проверка типов, выполнение тестовых участков и кодогенерация), а может быть встроен в язык общего назначения, что позволяет экономить время на написание трёх этапов из пяти.

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

2  Возможные ошибки моделирования ядер процессоров

Какие проблемы стоят перед системами моделирования? Какие возможности требуются от них? Почему бы не воспользоваться существующими средствами — например, доступными в исходных кодах моделями процессоров (QEMU [11] или аналогичными эмуляторами)?

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

Напрямую использовать эмуляторы процессорных ядер в открытых исходных кодах невозможно по нескольким причинам. Одна из них — лицензии, под которыми выпущены эти эмуляторы. Обычно это GNU GPL, которая препятствует их использованию в системах моделирования с закрытым кодом. Кроме того, есть две технических проблемы: нам надо, чтобы, во-первых, модель процессора эффективно работала в моделировании схемы в целом и, во-вторых, чтобы мы могли использовать модель процессора в разных окружениях (разные ядра моделирования, разные протоколы шины, разная точность моделирования). Эмуляторы в открытых исходных кодах обычно написаны на языке C, что делает их доработку, как минимум, трудоёмкой задачей. Если же мы планируем использовать параллельное моделирование (с использованием процессов операционной системы или MPI), да ещё под разными целевыми платформами (кодогенерация в C, в Java VM с языком Java, в .Net с C#), то использование языка C становится прямо противопоказанным.

Есть также ещё ряд желательных требований:

  1. правильное взаимодействие отдельных частей внутри модели, а также между моделью и внешним миром;
  2. гибкость в подключении к внешнему миру;
  3. гибкость в размене точности моделирования на скорость моделирования;
  4. гибкость в выборе системы моделирования (целевая VM или язык, метод моделирования — параллельный (на нескольких процессорных ядрах или даже на кластере) или последовательный);
  5. максимальное повторное использование кода внутри линейки процессоров (снижение комбинаторной сложности с произведения на сумму).

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

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

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

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

Итак, ядро описания процессорных ядер должно быть встроено в язык программирования высокого уровня. В нём должны присутствовать следующие возможности:

Все это позволяет решить пять проблем, обозначенных выше, с минимальными затратами.

На роль языка-носителя для нашего DSL подойдёт любой язык с вычислениями на уровне типов и (хотя бы) возможностью создания (инфиксных) операторов пользователя. Тонким моментом является возможность связывания переменных и значений — можно ли посередине описания ввести в обиход новый идентификатор, или нет. Если такая возможность есть, то использование DSEL становится более удобным.

Рассмотрим пригодность на роль языка-носителя несколько распространённых языков:

Перед тем, как приступить к объяснению технических деталей описания модели, приведём фрагмент кода, дающий примерное представление о получающемся описании:

-- команда ADC — сложение с переносом. -- сперва идёт название команды с её форматом, -- потом код команды в микрокомандах. cADC = command "adc" (rdddddrrrr [0,0,0,1,1,1]) $ do -- eFC — выражение, адресующее флаг C. -- Оно имеет размер 1 бит и должно быть расширено -- нулями до размера регистра. -- -- regRr и regRd — значения регистров по адресам -- из переменных Rr и Rd. varRes $= regRr + regRd + zeroExt efC setflags False False -- вычитание ли, с переносом ли regRd regRr regRes -- откуда брать данные [FH,FS,FV,FN,FZ,FC] [] -- какие флаги менять writeRd regRes test_ADD_SUB False False True noVar -- Тестирование команд сложения, вычитания и прочих. -- -- AVCCM — монада описания команд AVR, частный вариант -- монады описания команд. -- -- Maybe (AVRVar a size) используется для указания переменной -- процессора с константой (любого размера). test_ADD_SUB :: (AVRProgMem a, NatInt size) => Bool -> Bool -> Bool -> Maybe (AVRVar a size) -> AVRCCM a () test_ADD_SUB testSub resultIsA withCarry mbReg = -- test_binary произведёт вызов кода команды с -- разными входными данными и сравнит результаты -- прогона с результатами вычисления функции answer. test_binary answer withCarry (not resultIsA) mbReg [FH,FS,FV,FN,FZ,FC] where answer a b inputC = (r,oc,hc,v) where -- здесь вычисляются результат команды r и -- всевозможные флаги (oc, hc и v) простейшим -- способом (сложением и сдвигами). Алгоритм -- отличается от алгоритма в документации, но -- смысл сохранён. -- Это помогло обнаружить ошибки, допущенные -- при редактировании методом copy-paste.

В определении команды ADC мы видим:

В следующей главе рассказано о технических решениях, позволивших добиться, чтобы проверялось всё, что требуется.

3  Ядро языка описания

Ядро состоит из трёх модулей: модуля арифметики на типах данных для задания размерности данных, модуля описания микрокоманд и модуля формирования модели команды. Они напрямую соответствуют предметной области, и строились примерно в перечисленном порядке.

Все операции ядра описания команд параметризованы типом процессора, поэтому мы можем контролировать используемые возможности процессоров и размеры типов данных. Ядро позволяет нам решить первые две проблемы из списка 2.

Описание микрокоманд также бьётся на три части: присваиваемые выражения, разрешённые типы микрокоманд и сборка описаний.

3.1  Варианты описания

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

-- где-то объявлена функция createDescription. -- vs — это вложенные пары, начиная с (): -- (), (a,()), (b,(a,()))... createDescription :: VarList vs => (vs -> [Stat]) -> Description -- вот, как мы создадим наше описание: ourDescription = createDescription -- изобретением имён заведует -- createDescription. (\(x,(y,(z,()))) -> -- здесь мы можем использовать -- данные нам идентификаторы. [ input x, y $= f x, load y z , y $= g z, ...])

С возможностью связывания всё немного проще:

-- где-то есть функция createDescription: createDescription :: DescriptionAction () -> Description -- вот наше описание: description = createDescription $ do -- здесь и изобретение имени, и -- создание части описания одновременно. x <- input -- изобретение имени <<по месту>>: y <- declareVar y $= f x z <- declareVar load y z y $= g z

Если обобщить, то первый вариант описывается оператором >> из класса Monad, для второго требуется оператор >>=:

class Monad m where return :: a -> m a (>>=) :: m a -> (a -> m b) -> m b (>>) :: m a -> m b -> m b

Если все операторы первого примера (input, load, (var $expr)) имеют одинаковый тип Stat, то подойдёт и обычный список.

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

3.2  Арифметика на типах данных и битовые вектора

Идея арифметики на типах данных [15] проста: мы выражаем некоторые вычисления внутри системы типов, контроль типов проводит вычисления во время компиляции и сообщает нам о найденных ошибках. В принципе, это похоже на проверку типов в языках Паскаль или Ада [1], только размеры массивов-векторов не обязаны быть константными, и типы по возможности выводятся автоматически, поэтому от многих объявлений типов можно отказаться.

Технически, простейший вариант основан на арифметике Пеано [13]. Мы создаём два пустых типа, Z и S n и с помощью семейств типов конструируем «функции» для сложения «численных типов»:

data Z -- 0 data S n = S {sArgument :: n} -- 1+n type family Plus a b -- 0+x == x type instance Plus Z a = a -- (1+x)+y == 1+(x+y) type instance Plus (S a) b = S (Plus a b)

Недостаток простой арифметики Пеано — очень длинные выражения для размерностей. Число 8 в типах выглядит так: S (S (S (S (S (S (S (S Z))))))). Поэтому для задания размеров придётся завести несколько констант:

type ONE = S Z type TWO = Plus ONE ONE ... type SIZE12 = Plus SIX SIX type SIZE16 = Plus EIGHT EIGHT ...

В процессе работы нам может понадобиться вычисленное целочисленное значение размера. Его легко получить с помощью класса:

class NatInt a where natInt :: a -> Int instance NatInt Z where natInt = const 0 instance NatInt n => NatInt (S n) where natInt (S n) = 1+natInt n

Класс NatInt сам по себе служит дополнительной проверкой ограничений во время компиляции — он не даёт задать в качестве параметра-размера произвольный тип данных.

При использовании параметризованных размерами типов мы уменьшаем количество ошибок, связанных с учетом размером данных (см. список в 2).

3.3  Описание микрокоманд

Ниже в описании микрокоманд часто фигурирует параметр cpu. Это тип, определяющий характеристики процессора — его возможности и размерности некоторых операндов. Характеристики процессора и других частей системы задаются как типы данных, чтобы иметь возможность как можно раньше контролировать правильность создаваемого кода интерпретатора.

Параметры определяются ассоциированными типами данных [16] для класса CPU:

class CPU cpu where type RegDataSize cpu type RegAddrSize cpu type MemDataSize cpu type MemAddrSize cpu type Vars cpu type Funcs cpu

Сперва идут четыре параметра — размеры данных для различных частей системы, регистрового файла и памяти. Они задаются в виде чисел в аксиомах Пеано.

Параметр type Vars cpu позволяет уточнить доступные конкретной реализации процессора переменные. Например, 8086 не поддерживал переменную «корень таблицы трансляции адресов», а 80386 и выше её поддерживают. Задав типы переменных процессора, мы можем ограничивать набор команд — команды управления трансляцией адресов будут требовать расширенный набор переменных и не попадут в модель 8086.

Разные процессоры имеют разные специальные функции, которые не могут быть выражены в виде примитивных команд, что и служит основанием для наличия параметра type Funcs cpu. Примером специфичной для AVR функции может служить установка сигнала watchdog, которая не встречается во многих других процессорах.

Параметр cpu может быть параметризованным типом. Например, для MIPS32 и MIPS64:

data MIPS bits type MIPS32 = MIPS SIZE32 type MIPS64 = MIPS SIZE64 instance NatInt bits => CPU (MIPS bits) where type RegDataSize (MIPS bits) = bits type RegAddrSize (MIPS bits) = FIVE -- 32 regs. type MemDataSize (MIPS bits) = bits type MemAddrSize (MIPS bits) = Sub bits (Log2 (MemDataSize (MIPS bits))) type Vars (MIPS bits) = ... type Funcs (MIPS bits) = ...

Код команд для обоих вариантов MIPS должен уметь работать с любым размером регистров, и проверка типов убедится, что это именно так.

Добавив параметр типа для указания типа шины, мы можем усложнить код — размеры адреса и данных при обращении к памяти, переменные процессора и функции процессора будут зависеть от типа шины. Таким образом, мы можем получить MIPS64, подключенный к 32-битной AXI — (MIPS SIZE64 (BusAXI SIZE32)), — или наоборот.

3.4  Присваиваемые в микрокомандах выражения

Мы выделили два типа переменных: переменные процессора, содержащие значение типа Vars cpu, и пронумерованные временные переменные:

data Var cpu size where CPUVar :: Vars cpu -> Var cpu size TempVar :: Int -> Var cpu size

Переменные процессора соответствуют частям состояния процессора и отражены в документации. Многие из них сохраняются между циклами выполнения различных команд. Временные переменные требуются для хранения значений, которые не потребуются при выполнении следующей команды.

Описание используемых выражений не несёт никаких особенных сюрпризов — это привычный набор из констант, переменных, бинарных и унарных выражений. Есть даже тернарный оператор ESelect, аналог оператора ?: из языка Си. Исключение составляют взятие значения из регистра EReg1 и обращение к функциям процессора.

Отметить стоит лишь богатую параметризацию всех операций: размеры результатов и операндов связаны либо через параметр cpu (путём использования производных от него параметров-типов), либо через размеры операндов и результата конкретных операций, например, BinOp.

data Expr cpu size where EConst :: NatInt size => Integer -> Expr cpu size EVar :: NatInt size => Var cpu size -> Expr cpu size EReg :: Expr cpu (RegAddrSize cpu) -> Expr cpu (RegDataSize cpu) EBinary :: (NatInt leftsize, NatInt rightsize , NatInt resultsize) => BinOp leftsize rightsize resultsize -> Expr cpu leftsize -> Expr cpu rightsize -> Expr cpu resultsize ESelect :: Expr cpu ONE -> Expr cpu size -> Expr cpu size -> Expr cpu size EUnary :: (NatInt argsize, NatInt resultsize) => UnOp argsize resultsize -> Expr cpu argsize -> Expr cpu resultsize EFunc :: Show (CPUFuncs cpu resultsize) => CPUFuncs cpu resultsize -> Expr cpu resultsize

Типы BinOp и UnOp заслуживают пристального внимания2:

data BinOp leftsize rightsize resultsize where Plus, Minus, Mul, And, Or, Xor :: BinOp size size size Mul2, Concat :: BinOp size size (Plus size size) ShiftRL, ShiftRA, ShiftL :: BinOp size shiftsize size Equal, NEqual, GetBit :: BinOp size size ONE data UnOp argsize resultsize where Negate, Complement :: UnOp argsize argsize ZeroExt, SignExt :: UnOp argsize resultsize

Тип BinOp содержит: а) операции с одинаковым размером операндов и результата операции, размер результата которых равен некоей функции (сумме) размеров операндов, б) операции, один из операндов которых не имеет фиксированного размера3 и в) операции с фиксированным размером результата.

Тип UnOp не столь разнообразен. Он содержит две операции, не изменяющих размер, и две операции, изменяющих размер в произвольную сторону. Операция ZeroExt применяется для преобразований между числами разного размера, иногда не совсем безопасно.

Похожие операции есть в каждом языке описания аппаратуры. В VHDL/Verilog производится контроль размерности и используются операции на обычных целых числах или константах. В Bluespec Verilog в систему типов был заведен сорт (kind) Integer, который тоже позволяет использовать (ограниченный, по словам самих создателей Bluespec) набор функций над целыми значениями в типах. Мы же внесли недостающие операции в систему типов, практически не расширяя используемый язык, описанный в 3.2.

3.5  Типы микрокоманд

Микрокоманды имеют небольшую номенклатуру, буквально самое необходимое:

data Stat cpu where SAssign :: NatInt size => Var cpu size -> Expr cpu size -> Stat cpu SLoad :: CPU cpu => Var cpu (MemDataSize cpu) -> Expr cpu (MemAddrSize cpu) -> Stat cpu SStore :: CPU cpu => Expr cpu (MemDataSize cpu) -> Expr cpu (MemAddrSize cpu) -> Stat cpu SWriteReg :: CPU cpu => Expr cpu (RegAddrSize cpu) -> Expr cpu (RegDataSize cpu) -> Stat cpu -- Вызов функции, не требующей присваивания результата. -- Возвращается результат размером 0, что соответствует тривиальному типу (). SStat :: (CPU cpu, Show (CPUFuncs cpu Z)) => CPUFuncs cpu Z -> Stat cpu -- Разделитель этапов (носит характер указания). SStage :: Stat cpu

Здесь упомянуты присваивание, загрузка слов из памяти, сохранение слов в память, запись в регистровый файл4, произвольное действие с окружающей средой и разграничение этапов.

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

Количество применений SStat, вызывающих специфичные для процессора функции и представляющих особый случай для кодогенератора, как показывает практика, невелико.

3.6  Сборка описаний

Описание команд процессора в виде микрокоманд создаётся внутри параметризованной монады состояния (State Monad) поверх монады IO (последняя нужна для отображения результатов тестирования). Ниже приведёны типы, с помощью которых хранится описание процессоров:

-- Кортеж описания отдельной команды. -- Состоит из: -- имени, битового формата команды, состояния, -- счётчика временных переменных и флага, -- была ли команда протестирована. data Cmd cpu = Cmd { cmdName :: String , cmdMatch :: [Match cpu] , cmdStats :: [Stat cpu] , cmdTempVarIndex :: Int , cmdTested :: Bool } -- Список команд и флаг разрешения прогона тестов при генерации. data CCMState cpu = CCMState { ccmStateCommands :: [Cmd cpu] , ccmStateTestsEnabled :: Bool } deriving Show -- CCM расшифровывается как CPU Construction Monad. type CCM cpu a = StateT (CCMState cpu) IO a

Примитив command создаёт начальное описание команды, с заданным форматом команды, нулевым счётчиком временных переменных и пустым списком микрокоманд. Микрокоманды постепенно добавляются в конец списка примитивом addStat, поверх которого реализованы все действия выше уровнем — оператор $=, функции writeRd и setFlags и другие операции описания, не представленные в этой статье.

addStat :: Stat cpu -> CCM cpu () addStat stat = modifyLastCmd $ \ c -> c { cmdStats = cmdStats c ++ [stat] } modifyLastCmd :: (Cmd cpu -> Cmd cpu) -> CCM cpu () modifyLastCmd f = modify $ \ccms -> let (lastCmd:cmds) = ccmStateCommands ccms in ccms { ccmStateCommands = f lastCmd : cmds } ($=) :: NatInt size => Var cpu size -> Expr cpu size -> CCM cpu () v $= e = addStat (SAssign v e)

Отдельно стоит упомянуть выделение временных переменных. Размер получаемой переменной не фиксирован:

tempVar :: NatInt size => CCM cpu (Var cpu size)

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

Вывод типов срабатывает не всегда, иногда требуется задать размер явно. У нас таких случаев оказалось всего два: байтовая переменная и переменная в 16 бит. Авторы считают, что это связано с недостаточно хорошо прописанными ограничениями в типах операций. Этот недостаток описания не привел к серьёзным проблемам в процессе реализации проекта.

То, что команды и даже их отдельные части являются объектами первого класса в Haskell, нашем языке-носителе, позволяет нам повторно использовать код без ограничений.

4  Тестирование

Тестирование производится ещё в одном преобразователе состояния StateT:

type TestMonad cpu a = StateT (TestMonadState cpu) IO a

Микрокоманды из описания поведения переносятся в состояние TestMonadState и интерпретируются с разными окружениями, в которых задаются значения индексов регистров-операндов, значения самих регистров-операндов, значения ячеек памяти и т. п.

Параметр cpu, помимо возможности задания значений переменных, определяет ещё и карты памяти всевозможных конфигураций. В общем случае, процессор может обращаться к нескольким адресным пространствам — памяти программ и данных, пространству ввода-вывода, а в некоторых специализированных моделях существуют и другие варианты пространств. В процессе работы в составе системы процессор будет выполнять обращения по разным протоколам. Для тестирования достаточно просто разнести разные по смыслу пространства.

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

Интерпретатор микрокоманд выполняет действия, заданные в описании поведения текущей команды, рапортуя об отсутствующих (не установленных в процессе выполнения или как часть начального окружения команды) значениях регистров или адресов памяти.

5  Результаты и обсуждение

5.1  Результаты применения

Мы использовали язык описания для создания моделей процессоров семейства Atmel AVR: ATtiny10, ATmega8, ATmega128 и ATmega640. Они отличаются размером счётчика команд (9 бит для ATtiny10, 16 бит для ATmega128) и наличием или отсутствием некоторых команд. Другой особенностью этой линейки является отображение регистров процессора и портов ввода-вывода на пространство адресуемой памяти.

Использовалась внешняя шина APB с немного изменённым протоколом.

Все особенности процессоров были занесены в параметры моделей. Размеры счётчика команд и наличие различных команд были заданы в качестве параметра модели и проверялись статически. Карта памяти, также являвшаяся частью модели, учитывалась при кодогенерации5.

Код описания 125 команд содержит 710 полезных строк (5,7 строк на одну команду). Кодогенератор в Java состоит из трёх файлов, содержащих 287 полезных строк. Текст на Java, создаваемый по описанию команд, занимает более 1500 строк.

Работы над описанием команд и кодогенерацией производились тремя программистами: двое хорошо знали Haskell, а третий изучал его в процессе. Основная часть работ по описанию команд и кодогенерации была выполнена нашим коллегой в процессе изучения языка. Средняя скорость описания команд составила приблизительно три команды в день6. Один из опытных программистов на Haskell добавил в описания команд тесты, выполняемые перед кодогенерацией, второй улучшил кодогенерацию и подключил модели процессоров к нашей системе моделирования, выполнив на них функциональные тесты.

Поскольку система времени выполнения AVR-gcc использует достаточно большой процент команд AVR, мы использовали 4 функциональных теста на языке Си, основу которых составлял тест с вызовом sprintf и вычислениями с плавающей точкой. Прогон функциональных тестов выявил в модели всего 6 ошибок, две из которых относились к неполной документации в описании команд и были поправлены путём поиска дополнительной информации в Интернет, оставшиеся четыре находились в функционале команд условного перехода, трудных для тестирования без функционального теста7.

5.2  Возможные варианты использования

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

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

Мы можем сформировать и конвейерное выполнение, ведь мы знаем обо всех внутренних переменных процессора, и можем проанализировать команды попарно на предмет наличия межстадийных зависимостей. (Например, если одна команда пишет свой результат в определённую переменную состояния, а другая из неё читает, то требуется внести циклы ожидания во вторую команду до завершения работы первой. Подробнее см. [9].) Эта задача сложнее, но достижима.

Используя интерпретатор микрокоманд, мы можем сделать автоматический генератор кода для кодогенерации, например, для gcc [7] или BURG [14, 8]. В случае BURG кодогенерация идёт путём сравнения текущего дерева выражений программы с набором образцов, заданных в файле описания процессора. У каждого возможного дерева выражений есть определённая семантика. Для создания автоматического генератора кодогенераторов потребуется автоматическое перечисление (всех) возможных образцов дерева выражений программы, а также транслятор семантики образца в семантику изменения регистров и переменных программы. Похожие техники (правда, с ограниченным количеством примитивов) уже использовались в прошлом для устранения ветвлений при трансляции некоторых конструкций языка C [17].

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

6  Заключение

В статье мы постарались показать, как можно попытаться сэкономить время разработки, планируя реакцию на возможные ошибки. Мы также постарались показать на примерах, какие средства язык программирования Haskell предоставляет для создания встроенных в язык проблемно-ориентированных языков (DSL). В нашей работе мы отталкивались от ошибок, которые можно совершить при создании моделей процессорных ядер. Современная система типов Haskell позволила нам защититься от большинства из них без особых затрат. Похожие рассуждения можно применить и в других предметных областях.

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

Использование функционального языка не является препятствием для создания описаний процессоров даже при отсутствии соответствующего опыта у программиста. Более того, только в современных функциональных языках программирования система типов достаточно выразительна [16, 15] для указания достаточного количества ограничений.

Если сравнивать наш проект с проектом CGEN [4], открытым проектом для создания средств описания ассемблеров, дизассемблеров и симуляторов для различных архитектур микропроцессоров, то можно отметить следующее: во-первых, наш DSL ориентирован на создание моделей (симуляторов), хотя может быть расширен и информацией о командах для ассемблеров и дизассемблеров; во-вторых, мы используем метапрограммирование на типах для более ранней диагностики возможных ошибок, тогда как CGEN использует макроопределения языка Scheme. CGEN ориентирован на создание симуляторов на языке C, тогда как нашей задачей было получить возможность кодогенерации в разные ЯП для достижения максимально возможного быстродействия всего комплекса моделирования (в частности, с использованием параллельного выполнения разных частей на разных ядрах).

Список литературы

[1]
Ada Reference Manual. http://www.adaic.org/standards/95lrm/html/RM-TTL.html. ISO/IEC 8652:1995(E).
[2]
AMBA Specification Rev2.0. http://www.arm.com/products/solutions/AMBA_Spec.html. Описание семейства шин AMBA.
[3]
An experimental domain specific language for template metaprogramming. http://goo.gl/btlV. Доклад о применении языка Haskell для программирования в обобщённом стиле на C++/Boost.
[4]
CGEN, the Cpu tools GENerator. http://sourceware.org/cgen. Описание архитектур CPU.
[5]
CoreConnect Bus Architecture. https://www-01.ibm.com/chips/techlib/techlib.nsf/products/CoreConnect_Bus_Architecture. Шина CoreConnect фирмы IBM.
[6]
Generic Libraries in C++ with Concepts from High-Level Domain Descriptions in Haskell. http://dsl09.blogspot.com/2009/07/here-are-talk-slides-as-pdf.html. Доклад о применении DSL на Haskell для программирования в обобщённом стиле на C++.
[7]
GNU Compiler Collection. GCC, компилятор C, C++, Ada и многих других языков.
[8]
lcc: A portable C compiler. http://sites.google.com/site/lccretargetablecompiler/. Компилятор ANSI C с быстрой настройкой под выбранную архитектуру.
[9]
Lecture 6: Pipelining Contd. http://www.stanford.edu/class/ee282h/handouts/Handout16.pdf. Часть цикла лекций Стэндфордского университета про реализацию микропроцессорных архитектур.
[10]
Microprocessor without Interlocked Pipeline Stages. http://en.wikipedia.org/wiki/MIPS_architecture. Один из самых простых RISC-микропроцессоров.
[11]
QEMU — a generic and open source machine emulator and virtualizer. http://wiki.qemu.org/Main_Page. Эмулятор для большого числа процессоров и виртуальной периферии на большом числе платформ, включает в себя двоичную трансляцию.
[12]
WISHBONE System-on-Chip (SoC) Interconnection Architecture for Portable IP Cores. http://www.opencores.org/downloads/wbspec_b3.pdf. Описание шины внутрикристального взаимодействия Wishbone.
[13]
Арифметика Пеано. http://ru.wikipedia.org/?oldid=20954203. Статья в Wikipedia об аксиомах арифметики Пеано.
[14]
T. A. Proebsting C. W. Fraser, R. R. Henry. BURG — fast optimal instruction selection and tree parsing. 1992. Описание генератора кодогенераторов на основе сравнения с образцом поверх деревьев внутреннего представления компиляторов.
[15]
Oleg Kiselyov. Number-parameterized types. 2005. Целочисленная арифметика внутри системы типов Haskell.
[16]
Tom Schrijvers, Simon Peyton-Jones, Manuel M. T. Chakravarty, and Martin Sulzmann. Type Checking with Open Type Functions. 2008. Семейства типов — простые вычисления над типами во время компиляции.
[17]
Richard Kenner Torbjorn Granlund. Eliminating Branches using a Superoptimizer and the GNU C Compiler. 1992. Использование супероптимизации для улучшения кодогенерации GCC.

1
Авторы считают, что внесение этого действия в набор общих выражений — не самый лучший ход, но из песни слова не выкинешь.
2
Конструкторы с одним типом перечислены через запятую для уменьшения размера кода, Haskell не позволяет такой синтаксис.
3
А мог бы: Shift* :: BinOp size (Log2 sizesize, что было бы правильней.
4
Здесь он один, но во многих архитектурах, даже MIPS [10], бывает и несколько регистровых файлов для сопроцессоров.
5
Обращение к некоторым регистрам AVR производится с помощью команд IN/OUT. Для таких адресов выполнять обращение во внешнюю память не требуется, однако требуется сохранить время выполнения команды.
6
За время от начала работ до их завершения в связи с успешным окончанием тестирования, работы велись практически последовательно.
7
Полный алгоритм команд возврата из процедуры и вызова процедуры в документации указан не был. Эту ошибку без функциональных тестов выявить не удалось.

Этот документ был получен из LATEX при помощи HEVEA