How Parallel Computing Speeds Up Filters: A Lesson from Galaxies express
A traditional filter works like a long chain of people passing a message around: each waits for the previous one to finish. That's slow. Engineers applied a clever method — cyclic reduction. They rearrange data so that dependencies between samples become not long chains but small groups. Now the process resembles the game of Telephone, where after each round the number of participants is halved: information is merged and quickly reaches everyone. This trick allows modern processors, like Meteor Lake chips, to process several signals simultaneously, like many short phone lines instead of one long one. AVX2 technology speeds up calculation like the speed of light in optical fiber compared to copper wire. Pioneers of parallel computing John von Neumann and John Bardeen laid the groundwork for such architectures. As a result, a 16th-order filter processes up to 618 million samples per second on a single core — 8 times faster than standard solutions. It's a step toward instant audio and signal processing in science, for instance when studying pulsars or spectroscopy of distant galaxies.
Original abstract
as written by the authors arXiv:2607.14054
Recursive (IIR) filters realized as cascaded second-order sections (biquads) offer both design generality and robustness against coefficient quantization. However, their inherent sample-to-sample feedback dependency poses a fundamental obstacle to parallel computation. This paper reformulates the biquad difference equation as a banded block-Toeplitz linear system and introduces a stride-$$N$$ permutation that maps a group of $$NL$$ samples into a block-tridiagonal structure whose entries are scalar multiples of identity and shift matrices. Within this framework, two parallel algorithms are developed for the recursive solution: a partial LU (PH) factorization that preserves the sparse block structure and a cyclic reduction that is applied to recursive filtering, to the best of our knowledge, for the first time. It reduces the sequential dependency depth from $$\mathcal{O}(N)$$ to $$\mathcal{O}(\log_2 N)$$. For a cascade of $$K$$ biquads, the intermediate permutations between successive sections cancel exactly, so that only a single permutation/de-permutation pair is required for the entire cascade, eliminating $$2(K{-}1)$$ redundant stages. Exact block-level operation counts are derived for every algorithmic stage and validated against cycle-accurate measurements on three Intel micro-architectures supporting AVX2 SIMD instructions. Experimental results for a 16th-order system show that the proposed multi-block algorithms reduce clock cycles per sample by up to $$10\times$$ compared to scalar filtering, with both algorithms scaling favorably on newer architectures. On a single Meteor Lake core, cyclic reduction achieves approximately 618 MS/s -- an $$8\times$$ throughput improvement over scipy.signal.sosfilt.
A single Meteor Lake processor core filters as many signals per second as the combined heartbeats of 60 elephants.