⚡ electrical engineering

Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation

이 논문은 부분 LU 분해(partial LU factorization)와 순환 감소(cyclic reduction)를 통해 고도의 병렬 처리를 가능하게 하는 직렬 2차 IIR 필터의 블록 행렬 재구성을 도입하며, 이를 통해 순차적 의존성 깊이를 $\mathcal{O}(N)$ 에서 $\mathcal{O}(\log_2 N)$ 으로 줄임으로써 기존의 스칼라 방식 대비 최대 10배의 속도 향상을 달성한다.

원저자: Haotian Zhai, Bernd-Peter Paris

게시일 2026-07-16

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Haotian Zhai, Bernd-Peter Paris

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 아주 오래되고 약간 고장 난 라디오로 가장 좋아하는 노래를 들으려고 한다고 상상해 보세요. 가끔 소리가 흐릿하거나 이상한 웅웅거리는 소리가 들릴 때가 있습니다. 이를 해결하기 위해 엔지니어들은 **필터(filter)**라고 불리는 특별한 수학적 도구를 사용합니다. 필터를 소리를 거르는 체(sieve)라고 생각하면 쉽습니다. 필터는 좋은 소리는 통과시키되, 원치 않는 잡음과 정전기는 잡아냅니다. 이 체를 만드는 데는 두 가지 주요 방법이 있습니다. 한 가지 방법은 수많은 단순한 거름망(FIR 필터라고 불림)을 쌓아 올리는 것과 같습니다. 이는 매우 신뢰할 수 있지만, 물을 통과시키기 위해 많은 노력이 필요합니다. 하지만 이 논문이 집중하고 있는 다른 한 가지 방법은 영리하고 스스로 교정되는 루프(IIR 또는 재귀적 필터라고 불림)를 사용하는 것입니다. 이 루프는 매우 효율적이어서, 동일하게 깨끗한 소리를 얻는 데 훨씬 적은 부품이 필요합니다.

하지만 여기에는 함정이 있습니다. 이 효율적인 루프는 "직렬(serial)" 과정이라는 점입니다. 사람들이 줄을 서서 물 양동이를 전달하는 상황을 상상해 보세요. 사람 A가 양동이를 채우기 전까지는 사람 B에게 전달할 수 없고, 사람 B가 양동이를 채우기 전까지는 사람 C에게 전달할 수 없습니다. 단순히 사람을 더 많이 투입한다고 해서 속도를 높일 수는 없습니다. 왜냐하면 모든 사람이 앞사람을 기다려야 하기 때문입니다. 컴퓨터의 세계에서 이 "기다림"은 병목 현상을 일으키며, 특히 실시간 비디오나 고속 인터넷처럼 방대한 양의 데이터를 처리해야 할 때 속도를 늦춥니다. 핵심적인 질문은 이것입니다. 인과관계의 사슬을 깨뜨리지 않으면서, 어떻게 하면 이 효율적이고 스스로 교정되는 루프를 동시에 여러 작업을 수행하는 방식으로 더 빠르게 만들 수 있을까?

"Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation"이라는 제목의 이 논문은 바로 그 문제를 다룹니다. 저자인 하오티안 자이(Haotian Zhai)와 베른트-페터 파리스(Bernd-Peter Paris)는 데이터가 한 번에 하나씩 지나가는 긴 줄 형태가 아니라, 데이터 전체를 하나의 커다란 **블록(block)**으로 묶어 하나의 복잡한 퍼즐처럼 취급하면 된다는 사실을 깨달았습니다.

그들은 데이터를 특정 패턴으로 카드 덱을 섞는 것처럼 재배열하여, 지루하게 기다려야 하는 줄을 깔끔하고 조직적인 구조로 바꾸는 영리한 방법을 발견했습니다. 일단 데이터가 이 새로운 형태를 갖추면, 그들은 퍼즐을 풀기 위해 두 가지 다른 "초고속" 전략을 적용했습니다.

"부분 LU" 전략 (PH Factorization): 이 방법은 퍼즐 조각들을 깔끔하고 희소한 상자 안에 그대로 유지하는 스마트한 조립 라인과 같습니다. 이 방식은 문제를 "특정(specific)" 부분(입력이 어떤 모습인지)과 "일반(general)" 부분(시스템이 어떻게 반응하는지)으로 나누어, 보통의 처리를 느리게 만드는 무겁고 복잡한 수학 연산을 피하며 해결합니다.
"순환 축소(Cyclic Reduction)" 전략: 이것이 진정한 주인공입니다. 1,000명의 사람이 줄을 서서 양동이를 전달하는 상황을 상상해 보세요. 전체 줄이 다 끝날 때까지 기다리는 대신, 이 방법은 사람들을 짝지어 주고, 그 쌍들의 결과를 다시 짝지으며, 전체 줄이 완료될 때까지 속도를 배로 높여가며 해결합니다. 마치 거대한 종이를 아주 작아질 때까지 계속해서 반으로 접는 것과 같습니다. 저자들이 이 유형의 필터링에 처음으로 적용한 이 기술은 "기다리는 시간"을 샘플 수에 비례하는 것이 아니라 샘플 수의 *로그(logarithm)*에 비례하도록 줄여줍니다. 쉽게 말해, 데이터 양이 두 배가 되어도 처리 시간은 두 배가 되는 것이 아니라, 시간이 거의 늘어나지 않습니다.

