ShakeFlow: Functional Hardware Description with Latency-Insensitive Interface Combinators

Functional hardware languages let designers build circuits by chaining small reusable operations such as map and filter, but real hardware modules talk through valid/ready handshakes that send data forward and back-pressure backward at the same time, and that two-way loop breaks the one-way plumbing those operations assume — ShakeFlow gives every interface an explicit forward type and backward type and makes each combinator a small state machine over both directions, so valid/ready pipelines compose like ordinary functional code; porting a 100 Gbps network card and a hardware library this way cut their code by 26 and 38 percent while keeping the same throughput.

Why this problem is worth solving

Consider the transmit checksum unit of a network card. Packets arrive on one stream, commands on another. The unit must merge the two streams fairly, split the merged stream so one copy goes to a checksum calculator and one waits in a packet buffer, serialize the checksum result through a queue, then merge checksum and packet back together, drop packets that need no checksum, and add a buffer so the downstream stage can stall without losing data. In the original Corundum network card this module is 424 lines of Verilog. Almost all of the difficulty is not the arithmetic; it is the handshakes. Each of the dozen sub-stages has a

The functional style promises to make this a dozen lines: mux, duplicate, map, FIFO, map, filter, buffer. The artifact shows the ShakeFlow version of that module does read almost like that list, with a round-robin mux, a duplicate, a state machine, maps, FIFOs, filter-maps and a skid buffer chained one after another, and it is 297 lines rather than 424, with the compiler generating 1,466 lines of Verilog from it. The reason nobody could write it that way before is the subject of the paper.

What people did before, and where it broke

• Verilog and SystemVerilog. Wires, registers and always blocks. Where it broke. Every valid/ready boundary is hand-written. Reuse is by copying; composition is by wiring; a change to one stage’s stall behaviour ripples into its neighbours.
• Chisel and other embedded hardware languages. Better abstraction and generation, and a Decoupled type for valid/ready. Where it broke. Decoupled is a bundle of wires, not a stream you can map over. Connecting stages is still explicit port wiring, and there is no standard library of stream combinators that manage ready as well as data.
• Functional hardware languages: Lava, Clash, and stream libraries. True combinators over signals. Where it broke. Their signals are one-directional values per cycle. A backward ready signal that depends combinationally on the same cycle’s forward valid creates a loop that their model cannot express, so latency-insensitive designs fall outside what the combinators can build.
• BaseJump STL. A carefully engineered Verilog library of valid/ready modules with a published discipline (helpful versus demanding endpoints) for avoiding combinational loops. Where it broke. The discipline is documentation, not types; the modules are still Verilog and still composed by hand.
• The gap. No language offered functional combinators whose type captured both directions of a latency-insensitive interface and whose implementation handled the backward path correctly by construction.

Where ShakeFlow sits

The idea

An interface is two signal types. In the compiler, the Interface trait has two associated types, Fwd and Bwd. The forward type is what the producer drives; the backward type is what the consumer drives. A plain one-way wire has an empty backward type. A valid/ready channel has forward Valid<V>, a struct of the payload plus a valid bit, and backward Ready, a struct of one ready bit. Because both directions are part of the type, a combinator’s signature says exactly which signals it may read and which it must produce in each direction, and composite interfaces, such as a pair of channels or an array of channels, are built from the same trait.

The generic combinator is a state machine over both directions. ShakeFlow’s core operation, called fsm in the compiler, takes an initial state and a function of one clock cycle. That function receives three things: the forward signals arriving on the input, the backward signals arriving from the output, and the current state. It returns three things: the forward signals to drive on the output, the backward signals to drive on the input, and the next state. This is the whole trick. A map over a valid/ready stream is an fsm whose logic sets the output’s data to f(input data), copies valid forward and copies ready backward. A filter passes ready backward unconditionally but raises valid forward only for kept elements. A FIFO keeps a buffer as state, raises valid when the buffer is non-empty and ready when it is not full. Because the logic sees both directions at once, the cyclic dependency that defeated one-way combinators is simply a function of two inputs.

Which side may depend on which. A combinational loop appears if the consumer’s ready depends on valid while the producer’s valid depends on ready in the same cycle. ShakeFlow encodes BaseJump’s discipline in the channel type as a protocol parameter: a channel is Helpful if its producer offers valid up front, so the consumer’s ready may depend on it, and Demanding if it does not, in which case the consumer’s ready must not depend on valid. The standard library’s combinators are typed accordingly, so a design that would loop fails to type-check rather than fails in simulation.

