2009 → Выпуск 2

Прототипирование с помощью функциональных языков

Сергей Зефиров, Владислав Балин

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

The article discusses the use of functional programming languages in hardware modelling. The criteria are provided for choosing the functional programming languages over the more mainstream tools, and the results of the authors’ work are described.

Обсуждение статьи ведётся по адресу
http://community.livejournal.com/fprog/2260.html.

1 Введение

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

Длительный цикл разработки. Если природа задачи такова, что разработка состоит из большого количества этапов, у вас просто не хватит времени исправить ошибку в подходе. Скажем, разработка программно-аппаратных комплексов именно такова. В особенности, если у вас…
…высокая стоимость получения результата. Постановка на производство автомобиля, как и изготовление опытных образцов, является дорогой операцией. Не хватит не только времени, но и денег. На данных этапах надо действовать наверняка. Что сложно, если налицо…
…отсутствие должного опыта у инженерной группы. В случае инновационной разработки, когда вы делаете продукт на уровне лучших аналогов (или превосходящий их), это всегда так, ибо вы делаете то, что до вас почти никто не делал.

Разработка микроэлектроники, как отличный пример проектов такого типа, имеет длительный (типичная длительность проекта — 1,5 года) и многоступенчатый цикл разработки, в котором задействовано много разных специальностей. В микроэлектронике крайне велика стоимость получения результата и, следовательно, высока цена ошибки. Набор фотошаблонов для современных тех-процессов (тоньше чем 90 нм), без которого не получить образцы микросхем, стоит миллионы долларов и изготавливается фабрикой в срок от 2 месяцев, а бюджет относительно простых проектов составляет от единиц до десятков миллионов долларов. В таких условиях группа разработки продукта должна действовать наверняка — ошибка в требованиях или в выборе подхода к проблеме неприемлема и закончится для проекта фатально. Стоит отметить, что подобное происходит не только в разработке микроэлектроники — некоторые чисто программные проекты также во многих аспектах обладают подобными характеристиками. В связи с этим многие компании-разработчики микроэлектроники выполняют моделирование на раннем этапе для проверки своих решений. Определенного стандарта в данный момент не существует, применяемые инструменты варьируются от одной компании к другой. Ниже мы рассмотрим существующие средства прототипирования микроэлектроники с их сильными и слабыми сторонами и расскажем об опыте применения функциональных языков программирования в данной задаче.

2 Инструменты прототипирования компонентов

Описание рассматриваемого микроэлектронного устройства, такого как микропроцессор, представляет собой цифровую логическую схему, которая может быть сведена к комбинации элементов памяти (триггера) и логического элемента 2–и–не, соединенных проводами. Схема может быть описана в терминах этих (и более сложных) элементов, набор которых называется «библиотекой» и предоставляется фабрикой. Аналогом такого описания в программировании является язык ассемблера, специфичный для каждой их процессорных архитектур.

Сейчас разработка устройства в терминах библиотечных элементов является скорее исключением, и для описания аппаратуры применяются языки высокого уровня, такие как Verilog и VHDL, наиболее популярен из них первый.

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

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

Разработчиками САПР поддерживается два языка для решения данной проблемы. Первый из них — SystemC — на деле языком не является, это некоторый фреймворк для С++. По сути, данная библиотека позволяет писать на С++ в стиле Verilog, в том числе описывая и синтезируемые конструкции. Авторы SystemC надеялись, что развитые языковые средства С++ позволят программистам и инженерам описывать более сложные модели.

Вторым языком является SystemVerilog. Это последняя редакция языка Verilog, расширенная современными конструкциями вроде классов и типов. Упрощая структурирование крупной системы для разработчиков аппаратуры, данный язык в целом сохраняет подход Verilog и не адресует проблем архитектурного прототипирования.

Основные требования к инструментам прототипирования микроэлектроники перечислены ниже, в порядке убывания важности:

Низкие затраты на разработку. Чем раньше будет создан прототип, тем лучше.
Низкая стоимость внесения изменений. Прототип не является чем-то статичным, в него очень часто вносятся изменения. Чем короче цикл внесения изменений, тем больше экспериментов удастся провести на этапе проектирования. В идеальном случае цикл внесения изменений не должен превышать нескольких дней.
Скорость работы модели (скорость моделирования). Чем выше скорость, тем большие по объёму тесты можно будет подать на вход модели. Разница в поведении на малом и большом тестах может быть значительной¹ и существенно повлиять на выбор подхода к решению.
Масштабируемость инструмента реализации. Возможно ли задействовать большее число людей для повышения скорости реализации.
Встроенность в цикл разработки: возможность постепенного уточнения описания компонента с целью перехода к описанию уровня синтезируемой модели.