또한 이 논문은 "직렬 연결된(cascaded)" 필터의 까다로운 문제도 해결했습니다. 보통 여러 개의 필터를 쌓을 때(여러 개의 체를 쌓는 것처럼), 각 필터 사이에서 데이터를 주고받으며 시간을 낭비하게 됩니다. 저자들은 자신들의 새로운 방법을 사용하면 필터 사이의 이러한 데이터 이동이 완벽하게 상쇄된다는 것을 보여주었습니다. 이는 마치 문을 지날 때마다 신발을 갈아 신어야 하는데, 문들이 배치된 방식 덕분에 신발을 갈아 신기 위해 멈출 필요가 전혀 없어진 것과 같습니다.

이것이 단지 종이 위의 멋진 아이디어에 불과하다는 것을 증명하기 위해, 저자들은 실제 컴퓨터 칩(구체적으로 Intel 프로세서)에서 테스트를 진행했습니다. 그 결과, 복잡한 16차 필터에 대해 새로운 "순환 축소" 방식이 오늘날 사람들이 사용하는 표준 소프트웨어(예: scipy.signal.sosfilt 도구)보다 약 8배 빠르고, 데이터를 한 번에 하나씩 처리하는 기존의 느린 방식보다 최대 10배 빠르다는 것을 발견했습니다. 현대적인 컴퓨터 칩에서 이 새로운 방식은 초당 6억 1,800만 개 이상의 샘플을 처리할 수 있었습니다.

저자들은 시뮬레이션이 아닌 실제 하드웨어의 클록 사이클을 측정했기 때문에 이 결과에 매우 확신하고 있습니다. 그들은 "부분 LU" 방식이 적은 양의 데이터를 처리할 때 유용하다면, "순환 축소" 방식은 엄청난 양의 데이터를 처리할 때 독보적인 성능을 발휘하며, 이는 실시간 비디오 처리나 첨단 통신 시스템과 같은 고속 애플리케이션 분야에서 게임 체인저가 될 수 있음을 보여주었습니다. 그들은 또한 이 코드를 오픈 소스로 공개하여 다른 이들도 사용할 수 있게 함으로써, 강력한 필터를 일상적인 기술에 빠르고 실용적으로 적용할 수 있는 중요한 진전을 이루었습니다.

기술 요약: 블록 행렬 재구성을 통한 빠른 직렬 연결된 재귀적 필터링

문제 정의
직렬 연결된 2차 섹션(biquad)으로 구현된 재귀적(IIR) 필터는 설계의 일반성과 계수 양자화에 대한 견고함 덕분에 디지털 신호 처리의 표준으로 자리 잡고 있다. 그러나 본질적인 샘플 간 피드백 의존성은 효율적인 병렬 계산을 방해하는 순차적 병목 현상을 생성한다. 기존 연구들은 병렬 직접 형태(direct-form) 필터를 탐색하거나 FFT 기반 근사법을 활용해 왔으나, 이러한 접근 방식들은 안정성을 보장하지 못하거나 직렬 연결된 여러 biquad가 도입하는 특유의 복잡성을 해결하지 못한다. 기존의 병렬 알고리즘들은 대부분 직렬 연결 구조를 무시하고 필터를 단일 직접 형태 엔티티로 취급하며, 이로 인해 직렬 연결의 계산 오버헤드를 해결하지 못하는 문제를 남긴다.

방법론
저자들은 블록 내부 및 블록 간 수준 모두에서 병렬성을 노출하기 위해 직렬 연결된 2차 IIR 필터에 대한 블록 행렬 재구성을 제안한다. 핵심 방법론은 다음과 같다:

