OpenMP — метод Якоби решения СЛАУ

  • В этой теме 0 ответов, 1 участник, последнее обновление 3 месяца, 2 недели назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6553
      @admin
      StudLance.ru

      Последовательный алгоритм подробно описан в статье: Метод Якоби решения СЛАУ.

      Вводятся матрица А и вектора b, x. Далее в качестве начального приближения берется столбец правых членов — вектор b. По потокам распределяем элементы матрицы А и вектора b, и выполняем первую итерацию. Проверяем выполнение условие останова, если не выполняется, переходим к следующей итерации, если выполняется, заканчиваем вычисления.

      На рисунке представлен пример распределения системы по трем потокам:

      Параллельная схема алгоритма:

      Реализация параллельной версии на С++:

      #include <math.h>
      #include <omp.h>
      #include <iostream>
      
      using namespace std;
      
      float form_jacobi_parallel(float **alf, float *x, float *x1, float *bet, int n,
                                 int core) {
        int i, j;
        float s, max;
      #pragma omp parallel for private(i, j, s)
        for (i = 0; i < n; i++) {
          s = 0;
          for (j = 0; j < n; j++) {
            s += alf[i][j] * x[j];
          }
          s += bet[i];
          if (i == 0) {
            max = fabs(x[i] - s);
          } else if (fabs(x[i] - s) > max) {
            max = fabs(x[i] - s);
          }
          x1[i] = s;
        }
        return max;
      }
      
      int jacobi_parallel(float **a, float *b, float *x, int n, float eps, int core) {
        float **f, *h, **alf, *bet, *x1, *xx, max;
        int i, j, kvo;
        f = new float *[n];
        for (i = 0; i < n; i++)
          f[i] = new float[n];
        h = new float[n];
        alf = new float *[n];
        for (i = 0; i < n; i++)
          alf[i] = new float[n];
        bet = new float[n];
        x1 = new float[n];
        xx = new float[n];
      #pragma omp parallel for
        for (i = 0; i < n; i++) {
      #pragma omp parallel for
          for (j = 0; j < n; j++)
            if (i == j)
              alf[i][j] = 0;
            else
              alf[i][j] = -a[i][j] / a[i][i];
          bet[i] = b[i] / a[i][i];
        }
        for (i = 0; i < n; i++)
          x1[i] = bet[i];
        kvo = 0;
        max = 5 * eps;
        while (max > eps) {
          for (i = 0; i < n; i++)
            x[i] = x1[i];
          max = form_jacobi_parallel(alf, x, x1, bet, n, core);
          kvo++;
        }
        delete[] f;
        delete[] h;
        delete[] alf;
        delete[] bet;
        delete[] x1;
        delete[] xx;
        return kvo;
      }
      
      int main() {
        omp_set_dynamic(0);
        int cores[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        int sizes[] = {500, 1000, 5000, 10000, 15000, 20000};
        int result, i, j;
        float **a;
        float *b;
        float *x;
        float ep;
        ep = 1e-6;
      
        for (auto size : sizes) {
          cout << "время для N = " << size << ":" << endl;
          for (auto core : cores) {
            omp_set_num_threads(core);
            a = new float *[size];
            for (i = 0; i < size; i++)
              a[i] = new float[size];
            b = new float[size];
            x = new float[size];
            for (i = 0; i < size; a[i][i] = 1, i++)
              for (j = 0; j < size; j++)
                if (i != j)
                  a[i][j] = 0.1 / (i + j);
            for (i = 0; i < size; i++)
              b[i] = sin(i);
      
            auto t1 = omp_get_wtime();
            jacobi_parallel(a, b, x, size, ep, core);
            auto t2 = omp_get_wtime();
            cout << t2 - t1 << ' ';
            cout.flush();
            delete[] a;
            delete[] b;
            delete[] x;
          }
          cout << endl;
        }
        return 0;
      }

      Результат работы программы:

      В таблице показана зависимость времени вычислений от объема исходных данных и количества задействованных вычислительных ядрах:

      График зависимости времени расчетов от количества задействованных вычислительных ресурсов и объема задачи:

      График зависимости ускорения от количества задействованных вычислительных ресурсов и объема задачи:

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×