Исследование эффективности реализации параллельных вычислений на класстере МЭИ (статья Лю Ляна), страница 2

В табл, 2 приведены результаты параллельного рсшения СЛЛУ методом Гаусса ддя размера матрицы и = 5000, а на рис. 5, б, 7 и 3 показаны графики изменения соответствующих критериев эффективности в зависимости от количества выделяемых процессоров. Пусть дана СЛАУ '~Г а .х, = а,. „+, где ! = 1, /=1 2, ..., и. В предположении, что а!! а О, первое урав- и пение системы ~~Г а! х/ = а! „ь ! делим на коэффи/=1 циент а! 1, в результате получаем уравнение ! ! ! х! ч- ~' а!/х = и! „„1, где а = а! /а 1, / = 1,, и; /=г ! а! „ь ! = а! „+ !/а1! . Затем из каждого из остальных уравнений вычитается первое уравнение, умноженное на соответствующий коэффициент а,1, В результате эти уравнения преобразуются к виду ! ! 1 а, х = а,, „, 1, где / = 2, ..., и', а, = а1/а,! ! /=г 1 а! „ч ! = а! „+ !/а!1.

Первое неизвестное оказалось исключенным из всех уравнений, кроме первого. Да! лее, предположив, что агг м О, делим второе уравне- 2.2,2. Метод Якоби Метод Якоби, называемый методом простой итерации, один из простейших итерационных методов. 1 2 4 8 !2 16 20 24 28 32 36 40 44 48 52 56 60 64 589053„639957 301279,05798 154554,130077 92839,938184 62883,428955 47523,73004 38250,087976 31784,298897 27630,589962 24702,032089 21320,162058 20164,668083 18647,03393 17036,904049 163 11,463 ! ! 8 15293,591022 14673,516939 !3982,443094 0 173,974037 323,826!89 973,13797 1!48,761034 1354,261446 1454,1502 1480,543!37 1703,55 1531 1382,194519 1988,701582 2036,68 Н14 2270,497084 2322,613573 2546,490908 2645,457745 2759,005308 2822,58997 1 1,955176353 3,31!309925 6,341412045 9,367391374 12,39493805 15,40006105 18,53285145 21,31839653 23,84636567 26,99584395 29,21216891 31,58967223 34,47398594 36,1128665 38,5163752 40,14400163 42,12809493 1 0,977588177 0,952327481 0,792676506 0,780615948 0,774683628 0,770003052 0,772202144 0,761389164 0,745198927 0,749884554 0,730304223 0,717947096 0,71820804 0,694478202 0,687792414 0,669066694 0,658251483 АВТОМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА, ИНФОРМАТИКА 0(83 1,00 600 000 540 000 .

480000 к~ 420000 !3 360000 в !ааааа в 240 000 Р. = 180000 Ол щаааа 60 000 0,95 0,90 0,85 0,80 О О О О О 0,75 О О О О О О О О 0,70 О О О О О О О „ 2750 л э л 2250 !750 Ой й 1250 О О К 750 О~ 250 О О о О О О О О с!К3 42,5 О О о О О О О О О О 37,5 27,5 22,5 17,5 12,5 7,5 2,5 О О 4 8 1г и ю 24 гз 32 36 4а 44 48 52 56 60 64К Рис. 5. Залксимость времени решения СЛАУ От количества провессорол К О 4 8 !2 16 20 24 28 32 36 40 44 48 52 56 60 64 К Рис.

б, Зависимость времени обмена данными от количе- ства процессоров К О 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 К Рис. 7. Зависимость коэффициента ускорения С(К1 от количества процессоров К л Для системы ~' а,"х..= Ь,, где 1 = 1, 2, ..., и, 1=1 по методу Якоби вычисляется последовательность приближений неизвестных по формуле х = — ~хая.

+Ь. ! = 1 ... и)с = 12.. а и !43 0 и во всех итерационных методах х7, ! = 1, 2,, и, представляют собой заданную начальную аппрокси- 0,65 О 4 8 !2 16 20 24 26 32 36 40 44 48 52 56 60 64К Рис, 8, Зависимость эффективности Д(К) от количестал процессоров К мацию решения системы. Метод Якоби сходится, если выполнены неравенства !аи~ > '~ ~а, ~, где 1=!, 2,...,и. Окончание процесса решения СЛАУ методом Якоби контролируется по формуле /с 8 — 11 !пах (!х! -х, ~ < е), где 8 = 1, 2...„8 — за!6!ли данная точность. Метод Якоби просто распараллеливается путем равномерного распределения вычислений значений х1, !' = 1, 2, ..., и, на К процессорах кластера, анало- гично тому, как это делалось выше для перемножения матриц, Параллельная МР!-программа построена таким образом, что на каждый процессор кластера распределяется один и тот же МР!-процесс, вычисляющий распределенные на него значения неизвестных.

При этом на каждом шаге итерации все процессы пересылают на один из процессоров вычисленные имн значения неизвестных СЛАУ, МР1-процесс на этом процессоре осуществляет контроль окончания вычислений по заданной точности. Это так называемая синхронная схема организации процесса решения СЛАУ. В табл. 3 приведены результаты решения СЛАУ с размером матрицы и = 500 с точностью 1. 10 6 методом Якоби для различного количества процессоров К в кластере. В табл. 4 приведены результаты решения СЛАУ с размером матрицы п = 5000 и точностью 1х10 6 методом Якоби для различного количества процессоров К в кластере, а на рис.

9 — !2 показаны зависимости от К соответствующих критериев эффективности. Как следует из анализа'полученных результатов исследования, при увеличении количества процессоров в кластере, а следовательно узлов, увеличивается время, затрачиваемое на обмены между узлами, и эффективность работы кластера (загрузка его процессо- 95 АВТОМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА, ИНФОРМАТИКА Таблица 3 Коэффициент ускорения С(К) Время обмена данными, мс Количество процессоров К Эффективность Д(К) Время решения СЛАУ, мс Таблица 4 Количество процессоров К Коэффициент ускорения С(К) Время обмена данными, мс Эффективность ЯК) Время решения СЛАУ, мс ров) уменьшается.

Кроме того, при количестве выделяемых процессоров К ь 4 все вычисления осушествляются на узле кластера, и в этом случае межузловые обмены отсутствуют. Этим объясняется, что время решения СЛАУ уменьшается прямо пропорционально увеличению К для К < 4. Заключение Выполненные эксперименты показывают, насколько может быть важен метод решения сложной задачи на кластере. Например, сравнивая результаты ! 2 8 12 !6 20 24 28 32 36 40 44 48 52 56 60 64 1 2 4 8 12 !6 20 24 28 32 36 40 44 43 52 56 60 64 21,343946 !0,694981 5,460024 6,074051 7,423018 8,630037 9,65504! !0,787882 ! 1,664367 13,657974 14,598795 !6,033919 ! 7,164946 18,556327 19,393921 20,76602 22,582033 24,49587 1566,929102 798,763037 401,993997 206,50506 144,286156 114,586 95,177973 81,830978 71,996927 65,586163 61,047098 58,547062 54,83391 52,658081 50,033146 48,! 08079 46,477924 44,4691 ! 8 0 0,131776 0,86443 1,977196 2,544958 3,351604 4,2!6565 5,072201 6,13524 7,664246 8,360687 9,865606 10,90593 11,380735 12,192255 !3,293308 !4,004894 14,460087 0 0,294209 3,970623 5,67913! 6,692225 8,186917 8,681982 10,149759 11,038834 11,9249! ! 2,704031 12,985075 13,507342 14,0909! 2 14,922869 !5,571535 16,29074 16,992092 ! 1,995697421 3,909!30436 3,513955678 2,875373063 2,473216048 2,210653067 1,978511259 1,82976334 1,562746!29 1,462034778 1,327036402 1,243461296 1,150193727 1,100548259 1,027830369 0,945!73803 0,87!32335 ! 1,961694557 3,897843312 7,587848462 10,85987142 13,67469937 16,463!4848 19,!4836093 21,76383309 23.89!!5372 25,66754446 26,763582!2 28,5759141 29,75666929 31,31782083 32,57101789 33,71340557 35,23634316 1 0,997848711 0,977232609 0,43924446 0,239614422 0,154576003 0,110532653 0,082437969 0,065348691 0,0488358!7 0,040612077 0,03317591 0,028260484 0,023962369 0,02116439 0,018354114 0,015752897 0,0!3614505 1 0,980847273 0,974460828 0,948431058 0,904989285 0,854668711 0,823157424 0,797848372 0,777279753 0,746598554 0,712987346 0,669089553 0,649452593 0,6!99306! 0,602265785 0,53!62532 0,56!390093 0,550567862 96 АВТОМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА, ИНФОРМАТИКА 0470 1,О 1500 '.1ЗОО «- 1100 Й й 900 « 700 « 500 К зоо 0,9 О,о О,7 0,6 о о о Рпс.

9. Зависимость времени решения СЛАУ от колнчес- пгя процессоров К !7 о 0 о о о О о «15 о о о о е о о 0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 К Рис. 10. Зависимость времени обмена данными от коли- «есгва процессоров К с!8) 40 о о о о о 3О 25 о о о 15 о о ш 5 с О 4 8 Гг Ы 20 24 28 Зг Зб 40 44 48 Щ 56 6О 64К Рис.

