Parallel Cascaded Recursive Filtering on Multi-Core CPUs and GPUs

당신이 가장 좋아하는 노래의 노이즈를 제거하려고 하거나, 혹은 환경에 즉각적으로 반응해야 하는 로봇을 만들고 있다고 상상해 보십시오. 두 경우 모두, 좋은 소리와 나쁜 소리를 분리하기 위한 디지털 "필터"가 필요합니다. 이 작업을 수행하는 가장 강력한 도구는 **재귀 필터(recursive filters)**라고 불립니다. 이것은 마치 마법 같은 에코 챔버와 같습니다. 다음 소리가 무엇인지 알아내기 위해, 필터는 현재의 소리와 방금 전 자신이 만들어낸 소리들을 되돌아봅니다. 이러한 "되돌아보기"는 매우 적은 컴퓨터 자원을 사용하면서도 복잡한 작업을 수행할 수 있게 하여 이들을 매우 효율적으로 만듭니다. 하지만 여기에는 함정이 있습니다. 각 새로운 소리가 이전의 소리에 의존하기 때문에, 필터는 마치 긴 복도를 따라 걷는 한 사람처럼 단계별로 작업해야 합니다. 이는 고화질 비디오나 실시간 라디오와 같이 방대한 양의 데이터를 처리해야 할 때 병목 현상을 일으켜 속도를 늦춥니다.

수십 년 동안 과학자들은 이를 가속화하기 위해 더 많은 컴퓨터가 돕도록 노력해 왔습니다. 문제는 여러 대의 컴퓨터로 작업을 나누면, 모든 컴퓨터가 앞사람의 단계가 끝나기를 기다려야 하기 때문에 혼란에 빠진다는 점입니다. 이는 마치 주자들이 서로 다른 트랙에 서 있더라도 바톤을 받기 위해 기다려야 하는 계주와 같습니다. 이 논문은 바로 그 문제를 다룹니다. 이 논문은 이미 단일 초고속 컴퓨터 칩에서 작동하는 것으로 증명된 영리한 수학적 기법을 가져와, 이를 현대적인 멀티 코어 컴퓨터와 강력한 그래픽 카드(GPU)에서 실행되도록 확장했습니다. 저자들은 이 컴퓨터들이 서로 기다리지 않고 협력하게 만드는 방법을 찾아냈으며, 이를 통해 이 유형의 수학 계산에서 이전에는 불가능하다고 여겨졌던 속도를 구현하여 느린 일렬 행렬을 고속 다차선 고속도로로 바꾸어 놓았습니다.

계주 문제와 마법의 기술

이 혁신을 이해하기 위해, 이 필터들이 보통 어떻게 작동하는지 살펴보겠습니다. 메시지를 전달하는 긴 줄의 사람들이 있다고 상상해 보십시오. 각 사람은 자신의 부분을 추가하여 전달하기 전에 앞사람이 메시지를 속삭여 줄 때까지 기다려야 합니다. 이것이 "재귀적"인 부분입니다. 줄이 길어지면 메시지가 끝에 도달하는 데 오랜 시간이 걸립니다.

이 논문의 저자들은 긴 사슬을 더 빠르게 처리할 수 있는 작은 덩어리, 즉 "블록"으로 나누는 방법을 이미 찾아냈습니다. 하지만 이 블록들을 여러 컴퓨터(예: 작업 팀)에 동시에 배정하려고 했을 때 새로운 문제가 발생했습니다. 한 블록의 끝이 다음 블록의 시작점이기 때문입니다. 만약 작업자 1에게 블록 A를 주고 작업자 2에게 블록 B를 준다면, 작업자 2는 작업자 1이 블록 A를 마칠 때까지 기다려야 합니다. 결국 팀 전체가 여전히 하나씩 순서대로 작업하게 되어, 팀을 구성하는 목적이 무색해집니다.

이 논문의 주요 발견은 **중첩(superposition)**이라 불리는 수학적 "마법의 기술"입니다. 이전 블록으로부터의 답을 기다리는 대신, 작업자들은 0에서 시작했을 때의 답이 무엇일지 "추측(zero-state guess)"합니다. 그들은 이 계산을 즉시 수행합니다. 그런 다음, 이전 작업자로부터 오는 실제 시작 숫자를 기다립니다. 일단 숫자가 도착하면, 그들은 자신의 추측값에 작은 "보정치"를 더하기만 하면 됩니다. 이는 마치 요리사가 아직 재료가 없다고 가정하고 레시피에 따라 수프를 만들기 시작하는 것과 같습니다. 마침내 배달 트럭이 실제 채소를 떨어뜨려 놓으면, 요리사는 그저 채소를 넣고 저어주기만 하면 됩니다. 이미 병렬적으로 요리 과정의 힘든 작업이 완료되었기 때문에 수프는 거의 즉시 완성됩니다.

경주를 실행하는 두 가지 다른 방법

이 논문은 당신이 무엇을 하려느냐에 따라 이 마법의 기술을 두 가지 매우 다른 방식으로 사용할 수 있음을 보여줍니다.

1. 실시간 스트림 (조립 라인)
라디오 방송과 같이 실시간 데이터를 처리하는 경우, 다음 몇 초의 오디오를 재생하기 위해 전체 배치가 끝날 때까지 기다릴 수 없습니다. 데이터가 들어온 순서 그대로(First-In, First-Out) 나와야 합니다.

