Теоретические оценки ускорения и эффективности параллельной реализации ПТМ скорейшего спуска

Раздел VI. Параллельные алгоритмы

УДК 551.466

А.Е. Чистяков

ТЕОРЕТИЧЕСКИЕ ОЦЕНКИ УСКОРЕНИЯ И ЭФФЕКТИВНОСТИ

ПАРАЛЛЕЛЬНОЙ РЕАЛИЗАЦИИ ПТМ СКОРЕЙШЕГО СПУСКА

Рассматривается параллельная реализация алгоритма ПТМ скорейшего спуска для решения сеточных уравнений. Приведены оценки ускорения и эффективности работы параллельного алгоритма в случаях декомпозиции по одному и двум пространственным направлениям. Получена зависимость ускорения от числа процессоров.

Параллельный алгоритм; попеременно треугольный метод; теоретические оценки .

A.E. Chistyakov SPEEDUP AND EFFICIENCY ESTIMATION OF PARALLEL SSOR ALGORITHM

Parallel realization of analog SSOR has been presented at the paper. Speed-up and efficiency estimation for 1D and 2D domain decomposition techniques has been presented. The relation between speed-up and involved processors is given.

Parallel realization; SSOR; Estimates for speedup.

Параллельный алгоритм описан с учетом особенностей имеющегося в Технологическом институте Южного федерального университета (ТТИ ЮФУ) HPC-кластера, представляющего собой систему с распределенной памятью, из 128 узлов, объединенных сетью InfiniBand, с пропускной способностью 20 Гбит/с., , , SMP- 16- -

емом ОЗУ 32 Гбайта. Параллельные вычисления с применением технологий MPI

128 -

цессоров. Проведенные численные эксперименты показали, что максимальное ускорение (дая задачи размерностью 351x251x14), равное 43,6, достигалось на 128 про.

Для оценки характеристик параллельного алгоритма нам понадобятся некоторые фактические данные о производительности вычислительной системы. Данные получены в результате тестирования пакетами Linpack и Pallas MPI benchmark.

Infiniband, -

( ):

♦ латентность: 1,82 мкс;

♦ пропускная способность: 1224.38 Гбайт/с.

Пиковая производительность одного вычислительного ядра узла кластера: 9.2 GFlops.

Метод решения сеточных уранений. В конечномерном гильбертовом про-

H

где А - линейный, самосопряженный (А = А ), положительно определенный оператор (А > 0). Для нахождения задачи (1) будем использовать неявный итерационный процесс

В

т+1 т

х - х

+ Ахт = /, В: Н ^ Н.

где т - номер итерации, т > 0 - итерационный параметр, а В - некоторый обратимый оператор. По определению обращения оператора В в (2) должно быть суще, А (1).

При построении В будет исходить из аддитивного разложения

а = а+а2, а* = а2.

В силу

В = (Е + соА1)(Е + соА2),^> 0, у є Н .

Поскольку А = А > 0, то вместе с (3) это дает В = В > 0. Соотношения (2)-(4) задают попеременно-треугольный итерационный метод (ПТМ) [1] решения (1).

-

спуска [5] для расчета сеточных уравнений имеет вид

гт = Ахт - /, В(ют )аТ = гп, 2

со =

а

АО 2

т +, = а +

т+1 т

а

х

т+1 т _ , т

= Х -Тт+1О ,

а + = а

т+1 т

Декомпозиция области по одному пространственному направлению. Каждый процессор получает область, полученную путем разбиения исходной области на части по одному из координатных направлений с пересечением в двух узлах (рис. 1). После того как каждый процессор получит свою часть области, рассчитыва-(5) ( -

мент) (рис. 2).

2

Рис. 1. Декомпозиция области. Кружками обозначены узлы одного процессора,

крестами - соседнего к нему

Рис. 2. Расчет вектора невязки

После чего каждый процессор определяет максимальный по модулю элемент и предает его значение каждому процессору (рис. 3).

Рис. 3. Схема передачи от каждого процессора к каждому

После передачи каждый процессор считает максимальный элемент, в нем будет храниться норма вектора невязки.

Подставим

(Е + атА)( Е + атА2)ат = гт.

, А1 - , -

гда А2 - верхнетреугольная. Задачу (11) можно разбить на две подзадачи

Вначале вычисляются сверху вниз вектор ут, затем снизу вверх вектор оО . Схемы расчетов векторов ут и оО изображены на рис. 4.

Рис. 4. Схема для расчета вектора ут изображена сверху, вектора а - снизу>

