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

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

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

    Similar posts

    Comments 19

      +1
      Ценная тема кстати, давно собирался изучить Haskell именно для исследования такой возможности
        +6
        Так вот как оно начиналось
        image
          +1
          Не-а, там под винду на C пишут

          +3
          Если говорить о тенденциях, то на мой взгляд сейчас куда перспективнее изучать Chisel/Scala, поскольку на нем написан новый опен-сорс процессор RISC-V. Беркли достаточно авторитетны, чтобы продвинуть этот новый HDL в массы. Впрочем, пока коммерческие тулы Synopsys и Cadence не начнут новый язык поддерживать, все это не серьезно.
            0
            Читаю сейчас книгу про Scala и параллельно играюсь с Chisel, но пока не понял чем же он хорош — очень всё низкоуровневое. Можете рассказать чем Chisel лучше чем VHDL/Verilog?
            +1
            Scala сейчас основной мой рабочий инструмент :-). Но посмотреть на Chisel я пока не успел. Надо восполнить этот пробел.
            Но все равно я думаю, что Haskell сильно проще чем Scala и переход на него пойдет легче.
              +1
              У меня есть только 16 лет опыта кодинга на верилоге (из HDL языков), но сложилось следующее мнение: чтобы писать качественный, синтезируемый код на верилоге, используется всего несколько унифицированных конструкций. При этом возможности (и косяки) языка раскрываются только при написании тестбенчей. Из чего следует, что имея хороший транслятор в верилог, можно действительно писать на чем угодно. Но! транслятор должен быть действительно хороший, поскольку есть нюансы, связанные с F-End тулами: должна определенным образом транслироваться стейт машина, определенным образом транслироваться описание триггера, защелки, и т.д. Так же возникают вопросы по поводу автоматической трансляции параметризованных верилог-модулей. Итого, вопрос только в совершенстве транслятора языка.
                0
                Транслятор вполне может учитывать особенности и генерировать только эффективно синтезируемое подмножество. По моему, всю параметризацию Clash раскрывает на этапе компиляции. Но я очень мало работал с HDL, что бы проверить качество создаваемого кода.
            0
            Основная проблема функциональных HDL языков в том что большинство программистов имеют опыт работы с императивными языками программирования, но не знают как писать программы в функциональном стиле. Человеку с опытом программирования на Си или Java гораздо проще объяснить Verilog чем Clash.
              +3
              когда в универе изучали vhdl было ощущение что императивные привычки только мешают
                0
                Да мешают. Мои студенты тоже писали совершенно безумные с точки зрения аппаратуры вещи, например видел сортировку пузырьком в комбинационном процессе :) Но процессы в Verilog, VHDL, SystemC описываются в императивном стиле.
                Если посмотреть на моделирование тестового окружения, оно вполне огранично ложится на императивный стиль.
                  0
                  По моему, это повод учить студентов функциональному стилю.
              +2
              bluespec относительно используемый промышленный язык, основанный на haskell. На нем, например, написана BERI — реализация MIPS архитектуры, и ее расширение CHERI.
                0
                У вас ссылки битые (отсутствует ":" после http), лучше проверять перед постингом. Правильные:
                bluespec
                BERI
                +3
                Интересно! А типизация распространяется только на комбинационные сигналы? Нельзя ли связать типом значения сигнала на разных тактах? Например, можно ли описать сигнал похожий на Either A B, но что не просто приходит сигнал типа A или B, а в более жестком смысле, что данные типов A и B чередуются во времени: A, B, A, B, ...?

                Мне часто приходится передавать данные «размазанные» по времени и хочется уметь описывать каком-то образом их типы, чтобы компилятор проверял, правильно ли такие данные генерируются и потребляются.
                  +1
                  Да, типизация всегда была сильной стороной Haskell.
                  etest ::  Either Bool (Bool,Bool) -> Bool -> ((Either Bool (Bool,Bool)), Bool)
                  etest (Left a) b = ((Right (a,b)), a)
                  etest (Right (x,y)) b = ((Left b),(x `xor` y))
                  
                  topEntity = mealy etest (Left True)
                  

                  компилируется в
                  systemverilog
                  // Automatically generated SystemVerilog-2005
                  module E_mealy(w2
                                ,// clock
                                system1000
                                ,// asynchronous reset: active low
                                system1000_rstn
                                ,result);
                    input logic [0:0] w2;
                    input logic system1000;
                    input logic system1000_rstn;
                    output logic [0:0] result;
                    logic [0:0] y;
                    E_types::Tup2 result_0;
                    logic [2:0] x;
                    logic [2:0] x_app_arg;
                    logic [2:0] x_0;
                    assign result = y;
                    
                    assign y = result_0.Tup2_sel1;
                    
                    E_etest E_etest_result_0
                    (.result (result_0)
                    ,.ds (x)
                    ,.b (w2));
                    
                    // register begin
                    logic [2:0] dout;
                    
                    always_ff @(posedge system1000 or negedge system1000_rstn) begin : E_mealy_register
                      if (~ system1000_rstn) begin
                        dout <= {1'b0,1'b1,1'b0};
                      end else begin
                        dout <= x_app_arg;
                      end
                    end
                    
                    assign x = dout;
                    // register end
                    
                    assign x_app_arg = x_0;
                    
                    assign x_0 = result_0.Tup2_sel0;
                  endmodule
                  0

                  Минуточку, мне всегда казалось что данная ниша была за Си только благодаря ручному контролю за использованием памяти. Но ведь если в данной сфере переходить на функциональные языки то этот контроль будет потерян. Или тут все дело в хитрой транслитерации с <Мой-любимый-фя> на Си код? Поясните пожалуйста данный момент. Спасибо.

                    +1
                    За C ниша встраиваемого ПО. И то ее уже начинают теснить Rust и кодогенерация через Ivory.
                    Я про нишу еще более низкого уровня — hardware description languages (языки описания аппаратуры). Здесь тотально доминируют специализированные HDL — Verilog, Systemverilog и VHDL. Используют так же встроенный в C++ DSL (SystemC), но на мой взгляд он еще менее удобен.
                    Я описываю подмножество Haskell, которое может транслироваться в работу на фиксированной памяти — сигналы и регистры. И показываю, как оно может транслироваться в синхронную аппаратуру. При этом полноценнфй Haskell остается возможерсть использовать на этапах кодогенетации, тестирования и, возможно, верификации (в Clash я про это ни чего не нашел, но выдел упоренание интеграции с солверами в Lava).

                  Only users with full accounts can post comments. Log in, please.