トップ | puarts.com
メモ  |  制作記  |  開発記  |  日常の記録  |  デジタルコンテンツ制作  |  ファイアーエムブレム  |  ゲーム  |  C/C++  |  C#  |  PC/ソフトウェア  |  Web 開発  |  スクリプト言語  |  その他プログラミング  |  
「OpenMP」に関連する記事一覧

0  

OpenMP 内・外ループ並列化による処理速度計測実験

2011/10/30
OpenMPでステレオブロックマッチングを並列化していたのですが、2次元の画像で並列化を考えると必ずどこかに次のようなループ構造ができます。

for(y=0;  y<ysize;  y++) //外側ループ
    for(x=0;  x<xsize;  x++) //内側ループ

内側ループを並列化すると外側ループよりも並列化のための準備処理が外側ループの回数分必要になってしまい、縦軸探索の範囲が広い場合には余計な処理時間がかなり増えてしまうような気がしますが、どのくらい処理時間が違ってくるのかよく知りませんでした。

ということで試しに、ステレオブロックマッチングの縦横探索範囲を内側ループを並列化した場合と外側ループを並列化した場合のそれぞれの速度を計測してみました。

OS: Windows 7 64bit
CPU: Core i7-930
memory: 6GB
実験に使用した画像解像度: 397x410
探索範囲: x方向40pixel, y方向40pixel (1画素辺りの探索ループ回数は1600回)

以下が計測結果です。単位はsec。試行回数は少なすぎますが挙動を知りたかっただけなので5回としました。

並列化なし
28.05
27.95
27.91
27.72
28.02
average: 27.93
 
内側ループの並列化
10.76
10.72
10.58
10.51
10.31
average: 10.576
 
外側ループの並列化
9.74
9.55
9.77
9.63
9.55
average: 9.648

内側ループ並列化+Qtのプログレスバー更新
11.06
10.83
10.92
10.95
11.0
average: 10.952

外側ループ並列化+Qtのプログレスバー更新
9.98
9.88
10.05
10.02
10.21
average: 10.028
 

実験結果からやはり内側よりも外側のループを並列化させた方が若干速くなるらしいということがわかりました。そんなに劇的な違いは見られなかったので、もしも、外側ループが極端に少ない場合などは内側ループを並列化しておいても問題はなさそうです。

それと、プログレスバーを使おうとするとやはり若干速度は遅くはなりますが、こちらもそんなに大きなロスはなさそうなので問題なく使えそうです。

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

2011/10/27
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も並列化して、力の計算のところも並列化して、さらなる高速化やってみようと思います。

Core i7でのOpenMPによる並列化実験

2011/10/21
並列化というと何だか難しそうな印象があって今まで取り組もうともしていなかったのですが、マルチコアCPUのPCであればOpenMPで簡単な文をコード中に挿入するだけで並列化ができてしまうという話を大学の教授から教えてもらったのでVisual C++でOpenMPを使って、そんなに簡単に高速化ができてしまうものなのか試してみました。

Visual C++でのOpenMPの使うにはまず環境変数OMP_NUM_THREADSを作り、OMP_NUM_THREADSに並列化スレッド数を指定し、あとはVisual C++でOpenMPのディレクティブをコードの並列化したいところに挿入して、コンパイルオプションに/openmpを追加してコンパイルするだけという超簡単仕様。

コンパイルオプションに/openmpを追加する具体的な方法は次のようになります。
1. Visual C++でプロジェクトのプロパティを開く
2. 構成プロパティ >> C/C++ >> 言語 >> OpenMPのサポートを "はい (/openmp)" に変更する。
もしくは構成プロパティ >> C/C++ >> コマンドラインに直接/openmpを追加する。

ちなみに並列化スレッド数はコードの中にomp_set_num_threads(並列化スレッド数)というコードを入れてあげると環境変数を無視してスレッド数の設定が可能なようです。例えばスレッド数を2にしたいなら次のようにします。

omp_set_num_threads(2);

