6

かなりうまく動作するコードがいくつかありますが、もっとうまく動作させたいと思います。私が抱えている主な問題は、ネストされたforループが必要なことです。外側のものは反復用であり（これは連続して発生する必要があります）、内側のものは検討中の各点粒子用です。外側のものについてできることはあまりないことは知っていますが、次のようなものを最適化する方法があるかどうか疑問に思っています。

    void collide(particle particles[], box boxes[], 
        double boxShiftX, double boxShiftY) {/*{{{*/
            int i;
            double nX; 
            double nY; 
            int boxnum;
            for(i=0;i<PART_COUNT;i++) {
                    boxnum = ((((int)(particles[i].sX+boxShiftX))/BOX_SIZE)%BWIDTH+
                        BWIDTH*((((int)(particles[i].sY+boxShiftY))/BOX_SIZE)%BHEIGHT)); 
                        //copied and pasted the macro which is why it's kinda odd looking

                    particles[i].vX -= boxes[boxnum].mX;
                    particles[i].vY -= boxes[boxnum].mY;
                    if(boxes[boxnum].rotDir == 1) {
                            nX = particles[i].vX*Wxx+particles[i].vY*Wxy;
                            nY = particles[i].vX*Wyx+particles[i].vY*Wyy;
                    } else { //to make it randomly pick a rot. direction
                            nX = particles[i].vX*Wxx-particles[i].vY*Wxy;
                            nY = -particles[i].vX*Wyx+particles[i].vY*Wyy;
                    }   
                    particles[i].vX = nX + boxes[boxnum].mX;
                    particles[i].vY = nY + boxes[boxnum].mY;
            }   
    }/*}}}*/

SIMDについてはあまりわかりませんが、SIMDを調べました。データを適切に抽出してパックするために必要な処理が、明らかに半分の命令を実行するだけの価値があるかどうかは完全にはわかりません。一度に2つのダブルを使用できます。

shmとpthread_barrierを使用して複数のスレッドに分割しようとしましたが（上記のコードが1つであるさまざまなステージを同期するため）、速度が低下しました。

私の現在のコードはかなり速く進みます。これは、10Mのパーティクル*反復ごとに1秒のオーダーであり、gprofからわかるように、私の時間の30％はその関数だけに費やされています（5000回の呼び出し、PART_COUNT = 8192パーティクルは1.8秒かかりました）。小さくて一定の時間のことは心配していません。512Kの粒子*50Kの反復*1000回の実験が前回1週間以上かかっただけです。

私の質問は、これらの長いベクトルを単にループするよりも効率的な方法があるかどうかだと思います。あるべきだと思いますが、見つかりません。

4

5 に答える 5

6

SIMD がどの程度の利益をもたらすかはわかりません。内側のループは非常に小さくてシンプルなので、(見ただけで) おそらく他の何よりもメモリに縛られていると思います。それを念頭に置いて、ループの主要部分を書き直して、必要以上にパーティクル配列に触れないようにします。

const double temp_vX = particles[i].vX - boxes[boxnum].mX;
const double temp_vY = particles[i].vY - boxes[boxnum].mY;

if(boxes[boxnum].rotDir == 1)
{
    nX = temp_vX*Wxx+temp_vY*Wxy;
    nY = temp_vX*Wyx+temp_vY*Wyy;
}
else
{
    //to make it randomly pick a rot. direction
    nX =  temp_vX*Wxx-temp_vY*Wxy;
    nY = -temp_vX*Wyx+temp_vY*Wyy;
}   
particles[i].vX = nX;
particles[i].vY = nY;

これには、最後に余分な追加を行わないという小さな潜在的な副作用があります。

別の潜在的な高速化は__restrict、粒子配列で使用することです。これにより、コンパイラは速度への書き込みをより適切に最適化できます。また、Wxx などがグローバル変数の場合、レジスタに格納するのではなく、ループのたびに再ロードする必要がある場合があります。を使用__restrictすると、それにも役立ちます。

順番にパーティクルにアクセスしているため、__builtin_prefetchキャッシュ ミスを減らすために、いくつかのパーティクルを先に (GCC などで) プリフェッチすることができます。予測できない順序でボックスにアクセスしているため、ボックスのプリフェッチは少し難しくなります。あなたは次のようなものを試すことができます

int nextBoxnum = ((((int)(particles[i+1].sX+boxShiftX) /// etc...
// prefetch boxes[nextBoxnum]

私が気付いた最後の 1 つ - box::rotDir が常に +/- 1.0 の場合、次のように内部ループで比較と分岐を削除できます。

const double rot = boxes[boxnum].rotDir; // always +/- 1.0
nX =     particles[i].vX*Wxx + rot*particles[i].vY*Wxy;
nY = rot*particles[i].vX*Wyx +     particles[i].vY*Wyy;

当然のことながら、プロファイリング前後の通常の警告が適用されます。しかし、これらはすべて役立つ可能性があり、SIMD に切り替えるかどうかに関係なく実行できると思います。

于 2010-07-18T21:49:29.507 に答える
3

ちなみにlibSIMDx86もあります！

http://simdx86.sourceforge.net/Modules.html

(コンパイル時に、gcc -O3 -msse2 などを試すこともできます)。

于 2010-07-19T08:33:21.963 に答える
2 
((int)(particles[i].sX+boxShiftX))/BOX_SIZE

sX が int の場合、コストがかかります (わかりません)。ループに入る前に、boxShiftX/Y を int に切り捨てます。

于 2010-07-18T19:40:22.783 に答える
1

その関数内のどこで時間が費やされているかを知るのに十分なプロファイリングがありますか?

たとえば、時間が費やされているのは boxnum 計算の div と mod ではないでしょうか? 人間 (または、少なくとも、私が知らない BOX_SIZE と BWIDTH/BHEIGHT を知っている人) ができる可能性がある場合でも、コンパイラは可能なシフト/AND の代替案を見つけられないことがあります。

コードの間違ったビットを SIMD 化するのに多くの時間を費やすのは残念なことです...

検討する価値のあるもう 1 つのことは、プロセッサの最適な使用方法について十分な情報に基づいた決定を下す IPP のようなライブラリで動作するものに作業を強制できるかどうかです。

于 2010-07-18T19:02:41.820 に答える