Hierarchical hybrid dataflow for butterfly computation on GPUs.
cuButterfly is a CUDA research library for FFT, NTT, FWHT, structured 2×2, and subset/superset zeta transforms. It derives local work and communication from butterfly dependencies, then combines spatial expansion and temporal reuse under hardware constraints. Compatible arithmetic cores remain replaceable; a single-band transform is also a valid organization. The v0.9 overview describes the framework and public interfaces.
Teng Wang
High Efficient Intelligent Computing Lab
Suzhou Institute for Advanced Research,
University of Science and Technology of China · Suzhou, China
wangt635@ustc.edu.cn
Author affiliation, software citation and third-party attribution are maintained in Project and authorship, CITATION.cff and third-party notices. This is independently maintained research software, not an institutional release.
| Task | Entry |
|---|---|
| Install and call the library | Getting started → Public planner → Support contract |
| Understand the method | Design overview → Research principles → Design space |
| Extend an operator, core or platform | Engineering map → Contributing |
| Calibrate or tune a GPU | Hardware workflow → Target runbooks |
| Run a comparison | Benchmark guide → Reporting protocol |
| Read benchmark results | Experimental results → Reproduction tools |
The documentation index provides the complete reading routes. The archive preserves version history and research records.
A fast local core still depends on data supply, storage capacity, communication and concurrency. Roofline bounds the available performance, but does not choose how dependent stages and data regions should execute. cuButterfly studies that organization problem across butterfly arithmetic families.
- Derive local work and handoffs. Stage dependencies define closed regions; their intersections identify exchanged values and consumer predecessors.
- Characterize resource demand. Stage and data dimensions admit spatial expansion and temporal reuse. Their combination determines live state, communication, arithmetic work and ready work at each storage scope.
- Execute tile subgraphs. Bind legal regions to compatible cores and bounded storage. Producer writes and consumer reads jointly determine boundary placement; publication and buffer reuse preserve dependencies.
The same construction repeats across storage scopes. Its winning partition, core, layout and pipeline depth may differ by arithmetic, precision, workload and hardware. More residency or overlap need not improve every request.
The editable diagram separates the method from its engineering pipeline. Calibration supplies target-local observations; selection, compilation and caching prepare executable plans. These mechanisms support the research method and are not separate novelty claims. Warm execution excludes preparation; required permutations, conversions and normalization stay inside the complete-call timing boundary.
The A100 80GB PCIe overview compares complete transforms with a common CPU reference for each operator family. Each value is CPU latency divided by the latency of the GPU backend on the same request.
Boxes show workload IQR, the center line is the median, and whiskers span the observed range. Each point is a matched CPU/GPU request. The letters above each group report each backend's geometric mean and sample count. CPU references are FFTW with eight threads, and FXT, HEXL or the author Butterfly implementation with one thread, as indicated in the figure. These shared-host CPU measurements are provisional. CPU wall time and resident GPU time have different boundaries; host-device transfers are excluded from GPU measurements.
The paired GPU comparison separately reports specialized-library latency divided by cuButterfly latency, including losses. Its main comparison, cyclic NTT extension and FP16 cohort retain independent populations. The results guide describes coverage, modulus limits, numerical reports and interface contracts. Missing external comparisons remain gaps, not zero-valued measurements.
The separate PRO6000 Figure 9 extension provides all six Full66 operator families, local Xeon CPU denominators, an independent final-build FFT17 comparison and an explicitly adapted FP16 MMA9 panel. It retains unsupported cells, GPU-NTT failures and floating review; its PRO6000 and historical A100 measurements are never pooled. The finite follow-up adds legal cyclic NTT8, three-process CPU confirmation and a self-contained record package; backend-specific status keeps exact cuButterfly results distinct from external GPU-NTT failures.
Use a CUDA toolkit and compiler compatible with the target GPU. Follow Getting started for a shared-library installation, Python descriptor validation and the public execution interface. The installer can detect the target and reuse compatible static profiles. Refresh and tuning are explicit operations; a bounded calibration is not exhaustive optimization.
For a configured research platform, one entry prepares dependencies, builds the library, parallelizes CPU preparation, then calibrates and benchmarks an idle GPU:
python3 scripts/research_platform.py all --target config/platforms/pro6000_server96.json \
--gpu 0 --mode full --jobs 8Use --prepare-only for CPU preparation or --gpus 0,1 for independent cards.
See the platform workflow
for toolchain prerequisites, reuse, scope and reports.
On an existing checkout, these checks need no GPU:
python scripts/check_repository.py
python -m benchmark.manifest config/benchmark_quick.json --mode quick \
--output /tmp/cubutterfly-quick-manifest.jsonUse the Python environment selected for installation. Manifest expansion records requested cases without executing GPU workloads. See the benchmark guide for measurement and reproduction.
A request combines operator semantics with precision, direction, normalization, input/output order, rank, shape, batch, placement and strides. The support contract distinguishes a valid request from an implemented, compiled, measured or selected realization. Adapters retain full conversion costs; unavailable combinations remain explicit.
Evaluation covers three complementary questions:
| Experiment | Question |
|---|---|
| Operator comparisons | How do complete generated transforms compare with specialized libraries? |
| Controlled organization experiments | What changes when the arithmetic core is held fixed, and which resource effects explain it? |
| Applications | How much of the transform benefit reaches a complete application under matched invocation and output contracts? |
Experimental results report the measured domains, protocols and limitations, including negative results. The common method permits different winning organizations; it does not require every mechanism to help every request.
Ascend-FFT and Kunlunxin-FFT are independent lowerings of the method to Huawei Ascend and Kunlunxin P800, respectively. Their hardware-specific kernels, interfaces and measurements belong to their own repositories. See platform ports for the relationship; their results are not pooled with CUDA comparisons.
Use CITATION.cff for software metadata. Software metadata identifies this implementation and its release version.
@software{wang_cubutterfly_2026,
author = {Teng Wang},
title = {cuButterfly: Hardware-Mapped Space-Time Parallelism for Butterfly Computations on GPUs},
year = {2026},
version = {0.9.0},
url = {https://github.com/TruNcat3/cuButterfly},
organization = {High Efficient Intelligent Computing Lab,
Suzhou Institute for Advanced Research,
University of Science and Technology of China}
}The Research-Only Non-Commercial License permits the uses stated there; commercial use requires a separate license. Third-party components retain their own notices and licenses.