Последовательная версия

Параллельная версия

Последовательная версия 
void SolveSystem(double* Matrix,double eps,int m,int n)
{
  double dmax= 0; //Наибольшее изменение в матирце Matrix
  do 
  {
    dmax=0;
    for (int i=m+1; i < (n-1)*m - 1; i++)
    {
      if ( (i%m == 0)||(i%m == m-1) ) continue;
      double temp = Matrix[i];
      Matrix[i] = 0.25*(Matrix[i-1]+Matrix[i+1]
      +Matrix[i-m]+Matrix[i+m]);
      double dm = fabs(temp-Matrix[i]);
      if ( dmax< dm ) dmax= dm;
    }

  } while( dmax> eps);
}
Параллельная версия
//Инициализируем MPI
    MPI_Init(&argc,&argv);
    //Ранг процесса
    int ProcRank;
    //Число процессов
    int ProcNum;
    //Определим общее число процессов в рамках нашей задачи
    MPI_Comm_size(MPI_COMM_WORLD,&ProcNum);
    //Процесс узнает свой ранг в коммуникаторе MPI_COMM_WORLD
    MPI_Comm_rank(MPI_COMM_WORLD,&ProcRank);

    //Размеры сетки должны храниться на всех процессах
    // Причём число строк (n) обязательно кратно числу процессов!
    int m=0,n=0;

    MPI_Status Status;
    //Просто матрица, используется только 0 процессом как начальная
    double * Matrix=new double;
    //Матрица с значениями функции в узлах сетки - для каждого процесса своя
    double * FunctionValues;
    //Матрица в которую считаются значения функции 
    double* Fvalues = new double;
    //Узнать точность
    double eps = atof(argv[3]);

    //Прочитать и распарсить файл c граничными условиями 0 процессом
    if (ProcRank == 0)
    {
      double *left,*top,*right,*bottom;
      ParseFileDim(argv[1],&m,&n);
      delete Matrix;
      //Память под границы
      left = new double[n];
      right = new double[n];
      top = new double[m];
      bottom = new double[m];
      //И под саму матрицу
      Matrix = new double [m * n];
      ParseFile(argv[1],left,top,right,bottom);
      CreateMatrix(Matrix,left,top,right,bottom,m,n);
    }

    //Рассылка размеров матрицы
    MPI_Bcast(&m,1,MPI_INT,0,MPI_COMM_WORLD);
    MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);

    //Выделение памяти на значения функции
    FunctionValues = new double [m * n / ProcNum];

    if ( ProcRank == 0 )
    {
      delete Fvalues;
      Fvalues = new double[m * n];
      ParseForValues(argv[2],Fvalues,m,n);
    }

    MPI_Scatter(Fvalues,m * n / ProcNum,MPI_DOUBLE,FunctionValues,m * n / ProcNum,MPI_DOUBLE,0,MPI_COMM_WORLD);


    //Локальная матрица в которой и будут происходить вычисления для всех процессов
    double* LocalMatrix = new double[m * n / ProcNum + 2 * m];

    //Разослать в LocaMatrix с нужной позиции
    MPI_Scatter(Matrix, m * n / ProcNum, MPI_DOUBLE,&LocalMatrix[m],m * n / ProcNum,MPI_DOUBLE,0,MPI_COMM_WORLD);


    //dmax - максимальное изменение значения в матрице
    //Условие останова цикла основано на том что dmax < eps
    double dm,dmax;
    //Переменные для передачи сообщения
    int NextProc = (ProcRank + 1)%ProcNum;
    int PrevProc;
    if (ProcRank == 0)PrevProc = ProcNum - 1;
    else PrevProc = ProcRank - 1;

    //Вычислительный цикл
    do
    {
      dm = 0.0;
      MPI_Sendrecv(&LocalMatrix[m * n /ProcNum],m,MPI_DOUBLE,NextProc,0,LocalMatrix,m,MPI_DOUBLE,PrevProc,0,MPI_COMM_WORLD,&Status);
      MPI_Sendrecv(&LocalMatrix[m],m,MPI_DOUBLE,PrevProc,0,&LocalMatrix[m * n /ProcNum + m],m,MPI_DOUBLE,NextProc,0,MPI_COMM_WORLD,&Status);
      if ( ProcRank == 0 )
      {
        DoGausseSeidelStep_first(LocalMatrix,FunctionValues,&dm,m,n / ProcNum + 2);
      }
      if ( ProcRank == ProcNum - 1)
      {
        DoGausseSeidelStep_last(LocalMatrix,FunctionValues,&dm,m,n / ProcNum + 2);

      }
      if (( ProcRank != 0) && ( ProcRank != ProcNum - 1))
      {
        DoGausseSeidelStep(LocalMatrix,FunctionValues,&dm,m, n / ProcNum + 2);

      }
      MPI_Allreduce(&dm,&dmax,1,MPI_DOUBLE,MPI_MAX,MPI_COMM_WORLD);
    }while (dmax > eps);

n - количество узлов по каждой из координат области D.

m - число операций, выполняемых методом для одного узла сетки.

k - количество итераций метода до выполнения условия остановки.

T1 - время решения задачи в 1 процесс.

Tp - время решения задачи запущенной в p процессов.

S - ускорение (speedup). Ускорение определяется из отношения: S=T1/Tp. Числитель в этом выражении: параллельная программа запущеная в 1 процесс.

Вычислительная трудоёмкость последовательного алгоритма T1 = k*m*n*n.

Для p потоков:Tp=k*m*n*n/p.

Из элементарных соображений получаем, что: S -> p

Для оценки идеального времени работы параллельной версии воспрользуемся следующей аппроксимацией:

OS: Windows 7 x64

Разработка велась в MSVS2008 с встроенным компилятором, в режиме релиза была включена полная оптимизация(ключ /Ox)

Работу выполнил студент 3 курса Малышев Александр.