Skip to content

About

Hardware-mapped space-time parallelism for FFT, NTT, FWHT, and butterfly computations on GPUs

Topics

Resources

Contributing

Stars

1 star

Watchers

0 watching

Forks

Latest commit

 

History

89 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

cuButterfly

Hierarchical hybrid dataflow for butterfly computation on GPUs.

Repository checks License Citation

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.

Start with your task

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.

Research method and engineering

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.

  1. Derive local work and handoffs. Stage dependencies define closed regions; their intersections identify exchanged values and consumer predecessors.
  2. 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.
  3. 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.

Dependencies define regions and handoffs; organization and compatible cores are checked against static hardware profiles before preparation and execution

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.

Performance overview

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.

CPU-normalized performance distributions grouped by butterfly operator and precision. Boxes compare cuButterfly and available external GPU libraries on a shared axis.

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.

Installation and first checks

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 8

Use --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.json

Use the Python environment selected for installation. Manifest expansion records requested cases without executing GPU workloads. See the benchmark guide for measurement and reproduction.

Capability and evidence scope

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.

Citation and license

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.

About

Hardware-mapped space-time parallelism for FFT, NTT, FWHT, and butterfly computations on GPUs

Topics

Resources

Contributing

Stars

1 star

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages