How to parallelize the given algorithm

Question

1.00/5 (1 vote)

See more:

Hi,
I have converted the GE algorithm given in the book. Now I want to parallelize it using MPI. Can somebody please guide me how to do that. My serial version is given below:

void GaussianElimination(double **A, double *b,double *y) {
     cout<<"Inside Gaussian 1";
     for(int k=0; k<=n-1; ++k) {
        cout<<"k =" <<k<<endl;
        for(int j= k+1; j <=n-1; ++j){
           cout<<"A["<<k<<"]["<<k<<"] =" <<A[k][k] <<endl;
           A[k][j] = A[k][j]/A[k][k]; 
         }
      
       
        y[k] = b[k]/A[k][k];
        A[k][k]=1;
        cout<<"Reached";
        for(int i=k+1; i<=n-1; i++){
           for(int j=k+1; j<=n-1; j++)
              A[i][j] = A[i][j] -A[i][k] *A[k][j];
           b[i]= b[i] -A[i][k] * y[k];
           A[i][k] = 0;
        }
     }
     cout<<"answers"<<endl;
     for(int i=0; i<=n-1; i++){
        for(int j=0;j<=n-1;j++)
        cout<<A[i][j]<<" ";
        cout<<endl;
     }
}

Some body please guide me.

What I have tried:

Hi,
I am searching web.

Zulfi.

Posted 2-May-19 7:45am

zak100

Updated 9-May-19 0:32am

Add a Solution

Comments

[no name] 2-May-19 15:51pm

Have you figured out what can run parallel?

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Stefan_Lang · Answer 1 · 2019-05-09T00:33:00

The main problem in parallelizing an algorithm is identifying pieces of code that are 100% independent of the rest of the code, in the sense that the order of processing each of the pieces does not matter. For Gaussian elimination in its original form, this is not easily possible: every step builds on another.

Yes you can run the body of the innermost loops in parallel, but these only consist of a single statement, and creating a thread takes way more resources and processing time - so what would be the point?

Which raises the question: what is the goal that you want to achieve by parallelizing GE?

P.S.: I doubted that its' possible to parallelize GE in a meaningful way, but I knew that optimized libraries can do this kind of stuff very efficiently, so I did a search, and found this article:
Parallel Gaussian Elimination using MPI (pdf)[^]

zak100 · Answer 2 · 2019-05-02T10:27:00

Solution 1

Hi,
Yes, the inner loop can be, outermost can't be unless we use pipelined technique.

for(int j= k+1; j <=n-1; ++j){
          :
          
          :
          :
   

     }

Zulfi.

Posted 2-May-19 10:27am

zak100

Comments

[no name] 2-May-19 17:12pm

The inner loop depends on "k" from the outer loop; and the rest of the outer loop depends on the results of the inner loop. You need multiple outer loops if you want to start multiple "inners" in parallel.

And, you've "answered" your own question.

zak100 2-May-19 17:39pm

Hi,
One naive approach could be:
if(rank == 0){
k=0;
for(int j= k+1; j <=n-1; ++j){
:

:
:

}
}
else if(rank == 1) {
k=1;
:
:
}
else if (rank== 20){//
k=20;
:
:
}
Can any body please improve on this?

Zulfi.