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

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

アルゴリズム1：素数を求める

　素数とはなんでしょうか。1と、その数以外の数では割り切ることができない数です。では、どうやってこれを求めましょうか。2からその数の手前までの数で順番に割ってみて、割りきれる数があるかどうか調べます。つまり、11が素数かどうか調べるには、2、3、4、5、6、7、8、9、10で割り切れるかどうかを調べます。コードで示すと次のようになります。

素数を判別するコード例

// 素数かどうか、判別する
// 戻り値：0…素数ではない / 0以外…素数
int IsPrimeNumber(const int 調べる数)
{
  for (int i = 2; i < 調べる数; ++i) {
      if (調べる数 % i == 0) {
          return 0;
      }
  }
  return 1;
}

　素数を求めたい範囲について、for文でループします。それぞれの数についてこの判別関数を通すことで、素数かどうかを調べます。とりあえず、この関数では「素数の数」だけ返すようにします。処理を並列化することの効率を測定するので、コンソールへの出力は行いません。コンソールへの出力がシリアル化される、コンソール出力は遅い処理である、というのが理由です。求めた素数は配列へ格納します。配列を動的に拡張すると、メモリを確保するという並列化できない要素が出てくるため、呼び出し側で確保しておくこととします。

ある数までの素数を求めるコード例

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;
}

　これで「ある数までの素数の数を求めるコード」ができました。では、このコードが正しいかどうか、検証します。コードによって、1～20までの素数の数を求めさせます。これくらいなら、自分で計算もできるでしょう。その結果とつきあわせます。

素数（の数）を求めるコードを検証するコード

#include "stdafx.h"
#include <iostream>
#include <omp.h>
int IsPrimeNumber(const int 調べる数) をここに
int GetPrimeNumbers(const int この数まで, int *素数配列 = NULL, const int 配列数 = 0) をここに
int _tmain(int argc, _TCHAR* argv[])
{
    std::cout << GetPrimeNumbers(2) << "個/2…1\n";
    std::cout << GetPrimeNumbers(3) << "個/3…2\n";
    std::cout << GetPrimeNumbers(4) << "個/4…2\n";
    std::cout << GetPrimeNumbers(5) << "個/5…3\n";
    std::cout << GetPrimeNumbers(6) << "個/6…3\n";
    std::cout << GetPrimeNumbers(7) << "個/7…4\n";
    std::cout << GetPrimeNumbers(8) << "個/8…4\n";
    std::cout << GetPrimeNumbers(9) << "個/9…4\n";
    std::cout << GetPrimeNumbers(10) << "個/10…4\n";
    std::cout << GetPrimeNumbers(11) << "個/11…5\n";
    std::cout << GetPrimeNumbers(12) << "個/12…5\n";
    std::cout << GetPrimeNumbers(13) << "個/13…6\n";
    std::cout << GetPrimeNumbers(14) << "個/14…6\n";
    std::cout << GetPrimeNumbers(15) << "個/15…6\n";
    std::cout << GetPrimeNumbers(16) << "個/16…6\n";
    std::cout << GetPrimeNumbers(17) << "個/17…7\n";
    std::cout << GetPrimeNumbers(18) << "個/18…7\n";
    std::cout << GetPrimeNumbers(19) << "個/19…8\n";
    std::cout << GetPrimeNumbers(20) << "個/20…8\n";
    return 0;
}

実行結果

1個/2…1
2個/3…2
2個/4…2
3個/5…3
3個/6…3
4個/7…4
4個/8…4
4個/9…4
4個/10…4
5個/11…5
5個/12…5
6個/13…6
6個/14…6
6個/15…6
6個/16…6
7個/17…7
7個/18…7
8個/19…8
8個/20…8

　コードが正しいことが検証できました。これを基に、マルチスレッド化のためのコードを追加します。

GetPrimeNumbersをマルチスレッド化する

int GetPrimeNumbersParallel(const int この数まで, int *素数配列 = NULL, const int 配列数 = 0)
{
    int index = 0;
    int count = 0;
#pragma omp parallel for
    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;
}

　これも、検証しておきます。GetPrimeNumbersがシングルスレッドで動作することと、GetPrimeNumbersParallelがマルチスレッドで動作しているかを確認します。確認を行う土台が、確認を行う目的にとって正しいことを確認しておかないと、何を確認しているのかわからなくなります。

　次のように_tmain関数を書き換え、実行します。実行中、タスクマネージャーの［プロセス］タブで実行しているプロセスのスレッド数と、CPU使用率を見ます。スレッド数は、初期状態では表示されていないので、［表示］メニューから［列の選択］を選び、一覧から［スレッド数］を探してチェックします。シングルスレッドの方は、スレッド数が“1”、CPU使用率は“(100/CPU数)％”であることを確認します。また、マルチスレッドの方は、スレッド数が“CPU数”、CPU使用率が“100％”であることを確認します。もし、マルチスレッド側のスレッド数が“1”の場合、プロジェクトのプロパティで、［構成プロパティ］→［C/C++］→［言語］を開き、［OpenMPサポート］が「はい(/openmp)」になっていることを確認してください。

シングルスレッドであることを確認する

int _tmain(int argc, _TCHAR* argv[])
{
    GetPrimeNumbers(300000);
    return 0;
}

マルチスレッドであることを確認する

int _tmain(int argc, _TCHAR* argv[])
{
    GetPrimeNumbersParallel(300000);
    return 0;
}