Распараллеливание алгоритма Гаусса-Жордана с OpenMP

      Комментарии к записи Распараллеливание алгоритма Гаусса-Жордана с OpenMP отключены

Главная Форумы Программирование Параллельное программирование Использование OpenMP Распараллеливание алгоритма Гаусса-Жордана с OpenMP

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

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

    Основная работа в реализации алгоритма Гаусса-Жордана выполняется в функции solve, которая выполняет перестановку строк, а также элементарные преобразования над строками матрицы – домножение строки на число и ее добавление к другой строке.

    Перестановка строк выполняется функцией swap и реализуется очень эффективно – выполняется за константное время (асимптотическая сложность O(1)), т.к. для класса vector реализована семантика перемещения.

    Во время выполнения прямого и обратного хода для каждой строки матрицы, расположенной ниже опорной вызывается функция composition, которая выполняет умножение строки на константу и сложение строк. Имеет смысл либо распараллелить эту функцию, либо – циклы, в которых происходит обращение к ней. В обоих случаях распраллеливание будет сводиться к добавлению параллельного цикла, выполним это для всех обращений к функции:

    #pragma omp parallel for schedule(dynamic)
        for (int i= k+1; i<a.size(); i++){
          composition(a[i], a[k], -a[i][k]); 
        }
      }

    и
    for (int k = a.size()-1; k>=0; k--){
    #pragma omp parallel for schedule(dynamic)
        for (int i = k-1; i>=0; i--){
          composition(a[i], a[k], -a[i][k]);
        }
      }

    Запустив программу для матрицы размера 1500х1501 со случайными числами, получим следующие графики загрузки процессора (4 ядра) для последовательной и параллельных реализаций:
    gauss-zhordan-cpp-benchmark
    gauss-zhordan-cpp-openmp-benchmark

    Последовательная программа выполнялась 37 секунд, параллельная – 10 секунд. Изменение опции schedule параллельного цикла не оказало влияния на результат (были попробованы режимы static, dinamic и guided), скорее всего потому, что все итерации цикла имеют примерно одинаковую трудоемкость.

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