Теория и практика параллельных вычислений
Краткий обзор лекции
Данная лекция посвящена проблеме параллельных вычислений при решении систем линейных уравнений. Изложение учебного материала проводится с использованием двух широко известных алгоритмов: метода Гаусса как примера прямого алгоритма решения задачи и итерационного метода сопряженных градиентов.
Параллельный вариант метода Гаусса (подраздел 8.2) основывается на ленточном разделении матрицы между процессорами с использованием циклической схемы распределения строк, что позволяет сбалансировать вычислительную нагрузку. Для определения параллельного варианта метода проводится полный цикл проектирования – определяются базовые подзадачи, выделяются информационные взаимодействия, обсуждаются вопросы масштабирования, выводятся оценки показателей эффективности, предлагается схема программной реализации и приводятся результаты вычислительных экспериментов. Как видно из графика, представленного на рис. 8.8, параллельный алгоритм Гаусса демонстрирует достаточно высокие показатели ускорения и эффективности.
Важный момент при рассмотрении параллельного варианта метода сопряженных градиентов (подраздел 8.3) состоит в том, что способ параллельных вычислений для этого метода может быть получен через параллельные алгоритмы выполняемых вычислительных действий – операций умножения матрицы на вектор, скалярного произведения векторов, сложения и вычитания векторов. Выбранный для учебного примера подход состоит в распараллеливании вычислительно наиболее трудоемкой операции умножения матрицы на вектор, в то время как все вычисления над векторами дублируются на каждом процессоре для уменьшения числа выполняемых операций передачи данных — показатели эффективности подобного способа организации параллельных вычислений представлены на рис. 8.8.
Рис. 8.8. Ускорение параллельных алгоритмов решения системы линейных уравнений с размером матрицы 3000x3000
