処理並列は、必ず処理速度が向上するのか

3つのアルゴリズムを並列化

　さて、一通りできました。ここまでのコードを、もう一度掲示しておきます。

検証コード（全体）

#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <omp.h>
#include <sys/types.h>
#include <sys/timeb.h>
#include <time.h>
#include <stdlib.h>
#define PRIMENUMBERS      500000
#define FIZZBUZZMAX     30000000
#define BSORTNUM           30000
#define ROUNDCOUNT             5
char FB結果[FIZZBUZZMAX][12];
int BS配列[BSORTNUM];
#define TmToSec(X) ((X).time + (X).millitm / 1000.0)
#define DiffTmSec(START, STOP) (TmToSec(STOP) - TmToSec(START))
// 素数かどうか、判別する
// 戻り値：0…素数ではない / 0以外…素数
int IsPrimeNumber(const int 調べる数)
{
    for (int i = 2; i < 調べる数; ++i) {
        if (調べる数 % i == 0) {
            return 0;
        }
    }
    return 1;
}
int IsPrimeNumberFast(const int 調べる数)
{     
    if (調べる数 == 2) { return 1;}
    if (調べる数 % 2 == 0) { return 0;}
    int limit = (int) sqrt((double)調べる数);
    for (int i = 3; i <= limit; i += 2) {
        if (調べる数 % i == 0) {
            return 0;
        }
    }
    return 1;
}
int GetPrimeNumbers(const int この数まで, int *素数配列 = NULL, const int 配列数 = 0)
{
    int index = 0;
    int count = 0;
    for (int i = 2; i <= この数まで; ++i) {
        if (IsPrimeNumber(i) != 0) {
            ++count;
            if (素数配列 != NULL && index < 配列数) {
                素数配列[index++] = i;
            }
        }
    }
    return count;
}
int GetPrimeNumbersParallel(const int この数まで, int *素数配列 = NULL, const int 配列数 = 0)
{
    int index = 0;
    int count = 0;
    #pragma omp parallel for schedule(static)
    for (int i = 2; i <= この数まで; ++i) {
        if (IsPrimeNumber(i) != 0) {
#pragma omp atomic
            ++count;
            if (素数配列 != NULL) {
#pragma omp critical
                if (index < 配列数) {
                    素数配列[index++] = i;
                }
            }
        }
    }
    return count;
}
void FizzBuzz(const int この数まで)
{     
    for (int i = 1; i <= この数まで; ++i) {
        if (i % 15 == 0) {
            strcpy_s(FB結果[i], sizeof(FB結果[i]), "FizzBuzz");
        } else if (i % 3 == 0) {
            strcpy_s(FB結果[i], sizeof(FB結果[i]), "Fizz");
        } else if (i % 5 == 0) {
            strcpy_s(FB結果[i], sizeof(FB結果[i]), "Buzz");
        } else {
            sprintf_s(FB結果[i], sizeof(FB結果[i]), "%d", i);
        }
    }
}
void FizzBuzzParallel(const int この数まで)
{
#pragma omp parallel for
    for (int i = 1; i <= この数まで; ++i) {
        if (i % 15 == 0) {             
            strcpy_s(FB結果[i], sizeof(FB結果[i]), "FizzBuzz");
        } else if (i % 3 == 0) {             
            strcpy_s(FB結果[i], sizeof(FB結果[i]), "Fizz");
        } else if (i % 5 == 0) {             
            strcpy_s(FB結果[i], sizeof(FB結果[i]), "Buzz");
        } else {             
            sprintf_s(FB結果[i], sizeof(FB結果[i]), "%d", i);
        }
    }
}
void BubbleSort(int* 対象配列, const int 配列数)
{     
    for (int 決定済み数 = 0; 決定済み数 < 配列数; ++決定済み数) {
        for (int y = 配列数 - 1; y > 決定済み数; --y) {
            if (対象配列[y] < 対象配列[y - 1]) {
                int tmp = 対象配列[y];
                対象配列[y] = 対象配列[y - 1];
                対象配列[y - 1] = tmp;
            }
        }
    }
}
void BubbleSortParallel(int* 対象配列, const int 配列数)
{
#pragma omp parallel for ordered
    for (int 決定済み数 = 0; 決定済み数 < 配列数; ++決定済み数) {
        for (int y = 配列数 - 1; y > 決定済み数; --y) {
#pragma omp critical
            if (対象配列[y] < 対象配列[y - 1]) {
                int tmp = 対象配列[y];
                対象配列[y] = 対象配列[y - 1];
                対象配列[y - 1] = tmp;
            }
        }
    }
}
void Shuffle(int *対象配列, const int 配列数)
{
    for (int i = 0; i < 配列数; ++i) {
        対象配列[i] = i + 1;
    }
    int half = 配列数 / 2;
    int r = rand() % half;
    for (int i = 0; i < (half + r); ++i) {
        int b = rand() % half + half;
        int s = rand() % half;
        int tmp = 対象配列[b];
        対象配列[b] = 対象配列[s];
        対象配列[s] = tmp;
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    struct _timeb startTm, stopTm;    // ストップウォッチ用
    srand((unsigned int) time(0));
    int cnt;     
    double bsSeri = 0.0, bsPall = 0.0;
    double fbSeri = 0.0, fbPall = 0.0;
    double pnSeri = 0.0, pnPall = 0.0;
    std::cout << "素数の数を求める範囲\t" << PRIMENUMBERS << "\n";
    std::cout << "FizzBuzz を求める範囲\t" << FIZZBUZZMAX << "\n";
    std::cout << "Bubble Sort の要素数\t" << BSORTNUM << "\n";
    std::cout << "繰り返し回数\t" << ROUNDCOUNT << "\n";
    std::cout << "\n";
    /**/
    for (int i = 0; i < ROUNDCOUNT; ++i) {
        Shuffle(BS配列, BSORTNUM);
        _ftime_s(&startTm);
        BubbleSort(BS配列, BSORTNUM);
        _ftime_s(&stopTm);
        std::cout << "BubbleSort シリアル\t" << DiffTmSec(startTm, stopTm) << " sec.\n";
        bsSeri += DiffTmSec(startTm, stopTm);
    }
    /**/
    for (int i = 0; i < ROUNDCOUNT; ++i) {
        _ftime_s(&startTm);
        FizzBuzz(FIZZBUZZMAX);
        _ftime_s(&stopTm);
        std::cout << "FizzBuzz シリアル\t" << DiffTmSec(startTm, stopTm) << " sec.\n";
        fbSeri += DiffTmSec(startTm, stopTm);
    }
    /**/
    for (int i = 0; i < ROUNDCOUNT; ++i) {
        _ftime_s(&startTm);
        cnt = GetPrimeNumbers(PRIMENUMBERS);
        _ftime_s(&stopTm);
        std::cout << "素数 シリアル " << cnt << "個\t" << DiffTmSec(startTm, stopTm) << " sec.\n";
        pnSeri += DiffTmSec(startTm, stopTm);
    }
    /**/
    for (int i = 0; i < ROUNDCOUNT; ++i) {
        Shuffle(BS配列, BSORTNUM);
        _ftime_s(&startTm);
        BubbleSortParallel(BS配列, BSORTNUM);
        _ftime_s(&stopTm);
        std::cout << "BubbleSort パラレル\t" << DiffTmSec(startTm, stopTm) << " sec.\n";
        bsPall += DiffTmSec(startTm, stopTm);
    }
    /**/
    for (int i = 0; i < ROUNDCOUNT; ++i) {
        _ftime_s(&startTm);
        FizzBuzzParallel(FIZZBUZZMAX);
        _ftime_s(&stopTm);
        std::cout << "FizzBuzz パラレル\t" << DiffTmSec(startTm, stopTm) << " sec.\n";
        fbPall += DiffTmSec(startTm, stopTm);
    }
    /**/
    for (int i = 0; i < ROUNDCOUNT; ++i) {
        _ftime_s(&startTm);
        cnt = GetPrimeNumbersParallel(PRIMENUMBERS);
        _ftime_s(&stopTm);
        std::cout << "素数 パラレル " << cnt << "個\t" << DiffTmSec(startTm, stopTm) << " sec.\n";
        pnPall += DiffTmSec(startTm, stopTm);
    }
    /**/
    std::cout << "\n";
    std::cout << "BubbleSort シリアル平均 " << (bsSeri / (float) ROUNDCOUNT) << " sec.\n";
    std::cout << "BubbleSort パラレル平均 " << (bsPall / (float) ROUNDCOUNT) << " sec.\n";
    std::cout << "FizzBuzz シリアル平均 " << (fbSeri / (float) ROUNDCOUNT) << " sec.\n";
    std::cout << "FizzBuzz パラレル平均 " << (fbPall / (float) ROUNDCOUNT) << " sec.\n";
    std::cout << "素数 シリアル平均 " << (pnSeri / (float) ROUNDCOUNT) << " sec.\n";
    std::cout << "素数 パラレル平均 " << (pnPall / (float) ROUNDCOUNT) << " sec.\n";
    std::cout << "\n";
    std::cout << "BubbleSort 処理効率 " << (bsSeri / bsPall) << "\n";
    std::cout << "FizzBuzz 処理効率 " << (fbSeri / fbPall) << "\n";
    std::cout << "素数 処理効率 " << (pnSeri / pnPall) << "\n";

    return 0;
}

実行結果（一例）

素数の数を求める範囲    500000
FizzBuzz を求める範囲   30000000
Bubble Sort の要素数    30000
繰り返し回数    5

BubbleSort シリアル     3.651 sec.
BubbleSort シリアル     3.853 sec.
BubbleSort シリアル     3.9 sec.
BubbleSort シリアル     3.682 sec.
BubbleSort シリアル     3.807 sec.
FizzBuzz シリアル       11.384 sec.
FizzBuzz シリアル       10.92 sec.
FizzBuzz シリアル       10.921 sec.
FizzBuzz シリアル       10.874 sec.
FizzBuzz シリアル       10.921 sec.
素数 シリアル 41538個   52.481 sec.
素数 シリアル 41538個   52.497 sec.
素数 シリアル 41538個   52.606 sec.
素数 シリアル 41538個   52.45 sec.
素数 シリアル 41538個   52.543 sec.
BubbleSort パラレル     54.057 sec.
BubbleSort パラレル     56.287 sec.
BubbleSort パラレル     56.474 sec.
BubbleSort パラレル     56.443 sec.
BubbleSort パラレル     56.459 sec.
FizzBuzz パラレル       5.943 sec.
FizzBuzz パラレル       5.882 sec.
FizzBuzz パラレル       5.819 sec.
FizzBuzz パラレル       5.819 sec.
FizzBuzz パラレル       5.804 sec.
素数 パラレル 41538個   38.533 sec.
素数 パラレル 41538個   38.767 sec.
素数 パラレル 41538個   39.001 sec.
素数 パラレル 41538個   38.924 sec.
素数 パラレル 41538個   38.814 sec.

BubbleSort シリアル平均 3.7786 sec.
BubbleSort パラレル平均 55.944 sec.
FizzBuzz シリアル平均 11.004 sec.
FizzBuzz パラレル平均 5.8534 sec.
素数 シリアル平均 52.5154 sec.
素数 パラレル平均 38.8078 sec.

BubbleSort 処理効率 0.0675425
FizzBuzz 処理効率 1.87993
素数 処理効率 1.35322