Постановка задачи

Необходимо реализовать параллельную программу, которая решает системы линейных алгебраических уравнений (СЛАУ) методом Гаусса с помощью библиотеки MPI. Также нужно провести теоретический анализ эффективности алгоритма, провести эксперименты и сделать выводы.

Описание алгоритма

Алгоритм

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

Приведение матрицы к треугольному виду называется прямым ходом метода Гаусса. Обратный ход начинается с решения последнего уравнения и заканчивается определением первого неизвестного.

Имеем Ax=b, где A=[aij] – матрица размерности n*n, det A>0, b=(a1, n+1, …, an, n+1)T. В предположении, что a11>0, первое уравнение системы:

делим на коэффициент a11, в результате получаем уравнение

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

Первое неизвестное оказалось исключенным из всех уравнений, кроме первого. Далее предполагаем, что , делим второе уравнение на и исключаем неизвестное x2 из всех уравнений, начиная со второго, и т.д. В результате последовательного исключения неизвестных система уравнений преобразуется в систему уравнений с треугольной матрицей:

Из n-го уравнения системы определяем Xn, из (n-1)-го – Xn-1 и т.д. до X1. Совокупность таких действий называется обратным ходом метода Гаусса. Реализация прямого хода требует арифметических операций, а обратного – арифметических операций.

Параллельная схема

Алгоритм

Все вычисления методом Гаусса сводятся к однотипным вычислительным операциям над строками матрицы коэффициентов системы линейных уравнений. Поэтому, в качестве базовой подзадачи можно принять все вычисления, связанные с обработкой одной строки матрицы A и соответствующего элемента вектора b. Рассмотрим общую схему параллельных вычислений и возникающие при этом информационные зависимости между базовыми подзадачами. Для выполнения прямого хода метода Гаусса необходимо осуществить (n-1) итерацию по исключению неизвестных для преобразования матрицы коэффициентов A к верхнему треугольному виду. Выполнение итерации i, 0<=i<n-1, прямого хода метода Гаусса включает ряд последовательных действий. Прежде всего, в самом начале итерации необходимо выбрать ведущую строку, которая при использовании метода главных элементов определяется поиском строки с наибольшим по абсолютной величине значением среди элементов столбца i, соответствующего исключаемой переменной xi. Поскольку строки матрицы A распределены по подзадачам, для поиска максимального значения подзадачи с номерами k, k<i, должны обменяться своими элементами при исключаемой переменной xi. После сбора всех необходимых данных в каждой подзадаче может быть определено, какая из подзадач содержит ведущую строку и какое значение является ведущим элементом. Далее для продолжения вычислений ведущая подзадача должна разослать свою строку матрицы A и соответствующий элемент вектора b всем остальным подзадачам с номерами k, k<i. Получив ведущую строку, подзадачи выполняют вычитание строк, обеспечивая тем самым исключение соответствующей неизвестной xi. При выполнении обратного хода метода Гаусса подзадачи выполняют необходимые вычисления для нахождения значения неизвестных. Как только какая-либо подзадача i, 0<=i<n-1, определяет значение своей переменной xi, это значение должно быть разослано всем подзадачам с номерами k, k<i. Далее подзадачи подставляют полученное значение новой неизвестной и выполняют корректировку значений для элементов вектора b.

Масштабирование и распределение подзадач по процессорам

Выделенные базовые подзадачи характеризуются одинаковой вычислительной трудоемкостью и сбалансированным объемом передаваемых данных. В случае когда размер матрицы, описывающей систему линейных уравнений, оказывается большим, чем число доступных процессоров (т.е. p<n), базовые подзадачи можно укрупнить, объединив в рамках одной подзадачи несколько строк матрицы. Однако применение последовательной схемы разделения данных для параллельного решения систем линейных уравнений приведет к неравномерной вычислительной нагрузке процессоров: по мере исключения (на прямом ходе) или определения (на обратном ходе) неизвестных в методе Гаусса для все большей части процессоров все необходимые вычисления будут завершены и процессоры окажутся простаивающими. Возможное решение проблемы балансировки вычислений может состоять в использовании ленточной циклической схемы для распределения данных между укрупненными подзадачами. В этом случае матрица A делится на наборы (полосы) строк вида:

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

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

Распределение подзадач между процессорами должно учитывать характер выполняемых в методе Гаусса коммуникационных операций. Основным видом информационного взаимодействия подзадач является операция передачи данных от одного процессора всем процессорам вычислительной системы. Как результат, для эффективной реализации требуемых информационных взаимодействий между базовыми подзадачами топология сети передачи данных должны иметь структуру гиперкуба или полного графа.

Анализ эффективности

