Постановка задачи
Множество n линейных уравнений назвается системой линейных
уравнений или линейной системой
В матричной форме:
Под задачей решения системы линейных уравнений для
заданных матрицы А и вектора b понимается нахождение значения
вектора неизвестных x, при котором выполняются все уравнения системы.
Метод решения
Метод сопряженных градиентов–один из наиболее
известных итерационных методов решения систем линейных уравнений. Он может быть
применен для решения системы линейных уравнений с симметричной,
положительноопределенной матрицей
-Матрица А называется симетричной если она совпадает со своей
транспонированной матрицей 
-Матрица А называется положительноопределенной если 
После выполнения n итераций метода сопряженных градиентов(n
есть порядок решаемой системы линейных уравнений), очередное приближение Xn
совпадает с точным решением.
Если матрица А симметричная и положительноопределена, то
функция:
имеет единственный минимум
который достигается в точке X*, совпадающий с решением системы линейных
уравнений.
Итерация метода сопряженных градиентов состоит в вычислении
очередного приближения к точному решению
где
- очередное
приближение
- приближение,
построенное на предыдущем шаге
- скалярный шаг
- вектор
направления
Перед выполнением первой итерации Xо и do
полагаются равными нулю, а для вектора g0 устанавливается значение -b
Алогритм:
1. Вычисление градиента
2. Вычисление вектора
направления
3. Вычисление величины смещения по
заданному направлению
4. Вычисление нового
приближения
Вычислительная сложность
алгоритма 
Параллельная схема
Выполнение итераций метода осуществляется последовательно,
следовательно наиболее целесообразный подход состоит в распараллеливании
вычислений, реализуемых в ходе выполнения отдельных итераций. Основные
вычисления, выполняемые в соответствии с методом, состоят в перемножении матрицы
А на вектора x и d. Дополнительные вычисления, имеющие меньший порядок сложности
представляют собой различные операции обработки векторов( скалярное
произведение, сложение и вычитание, умножение на скаляр).
В последовательном алгоритме всего 2 умножения матрицы на
вектор на шагах 1 и 3, именно здесь и задействуется параллельная схема.
Рассмотрим параллельный вариант умножения матрицы на вектор. Распределение
данных- разбиение матрицы на строки
Базовая подзадача для выполнения вычисления должна содержать
строку матрицы А и копию вектора b. После завершения вычислений каждая базовая
подзадача будет содержать один из элементов ветора результата с. Для объединения
результатов расчетов и получения полного вектора с на каждом из процессоров
выислительной системы необходимо выполнить операцию обобщенного сбора
данных.
Если число процессоров p меньше числа базовых подзадач m,
базовые подзадачи могут быть укрупнены с тем, чтобы каждый процессор выполнял
несколько операций умножения строк матрицы А и вектора b. В этом случае, по
окончании вычислений каждая базовая подзадача будет содержать набор элементов
результирующего вектора с.
Распределение подзадач между процессорами вычислительной системы
может быть выполнено с учетом возможности эффективного выполнения операции сбора
данных.
Анализ эффективности
Вычислительная сложность параллельных операций умножения матрицы
на вектор при использовании схемы ленточного горизонтального разделения
матрицы
Как результат, при условии дублирования всех вычислений над
векторами общая вычислительная сложность параллельного варианта метода
сопряженных градиентов является равной
Общая оценка показателей ускорения и эффективности
С учетом длительности выполняемых вычислительных операций и информационного взаимодействия
процессов, время выполнения параллельного варианта метода сопряженных градиентов для решения систем линейных уравнений принимает вид:
Результаты вычислительных экспериментов
Параметры оборудования:
ПК:
процессор: Intel Core 2 Duo CPU E8500, 3.16 GHz(2 CPUs)
память: 2048MB RAM
OS: Win XP SP3
Компилятор: С++ встроенный в Visual Studio 2005
Длительность τ базовой скалярной операции - 0.0000000015 сек
Параметры передачи между процессами на одной машине:
латентность α - 0.000024 сек, пропускная способность β - 267506473
байт/сек
Размер элемента упорядочиваемых данных в байтах w= 4 и соответствует типу int
|
размерность
матрицы |
последовательный
алгоритм |
2
процесса |
ускорение 2
процесса |
4
процесса |
ускорение 4
процесса |
|
100 |
0.00398184 |
0.00579593 |
0.69 |
0.0141547 |
0.28 |
|
200 |
0.0255704 |
0.0210043 |
1.22 |
0.0376483 |
0.68 |
|
300 |
0.08509408 |
0.0553403 |
1.54 |
0.131018 |
0.65 |
|
400 |
0.198999 |
0.116307 |
1.71 |
0.184714 |
1.07 |
|
500 |
0.379677 |
0.213407 |
1.78 |
0.299482 |
1.28 |
|
600 |
0.658378 |
0.35659 |
1.85 |
0.417103 |
1.58 |
|
700 |
1.02645 |
0.590921 |
1.73 |
0.678388 |
1.51 |
|
800 |
1.54995 |
0.841979 |
1.84 |
0.970116 |
1.59 |
|
900 |
2.38614 |
1.39978 |
1.70 |
1.60877 |
1.48 |
|
1000 |
3.42194 |
2.31082 |
1.48 |
2.44232 |
1.4 |
|
1500 |
11.6192 |
8.9307 |
1.3 |
9.577 |
1.21 |
|
2000 |
27.5323 |
20.92 |
1.31 |
22.15 |
1.24 |
|
3000 |
94 |
73.6611 |
1.28 |
74.6728 |
1.26 |
Таблица сравнения времени экспериментов с модельным временем:
|
размерность
матрицы |
2
процесса |
4
процесса |
|
T |
T* |
T |
T* |
|
100 |
0,00323336253966435 |
0,00579593 |
0,00177248594889392 |
0,0141547 |
|
200 |
0,0249136816010678 |
0,0210043 |
0,0130504066803965 |
0,0376483 |
|
300 |
0,0830409571842104 |
0,0553403 |
0,0428337621945078 |
0,131018 |
|
400 |
0,195615189289092 |
0,116307 |
0,100122552491228 |
0,184714 |
|
500 |
0,380636377915713 |
0,213407 |
0,193916777570557 |
0,299482 |
|
600 |
0,656104523064073 |
0,35659 |
0,333216437432494 |
0,417103 |
|
700 |
1,04001962473417 |
0,590921 |
0,52702153207704 |
0,678388 |
|
800 |
1,55038168292601 |
0,841979 |
0,784332061504195 |
0,970116 |
|
900 |
2,20519069763959 |
1,39978 |
1,11414802571396 |
1,60877 |
|
1000 |
3,0224466688749 |
2,31082 |
1,52546942470633 |
2,44232 |
|
1500 |
10,1754308728776 |
8,9307 |
5,11965794140732 |
9,577 |
|
2000 |
24,0895889899237 |
20,92 |
12,1014823276735 |
22,15 |
|
3000 |
81,2014269631464 |
73,6611 |
40,7280387089016 |
74,6728 |
На данной конфигурации оборудования
оптимальные показатели эффективности будут при запуске на 2 процессах, т.к. у процессора всего два физических ядра.
При небольших размерностях исходной матрицы время выполнения операций вычисления ниже чем
время пересылки команд MPI, запуска процессов, из чего
следует ,что последовательный алгоритм показывает лучшее время. При
высоких размерностях алгоритм сходится к одному и тому
же показателю эффективности.
Авторы
Нижегородцев А., Михайлова О. группа 8410
