Функциональные языки, как правило, не слишком подходят для низкоуровнеого программирования, хотя и применяются для кодогенерации. Но если спуститься еще ниже, на уровень аппаратуры, то неожиданно ФП оказывается очень кстати. Ведь блок комбитаторной логики не что иное, как функция из величин входящих сигналов в величины исходящих, а для последовательной логики достаточно добавить в параметры и результат старое и новое состояние.
Когда я только изучил 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]Строки в 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]zip выражается через zipWith
zip = zipWith (,)
zip3 и zipWith3 работают аналогично, но для трех списков.
scanl применяет функцию к каждому элементу списка «с накоплением». Его тип (сигнатура) описывается так:
scanl :: (b -> a -> b) -> b -> [a] -> [b]Первый аргумент scanl — функция от двух аргументов, второй — начальное значение аккумулятора, третий — входной список.
scanl (+) 0 [1,2,3,4]($) — постфиксная запись применения функции к аргументу.
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 создает узел по двум этим функциям и начальному состоянию.
// 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 за организация издания учебника «Цифровая схемотехника и архитектура компьютера», который я сейчас читаю, и который сподвиг меня на написание этой статьи.
Комментарии (19)
Labunsky
09.12.2016 22:30+6Так вот как оно начиналось
burjui
10.12.2016 02:16+1Не-а, там под винду на C пишут
Khort
09.12.2016 23:01+3Если говорить о тенденциях, то на мой взгляд сейчас куда перспективнее изучать Chisel/Scala, поскольку на нем написан новый опен-сорс процессор RISC-V. Беркли достаточно авторитетны, чтобы продвинуть этот новый HDL в массы. Впрочем, пока коммерческие тулы Synopsys и Cadence не начнут новый язык поддерживать, все это не серьезно.
Daffodil
10.12.2016 01:51Читаю сейчас книгу про Scala и параллельно играюсь с Chisel, но пока не понял чем же он хорош — очень всё низкоуровневое. Можете рассказать чем Chisel лучше чем VHDL/Verilog?
Khort
10.12.2016 09:53Своего мнения у меня не сложилось пока, к сожалению. Но вот ответ на Ваш вопрос от разработчика RISC-V https://www.quora.com/What-exactly-is-the-point-of-developing-RISC-V-based-CPUs-in-Chisel-rather-than-Verilog-or-VHDL-What-are-the-pros-and-cons
potan
10.12.2016 12:38+1Scala сейчас основной мой рабочий инструмент :-). Но посмотреть на Chisel я пока не успел. Надо восполнить этот пробел.
Но все равно я думаю, что Haskell сильно проще чем Scala и переход на него пойдет легче.Khort
11.12.2016 10:17+1У меня есть только 16 лет опыта кодинга на верилоге (из HDL языков), но сложилось следующее мнение: чтобы писать качественный, синтезируемый код на верилоге, используется всего несколько унифицированных конструкций. При этом возможности (и косяки) языка раскрываются только при написании тестбенчей. Из чего следует, что имея хороший транслятор в верилог, можно действительно писать на чем угодно. Но! транслятор должен быть действительно хороший, поскольку есть нюансы, связанные с F-End тулами: должна определенным образом транслироваться стейт машина, определенным образом транслироваться описание триггера, защелки, и т.д. Так же возникают вопросы по поводу автоматической трансляции параметризованных верилог-модулей. Итого, вопрос только в совершенстве транслятора языка.
potan
12.12.2016 13:20Транслятор вполне может учитывать особенности и генерировать только эффективно синтезируемое подмножество. По моему, всю параметризацию Clash раскрывает на этапе компиляции. Но я очень мало работал с HDL, что бы проверить качество создаваемого кода.
Daffodil
10.12.2016 02:10Основная проблема функциональных HDL языков в том что большинство программистов имеют опыт работы с императивными языками программирования, но не знают как писать программы в функциональном стиле. Человеку с опытом программирования на Си или Java гораздо проще объяснить Verilog чем Clash.
OlegYch_real
10.12.2016 12:01+3когда в универе изучали vhdl было ощущение что императивные привычки только мешают
Daffodil
10.12.2016 21:14Да мешают. Мои студенты тоже писали совершенно безумные с точки зрения аппаратуры вещи, например видел сортировку пузырьком в комбинационном процессе :) Но процессы в Verilog, VHDL, SystemC описываются в императивном стиле.
Если посмотреть на моделирование тестового окружения, оно вполне огранично ложится на императивный стиль.
yuklimov
10.12.2016 12:01+3Интересно! А типизация распространяется только на комбинационные сигналы? Нельзя ли связать типом значения сигнала на разных тактах? Например, можно ли описать сигнал похожий на Either A B, но что не просто приходит сигнал типа A или B, а в более жестком смысле, что данные типов A и B чередуются во времени: A, B, A, B, ...?
Мне часто приходится передавать данные «размазанные» по времени и хочется уметь описывать каком-то образом их типы, чтобы компилятор проверял, правильно ли такие данные генерируются и потребляются.potan
10.12.2016 12:35+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
vba
12.12.2016 14:52Минуточку, мне всегда казалось что данная ниша была за Си только благодаря ручному контролю за использованием памяти. Но ведь если в данной сфере переходить на функциональные языки то этот контроль будет потерян. Или тут все дело в хитрой транслитерации с <Мой-любимый-фя> на Си код? Поясните пожалуйста данный момент. Спасибо.
potan
12.12.2016 16:55+1За C ниша встраиваемого ПО. И то ее уже начинают теснить Rust и кодогенерация через Ivory.
Я про нишу еще более низкого уровня — hardware description languages (языки описания аппаратуры). Здесь тотально доминируют специализированные HDL — Verilog, Systemverilog и VHDL. Используют так же встроенный в C++ DSL (SystemC), но на мой взгляд он еще менее удобен.
Я описываю подмножество Haskell, которое может транслироваться в работу на фиксированной памяти — сигналы и регистры. И показываю, как оно может транслироваться в синхронную аппаратуру. При этом полноценнфй Haskell остается возможерсть использовать на этапах кодогенетации, тестирования и, возможно, верификации (в Clash я про это ни чего не нашел, но выдел упоренание интеграции с солверами в Lava).
YuriPanchul
Ценная тема кстати, давно собирался изучить Haskell именно для исследования такой возможности