Теория и практика параллельных вычислений
Анализ эффективности
Оценим трудоемкость рассмотренного параллельного варианта метода Гаусса. Пусть, как и ранее, n есть порядок решаемой системы линейных уравнений, а p, p<n, обозначает число используемых процессоров. Тем самым, матрица коэффициентов А имеет размер n?n, и, соответственно, n/p есть размер полосы матрицы А на каждом процессоре.
Прежде всего, несложно показать, что общее время выполнения последовательного варианта метода Гаусса составляет:
|
(8.3) |
Определим теперь сложность параллельного варианта метода Гаусса. При выполнении прямого хода алгоритма на каждой итерации для выбора ведущей строки каждый процессор должен осуществить выбор максимального значения в столбце с исключаемой неизвестной в пределах своей полосы. Начальный размер полос на процессорах равен n/p, но по мере исключения неизвестных количество строк в полосах для обработки постепенно сокращается. Текущий размер полос приближенно можно оценить как (n-i)/p, где i, 0i<n-1, есть номер выполняемой итерации прямого хода метода Гаусса. Далее после сбора полученных максимальных значений, определения и рассылки ведущей строки каждый процессор должен выполнить вычитание ведущей строки из каждой строки оставшейся части строк своей полосы матрицы A. Количество элементов строки, подлежащих обработке, также сокращается при исключении неизвестных, и текущее число элементов строки для вычислений оценивается величиной (n-i). Тем самым, сложность процедуры вычитания строк оценивается как 2·(n-i) операций (перед вычитанием ведущая строка умножается на масштабирующую величину aik/aii). С учетом выполняемого количества итераций общее число операций параллельного варианта прямого хода метода Гаусса определяется выражением:
На каждой итерации обратного хода алгоритма Гаусса после рассылки вычисленного значения очередной неизвестной каждый процессор должен обновить значения правых частей для всех строк, расположенных на этом процессоре. Отсюда следует, что трудоемкость параллельного варианта обратного хода алгоритма Гаусса оценивается как величина:
Выберем для дальнейшего анализа эффективности получаемых параллельных вычислений параллельный алгоритм матрично-векторного умножения при ленточном горизонтальном разделении матрицы и при полном дублировании всех обрабатываемых векторов.
Трудоемкость последовательного метода сопряженных градиентов была уже определена ранее в (8.12).
Определим время выполнения параллельной реализации метода сопряженных градиентов. Вычислительная сложность параллельных операций умножения матрицы на вектор при использовании схемы ленточного горизонтального разделения матрицы составляет:
(см. лекцию 6).
Как результат, при условии дублирования всех вычислений над векторами общая вычислительная сложность параллельного варианта метода сопряженных градиентов равна:
С учетом полученных оценок показатели ускорения и эффективности параллельного алгоритма могут быть выражены при помощи соотношений:
Рассмотрев построенные показатели, можно отметить, что балансировка вычислительной нагрузки между процессорами в целом является достаточно равномерной.
Уточним теперь приведенные выражения – учтем длительность выполняемых вычислительных операций и оценим трудоемкость операции передачи данных между процессорами. Как можно заметить, информационное взаимодействие процессоров возникает только при выполнении операций умножения матрицы на вектор. С учетом результатов лекции 6 коммуникационная сложность рассматриваемых параллельных вычислений равна:
где – латентность, ? – пропускная способность сети передачи данных, а w есть размер элемента упорядочиваемых данных в байтах.
Окончательно, время выполнения параллельного варианта метода сопряженных градиентов для решения систем линейных уравнений принимает вид:
|
(8.13) |
где ? есть время выполнения базовой вычислительной операции.
