跳到正文
Hacker News· cyranka·· 6 天前AI 评分28

SweepFFT：面向缓存外快速傅里叶变换的最小遍历算法

SweepFFT: Pass-Minimal Algorithms for Out-of-Cache Fast Fourier Transforms

AI 导读

SweepFFT 提出面向缓存外 FFT 的最小遍历（pass-minimal）算法，在五台机器上比 MKL 快 1.15–1.96×、比 FFTW 快 1.27–3.52×，所有主要端点 p_Holm = 0.002。

正文 · AI 翻译

SweepFFT：面向缓存外快速傅里叶变换的通过次数最少算法。

近期工作证明了在多带图灵机上整数乘法和 DFT 可在 O(n (log n)^{1-κ}) 内完成：

这一增益本身，在任何能放进 RAM 的规模下都无法测量。但证明所优化的代价模型，即对磁带的通过次数，与对 DRAM 的扫描紧密对应，而这正是限制大规模 FFT 的因素。

在所有系统共有的最大变换长度下，在头条协议下，SweepFFT 比 MKL 快 1.15–1.96 倍，比 FFTW 快 1.27–3.52 倍。这一优势取决于缓存占用、因式分解、规划和分页。在一个系统上进行的析因消融实验将 94.5–99.6% 的可解释缓存外对数运行时间变异归因于批处理、融合、二者的交互作用以及非临时存储。

预印本链接。

完整报告：results/REPORT.md。

最终结果

五台机器：预注册端点

每台机器都用最终代码运行了完整测试套件（scripts/run_machine.sh <label> --all），包括来自 results/ENDPOINTS.md 的两项预注册研究。每项研究包含 10 个区块的全新固定进程，使用 2^22 – 2^26 上的几何平均值，并报告 95% 区块自助法置信区间。以下每个主要端点都支持 pmfft，p_Holm = 0.002。普通指调用方数组以普通方式分配（主要研究）；大页指调用方数组位于 2 MB 页上。

机器 对比 FFTW，普通 对比 FFTW，大页 对比 MKL，普通 对比 MKL，大页 大型非二次幂对比 MKL
Intel i7-13700H（笔记本） 1.18 [1.16, 1.20] 1.45 1.03 [1.02, 1.04] 1.13 2.29
Intel Xeon Gold 6234（服务器，Cascade Lake） 1.23 [1.20, 1.25] 1.39 1.18 [1.15, 1.20] 1.19 1.20
AMD EPYC 7302（服务器，Zen 2） 1.32 [1.30, 1.34] 1.56 1.17 [1.16, 1.18] 1.65 1.97
AMD Ryzen 9 3900X（台式机，Zen 2） 1.31 [1.30, 1.31] 1.60 1.22 [1.22, 1.22] 1.74 2.00
AMD Ryzen 7 7800X3D（台式机，Zen 4，96 MB L3） 1.23 [1.22, 1.24] 1.45 1.28 [1.26, 1.30] 1.15 2.08
  • pmfft 在哪里落败：在缓存内（2^4 – 2^11），每台机器上的大多数规模下 FFTW 都更快。
  • 分页效应因机器而异（REPORT §20–21）。它在 Zen 2 上最强，在 Xeon 上较小，而在 7800X3D 上对 MKL 则相反。
  • 在任何机器上，单核下都没有重叠。数据移动和算术运算是相加而非重叠：在所有情况下它们的总和为完整时间的 0.88 – 1.00（REPORT §22）。

在你的机器上运行基准测试

要求：

  • x86-64 上的 Linux，支持 AVX2 + FMA（Intel Haswell 或更新，AMD Zen 或更新）；
  • gcc/g++ ≥ 11、make、curl、git、python3 以及 uv；
  • 约 2 GB 磁盘空间；
  • 最大规模需要 16 GB 或更多 RAM（2^26 在规划时每个进程约需 8.5 GB；较小的机器会自动停在较小的规模）。
git clone https://github.com/dzako/sweepfft && cd sweepfft
uv sync                                   # Python env (pandas, numpy, ...) for the scripts
scripts/setup_third_party.sh              # download + build FFTW 3.3.10, MKL 2024.2.2 (wheels), ducc0 (~5 min)
scripts/build.sh                          # build all benchmarks into build/
scripts/run_machine.sh my-box --quick     # 5-minute smoke test -> results/machines/my-box-quick/
scripts/run_machine.sh <label>            # full run (45-90 min)  -> results/machines/<label>/
scripts/run_machine.sh <label> --all      # every study below (~12-20 h)

完整运行测量什么

除非给出 --mt，否则一切都以单核运行，使用与报告相同的协议：

  • 从 2^4 到 2^26 的二次幂；
  • 光滑合数规模；
  • 素数，包括精确模式和 fast=1；
  • 3 次扫描卷积；
  • 多进程带宽扩展测试，k = 1、2、4、8、… 个进程，最多到插槽 0 上的物理核心数。

