OpenMPでの最適なスレッド数

プログラミング全般

コア数に依存する数値があると思って調べたけど分からなかったので計測した。

環境

CPU
Intel Core 2 Duo T7200 @2.2GHz 2.2GHz
RAM
1GB x 2
コンパイラ
VC++ 2008 Expressについているもの
OpenMP
Windows SDKを入れたら使えた

コード

ひたすら素数を数えるもの。動いておけばいいので最適化とかはあまり考えていない。
まず並列化なし測定して、次にスレッド数を2, 4, 8...64と増やしながら計測する。128には設定できなかったので64まで。

#include <stdio.h>
#include <windows.h>
#include <omp.h>

#define LOOP 5
#define TEST 0xffff
#define FILEOUTPUT 0

//    return m == 1 ? 1:(n % m == 0 ? 0: is_prime(n, m - 1));
int is_prime(int n)
{
    int m;
    for (m = n - 1; m > 1; --m) {
        if (n % m == 0) {
            return 0;
        }
    }
    
    return 1;
}

int main(void)
{
    int n, s, e, t, i;
    int c = 0;
#if FILEOUTPUT
    FILE *fp;
#endif

    // 事前に少し動かしておく
    s = GetTickCount();
    for (n = 3; n < TEST; ++n) {
        if (is_prime(n)) {
            ++c;
        }
    }
    e = GetTickCount();
    
    // 標準計測
    for (i = 0; i < LOOP; ++i) {
#if FILEOUTPUT
        fp = fopen("./test", "w");
#endif
        c = 0;
        s = GetTickCount();
        for (n = 3; n < TEST; ++n) {
            if (is_prime(n)) {
                ++c;
#if FILEOUTPUT
                fprintf(fp, "%d\n", n);
                fflush(fp);
#endif
            }
        }
        e = GetTickCount();
        printf("S   : %d (%d)\n", e - s, c);
#if FILEOUTPUT
        fclose(fp);
#endif
    }
    for (t = 2; t <= 64; t *= 2) {
        // OpenMP計測
#ifdef _OPENMP
        omp_set_num_threads(t);
#endif
        for (i = 0; i < LOOP; ++i) {
#if FILEOUTPUT
            fp = fopen("./test", "w");
#endif
            c = 0;
            s = GetTickCount();
    
#ifdef _OPENMP
#pragma omp parallel for reduction(+:c)
#endif
            for (n = 3; n < TEST; ++n) {
//                if (omp_get_num_threads() != t) {
//                    fprintf(stderr, "illegal threads %d,%d\n", t, omp_get_num_threads());
//                }
                if (is_prime(n)) {
                    ++c;
#if FILEOUTPUT
                    fprintf(fp, "%d\n", n);
                    fflush(fp);
#endif
                }
            }
            e = GetTickCount();

            printf("M%-3d: %d (%d)\n", t, e - s, c);
#if FILEOUTPUT
            fclose(fp);
#endif
        }
    }
    getchar();

    return 0;
}

個人的予想では8が一番速い。

結果

ファイル出力はあってもなくてもそう変わらなかった。ディスクキャッシュ？
ファイル出力ありの結果。

// シングル/マルチ[スレッド数]: 完了時間ms: (素数数 @並列化がバグっていると変な値になる)
S   : 7862 (6541)
S   : 7863 (6541)
S   : 7956 (6541)
S   : 7878 (6541)
S   : 7925 (6541)
M2  : 6271 (6541)
M2  : 6240 (6541)
M2  : 6224 (6541)
M2  : 6225 (6541)
M2  : 6240 (6541)
M4  : 5522 (6541)
M4  : 5367 (6541)
M4  : 5304 (6541)
M4  : 5117 (6541)
M4  : 5631 (6541)
M8  : 4680 (6541)
M8  : 4696 (6541)
M8  : 4508 (6541)
M8  : 4353 (6541)
M8  : 4726 (6541)
M16 : 4431 (6541)
M16 : 4508 (6541)
M16 : 4493 (6541)
M16 : 4461 (6541)
M16 : 4181 (6541)
M32 : 4399 (6541)
M32 : 4259 (6541)
M32 : 4275 (6541)
M32 : 4227 (6541)
M32 : 4244 (6541)
M64 : 4228 (6541)
M64 : 4259 (6541)
M64 : 4243 (6541)
M64 : 4196 (6541)
M64 : 4525 (6541)

32で頭打ちな感じ。

感想

スレッド数が増えれば増えるほど速くなるのは、Windowsのスケジューラーがスレッド単位でまわしているから、スレッドが多いほうが得られる実行時間が長いとか？　うー、ハードのことは分からない。最適なスレッド > コア数ということは分かった。

けつろん

あまり納得のできる結果は得られなかったけど、16くらいにする。実行中に変数の同期を取るタイミングあったりするとまたややこしいことになりそう。Intelの意見が聞きたい。
とりあえず#pragma ompと書くだけで2倍の性能になったので、OpenMPすげー、実行速度を気にするならまず並列化しろー、と思いました。

このテストとは関係ないけど

再起で書くとスタックオーバーフローした。
コンパイラがこうだから、再起関数は使えないという認識がある。