使用 Haskell Clash 在 FPGA 上解决 Advent of Code

# 用 Haskell RetroClash 在 FPGA 上解决 Advent Of Code 源码：https://midirus.com/blog/advent-of-fpga 本文展示了我如何使用 Clash（https://clash-lang.org/）在 FPGA（现场可编程门阵列）芯片上解决 Advent Of Code（AOC（https://adventofcode.com/））第四天的问题：logo - 首先，我会介绍使用 Clash 进行硬件设计的细节。 - 接下来，我会演示三个逐步改进的设计，来解决最初的几个问题。 - 最后，我会展示如何在真实硬件上计算结果。 diagram 这篇文章包含许多面向 Haskell 程序员的代码片段，完整源码可以在我的 advent-of-clash（https://codeberg.org/TristanCacqueray/advent-of-clash）仓库中找到。要更深入地了解其工作原理，我强烈推荐 Retrocomputing with Clash（https://unsafeperform.io/retroclash/）这本书。 我邀请您通过启动一个 REPL 来跟进这篇文章，如下所示： `` $ git clone https://codeberg.org/TristanCacqueray/advent-of-clash $ cd advent-of-clash $ nix run git+https://codeberg.org/TristanCacqueray/clash-osc#ghci λ> import Clash.Prelude λ> :load AdventOfClash.Utils [1 of 1] Compiling AdventOfClash.Utils ( AdventOfClash/Utils.hs, interpreted ) Ok, one module loaded. λ> showDigit 7 0b0011_0111 `` ## 引言 https://midirus.com/blog/advent-of-fpga.html#introduction FPGA 是一种数字电路，可以使用硬件描述语言（HDL）在非常低的层次进行编程。Clash 是一种函数式 HDL，它可以将用 Haskell 编写的高级设计编译为低层次的可综合 HDL，例如 Verilog。 AOC 是一个由小型编程谜题组成的降临历，每个谜题包含一个问题描述、一个文本输入和期望输出。AOC 一直是我学习新编程语言的好方法，因为这些谜题会逐步引入语言中的新概念。 第四天的问题涉及处理一个类似于单规则生命游戏的网格。这是一个有趣的挑战，因为我对 Clash 只有肤浅的理解。解决这个谜题促使我实现自己的 RAM 机器，这是我以前从未接触过的基本构建模块。 ## Clash 前奏库 https://midirus.com/blog/advent-of-fpga.html#clash-prelude 在深入 FPGA 设计之前，本节介绍 Clash 的标准库，名为 clash-prelude（https://hackage.haskell.org/package/clash-prelude）。它提供了专门为创建设计而设计的备选数据类型和 API。这是必要的，因为 Haskell 标准库提供的核心数据类型并不适合 HDL 综合。 ### KnownNat https://midirus.com/blog/advent-of-fpga.html#knownnat Clash 的大部分 API 依赖 `KnownNat` 约束来表达静态大小。它们是类型级别的自然数，其值包含在类型中。这种编译期大小信息对 FPGA 很重要，因为在综合之前，集成电路（IC）必须以精确的位宽线缆互连。这要求启用 Haskell 语言扩展 `DataKinds`，才能在类型级别使用项级值。 因此，Clash 使用在 Clash.Promoted.Nat（https://hackage-content.haskell.org/package/clash-prelude-1.8.4/docs/Clash-Promoted-Nat.html）中定义的单例类型来表示类型级别的自然数，其构造器如下： `` SNat :: KnownNat n => SNat n `` ... 可以像这样创建： `` -- 41 是一个类型级别的 KnownNat 值。 myNat :: SNat 41 myNat = SNat -- 21 也是一个 KnownNat，以内联类型应用声明。 twentyOne = SNat @21 `` SNat 可以用于进行类型级别的计算，例如： `` -- 来自 Clash.Promoted.Nat: succSNat :: SNat a -> SNat (a + 1) mulSNat :: SNat a -> SNat b -> SNat (a * b) `` 这些类型定义相当特殊，因为它们包含类型级别的运算，如 `a + 1` 或 `a * b`。SNat 的值在编译时已知，例如通过推断最终类型： `` λ> :t succSNat myNat succSNat myNat :: SNat 42 λ> :t mulSNat twentyOne (SNat @2) mulSNat twentyOne (SNat @2) :: SNat 42 `` 为了提高 KnownNat 的易用性，Clash 提供了自定义编译器插件，以便在高级用法中解决约束。REPL 必须这样设置： `` ghci -XDataKinds -fplugin GHC.TypeLits.KnownNat.Solver -fplugin GHC.TypeLits.Normalise -fplugin GHC.TypeLits.Extra.Solver `` 像 SNat 这样的单例类型花了我一点时间来习惯，尽管在实践中它们并不太复杂。这个 Unfolder 第 50 集（https://www.youtube.com/watch?v=-zxxl-WuwuE）提供了关于它们如何工作以及为何必要的扎实解释。 ### BitPack 约束 https://midirus.com/blog/advent-of-fpga.html#bitpack-constraint 得益于 `KnownNat`，Clash 前奏库提供了固定大小的数据类型，可以在位级别高效表示。 #### 有大小整数 https://midirus.com/blog/advent-of-fpga.html#sized-integers Clash 提供了自己的数据类型来表示固定大小的整数： - `Unsigned n` 类似于 `Word`。 - `Signed n` 类似于 `Int`。 例如，`Signed 64` 等价于 `Int64`，或者 `Unsigned 8` 就像 `Word8`。 这些数据类型带有方便的 `bitCoerce` 和 `resize` 函数，用于在表示之间转换： `` resizeDemo :: Signed 8 -> Signed 16 resizeDemo = resize bitCoerceDemo :: Signed 8 -> Unsigned 8 bitCoerceDemo = bitCoerce bitResizeDemo :: Signed 8 -> Unsigned 16 bitResizeDemo = resize . bitCoerce `` 这些新数据类型功能强大，因为它们允许定义任意大小的数字，不必限于 2 的倍数。例如，这里是用 13 位可以表示的最大数字： `` λ> maxBound :: Unsigned 13 8191 `` 这些新数据类型在硬件设计中至关重要，因为它们允许您使用恰好正确的位数（例如 13 位而不是 16 位），以匹配 IC 之间的线缆数量（例如 13 位就是 13 根物理线）。与原始位操作不同，BitPack 约束提供了类型安全性，以防止会导致综合错误的宽度不匹配。 Clash 还提供了 `Index n` 类型，用于从 0 到 *n* 的值。它们对于可计数的事物很有用，例如向量位置，或者接下来的章节中展示的数字。 #### 有大小向量 https://midirus.com/blog/advent-of-fpga.html#sized-vectors 在使用 Clash 时，Haskell 的列表并不合适，因为它们的大小可以是无界的。相反，Clash 规定使用以下向量类型： `` -- 来自 Clash.Sized.Vector: data Vec :: Nat -> Type -> Type where Nil :: Vec 0 a Cons :: a -> Vec n a -> Vec (n + 1) a pattern (:>) :: a -> Vec n a -> Vec (n + 1) a `` 如您所见，空向量 `Nil` 的类型级别大小为 0，添加一个元素会将其大小增加 1。例如，创建向量如下所示： `` λ> myVec = 4 :> 2 :> Nil λ> :t myVec myVec :: Vec 2 Int `` 注意推断如何在类型级别自动跟踪元素数量。要初始化一个向量，可以使用 `repeat` 函数： `` repeat :: KnownNat n => a -> Vec n a `` 以下是一些来自 Clash.Sized.Vector（https://hackage-content.haskell.org/package/clash-prelude/docs/Clash-Sized-Vector.html）模块的示例： `` head :: Vec (n + 1) a -> a (++) :: Vec n a -> Vec m a -> Vec (n + m) a zip :: Vec n a -> Vec n b -> Vec n (a, b) `` Vec API 在操作值列表时提供了强大的类型安全性，例如： - `head` 确保向量至少有一个元素。 - `++` 返回一个连接后的向量，其长度是参数长度之和。 - `zip` 只能处理长度相同的向量。 下面是当向量长度不匹配时编译错误的示例： `` λ> zip (4 :> 2 :> Nil) (1 :> Nil) :5:20: error: [GHC-83865] • Couldn't match type ‘1’ with ‘2’ Expected: Vec 2 a Actual: Vec 1 a • In the second argument of ‘zip’, namely ‘(1 :> Nil)’ `` #### BitVector https://midirus.com/blog/advent-of-fpga.html#bitvector Clash 提供了一种自定义数据类型来表示原始位，称为 `BitVector n`，类似于 `ByteString`： `` -- 来自 Clash.Class.BitPack: pack :: BitPack a => a -> BitVector (BitSize a) unpack :: BitPack a => BitVector (BitSize a) -> a `` 可以这样使用： `` λ> pack (7 :: Index 10) 0b0111 λ> resize @BitVector @_ @8 $ pack 'A' 0b0100_0001 `` 这里有一些将 ASCII Char 转换的辅助函数示例： `` -- 来自 AdventOfClash.Utils: type Byte = BitVector 8 -- 将 Unicode 截断为 ASCII 字节: charPack :: Char -> BitVector 8 charPack = resize @BitVector @21 @8 . pack -- 将 ASCII 扩展为完整的 Haskell 字符大小 charUnpack :: BitVector 8 -> Char charUnpack = unpack . resize @BitVector @8 @21 `` ### 二进制编码十进制 https://midirus.com/blog/advent-of-fpga.html#binary-coded-decimal 二进制编码十进制（BCD）是一种特殊的十进制数字编码，在处理十进制数字时可能比常规整数更高效。BCD 对于输出 AOC 的解决方案很有用，因为它们由十进制数字组成。 使用 Clash，可以这样定义 BCD： `` type Digit = Index 10 type BCD n = Vec n Digit `` 要确定给定整数的 BCD 表示长度，可以使用以下类型级别函数： `` -- 来自 RetroClash.BCD: -- 计算给定 /n/ 位大小数字的位数 type BCDSize n = CLog 10 (2 ^ n) -- | 将 Unsigned 数字转换为数字列表 toBCD :: forall n. (KnownNat n) => Unsigned n -> BCD (BCDSize n) `` ... 可以这样使用： `` λ> import RetroClash.BCD λ> toBCD (42 :: Unsigned 13) 0 :> 0 :> 4 :> 2 :> Nil `` `toBCD` 能够为给定的数字类型产生正确的向量大小（这里需要 4 位数字来显示一个 13 位数字），这要归功于 `BCDSize`，它在编译时执行计算。 总而言之，以下是 Clash 引入的新类型类： - `BitPack a` 用于转换类型，并计算表示类型 *a* 的元素所需的位数。提供：`pack`、`unpack` 和 `bitCoerce` - `Resize f` 用于将一个值的表示强制转换为不同位数。提供：`resize` - `SaturatingNum a` 用于处理溢出和下溢行为。提供：`satAdd`、`satSub`，... 现在我们已经理解了 Clash 的类型级数据结构，我们需要探索这些类型如何与硬件时序交互。与无时间的纯函数式编程不同，大多数 FPGA 设计必须考虑时钟周期和状态变化。 ### 寄存器传输级 https://midirus.com/blog/advent-of-fpga.html#register-transfer-level 在继续使用 FPGA 解决 Advent Of Code 之前，我需要介绍另一个 Clash 原语，用于定义线缆和创建寄存器。 在数字电路中，寄存器传输级建模（RTL）是 HDL 基础之上的设计抽象： RTL FPGA 本质上由诸如与非门之类的逻辑门构成。为了建模状态化计算，我们需要定义状态多久更新一次，以及在哪里存储正在计算的值。 因此，RTL 是一个同步模型，由以下部分组成： - 时序逻辑，由寄存器（如触发器或锁存器）组成，每个时钟周期更新一次。 - 组合逻辑，处理值并将其输出反馈给寄存器。 #### 时钟 https://midirus.com/blog/advent-of-fpga.html#clock Clash 的时钟由一个域类型变量参数化，通常命名为 *dom*，它描述其频率以及其他属性，如有效边沿。得益于类型级别计算，可以使用域类型变量获得分频器： `` -- 来自 RetroClash.Clock: type ClockDivider dom ps = ps `Div` DomainPeriod dom type Nanoseconds (ns :: Nat) = 1_000 * ns type Microseconds (us :: Nat) = Nanoseconds (1_000 * us) type Milliseconds (ms :: Nat) = Microseconds (1_000 * ms) `` Clash 提供了一个默认时钟，名为 `System`，运行在 100MHz，并且可以这样计算给定持续时间的周期数： `` -- 100MHz 下的 10 纳秒持续 1 个周期 λ> SNat :: SNat (ClockDivider System (Nanoseconds 10)) SNat @1 -- 100MHz 下的 42 毫秒持续 4,200,000 个周期 λ> SNat :: SNat (ClockDivider System (Milliseconds 42)) SNat @4_200_000 `` 时钟域类型变量通过 `KnownDomain` 约束，使得能够编写适用于任何时钟的电路： `` -- 来自 Clash.Signal: class (KnownSymbol dom, KnownNat (DomainPeriod dom)) => KnownDomain (dom :: Domain) `` 这允许您编写一个单一的电路设计，并在具有不同时钟的 FPGA 上重用，而无需修改代码。 此外，寄存器还需要 *复位* 和 *使能* 线，因此，与其到处传递这些线缆，不如使用以下约束： `` type HiddenClockResetEnable dom = (HiddenClock dom, HiddenReset dom, HiddenEnable dom) `` 这样，时钟只需在设计的根处设置一次，方法如下： `` withResetEnableGen :: KnownDomain dom => (HiddenClockResetEnable dom => circuit) -> Clock dom -> circuit withResetEnableGen circuit clk = withClockResetEnable clk resetGen enableGen circuit `` 这个辅助函数接收一个受 `HiddenClockResetEnable` 约束的电路和一个 `Clock`，并通过自动连接时钟、复位和使能线来移除约束，返回一个完全连接的电路。 #### 寄存器 https://midirus.com/blog/advent-of-fpga.html#register 寄存器本质上是一个记住其先前值的信号。虽然 Signal 表示任何随时间变化的值，但寄存器专门跨时钟周期存储状态。 以下是使用 Clash 创建寄存器的方法： `` -- 来自 Clash.Signal: register :: (HiddenClockResetEnable dom, NFDataX a) => a -> Signal dom a -> Signal dom a `` NFDataX 是传递给 Signal 的值的一个额外约束。它可以像 NFData 一样自动派生。 这个定义精确地将寄存器建模为上面的 RTL 图中所示：它接收一个初始值和一个输入值信号，并产生输出值信号。 Signal 实现了 Applicative 类型类，这意味着可以使用惯用的 Haskell 代码来操作它们。 例如，这里是如何使用寄存器创建一个组件，重复计数到 5： `` count2five :: (HiddenClockResetEnable dom) => Signal dom (Index 5) count2five = counter where counter = register 0 (satSucc SatWrap <$> counter) `` 注意 counter 是如何递归定义的。它的下一个值是根据前一个值在反馈回路中产生的，这正是 RTL 设计的工作方式。 如果您好奇，这里是 Clash 如何将此代码编译为 verilog：Count2Five.v（https://codeberg.org/TristanCacqueray/advent-of-clash/src/branch/main/verilog/Count2Five.topEntity/topEntity.v）。 Clash 提供了一些与 Signal 配合良好的运算符： `` mux :: Applicative f => f Bool -> f a -> f a -> f a (.&&.) :: Applicative f => f Bool -> f Bool -> f Bool (.||.) :: Applicative f => f Bool -> f Bool -> f Bool `` `mux` 类似于 `if` 语句，可以与信号一起使用。这是另一个示例组件，通过将最后看到的值存储在名为 `prev` 的本地寄存器中，来丢弃 `Maybe` 值流中重复的 `Just`： `` onceJust :: (HiddenClockResetEnable dom, NFDataX a) => Signal dom (Maybe a) -> Signal dom (Maybe a) onceJust i = mux (hasChanged <$> prev <*> i) i (pure Nothing) where hasChanged Nothing (Just _) = True hasChanged _ _ = False prev = register Nothing i `` 最后，信号可以使用 `sample` 进行模拟： `` -- 来自 Clash.Signal: sample :: (KnownDomain dom, NFDataX a) => (HiddenClockResetEnable dom => Signal dom a) -> [a] `` ... 可以这样使用： `` λ> take 13 $ sample @System $ count2five [0,0,1,2,3,4,0,1,2,3,4,0,1] λ> take 6 $ sample $ onceJust @System [Nothing, Just 42, Just 42, Nothing, Just 23] [Nothing,Just 42,Nothing,Nothing,Just 23,Nothing] `` #### Bundle https://midirus.com/blog/advent-of-fpga.html#bundle 最后，Clash 提供了一个额外的功能来帮助处理信号：`Bundle`。当处理具有多个输入和输出信号的复杂电路时，单独管理它们变得很麻烦。