OpenMP — метод Гаусса решения СЛАУ

      Комментарии к записи OpenMP — метод Гаусса решения СЛАУ отключены

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 1 месяц назад.

  • Автор
    Сообщения
  • #3968

    Недавно мы рассматривали реализацию метода Гаусса решения СЛАУ на языке С++. А сегодня займемся его распараллеливанием с помощью библиотеки OpenMP.

    Метод состоит из прямого и обратного ходов. Прямой ход заключается в сведении расширенной матрицы системы уравнений к треугольному виду путем применения эквивалентных преобразований. Если мы посмотрим на исходный код этой функции, то заметим, что вычислительная сложность алгоритмаO(n^3). На самом деле, для каждой (i-той) из n строк мы перебираем все строки (j-тые), расположенные ниже и выполняем сложение строк с домножением элемента на константу. Сложение выполняется на O(n), т.к. строка состоит из n+1 элемента.

    Обратный ход заключается в вычислении суммы a[i][j]*x[j] для каждой из n строк, начиная с последней. При этом обрабатываются j только большие чем i (элементы выше главной диагонали). Асимптотическая сложность такого алгоритма — O(n*n).

    Таким образом, распараллеливать целесообразно только прямой ход. Даже если мы параллельно выполним вычисления обратного хода с нулевыми издержками (на создание потоков и синхронизацию), например, на 4 ядрах — то теоретическое ускорение составит 0.4%. Если прямой ход будет выполняться на тех же четырех ядрах год, то обратный — меньше минуты Ускорение от распараллеливания обратного хода составит в районе трех минут, а прямого — трех лет.

    Для эффективного распараллеливания прямого хода, достаточно использовать в нем параллельную функцию триангуляции (по ссылке рассмотрено несколько вариантов реализации, можно брать любой).

    Для проверки правильности работы программы использовались такие же модульные тесты, как и для последовательной версии. Для оценки эффективности распараллеливания создавались случайные СЛАУ разных размеров:

    #include "matrix.h"
    #include <iostream>
    #include <vector>
    #include "omp.h"
    
    int main() {
      for (int n = 500; n < 2500; n += 500) {
        std::vector<std::vector<double> > matrix(n);
        for (int i = 0; i < n; ++i) {
          matrix[i].resize(n);
          for (int j = 0; j < n; ++j)
            matrix[i][j] = rand();
        }
        std::vector<double> column(n);
        for (int j = 0; j < n; ++j)
          column[j] = rand();
        double start_time = omp_get_wtime();
        std::vector<double> solution = gauss_solving(matrix, column, n);
        std::cout << n << " " << omp_get_wtime() - start_time << std::endl;
      }
    }

    Результаты запусков приведены в таблице:

    размерностьпоследовательнаяпараллелльная
    5000.4872710.296135
    10003.929682.22638
    150013.51387.43943
    200035.019718.1513
    250060.600243.9973

    Вычисления производились на двухъядерном компьютере: Intel® Pentium(R) CPU G2130 @ 3.20GHz × 2 с 5.8 Гб оперативной памяти и операционной системой openSUSE Leap 42.1 (x86_64) 64-бит.

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