C言語での並列処理で総和の計算が一致しない。

Question

前提・実現したいこと

C言語において並列処理(pthread.h)を用いて0からnまでの総和を求めるプログラムの計算を行いたいと考えています。

該当のソースコード

ワークフローとしては

1. DATA_NUMで0から幾つまでの数の総和を求めるのか決め、DATANUMの値を基にそのサイズのdata二次元配列を作成する。
2. data[i][0]にiを代入、data[i][1]にdata[i][0]が計算済みか否かのフラグを導入
3. 並列処理部分の関数(do_calc)で並列処理を行い、data[i][0]の値をグローバル変数のsumに値を追加 , [i][1]に処理を行ったスレッドの番号を追加
4. main関数でsumをprintfし、各スレッドがsumに何回加算したか計算する。

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>


// 幾つのスレッドで並列処理を行うか
#define THREAD_NUM 4

// いくつまでの数の総和を求めるか
#define DATA_NUM 100000

// 結果を収納する配列
unsigned long data[DATA_NUM][2];

// 総和を収納する配列
unsigned long sum = 0;

//Mutexオブジェクト
pthread_mutex_t mutex;


pthread_t tid[THREAD_NUM]; // スレッドID を保持する配列
int param[THREAD_NUM];


//　プロトタイプ処理
void *do_calc(void *);


void *do_calc(void* arg) {

    // 1回の処理で担当する回数
    int Number_Interval;
    Number_Interval = DATA_NUM/THREAD_NUM;

    //StartするIndex
    int Start_Index , *id;
    id = arg; 
    Start_Index = *id * Number_Interval;

    //終わるIndex
    int Finish_Index;
    Finish_Index = Start_Index + Number_Interval;

    for(int i = Start_Index;i<Finish_Index;i++){

        // もし値が0(未作業)の場合は、data[i][0]の値をグローバル変数のsumに追加した後にdata[i][1]にスレッド番号を収納
        if (data[i][1] == 0){
            pthread_mutex_lock(&mutex);
            sum = sum + data[i][0];
            data[i][1] = arg;
            pthread_mutex_unlock(&mutex);
        }
    
    }
    pthread_exit(NULL);


}


int main(){

    // DATA_NUM-1の範囲で、data[i][0]にはiを代入 、 data[i][1]には0を代入
    for(int i = 0; i <DATA_NUM;i++){
        data[i][0] = i;
        data[i][1] = 0;
    }

    //Mutexオブジェクトの初期化
    pthread_mutex_init(&mutex, NULL);


    //指定された数のスレッドを作成する。
    for (int i =0; i < THREAD_NUM; i++){
        param[i] = i;
        pthread_create(&tid[i],NULL,do_calc,&param[i]);
    }


    for(int i=0; i<THREAD_NUM; i++){
        pthread_join(tid[i], NULL);
    }

    for(int i=0; i < DATA_NUM; i++){
        printf("%lu \n",data[i][1]);
        

    }

    printf("Sum is %lu \n",sum);

 

}



//i=0からdata[i][1]を調べて、それが0だったら、「作業」が済んでいないとみなして、data[i][0]の値をグローバル変数sumに加算する。

//「作業済み」として、data[i][1]にスレッドを区別する番号（例えば、1からTHREAD_NUMのどれか）を代入して次のiを調べる。

//iが DATA_NUM-1まで調べたら各スレッドは終了する。

//すべてのスレッドが終了したら、mainの中で、sumの値と、各スレッドがsumに何回加算したかを表示する。

//各スレッドがsumに何回加算したかは、data[i][1]を全部調べて、その値を表示してください。

//sumを正しく計算するために、グローバル変数sumへの加算時と、data[i][1]で作業済みかどうかのチェックなどで必要な排他制御を行うプログラムにしてください。
//DATA_NUMが100の場合、0から99の和ですから、4950が答えになるはずです。

発生している問題・エラーメッセージ

大方の実装は終わっているのですが、DATA_NUMの値が100000を超えた時の総和がおかしくなる、ワークフロー4.の「各スレッドがsumに何回加算したか計算する」の実装を行うにあたってスレッド番号が大きくなってしまう(実際の0,1,2,3...)というエラーが解決できていないです。

DATA_NUM = 100 THREAD_NUM = 4 の時

4212384 
...
4212388 
....
4212392 
...
4212396 
-------------
Sum is 4950 
-------------

DATA_NUM = 1000 THREAD_NUM = 4 の時
-------------
Sum is 4995000
-------------

