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

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

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

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

0 : [1,2,3,4,5]

zip [1,2,3,4] "1234"

[(1,'1'),(2,'2'),(3,'3'),(4,'4')]

zipWith (+) [1,2,3,4] [1,3,5,7]

zip = zipWith (,)

scanl :: (b -> a -> b) -> b -> [a] -> [b]

scanl (+) 0 [1,2,3,4]

f $ x = f x

Такой подход позволяет сравнительно легко моделировать на уровне 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 создает узел по двум этим функциям и начальному состоянию.

// 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

-- 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 за организация издания учебника «Цифровая схемотехника и архитектура компьютера», который я сейчас читаю, и который сподвиг меня на написание этой статьи.

Автор: potan

Источник