Pull to refresh

Функциональные языки в разработке аппаратуры

Reading time 8 min
Views 14K
Функциональные языки, как правило, не слишком подходят для низкоуровнеого программирования, хотя и применяются для кодогенерации.

Примеры проектов
генерация безопасного кода на C (используется в лаборатории Касперского) Ivory, поддержка реактивного программирования на Arduino, и так далее Atom, Ion

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

Когда я только изучил Haskell, я присоединился к одной бурной дискуссии «на чем лучше моделировать RS-триггер». Я сразу заметил, что свежеизученный мной язык решает все всплывающие в этой дискуссии проблемы.

Моделирование предполагает наблюдение за эволюцией состояния модели во времени, но в Haskell как такового изменяемого состояния нет. За то есть ленивые списки, которые превращаются в «горизонтальное время».

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

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

delay s = 0:s

Или так
delay = 0:


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

data Signal v = S v (Signal v)
delay v s = S v s

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


RS-триггер представляет из себя два NOR-узла, соединенные взаимно-рекурсивно. У этой системы есть два стабильных состояния, в которых на выходе одного NOR единица, а другого — ноль. Подавая единицу на второй вход одного из NOR-узлов можно переключать состояния.

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

nor '_' '_' = '~'
nor _ _ = '_'

rs r s = (q, nq)
  where 
    q = '_' : zipWith nor r nq
    nq = '_' : zipWith nor q s

main = let
   r = "~_______"
   s = "___~~___"
   (q,nq) = rs r s
  in do
      print r
      print s
      print q
      print nq

Краткий справочник по Haskell
Имена переменных (точнее констант, так как они в пределе области видимости не могут меняться) и функций начинается с маленькой буквы и состоит из алфовитно-цифровых символов или состоит из спецсимволов и не начинается с ':'.

С большой буквы (или с ':') начинаются имена типов, конструкторов (можно считать, что это имена констант в перечислениях) и имена модулей.

(:) — конструктор списка. Создает новый список, добавляя к старому в начало один элемент.
0 : [1,2,3,4,5]
эквивалентно [0,1,2,3,4,5]
Строки в Haskell представляются как список символов. «1234» означает то же самое, что и ['1','2','3','4']

zip — превращает два списка в список пар.

zip [1,2,3,4] "1234"
буден равно
[(1,'1'),(2,'2'),(3,'3'),(4,'4')]


zipWith применяет функцию к элементам из двух списков

zipWith (+) [1,2,3,4] [1,3,5,7]
вычислит поэлементную сумму списков [2,5,8,11]
zip выражается через zipWith
zip = zipWith (,)


zip3 и zipWith3 работают аналогично, но для трех списков.

scanl применяет функцию к каждому элементу списка «с накоплением». Его тип (сигнатура) описывается так:
scanl :: (b -> a -> b) -> b -> [a] -> [b]

Первый аргумент scanl — функция от двух аргументов, второй — начальное значение аккумулятора, третий — входной список.
scanl (+) 0 [1,2,3,4]
вычислит список частичных сумм: [0,1,3,6,10]

($) — постфиксная запись применения функции к аргументу.
f $ x = f x

Часто применяется что бы писать меньше скобок:
f x $ g y эквивалентно f x (g y)

Запись \x y -> f y x означает анонимную функцию (еще называемую замыканием) с параметрами x и y.

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

fmap — «поднимает» функцию от отдельной величины до функции над целым контейнером. Контейнер должен быть функтором, но почти все им является. В частности такими контейнерами являются сигналы, хранящие значения для каждого момента времени. Так же такими контейнерами являются списки, хотя для них, по историческим причинам, есть специальная функция «map» с той же функциональностью.
liftA — то же самое, что fmap, но для аппликативных функторов (о чем свидетельствует буква 'A' в названии). Сигналы так же являются аппликативными функторами, а со списками все сложнее. Формально списки тоже аппликативные функторы и liftA с ними работает ожидаемым образом. Но liftA2 и liftA3 ведут себя неожиданно, но это тема для отдельной статьи.

liftA2 и liftA3 «поднимают» функции от двух и трех аргументов до функций от контейнеров. Они будут работать с сигналами, а для списков лучше использовать zipWith и zipWith3.

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

