Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
учебник_Вс.doc
Скачиваний:
14
Добавлен:
01.03.2025
Размер:
13 Мб
Скачать
☆

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.

Основные этапы алгоритма:

  1. Вычисление частей скалярного произведения (ak+1, xk) и после пересылки частей получение на каждом процессоре всего произведения

Рисунок 2.2.2. Распределенние данных между ВМ на первом этапе алгоритма

  1. Затем на каждом процессоре вычисляется

где k=0,…,n.

  1. Параллельно на всех процессорах системы вычисляем соответствующие компоненты произведений Ax1, Aen+1 , а также соответствующие части скалярных произведений.

Рисунок 2.2.3. Распределение данных на третьем этапе

  1. Каждый из процессоров системы посылает одному из процессоров вычисленные суммы. На этой основе указанный процессор формирует вектор 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. Представление схемы алгоритма в виде графа