SSM-RDU: A Reconfigurable Dataflow Unit for Long-Sequence State-Space Models
Sho Ko, Kunle Olukotun · 2025
Read SSM-RDU: A Reconfigurable Dataflow Unit for Long-Sequence State-Space Models by Sho Ko, Kunle Olukotun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-22937.txt.
Introduction
Sho Ko and Kunle Olukotun redesign a programmable chip unit for state-space sequence models, in a 2025 hardware paper. Models such as Mamba and Hyena handle long sequences with scans and Fourier transforms instead of attention. Graphics processors are built for dense matrix math and handle these operations poorly. The authors extend a reconfigurable dataflow unit with light wiring changes inside its compute tiles.
The tweaks let Fourier and scan dataflows map onto the chip in space, at under one percent extra area and power. For Hyena, the unit ran about six times faster than a graphics processor and twice the base design. For Mamba, the gains were about twofold on both comparisons. The work argues sequence models need hardware shaped to their real operations.
Catalog record
| CREATOR | Sho Ko, Kunle Olukotun |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-22937
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SSM-RDU: A Reconfigurable Dataflow Unit for Long-Sequence State-Space Models Sho Ko, Kunle Olukotun Abstract Long-sequence state-space models (SSMs) such as Hyena and Mamba replace the quadratic complexity of self-attention with more efficient FFT and scan operations. However, modern accelerators like GPUs are poorly suited to these non-GEMM workloads due to rigid execution models and specialization for dense matrix operations. This paper proposes architectural extensions to a baseline Reconfigurable Dataflow Unit (RDU) that efficiently support FFT-based and scan-based SSMs. By introducing lightweight interconnect enhancements within compute tiles, the extended RDU enables spatial mapping of FFT and scan dataflows with less than 1% area and power overhead. The resulting architecture achieves a 5.95 × 5.95\times speedup over the NVIDIA A100 GPU and a 1.95 × 1.95\times speedup over the baseline RDU for Hyena, and a 2.12 × 2.12\times and 1.75 × 1.75\times speedup over the A100 GPU and baseline RDU, respectively, for Mamba. I Introduction Self-attention-based large language models (LLMs) [ 39 ] have revolutionized the field of machine learning but they suffer from the quadratic computational complexity O(N^{2}) relative to the sequence length, making them impractical for long-sequence modeling. However, long-sequence modeling is crucial for application domains requiring high-resolution temporal understanding such as genomics and bio-informatics [ 29 ] , audio processing [ 16 ] , video understanding [ 26 ] , financial forecasting [ 35 ] , and weather modeling [ 1 ] . State-space models (SSMs) such as Hyena [ 29 , 31 , 27 ] and Mamba [ 17 , 13 ] are promising solutions for long-sequence modeling since they replace the quadratic attention computation with sub-quadratic log-linear O(Nlog_{2}(N)) computation patterns such as FFT and scan. SSMs can scale up to a sequence length of one million. Modern GPUs are ill-suited for SSM workloads due to two key constraints. First, their computational throughput is dominated by tensor cores, which contribute up to \sim 80\% of their peak theoretical FLOPs [ 30 ] . While tensor cores excel at dense matrix multiplication (GEMM), they are inherently inefficient for non-GEMM kernels such as FFT kernels in Hyena and scan kernels in Mamba, which involve irregular memory access patterns, data-dependent computation, and low arithmetic intensity. Forcing non-GEMM kernels on tensor cores in GPUs results in sub-optimal algorithm [ 15 ] or significant software change [ 12 ] . Second, GPUs suffer from limited kernel fusion capabilities due to their rigid execution model, which processes kernel-by-kernel sequentially. This forces intermediate results to be staged in off-chip memory, incurring significant latency and energy overheads [ 33 ] . To address these limitations, people have proposed a Reconfigurable Dataflow Unit (RDU) architecture optimized for diverse computational patterns in both academia [ 34 ] and industry [ 33 , 32 ] . Unlike GPUs, which centralize compute resources and memory hierarchies, the RDU employs a distributed pattern compute units (PCUs) and pattern memory units (PMUs) coupled with programmable network-on-chip (NoC) switches. We start with a baseline architecture of a RDU, which can dynamically reconfigured to support different computation patterns such as SIMD and systolic, and extend it to support FFT and scan operations. With such design, two critical advantages are enabled: kernel fusion and adaptive parallelism. For kernel Fusion, multiple kernels reside on the chip simultaneously and data are streamed and pipelined across kernels on-chip, eliminating off-chip memory bottlenecks and enabling fusion of multiple kernels. For adaptive parallelism, RDU compute tiles can be reconfigured at runtime to match the dataflow requirements of FFT (butterfly operations) and scan (prefix-sum trees), maximizing parallelism while minimizing control overheads. We summarize the key contributions of this work as follows: • We present an in-depth analysis of the RDU architecture, along with a detailed study of Hyena SSM and Mamba SSM algorithms. • We propose an extension to the baseline RDU to support FFT operations, enabling an efficient mapping of the Hyena SSM onto the RDU. This implementation achieves a 1.95\times speedup over the baseline RDU and a 2.0\times to 5.95\times speedup over a baseline GPU, while incurring less than 1% area and power overhead. • We propose a second extension to baseline RDU to support scan operations, facilitating the mapping of the Mamba SSM onto the RDU. This approach achieves a 1.75\times speedup over the baseline RDU and a 2.12\times speedup over a baseline GPU, also with less than 1% area and power overhead. II Background II-A Reconfigurable Dataflow Architecture Fig. 1: (A) The workload dataflow graph in which vertices represent computation kernels and edges represent tensors. (B) Dataflow execution: multiple kernels are fused on-chip and data is pipelined through the kernels in a streaming fashion. (C) Kernel-by-kernel execution: kernels are executed sequentially with frequent DRAM accesses between kernels. When executing a workload dataflow graph shown like the one in Figure 1 A, different accelerators can be classified into two categories of execution models: kernel-by-kernel and dataflow. Kernel-by-kernel execution is typically done in instruction-based processor architectures such as NVIDIA’s graphics processing unit (GPU) [ 10 , 9 ] . Kernel-by-kernel execution loads the data from memory to on-chip, executes the kernel, and then stores the results back to memory, as shown in Figure 1 C. This incurs more memory traffic and results in compute under-utilization. Dataflow execution is typically done in spatial architectures like SambaNova’s reconfigurable dataflow unit (RDU) [ 33 , 32 ] . Dataflow execution is capable of mapping multiple kernels spatially, fusing them on-chip, and pipelining input data through the kernels in a streaming fashion, as shown in Figure 1 B. This spatial computing paradigm results in less memory traffic and improves compute utilization. Zooming into the micro-architecture of the RDU, it comprises a grid of distributed compute tiles (PCUs) and memory tiles (PMUs). Each PCU features a pipelined SIMD architecture with multiple lanes and stages: Figure 2 depicts an instance with 8 lanes and 6 pipeline stages. The PCU supports three primary operation modes: element-wise, systolic, and reduction. In the element-wise mode, data flows unidirectionally from left to right. In the systolic mode, data flows both horizontally (left to right) and vertically (top to bottom), enabling efficient matrix-like computations. In the reduction mode, data flows from left to right, leveraging an inter-stage reduction tree interconnect to aggregate partial results efficiently. Each Functional Unit (FU) has a total of four input sources: two from the lane dimension, one from the stage dimension, and one constant input. The FU supports three core operations: scalar multiplication, scalar addition, and multiply-and-accumulate (MAC). The MAC operation is employed in the systolic mode configuration of the PCU, where it performs partial product accumulation and propagates results to neighboring FUs. The scalar addition and multiplication operations enable flexible computation between any two of the four available inputs. These scalar operations are primarily used in the element-wise and reduction modes of the PCU configuration. Fig. 2: The RDU chip is composed of a grid of PCUs and PMUs. Each PCU features a pipelined SIMD architecture with multiple lanes and multiple pipeline stages. It supports three execution modes: element-wise, systolic, and reduction. Within each functional unit (FU), there are four input sources, along with dedicated add and multiply operations. The FU can be configured to perform a multiply-and-accumulate (MAC) operation, or a scalar addition