Parallel Cascaded Recursive Filtering on Multi-Core CPUs and GPUs

お気に入りの曲のノイズを除去しようとしていたり、あるいは環境に即座に反応する必要があるロボットを構築していたりすると想像してみてください。どちらの場合も、良い音と悪い音を分けるためのデジタルな「フィルター」が必要です。この仕事において最も強力なツールは、「再帰的フィルター（recursive filters）」と呼ばれるものです。これらは、魔法のエコーチェンバーのようなものだと考えてください。次の音がどうなるべきかを判断するために、フィルターは現在の音だけでなく、少し前の瞬間に自分が作り出した音も振り返って確認します。この「振り返る」という動作によって、非常に少ない計算能力で複雑な作業を行うことができ、驚異的な効率性を実現しています。しかし、一つ落とし穴があります。各新しい音がその前の音に依存しているため、フィルターは一歩ずつ進む必要があり、まるで長い廊下を一人で歩いているようなものです。これがボトルネックとなり、高精細ビデオやリアルタイムの無線通信のように、膨大なデータを処理する必要がある場合に、すべてを遅らせてしまいます。

何十年もの間、科学者たちはこれを高速化するために、より多くのコンピュータを使って助けを得ようとしてきました。課題は、もし仕事を複数のコンピュータに分割した場合、前の人が自分のステップを終えるのを全員が待ってしまうため、コンピュータ同士が混乱してしまうことです。それは、たとえ異なるトラックに立っていたとしても、バトンを受け取るために待機しているランナーがいるリレーレースのようなものです。本論文は、まさにその問題に取り組んでいます。すでに超高速な単一のコンピュータチップ上で動作することが証明されている巧妙な数学的トリックを、現代のマルチコアコンピュータや強力なグラフィックスカード（GPU）へとスケールアップさせる手法を提案しています。著者らは、これらのコンピュータが互いに待ち合うことなく協力して作業できる方法を見出し、この種の数学処理においてこれまで不可能と思われていたスピードを実現し、単一の列を高速な多車線ハイウェイへと変貌させました。

リレーレースの問題と魔法のトリック

この画期的な成果を理解するために、これらのフィルターが通常どのように機能するかを見てみましょう。長い列に並んだ人々がメッセージを伝達していく様子を想像してください。各人は、前の人がメッセージをささやくのを待ってから、自分の部分を付け加えて次に渡さなければなりません。これが「再帰的（recursive）」な部分です。もし長い鎖があれば、メッセージが終点に到達するまでに長い時間がかかります。

本論文の著者たちは、長い鎖をより速く処理できる小さな塊、すなわち「ブロック」に分割する方法をすでに編み出していました。しかし、これらのブロックを一度に多くのコンピュータ（例えば作業チーム）に割り当てようとすると、新たな問題が発生しました。あるブロックの終わりが、次のブロックの始まりになるからです。もしブロックAをワーカー1に、ブロックBをワーカー2に任せたとしても、ワーカー2はワーカー1がブロックAを完了するまでブロックBを開始できず、立ち往生してしまいます。結局、チームは結局一人ずつ作業することになり、チームで作業する意味がなくなってしまうのです。

本論文の主要な発見は、「重ね合わせ（superposition）」と呼ばれる数学的な「魔法のトリック」です。前のブロックからの答えを待つ代わりに、ワーカーたちは、もしゼロから始めたとしたら答えはどうなるかという「ゼロ状態」の予測を行います。彼らはこの計算を即座に実行します。その後、前のワーカーからの「実際の」開始数値が到着するのを待ちます。数値が到着したら、彼らは自分の予測に対して、わずかな「補正」を加えるだけです。これは、まだ材料がないと仮定してレシピに基づいてスープを作り始めるシェフのようなものです。配送トラックが実際の野菜を届けたとき、シェフはそれらを加えて混ぜるだけで済みます。調理という大変な作業はすでに並列で行われていたため、スープはほぼ瞬時に完成します。

二つの異なる実行方法

この論文は、何をしようとしているかに応じて、この魔法のトリックを二つの全く異なる方法で使用できることを示しています。

1. リアルタイム・ストリーム（組立ライン）
ラジオ放送のようなライブデータを処理する場合、次の1秒間の音を再生する前に、バッチ全体の処理が終わるのを待つことはできません。データは入ってきた通りの順番（先入れ先出し：FIFO）で出てくる必要があります。

