0

私はここでは比較的新しいですが、誰かが助けてくれるとしたら、ここにいる誰かだと思いました。

非常に大規模な原子格子シミュレーションのプログラムを実行していますが、この非常に単純な関数が何度も使用されるため、プロセスが大幅に遅くなります。

周期格子内のサイトの 8 つの隣接 (BCC にいます) のタイプ (原子のタイプを表す整数 t を含む、格子と呼ばれる構造の 3 次元ベクトルの一部) をチェックするだけです。

これ以上合理化することは不可能かもしれませんが、何かインスピレーションがあれば教えてください。

//calculates number of neighbours that aren't vacancies
int neighbour(int i, int j, int k)
{
//cout << "neighbour" << endl;
int n = 0;

if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j][k+1].t)
{
    n++;
}
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j][k-1].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j][k+1].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j][k-1].t)
{
    n++;
}

return n;
}
4

2 に答える 2

2

まず、使用中のラティス ラッピング ソリューション ( (i+1) & (LATTICE_SIZE-1)) は、LATTICE_SIZE が 2 のべき乗である場合にのみ適切に機能します。たとえば、期待値が 0である場合LATTICE_SIZE == 100とi == 99、 の場合です。(i+1)&(LATTICE_SIZE-1) == 100 & 99 == 0x64 & 0x63 == 0x60 == 96

そのため、多次元配列のインデックス作成がコンパイラとプラットフォームでどのように機能するかを確認することをお勧めします。LATTICE_SIZE が 2 の累乗に等しい場合、n 番目のインデックスの乗算は、一部のアーキテクチャでは大幅に高速な左シフトに効果的に置き換えることができます。VC++11 はこの最適化を自動的に行いますが、私はあなたのコンパイラが何であるかを知りません。

頭に浮かぶもう1つの改善点は、高次のインデックスからのオフセットの再計算を回避しようとすることです。同じ高次のインデックスをグループ化すると、オプティマイザーがそれを達成するのに役立ちます。式をソートするだけでそれを達成しました：

if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k  ].t)  n++;
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j                       ][k+1].t)  n++;
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j                       ][k-1].t)  n++;
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k  ].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k  ].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j                       ][k+1].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j                       ][k-1].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k  ].t)  n++;

私のオプティマイザーはそれを利用しましたが、その結果、スピードアップはわずか 4% でした。ただし、システムによっては異なる値になる場合があります。

また、最適化の多くは実際には関数の使用に依存します。たとえば、次のような簡単なテストを作成しました。

volatile int n = 0;
for ( int i = 0; i != LATTICE_SIZE; ++i )
    for ( int j = 0; j != LATTICE_SIZE; ++j )
        for ( int k = 0; k != LATTICE_SIZE; ++k )
            n += neighbour ( i, j, k );

私の測定では、neighbour() 呼び出しごとに約 12 ns でした。その後、隣人は 2 つの高次平面でのみチェックされることに気付きました。関数をリファクタリングして、オプティマイザーにより明確なヒントを与えました。

int neighbour_in_plane ( elem_t l[LATTICE_SIZE][LATTICE_SIZE], int j, int k )
{
    int n = 0;
    if (V != l[(j-1) & (LATTICE_SIZE-1)][k  ].t)  n++;
    if (V != l[j                       ][k-1].t)  n++;
    if (V != l[j                       ][k+1].t)  n++;
    if (V != l[(j+1) & (LATTICE_SIZE-1)][k  ].t)  n++;
    return n;
}

//calculates number of neighbours that aren't vacancies
int neighbour(int i, int j, int k)
{
    return neighbour_in_plane ( lattice[(i-1) & (LATTICE_SIZE-1)], i, j ) +
           neighbour_in_plane ( lattice[(i+1) & (LATTICE_SIZE-1)], i, j );
}

そして驚くべきことに、呼び出しごとに 4 ns しか見られませんでした。コンパイラの出力を確認したところ、今回は両方の関数が呼び出しループにインライン化され、多くの最適化が行われていることがわかりました。つまり、2 つの内部ループを neighbour_in_plane() 関数に効果的に移動したため、何千もの lattice[(i-+1) & (LATTICE_SIZE-1)]式の再計算を回避できました。

肝心なのは、コード+コンパイラ+プラットフォーム環境でこの関数を試して、速度を最大限に引き出す必要があるということです。

于 2013-08-13T08:35:26.413 に答える
1

LATTICE_SIZE は 2 のべき乗であると想定して& (LATTICE_SIZE-1)います。さらに、「k」次元がラップされていないことに気付きました。それはわざとですか？

次に、C ++では、そのコードの実行時間は、「格子」がどのタイプの「配列」であるか、および比較 V !=lattice[i][i][k].t がどれほど高価であるか安価であるかに大きく依存します。一般に、ネストされた std::vector または boost::multi_array は、従来の「C」配列よりもかなり遅くなる可能性があります。

3 つの次元すべてに空の境界線 (基本的には空のサーフェス) を残す余裕がある場合は、 ですべてのラップアラウンドを除外できるため、効率が向上する可能性があります& (LATTICE_SIZE-1)。コンパイル時の定数 LATTICE_SIZE がある場合、コンパイラはさまざまな配列アクセス間の定数オフセットを決定できるため、lattice[i-1][j][k+1] のような正確なインデックスの計算は、これらのラップなしではるかに高速です。 .

最後に、その関数に対して生成されたアセンブラー出力を確認することをお勧めします (-S スイッチを使用してコンパイルし、生成された .s ファイルを確認してください)。コンパイラが「if」を「n++」の周りの条件付きジャンプに変換する場合 (これは に変換されinc %regます)、さらに最適化する余地が残されます。これは、条件付きジャンプが CPU によって誤って予測される傾向があり、多くの余分なクロック サイクルが発生するためです。 . cmov が使用されている場合、または "if" の結果が条件付き set ディレクティブ (setc や setg など) を介してレジスタに変換されている場合、コードはすでに最適に近づいている可能性があります。コンパイラが Intel x86 で setxx 操作を効率的に使用できるようにするには、結果カウント "n" を "unsigned char" に変換してみてください。

于 2013-08-13T07:30:08.670 に答える