如何并行化给定的算法 [英] How to parallelize the given algorithm

问题描述

我已经转换了书中给出的GE算法。现在我想使用MPI并行化它。有人可以指导我如何做到这一点。我的序列版本如下：

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;
     }
} 

有些人请指导我。



我尝试过的事情：





我在网上搜索。



Zulfi。

Some body please guide me.

What I have tried:

Hi,
I am searching web.

Zulfi.

推荐答案

并行算法的主要问题是识别100％独立的代码片段代码的其余部分，在某种意义上说，处理每个部分的顺序无关紧要。对于原始形式的高斯消除，这是不可能的：每一步都建立在另一步上。



是的，你可以并行运行最里面的循环体，但是这些只包含一个语句，并且创建一个线程会占用更多的资源和处理时间 - 那么重点是什么？



这提出了一个问题：什么是你希望通过并行化GE实现目标吗？





PS：我怀疑它是否有可能以有意义的方式并行化GE ，但我知道优化的库可以非常有效地完成这类工作，所以我做了一个搜索，发现了这篇文章：

使用MPI进行并行高斯消除（pdf） [ ^ ]

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)[^]

是的，除非我们使用流水线技术，否则内部循环可以是最外层的。

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。

Zulfi.

这篇关于如何并行化给定的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！