FFTからの復元をマルチスレッドで高速化

2025/03/15

　本記事では、音声圧縮体験ツールにて、「高速フーリエ変換(FFT)」で変換されたデータを、音声データに復元する処理について、 マルチスレッドでの並列処理による高速化を解説します。

フーリエ変換後の一部のデータ配列から全音声データを復元

　音声圧縮体験ツールでは、使用者の操作で復元に使用するデータ数を指定します。 そしてフーリエ変換結果の、影響度の高い方から指定された数だけデータを取り出して、音声を復元します。
　この図では、復元データ数に3が指定され、\(F_0\)から\(F_2\)が復元に使用されるフーリエ変換情報です。 下段の\(D_0\)から\(D_7\)が復元される音声データです。
　復元のための計算には、 例えば、\(D_0\)を復元するためには、\(F_0\)から\(F_2\)のすべてを加算して求めます。 \(D_1\)を復元するためにも、\(F_0\)から\(F_2\)のすべてを加算します。
　各音声データそれぞれに対して、復元に使用されるデータのすべてが必要です。

計算量はデータ数の積の回数

　つまり、復元の元データとして使用されるデータ数と、復元される音声のデータ数の積が、復元処理の計算量となります。
　上図では \(3 \times 8\) が計算量です。 この程度なら処理速度が問題になることはありませんが、 例えば44.1KHzでサンプリングされた音声データ1秒を、その\(\frac{1}{10}\)の量のデータから復元しようとすると、 \(4410 \times 44100 = 194,481,000\)回の計算が必要です。 約2億回ですね。 いくらコンピューターは高速に動作するといっても、さすがに処理時間がかかります。

理論による処理時間削減は難しい

　しかしながら、これを高速化する理論は、少なくとも筆者には思いつきませんでした。 そのため、実装テクニックで高速化を目指します。

逐次処理のプログラミング

　まず初めにプログラムを確認しましょう。 この図のように、最初の計算で \(D_0\) を求めます。 それが完了したら、次の計算に \(D_1\) を求め、、、と、逐次計算処理しています。

\(D_0\)の計算結果は他の\(D_x\)には影響しない

　この処理の中で、\(D_0\)の計算結果は\(D_1\)や\(D_2\)等々には影響しません。 つまり、\(D_0\)を求める処理を、\(D_1\)より先にする理由は無いのです。

並列処理することで高速化

　そのため今回の計算処理は、この図のように、\(D_0\)と\(D_1\)、\(D_2\)…の計算処理を行う処理を、並列に動作させるようにプログラムすることで、高速化できます。

マルチスレッド

　複数の処理を並列に動作させることをマルチスレッドと呼びます。
　処理を行う単位はスレッド(Thread)と呼ばれます。 それがマルチすなわち複数動作している状態がマルチスレッドです。 対して、並列せずに処理することをシングルスレッドと呼びます。 1スレッドのみの処理ということです。

どのくらい高速化されるか

　コンピューターは主に、実行を司るCPU(しーぴーゆー)と、記憶を司るメモリーから成り立ちます。
　そのうちCPUの能力が、処理速度に直結します。
　パソコンやスマートフォン、および家庭用ゲーム機を含めて、今のコンピューターの多くには、CPUの中に、コアと呼ばれるものが複数入っています。 コアは実際にプログラムを動作させる装置で、そのコアの数だけ、プログラムを同時に動かすことができます。
　つまり本記事の例では、コア数倍に高速化されます。 例えばコア数が16であれば、16の処理を並列に動作させられますので、16倍高速化されます。

実装は少し複雑

　理屈としては以上です。 順番に処理していたものを並列に処理するというだけですので、比較的単純でしょう。 ただしマルチスレッドのプログラミングは、実装難易度が高いです。

処理順序が不定になる問題

