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