3

Intel 64 で実行する論理検証問題をベクトル化しようとしています。

私は最初に問題を説明しようとします：

v[]コンパイル時にすべて既知の 70 ビット整数 (約 400,000 個) の静的配列があります。

プロデューサは 70 ビット整数aを大量に非常に迅速に作成します。

それぞれについて、 whichaの要素が存在するかどうかを調べる必要があります。vv[i] & a == 0

これまでのところ、C での私の実装は次のようなものです (簡略化):

for (; *v; v++) {
    if (!(a & *v))
        return FOUND;
}

// a had no matching element in v
return NOT_FOUND;

SSE/AVX を使用してこれを最適化し、プロセスを高速化し、これらのテストを並行して実行することを検討しています。それぞれをレジスターにロードaし*vて、検証を行うためXMMの命令を呼び出すところまで行きました。PTEST

YMMこれを拡張して、新しいレジスタの 256 ビットすべてを使用する方法があるかどうか疑問に思っています。3x70 ビットを 1 つのレジスタに詰め込むことはできますか? テストごとに1つのレジスタを使用するだけでなく、正当化するのに十分な効率でそれらをパック/アンパックする方法はよくわかりません。

入力の性質についてわかっていることがいくつかあります。

  • のすべての要素には、v[]設定されているビット数が非常に少ない
  • v[]70ビット未満を使用するように並べ替え/圧縮することはできません
  • 平均で約20%確認後、FOUND条件が満たされる見込みです。v[]
  • aバッチでチェックする前に、複数をバッファすることができます。
  • v[]のどの要素が一致したかを必ずしも知る必要はありません。一致したかどうかだけを知る必要があります。
  • プロデュースaに必要なメモリは非常に少ないため、前回の呼び出しで L1 に残っていたものはまだ残っている可能性があります。

結果のコードは、SSE4.2、AVX 命令をサポートする最新世代の Intel Xeon プロセッサで実行することを目的としています。Intel C コンパイラまたは少なくとも GCC でコンパイルされるアセンブリまたは C を喜んで受け入れます。

4

1 に答える 1

3

あなたが本当に必要としているのは、v[] を保存するためのより優れたデータ構造であるように思えます。そのため、検索にかかる時間は直線的ではありません。

(v[0] & v[1]) & aがゼロでない場合は、どちらもゼロにならない(v[0] & a)ことを考慮してください(v[1] & a)。これは、v[] が葉で、親ノードがその子の AND 結合であるツリー構造を作成できることを意味します。次に、parentNode & aゼロ以外の値が返された場合は、子の表示をスキップできます。

ただし、これは必ずしも役立つとは限りません。親ノードは、子ノード間で共通のビットをテストするだけなので、その数が少ない場合でも、多数のリーブ ノードをテストすることになります。しかし、データ セット内でクラスターを見つけて、多くの類似した v[] を共通の親の下にグループ化できれば、必要な比較の回数を大幅に減らすことができます。

一方で、このようなツリー検索は条件分岐が多く (コストがかかり)、ベクトル化が困難です。最初に 2 つのレベルだけで済むかどうかを試してみます。まず、クラスターの親ノード間でベクトル化された検索を実行し、次に一致ごとにそのクラスター内のエントリを検索します。

実際には、70 ビットがレジスタにうまく収まらないという事実を助けるための別のアイデアがあります: v[] を 64 (=2^6) の異なる配列に分割できます。元の v[] の 70 ビットのうち、最上位 6 ビットを使用して値を格納する配列を決定し、残りの 64 ビットのみが実際に配列に格納されます。

配列インデックスに対してマスクをテストすることによりa、64 個の配列のどれを検索するかがわかります (最悪の場合、a最上位の 6 ビットが設定されていない場合、すべての配列になります)。配列検索は要素あたり 64 ビットのみを扱います (パックする方がはるかに簡単です)。

実際、この 2 番目のアプローチは、ツリー構造に一般化することもできます。これにより、ある種のtriが得られます。

于 2012-10-14T17:40:18.760 に答える