3

私はC++でマルチグリッドソルバーに取り組んでおり、現在、シリアルパフォーマンスを改善しようとしています。これで最も時間のかかる部分はよりスムーズな部分であり、私の場合は連続的な過緩和ソルバーです。これは次のようになります（私はそれがかなり自明であることを願っています）：

int idx; 
int strideY = stride_[level][0];
int strideZ = stride_[level][1];
for(int i = 0; i < steps; ++i) {

    for(int z = 1; z <= innerGridpoints_[level][2]; ++z) {
        for(int y = 1; y <= innerGridpoints_[level][1]; ++y) {
            idx = getIndexInner(level, 1,y,z);
            for(int x = 1; x <= innerGridpoints_[level][0]; ++x, ++idx) {
                grid[idx] = (1. - omega)  * grid[idx] + omega * 1./6. * (grid[idx+1] + grid[idx-1] +
                                    grid[idx + strideY]  + grid[idx - strideY] + 
                                    grid[idx + strideZ]  + grid[idx - strideZ] - 
                                    spacing_[level] * spacing_[level] * rhs[idx]);
            }
        }
    }
}

すでにいくつかの最適化を行いました。ループは、内側のループが最もローカルなエントリを提供するように配置され（つまり、隣接する要素がx次元に沿っている）、idxの事前計算（これはインライン関数ですが、かなりの節約になります）このように時間）。また、ブロックを試みました。つまり、グリッド全体を反復処理するのではなく、局所性を高めるために小さなチャンクのみを反復処理しましたが、影響はありませんでした。私が持っている最後のアイデアは、ループ展開を試すことですが、実際にはそれによる大きな改善は期待していません。私は、メモリアクセスに向けていくつかの可能な改善があるかもしれないと思っていました。どんなヒントも歓迎します:)

参考までに：グリッドサイズは非常に小さいものから255x255x255までさまざまです。また、グリッドにはすべての次元にいくつかの境界があり、少数の行で構成されています。つまり、反復はグリッド全体ではありません。

4

1 に答える 1

7

とにかく、優れた最適化コンパイラは、ほとんどの簡単なことをやってくれるので、行っている変更が実際に改善するかどうかを常に測定してください。そして、生成されたアセンブリ コードを調べて (そして理解することを学んで)、コンパイラが実際に何をしているのかを確認します。

しかし、式が複雑で、優れたオプティマイザーでさえ、少し助けが必要な場合があるため、試してみたいことがいくつかあります。

まず、内側のループ内で不変な部分式を周囲のループに巻き上げます。あなたの例では、明らかなもの spacing_[level] * spacing_[level]はomega * 1./6.

もう 1 つは、idx を配列インデックスではなくポインターにし、ループ内でポインターをインクリメントすることです。

 int *idx = &grid[getIndexInner(level, 1,y,z)];  // assuming grid is array of ints.

あなたの表情はこのように見え始めます

*idx = (1. - omega)  * *idx + omega * 1./6. * (idx[1] + idx[-1] +
                                idx[strideY]  + idx[- strideY] + // etc...

オプティマイザー (オンになっていると仮定して???) は、既にこれを実行している可能性があります。しかし、それは一見の価値があります。私が言ったように、測定がなければ、これは無意味な作業です。

そして、@ AkiSuihkonen が上記のコメントで言及しているように、「最初に機能させる」。高度に最適化されたコードのデバッグははるかに難しいため、パフォーマンスについて心配する前に、アルゴリズムが本来あるべき状態で正確に実行されていることを確認してください。

于 2013-03-20T22:25:11.013 に答える