у т -

нительной информации и может независимо от других процессоров посчитать свою часть области, остальные процессоры ждет от предыдущего, пока он не пе-, .

,

передачи, их можно избежать в случае увеличения объема передач. Данные рассуждения также используются для расчета вектора оО .

Далее считаются скалярные произведения

I

I

I

Каждый процессор считает свою часть скалярных произведений (14)-(16), затем осуществляется передача от всех ко всем рис 3. Значение скалярных произведений будет равно сумме всех передаваемых элементов. Остается только подставить значения скалярных произведений (14)-(16) в уравнения (7)-(8). С помощью формулы (9) осуществляется переход на следующую итерацию. Результаты использования многопроцессорных технологий для расчета полей течений приведены в табл. 1.

1

Количество процессоров Время, с, Ускорение эффективность

1 1447,415 1 1

2 795,307 1,82 0,91

3 598,875 2,42 0,81

4 504,043 2,87 0,71

5 399,695 3,62 0,72

6 352,892 4,1 0,68

7 304,012 4,76 0,68

8 287,366 5,04 0,63

9 270,897 5,34 0,59

10 262,657 5,51 0,55

Как видно из табл. 1 видно, что параллельный алгоритм попеременнотреугольного метода может быть применен для реальных задач и применение параллельных технологий вносит существенный вклад в увеличение скорости схо-.

Декомпозиция области по двум пространственным направлениям. Каждый процессор получает область, полученную путем разбиения исходной расчетной области на части по двум координатным направлениям, рис. 5. Смежные области перекрываются в двух узлах по направлению, перпендикулярному плоско.

После того как каждый процессор получит свою часть области, рассчитыва-(5) ( -

).

максимальный по модулю элемент и передает его значение каждому процессору. После передачи каждый процессор считает максимальный элемент, в нем будет храниться норма вектора невязки.

Вначале вычисляются сверху вниз вектор ут, затем снизу вверх - вектор ат . Схема расчета вектора ут изображена на рис. 6.

Рис. 6. Схема для расчета вектора ут

Показана передача элементов после расчета двух слоев первым процессором. На первом шаге вычислений первый процессор обрабатывает верхний слой. Затем осуществляется передача перекрывающихся элементов смежным процессорам. На следующем шаге первый процессор обрабатывает второй слой, а его сосе-

- .

6. ут

требует дополнительной информации и может независимо от других процессоров вести обработку своей части области, остальные процессоры ждут результатов от

,

функций для узлов сетки, располагающихся в предшествующих позициях данной строки. Процесс продолжается до тех пор, пока не будут рассчитаны все слои.

(14)-(16).

Каждый процессор считает свою часть скалярных произведений (14)-(16), затем осуществляется передача от всех ко всем (рис. 3). Значение скалярных произведений будет равно сумме всех передаваемых элементов. Остается только подставить значения скалярных произведений (14)-(16) в уравнения (7)-(8). С помощью формулы (9) осуществляется переход на следующую итерацию. Результаты использования многопроцессорных технологий для расчета полей течений приведены в табл. 2.

Таблица 2

Количество процессоров Время, с. Ускорение Эффективность

1 7,490639 1 1

2 4,151767 1,804 0,902

4 2,549591 2,938 0,734

8 1,450203 5,165 0,646

16 0,882420 8,489 0,531

32 0,458085 16,351 0,511

64 0,265781 28,192 0,44

128 0,171535 43,668 0,341

Из таблицы видно, что алгоритм попеременно-^еугольного итерационного метода скорейшего спуска и его параллельная реализация на основе декомпозиции по двум пространственным направления могут эффективно применяться для решения задач гидродинамики при достаточно большом числе вычислительных узлов.

Теоретические расчеты ускорения и эффективности параллельной реализации ПТМ. Теоретически найдем трудоемкость, необходимую для выполнения шага ПТМ скорейшего спуска для СЛАУ с семидиагональной матрицей на

.

гт = Ахт - /

нам необходимо выполнить 14N арифметических операций (сложение и умноже-).

гч т

Расчет вектора И , из уравнении

(Е + А)/” = гт,

(е + А)ит = /”,

требуется по 9N операций на каждом полушаге (всего 18^, т.е. при расчете СЛАУ с верхнетреугольной и нижнетреугольной матрицей соответственно.

Для перехода на следующую итерацию

Хт+1 = Хт -Т^иГ

потребуется еще 2N операции.

Также необходимо учесть количество арифметических операций затрачиваемых на расчет скалярных произведений в оптимизированном ПТМ скорейшего спуска

(т т\ X 1 ( т\ 2

и; , и ) = ^ ) ,

I

(Аит, ит ) = ^ ),