Оценим трудоемкость рассмотренного параллельного варианта метода Гаусса. Пусть, как и ранее, n есть порядок решаемой системы линейных уравнений, а p, p<n, обозначает число используемых процессоров. Тем самым, матрица коэффициентов А имеет размер n x n, и, соответственно, n/p есть размер полосы матрицы А на каждом процессоре.

Прежде всего, несложно показать, что общее время выполнения последовательного варианта метода Гаусса составляет:

Определим теперь сложность параллельного варианта метода Гаусса. При выполнении прямого хода алгоритма на каждой итерации для выбора ведущей строки каждый процессор должен осуществить выбор максимального значения в столбце с исключаемой неизвестной в пределах своей полосы. Начальный размер полос на процессорах равен n/p, но по мере исключения неизвестных количество строк в полосах для обработки постепенно сокращается. Текущий размер полос приближенно можно оценить как (n-i)/p, где i, 0<=i<n-1, есть номер выполняемой итерации прямого хода метода Гаусса. Далее после сбора полученных максимальных значений, определения и рассылки ведущей строки каждый процессор должен выполнить вычитание ведущей строки из каждой строки оставшейся части строк своей полосы матрицы A. Количество элементов строки, подлежащих обработке, также сокращается при исключении неизвестных, и текущее число элементов строки для вычислений оценивается величиной (n-i). Тем самым, сложность процедуры вычитания строк оценивается как 2x(n-i) операций (перед вычитанием ведущая строка умножается на масштабирующую величину aik/aii ). С учетом выполняемого количества итераций общее число операций параллельного варианта прямого хода метода Гаусса определяется выражением:

На каждой итерации обратного хода алгоритма Гаусса после рассылки вычисленного значения очередной неизвестной каждый процессор должен обновить значения правых частей для всех строк, расположенных на этом процессоре. Отсюда следует, что трудоемкость параллельного варианта обратного хода алгоритма Гаусса оценивается как величина:

Просуммировав полученные выражения, можно получить

Как результат выполненного анализа, показатели ускорения и эффективности параллельного варианта метода Гаусса могут быть определены при помощи соотношений следующего вида:

Полученные соотношения имеют достаточно сложный вид для оценивания. Вместе с тем можно показать, что сложность параллельного алгоритма имеет порядок ~(2n^3/3)/p, и, тем самым, балансировка вычислительной нагрузки между процессорами в целом является достаточно равномерной.

Дополним сформированные показатели вычислительной сложности метода Гаусса оценкой затрат на выполнение операций передачи данных между процессорами. При выполнении прямого хода на каждой итерации для определения ведущей строки процессоры обмениваются локально найденными максимальными значениями в столбце с исключаемой переменной. Выполнение данного действия одновременно с определением среди собираемых величин наибольшего значения может быть обеспечено при помощи операции обобщенной редукции (функция MPI_Allreduce библиотеки MPI ). Всего для выполнения такой операции требуется log2p шагов, что с учетом количества итераций позволяет оценить время, необходимое для проведения операций редукции, при помощи следующего выражения:

где – латентность сети передачи данных, – пропускная способность сети, w – размер пересылаемого элемента данных.

Далее также на каждой итерации прямого хода метода Гаусса выполняется рассылка выбранной ведущей строки. Сложность данной операции передачи данных:

При выполнении обратного хода алгоритма Гаусса на каждой итерации осуществляется рассылка между всеми процессорами вычисленного значения очередной неизвестной. Общее время, необходимое для выполнения подобных действий, можно оценить как:

В итоге, с учетом всех полученных выражений, трудоемкость параллельного варианта метода Гаусса составляет:

где есть время выполнения базовой вычислительной операции.

Результаты вычислительных экспериментов

Выводы

Как видно из приведённых результатов при локальных вычислениях (на одном компьютере) с числом процессов, равным числу ядер ЦП (2 ядра), выигрыш во времени происходит практически сразу и ускорение достаточно близко к идеальному (идеальное ускорение на двух ядрах = 2). При вычислениях в 4 процесса на двух ядрах получаем наоборот – замедление. Это связано с дополнительными коммуникационными расходами при передаче данных между большим числом процессов и разделением времени ЦП. Следовательно, эффективнее использовать число процессов равное числу ЦП (или ядер) на компьютере.

При вычислениях на процессах, запущенных на нескольких узлах, также получаем ускорение большее единицы, как и при двух локальных процессах, но не сразу. При малых размерах матрицы – сетевой вариант (1 процесс-1 процесс) уступает локальному (2 процесса) из-за дополнительных накладных расходов при передаче данных по сети, но сравнивается с ним при больших размерах данных. Вариант (2 - 2) становится эффективен только при ещё больших размерах матрицы, т.е. когда время на пересылки данных становится менее «решающим» по сравнению со временем, потраченным на непосредственные вычисления.

Об авторах

Ширяев Михаил и Павлов Дмитрий
группа 8409