Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
 
-4 / 6 / 0
Регистрация: 05.04.2010
Сообщений: 350
1

Распараллеливание на C++ и MPI

05.02.2011, 13:33. Просмотров 4196. Ответов 0
Метки нет (Все метки)

Задача состоит в том, чтобы написать параллельный алгоритм метода сопряженных градиентов для решения линейной системы.

Непосредственно метод сопряженных градиентов сожержит на некоторых этапах: скалярное умножение векторов и умножение матрицы на вектор. Причем, умножение матрицы на вектор-диагональное, а матрица симметричная, положительно определена, разреженная. Хранится она в виде вектора, куда записывается верхний треугольник матрицы. таким образом, трехдиагональная, к примеру, матрица из 1, имеющая размерность 5*5 будет записана так : 111111111.
Последовательный алгоритм уже мной написан. Так же в отдельной программе распараллелено скалярное произведение.

Загвоздка в распараллеливании матрично-векторного произведение и в том, чтобы все это сшить в одну программу(включая скалярное произведение).
Поможите чем можите icon_upset.gif

писал на VS 2005, C++ (и mpich2)
Тут имеются безуспешные(работает только при запуске одного процесса) попытки вставить распараллеленое скалярное произведение, если так можно выразиться
Код C++

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
 #include <mpi.h>
#include <iostream>
#include <stdio.h>
#include <math.h>
const  int N=5;//размерность матрицы
const int di=3;//количество диагоналей а матрице
const double eps=0.0001;
int proc_rank;
int proc_num;
using namespace::std;
//функция, реализующая последовательный алгоритм диагонального матрично-векторного произведения
double *Mov(double *A, double *b)
{
  double *x,*y;
  x=new double [N];
  y=new double [N];
  for(int i=0;i<N;i++)
  {
    x[i]=0;
    y[i]=0;
  }
  int k=0,t=0,l=0,f=0;
 
  for(int v=0;v<(di/2+1);v++)
  {
    k=N-v;
    for(int j=t;j<k+t;j++)
    {
      if(v==0)
        x[j]+=A[j]*b[j];
      else
      {
        x[l]+=A[j]*b[v+f];
        y[v+f]+=A[j]*b[l];
        l++;
        f++;
      }
    }
    f=0;
    l=0;
    t+=k;
  }
 
  for(int u=0;u<N;u++)
    x[u]+=y[u];
  delete []y;
 
  return x;
}
//скалярное произведение
double Dot_pr(double *a,double *b)
{
  double little_mult=0, mult=0,k,n1,n2;
  if(proc_rank==0)
     mult=little_mult;    
 
  k=N/proc_num;
  n1=k*proc_rank;
  n2=k*(proc_rank+1);
 
  if(proc_rank==proc_num-1)
    n2=N;
  for(int i=n1;i<n2;i++)
    little_mult=a[i]*b[i]+little_mult;
  MPI_Reduce(&little_mult,&mult,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD);
  if(proc_rank==0)
    return mult;
 
}
 
//сам метод сопряженных градиентов
double *Msg(double *A,double *b,double eps)
{
  double *x,*q,*err,*r,*p,w=0,w_infinity, wk=0,alfa=0,betta=0,gamma=0;
  x=new double [N];
  q=new double [N];
  r=new double [N];//невязка
  p=new double [N];
  err=new double[N];
 
  int step=0;
  for(int i=0;i<N;i++)
  {
    x[i]=0;
    q[i]=0;
    r[i]=b[i];
    p[i]=r[i];
  }
 
  w=Dot_pr(r,r);
  w_infinity=eps*w;
  while(w>=w_infinity)
  {
    q=Mov(A,p);
    gamma=Dot_pr(q,p);
    alfa=w/gamma;
    for(int h=0;h<N;h++)
    {
      x[h]=x[h]+alfa*p[h];
      r[h]=r[h]-alfa*q[h];
 
    }
 
    wk=Dot_pr(r,r);
    betta=wk/w;
    for(int g=0;g<N;g++)
      p[g]=r[g]+betta*p[g];
 
    w=wk;
    wk=0;
    gamma=0;
    step++;
  }
 
  cout<<"steps: "<<step<<endl;
 
  delete [] p;
  delete [] q;
  delete [] err;
  delete [] r;
 
  return x;
}
 
 
 
int main(int argc, char *argv[])
{
  int M=0; double *A,*b;
 
  MPI_Init(&argc, &argv);
  MPI_Comm_size(MPI_COMM_WORLD,&proc_num);
  MPI_Comm_rank(MPI_COMM_WORLD,&proc_rank);
  for(int i=0;i<(di/2+1);i++)
      M+=N-i;
  A=new double [M];
  b=new double [N];
  if (proc_rank==0)
  {
    cout<<"M="<<M<<endl;
    cout<<"b"<<endl;
    for(int k=0;k<N;k++)
      cin>>b[k];
    cout<<"A"<<endl;
    for(int j=0;j<M;j++)
      cin>>A[j];
   }
 
  MPI_Bcast(A,M,MPI_DOUBLE,0,MPI_COMM_WORLD);
  MPI_Bcast(b,N,MPI_DOUBLE,0,MPI_COMM_WORLD);  
  double *z;
  z=new double [N];
  z=Msg(A,b,eps);
  if(proc_rank==0)
    for(int i=0;i<N;i++)
      cout<<z[i]<<endl;
  delete []z;
  delete [] A;
  delete [] b;
  MPI_Barrier(MPI_COMM_WORLD);
  MPI_Finalize();
  return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.02.2011, 13:33
Ответы с готовыми решениями:

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

Распараллеливание с MPI
Всем привет, помогите, пожалуйста распараллелить программу с помощью технологии MPI написанную на...

Парсинг лог файла и распараллеливание используя mpi
собственно, есть лог-файлы вида Нужно сортировать по дате, выводить собственно саму дату,...

Распараллеливание
Пишу в C++/CLI программу. Потребовалось распараллелить построение фрактала. Вопрос: кто-нибудь...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.02.2011, 13:33

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Распараллеливание
Здраствуйте. Подскажите как распаралелить функцию поиска минимального элемента в масиве средствами...

Распараллеливание
Написал программу для полного перебора всех возможных n-значных комбинаций состоящих из . Написал 3...

Распараллеливание
Подскажите, что не так. Есть массив из 13 элементов, мне нужно разбить на три блока, один блок...

Распараллеливание
Всем добрый вечер. Если кто знает подскажите,мне надо распараллелить перемножение...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.