ロゴ メインコンテンツへ
RSSフィード
「ソフトウェア開発」に関連する記事一覧

OpenMPでSPH全探索アルゴリズムを並列化

2011/10/27
(この記事の文字数: 1934)
2次元SPHシミュレーションプログラムの全探索プログラムにOpenMPを導入して並列化させてみました。
3000個の粒子の計算を1000フレーム分計算させた時間を5回計測し、それらの平均を取るという方法で処理時間を比較してみました。
 
環境は以下の通りです。
 
OS: Windows 7 64bit
CPU: Core i7 860 (2.80GHz)
Memory: 8GB
 
まず下記のようなプログラムが私が最初に書いた全探索のプログラムです。
 
MyParticle *pi, *pj;
for(i=0; i<num_prt; i++){
    pi = particle_list[i];
    for(j=i+1; j<num_prt; j++){
        pj = particle_list[j];
        if(particle_list[i]->GetDistanceSquare(particle_list[j]) < affect_radius){
            pi->neighbors().Append(pj);
            pj->neighbors().Append(pi);    
        }
    }
}

このプログラムの平均処理時間は40.31秒でした。
次にこちらは一時変数を使わないで書いたプログラムです。

for(i=0; i<num_prt; i++){
    for(j=i+1; j<num_prt; j++){
        if(particle_list[i]->GetDistanceSquare(particle_list[j]) < affect_radius){
            particle_list[i]->neighbors().Append(particle_list[j]);
            particle_list[j]->neighbors().Append(particle_list[i]);
        }
    }
}

こちらの平均処理時間は39.0006秒でした。見やすいようにと一時変数を使っていたのですが、1秒以上差が出たので、粒子シミュレーションのようなループの多いプログラムでは不要な一時変数を使うことは避けるべきだと思いました。
 
次に一時変数を使いつつ並列化したものです。近傍粒子として追加するところでは排他制御を行わないとシミュレーション中にプログラムが落ちてしまったので、criticalを使って排他制御を行うようにしました。
 

#ifdef _OPENMP
#pragma omp parallel
#endif
{
    int i, j;
    MyParticle *pi, *pj;
    #ifdef _OPENMP
    #pragma omp for
    #endif
    for(i=0; i<num_prt; i++){
        pi = particle_list[i];
        for(j=i+1; j<num_prt; j++){
            pj = particle_list[j];
            if(particle_list[i]->GetDistanceSquare(particle_list[j]) < affect_radius){
                #ifdef _OPENMP
                #pragma omp critical
                #endif
                {
                    pi->neighbors().Append(pj);
                    pj->neighbors().Append(pi);    
                }
            }
        }
    }
}

こちらの平均処理時間は25.662秒でした。
最後に一時変数を使わないで書きなおしたものを試しました。

#ifdef _OPENMP
#pragma omp parallel
#endif
{
    int i, j;
    #ifdef _OPENMP
    #pragma omp for
    #endif
    for(i=0; i<num_prt; i++){
        for(j=i+1; j<num_prt; j++){
            if(particle_list[i]->GetDistanceSquare(particle_list[j]) < affect_radius){
                #ifdef _OPENMP
                #pragma omp critical
                #endif
                {
                    particle_list[i]->neighbors().Append(particle_list[j]);
                    particle_list[j]->neighbors().Append(particle_list[i]);
                }
            }
        }
    }
}

こちらは平均時間が25.18秒でした。
並列化後は並列化前に比べて1.5倍ほど速くなりましたが、平均化後の方が時間にばらつきが多い結果になりました。排他制御で待ち時間が毎回変わってしまうことが影響していると思います。

全探索だけでなくLinked List Searchも並列化して、力の計算のところも並列化して、さらなる高速化やってみようと思います。

  このエントリーをはてなブックマークに追加  

<<「ソフトウェア開発」の記事一覧に戻る

<<「ソフトウェア開発」の次の記事
「ソフトウェア開発」の前の記事 >>

コメント(0 件)



コンテンツロード: 0.0084 sec
Copyright(C)2006-2024 puarts All Rights Reserved