Feedback and instantiation. Real designs contain loops between modules, for example a credit counter whose output feeds back to an arbiter’s input. A loop_feedback combinator takes a module whose input and output both carry an extra feedback interface and connects the output side’s feedback to the input side’s, producing a module without the extra ports. Existing Verilog IP, such as the vendor’s Ethernet block, is brought in with a module-instantiation combinator that gives it ShakeFlow interface types on its ports.

Signal expressions. Data transformations inside a combinator are written as expressions over typed signals, integers of fixed width, arrays, structs and enums, with the usual arithmetic, projections and a select construct, so the arithmetic of a checksum or a filter coefficient is written in the same language as the plumbing.

Tracing a valid/ready map through the combinator

in: valid 1, data 5 | out bwd: ready 1 | map -> out: valid 1, data 10; in bwd: ready 1 | transfer on both sides

Why it works

• Typing both directions removes the mismatch. Because a channel’s backward signals are part of its type, a combinator cannot forget to drive ready, and a module cannot be connected to a port of the wrong protocol. What was an unwritten wiring convention becomes a compile-time check.
• The fsm signature is exactly the shape of a latency-insensitive stage. A stage’s outputs in one direction depend on its inputs in the other direction plus state. Giving the one-cycle function all three inputs and asking for all three outputs matches the hardware, so every standard stage is expressible, from a stateless map to a FIFO to an arbiter.
• Protocol annotations rule out combinational loops. Encoding Helpful and Demanding in the channel type means the only way to build a ready-depends-on-valid-depends-on-ready cycle is to violate a type, which the compiler rejects.
• Combinators compose because interfaces are values. Each combinator consumes an interface value and returns a new one, so a pipeline is an expression: mux, then duplicate, then map, then FIFO. The compiler assembles the submodules and wires forward and backward ports from the types.
• Feedback restores generality. Since a module with an extra feedback interface on both sides can be closed by loop_feedback, cyclic module graphs, not only linear pipelines, stay inside the functional style.

What it costs

• Generated code is larger. The 3,791 lines of ShakeFlow for the Corundum modules become 16,419 lines of Verilog, and BaseJump’s 3,389 lines become 31,423. That is the synthesizer’s input, not the designer’s, but it affects simulation and inspection.
• Rust as a host language. Designs are Rust programs using traits, const generics and macros; the artifact pins a 2022 nightly toolchain. Hardware engineers must learn both the language and the embedded model.
• Standard-library discipline is required. The Helpful and Demanding annotations must be chosen correctly when writing new combinators; the types then enforce them for users, but the library author carries the burden.
• Vendor IP stays opaque. Instantiated Verilog modules get ShakeFlow ports but no ShakeFlow semantics; the compiler cannot check inside them.
• Resource and timing effects are in the paper’s Table 2. The artifact reproduces a resource-consumption comparison between the original and ported network cards, but the numbers were not available for this page.

The evaluation

The artifact evaluates ShakeFlow on two real code bases. BaseJump STL’s dataflow and network-on-chip modules were ported, and so were the core packet-processing modules of Corundum, an open-source 100 Gbps FPGA network card: descriptor and completion queue management, checksum validation and offload, receive hashing and receive-side scaling. The ported card was built with Vivado 2021.1 for a Xilinx Alveo U200 and benchmarked against the original Corundum and a commercial Mellanox MCX556A two-port 100 Gbps card, on identical hosts with an AMD Ryzen 5600X, PCIe 4.0 and Linux 5.11, using iperf, fio and nginx workloads at 1500 and 9000 byte MTU.

Check yourself

Sources

The paper is “ShakeFlow: Functional Hardware Description with Latency-Insensitive Interface Combinators” by Sungsoo Han, Minseong Jang and Jeehoon Kang, KAIST, published at ASPLOS 2023, Volume 2, DOI 10.1145/3575693.3575701. The artifact is open source at github.com/kaist-cp/shakeflow and archived on Zenodo (record 7275790); it contains the compiler, the standard library, the BaseJump STL and Corundum ports, the FIR filter example and the evaluation scripts and raw data.

This explainer is marked as a draft because the full text was not accessible. The paper is gold open access, but the ACM Digital Library returned an anti-bot page on every URL tried; there is no arXiv preprint, the KAIST laboratory and institutional pages link only to the DOI, and the Zenodo archive holds the artifact README rather than the paper. Claims attributed to the paper come from its abstract. The description of interface types, the fsm combinator, protocol annotations, standard combinators, feedback and instantiation comes from reading the compiler and standard-library source; the module-by-module line counts, the tx_checksum decomposition and the evaluation hardware and workloads come from the artifact README. The traced example is illustrative.