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

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

  • Автор
    Сообщения
  • #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;
      }
    }

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

    размерность последовательная параллелльная
    500 0.487271 0.296135
    1000 3.92968 2.22638
    1500 13.5138 7.43943
    2000 35.0197 18.1513
    2500 60.6002 43.9973

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

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