　マルチスレッドのプログラミングは、スレッドを生成して、生成したスレッドにプログラムとデータを渡して処理してもらうイメージになります。
　渡されたスレッドは、それぞれ独立して動きます。 連動していないため、処理順序は不定です。 つまりスレッドを作成した順番通りに終了するとは限りません。
　そのため正しく完了を検知するためには、例えば、計算が完了する度にカウントアップしていき、音声データ数に達したら終了する、といったプログラミングが必要で、実装難易度が上がります。

同時アクセスの問題

　前記の完了検知処理を具体化します。
　まず、あるメモリーを共通カウンターとして、初期値0を格納しておきます。
　マルチスレッドの各スレッドでは、計算処理が完了したら、その共通カウンターをカウントアップします。 そして、メインスレッド(プログラム本体)では、共通カウンターを監視し、音声データ数に到達したら完了とするプログラムを考えます。
　このとき、各スレッドが共通カウンターをカウントアップする処理は、この図のように、メモリーから共通カウンターの内容を読み込み、1を加えて、書き戻す、というプログラムになるのが普通でしょう。
　しかし、この図のようにスレッド6とスレッド7がほぼ同時に完了した場合、共通カウンターをメモリーから読む時点でどちらも6だったため、1を加えて7となり、両スレッドが7を書き込んで完了してしまいます。 メインスレッドは、共通カウンターが8になるまで待っていますので、永遠に待ち続ける不具合になります。
　この問題自体は、ロックやセマフォと呼ばれる技術を用いて、共通カウンターにアクセスできるスレッドを1つに絞り、カウントアップ処理が同時に動かないようにプログラミングできます。 これを排他制御と呼びます。
　ただし、その状況は、カウントアップしたいけど待たされてしまうスレッドがいることになります。 それが多いと、並列動作している割合が下がり、パフォーマンスに影響が出ます。 そのためロックやセマフォの使用は必要最小限に絞る必要があり、効率的なプログラミングをするには実装難易度が上がります。
　なお今回の実装では、メッセージキューと呼ばれる方式を用いています。 各処理スレッドの終了時に、メインスレッド宛に終了メッセージを送ります。 そのメッセージは、キューと呼ばれる場所に順番に保存されます。 その保存の際に排他制御が必要ですが、それは実装に用いたJavaScriptの中で行われます。 そしてメインスレッドが、キューに保存されたメッセージを順番に読み込んで処理することで、この問題を解決しています。

デバッグがしづらい問題

　マルチスレッドが原因の不具合は、デバッグがしづらいという問題もあります。 例えば、処理順番が特定の状態になったときだけ発生する不具合は、その処理順番になってくれないと不具合が再現できず、修正しても治ったかどうかの確認が困難です。
　マルチスレッドのプログラミングでは、なんとなく書いたら動いたからOK、などではなく、論理的に不具合にならない設計が重要です。

マルチスレッドの使いどころ

　マルチスレッドによる高速化は、非常に強力です。 理論的に高速化できなくても、マルチスレッドによる高速化が有効なことは多いです。
　しかしプログラミングの実装難易度が高いため、その効果を見極めて選択すべきでしょう。

まとめ

　本記事では、FFTからの復元処理における、マルチスレッドによる高速化について解説しました。
　プログラミング実装は少し(かなり?)大変ですが、概念としてはシンプルです。 本記事が少しでも、プログラミングへの興味や、高速化のためのヒントに繋がりましたら幸いです

補足

・FFTは Fast Fourier Transform です。直訳で「高速フーリエ変換」です。
・アプリケーション等によりコアのことをCPUと呼ぶ場合もあります。
・コア数ぶん高速化されるのは復元される音声データ量が充分に大きい場合です。
・今回使用したフーリエ変換は、厳密には離散フーリエ変換です。これはデジタルデータを処理するフーリエ変換です。
・画像内のラスタライズ文字フォントにOpen Font LicenseのZen Antiqueを使用しております。
・画像内のラスタライズ文字フォントにOpen Font LicenseのNoto Sans Japaneseを使用しております。
・数式表現にMathJaxを使用しております。助かります！
・(本記事公開後)順番の制御にメッセージキューを使用している旨を追記しました。

カテゴリー：オーディオ推し,プログラミング