CS Paper Radar

A Comparative Study of Parallel Implementations of Short-Time Fourier Transform

Minh Chau Nguyen, Marcelo Ponce

cs.DC cs.PF ·submitted 2026-10-27 23:37 UTC · v1
publishedunusual

Abstract

The short-time Fourier transform (STFT) computes the Fourier transform of a short-duration window of a longer signal, which characterizes how a frequency changes over time. While the Fourier transform algorithms, particularly the Fast Fourier Transform (FFT) algorithm, has been well developed to take advantage of parallel computing, there is limited work on understanding the performance of parallel short-time Fourier transform algorithms. In this study, two parallel short-time Fourier transform algorithms, one is FFT-based and the other a quasi-parallel feedforward algorithm, are implemented and analyzed in comparison with each other. It is found that while the quasi-parallel algorithm outperforms in runtime under low concurrency settings, the FFT-based algorithm scales better and has lower memory usage. For each algorithm, three parallel approaches, shared-memory, distributed-memory and hybrid distributed-shared-memory, are tested. Profiling results show that all implementations are compute bound except for the hybrid feedforward algorithm, and that the distributed-memory variants incur significantly higher communication cost. Overall, this study presents a deeper and more comprehensive analysis and demonstrates the defining characteristics of different families of parallel short-time Fourier transform algorithms, in which the FFT-based approach uses less memory while the quasi-parallel feedforward algorithm has lower runtime but higher serial fraction.

Comment
Presented at the 38th IEEE/SBC International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), October 14-16, 2026. Madrid, Spain. To appear in conference's proceedings

Closest papers

Nearest neighbours by meaning across the whole index.

Universal Short-Time Fourier Transform: Data-Adaptive Window-Length Selection for Time-Frequency Analysis

eess.SP cs.ITcs.SDeess.AS+1 ·2026-10-27 ·Manan Mittal, Kanad Sarkar, Ryan M. Corey, John R. Buck, Andrew C. Singer
similarity 0.54
Abstract · 12 pages; 7 figures; SANE 2026, ASA 2026

The short-time Fourier transform (STFT) characterizes the local frequency content of time-varying signals by evaluating the discrete Fourier transform over a sliding analysis window. The STFT is governed by a fundamental resolution trade-off: a short window localizes rapid transients in time at the cost of frequency resolution, whereas a long window resolves closely spaced harmonics at the expense of temporal resolution. The Universal Short-Time Fourier Transform (U-STFT) resolves this trade-off sequentially by modeling the analysis window duration as a data-adaptive state variable that indexes the number of hops included in the current observation interval. At each frame, a bank of candidate window durations is scored using normalized order-three Rényi entropy to quantify joint time-frequency concentration. A window length trellis aggregates the resulting $\mathcal{O}(3^M)$ candidate window schedules with linear complexity per frame, guaranteeing a cumulative mix-loss regret bound of $\mathcal{O}((k+1)\log M)$ relative to any hindsight window schedule with $k$ resolution changes over $M$ frames. By linearity of the Fourier transform, posterior expectation across the candidate bank yields a single spectrum equivalent to an STFT evaluated with a data-adaptive effective window, while an envelope-normalized synthesis stream guarantees exact overlap-add reconstruction. Evaluations on synthetic and marine bioacoustic signals demonstrate adaptive resolution tracking, enhanced spectral concentration, and exact time-domain invertibility.

0.33

Performance Evaluation of Fast Fourier Transforms on Emerging RISC-V Hardware with Vector Extension Support

cs.MS cs.DCmath.NA ·2026-08-28 ·Daniel Seibel, Kaveh Haghighi Mood, Jayesh Badwaik, Prateek Chawla, Stepan Nassyr +1 more
code/data similarity 0.53
Abstract · Accepted for International workshop on RISC-V for HPC at ISC26

