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:
- 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.
- 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