auの日記

プログラミング初心者の日記。(auはハンドルネームです)

非決定アルゴリズムって何だろう

auです。

コンピュータのシステムについて学んでいるときに、「OpenMPは非決定的である」という用語が出てきたのですが、何のことだろうと思い調べてみました。

非決定的とは

非決定的とは、非決定アルゴリズムとも呼ばれ、動作結果を予測できないものを指します。

つまり・・・どういうこと?と思うかもしれないですが、OpenMPを例にして解説していこうと思います。

OpenMPとは、主にC言語で用いられる並列化処理を行うためのAPIであり、指示文と呼ばれるものを並列化させたいプログラムの直前に書くことで、簡単に実装することができます。

6つのプロセッサーがある場合、スレッドの数が6つの並列処理になるため以下のようになります。

#include <stdio.h>

int main(void)
{
    # pragma omp parallel /* ここより下が並列化される */ 
    printf("Hello World!\n");
    return 0;
}

// 実行結果
Hello World!
Hello World!
Hello World!
Hello World!
Hello World!
Hello World!

以前記事にしたように、プロセッサー分の実行結果が出力されていることが分かりました。

これだと、6つのスレッドがあるが、どのスレッドから呼び出された「Hello World!」なのかわからないため、番号を表示することにします。

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

int main(void)
{
    int max_thread = 0;
    int thread_number = 0;
    max_thread = omp_get_max_threads(); // 最大スレッド数の取得
    # pragma omp parallel for
    for (int i = 0; i < max_thread; i++) {
        thread_number = omp_get_thread_num(); // 実行しているスレッド番号の取得
        printf("thread num: %d  Hello World!\n", thread_number);
    }
    return 0;
}

// 実行結果
thread num: 0  Hello World!
thread num: 1  Hello World!
thread num: 5  Hello World!
thread num: 2  Hello World!
thread num: 4  Hello World!
thread num: 3  Hello World!

このように、スレッドの番号はバラバラになっていることがわかると思います。これは、予測ができず、実行するたびに番号が変わってしまいます。

長くなってしまいましたが、非決定に話を戻すと、処理結果が予測できないアルゴリズムをもつプログラムのことを指します。