This manuscript presents a performance evaluation of Fast Fourier Transform (FFT) implementations on emerging processors supporting the RISC-V Vector Extension (RVV 1.0). By introducing juFFTe, a light-weight high-performance library for discrete Fourier transforms, it is demonstrated how effective vectorization of performance-critical FFT kernels can be achieved on RVV-enabled hardware. Comprehensive benchmarks on three RVV 1.0-ready processors, the SiFive X280, the X100 core of the SpacemiT K3 and the C920v2 core of the Sophon SG2044, reveal substantial performance improvements of juFFTe (https://github.com/FZJ-JSC/juFFTe) over the widely used FFTW3 library. Although RVV-enabled platforms show promising results at this stage of development, a comparison with AMD's Zen 5 architecture indicates that RISC-V needs further maturing to reach the performance of established micro-architectures.

0.64

ConfluxServe: Reconciling Resource Utilization and Parallelism Efficiency across Prefill and Decode in LLM Serving

cs.DC ·2026-10-27 ·Wenhao Chen, Hong Zhang
similarity 0.53
Abstract · 20 pages, 18 figures

Prefill and decode are complementary in resource usage, but often divergent in parallelism preferences. Executing the two phases separately preserves their preferred parallelism but leaves complementary resources underutilized, while co-batching improves utilization but often requires a uniform parallel configuration that hurts execution efficiency. To resolve this utilization-efficiency dilemma, we propose Conflux Parallelism (XP), a parallel execution abstraction that co-executes prefill and decode with different parallelism within the same batch. Conflux Parallelism exploits operator-level Transformer structure to construct a heterogeneous execution path with different batching and parallelism strategies across operators, combining the best of co-batching and phase-specific execution. Building on Conflux Parallelism, we design ConfluxServe, an SLO-aware serving system that maximizes cluster goodput under TTFT and TBT constraints. Evaluation on production workloads shows that ConfluxServe improves serving goodput by 1.26-1.62x over the strongest baselines.

0.26

NITRO: High-Performance 3D NAND Flash-Based In-Storage Computing with Enhanced Activation Dataflow

cs.AR ·2026-08-12 ·Sanghun Shin, Sangyeon Kim, Gisan Ji, Sungju Ryu
published similarity 0.53
Abstract · Extended manuscript of DATE 2026

In-storage computing (ISC) is considered a next-generation memory architecture for its ability to relieve the data bottleneck between the host and the memory. While the required resources of large language models (LLMs) have increased significantly in recent years, the memory density has not scaled accordingly. Recently, several works have studied NAND flash-based processing-in-memory (NAND-PIM) schemes to exploit the high density of the memory. However, they do not address the dataflow/buffer for the intermediate values, so a simple method is to deal with the values in the slow flash memory array. To overcome such a limitation, we propose a high-performance NAND flash-based ISC architecture with enhanced activation buffering. Instead of using the very slow flash memory array for the intermediate values, our architecture buffers the values in a fast DRAM subsystem. This approach effectively handles the high-latency penalties when activations are programmed into slower TLC NAND flash. We also introduce a distributed dataflow approach for the NAND-PIM array. This approach maximizes computational parallelism by employing efficient intra-plane data mapping. The results show that our proposed architecture achieves significant performance improvements, reducing the inference latency by up to 85% compared to the baseline.

0.17

CHARM+: Cross-Hardware Attention with Re-Merge Multistream Mechanism

cs.AI cs.ARcs.DC ·2026-11-04 ·Xinhang Zhang, Boning Zhang, Chengchun Liu, Chunpu Li, Lei Sun +2 more
publishedhot direction similarity 0.52
Abstract · Accepted to NeurIPS 2026 (Poster)

As sequence lengths continue to grow, distributed attention based on sequence parallel (e.g., Ring-Attention) has become a mainstream solution for large language models (LLMs). Nevertheless, inherent communication dependencies limit computation-communication overlap, reducing GPU utilization. Moreover, in cross-hardware (NUMA or node) architectures, due to imbalanced communication bandwidth, frequent communication synchronization will limit overall performance. Based on these insights, we propose CHARM+, Cross-Hardware Attention with Re-Merge Multistream Mechanism. We reorganize sequential communications into several levels and achieve intra-level parallelism and computation overlap. Furthermore, we decouple cross-hardware communication from intra-hardware communication, eliminating synchronization overhead caused by bandwidth imbalance. Forward and backward algorithms were evaluated on multiple hardware architectures and consistently outperformed state-of-the-art methods. Compared to Ring-Attention, our forward and backward algorithms achieve average speedups of 1.3x and 1.7x on a dual-NUMA PCIe architecture, and 2.8x and 2.9x on a dual-node NVLink architecture, respectively.

0.35

Falcons: Pushing the Speed-Ratio Limits of Lossy Compression for Parallel Scientific Applications

cs.DC ·2026-10-30 ·Bing Lu, Jinyang Liu, Xinyang Ma, Quantong Fu, Chenwei Hou +11 more
similarity 0.52
Abstract

The extreme volume of scientific data has become a critical challenge for modern exa-scale scientific computing applications, and error-bounded lossy compression remains indispensable for scientific data management due to its high data reduction rate and controllable data fidelity. However, to ensure sufficient data reduction, existing compressors incur prohibitive computational overheads in real-world parallel scientific computing applications. To overcome the performance bottlenecks of error-bounded lossy compression, we present \textbf{Falcons}, a broadly deployable error-bounded lossy compressor that simultaneously achieves \textbf{high compression ratios with ultra-fast throughput, minimizing the overhead in parallel scientific applications}. Falcons integrates three key designs: memory-regularized interpolation with SIMD (Single Instruction Multiple Data) vectorization, distribution-adaptive lossless coding, and application-oriented optimizations for multiple parallelization schemes. Across our evaluations on cutting-edge supercomputers, Falcons clearly outperforms state-of-the-art compressors, simultaneously achieving up to 29\% compression ratio improvement and 255\% throughput improvement. In case studies of real-world applications, Falcons accelerates large-scale parallel data I/O and remote transfer by up to 44.6\% and 51.5\%, and provides 1.55$\times$ end-to-end speedup for the full WRF (Weather Research \& Forecasting) application workflow.

0.08

Bandwidth, Not FLOPS: FFT Kernels, Matrix Units and SAR Imaging on Apple M6

cs.PF cs.AR ·2026-09-26 ·Mohamed Amine Bergach
hot direction similarity 0.50
Abstract

The fast Fourier transform (FFT) underlies radar, imaging and scientific computing. A classic rule for fast GPU FFTs is to compute the largest block that fits on chip and compose larger transforms from such blocks. We test this rule on Apple's M6 chip, whose GPU performs 29 arithmetic operations in the time it reads one byte from main memory, and which adds matrix units to both its GPU and CPU. Comparing our kernels with Apple's MPSGraph and vDSP libraries and MLX, we find that data movement, not arithmetic, sets FFT speed. Large batches run at or near the main-memory bandwidth limit in every GPU library, and benchmarks that keep data in cache overstate real throughput by up to $3.7\times$. The on-chip rule still predicts where speed collapses: MPSGraph and MLX lose half or more of their speed once a transform outgrows the GPU's 32\,KiB local memory. Keeping such transforms in registers avoids an extra trip through memory: $2.2\times$ faster than MPSGraph, and $4.4\times$ with half-precision storage. The GPU's matrix units do not help, because recasting the FFT as matrix products adds as much arithmetic as they save. The CPU's matrix unit, 47 times faster than its vector units, does: our kernel for it beats vDSP by up to $5.3\times$. End to end, a $4096\times4096$ synthetic aperture radar image takes 8.1\,ms on the GPU (6.0\,ms with half-precision intermediates), $14$--$19\times$ faster than a CPU reference. Running the CPU's matrix unit alongside the GPU gains nothing: both share one memory bandwidth.

0.32

PACO: A Fully Cache-Oblivious Parallel FFT with One Global Redistribution

cs.DS cs.DC ·2026-09-06 ·Shina Guo, Weiguo Gao, Yuan Tang
similarity 0.50
Abstract · 11 pages, 1 figure, with about 10 appendices as supplementary materials

Fast Fourier transforms on parallel machines incur two forms of data movement: processor-local transfers through the memory hierarchy and global redistribution between processors. Four-step FFT organizations switch the active transform dimension with one global transpose-like exchange, but this alone does not yield cache-efficient local computation. Cache-oblivious FFTs achieve asymptotically optimal local memory traffic through recursive layout transformations, whose direct materialization can require extra data-rearrangement passes and global exchanges. We present PACO, a fully cache-oblivious parallel FFT framework that reconciles these objectives. PACO executes LocalFFT -> OneGlobalPermutation -> LocalFFT. Its local stages recursively partition both transform and batch dimensions without knowledge of the cache parameters. Rather than materializing the transpose-like layouts induced by this recursion, PACO defers them, showing that they compose into a base-b digit-reversal permutation that is fused with the redistribution already required to change the local transform dimension. The resulting middle stage is a perfectly balanced parallel cache-oblivious digit-reversal permutation in which each source-destination processor pair exchanges exactly $N/p^2$ elements. Under an exact base-b slab decomposition in a hybrid ideal-cache/BSP model, PACO computes an N-point DFT exactly with maximum per-processor work $Θ((N/p) \log N)$ and maximum per-processor cache complexity $Θ((N/(pB))(1 + \log_M N))$, using exactly one global redistribution round. PACO returns canonical logical DFT coefficients under a factor-swapped target slab ownership. The single redistribution is necessary under the stated no-replication ownership model, while its communication volume is optimal for the prescribed fused permutation and source-target slab distributions.

0.23