6

MPI と opemMP を併用して、「Harmonic Progression Sum」問題の並列バージョンを作成しようとしています。しかし、出力はプロセスごとに異なります。

誰かがこの問題を終わらせるのを手伝ってくれませんか?

並列プログラム: (MPI および OpenMP)

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <time.h>
#include <omp.h>
#include <mpi.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;

double t_ini, t_fim, t_tot;

int getProcessId(){
    int rank;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    return rank;
}

int numberProcess(){
    int numProc;
    MPI_Comm_size(MPI_COMM_WORLD, &numProc);
    return numProc;
}

void reduce(long unsigned int digits1 [])
{
    long unsigned int digits2[d + 11];
    int i = 0;
    for(i = 0; i < d + 11; i++) digits2[i] = 0;

    MPI_Allreduce(digits1, digits2,(d+11),MPI_INT,MPI_SUM,MPI_COMM_WORLD);

    for(i = 0; i < d + 11; i++) digits1[i] = digits2[i];

}

void slave(long unsigned int *digits)
{
    int idP = getProcessId(), numP = numberProcess();

    int i;
    long unsigned int digit;
    long unsigned int remainder;

    #pragma omp parallel for private(i, remainder, digit)
    for (i = idP+1; i <= n; i+=numP){
        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
            digits[digit] += div;
            remainder = mod * 10;
        }
    }
}

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

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

    reduce(digits);
    slave(digits);

    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(int argc, char **argv) {
    MPI_Init(&argc,&argv);

    t_ini = clock();

    //Parallel MPI com OpenMP Method
    cout << "Parallel MPI com OpenMP Method: " << endl;
    char output[d + 10];
    HPS(output);

    t_fim = clock();
    t_tot = t_fim-t_ini;

    cout << "Parallel MPI with OpenMP Method: " << (t_tot / 1000) << endl;
    cout << output << endl;

    MPI_Finalize();

    system("PAUSE");
    return 0;
}

例:

入力：

#define d 10
#define n 1000

出力：

7,4854708606

入力：

#define d 12
#define n 7

出力：

2,592857142857
4

1 に答える 1

4

ここで間違いがあります：

void HPS(char* output) {
    ...
    reduce(digits);
    slave(digits);

    ...
}

最初に計算してからリダクションを実行する必要があります。その逆ではありません。への変更：

void HPS(char* output) {
    ...

    slave(digits);
    reduce(digits);
    ...
}

MPI + OpenMP を使用したいので、これを残すこともできます:

for (i = idP+1; i <= n; i+=numP)

プロセス間で分割する。そして内側のループはスレッド間で分割されます:

 #pragma omp parallel for private(remainder)
 for (digit = 0; digit < d + 11 && remainder; ++digit)

したがって、次のようなものがあります：

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

また、必要に応じて (これはあなたが行ったことと同様です)、次のように、すべての並列タスク (スレッド/プロセス) で外側のループの作業数を分割することもできます。

int idT = omp_get_thread_num();      // Get the thread id
int numT = omp_get_num_threads();    // Get the number of threads.
int numParallelTask = numT * numP;   // Number of parallel task
int start = (idP+1) + (idT*numParallelTask); // The first position here each thread will work

#pragma omp parallel
{

for (i = start; i <= n; i+=numParallelTask)

...
}

これで最高のパフォーマンスが得られると言っているわけではありませんが、これはスタートです。MPI+OpenMP でアルゴリズムが適切に機能するようになったら、より高度なアプローチに進むことができます。

于 2012-11-24T21:09:57.580 に答える