macD r x y = acc
  where
    prods = zipWith (*) x y
    sums = zipWith (+) acc prods
    acc = 0 : zipWith (\r v -> if r == 1 then 0 else v) r sums

macS r x y = scanl macA 0 $ zip3 r x y
  where
   macA acc (r,x,y) = if r == 1 then 0 else acc+x*y

Здесь описаны две эквивалентные модели операции MAC (умножение со сложением) с аккумулятором. macD — с использованием рекурсивного сигнала с задержкой, macS — с использованием явно описанного состояния.

Если подмножество Haskell так хорошо моделирует синхронную аппаратуру, то почему бы из него не синтезировать HDL? Есть несколько проектов расширения компилятора, которое позволяет это делать: коммерческий Bluespec, свободные Lava и CλaSH.

Clash


В качестве примера я хочу рассмотреть Clash, так как он умеет компилировать и в VHDL, и в SystemVerilog, и в старый добрый Verilog (который меня привлекает тем, что используется не только в микроэлектронике :)

Процесс инсталляции достаточно подробно описан на сайте. К нему стоит отнестись внимательно — во первых заявлена совместимость с ghc-7.x (то есть с 8.x может не работать), во вторых не надо пробовать запускать «cabal install clash» — это устаревший пакет, надо устанавливать clash-ghc («cabal install clash-ghc --enable-documentation»).

Исполняемый файл clash (или clash.exe, в зависимости от OS) будет установлен в директорию "~/.cabal/bin", лучше добавить ее в $PATH.

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

Например, рассмотрим однобитный сумматор:

topEntity :: Signal (Bool, Bool) -> Signal (Bool, Bool)
topEntity s = fmap (\(s1,s2) -> (s1 .&. s2, s1 `xor` s2)) s

Весь файл
module ADD1 where

import CLaSH.Prelude

topEntity :: Signal (Bool, Bool) -> Signal (Bool, Bool)
topEntity = fmap (\(s1,s2) -> (s1 .&. s2, s1 `xor` s2))

fmap превращает функцию от пары логических величин в функцию от сигнала. Откомпилировать файл в verilog можно командой «clash --verilog ADD1.hs»

Результат
// Automatically generated Verilog-2001
module ADD1_topEntity_0(a1
                       ,result);
  input [1:0] a1;
  output [1:0] result;
  wire [0:0] app_arg;
  wire [0:0] case_alt;
  wire [0:0] app_arg_0;
  wire [1:0] case_alt_0;
  wire [0:0] s1;
  wire [0:0] s2;
  assign app_arg = s1 & s2;

  reg [0:0] case_alt_reg;
  always @(*) begin
    if(s2)
      case_alt_reg = 1'b0;
    else
      case_alt_reg = 1'b1;
  end
  assign case_alt = case_alt_reg;

  reg [0:0] app_arg_0_reg;
  always @(*) begin
    if(s1)
      app_arg_0_reg = case_alt;
    else
      app_arg_0_reg = s2;
  end
  assign app_arg_0 = app_arg_0_reg;

  assign case_alt_0 = {app_arg
                      ,app_arg_0};

  assign s1 = a1[1:1];

  assign s2 = a1[0:0];

  assign result = case_alt_0;
endmodule

Для работы с состоянием можно использовать автоматы Мура и Мили. Рассмотрим делитель частоты, сначала с помощью автомата Мура.

data DIV3S = S0 | S1 | S2

div3st S0 _ = S1
div3st S1 _ = S2
div3st S2 _ = S0

div3out S2 = True
div3out _ = False

topEntity :: Signal Bool -> Signal Bool
topEntity = moore div3st div3out S0

data — это конструкция Haskell описывающая тип данных. В этой программе мы описываем тип DIV3S представляющего состояние нашего автомата. Возможные значения этого типа перечислены через '|' — S0, S1 и S3.
div3st — функция состояния (символом "_" принято называть неиспользуемый параметр, в данном случае значение входного сигнала).
div3out — функция из состояние в величину выходного сигнала.

Библиотечная функция moore создает узел по двум этим функциям и начальному состоянию.