! !. Зависимость коэффициента ускорения С(К) от ко- личества процессоров К решения СЛАУ с количествам уравнений, равным 5000, методом Гаусса и методом Якоби, легко видеть (см. табл. 2 и 4), чта итерационным методам можно Литература лучше распараллелить задачу при хорошем угадыва- нии начальных приближений корней (когда число итераций оказывается небольшим) и существенно ус- корить процесс вьгчислений.

х 13 й 11 й 9 .х 7 В и 5 йз О 4 8 !2 !6 20 24 28 32 36 40 44 '48 52 56 60 64 К 0,5 О 4 8 12 16 20 24 28 32 36 40 44 48 «2 56 60 64 К Рис. !2. Зависимость эффективности 5г(К) ст количества процессоров К Результаты экспериментов также показывают, что при увеличении количества узлов и соответственно процессоров в кластере обменные взаимодействия даже для рассмотренных примеров задач с их неболь- шим числом оказывают существенное влияние на критерии эффективности. Нами были проведены аналогичные эксперименты решения СЛАУ с количеством уравнений 5000 на кластере, организованном из обычных двухъядерных компьютеров и сетью обмена Ейгепгег, имеющей латентность 120 мкс по сравнению с 4 — 5 мкс сети 1)бр1)«)1ВА)«)13 кластера МЭИ, Эти эксперименты по- казывают, что время параллельного решения задач на кластере МЭИ в среднем на 20 — 50% меньше, чем аналогичное время для кластера, организованного из персональных компьютеров.

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

1. Центр суперкомпьютерных технологий 1ЦСТ) МЗИ. П1!р:77ацрегсопзро1!по.арргпа1.го, 2. Суперкомпьютеры. 011ругягае.ацрегсопгрогега.гв. 3. Демидович Б.П., Маром И.А. Основы вычислитель. ной математики. Мс Наука, 1970. 4. Информационно-аналитический центр по парап. лепьныц вычислениям. 01!рэурага!!е!.гц. .