- •Оглавление
- •Глава 1. Архитектура вычислительных систем 11
- •Глава 2. Реализация параллельных алгоритмов 63
- •Глава 3. Надежность и живучесть вычислительных систем 96
- •Глава 4. Библиотека параллельных программ 120
- •Глава 5. Граф-схемы параллельных алгоритмов 150
- •Глава 6. Исследование информационных граф-схем со скалярными весами для планирования параллельных вычислений 182
- •Глава 7. Исследование информационных граф-схем решаемых задач с векторными весами для планирования параллельных вычислений 204
- •1.Количественные характеристики, применяемые для оценок параметров вычислительных систем
- •Глава 1. Архитектура вычислительных систем
- •Для случая неоднородной системы номинальное быстродействие выразится как
- •Здесь – вероятность выбора j-й операции, , . Для однородной вс её быстродействие по Гибсону выразится соотношением
- •Для неоднородной вс это быстродействие может быть определено, как
- •1.1.1. Вопросы к разделу 1.1.
- •2.Понятие о современных вычислительных системах
- •Пример графа регулярной вычислительной системы представлен на рисунке 1.2.1.
- •Примечание: Для регулярной вычислительной системы
- •2.1. Вопросы к разделу 1.2.
- •3.Структура современных вычислительных систем
- •3.1.Схема обмена с помощью структуры «Общая шина»
- •3.2.Схема обмена с помощью структуры «Линейка»
- •3.3.Вычислительная система, имеющая структуру типа «Кольцо»
- •3.4.Схема обмена с помощью структуры типа «Решётка»
- •1.3.5. Схема обмена с помощью структуры типа «Двумерный тор»
- •3.1.Схема обмена с помощью структуры типа «n-мерный двоичный гиперкуб» или «nD-куб»
- •3.2.Реализация обмена с помощью структуры типа «Обобщенный nD-куб»
- •3.3.Структура вс типа «n-мерный обобщённый тор»
- •3.4.Структура вс с сетью типа «Циркулянт»
- •1.3.10. Вычислительная система «Максимальный обхват»
- •1.3.11. Вычислительные системы со структурой сетей типа «Симметричные графы»
- •На рисунке 1.3.11. Представлена вс с симметричным графом.
- •1.3.12. Вычислительные системы с сетью связей типа «Гомоморфные графы»
- •1.3.13. Вычислительные системы с сетью связей типа «Граф л(n,V,g)»
- •1.3.14. Структура вычислительной системы типа «Бинарное дерево t0(n) глубины n»
- •1.3.15. Структура вычислительной системы типа «Мультидерево глубины n и ширины k t1(n,k)»
- •3.5. Вопросы к разделу 1.3
- •4.Коммуникационные среды вычислительных систем
- •Коммуникационная среда должна удовлетворять следующим требованиям:
- •4.1.Коммуникационная среда на основе масштабируемого когерентного интерфейса sci
- •4.2.Коммуникационная среда на основе технологии Myrinet
- •1.4.3. Краткая характеристика коммуникационной среды QsNet II
- •4.3. Вопросы к разделу 1.4
- •5.Коммутаторы вычислительных систем
- •1.5.1. Типы коммутаторов
- •5.1. Управление коммутаторами
- •5.2. Алгоритмы определения маршрутов
- •5.3. Дедлоки в составных коммутаторах
- •5.4.Вопросы к разделу 1.5
- •6.Процесс функционирования вычислительных систем
- •6.1. Вопросы к разделу 1.6.
- •7.Принципы технической реализации вс
- •1.7.1. Вопросы к разделу 1.7
- •1.8. Архитектурные особенности вс
- •1.8.1. Архитектурные свойства вс
- •1.8.2. Схема обмена информацией между ветвями параллельных алгоритмов
- •7.1.Опыт применения методики крупноблочного распараллеливания сложных задач
- •7.2.Архитектурные аспекты при создании ос вс
- •7.3.Структурные характеристики вс
- •7.4.Классификация структур вс
- •7.5.Вопросы к разделу 1.8.
- •Глава 2. Реализация параллельных алгоритмов
- •2.1. Реализация параллельных алгоритмов
- •2.1.1. Определение параллельного алгоритма
- •7.6.Организация динамического распараллеливания в суперскалярных микропроцессорах
- •2.1.3. Предварительная выборка команд и предсказание переходов
- •7.7.Декодирование команд, переименование ресурсов и диспетчеризация
- •7.8.Исполнение команд
- •2.1.6. Работа с памятью
- •2.1.7. Завершение выполнение команды
- •2.1.8. Направления развития суперскалярной архитектуры
- •7.9.Мультитредовая модель выполнения программы
- •7.10.Аппаратные и программные средства, необходимые для мультитредовой архитектуры
- •2.1.11. Специфика мультитредовых моделей распараллеливания
- •2.1.12. Вопросы к разделу 2.1
- •2.2.Организация распараллеливания на уровне программных модулей
- •2.2.1. Примеры организации вычислений на уровне программных модулей
- •2.2.2. Решение системы линейных уравнений методом Гаусса с помощью вс типов «решётка» и «линейка»
- •2.2.3. Исполнение алгоритма Гаусса на «решётке» n*n вm
- •2.2.4. Исполнение алгоритма Гаусса на «линейке», состоящей из n вм
- •2.2.5. Показатели эффективности параллельных алгоритмов
- •2.2.6. Понятие о сложных задачах
- •2.2.7. Вопросы к разделу 2.2
- •Глава 3. Надежность и живучесть вычислительных систем
- •8.Основные задачи создания отказоустойчивых систем
- •8.1.Вопросы к разделу 3.1
- •9.Классификация типов отказоустойчивости сложных систем и ее критерии
- •9.1.Вопросы к разделу 3.2
- •10.Способы обеспечения отказоустойчивого функционирования вс
- •3.3.1. Диагностическое тестирование вс
- •3.3.3. Способы восстановления отказоустойчивых вс
- •10.1.Вопросы к разделу 3.3
- •3.4. Построение живучих вс на основе экспоненциально- надежностного подхода
- •3.4.1. Показатели надежности вс
- •10.2. Методика расчета показателей надежности вс
- •3.4.3. Живучесть вс
- •3.4.4. Вопросы к разделу 3.4
- •11.Построение живучих вс, работоспособных в расчетном диапазоне кратностей отказов
- •3.6.1. Горячий резерв
- •3.6.2. Репликация
- •3.6.3. Кластеры высокой готовности
- •3.5.1. Вопросы к разделу 3.5
- •3.6. Реализация модели отказоустойчивых систем
- •4.1.2. Принципиальная схема программирования в OpenMp
- •11.2. Описание основных конструкций open mp
- •4.1.4. Способы построения параллельных программ
- •4.1.6. Вопросы к разделу 4.1
- •4.2. Основы построения библиотеки mpi
- •4.2.1. Основные понятия
- •4.2.2. Структура программ в mpi
- •4.2.3. Определение структуры приходящего сообщения
- •4.2.4. Определение базовых характеристик коммуникационной сети
- •11.4.Анализ тупиковых ситуаций при обмене
- •4.2.6. Организация передачи-приёма сообщений без блокировки
- •4.2.7. Реализация отложенных запросов на взаимодействие
- •4.2.8. Сравнительная оценка различных способов обмена данными
- •4.2.9. Использование глобальных операций в mpi
- •4.2.10. Взаимодействие процессов в mpi
- •4.2.11. Вопросы к раделу 4.2
- •Глава 5. Граф-схемы параллельных алгоритмов
- •5.1. Представление параллельных алгоритмов в виде граф-схем
- •5.1.1. Преобразование последовательных алгоритмов в параллельные
- •5.1.2.Использование граф-схем для представления параллельных алгоритмов
- •5.1.3. Вопросы к разделу 5.1
- •5.2.1. Вычисление матриц следования, расширенных матриц следования и матриц следования с транзитивными связями
- •5.2.2. Вопросы к разделу 5.2
- •11.5.Построение матрицы логической несовместимости.
- •5.3.2. Построение матрицы логической несовместимости операторов
- •5.3.3. Вопросы к разделу 5.3
- •5.4.1. Построение множеств взаимно независимых операторов.
- •5.4.2. Вопросы к разделу 5.4
- •Глава 6. Исследование информационных граф-схем со скалярными весами для планирования параллельных вычислений
- •6.1. Численные характеристики информационных граф-схем со скалярными весами
- •6.1.1 Определение ранних и поздних сроков окончания выполнения операторов.
- •11.6.Определение функций плотности загрузки, и минимальной загрузки для информационных граф-схем
- •6.1.3. Вопросы к разделу 6.1
- •6.2.1. Распределение операторов по вм вычислительной системы с общим полем памяти для информационной граф-схемы
- •6.2.2. Распределение операторов по вм вычислительной системы с общим полем памяти для информационно-логической граф-схемы
- •При срабатывании условного оператора «один», дуги 1.1 требуется 10 вм. Время решения задачи составит 22 условные единицы.
- •6.2.3. Распределение операторов по вм вычислительной системы с распределённой памятью для информационной граф-схемы
- •6.2.4. Реализация диаграмм для общепринятых способов обмена данными между вм вычислительной системы с распределённой памятью для информационной граф-схемы
- •6.2.5. Вопросы к разделу 6.2
- •Глава 7. Исследование информационных граф-схем решаемых задач с векторными весами для планирования параллельных вычислений
- •7.1 Информационная граф-схема решаемых задач с векторными весами вершин
- •7.1.1 Понятие об неоднородных системах
- •7.1.2. Основные определения, используемые для неоднородных вс
- •7.1.3. Вопросы к разделу 7.1
- •Литература
2.1.12. Вопросы к разделу 2.1
1. Какое различие существует между архитектурой ЭВМ и архитектурой ВС ?
2. Перечислите направления развития ВС.
3.Чем характерны архитектуры SISD, MISD, SIMD и MIMD ?
4. Охарактеризуйте суперскалярные ВМ.
5. Какие аппаратные и программные средства необходимы для мультитредовой архитектуры ?
6. В чём специфика мультитредовых моделей распараллеливания ?
7. В чём сущность мультитредовой модели выполнения программы ?
2.2.Организация распараллеливания на уровне программных модулей
2.2.1. Примеры организации вычислений на уровне программных модулей
При решении задач обработки информации возникает необходимость умножения матриц большой размерности. При увеличении размерности прямоугольных матриц существенно возрастает время выполнения операций над ними. Одним из решений этой проблемы является использование распределённой вычислительной системы (РВС), состоящей из нескольких однотипных вычислительных модулей (вычислителей, ВМ). Для повышения эффективности использования РВС требуется создать алгоритм, позволяющий распараллелить вычисления произведений соответствующих элементов исходных матриц и добиться равномерной загрузки всех ВМ системы.
Даны две матрицы:
размерности NxK
размерности KxM, причём
размерность матриц существенно превышает
количество ВМ
:
N>>n, K>>n, M>>n (2.2.1).
Необходимо вычислить произведение
матриц
по формуле
,
где
,
(2.2.2)
используя все имеющиеся ВМ системы.
Разбиение матриц, пересылка исходных
данных. Поскольку предельная
размерность матриц, которые можно
перемножить на РВС за один цикл пересылок,
равна количеству вычислителей, необходимо
разбить исходные матрицы на части по
элементов. В связи с особенностями
формулы (2.2.2) произведём разбиение
матрицы
по горизонтали (на
горизонтальных полос по
строк в каждой), а разбиение матрицы
– по вертикали (на
вертикальных полос по
столбцов в каждой).
Перенумеруем вычислители, начиная с 1:
.
Для начала работы алгоритма необходимо
разместить в памяти каждого ВМ
соответствующую его номеру строку
первой горизонтальной полосы матрицы
и соответствующий его номеру столбец
первой вертикальной полосы матрицы
.
В дальнейшем будут осуществляться
последовательный проход по вертикальным
полосам матрицы
(со сменой начального передающего
вычислителя
)
и по горизонтальным полосам матрицы
.
Пересылка рабочей строки. Рассмотрим
отдельно взятые горизонтальную и
вертикальную полосы соответствующих
матриц. Обозначим их
и
,
соответственно (в каждой полосе содержится
элементов, зависящих от её ориентации
в матрице – строк или столбцов). Смещения
начальных элементов рассматриваемых
полос от начала матриц будут равны
и
,
соответственно.
Каждый вычислитель должен произвести
вычисление одного элемента результирующей
матрицы (ЭРМ): номер строки этого элемента
соответствует номеру передающего
вычислителя
,
а номер столбца – номеру данного ВМ
.
Для этого необходимо поместить в память
данного ВМ текущую строку горизонтальной
полосы
матрицы
.
В памяти одного ВМ эта строка уже
присутствует – назовём этот вычислитель
передающим, поскольку именно он будет
производить пересылку текущей строки
всем остальным ВМ. Содержимое памяти
передающего ВМ показано на рис.2.2.1.
Рисунок 2.2.1. Содержимое памяти передающего ВМ
В памяти вычислителя, не являющегося
передающим, будут храниться две строки
– строка, соответствующая его номеру
(
),
и строка, соответствующая номеру
передающего ВМ (
).
Последняя из двух является рабочей
строкой для вычисления ЭРМ.
Назовём часть результирующей матрицы
,
соответствующую полосам
,
матричным блоком (МБ). Каждый МБ состоит
из
ЭРМ. В пределах одного МБ за полный цикл
расчёта каждый вычислитель РВС один
раз является передающим.
Вычисление элемента результирующей
матрицы. Вычисляемый ЭРМ представляет
собой строку размерности
.
Все ячейки этой строки вычисляются
параллельно, с использованием всех
вычислителей РВС. Частичные произведения
из формулы (2.2.2) суммируются во внутренней
промежуточной переменной
,
затем соответствующим ячейкам ЭРМ
последовательно присваиваются полученные
значения.
Переход к следующей строке внутри текущего МБ. Переход к следующему МБ. После вычисления очередного ЭРМ, не являющегося последним, в текущем МБ, передающим становится следующий по порядку вычислитель, номер вычисляемого ЭРМ также увеличивается на единицу.
Если очередной ЭРМ является последним
в текущем МБ, производится переход к
следующему МБ, соответствующему полосам
результирующей матрицы
.
Если все МБ текущей горизонтальной
полосы матрицы
обработаны, производится переход к МБ,
соответствующему первой вертикальной
полосе матрицы
и следующей по порядку горизонтальной
полосе матрицы
,
т. е. к МБ, соответствующему полосам
.
Рисунок. 2. Упрощённая блок-схема алгоритма умножения матриц большой размерности с использованием РВС
Если все МБ обработаны, то алгоритм завершается: в памяти каждого ВМ хранятся те столбцы результирующей матрицы , номера которых можно определить по формуле
,
(2.2.3)
где
– номера столбцов результирующей
матрицы
,
хранящихся в
-ом
ВМ.
Упрощённая блок-схема рассмотренного алгоритма представлена на рисунке 2.2.2.
Оценка вычислительной сложности алгоритма. Для оценки вычислительной сложности алгоритма введём следующие обозначения:
– среднее время пересылки
ячеек матрицы из области памяти, в
которой записаны исходные данные, в
память текущего вычислителя или из
памяти текущего вычислителя в область
памяти, где записывается результирующая
матрица;
– среднее время перемножения двух ячеек
исходных матриц (частичные произведения
в формуле (2.2.2));
– среднее время сложения двух частичных
произведений по формуле (2.2.2).
Все времена измеряются в относительных единицах, например, в процессорных тактах.
Длительность пересылки исходных данных для одного ВМ оценивается как
,
(2.2.4)
длительность пересылки рабочей строки для одного ВМ –
,
(2.2.5)
длительность вычисления ЭРМ для одного ВМ –
,
(2.2.6)
длительность пересылки результатов для одного ВМ –
.
(2.2.7)
Итак, суммарная длительность выполнения алгоритма умножения матриц большой размерности, удовлетворяющих условию (2.2.1), с использованием РВС, в соответствии с соотношениями (2.2.4) – (2.2.7) оценивается как
,
(2.2.8)
в то время как суммарная длительность перемножения матриц малой размерности на одном ВМ равна
.
(2.2.9)
Для определённости примем, что размеры
матриц одного порядка (обозначим этот
характерный размер матриц
).
Сопоставляя выражения (2.2.8) и (2.2.9), можно
прийти к выводу, что рассмотренный
алгоритм имеет большую вычислительную
сложность организации пересылок данных
(примерно в
раз), но значительно ускоряет собственно
умножение (примерно в
раз). Из этого следует, что алгоритм даёт
больший выигрыш во времени при реализации
в РВС с общей памятью.
Предложенный простой алгоритм умножения
матриц большой размерности с использованием
РВС позволяет распараллелить вычисления
и добиться равномерно высокой загрузки
всех ВМ системы. Данный алгоритм
эффективен для РВС из
вычислителей, если время пересылки
данных не превосходит времени вычисления
значения одной ячейки результирующей
матрицы
,
умноженного на утроенное количество
ВМ в системе:
.
При решении различных задач физики и математики возникает необходимость решения систем линейных алгебраических уравнений (СЛАУ). При этом число уравнений в системах может быть велико и однопроцессорный компьютер либо не может их решить из-за нехватки памяти, либо их решение занимает очень много времени, поэтому возникает необходимость разработки параллельных алгоритмов решения СЛАУ.
Традиционно методы решения делятся на точные (дающие точный ответ без учета ошибок округления) и итерационные (точное решение есть предел бесконечной последовательности приближений).
Пусть A - заданная матрица невырожденная симметричная положительно определенная (n*n), b – известный (n*1)-вектор, а y – неизвестный (n*1)-вектор. Рассмотрим систему линейных алгебраических уравнений (СЛАУ)
Ay=b (2.2.10)
Итерационные методы решения системы
(2.2.10) позволяют строить последовательность
приближений (итераций)
Если эта последовательность имеет
предел, то он называется решением системы
(2.2.10).
Очередное приближение строится с помощью рекуррентной формулы
(2.2.11)
где k - номер итерации. Преимущественно используется простейшая рекуррентная формула
(2.2.12)
где B - квадратная nxn
матрица, а h - n-мерный
вектор. Для организации счета по такой
формуле требуется задание начального
приближения
.
Вид матрицы B и вектора h
определяет тот или иной итерационный
метод.
В общем случае, итерационный метод сходится, если ||B|| < 1. Отсюда следует, что сходимость имеет место, если:
все собственные числа матрицы B по модулю меньше единицы;
имеет место диагональное преобладание элементов матрицы B .
Все итерационные методы строятся по одной схеме: система (2.2.10) преобразуется к виду
(2.2.13)
где
, и
- легко обращаемая матрица: единичная,
диагональная или треугольная. В этом
случае из (3) без труда получается
выражение
h,
(2.2.14)
которое далее используется в качестве рекуррентной формулы (2.2.12).
Рассмотрим параллельный алгоритм решения СЛАУ методом простой итерации.
|
|
Приближенные решения (итерации) системы линейных уравнений последовательно находятся по формуле:
(2.2.15)
Для решения этой задачи на параллельной системе исходную матрицу коэффициентов А разрезаем на p1 горизонтальных полосы по строкам, где p1 - количество процессоров в системе. Аналогично, горизонтальными полосами разрезаются вектор b (правая часть) и вектора y0 (начальное приближение), yk (текущее приближение) и yk+1 (следующее приближение). Полосы последовательно распределяются по соответствующим процессорам системы. Каждый процессор системы вычисляет "свое" подмножество корней. Поэтому после нахождения приближенных значений корней на очередном шаге итерации на каждом процессоре проверяется выполнение следующего условия для "своих" подмножеств корней:
(2.2.16)
Условием завершения работы каждого процесса является безусловное выполнение условия (2.2.16) на всех процессорах. И если условие (2.2.16) не выполнилось хотя бы на одном процессоре, то вычисление корней продолжается и каждый процесс передает всем остальным процессам полученную итерацию своих корней. Тем самым вектор y полностью восстанавливается в каждом процессе для выполнения операции его умножения на матрицу коэффициентов на следующем шаге итерации.
Параллельный алгоритм решения СЛАУ методом сопряженных направлений.
Данный алгоритм оптимизирован для запуска на многопроцессорной системе, где каждый процессор соединен с каждым.
Решение СЛАУ (2.2.10) эквивалентно отысканию минимума квадратичной формы
(2.2.17)
Распараллеливание метода сопряженных направлений сводится к распараллеливанию вычисления указанных скалярных произведений и матрично-векторных произведений.
Положим для простоты записи, что порядок n системы (2.2.10) кратен количеству процессоров N в системе, т.е. что величина n кратна величине N , так что p=m/N.
Основные этапы алгоритма:
Вычисление частей скалярного произведения (ak+1, xk) и после пересылки частей получение на каждом процессоре всего произведения
Рисунок 2.2.2. Распределенние данных между ВМ на первом этапе алгоритма
Затем на каждом процессоре вычисляется
где k=0,…,n.
Параллельно на всех процессорах системы вычисляем соответствующие компоненты произведений Ax1, Aen+1 , а также соответствующие части скалярных произведений.
Рисунок 2.2.3. Распределение данных на третьем этапе
Каждый из процессоров системы посылает одному из процессоров вычисленные суммы. На этой основе указанный процессор формирует вектор X* и сравнивает полученное решение с предыдущим, если разность между ними мала, то вычисления заканчиваются.
Рисунок 2.2.4. Формирование вектора Х*
Использование итерационных методов совместно с предобусловливанием по Булееву [33, 34] является одним из наиболее быстродействующих по времени и количеству итераций методом в настоящее время. Он относится к семейству методов вариационно-итерационного типа и применим для решения знаконеопределенных СЛАУ с несимметричной в общем случае матрицей, для которой неизвестны спектральные свойства.
Идея предобусловливания заключается в преобразовании исходной задачи (решение системы линейных уравнений) таким образом, чтобы матрица предобусловленной системы имела лучшие спектральные свойства и полученная система решалась более легко. Под этим понимается, что алгоритм требует меньше вычислительных ресурсов за меньшее число итераций.
Для ускорения процесса сходимости и уменьшения числа итераций может использо
ваться процедура предобусловливания по методу неполной факторизации Булеева, формулы которой получаются из формул явного метода Булеева исключением итерационных членов [33, 34].
Алгоритм предобусловливания (решение
систем вида Ky = pi
или Kz = s , K
A ) состоит из двух этапов: прямого и
обратного хода. На первом шаге вычисляются
прогоночные коэффициенты, формулы для
определения которых имеют рекуррентный
вид (где Θ – параметр компенсации 0 ≤ Θ
< 1):
(2.2.17)
А затем решение { y i j } находится по формуле
(2.2.18)
Отметим, что предобусловливание по методу Холесского или LU-факторизации для задач вида (2.2.10) менее эффективно, чем предобусловливание по Булееву [34].
Пусть требуется решить систему двух
связанных линейных дифференциальных
уравнений в единичном квадрате ((x,
y)
(0,1)x(0,1),
G – граница) с граничными условиями
третьего рода
(2.2.19)
где
(i=1,2)
- достаточно гладкие функции от x и
y , а
константы.
Результаты[35] численного эксперимента по решению системы (2.2.19) на кластере показали, что использование предобусловливателя более чем на порядок сокращает временные затраты на решение системы линейных алгебраических уравнений. На рис. 2.2.5 представлен график зависимости времени вычисления от числа используемых процессорных элементов.
Знание алгоритма формирования номеров ВМ и последовательности значений, которые каждый должен передать, позволяет создать эффективный коммуникационный процесс, учитывающий специфику производимых вычислений.
Анализ представленного примера позволяет акцентировать внимание на ряде обстоятельств. Во-первых, проблема ввода-вывода. Если данные вводить в каждый из n1 ВМ, то время ввода будет превышать по порядку величины время вычисления. Поэтому распределение данных по ВМ должно быть частью параллельного алгоритма. Во всяком случае, пропускная способность ввода/вывода данных должна быть сбалансирована со скоростью вычислений.
Рисунок 2.2.5. Зависимость времени счета от числа процессоров
Во-вторых, достаточно сложно автоматически выявить структуру и организацию межмодульных обменов. Поэтому автоматическое распараллеливание последовательных программ может и не привести к созданию эффективных параллельных программ. Но приведенные выше параллельные реализации метода умножения матриц и итерационного алгоритма решения СЛАУ показывают, к достижению какого результата надо стремиться при построении параллельных программ.
Метод простой итерации (метод Якоби)
Пусть имеется система линейных алгебраических уравнений (СЛАУ) вида (2.2.10), где А — заданная невырожденная матрица nxn с отличными от нуля диагональными элементами, b — заданный (nx1) вектор, а х — неизвестный (nx1) вектор.
Представим матрицу A в виде:
где D – диагональная матрица с диагональными членами матрицы A:
(2.2.20)
A − – часть матрицы A, лежащая ниже центральной диагонали; A + – часть матрицы A, лежащая выше центральной диагонали.
Тогда
Запишем итерационный метод в виде:
Отсюда получаем:
(2.2.21)
Итерационная формула:
(2.2.22)
где хiк+1 — значение компоненты i вектора x на (k+1)-ой итерации.
Метод Якоби заключается в разрешении каждого из уравнений системы относительно одной из компонент вектора. Таким образом, из первого уравнения системы выражается х1 и его значение принимается за х1к+1. Из второго уравнения определяется х2 и его значение принимается за х2к+1 и т. д. Переменные в правой части этих соотношений при этом полагаются равными их значениям на предыдущей итерации.
Теоремы о сходимости метода:
Теорема 1. Если матрица А имеет строгое диагональное преобладание, то итерации метода Якоби сходятся при любом начальном приближении Х0
Теорема 2. Если матрица А симметрична и положительно определена, то итерации метода Якоби сходятся при любом начальном приближении x0 тогда и только тогда, когда матрица (D+D-A) положительно определена.
М
атрица
А называется матрицей со строим
диагональным преобладанием, если для
всех имеет место неравенство
Критерий завершения процесса вычислений :
(2.2.23)
где xk – приближенное значение решения на k-м шаге численного метода.
Параллельный алгоритм метода простой итерации
Метод простой итерации описывает следующая система уравнений:
Значения компонента вектора х на каждой итерации не зависят друг от друга, а зависят только от значений вектра, вычисленных на предыдущих итерациях.
Схема параллельного алгоритма итерационного решения СЛАУ приведена на рис.2.2.6. Рассмотрим основные этапы алгоритма.
На первом шаге определяется количество
координат вектора, вычисляемых на каждом
ВМ. Для просторы записи положим, что
число строк и столбцов матрицы А кратно
количеству процессоров в системе, т. е.
если m — количество строк матрицы А, а
N — количество процессоров в системе,
то
.
Значению вектора Х на предыдущей итерации (Xold) присваивается значение вектора начального приближения Х0.
На следующем шаге происходит распределение по ВМ компонентов матриц А, b, Xold.
Следующие операции производятся параллельно на всех ВМ системы:
на ВМ1 вычисляются компоненты
;на ВМ2 вычисляются компоненты
;…
на ВМ n вычисляются компоненты
.
Вычисленные в каждом ВМ компоненты передаются остальным ВМ.
Рисунок 2.2.6. Схема алгоритма решения СЛАУ методом Якоби
Далее в соответствии в формулой (2.2.23) на одном из ВМ производится проверка критерия завершения процесса вычислений. При достижении требуемой точности:
,
где r — номер итерации, i — номер компоненты
вектора Х,
решение СЛАУ найдено (вектор Хr+1), работа алгоритма завершается.
В противном случае, значению Xold присваивается значение Хr+1, и происходит следующая итерация.
Представление схемы алгоритма в виде графа приведено на рис.2.2.7.
На данном графе оператор «1» выполняет определение числа координат вектора, вычисляемых на каждом из ВМ, оператор «3» выполяет рассылку необходимых компонент всем ВМ. Операторы «р1»... «рN» и «s1» … «sN» (вычисление компонент вектора по формуле (2.2.20) и рассылка вычисленных значений другим ВМ) выполняются параллельно на всех ВМ.
Операторы «r1» - «rm» организуют цикл для проверки выполнения критерия завершения вычисления. Они выполяются последовательно на одном из ВМ.
Рисунок 2.2.7. Представление схемы алгоритма в виде графа