Выходной systemverilog
// Automatically generated SystemVerilog-2005
module DIV3Moore_moore(w3
                      ,// clock
                      system1000
                      ,// asynchronous reset: active low
                      system1000_rstn
                      ,result);
  input logic [0:0] w3;
  input logic system1000;
  input logic system1000_rstn;
  output logic [0:0] result;
  logic [1:0] s1_app_arg;
  logic [1:0] s1;
  always_comb begin
    case(s1)
      2'b00 : s1_app_arg = 2'd1;
      2'b01 : s1_app_arg = 2'd2;
      default : s1_app_arg = 2'd0;
    endcase
  end

  // register begin
  logic [1:0] dout;

  always_ff @(posedge system1000 or negedge system1000_rstn) begin : DIV3Moore_moore_register
    if (~ system1000_rstn) begin
      dout <= 2'd0;
    end else begin
      dout <= s1_app_arg;
    end
  end

  assign s1 = dout;
  // register end

  always_comb begin
    case(s1)
      2'b10 : result = 1'b1;
      default : result = 1'b0;
    endcase
  end
endmodule

То же самое с автоматом Мили:

data DIV3S = S0 | S1 | S2

div3 S0 _ = (S1, False)
div3 S1 _ = (S2, False)
div3 S2 _ = (S0, True)

topEntity :: Signal Bool -> Signal Bool
topEntity = mealy div3 S0

Выходной VHDL
-- Automatically generated VHDL-93
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;
use IEEE.MATH_REAL.ALL;
use std.textio.all;
use work.all;
use work.div3mealy_types.all;

entity div3mealy_mealy is
  port(w2              : in boolean;
       -- clock
       system1000      : in std_logic;
       -- asynchronous reset: active low
       system1000_rstn : in std_logic;
       result          : out boolean);
end;

architecture structural of div3mealy_mealy is
  signal y         : boolean;
  signal result_0  : div3mealy_types.tup2;
  signal x         : unsigned(1 downto 0);
  signal x_app_arg : unsigned(1 downto 0);
  signal x_0       : unsigned(1 downto 0);
begin
  result <= y;

  y <= result_0.tup2_sel1;

  with (x) select
    result_0 <= (tup2_sel0 => to_unsigned(1
                                         ,2)
                ,tup2_sel1 => false) when "00",
                (tup2_sel0 => to_unsigned(2,2)
                ,tup2_sel1 => false) when "01",
                (tup2_sel0 => to_unsigned(0,2)
                ,tup2_sel1 => true) when others;

  -- register begin
  div3mealy_mealy_register : process(system1000,system1000_rstn)
  begin
    if system1000_rstn = '0' then
      x <= to_unsigned(0,2);
    elsif rising_edge(system1000) then
      x <= x_app_arg;
    end if;
  end process;
  -- register end

  x_app_arg <= x_0;

  x_0 <= result_0.tup2_sel0;
end;

В Clash вместо списков используются вектора фиксированного размера и большинство библиотечных функций переопределено на работу с ними. Добраться до стандартных списковых функций можно добавив в файл (или выполнив в REPL) строчку import qualified Data.List as L. После этого можно использовать функции, явно указав префикс «L.». Например

*DIV3Mealy L> L.scanl (+) 0 [1,2,3,4]
[0,1,3,6,10]

С векторами работают большинство привычных списковых функций.

*DIV3Mealy L> scanl (+) 0 (1 :> 2 :> 3 :> 4 :> Nil)
<0,1,3,6,10>
*DIV3Mealy L> scanl (+) 0 $(v [1,2,3,4])
<0,1,3,6,10>

Но там много тонкостей, за подробностями стоит обратиться к документации.

Руководство с примерами можно посмотреть здесь.

На сайте есть примеры проектов на Clash, в частности реализация процессора 6502.

Перспективы


Haskell очень мощный язык, и его возможно использовать для разработки DSL, например для разработки программного интерфейса устройства (с генерацией, кроме HDL, еще и через Ivory драйверов и эмуляторов для систем виртуализации), или описания архитектуры и микроархитектуры (с генерацией LLVM backend, оптимизирующий для данной микроархитектуры).

Пользуясь случаем, выражаю благодарность yuripanchul за организация издания учебника «Цифровая схемотехника и архитектура компьютера», который я сейчас читаю, и который сподвиг меня на написание этой статьи.
Tags:
Hubs:
+37
Comments 20
Comments Comments 20

Articles