SystemVerilog и SystemC в основном нацелены на решение последних двух пунктов требований, и практически не адресуют первые три.

Отдельно стоит упомянуть машины состояний. Электронная аппаратура практически вся построена на них, и сложность варьируется от простых машин с парой состояний (есть данные — нет данных) до сложных составных. Большая часть машин состояний не может быть представлена в виде упрощаемого цикла² и выглядит в простейшем случае примерно так:

loop1: action 1; loop2: action 2; if condition then goto loop1; action 3; goto loop2;

Хорошее средство прототипирования позволяет описывать машины состояний просто и безопасно. Чем проще такое описание, тем быстрее можно получить точный прототип компонента, тем выше скорость реализации — первый пункт в перечне выше.

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

Если попытаться посмотреть на функциональные языки с точки зрения инструмента для прототипирования аппаратуры, то выводы будут достаточно интересны:

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

Принимая во внимание цель прототипирования, «синтезируемость» от прототипа не требуется, требуется только потактовая аккуратность — совпадение временных диаграмм с точностью до такта. Это позволяет существенно сократить уровень детальности модели, подняв при этом скорость разработки и моделирования.

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

3 Моделирование аппаратуры с помощью функциональных языков

3.1 Общий подход

Общий подход прост: на основе текущего состояния и текущих входных данных надо рассчитать текущие выходные данные и состояние для следующего такта (k — номер компонента; состояние, входные и выходные сигналы представляют собой кортежи):

(O_ki, I_ki+1) = F_k (I_ki, S_ki)

Получается рекурсивная функция.

Между компонентами практически всегда существует кольцевая зависимость. Её наличие приводит к необходимости упорядочения вычислений выходов на основе входов. Ниже приведён RS-триггер на ИЛИ–НЕ элементах:

RS-триггер — это простое устройство с памятью на элементах логики. При подаче 1 на провод A (вход S, Set) и 0 на провод B (вход R, Reset) мы должны получить 1 на проводе C (выход Q, прямой выход), который останется при сбросе A в 0. И наоборот, при подаче пары 01 на AB мы должны получить на прямом выходе 0, который останется на входе после сброса провода B в 0.

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

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

Одним из вариантов абстрагирования от порядка вычислений является использование ленивых вычислений. Развитие событий во времени можно представить списком событий. Если скрестить эти два приёма, получатся ленивые списки событий [10].

Этот подход не является новым и широко известен как декомпозиция системы на «потоках» (streams). Подход хорошо описан в курсе SICP [11, 7, гл. 3.5] и является старейшим из известных подходов к моделированию состояния в «чистых» функциональных языках.

Ленивые списки могут применяться для обеспечения ввода-вывода⁵. Однако их применение в реальных программах затруднено⁶, поскольку события из внешнего мира могут приходить в произвольном порядке. В случае моделирования аппаратуры порядок фиксирован, и ленивые списки являются самым простым вариантом при использовании языков со ссылками (Lisp, семейство ML, Haskell) или с ленивым порядком вычислений (Clean, Haskell).

3.2 Вариант на языке Haskell

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

runningSum :: [Int] -> [Int] runningSum inputs = sum where sum = 0 : (zipWith (+) sum inputs)

Вот его схема:

Функция zipWith применит первый аргумент — двуместную функцию — к одинаковым по порядку элементам второго и третьего аргументов. (+) — это синоним безымянной функции λx y. x+y. Оператор (:) — это оператор конструирования списков. Слева находится голова списка, справа хвост.

Результат работы приведён ниже:

Prelude> runningSum [0,0,1,0,0,-1,10,0,0,-1] [0,0,0,1,1,1,0,10,10,10,9] Prelude> runningSum [1,0,1,0,0,-1,10,0,0,-1] [0,1,1,2,2,2,1,11,11,11,10]

Сумма поступает на выход с задержкой в один такт. Самый первый элемент всегда 0 — мы сформировали задержку путём добавления 0 в голову списка сумм. Второй элемент — функция от 0 (sum[0]) и inputs[0]. Третий элемент — функция от sum[1] (0+inputs[0]) и inputs[1], и так далее.

