SSM-RDU: A Reconfigurable Dataflow Unit for Long-Sequence State-Space Models

Sho Ko, Kunle Olukotun

TL;DR

State-Space Models (SSMs) like Mamba and Hyena offer a more efficient alternative to Transformers for long sequences, but they run poorly on GPUs designed for matrix multiplication. This paper introduces SSM-RDU, an enhanced reconfigurable architecture that adds specialized "butterfly" and "cross-lane" interconnects to support FFT and scan operations. The result is a chip that outperforms an NVIDIA A100 by up to 5.95x while adding less than 1% in area and power overhead.

What Problem Does This Paper Address?

The "quadratic bottleneck" of standard Transformers ($O(N^2)$ complexity) makes processing very long sequences—like entire genomes or long videos—prohibitively expensive. New State-Space Models (SSMs) solve this by using math that scales much better ($O(N \log N)$ or $O(N)$). Specifically, Hyena relies on Fast Fourier Transforms (FFTs), and Mamba relies on parallel "scans" (prefix sums).

However, modern GPUs are "GEMM-centric"—they are heavily optimized for dense matrix multiplication. When forced to do FFTs or scans, GPUs suffer from irregular memory access and low arithmetic intensity. Furthermore, GPUs execute kernels one-by-one, forcing intermediate data to be written back to slow off-chip memory (DRAM) between every step. This paper seeks to create a hardware architecture that handles these non-matrix operations as efficiently as a GPU handles a matrix.

Methods

The authors build upon a Reconfigurable Dataflow Unit (RDU). Unlike a GPU, which uses a fixed instruction-set architecture, an RDU consists of a grid of Pattern Compute Units (PCUs) and Pattern Memory Units (PMUs) that can be "rewired" at runtime to match a specific algorithm's dataflow.

The paper proposes two lightweight hardware extensions:

  1. FFT-mode PCU: Adds "butterfly interconnects" between pipeline stages. This allows the complex data-shuffling required for Cooley-Tukey FFTs to happen spatially on the chip without hitting memory.
  2. Scan-mode PCU: Adds cross-lane interconnects to support parallel scan algorithms (like Hillis-Steele and Blelloch). This allows the chip to calculate cumulative sums across a sequence in a single pass.

By using Kernel Fusion, the RDU can map an entire SSM layer onto the chip at once. Data streams through the kernels in a pipeline, eliminating the need to constantly move data in and out of DRAM.

Datasets

The authors evaluated their design using architectural simulation rather than training on a specific dataset. They benchmarked the performance of two primary workloads across sequence lengths of 256K, 512K, and 1M tokens:

  • Hyena: An FFT-based SSM.
  • Mamba: A scan-based SSM.
  • Baseline Comparison: They compared their results against an NVIDIA A100 GPU and a baseline RDU without the proposed extensions.

Key Insights and Ideas

  • The "Butterfly" is the Key: The most expensive part of an FFT isn't the multiplication; it's the specific way data needs to be reordered (the butterfly pattern). By baking these specific paths into the hardware wires (interconnects), the authors turned a complex software problem into a simple hardware flow.
  • Spatial vs. Temporal Computing: GPUs compute "temporally" (doing one thing at a time across the whole chip). RDUs compute "spatially" (unrolling the algorithm across the chip so data flows through it like a factory assembly line). This is much more efficient for the "irregular" math found in SSMs.
  • Minimalist Hardware Design: The authors proved that you don't need a completely new chip to support SSMs. Adding these specialized wires cost less than 1% in extra silicon area and power, making it a highly practical upgrade for future AI accelerators.
  • Amdahl’s Law Still Applies: Even with near-perfect scan/FFT performance, the total speedup is eventually limited by the standard MLP (Multi-Layer Perceptron) parts of the model, which don't benefit from these specific interconnects.

Key Results

  • Hyena Performance: The SSM-RDU achieved a 5.95x speedup over the NVIDIA A100 and a 1.95x speedup over the baseline RDU.
  • Mamba Performance: The SSM-RDU achieved a 2.12x speedup over the A100 and a 1.75x speedup over the baseline RDU.
  • Efficiency: The RDU matched the performance of a dedicated, fixed-function FFT ASIC (the VGA) while maintaining the flexibility to be reconfigured for other tasks.
  • Overhead: The specialized PCU modes (FFT and Scan) incurred negligible costs: ~0.4% to 0.7% area increase and ~0.3% to 0.5% power increase.

Limitations and Future Work

  • Simulation-Based: The results are based on DFModel, a performance modeling framework. While DFModel is a validated tool, physical silicon results would provide the ultimate proof of efficiency.
  • Fixed Precision: The hardware synthesis was performed using 16-bit integers (SInt16) due to tool limitations, whereas modern LLMs often use specialized floating-point formats like BF16 or FP8.
  • Scaling: The paper focuses on single-unit performance. Future work could explore how these reconfigurable units scale in a multi-chip system to handle models with billions of parameters.

Summary updated

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.95X speedup over the GPU and a 1.95X speedup over the baseline RDU for Hyena, and a 2.12X and 1.75X speedup over the GPU and baseline RDU, respectively, for Mamba.
BibTeX
@inproceedings{ko2025ssm,
  author = {Sho Ko and Kunle Olukotun},
  title = {{SSM-RDU: A Reconfigurable Dataflow Unit for Long-Sequence State-Space Models}},
  booktitle = {ICCD},
  year = {2025},
  doi = {10.1109/iccd65941.2025.00095},
}

Loading related content...

Figure