多くのデータを処理し、いくつかのパターンに基づいてグループに分類する必要があるプログラムがあります。少しお話しします。
このデータは行列のように表され、各列は「サブ要素」に分割された異なる要素です。プログラムはこの「サブ要素」を取得し、各パターン (パターンは DFA - 決定論的有限オートマトン * によって表されます) を調べて、要素が属するグループを確認します (要素は複数のグループに属しません)。 .
- このように行列を使用して、GPU に移植するときにメモリを合体させます。
以下の画像は、データ編成を視覚的に説明しています。
- 明らかに、データセットは 4 つの要素よりもはるかに大きいです
CPU-CODE - まず、このプログラムを CPU コードで書きました。それは完全にシリアル化された作品です。プログラムは要素から各サブ要素を取得し、要素が最初のパターンをチェックする 1 つのグループに属しているかどうかをチェックします。そうでない場合は、2 番目のパターンを見てください。等々。最初の要素が分類されると、2 番目の要素がチェックされ、次に 3 番目の要素がチェックされます。 /CPUコード
ご覧のとおり、このコードは並列化するとはるかに高速になります。次に、プログラムはCUDAでコーディングされました。
GPU-CODE - 少ないメモリ転送で GPU でコードを実行するために、「コードの分類」が開始する前に、すべてのデータとオートマトンが GPU メモリに転送されました。現在の違いは、多くのスレッドとブロックを起動できることと、各スレッドが 1 つの要素を取得して分類することです。下の画像は、GPU でどのように行われるかを説明しています。
GPU コードは CPU コードよりもはるかに高速です。/GPU コード
ここで質問があります: 私が言ったように、パターンはオートマトンに足を踏み入れてチェックされます。オートマトンにはいくつかの状態があり、各状態にはいくつかの遷移があります。トランジションの数は 6 を超えることはほとんどありません。メモリの制限により、オートマトンは、次の状態を取得するためにテーブルを 1 回見るだけで済むデフォルト モード (テーブル エンコーディング) では表現されません。
私のエンコーディングでは、次の状態を取得するために複数のルックが必要です。次の状態を取得するには、サブ要素を取得し、最初の遷移がそれによってトリガーされるかどうかを確認します。そうでない場合は、2 番目のトランジションなどをチェックします。
十分に明確でない場合、上記の CPU と GPU の両方のコードは、オートマトンの状態内を順番に歩きます。つまり、最初の遷移をチェックして、次の状態に一致するかどうかを確認します。そうでない場合は、次のトランジションなどを確認します。
この検索を各州内で並列化したいと考えています。つまり、トランジションごとに 1 つのスレッドが必要です。前述のように、状態内の遷移の数はほとんど 6 を超えません。遷移の数が少ないため、並列化する必要がないように思われることはわかっていますが、コードのこの部分 (一致) は数回繰り返されます。
各ステート内でこの検索を並列化しようとしましたが、実行時間はシリアル コードよりも大きくなりました。以下の単純な実装をどのように行ったかを説明します。
このテストでは、状態ごとに最大 4 つの遷移を持つオートマトンを使用しました (ただし、4 つ未満の遷移を持つこともできます)。そこで、スレッド ブロックの Y 次元で 4 つのスレッドを起動し (X 次元のスレッドは要素を受け取り、Y 次元のスレッドはサブ要素を受け取ります)、共有メモリに 1 つの配列を作成します。トランジションマッチ」か否か。この配列は、すべての要素に対して行われるため、ブロック (blockDim.x * blockDim.Y) のサイズを持ちます。
問題は、状態ごとの遷移が 4 つ未満の場合があることです。これは、たとえば、スレッド 3 が、関心のある状態ではなく、一致が間違っている他の状態をチェックできることを意味します。この問題により、「最初の一致」検索を行う必要があり、この検索を以前と同じように順次実行しますが、スレッドと配列を作成するためのオーバーヘッドが発生します (配列を設定します)。配列の要素を 0 に変更すると、オーバーヘッドが増加します)。したがって、私は何もしませんでした。
わかりやすくするために、この画像は私がやろうとしたことを示しています。
以前、stackoverflow で最初に一致する検索を行う方法を尋ねたことがありますが、私の質問には、コードと問題に関する重要な詳細がいくつか欠けていました。ここで説明します。
だから私の質問は、各状態内でこの検索を効率的に並列化できますか (遷移の数が少ない場合でも)、それは価値がなく、シリアル化された GPU コードを使用する必要がありますか?
並列化できると思う場合、「最初の一致」検索をより適切に実装した最後のコードを使用する必要がありますか、それともまったく異なるアプローチを使用する必要がありますか?