Второй пример будет чуть более сложным — RS-триггер на элементах ИЛИ–НЕ. У него два входа и два выхода: вход R (RESET, сброс), вход S (SET, установка) и выходы Q (прямой) и Q’ (инверсный).

nor :: [Bool] -> [Bool] -> [Bool] nor xs ys = False : zipWith nor' xs ys where nor' a b = not (a || b) rsTrigger :: [Bool] -> [Bool] -> ([Bool], [Bool]) rsTrigger r s = (q, q') where q = nor s q' q' = nor r q

Схема создания nor похожа на runningSum: вводим задержку с помощью (False : вычисление), само вычисление сводится к применению чистой функции к входам поэлементно.

rsTrigger уже отличается от предыдущих функций: на входе каждого nor есть выход другого nor. Такое зацикливание без всякого дополнительного программного текста возможно из-за ленивого порядка вычислений: компилятор формирует вычисления, а библиотека времени выполнения сама выстроит их по порядку.

Вот результат работы rsTrigger:

*Main> rsTrigger (replicate 5 False) (replicate 5 False) ([False,True,False,True,False,True] ,[False,True,False,True,False,True]) *Main> rsTrigger (True : replicate 4 False) (replicate 5 False) ([False,True,True,True,True,True] ,[False,False,False,False,False,False]) *Main> rsTrigger (replicate 5 False) (True : replicate 4 False) ([False,False,False,False,False,False] ,[False,True,True,True,True,True])

Самый первый запуск приводит к самовозбуждению схемы. Второй (r активен) приводит к установке q в 0, сбросу. Третий пример показывает работу входа s.

В RS-триггере единицей времени моделирования является задержка на элементе ИЛИ–НЕ. В накапливающем сумматоре единица времени не указана, это такт работы какой-то схемы. В принципе, при моделировании сложной аппаратуры пользуются именно вторым вариантом, в качестве единицы модельного времени берётся один такт всей схемы.

Накапливающий сумматор интересен потому, что в нём текущее состояние и входы определяют значение текущих выходов и следующего состояния. Такая схема весьма распространена, она называется автоматом Мили (Mealy machine). Легко оформив её в отдельный примитив, можно писать только чистые функции преобразования данных.

Вот приблизительный код этой функции ядра с примером применения — реализацией накапливающего сумматора:

mealy :: (state -> input -> (state,output)) -> state -> [input] -> [output] mealy f startState inputs = outputs where (nextStates,outputs) = unzip $ zipWith f states inputs states = startState : nextStates runningSumMealy :: [Int] -> [Int] runningSumMealy = mealy (\sum i -> (sum+i,sum)) 0

Результат работы runningSumMealy:

*Main> runningSumMealy [0,0,1,0,0,-1,10,0,0,-1] [0,0,0,1,1,1,0,10,10,10] *Main> runningSumMealy [0,0,1,0,0,-1,10,0,0,-1,0,0] [0,0,0,1,1,1,0,10,10,10,9,9]

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

3.3 Вариант на языке Erlang

Язык программирования Erlang является строгим, и языковые конструкции, соответствующие «потокам», в нем отсутствуют. Описываемый подход, тем не менее, возможно реализовать на базе очередей сообщений и процессов.

В данном случае каждый блок будет также представлен бесконечно-рекурсивной функцией, работающей в своём процессе. Однако, вместо того, чтобы работать со списками, функция должна принимать и отправлять сообщения. Логику посылки и отправки сообщений возможно выделить в отдельный модуль (как это сделано для модуля gen_server стандартной библиотеки).

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

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

Мы решили использовать Erlang для моделирования аппаратуры из-за его существенно более простого синтаксиса. Опрошенные инженеры сказали, что модели на Erlang воспринимаются ими проще — аргументы функций в скобках более привычны, последовательность операций более прозрачна (к примеру, where в Haskell «параллелен» в том смысле, что можно переставлять определения без изменения семантики).

3.4 Алгебраические типы и полиморфизм

Алгебраические типы при моделировании аппаратуры используются для описания машин состояний и структурирования передаваемой информации. Последнее, вместе с параметрическим полиморфизмом, существенно помогает в работе⁹.

В качестве примера можно привести описание команд микропроцессора.

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

data Cmd = Nop | Load DestReg Reg | Add DestReg Reg Reg

После этапа чтения операндов структура команд не изменится, поменяется только содержимое тех полей, что имели тип Reg.

data ReadCmd = Nop | Load DestReg Word32 | Add DestReg Word32 Word32

Разумно будет параметризовать команды:

data Cmd reg = Nop | Load DestReg reg | Add DestReg reg reg

Ниже приведены два примера: один из plasma [3] (свободно распространяемая реализация ядра MIPS [2] на VHDL), другой из тестовой реализации похожего ядра MIPS на Haskell.

Вот код декодера команд plasma:

entity control is port(opcode : in std_logic_vector(31 downto 0); intr_signal : in std_logic; rs_index : out std_logic_vector(5 downto 0); rt_index : out std_logic_vector(5 downto 0); rd_index : out std_logic_vector(5 downto 0); imm_out : out std_logic_vector(15 downto 0); alu_func : out alu_function_type; shift_func : out shift_function_type; mult_func : out mult_function_type; branch_func : out branch_function_type; a_source_out : out a_source_type; b_source_out : out b_source_type; c_source_out : out c_source_type; pc_source_out: out pc_source_type; mem_source_out:out mem_source_type; exception_out: out std_logic); end; --entity control architecture logic of control is begin control_proc: process(opcode, intr_signal) variable op, func : std_logic_vector(5 downto 0); variable rs, rt, rd : std_logic_vector(5 downto 0); variable rtx : std_logic_vector(4 downto 0); variable imm : std_logic_vector(15 downto 0); variable alu_function : alu_function_type; begin alu_function := ALU_NOTHING; shift_function := SHIFT_NOTHING; mult_function := MULT_NOTHING; a_source := A_FROM_REG_SOURCE; b_source := B_FROM_REG_TARGET; c_source := C_FROM_NULL; pc_source := FROM_INC4; branch_function := BRANCH_EQ; mem_source := MEM_FETCH; op := opcode(31 downto 26); rs := '0' & opcode(25 downto 21); rt := '0' & opcode(20 downto 16); rtx := opcode(20 downto 16); rd := '0' & opcode(15 downto 11); func := opcode(5 downto 0); imm := opcode(15 downto 0); is_syscall := '0'; case op is when "000000" => --SPECIAL case func is when "000000" => --SLL r[rd]=r[rt]\guillemotleft{}re; a_source := A_FROM_IMM10_6; c_source := C_FROM_SHIFT; shift_function := SHIFT_LEFT_UNSIGNED; when "000010" => --SRL r[rd]=u[rt]\guillemotright{}re; a_source := A_FROM_IMM10_6; c_source := C_FROM_shift; shift_function := SHIFT_RIGHT_UNSIGNED; when "011011" => --DIVU s->lo=r[rs]/r[rt]; s->hi=r[rs]%r[rt]; mult_function := MULT_DIVIDE; when "100000" => --ADD r[rd]=r[rs]+r[rt]; c_source := C_FROM_ALU; alu_function := ALU_ADD; when "000001" => --REGIMM rt := "000000"; rd := "011111"; ...

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

Вот код декодера команд на Haskell:

type RI = IntSz FIVE -- register index. data Dest = Dest RI deriving (Eq,Show) data Imm5 = Imm5 (IntSz FIVE) deriving (Eq,Show) data Signed = Signed | Unsigned deriving (Eq,Show) data MIPSCmd reg = Nop | Trap | Add reg reg Dest | And reg reg Dest ... ---- Decoder. mipsDecode :: Word32 -> MIPSCmd (IntSz FIVE) mipsDecode word = cmd where high6 :: IntSz SIX low26 :: IntSz SIZE26 (high6,low26) = castWires word base_rs :: IntSz FIVE rt :: IntSz FIVE offset :: IntSz SIZE16 (base_rs,rt,offset) = castWires low26 cmd = case (high6,base_rs,rt) of (0x00,_,_) -> mipsDecodeSpecial low26 (0x02,_,_) -> J (Imm26 low26) (0x20,_,_) -> LB Signed base_rs (RI rt) (Imm16 offset) (0x01,_,_) -> mipsDecodeRegImm (base_rs,rt,offset) (0x07,_,_) -> BGT base_rs rt (Imm16 offset) (0x06,_,_) -> BLE base_rs rt (Imm16 offset) (0x05,_,_) -> BNE base_rs rt (Imm16 offset) ... mipsDecodeRegImm :: (IntSz FIVE, IntSz FIVE, IntSz SIZE16) -> MIPSCmd (IntSz FIVE) mipsDecodeRegImm (base_rs,rt,offset) = cmd where cmd = case (base_rs,rt) of (0x00,0x11) -> BAL (Imm16 offset) ... mipsDecodeSpecial :: IntSz SIZE26 -> MIPSCmd (IntSz FIVE) mipsDecodeSpecial low26 = cmd where rs, rt,rd, bits5 :: IntSz FIVE specialOp :: IntSz SIX (rs,rt,rd,bits5,specialOp) = castWires low26 cmd = case (rs,rt,rd,bits5,specialOp) of (0,0,0,0,0) -> Nop (rs,rt,rd,0x00,0x21) -> AddU rs rt (RI rd) ...

Все заметные отличия сводятся к возможности более эффективного синтеза описаний компонентов. Именно поэтому данные декодера plasma идут по своим отдельным шинам. Зато при реализации выполнения команды на Haskell мы не перепутаем местами индекс регистра приёмника и одного из операндов. Нам не надо заводить типы ALU_NOTHING, MULT_NOTHING и им подобные, у нас есть тип Maybe. В общем и целом преобразования получаются проще и надёжнее.

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

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

3.5 Потактовая точность

О потактовой точности следует рассказать чуть более подробно. Рассмотрим пример работы конвейера типичного RISC процессора.

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

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

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

4 Результаты применения подхода в жизни

Мы использовали язык Haskell для создания модели современного микропроцессора с системой команд MIPS32 и внеочередным выполнением команд (out-of-order execution), параллельно были созданы модель контроллера памяти и модель динамической памяти. Модели контроллера памяти и самой памяти служили гарантией, что модель нашего микропроцессорного ядра будет работать в условиях, максимально приближенных к реальным — нам было известно, что многие идеи, хорошие на бумаге, показывали плохие результаты при соединении с обычной памятью со всеми её задержками.

Над проектом работала команда из двух программистов и двух инженеров; по паре «инженер с программистом» на модель ядра и на модель инфраструктуры памяти. Инженеры выступали в роли консультантов и контролёров, их время использовалось только частично.

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

Модель системы получилась высоко параметризованной: 14 параметров ядра процессора (размер кэшей и связанных буферов, размер окна предпросмотра, параметры предпросмотра и т. д.) и 9 параметров контроллера памяти (параметры алгоритма и размеры буферов) и самой памяти (пропускная способность).

Общий объём кода модели — 3400 полезных строк кода. Модель ядра микропроцессора — 2100 строк кода.

Модель опровергла некоторые наши первоначальные предположения, основным из которых являлся тезис о возможности (с использованием доступных нашей команде ресурсов) построения микропроцессорного ядра, способного декодировать видео высокого разрешения. После провала прототипа микропроцессора мы решили использовать специализированные аппаратные модули для декодирования видео и сосредоточиться на проблемах, критичных для нашей системы-на-кристалле: видеоконтроллер для телевидения высокой чёткости, декодирование и демультиплексирование потоков цифрового телевидения, DRM¹⁰, интеграционные задачи разного уровня.

Возвращаясь к вопросу о скорости, стоит отметить проведённое нами неформальное сравнение моделей двух, примерно одинаковых по функциональности, устройств. Одна из моделей была написана на SystemC, другая — на Haskell. Модель на языке Haskell показала заметное увеличение скорости моделирования по сравнению с моделью на SystemC, от 2 раз (с включёнными отчётами о работе устройств) до 100 (без отчётов). Причины столь гигантского разрыва кроются во «встроенной» в ленивые языки «оптимизации» — отчёты просто не вычислялись, а расходы на протягивание отложенных вычислений по иерархии компонентов минимальны. Второй причиной является то, что к ленивым спискам были применены методы оптимизации, давно и хорошо известные функциональному сообществу [8].

5 Заключение

Наш опыт говорит о том, что функциональные языки вполне применимы для моделирования цифровых электронных компонентов.

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

Строгая система типов с выводом типов и алгебраическими типами данных позволяет описывать типичные микроэлектронные решения просто и безопасно.

6 Краткий обзор библиотек моделирования
аппаратуры

Lava

Страничка: http://raintown.org/lava/

Самый известный язык описания аппаратуры, встроенный в Haskell. Схема описывается комбинаторами.

Алгебраические типы данных не поддерживаются.

Hydra

Страничка: http://www.dcs.gla.ac.uk/~jtod/Hydra/

Язык описания аппаратуры. Позволяет описывать комбинаторную логику, получать нетлисты¹¹ (результат синтеза).

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

Алгебраические типы данных не поддерживаются.

Hierarchical Sorting Dataflow Machine

Страничка: http://thesz.mskhug.ru/svn/hiersort/ (SVN)

Пример модели аппаратуры с использованием бесконечных списков. Ядро модели находится в подкаталоге core, содержит порядка 25 строк кода и может быть использовано для написания других моделей аппаратуры.

Получение синтезируемого описания модели не предусмотрено.

Алгебраические типы данных поддерживаются.

Другие языки

Для OCaml было создано два языка описания аппаратуры: HDCaml и Confluence. Оба языка больше не поддерживаются, оставшиеся исходные коды можно найти на http://funhdl.org/. Ни в одном из них не было сделано попытки реализовать поддержку ни алгебраических типов данных, ни полиморфизма.

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

[1]: ForSyDe: Formal System Design. Язык описания аппаратуры, встроенный в Хаскель через Template Haskell. Уровнем чуть выше, чем Hydra.
[2]: Mips, microprocessor without interlocked pipeline stages. http://en.wikipedia.org/wiki/MIPS_architecture. Один из самых простых RISC процессоров (и, пожалуй, самый элегантный).
[3]: Plasma - most mips i(tm) opcodes. http://www.opencores.org/project,plasma. Минималистическая реализация ядра MIPS.
[4]: Prelude.interact :: (String -> String) -> IO (). Функция диалога с клиентом, http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html\#v:interact. Один из первых вариантов ввода-вывода для ленивых функциональных языков.
[5]: The Hydra Computer Hardware Description Language. http://www.dcs.gla.ac.uk/~jtod/Hydra/. Высокоуровневый язык описания аппаратуры с использованием Template Haskell.
[6]: The Lava hardware description language. http://raintown.org/lava/. Один из первых языков описания аппаратуры, встроенный в Haskell.
[7]: Harold Abelson and Gerald J. Sussman. Structure and Interpretation of Computer Programs, 2nd Edition. The MIT Press, 1996.
[8]: John Launchbury Andrew Gill and Simon L Peyton Jones. A short cut deforestation. 1993. Преобразования вычислений над ленивыми списками. В частности, устранение промежуточных списков и ненужного выделения памяти.
[9]: Magnus Carlsson and Thomas Hallgren. Fudgets — purely functional processes with applications to graphical user interfaces. 1998. Варианты ввода-вывода для чистых функциональных языков, отличные от монадического подхода и подхода с уникальными типами.
[10]: Byron Cook John Matthews and John Launchbury. Microprocessor specification in hawk. Язык спецификации цифровых электронных схем, встроенный в Хаскель.
[11]: Харольд Абельсон and Джеральд Джей Сассман. Структура и интерпретация компьютерных программ. М.: Добросвет, 2006.

1: Например, кодирование видео. Разница между требуемой пропускной способностью подсистемы памяти для видео-потоков телевидения высокой и стандартной чёткости составляет >13 раз, тогда как разница в общем объёме данных не более 5 раз (1920*1080/(720*576)=5).
2: Неупрощаемый цикл определяется как цикл с несколькими точками входа.
3: Современными их аналогами, конечно же.
4: Lava [6], Hydra [5] и ForSyDe [1] позволяют надеяться на то, что ситуация изменится в ближайшем будущем.
5: В библиотеке языка Haskell этот атавизм можно наблюдать до сих пор [4].
6: Интересное обсуждение связанных с этим проблем содержится в [9].
7: Количество выходных элементов равно количеству входных из-за применения zipWith.
8: First class value — сущность, для которой доступны любые операции языка.
9: Это справедливо и для динамически типизированных языков, таких как Erlang, тем более, что полиморфизм типов данных в Erlang практически ничем не ограничен.
10: Digital Rights Management, защита видео- и аудиоинформации.
11: Netlist — очень подробный уровень описания аппаратуры, представляет из себя просто список компонентов с соединяющими их проводами.

Этот документ был получен из L^AT_EX при помощи H^EV^EA

Практика функционального программирования