とりあえずサンプルを動かしてみようということでMSDNにあったVisual C++でOpenMPを扱ってπの計算を並列化するサンプルを動かしてみました。
http://msdn.microsoft.com/ja-jp/library/fw509c3b(v=vs.80).aspx

並列化しないのとするのとで変えて試してみると、ちゃんと並列化によって高速化になった結果が得られました。

上記サイトのサンプルを少し改変して、並列化したものと並列化しないもので速度を比較するようにしたコードに直したので載せておきます。

#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <iostream>
 
volatile DWORD dwStart;
volatile int global = 0;
 
using namespace std;
 
double test(int num_steps) {
    int i;
    global++;
    double x, pi, sum = 0.0, step;
 
    step = 1.0 / (double) num_steps;
 
    #pragma omp parallel for reduction(+:sum) private(x)
    for (i = 1; i <= num_steps; i++) {
        x = (i - 0.5) * step;
        sum = sum + 4.0 / (1.0 + x*x);
    }
 
    pi = step * sum;
    return pi;
}
 
int main(int argc, char* argv[]) {
    double   d;
    int n = 1000000000;
 
    if (argc > 1)
        n = atoi(argv[1]);
 
 
    cout<<"The number of processors is "<<omp_get_num_procs()<<endl;
    omp_set_num_threads(1);
    cout<<"OpenMP : Enabled (Max # of threads = "<<omp_get_max_threads()<<")"<<endl;
 
    dwStart = GetTickCount();
    d = test(n);
    int time1 = GetTickCount() - dwStart;
    printf_s("For %d steps, pi = %.15f, %d milliseconds\n", n, d, time1);
 
 
    for(int i=2; i<9; i++){
        omp_set_num_threads(i);
        cout<<"OpenMP : Enabled (Max # of threads = "<<omp_get_max_threads()<<")"<<endl;
        dwStart = GetTickCount();
        d = test(n);
        int time2 = GetTickCount() - dwStart;
        printf_s("For %d steps, pi = %.15f, %d milliseconds\n", n, d, time2);
        printf("%f\n", time2/static_cast<double>(time1));
    }
}

以下の環境でこのコードをテストしてみました。

OS: Windows 7 64bit
CPU: core i7 860
memory: 8GB

下の表は上記のテストプログラムを走らせ、出力結果を表にしたものです。本当は何回も試して平均をとるべきですが、1回でも特徴がちゃんと出たのでこの表は1回のサンプルのみで作りました。

スレッド数 処理時間(ms) スレッド1に対する処理時間比率
1 6832 1.0
2 3744 0.538934
3 2668 0.390515
4 2246 0.328747
5 2106 0.308255
6 1966 0.287763
7 1919 0.280884
8 1887 0.276200

こちらはスレッド数による処理時間の折れ線グラフです。

parallel_test_graph.jpg


core i7はハイパースレッティングによりCPU4コアでスレッドが8となっていますが、教授の話だとハイパースレッディングではコアは1つのコアの空き時間を利用して擬似的に並列にしているだけで、複数のスレッドが同時に同じCPUリソースを使えないため、実質OpenMPでの並列化は4スレッド程度の並列化になると考えていいそうです。
実験結果からも並列スレッド数が4を超えると、あまり処理時間に変化が見られなくなりました。

それにしても、こんなに簡単に並列化ができてしまうなんて、思ってもみなかったです。
どうやら並列化で大事になるのはプロセスの中で並列化できない部分をできるだけ高速にすることと、さらに並列化できそうなホットスポットを探して、関数にすることのようです。

並列化を自動的にやってくれるツールなどもあるようですが、むやみやたらに並列化を入れても、並列化をする際のオーバーヘッドもあるので遅くなってしまうとのことで、気をつけなければいけないようです。

自分が今まで作ったものもOpenMPで高速化できるようなものがないか探してみようと思います。
0  

にほんブログ村 ゲームブログ ファイアーエムブレムへ にほんブログ村 デザインブログ コンピュータグラフィックスへ

0.022 sec

Copyright(C)2006-2018 wsp All Rights Reserved