• 해결책: 저자들은 멀티 코어 CPU를 위한 "웨이브프런트 파이프라인(wavefront pipeline)"을 구축했습니다. 여러 명의 작업자가 동일한 곡의 서로 다른 단계를 동시에 처리하는 조립 라인을 상상해 보십시오. 작업자 1은 베이스를 정리하고, 작업자 2는 보컬을 수정하며, 작업자 3은 에코를 추가합니다. 작업자 1이 한 덩어리를 마치면 작업자 2에게 전달하고, 작업자 2는 작업자 3에게 전달합니다.
• 결과: 6개의 강력한 코어를 가진 현대적인 컴퓨터에서, 이 방식은 복잡한 16차 필터에 대해 2.4 Gigasamples per second의 속도를 달성했습니다. 이는 단일 코어를 사용하는 것보다 거의 4배 더 빠른 속도입니다. 흥미롭게도, 그들은 더 느린 "효율성" 코어를 섞는 것이 오히려 전체 라인의 속도를 늦춘다는 것을 발견했으며, 이는 이 특정 작업에는 많은 느린 작업자보다 소수의 빠른 작업자가 더 낫다는 것을 증명합니다.

2. 배치 프로세싱 (공장)
영화나 데이터베이스와 같이 기록된 방대한 파일 데이터를 처리하는 경우, 순서보다는 순수한 속도가 중요합니다. 파일을 한꺼번에 처리할 수 있습니다.

• 해결책: 그들은 수천 명의 작은 작업자를 가진 강력한 그래픽 처리 장치(GPU)를 사용했습니다. 그들은 **디커플드 룩백(decoupled lookback)**이라는 기술을 사용했습니다. 모든 작업자가 제품의 각 부분을 즉시 계산하는 공장을 상상해 보십시오. 만약 어떤 작업자가 이전 스테이션으로부터 부품이 필요하다면, 그들은 멈추지 않습니다. 대신 "상태 게시판"을 확인하여 이전 스테이션이 완료되었는지 확인합니다. 완료되었다면 부품을 가져갑니다. 완료되지 않았다면, 준비될 때까지 다른 일을 계속합니다.
• 결과: 이 접근 방식은 믿을 수 없을 정도로 빨랐습니다. NVIDIA RTX 3060 그래픽 카드에서, 시스템은 단일 필터 섹션에 대해 38.2 Gigasamples per second에 도달했습니다. 이는 하드웨어가 이론적으로 낼 수 있는 최대 속도(메모리 대역폭 한계)의 **85%**에 달하는 수치입니다.

이것이 왜 중요하며 무엇을 능가하는가

저자들은 단순히 속도를 높인 것이 아니라, 그들의 방법이 기존 방식보다 더 신뢰할 수 있다는 것을 증명했습니다.

• "직접 형식(Direct Form)"의 실패: 하나의 거대한 단계로 수학을 처리하려는 "직접 형식"이라는 오래된 방법이 있습니다. 이 논문은 복잡한 필터(예: 16차 필터)의 경우 이 오래된 방식이 무너진다는 것을 보여줍니다. 숫자들이 너무 엉망이 되어 컴퓨터가 쓰레기 결과를 내놓거나 충돌을 일으키기 시작합니다. 이 논문에서 사용된 새로운 "캐스케이드(cascaded)" 방식은 이러한 높은 수준에서도 정확도를 유지합니다.
• 경쟁자와의 비교: 그들은 자신들의 새로운 GPU 코드를 기존에 존재하는 가장 강력한 병렬 필터 엔진들과 비교했습니다. 그들의 방식은 테스트된 모든 필터 차수에서 더 빨랐습니다.
• 속도의 비용: 논문은 또한 이 속도의 "비용"을 면밀히 측정했습니다. 그들은 최신형의 더 빠른 칩(예: RTX 3060)에서는 "장벽(barrier, 작업자가 진행할 수 있는지 확인하는 절차)"이 저렴하기 때문에 더 복잡하고 빠른 방법을 사용할 수 있다는 것을 발견했습니다. 반면 구형 칩에서는 이러한 확인 절차가 비용이 많이 들기 때문에 더 단순한 방법을 사용해야 합니다. 이는 엔지니어들이 서로 다른 하드웨어에 맞춰 소프트웨어를 어떻게 튜닝해야 하는지 정확히 알 수 있도록 도와줍니다.

결론

이 논문은 어려운 순차적 수학 문제를 병렬 파티로 바꾸어 놓았습니다. "추측하고 보정하는" 전략을 사용하여, 컴퓨터들이 서로 기다리지 않고 협력할 수 있게 했습니다.

• 실시간 스트리밍의 경우, 일반적인 컴퓨터에서 3.95배 더 빠른 파이프라인을 구축했습니다.
• 배치 프로세싱의 경우, 38.2 Gigasamples per second를 달성하는 GPU 엔진을 구축하여 엄청난 도약을 이루었습니다.
• 결정적으로, 그들은 이 방법이 단순히 더 빠를 뿐만 아니라, 기존 방식이 실패하는 지점에서도 정확도를 유지하며 더 뛰어나다는 것을 입증했습니다.

저자들은 자신들의 코드를 오픈 소스 라이브 library로 공개하여, 누구나 이 초고속 필터를 사용하여 더 나은 오디오 도구, 더 선명한 비디오, 더 똑똑한 로봇을 만들 수 있게 했습니다. 그들은 "순차적"인 병목 현상을 "병렬" 초고속도로로 바꿈으로써, 아무리 고집스러운 수학 문제라도 컴퓨터 팀이 서로 조화를 이루며 협력하게 함으로써 해결할 수 있음을 보여주었습니다.