행렬 재구성: biquad 차분 방정식을 밴드형 블록-토플리츠(banded block-Toeplitz) 선형 시스템으로 변환한다. $NL $개의 샘플 그룹에 스트라이드-$ N$ 치환(stride- $N$ permutation)을 적용하여, 시스템을 블록 삼중 대각(block-tridiagonal) 구조로 변환한다. 이 행렬의 항목들은 항등 행렬( $I$ )과 하부 이동(lower shift, $R$ ) 행렬의 스칼라 배로 구성된다.
병렬 솔버(Solvers): 결과로 도출된 재귀적 단계를 해결하기 위해 두 가지 병렬 알고리즘을 개발한다:
- PH 인자 분해 (Partial LU): 이 방법은 표준 LU 분해에서 발생하는 조밀한(dense) 행렬을 피함으로써 시스템의 희소 블록 구조를 보존한다. 이는 특수해(particular solution)를 전방 대입법으로 계산하고, 제차 보정(homogeneous correction)을 터미널 블록을 통해 적용하는 특수/제차 분해를 활용한다. 터미한 블록은 순차적 깊이를 줄이기 위해 블록 수준의 재귀적 배가(Sklansky construction)를 사용하여 해결된다.
- 순환 축소 (Cyclic Reduction): 재귀적 필터링에 처음으로 적응 적용된 이 기술은 교대되는 블록들을 체계적으로 제거하여 시스템 크기를 절반으로 줄인다. 이를 통해 순차적 의존성 깊이를 $O(N)$ 에서 $O(\log_2 N)$ 으로 감소시킨다.
직렬 연결 최적화: $K$ 개의 biquad로 구성된 직렬 연결에 대해, 저자들은 한 섹션의 출력에서 필요한 스트라이드- $N$ 치환과 다음 섹션의 입력에서의 역치환이 정확히 상쇄됨을 입증한다. 결과적으로 전체 직렬 연결의 시작 부분에서 단 한 번의 치환과 끝 부분에서 단 한 번의 역치환만 필요하게 되어, $2(K-1)$ 개의 불필요한 단계를 제거한다.

주요 기여

블록 행렬 문제 정식화: 2차 재귀 필터를 밴드형 블록-토플리츠 시스템으로 정식화하여 멀티 블록 필터링 알고리즘을 적용할 수 있는 체계적인 대수적 프레임워크를 제공한다.
PH 인자 분해: 특정/제차 분해를 2차 섹션으로 확장하여, 희소 블록 구조를 유지하면서 재귀적 배가를 사용하여 터미널 블록을 해결한다.
IIR을 위한 순환 축소: 재귀적 필터링에 순환 축소를 최초로 적용하여, 표준 인자 분해 방식의 $O(N)$ 깊이에 비해 $O(\log_2 N)$ 의 순차적 의존성 깊이를 달려낸다.
직렬 연결 비용 분담: 직렬 연결된 biquad들 사이의 중간 치환이 상쇄됨을 증명하여, 필터 차수가 높아짐에 따라 당당한 성능 향상을 가져오는 per-biquad 오버헤드를 크게 줄인다.
복잡도 분석 및 검증: 정확한 블록 수준 연산 횟수(FMA 및 shuffle 연산)를 도출하고 세 가지 Intel 마이크로아키텍처(Haswell, Skylake, Meteor Lake)에서의 사이클 정확도 측정값과 비교 검증하였다.

실험 결과
제안된 알고리즘은 SIMD 벡터 명령(AVX2)을 사용하는 C++로 구현되었으며, 16차 직렬 연결 IIR 필터 시스템에서 평가되었다.

성능 이득: 단일 Meteor Lake 코어에서, 순환 축소 알고리즘은 약 618 MS/s (Million Samples per second)의 처리량을 달성했다. 이는 표준 scipy.signal.sosfilt 구현(약 77 MS/s로 동작) 대비 8배의 처리량 향상을 나타내며, 스칼라 필터링 대비 최대 10배의 클록 사이클 감소를 보여준다.
확장성: 제안된 알고리즘은 최신 아키텍처에서 유리하게 확장된다. PH 인자 분해는 더 작은 샘플 크기에 대해 낮은 지연 시간을 제공하는 반면, 순환 축소는 감소된 순차적 깊이 덕분에 큰 샘플 크기에서 우수한 처리량을 달성한다.
효율성: 멀티 블록 알고리즘은 스칼라 필터링에 비해 클록 사이클을 최대 10배까지 성공적으로 줄였으며, 순환 축소 방식이 큰 블록 크기($NL = 512$)에서 가장 좋은 성능을 보였다.

의의 및 주장
본 논문은 실무에서 지배적인 구현 전략인 IIR 필터의 직렬 연결된 2차 구현을 위해 특별히 설계된 병렬 알고리즘을 제공함으로써 문헌의 중요한 공백을 메운다고 주장한다. 문제를 블록 삼중 대각 시스템으로 재구성함으로써, 저자들은 기존의 순차적 의존성 때문에 접근할 수 없었던 병렬성을 노출시켰다.

저자들은 본 연구가 알고리즘 이론과 단일 코어 SIMD 검증에 초점을 맞춘 2부작 연구 중 첫 번째 부분임을 강조한다. 이들은 수치적 정확도와 높은 처리량을 결다는 범용 하드웨어에서 직렬 연결된 2차 형태의 병렬 IIR 필터링을 제공하는 최초의 오픈 소스 라이브러리를 출시했다고 주장한다. 또한, 본 연구는 단일 코어 가속을 달성과 함께, 고처리량 배치 처리 및 저지연 실시간 시나리오를 위한 멀티 코어 및 GPU 구현을 다룰 후속 논문을 통해 범위를 확장할 것임을 명시하며 연구의 범위를 겸허히 설정하였다. 결과는 제안된 방법이 직렬 연결 형태의 설계 유연성이나 안정성을 해치지 않으면서도, 재귀적 필터링 고유의 순차적 병목 현상을 효과적으로 완화함을 확인시켜 준다.

유사한 논문