DATA_NUM = 10000 THREAD_NUM = 4 の時
-------------
Sum is 4995000
-------------

DATA_NUM = 100000 THREAD_NUM = 4 の時
-------------
Sum is 5
-------------

補足情報（FW/ツールのバージョンなど）

paiza ioでコンパイルしました。

Comments

[kaina]

>DATA_NUMの値が100000を超えた時の総和がおかしくなる
とありますが、別にDATA_NUMの値が100000以外も全部間違った総和ですよ？
まずTHREAD_NUMを1、DATA_NUMを10辺りにしてデバッグしたほうが良いかと思います。

[Savanof]

仕様の説明が曖昧でした。総和の意味は0~(DATA_NUM-1)という意味で言っていました。その場合は100000以外の総和は正しいと思います。
https://ja.wolframalpha.com/input/?i=0%2B1%2B2%2B...%2B99

Answer 1

sum = sum + data[i][0];

グローバル変数sumへの操作がアトミック操作ではないためsumが不定になります。

この場合はそれぞれのスレッドの範囲内の合計を計算した後にpthread_exit,pthread_joinでメインスレッドに戻した後に合計してやるとよいと思います。
こんな感じ

スレッド番号が大きくなってしまう

については、argがポインタだからです。

int id = *(int*)arg;

みたいにしないといけません。

Comments

[asm]

今回の場合変数sumに対し排他制御するとスレッドを使う意味がなくなると思っています。

[Savanof]

リンク付きでの解説ありがとうございます、キーワードが分かったので後は自決できそうです。

Answer 2

sum = sum + data[i][0];

を実行するとき、コンピュータ(つまりCPU)は
(1)sumという変数(で表されるアドレスのメモリ)をレジスタに持ってきて、
(2)それにdata[i][0]を加えてから、
(3)もとのメモリに書き戻します。

スレッド並列を行っていると、以下の順番に処理が起こる可能性があります。

スレッドA(1)sumという変数(で表されるアドレスのメモリ)をレジスタに持ってくる。
スレッドB(1)sumという変数(で表されるアドレスのメモリ)をレジスタに持ってくる。
スレッドA(2)それにdata[iA][0]を加える。
スレッドB(2)それにdata[iB][0]を加える。
スレッドA(3)もとのメモリに書き戻す。
スレッドB(3)もとのメモリに書き戻す。

これが起こると、data[iA][0]を加えた結果は一旦sumに保管されますが、その直後にスレッドBの書込みによって失われます。

従って、スレッド並列で同じメモリ領域(変数)に書き込むと、結果が正しくないことは良く起こります。
これを避けるためには、akiruno-oneoneさんが書いているように排他処理が必要です。

Comments

[Savanof]

返信ありがとうございます。mutexを使用した排他処理をおこなって同時にsumにアクセスできないような処理を加えたのですが、未だに一部の結果がおかしいです。mutexの使い方がおかしかったりしますか?

Answer 3

スレッド間で共有されるデータにアクセスする場合は、排他処理が必要です。
ぱっとみたところ、計算結果を格納するsumはスレッド間で排他処理がされていません。
mutexなどで排他処理を行いましょう。

Comments

[Savanof]

mutexで排他処理を行ってみたのですが、結果変わらず、値が同じままでした...
コードを更新したので、もし可能であればmutexの使い方を教えて頂けませんか?

Answer 4

(ふと見直したら適切なサイズになっていました。私の質問のコードの見間違えでした.... ）

排他制御についてみんな書かれているので、そもそもなんですが、int型のサイズを越えた計算になっていないか確認した方がいいですね。

intは型c言語だと大抵の場合（処理系依存ですが）、2byteとか4byteだと思います。とりあえず4byteとして、符号付きなので、 -2^31 ~ (2^31-1) [2^nは2のn乗とする]の範囲になります。この正の数の最大値を計算すると、わかりやすいように3桁でコンマを入れて記述します。

2^32 -1
= 2,147,483,647

とります。で、1 ~ (n-1)までの総和は sum(n)=n * (n-1) / 2となるので、

sum(100000) = 100000/2 * (100000 - 1)
= 4,999,950,000

となります。もし4byteのサイズであれば、なのでどこかでint型のサイズが溢れます。

なので、範囲は負数を使わないので、（おそらくですが）unsinged longあたりを使うべきでしょう。（あくまでサイズは処理系依存なので、適切サイズになるようにしてくださいね）