• 解決策: 著者らは、マルチコアCPU向けの「ウェーブフロント・パイプライン（wavefront pipeline）」を構築しました。これは、異なるワーカーが同じ曲の異なるステージを同時に扱っている組立ラインを想像してください。ワーカー1はベースを掃除し、ワーカー2はボーカルを修正し、ワーカー3はエコーを追加しています。ワーカー1がひと塊の処理を終えるとすぐにワーカー2へ渡し、ワーカー2はワーカー3へと渡します。
• 結果: 現代的なコンピュータの6つの強力なコアを使用した場合、この手法は複雑な16次フィルターに対して2.4ギガサンプル/秒の速度を達成しました。これは、単一のコアを使用する場合の約4倍の速さです。興味深いことに、低速な「効率化用（efficiency）」コアを混ぜると、かえってラインが遅くなることが分かりました。これは、この特定のタスクにおいては、多くの遅いワーカーよりも少数の速いワーカーの方が優れていることを証明しています。

2. バッチ処理（工場）
録画された膨大なファイル（映画やデータベースなど）を処理する場合、順番よりも生の処理速度が重要になります。ファイル全体を一度に処理できます。

• 解決策: 著者らは、数千の小さなワーカーを持つ強力なグラフィックス・プロセッシング・ユニット（GPU）を使用しました。彼らは「デカップルド・ルックバック（decoupled lookback）」という手法を用いました。これは、すべてのワーカーが製品のパーツを即座に計算する工場を想像してください。もしワーカーが前のステーションからのパーツを必要とする場合、彼らは停止しません。代わりに「ステータスボード」をチェックして、前のステーションが終了したかどうかを確認します。もし終了していれば、パーツを掴みます。もし終わっていなければ、準備ができるまで他の作業を続けます。
• 結果: このアプローチは驚異的に高速でした。NVIDIA RTX 3060 グラフィックスカードにおいて、システムは単一のフィルターセクションに対して38.2ギガサンプル/秒に達しました。これは、ハードウェアが理論的に到達可能な最大速度（メモリ帯域幅の天井）の**85%**に相当します。

なぜこれが重要であり、何に勝っているのか

著者らは単に高速化しただけでなく、彼らの手法が従来の方法よりも信頼性が高いことを証明しました。

• 「ダイレクトフォーム（Direct Form）」の失敗: 巨大な一歩で数学的処理を行おうとする「ダイレクトフォーム」と呼ばれる古い手法があります。本論文は、複雑なフィルター（16次フィルターなど）において、この古い手法が破綻することを示しています。数値が乱雑になりすぎて、コンピュータがゴミのような結果を出したり、クラッシュしたりするのです。本論文で使用されている新しい「カスケード（cascaded）」方式は、こうした高いレベルでも精度を維持します。
• 競合との比較: 彼らは、自らの新しいGPUコードを、現在利用可能な最強の並列フィルタリングエンジンと比較しました。彼らの手法は、テストされたすべてのフィルター次数において、より高速でした。
• 速度の代償: 論文では、速度の「コスト」についても注意深く測定しています。新しい高速なチップ（RTX 3060など）では、「バリア（ワーカーが行うチェック）」のコストが低いため、より複雑で高速な手法を使用できます。一方で、古いチップではこれらのチェックが高価であるため、より単純な手法を用いる必要があります。これにより、エンジニアはハードウェアに合わせてソフトウェアをどのようにチューニングすべきかを知ることができます。

結論

本論文は、困難な逐次的な数学問題を、並列的なパーティーへと変貌させました。巧妙な「予測と補正」戦略を用いることで、コンピュータが互いに待ち合うことなく協力できるようにしました。

• ライブストリーミングについては、標準的なコンピュータ上で3.95倍高速に動作するパイプラインを構築しました。
• バッチ処理については、38.2ギガサンプル/秒で動作するGPUエンジンを構築し、これは劇的な飛躍です。
• 極めて重要なのは、この手法が単に速いだけでなく、より「優れている」ことを証明した点です。従来のメソッドが失敗する場面でも精度を維持します。

著者らはコードをオープンソースライブラリとして公開しており、誰でもこれらの超高速フィルターを使用して、より優れたオーディオツール、より鮮明なビデオ、あるいはよりスマートなロボットを構築することができます。彼らは、逐次的なボトルネックを並列のスーパーハイウェイへと変え、たとえ最も手強い数学の問題であっても、コンピュータのチームを同期させることで解決できることを示しました。