Как параллельные вычисления ускоряют фильтры: урок от галактик экспресс
Традиционный фильтр работает как длинная цепочка людей, передающих сообщение по кругу: каждый ждёт, пока предыдущий закончит. Это медленно. Инженеры применили хитрый метод — циклическую редукцию. Данные переставляют так, что зависимости между отсчётами становятся не длинными, а собранными в маленькие группы. Теперь процесс напоминает игру в испорченный телефон, где после каждого раунда число участников сокращается вдвое: информацию объединяют, и она быстро доходит до всех. Этот трюк позволяет современным процессорам, вроде чипов Meteor Lake, обрабатывать несколько сигналов одновременно, как множество коротких телефонных линий вместо одной длинной. Технология AVX2 ускоряет счёт, как скорость света в оптоволокне по сравнению с медным кабелем. Пионеры параллельных вычислений Джон фон Нейман и Джон Бардин заложили основы для таких архитектур. В результате фильтр 16-го порядка обрабатывает до 618 миллионов отсчётов в секунду на одном ядре — в 8 раз быстрее стандартных решений. Это шаг к мгновенной обработке аудио и сигналов в науке, например, при изучении пульсара или спектроскопии далёких галактик.
Оригинальная аннотация
как её написали авторы, на английском 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.
Одно процессорное ядро Meteor Lake за секунду фильтрует столько сигналов, сколько сердечных сокращений за то же время у 60 слонов.