I

(.Аит,Аит) = £[Аит),

I

а их еще 16N штук.

Итого общее количество арифметических операций, необходимых для осуществления одного шага ПТМ скорейшего спуска, составляет 50№

Теоретически найдем время, необходимое для выполнения шага ПТМ скорей,

по одному пространственному направлению на кластере распределенных вычислений. На рис. 7 схематично изображены процессоры в кластере, их п штук. Вся наша область распределена между ними равномерно, т.е. каждый процессор получает об-

NN,.N

ласть размером

П

где Мх, Му, Nz - количество узлов по пространствен-

. -

, , -редачи в условиях нашей задачи. Оптимальный объем пакета обозначим т .

N..  N.

ІІ

1

2

3

N.

Рис. 7. Процессоры в кластере

Схема декомпозиции по одному пространственному направлению с пакетной .

На основании данных, полученных экспериментальным путем, были вычис-, .

А именно:

?0 - время выполнения полезной операции;

1х - время отклика (латентность);

1п - время, затрачиваемое на передачу чисел с плавающей точкой.

Теперь получим выражение для расчета времени вычислительного процесса .

Для расчета вектора невязки необходимо выполнить каждым процессором по

14 N

----- арифметических операций и сделать 2 передачи по N N переменных.

п

Таким образом, общее время расчета вектора невязки:

п

т

14 N

п

г0 + 2(г + г N N ).

О \ х п у г }

т - количество элементов в блоке (пакете);

Далее из-за малого количества передач при вычислении вектора невязки будем пренебрегать временем, затраченным на остановки счета.

Найдем время расчета вектора Wm .

N

—- - количество элементов в одной строке; п

N

X

п N

9—-т • ?0 - время расчета одним процессором одного блока (пакета); п

п -1 - количество передач, выполненное до старта последнего процессора; (п -1)^ - время организации передачи при остановке счета;

(п - 1)1п • т - время, затраченное непосредственно на саму передачу одного блока (пакета);

' N \

9—£. * т • ^ + ( + т • I ) ( -1)- общее время задержки старта, т.е. по-V п 0 х п ) следний процессор начинает работу через данное время;

N , \

9—* * т  го +

п

NN

у___і

- время, затраченное на расчет вектора

т

у последним процессором;

'N , С

9—- * т • £0 + и + т • £ )

0 \ х п )

V п

т

расчет вектора у ;

9*т • 1о +

V п

"у",

у т

NN

V

т

+

+

,

,

расчет вектора W .

Найдем оптимальное значение т

ґ

N.

\

9 ^ * т  го +

V п

NN.

т

+

( Г N \ \ (NN^/ Л

9—^ + т + гх + 1

V V п ) ) V т )

Г г

= 2

N

N л

9——  г + г

у ‘О т1п

п у

NyNz + гх

NN.

+

т

V

N л

9——  г + г

у 10 т 1п

п у

т

NN.

Ґ

18_  г0 + 2^уМг + 2гх (п - 1) + 2гх У г +

т

N

18~  г0 + 2п

п

т

18~П ' г0 + 2tnNУNz + 2гх

^уМп _! + (18 N  ^ + 2гп )(п -1 т

2гхМуМ,п т

\

(  г0 + 2гп )(п - 1) т

У

минимум достигается при

т =

2,МуМм

Ч

Время счета вектора Wm при оптимальном т равно

18 г0 + 2г N N + 2г (п -1) + 4 г N N

0 п у г х \ / Л/хуг

п

9—  г0 + 4гп

V п

(п -1).

1, N

16—и0 - время, затраченное на расчет скалярных произведении скорейшего п

спуска. Временные затраты для перехода на следующую итерацию равны 2 -^0.

п

Таким образом мы получили выражение для расчета времени вычислений на п процессорах:

= 50 N  + ^у», + 2г,п + А^,

V

9  г0 + 4г,

п

\

Теперь получим теоретические оценки ускорения и эффективности параллельной реализации ПТМ скорейшего спуска.

и

Л.

уск

, -

, п .

и = 50 • N • и0;

= 50 N  г„ + 4г,мум, + 2г,п + 4

V

9 —  г0 + 4гп

п

(п - 1);

Тогда

50 Мп

N

9 ^ • г0 + 4*п 1

V п )

