zak100 Ответов: 2

Как распараллелить данный алгоритм


Привет,
Я преобразовал алгоритм GE, приведенный в книге. Теперь я хочу распараллелить его с помощью MPI. Может кто-нибудь, пожалуйста, подскажет мне, как это сделать. Моя серийная версия приведена ниже:

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


Какое-нибудь тело, пожалуйста, направьте меня.

Что я уже пробовал:

Привет,
Я ищу в интернете.

Зульфи.

Gerry Schmitz

Вы уже поняли, что может идти параллельно?

2 Ответов

Рейтинг:
1

Stefan_Lang

Основной проблемой при распараллеливании алгоритма является идентификация фрагментов кода, которые на 100% независимы от остального кода, в том смысле, что порядок обработки каждого из фрагментов не имеет значения. Для гауссовского исключения в его первоначальной форме это не так просто: каждый шаг строится на другом.

Да, вы можете запускать тело самых внутренних циклов параллельно, но они состоят только из одного оператора, а создание потока занимает гораздо больше ресурсов и времени обработки - так в чем же смысл?

В связи с этим возникает вопрос: какой цели вы хотите достичь, РАСПАРАЛЛЕЛИВ GE?


P.S.: я сомневался, что его можно распараллелить значимым образом, но я знал, что оптимизированные библиотеки могут делать такие вещи очень эффективно, поэтому я сделал поиск и нашел эту статью:
Параллельное исключение Гаусса с использованием MPI (pdf)[^]


zak100

Цель состоит в том, чтобы ознакомиться с методами распараллеливания. Как только мы узнаем эту технику, мы сможем эффективно использовать кластеры. Это не ответ. Это вопрос. Я уже дал ответ. Я просил его улучшить. В любом случае спасибо за ваш ответ. Да благословит вас Бог.

Stefan_Lang

Вы правы, это был не ответ. Мне стало любопытно, и я немного огляделся - пожалуйста, проверьте мое решение еще раз на наличие ссылки, которую я нашел.

zak100

На самом деле ссылка, которую вы показали, касается использования GE пивотов. У меня другой алгоритм. Он известен как исключение Гаусса (GE) без поворотов. Я тоже нашел эту связь.Спасибо, что уделили мне время.

Рейтинг:
1

zak100

Привет,
Да, внутренняя петля может быть, внешняя не может быть, если мы не используем конвейерную технику.

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

     }


Зульфи.


Gerry Schmitz

Внутренняя петля зависит от "К" из внешней петли; и остальная часть внешней петли зависит от результатов внутренней петли. Вам нужно несколько внешних петель, если вы хотите запустить несколько "внутренних" параллельно.

И вы "ответили" на свой собственный вопрос.

zak100

Привет,
Одним из наивных подходов может быть:
если(ранг == 0){
k=0;
for(int j= k+1; j <=n-1; ++j){
:

:
:


}
}
иначе если(ранг == 1) {
k=1;
:
:
}
иначе если (ранг== 20){//
к=20;
:
:
}
Может ли любое тело, пожалуйста, улучшить это?

Зульфи.