为多线程对比添加 --mt。它在单个进程中针对多线程 MKL 和多线程 FFTW 运行 pmfft_mt，线程数从 1、2、4……直到 socket 0 上的物理核心数（在混合架构 Intel CPU 上包括 E 核），并且在启用计数器时以满线程数产生 DRAM 流量。FFTW 会为每个 (线程数, n) 组合规划最多 FFTW_TIMELIMIT_MT 秒（默认 300），因此 --mt 大约增加 1 – 3 小时；多核服务器处于时间较长的一端。它需要 build/bench_dft_mt，而 scripts/build.sh 会在 setup_third_party.sh 使用 OpenMP 构建 FFTW 后构建一次。要单独运行它：uv run scripts/scale_mt.py --quick（冒烟测试）或 uv run scripts/scale_mt.py --sizes 2^22,2^24。在笔记本电脑上，请保持机器接通电源并保持凉爽。持续的全核负载会触发功耗限制，使结果偏移 10 – 20%。

添加 --cache-transition 以对跨越 L2、LLC 和 2 – 8 × LLC 边界的 97 个平滑尺寸进行密集扫描（约 1 小时；增加一个相图图），并添加 --factorial 以对 NT 存储 × 批处理 × 融合转置 × 拆分策略进行完整的 2^4 因子消融，并在对数运行时间上使用交互模型（约 1 小时）。两者在启用时都使用 DRAM 计数器。

另外五个选项用于测试结果是否稳健且有用：

  • --fairness（约 3–4 小时）：协议敏感性。它涵盖原地、冷缓存、全新数组、4 KB 或全大页、带和不带 wisdom 的 FFTW ESTIMATE / MEASURE / PATIENT、首次调用计时、x86-64-v3 构建以及匹配协议比较。
  • --repro（约 2–3 小时）：可重复性研究，其终点预先固定在 results/ENDPOINTS.md 中。它运行 10 个块，保留每个样本，记录时钟和温度，并报告块自助法区间。它运行两次：使用普通分配的调用方数组（主要研究，repro_plain.*）和使用大页上的调用方数组（repro.*）。
  • --caller-pages（约 40 分钟）：调用方数组的分页如何改变每个库（大页与普通分配，交错进行），以及暴露 L2 组相联冲突的跨步收集微基准（GB/s 与行数、段大小、页大小、跨步填充）。
  • --overhead（约 45 分钟）：规划与内存开销。它报告 1 到 10,000 次变换的总时间、盈亏平衡重用次数，以及规划后保留的内存、规划峰值和执行暂存内存。
  • --contention (~2 h): controlled bandwidth contention, in two parts:
    • (A) 1 到所有核心的独立进程，带有 DRAM 流量和时钟；
    • (B) 一个 FFT 旁边有一个 STREAM-triad 负载，其带宽被测量。在具有多个 L3 域的 CPU 上，B 既运行负载共享 FFT 核心的 L3 的情况，也运行负载仅共享 DRAM 的情况。

--ceiling（约 1 小时）对两遍计划进行计时，分别去除其算术运算、去除其内存流量，以及作为两个普通流式遍。这显示了时间中有多少是数据移动、多少是算术运算，以及两者重叠了多少。它还映射了大素数的高斯重采样 DFT 的误差预算。

--all 开启所有可选研究（--ablations --mt --factorial --cache-transition --fairness --repro --overhead --contention --caller-pages --ceiling）。

添加 --ablations 以重新检查关键思想是否适用于你的硬件：非临时存储、批处理、四步拆分形状和显式转置。

DRAM 流量计数器（推荐）。如果允许系统级 perf 计数器，运行还会测量每次变换的 DRAM 字节数。在运行前启用它们（无需重启；该设置在重启时恢复）：

sudo sysctl kernel.perf_event_paranoid=0

计数器支持：

  • Intel：内存控制器（IMC）计数器。
  • AMD Zen 2/3：数据织物 DRAM 通道计数器，读 + 写合并。如果 /sys/bus/event_source/devices 没有 amd_df，请先加载 uncore 驱动：sudo modprobe amd_uncore。
  • WSL2 和大多数虚拟机：不可用，因此跳过此步骤。

传递 --no-counters 以跳过它。

