2

opemMP を使用して、「Harmonic Progression Sum」問題の並列バージョンを作成しようとしています。しかし、出力は入力によって異なります。(パラレルおよびシーケンシャル)

プログラム：

#include "stdafx.h"
#include <iostream>
#include <sstream>
#include <omp.h>
#include <time.h>

#define d 10    //Numbers of Digits (Example: 5 => 0,xxxxx)
#define n 1000  //Value of N (Example: 5 => 1/1 + 1/2 + 1/3 + 1/4 + 1/5)

using namespace std;

void HPSSeguencial(char* output) {
    long unsigned int digits[d + 11];

    for (int digit = 0; digit < d + 11; ++digit)
        digits[digit] = 0;

    for (int i = 1; i <= n; ++i) {
        long unsigned int remainder = 1;
        for (long unsigned int digit = 0; digit < d + 11 && remainder; ++digit) {
            long unsigned int div = remainder / i;
            long unsigned int mod = remainder % i;
            digits[digit] += div;
            remainder = mod * 10;
        }
    }


    for (int i = d + 11 - 1; i > 0; --i) {
        digits[i - 1] += digits[i] / 10;
        digits[i] %= 10;
    }
    if (digits[d + 1] >= 5) {
        ++digits[d];
    }


    for (int i = d; i > 0; --i) {
        digits[i - 1] += digits[i] / 10;
        digits[i] %= 10;
    }
    stringstream stringstreamA;
    stringstreamA << digits[0] << ",";


    for (int i = 1; i <= d; ++i) {
        stringstreamA << digits[i];
    }
    string stringA = stringstreamA.str();
    stringA.copy(output, stringA.size());
}

void HPSParallel(char* output) {
    long unsigned int digits[d + 11];

    for (int digit = 0; digit < d + 11; ++digit)
        digits[digit] = 0;

    int i;
    long unsigned int digit;
    long unsigned int remainder;
    #pragma omp parallel for private(i, remainder, digit)
    for (i = 1; i <= n; ++i) {
        remainder = 1; 
        for (digit = 0; digit < d + 11 && remainder; ++digit) {
            long unsigned int div = remainder / i;
            long unsigned int mod = remainder % i;
            digits[digit] += div;
            remainder = mod * 10;
        }
    }

    for (int i = d + 11 - 1; i > 0; --i) {
        digits[i - 1] += digits[i] / 10;
        digits[i] %= 10;
    }
    if (digits[d + 1] >= 5) {
        ++digits[d];
    }

    for (int i = d; i > 0; --i) {
        digits[i - 1] += digits[i] / 10;
        digits[i] %= 10;
    }
    stringstream stringstreamA;
    stringstreamA << digits[0] << ",";

    for (int i = 1; i <= d; ++i) {
        stringstreamA << digits[i];
    }
    string stringA = stringstreamA.str();
    stringA.copy(output, stringA.size());
}

int main() {
    //Sequential Method
    cout << "Sequential Method: " << endl;
    char outputSeguencial[d + 10];
    HPSSeguencial(outputSeguencial);
    cout << outputSeguencial << endl;

    //Cleaning vector
    string stringA = "";
    stringA.copy(outputSeguencial, stringA.size());

    //Parallel Method
    cout << "Parallel Method: " << endl;
    char outputParallel[d + 10];
    HPSParallel(outputParallel);
    cout << outputParallel << endl;

    system("PAUSE");
    return 0;
}

例:

入力：

#define d 10
#define n 1000

出力：

Sequential Method:
7,4854708606╠╠╠╠╠╠╠╠╠╠╠╠
Parallel Method:
6,6631705861╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠ÇJ^

入力：

#define d 12
#define n 7

出力：

Sequential Method:
2,592857142857╠╠╠╠╠╠╠╠╠╠╠╠╠╠ÀÂ♂ü─¨@
Parallel Method:
2,592857142857╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠ÇJJ

よろしく

ペーストコード

http://pastecode.org/index.php/view/62768285

4

2 に答える 2

2

digits配列を更新するとき、スレッドはお互いのつま先を踏みます。したがって、いくつかの追加が失われ、偽の結果が得られます（実行ごとに異なる結果が得られます（ほぼ確実に）。

digitsたとえば、アトミック（またはクリティカル）セクションへの書き込みを同期する必要があります。

// ... <snip>
#pragma omp parallel for private(i, remainder, digit)
for (i = 1; i <= n; ++i) {
    remainder = 1; 
    for (digit = 0; digit < d + 11 && remainder; ++digit) {
        long unsigned int div = remainder / i;
        long unsigned int mod = remainder % i;
        #pragma omp atomic     // <- HERE, could also be #pragma omp critical
        digits[digit] += div;
        remainder = mod * 10;
    }
}
// <snip> ...

一度に1つのスレッドだけがアレイを更新できるようにします。ただし、このようなタスクの場合、タスクを複数のスレッドに分割することによるメリットはおそらく無効になります。

于 2012-11-14T22:22:43.897 に答える
1

Daniel Fischerが指摘したように、書き込み競合がありますが、セクションよりもエレガントに回避できます。omp criticalたとえば、各スレッドに独自のコピーを与えdigits、ループの最後にそれらすべてを集約することです。

于 2012-11-14T22:27:37.613 に答える