4

私のアプリケーションは、それぞれ 8 バイトの何百万もの入力レコードを受け取り、それぞれを 2 つ以上の出力ビンにハッシュします。つまり、各入力キー K は少数のペア (B1,K)、(B2,K)、... を作成します。キーごとの出力ビンの数は、キーが処理されるまでわかりません。通常は 2 ですが、場合によっては 10 以上になることもあります。

各ビンのすべてのキーは後で一緒に処理されるため、これらの出力ペアはすべて最終的に 1 つの配列に格納する必要があります。これを効率的に行うには？

アトミック インクリメントを使用して、グローバル配列からペアを繰り返し予約すると、恐ろしく遅く聞こえます。別の明白な方法は、ビンごとのある種のストレージへのポインターの配列としてハッシュテーブルを初期化することです。それは遅く見えます。

ブロック共有配列の入力レコードごとに 2 ペアを事前に予約し、必要に応じてより多くのスペースを取得し (つまり、STL ベクトル予約操作の再実装)、各ブロックの最後のスレッドで共有ブロックをコピーすることを考えています。配列をグローバルメモリに。

しかし、私はそれを実装することを楽しみにしていません。ヘルプ？ありがとう。

4

1 に答える 1

1

アトミック インクリメントを使用して、グローバル配列からペアを繰り返し予約すると、恐ろしく遅く聞こえます。

一度に 1 つのエントリではなく、グローバル配列のビンをインクリメントできます。つまり、大きな配列を持つことができ、各スレッドは 10 個の可能な出力エントリで開始できます。スレッドがオーバーフローすると、グローバル配列から次に利用可能なビンが要求されます。原子番号 1 で速度が遅いのが気になる場合は、原子番号 10 個を配列の 10 個の部分に使用して、アクセスを分散させることができます。1 つがいっぱいになったら、別のものを探します。

また、データを 2 回処理することも検討しています。1 回目は、各入力レコードの出力レコード数を決定するためだけです。次に、十分なスペースを割り当て、最後にすべてのデータを再度処理します。

これは別の有効な方法です。ボトルネックは、各スレッドの結果の総数を取得したら、グローバル配列への各スレッドのオフセットを計算することです。私はそれを行うための合理的な並列方法を考え出していません。

私が考えることができる最後のオプションは、大きな配列を割り当て、ブロックに基づいて分散し、共有アトミック int を使用することです (低速のグローバル アトミックに役立ちます)。スペースがなくなったら、ブロックが終了しなかったことをマークし、どこで中断したかをマークします。次の反復では、まだ完了していない作業を完了します。

もちろん、グローバルメモリの分散部分の欠点は、タロンミーが言ったようなものです...結果を密にするためには、収集または圧縮が必要です。

幸運を！

于 2015-05-13T01:20:55.690 に答える