获得干净数字的提示

  • 关闭其他应用程序。
  • 尽可能使用 performance 调速器：sudo cpupower frequency-set -g performance。
  • 将透明大页设置为 madvise 或 always。
  • 选择核心。 单核运行会固定到最快的物理核心：在混合架构的 Intel 处理器上 即为 P-core，并避开 CPU 0。扩展性测试为插槽 0 的每个物理核心使用一个逻辑 CPU， 因此在多插槽服务器上它会保持在同一个内存控制器上。要覆盖此设置： BENCH_CPU=<cpu> 和 BENCH_CPUS=<a,b,c,...>。
  • AMD CPU。 MKL 是 Intel 的库，在 AMD 上可能不会使用其最佳代码路径。 与 FFTW 的对比是厂商中立的，后者在此处针对你的 CPU 使用 -march=native 构建。
  • FFTW planning time. FFTW_MEASURE planning is capped at FFTW_TIMELIMIT seconds per size (default 60). On slower machines the large sizes can hit the cap, which yields a truncated, slow plan; summary.md flags those sizes. For a fair comparison there:
    • 删除 results/machines/<label>/fftw_wisdom.dat；
    • 使用 FFTW_TIMELIMIT=600 scripts/run_machine.sh <label> 重新运行。每个受影响的规模大约会增加 10 分钟的 规划时间。
  • 虚拟机和 WSL2。 CPU 固定针对的是虚拟 CPU，由宿主机进行调度，因此预计 会有更多噪声。请在标签中注明，例如 ryzen-3900x-wsl。

贡献结果

完整运行后，results/machines/<label>/ 包含：

  • 原始 CSV 文件；
  • machine.txt，包含 lscpu、内核、编译器、调频器和内存大小（不含主机名或用户数据）；
  • summary.md；
  • 日志；
  • 所使用的 FFTW wisdom。

results/machines/COMPARISON.md 将所有机器并排展示。将该目录与重新生成的 COMPARISON.md 一起提交， 并打开一个拉取请求：

uv run scripts/compare_machines.py
git add results/machines/<label> results/machines/COMPARISON.md

复现完整研究

scripts/run_all.sh 在参考布局 results/*.csv 上重新运行所有消融实验、最终对比、Toeplitz 测试（T1–T3）以及 分析。大约需要 70 分钟。uv run scripts/analyze.py 重新生成 results/tables.md 和图表。

布局

csrc/common/common.h         aligned / huge-page allocation, timers, AVX2 complex helpers, accurate twiddles
csrc/ref/ref.h               __float128 reference DFT (error measurement)
csrc/dft/stockham.h          batched mixed-radix Stockham engine, fused radix-2^f passes      [I2, I9]
csrc/dft/rec4.h              recursive batched four-step, fused transposes, NT stores         [I1, I3, I4, I5, I11]
csrc/dft/rdit.h              depth-first recursive DIT for mid sizes
csrc/dft/arbitrary.h         Bluestein, Rader, Gaussian-resampling DFT                        [I7]
csrc/bench/impl_ours.c       all our variants + pmfft (the measuring planner), pmfft_heur, pmfft_mt
csrc/bench/impl_ext.c        FFTW / MKL wrappers;  impl_ducc.cpp: ducc0 wrapper
csrc/bench/bench_dft.c       driver -> CSV (time, GFlop/s = 5 n log2 n / t, error vs quad reference)
csrc/bench/bench_conv.c      cyclic convolution: library vs 3-sweep transposed-spectrum fusion [I9]
csrc/bench/bench_2d.c        2-D: Nussbaumer polynomial transform vs row-column               [I8]
csrc/tests/                  codelet/engine tests, transpose & axis-permutation benchmarks     [I1-toy, I14]
tests/test_toeplitz.py       Toeplitz representation tests T1-T3
scripts/                     setup_third_party.sh, build.sh, run_machine.sh, run_all.sh, run_bench.py,
                             scale_mp.py, scale_mt.py, mem_traffic.py, cache_transition.py (+ plot_cache_transition.py),
                             factorial.py, compare_machines.py, analyze.py, gen_codelets.py, cpus.py
results/                     reference-machine data, REPORT.md, tables.md, figures; machines/<label>/ per machine

引用

如果你使用 SweepFFT 或其结果，请引用该论文 （doi:10.5281/zenodo.23322613）：

@misc{cyranka2026sweepfft,
  author    = {Cyranka, Jacek},
  title     = {{SweepFFT}: Pass-Minimal Algorithms for Out-of-Cache Fast {Fourier} Transforms},
  year      = {2026},
  publisher = {Zenodo},
  note      = {Working paper, version 1},
  doi       = {10.5281/zenodo.23322613},
  url       = {https://doi.org/10.5281/zenodo.23322613}
}

许可证

GPL-2.0-or-later（见 LICENSE）。

该基准测试链接以下库。scripts/setup_third_party.sh 会下载它们；它们 不随本仓库分发：

  • FFTW（GPL-2.0-or-later）；
  • ducc0（GPL-2.0-or-later）；
  • Intel MKL（Intel Simplified Software License）。

来源：Hacker News · github.com

开源生态部署工程论文研究#论文/研究#开源/仓库#部署/工程