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