А = -

( 1 ( N л

г N N + , г N N п у 1 Л/ х у г 9~- • г0 + 4гп (п - !) +

V V п У

2п

25 тп

г п

2525Ж

п 2п

1 +-------

25Ж

( 1 ( N >

г N N +. tN N п у г Л/ х у г 9~ • г0 + 4гп (п - +

1 V п

2525Ж

Таким образом, мы получили теоретической оценки эффективности и уско-.

Теоретически найдем время, необходимое для выполнения шага ПТМ скорейшего спуска для СЛАУ с семидиагональной матрицей при помощи декомпозиции по двум пространственным направлениям на кластере распределенных вычислений. Вся наша область распределена между процессорами их п штук п = п • п

х у

(пусть п > п ), т.е. каждый из них получает область размером

МММ,

х у

,

, Му, количество узлов по пространственным направлениям.

14 N

Для расчета вектора невязки необходимо выполнить каждым процессором по арифметических операций, а также сделать 2 передачи по МуМ^^ перемен-

ных и 2 передачи по NхМ . Таким образом, общее время расчета вектора невязки:

14 N

п

-го + 2гпМуМ1 + 2гпМхМ1.

Найдем время расчета вектора W .

N Му

--х---1 - количество элементов в одном слое,

пх пу

N N

9—х—1 • г - время расчета одним процессором каждого слоя,

пх + пу - 2 - количество передач, выполненных до запуска последнего про-N N

цессора по Их. +__1 элем ентов,

N N

9 х у

го +

V

,

Кпх пу

г + г

п х

-

п

1

п

п

nN

9-г0 - время счета последним процессором,

п

+ гхпу ^NZ +{tnNx + гхпх - °бщее время, затраченное на пере-

т

дачи при расчете вектора у ;

Таким образом время расчета вектора М^т равно

18 — • ґ0 + 2N N + tn)N + 2N — + ґ п )

0 \ п у х у / г \ п х хх/ г

+2N + пу - 2)

9 ——

ґо +

+ —у

V пх пу ;

—

16—г - время, затраченное на расчет скалярных произведении скорейшего п

спуска. Временные затраты для перехода на следующую итерацию равны 2 -Nt0.

п

,

п :

50 — • ґ0 + 4N + —у )—А + 2N + пу

+

+2

+

/ „ Л

N N.

х + ,

К пх пу у

Рассмотрим случай пг = пу = >/п , при этом время счета будет

N

I Г

- 50— • ґ0 + 36 (П -

п ' ' п

Теперь получим теоретические оценки ускорения и эффективности параллельной реализации ПТМ скорейшего спуска.

А = — = -

Ауск ґ

50 — • + 36

Ауск = '

п

1 +

36 50—

(пп -1)+-

4п

50^

А

Ел —*2-

\ ’

^эф

1+

36 50—

+ -

4п

г /

50^

л

+ -

х у у

На рис. 8 изображены графики зависимости ускорения от количества процессоров, рассчитанные теоретически и экспериментально.

Рис. 8. Зависимость ускорения от числа процессоров. Сплошная кривая - зависимость, полученная теоретически, ломаная - экспериментально

В теоретических оценках ускорения рассматривается случай модельной задачи с прямоугольной областью. При решении задачи для реального водоема расчетная область имеет сложную форму. При этом реальное ускорение меньше его теоретической оценки. Из рис. 8 видно, что обе кривые проходят достаточно близко друг к другу, т.е. зависимость ускорения, полученную при теоретической оценки можно использовать в качестве оценки сверху ускорения для параллельной реализации алгоритма ПТМ скорейшего спуска путем декомпозиции области по двум пространственным направлениям.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Самарский А.А. Теория разностных схем. - М.: Наука, 1989.

2. Коновалов AM. К теории попеременно-треугольного итерационного метода // Сибирский математический журнал. - 2002. - № 43 (3). - С. 552-572.

Чистяков Александр Евгеньевич

Технологический институт федерального государственного образовательного учреждения высшего профессионального образования «Южный федеральный университет» . .

E-mail: cheese_05@mail.ru.

347928, Таганрог, пер. Некрасовский, 44.

Тел.: 88634371606.

Chistyakov Alexander Evgenjevich

Taganrog Institute of Technology - Federal State-Owned Educational Establishment of Higher Vocational Education “Southern Federal University”.

E-mail: cheese_05@mail.ru.

44, Nekrasovskiy, Taganrog, 347928, Russia.

Phone: +78634371606.