こんにちは、Habraコミュニティの皆さん。
GPGPU （ビデオカード）コンピューティングについてはすでに多くの人が聞いたことがあると思われますが、現時点では、このプログラミング手法の実装が多数あります。 そのうち2つに焦点を当てます-これはNvidiaの悪名高い
CUDAであり、人気はやや劣りますが、よく知られている
OpenCLフレームワークです。 これらの技術の基本原理を説明する記事がすでにハブに十分にありますので、これに焦点を合わせません。 記事では、データ圧縮のためにCPUと比較してGPGPUを使用したときに得られた結果を共有したいと思います。
背景
私は常に並列コンピューティングに興味を持っていたので、研究所では科学研究としてこの方向を選びました。 GPGPUに関するさまざまな記事を読み、生産性を向上させながら、論文のトピックを選択する必要が生じたとき、卒業証書のトピックはGPGPUに特に関連するものと判断しました。 データ圧縮を試してみることにしました（これはGPGPUの最適なタスクではないと言えます）。データ圧縮用の静的ハフマンアルゴリズムがアルゴリズムとして選択されました。
データ圧縮用の標準ハフマンアルゴリズム
アルゴリズムに慣れていない人のために、その操作の小さな例を挙げます。
例として、次の文字シーケンスを使用するアルゴリズムを検討してください。
aaaaaaaccaabccbbbb
ステップ1：ファイル全体を読み取り、拡張ASCIIセットの各文字が見つかった回数をカウントする必要があります。
この例では、文字の出現頻度はそれぞれ次と等しくなります。
a-9、b-5、c-4。
ステップ2：各シンボルの出現頻度をカウントした後、バイナリツリーを形成する必要があります。例を使用してツリーを構築するアルゴリズムを検討してください。
- シーケンスは3つの文字で構成されています。これらの文字を頻度の降順で並べます：{（a、9）、（b、5）、（c、4）}。
- 次の行では、前のセットから取得したセットを次のように記述します。
-周波数を持つ最後の2文字の代わりに、シンボルの名前の代わりに「Top #n」というエントリを持ち、周波数の代わりに新しい要素を書き込みます-前のセットの最後の2つの要素の周波数の合計。
-結果セットを降順に並べ替えます。
{（a、19）、（ "top＃1"、9）}。 - セットが1つの要素のみで構成されるまで、前の手順を繰り返します：（ "top #last_number"、summa_vseh_chastot）：
{（ "トップ＃2"、28）}
ルートが最後の頂点である二分木を得ました。
ステップ3：結果のツリーを使用して、ファイルをエンコードできます。 これを行うには、文字の新しいビットシーケンスを選択し、ツリーノードを上に移動して、各右ノードに1、左ノードに0を追加します。この例では、文字は次のようにエンコードされます。
a-0、b-10、c-11
ASCIIテーブルによると、圧縮前の文字は次のように見えていました。
a-01100001、b-01100010、c-01100011。
エンコード時に、文字をシーケンスデータに置き換えます。
ファイルをデコードできるようにするには、ツリーをファイルに保存する必要があります。 デコードは、ツリーをルートからリーフに渡すことで実行されます。
GPGPU圧縮アルゴリズム
エンコードプログラムは、論理的にプリプロセッサ（アルゴリズムのステップ1.2）と実際のエンコード（ステップ3）に分割されます。 アルゴリズムのステップ1.3がGPGPUに提出されました。
ハフマン法を実装する場合、前処理の最初の2つの段階は標準です。
- アルファベットのさまざまな文字が遭遇する頻度をカウントします。
- 周波数の配列の順序付け。
次に、ハフマンツリーを構築する必要があります（ステップ2）。 この例では、ハフマンツリーの代わりに、次を含む追加のデータ構造が構築されます。
- 文字コードの配列。
- 文字コード長の配列。
標準のハフマンツリーに代わるこのデータ構造を使用するという決定が下されました。これは、GPGPUに本格的なツリーを実装できるテクノロジーが使用されていないためです。
上記のすべての前処理ステップのうち、シンボル周波数のカウントのみが入力データのサイズに依存します。 前処理の残りの段階は基本的なステップです。
結果
C＃がプログラミング言語として選択されました。 効率を比較するために、CPU用に2つのバージョンのプログラム、CPU（非同期）-並列バージョンとCPU（同期）-シリアル、およびGPGPU用の2つのバージョン（OpenCLとCUDA）を作成しました。
テストには次の機器が使用されました。
- プロセッサー（CPU）：AMD PHENOM X4 965 Black Edition;
- グラフィックカード：MSI GeForce GTS 450。
プログラムの速度を測定するために、2つのファイルが選択されました。1つは200 MB（210 596 352バイト）、2つ目は603 MB（633 128 511バイト）のサイズです。 時間を測定するには、C＃で使用可能なStopwatch（）クラスを使用します。 時間測定の精度は、プロセッサの周波数に依存し、理論的には使用されるコンピューターにより1/36902109016524975 = 3.0e-16になります。
プログラムの各バージョンおよびファイルごとに10回測定が行われました。 図 1-4は、測定に基づく平均時間を示すグラフです。
図1
このテストでは、OpenCLとCUDAはCPU（同期）よりも8倍半、CPU（非同期）よりも2.5倍高速です。
図2
このテストでは、OpenCLとCUDAはCPU（同期）の4倍半、CPU（非同期）の1.5倍高速です。
図3
このテストでは、OpenCLとCUDAはCPU（同期）の8倍、CPU（非同期）よりも2.5倍高速です。
図4
このテストでは、OpenCLとCUDAはCPU（同期）よりも4〜3倍高速で、CPU（非同期）よりも1〜3倍高速です。おわりに
CUDAとOpenCLは、CPUと比較したテストでの有効性を証明しています。
結果に基づいて、多数の数学計算を使用しないタスクの場合、OpenCLを使用して記述されたプログラムのランタイムは、CUDAを使用して記述されたプログラムのランタイムと等しいと結論付けることができます。 記事の第2部では、実装の技術的な側面について説明します。