1

私は C++ プログラミングの世界に非常に慣れていないため、素人っぽい質問で申し訳ありません。

メイン メモリ (1 次元配列) に格納されたデータの大きなブロックを取得し、そこにあるデータの一部に頻繁にアクセスする必要があります。これを行う方法は次のとおりです。

float *x=new float[20];//array to store x;
int *indlistforx=new int[20];//array to store the index of x;
float *databank=new float[100000000];//a huge array to store data

/... fill data to databank.../


for (int i=0;i<N;i++)//where N is a very large number;
 {
  /... write index to indlistforx.../
  getdatafromdatabank(x, indlistforx, databank);
  //Based on the index provided by indlistforx, read data from databank then pass them to x

  /...do something with x.../
  };

これらのデータにアクセスするための効率的で高速な方法はありますか (x のインデックスは整列されておらず、整列することは不可能です)。

よろしくお願いします！

4

3 に答える 3

3

データバンクへのアクセス方法を実際に示していないため、これはすべて非常に推測的なものです。

  • はindlistforxデータバンクへの 20 個のインデックスのリストなので、20 回のランダム アクセスを行っていますか?

    • これらの指数の歩みはどのくらいですか?それらは連続しているか、近接しているか、またはランダムですか?
    • それらが連続しているか、近接している場合は、それらを並べ替えると役立つ場合があります（したがって、プリフェッチを改善するために昇順で読み取り、同じキャッシュラインからの読み取りをグループ化します）

  • 20 のインデックスの異なるグループはどのくらい飛び回りますか? それらは重なり合うことができますか？

    • それらがオーバーラップできない場合、データバンクは効果的にいくつかのチャンクサイズに分割され、異なるプロセッサで各パーティションを処理すると、使用できる有効なキャッシュの量が増える可能性があります (複数のプロセッサがある場合)。
    • データバンクが読み取り専用の場合、要求が重複して実行されても、それらを同時に実行できます。データバンクに何かが書き込まれると、キャッシュ スラッシングのレシピになります。

  • キャッシュの動作を改善するために、より高いレベルでアクセスを並べ替えることはできますか?

    • これは基本的に私の最初の提案と同じですが、単一のindlistforx要求のレベルを超えています
    • 同様に、それらを並べ替えてデータバンクを効果的に分割し、マルチプロセッサのアイデアを試すことを検討してください

すべてのコード (または代表的なサンプルであり、それが大きすぎる可能性があることも理解しています) を確認しないと、これ以上詳しく説明することは困難です。

ただし、機能する可能性のある一般的な手法が 1 つあります。実装コストが節約を上回るほど重い場合もあります。

  • getfromdatabank同期的に完了するのではなく、将来/約束/何でも返します（または、それがきめの細かいものでない場合は、20の先物のベクトル）
  • これらの非同期リクエストの多くを並行してディスパッチするようにしてください。個別のスレッド (future へのアクセスがブロック操作になる場合) またはイベント ループを使用して、明示的なコルーチンのようなもので完了を処理します。
  • 複数のリクエストからのすべてのデータバンク アクセスを専用のスレッドに集約し、それらを並べ替えてキャッシュ パフォーマンスを向上させる

これは、追加の同期オーバーヘッドが読み取りパフォーマンスの向上によって支配され、多くのクエリを並行して実行できる場合にのみ機能します。

于 2012-10-15T23:23:21.257 に答える
2

フロートを初期化する必要があるため、実際には std::vector<> を使用する必要があります。遅くはありません。次のように構築して塗りつぶします。

std::vector< float > databank( 100000000, 0.0f );

高速化にはいくつかのオプションがあります。

1）かなり大きなキー（インデックス）の再利用がある場合は、何らかのキャッシングまたは記憶戦略を使用できます。例については、 http://www.boost.org/doc/libs/1_51_0/libs/flyweight/doc/index.htmlを参照してください。

2) std::async() などを使用して、処理を複数のスレッドに分割できます。

3) コンパイラで simd 命令 (x86 では sse) がオンになっていて、それらが使用されていることを確認します。そうでない場合は、コンパイラ組み込み関数を使用して simd の使用を強制します。これにより、ほぼ 4 倍の改善が可能になります。

于 2012-10-15T23:00:20.200 に答える
1

問題は、あなたがあなたのdatabank. 問題は、それをどのように使用しているかです。離れた部分にランダムdatabankに短時間でアクセスすると、パフォーマンスが低下します。それを使用すると、パフォーマンスが低下getdatafromdatabank(x, indlistforx, databank)することがほぼ保証されます。indlistforxこれによって有効になるランダム アクセスにindlistforxは、パフォーマンスが大幅に低下します。そのランダムアクセスがあなたのdatabank仕事をどのように使用するかという理由で絶対に必要な場合、それはあなたが支払わなければならない代償です.

アルゴリズムを変更して、 内の連続したメモリ チャンクにアクセスできるようにすると、パフォーマンスが大幅に向上しますdatabank。配列 20 インデックスではなくgetdatafromdatabank、最初のインデックス ( にロードする要素のインデックス) のみを指定するように変更します。x[0]

xサイズが20になっている理由はありますか？x出力配列とdatabankレベル 1 キャッシュの関連チャンクをかろうじて保持できれば、最高のパフォーマンスが得られます。xのサイズがこの最適サイズを超えて大きくなると、パフォーマンスが低下し始め、大幅に低下する可能性があります。

于 2012-10-15T23:54:13.953 に答える