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

ЕНИСТЕРСГВО науки,. ВЫСШЕЙ ШКОЛЫ И ТЕХНИЧЕСКОЙ политики РОССИЙСКОЙ ФЕДЕРАЦИЙ, ■ • . ;

ТАГАНРОГСКИЙ РАДИОТЕХНИЧЕСКИЙ ИНСТИТУТ ш.В.Д.Кзлизкова

На правах рукописи

ОВЧАРЕНКО Ольга Игорегаа '

УДК 681.324 , 519.612

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ ' АЛГОРИТМОВ БЫСТРЫХ ПРЯМЫХ МЕТОДОВ ДЛЯ РЕШЕНИЯ РАЗНОСТНЫХ ЗАДАЧ МАТЕМАТИЧЕСКОЙ ФИЗИКИ

вцизлъность 05.13.13 - вычислительные машины, комплексы,

системы и сети.

■атгтзга 1к — тттгтлиенгаттр тлпгтгг* тг№па тол# 'гот^гт.гк-т*

математического моделирования и математических методов н научные исследованиях ^технические науки;.

АВТОРЕФЕРАТ диссертации на соискзнкв ученой степени кандидата технических наук

•Тогчотлг. _ 1 С»Сг£

РлЗога наполнена в Яаучко-исследоЕателъском , инстит/1 МНОГОПРОЦЕССОРНЫХ зычкс.ЧЕТаЛЬЕЫХ сесгэм пот Таганроге»

радиотехническом икституте ик.В.Д.йапшкова ■

Научный руководитель - доктор технтесквх наук,

профессор МШЕЕВИЧ 0. Б.

Официзльшв оппонента: доктор технических наук

КРАВЧЕНКО П.П. кандидат телшескнг наук ЕВДОКИМОВ В.П.

Ведувдя организация - Иастктут ¿дакладнах проблем механики и математики АН Украины /г.Льеов/

£з2ита состоится ьЛАХЛ&В- 1992г. 2 {£) час,

заседании ссеиналгзнссзанного совета Д 063.13.01 при Таганрога т:здист9хничэсксм институте им. В. Д.КагашкоЕз по адресу: 24Т928, Тагавоог, ул.Чехова 2.

диссертацией можно ознакомиться е сиолиогека института.

^тстэефе^ат т^эзослак "М 19Э2Г.

Ученый ■ сэк^тарь специализированного совета,, доктор технических наук профессор

Горелова Г.:

TTpTTt/jra

л jj

narí та

С'ЕЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

эточных эллиптических уравнений.

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

Создание многопроцессорных вычислительных систем {¡/ВС/ о

м 111

производительностью операций в секунду определило один из

взхгейша путей повышения скорости решения трудоемких задач и

ЧО НОЕт-гЙ отатт о па Г?Е?ТСГТ*Т* Ли/^ТЧ-ТТ- ппсиит г«п НГ>П

' ' -----------— * .. » ^ * иаи.^ш ".I..-----------л.С X ,

характеризующийся совместным исследованием параллельных свойств

При разработке параллельных алгоритмов оыстрых прямых методов возникает ряд проблем по выбору наилучшего вычислительного алгоритма в зависимости от размерности задачи, количества процессоров, значения параметра, характеризующего быстродействие каналов связи при заданной топологии (ЛВС, связанных с различными ^з^иантами распределения сеточной информации и алгоритмами выполнения отдельных зтапов.

Дг\ txa 7roT>irQTi/-i Tsnaifemrjr nonr^af.nwa т* rirnri wo тг^тэоит*а Л/л TruinT.tJr.r-tj о

параллельных, алгоритмов быстрых прямых методов щюеодились в предположении, что временем выполнения межпроцессорных оомонов mcshc пренебречь. Однако, времвннне затраты на обмены могут сильно tí ттатт- хта эффективность параллельного алгоритма, так как стремление увеличить быстродействие при рэздкзЕЦИи параллельного алгоритма на МВО не всегда согласуется с возможностями коммутационной системы.

■гЭКтй1 образом, требования к обеспечений максимальной эффективности использования параллельных вычислительных систем, с одной стороны, и недостаток аффективных параллельных алгоритмов, с другой, и определяют актуальность диссертационно!? работы.

Целью диссертационной рзоотн является разработка параллельных алгоритмов для решения краевых задач математической уазики быстрыми прямыми методам*, обеспечивающих эффектнее использование многопроцессорных вычислительных систем и

исследование способов их. реализации . на МВО с .различныш топологшши и производгаелыюсгяж каналов обмана информацией.

Для достшиния указанной цели в работе решались следухцие задач:::

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

- разработка и исследование параллельных алгоритмов прямых методов (циклической редукции,разложения по базису и методов типа РАОЙ), предназначенных для решения разностных уравнений, Еоаникаших при аппроксимации. многомерных уравнений эллиптического ж параболического типов;

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

■ Матовы исследований основываются на теории разностных схем к щда.:их. методов решения сеточных уравнений, теории многапроцассорных шчислителышх &истэм и параллельных вычислений, а такке методах оценки эффективности параллельных алгоритмов.

Научная новизна работы состоит в следующем:

- разработаны параллельные алгоритмы быстрых пряшх методов (циклической редукции, разложения по Оазису й типа РАОР), являщнвоя экономичными не только по количеству арифметических операций, но и по количеству операций обменов;

- предложены способа реализации параллельных алгоритмов, характеризующиеся различными вариантами распределения сеточной информации и алгоритмами енполнэния отдельных этапоЕ прямых методов, позволяющие уменьшить Ерэмекные 'затраты на решение разностных задач на .»¿ВС в среднем на 12Ж-505;

- получены оптимальные значения числа шагов- циклическог редукции Ь (Ь={1-6)) в ГАСй(Ь)-алгоритме для различных значена размерности задача К, количества ■ процессоров р и параметра, характеризующего быстродействие каналов связи к, позволяйте пс сравнению с вспольвоезешимисн ранее значениями (,Ь=(1 ,2}) повысит! эффектишость параллельных ?Д0Н(Ь) - алгоритмов в среднем н.! 203-50% для МВО с универсальной коммутацией и ез 50:5-85% для МВО < кесткой коммутацией;

- разработана рекомендация по использовании параллельны.'

алгоритмов быстрых ггч-ыс м»-годов д*» с реалявош тотгогияка и значениями пар'*. *: ;••, хчрвкмрвттм бистро'яастаже каналов связи.

Практическая ^энад^гь раосгы состоит:

- в разработка веки параллельных алгоритмов оыстрых прямых методов, обеслвтававсЕ: эДОжтиввооть (Е^/р) использования ыв<3 з диапазоне (0.5 - 0.98] при решении разностных эллиптических уравнений;

в ■ сокращении времени решения прикладных задач математической физики при использовании предлояешшх оггпшалыгых значений: параметра 1;

- з разработке набора программ, позволяющих определить коэффициенты эффективности и ускорения при использовании параллельных алгоритмов на МВС с учетом значений параметров N. р и X и типа топологии.

Реализация результатов раооты. Материалы диссертационной работы использованы при выполнении научно-исследовательских работ, проводимых в НИИ {.ВО при ТРТИ им.В.Д.Нвлмыкова по Государственным научно-техническим программам "Создание высокоэффективных средств вычислительной техники и передачи данных для автоматизации машин, оборудования, технологических процессов, научных исследований* проектно-конструкторсккх раоот, производства, управления и внедрение их е отрасли народного хозяйства" (Постановление СМ СССР от l6.06.B7r. .<£675-155) и "Перспективные . информационные технологии" (Проект . 05.01.0002Н (СК-НК)). Результаты диссертационной работа внедрены на предприятиях: НИМ приборостроения Москва), НИЦЭВТ (г.Москва), ВШИ ПВТИ (г.Москез), НИИ МВС (г.Таганрог), а такхз в учебный процесс при выполнении лабораторных, курсовых и дипломных работ. Они были использованы при создании математического обеспечения мультипроцессора (МВС "Парус"). Подтвержденный актом о внедрении оэдаемый экономический эффект - от использования результатов диссертационной работы составляет 12 тысяч рублей.

Апробация работы. Результаты диссертационной работы докладывались и обсуздалксь на:

Республиканской научно-технической конференции "Функционально-ориентированные вычислительные систем" (Харьков, 1986); Всесоюзной конференции "Проблемы создания суперЭВМ и суперсистем и эффективность их применения" (.»¿иск, 1987); Всесоюзной

б

научно-технической конференции "Проблемы создания аппаратных средств, вычислительной техники для машинного моделирования" (Москва; 4 987); 43-ей Всесоюзной научной сессии НТО РЭС кл.

A.С.Панова, посвяцэннйй Дню",радио (Москва, 1938); 2-м Всесоюзном совещании "Конвейерные вычислительные система" (Киев, 1983); Научно-технической конференции . молодых - ученых • ы специалистов , "Архитектура ЭВМ и мзгшнное моделирование". (Таганрог, 1939); 33-ей Всесоюзной школц - молодых ученых "Численные . мэтоды-./механики сплошной среды" (Красноярск; 1991); научно - технических конференциях профессорско- преподавательского состава ТРТИ- им.

B.Д.Каяиыкова (г.Таганрог, 198£-1988).

Публикации. -По материалам диссертации опубликовано 16 печатных работ. Нройэ того, результат исследований отражены в 4 отчетах по КИР *

Структура и объем работы. Диссертационная работа состоит• из введения, четырех разделов, заключения и придояеккЗ. Она содэркит 129 страниц нзшшопиского .текста, 133 страницы графического материала, 88 наименований литературных источников. ■

СОДЕРШШЕ РАБОТЫ ,

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

3 первом разделе рассматриваются области использования быстрых прямых методов при решении сеточных уравнений. Как правило, быстрые прямые катоды применимы в том случае, если разностную схему ногно свести к ревеню Еекторного уравнения вида:

v -т? v _р„

-о ""О ' *Ы Я * ' I •

где - вектор неизвестных, - заданная правая часть к ^ -

квадратная матрица В качестве модельной рассматривается

разностная, задача Дирихле для уравнения Пуассона в

прямоугольнике С =(СХ хц ..£1а,- а=1,2} нз прямоугольной сеткз

5={х^Н={И1,, ¡{¿¿Те СГ, О Н,, О Я2, ¡1, =1,/И,. И2=12/11гУ с границей 7:

лу =-Дх), хда, У1х)=0, Х€7»

Л = Л^+А,, ЛцУ®?^ х > а=1 ,2. . * а а

КЗ основании анализа современных архитектур выделятся кжовпнв особенности /ЖО, с учи гем которых в дальнейшем ^зарабатываются параллельные алгоритмы.

Параллельные алгоритмы быстрых прямых методов рассматривается га .'©0, имепцих возможность реализовать в ЮТ - резким, то есть исполнение одной программы многими процессорами и :арактеризугдихся следующими осооенностями:

1. Имеется реиащее поле <.РП), состоящее из р-процвссоров ,Пр), объединенных мэзду соОой началами системы коммутации ;СК).

2. Каждый процессор имеет оперативную память (011) для гранения данных.

3. Передавать дашшэ можно нескольким процессорам одновремен-ю, а принимать только от одного.

4. исмэн информацией между процессорам осуществляется б :оогв6тстеии с заданной топологией сеязи. Рассматриваются два :лучая: з первом,- топология связи представляется полным графом .универсальная коммутация;, а во втором - процессоры, не связанные ^посредственно, должны осмеливаться информацией через громеку точные процессоры (жесткая коммутация: "линейка", 'матрица", "куб")-

5 Ар71£?'8ТХЧ6СКЭЯ СП8р21^11 Я ВЯГСЛНЯ^'гся 33 « тэктсв 9 з время; гтеоуемое для передачи одного слова от одного Лр к другому, рашо

ТОЪГ^П^ и

6. Параметр к*-Ьп/Ъп характеризует быстродействие каналов :вязи. В рзооте рассмотрены МВД со следующим оыстродеЯствием саналов связи : низким К=4, умеренным К=1 и высоким х=0,25.

3 качества величин, характеркзутеих "рзспараллеливаемость"

алгоритмов прямых методов, оудем использовать коэффгпдаенты

аосолвтного ускорения З^Т^/Тр и абсолютной эффективности

алгоритма /р. Величина 'т, характеризует Бремя выполнения

"учшего последовательного алгоритма (на множестве

"насматриваемых;, а Тл - время выполнения алгоритма тактах; с г-"4""" Р

использованием р-процессоров.

При реализации прямых методов на МВО возможны несколько подходов к распределении сеточной информации по процессора».

Первый способ предполагает "разрезание" двумерного массива исходных данных на олокк по ОХ,, где х< (1)=!!^ , 1=1 ,N,-1.

При втором спосоое разрезания исходный массив "режется" по

-ъ

В первом разделе для метода циклической редукции были построек: два семейства параллельных алгоритмов, характеризующихся различными способами^ распределения сеточной информации. Казадое семейство, в свою очередь, ^состоит из двух груш, характеризулцихся различными способами и методами решения систем линейных алгебраических уравнений (СЛАУ;, потребность в ротььш которых возникает на отдельных этапах метода.

Реализация серий СЛАУ может осуществляться двумя способами:

- серии СЛАУ для различных значений 3(1; решаются параллельно на всем РП, и отдельная СЛАУ для фиксированного ¿(1) реализуется в одном Пр обычным последовательным алгоритмом;

- серии систем уравнений для различных значений 3(1; решаются последовательно, а отдельная ОШ для Таксированного 3(1) реализуется на всем И1 параллвльнш алгоритмом.

Для решения СЛАУ с трехдиагональной матрицей рассмотрены два наиболее эффективных и часто используемых на практике метода циклической редукции (.СНа; и прогонки (.РЕ) и их параллельные аналоги: параллельный алгоритм циклической редукции для скалярных трехточечных уравнений (РСЙз), характеристики которого привэдоны в разделе 1, к метод параллельной прогонки Якенко Н.Н. -Коновалова А.Н. (ЕРЕ).

Поиск наиболее' аффективных параллельных алгоритмог заключается в их поэтапном сравнении по различным критерия, (способам распределения сеточкой информация, методам к способа* решения СЛАУ). В результате первого этапа сравнения выбрань способы распределения сеточной информации, позволяющие, сократит! время "'решения разностных задач е среднем ка 12$.

на основе анализа коэффициентов абсолютного ускорения 5; (рис. 1) и эффективности £р на втором этапе выбраны наилучми алгоритмы для-различных значений N. р и К:

- для быстрых ;к=0,25; и умеренных (К=1) каналсгпри N«54 дл всех значений р к при й>64 для р^б следует использовать алгорит саоя, а для других гнз'^гшй р - 0?уш2;

_ медленных каналов (к=4 /"при N€256 для любых значений к при N>256 для рсгб следует применять алгоритм 0Н?К, а алгори; ОЕЦ^ е остальных случаях.

и Второй раздел посвящен параллельным алгоритмам мето;

разложения по базису.

Рассмотрены основные алгоритмы вычисления быстро

У

»образования Фурье лЩФ) на отдельных этапах в быстрых прямых этодзх, когда последовательности, ягляется не только здественной, но и обладает дополнительной симметрией.

Наиболее эффективными оказываются алгоритмы, специально ¡зрзботаннне для вычисления симметрических преобразований, гатывающие особенности последовательности, и являуздося сокомичкшлк по количеству операций. Одам из таких алгоритмов шгегся метод разложения по синусам. Единственным. недостатком ггоритмов,- полученных таким способом, является то,' что они )эктйчески не 1 поддаются распараллеливанию. Поэтому реализацию ггсркгкоЕ такого типа имеет сшсл рассматривать в одном юце ссоре.

Свободным от указанного недостатка является подход, снованный на использовании БШ> вещественных последовательностей, зторие являются аналогами комплексных преобразований. Один из 2ких алгоритмов, известный как алгоритм Лоллимора,--по объему ¡числений уступает метода разложения по и дусам, но регулярная груктура связей дает возможность рассматривать его реализации.как одном процессоре, так и на всем решающем поле МВС.

Вводятся обозначения параллельных алгоритмов в зависимости от гтодов и способов выполнения ЕПФ:

I. - метод разложения по сянусам;

II - алгоритм Доллимора;"

III - параллельный алгоритм Доллимора.

Методы и способы решения СЛАУ остаются такими же , как и для аклической редукции.

Проводится сравнение построенных параллельных алгоритмов по пособу распределения данных по процессорам, способам и методам ешения трехдиагональных систем, а такке способам и алгоритмам еализации БПФ.

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

На рисунке ¿ приведены графики изменения величины. Зр в ;зеисимости от р для й=25б и .

На основе анализа величин. Sp и Ер разработаны рекомендации по ¡ыбору наилучшего алгоритма: .

- при наличии каналов с высоким быстродействием (.К=0,25) и серенных (К=1}, следует применять алгоритм!, исполъзуЕщиэ метод

ю

Графика изменения величины Sp лля параллельных алгоритмов циклической репукции при к=1

ср>$

PCR

ppr

Pfto.I

Графики изменения величинп Sp для параллельных алгоритмов метопа разложения по базису при к=1

FA1

PR

V5

pr

Рис.ё

Eocjnp

.•ледснатадьясй прогоняя (?Л$р, 2 тагсхэ алгоритм ГЛ,-,^,

?орнй имеет близкие. к данным алгоритма характеристики "при

и-пттг М тт -

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

5 третьем раздела построена аффективные параллельные алгоритмы .'одоз типз ?а0й(Ь), хзракгэрязуещиэся ра злэтеыми споссйзак и. гадами выполнения отдельных этапов, обеспечивающие значения ¡ффщиентз эффективности 0,5-0,98 для размерностей задач 64-4095}, числа процессоров р=1'4-409б> и к={0,£5; 1; 4>.

• Бали ' выбрзш способы распределения : сеточной информации по (цессорвм в (¡ВО, поееоляидяэ • укеньппть ■ временные затраты на 1Лизщев: алгоритмов в среднем на 20%-25%.

Задача поиска1" наилучшего ?д0щь)-влгорятнв- существенно югпяэтся по сравнении с мзтодета•его'сосгзвляк^лл , тая- .как-¡ведение" алгоритма зависит не только.от паракэтров ]{, р и к, но

л и

т. -

количества аагов циклической редукции. Поэтому сравнение £ЦЬ) - алгоритмов было проведено е два этапа.

первый этап заключался з поиске наилучкего ?АС'Я(Ь; 'оритаа з. пределах каздой; грухшы алгоритмов, характеризупдахся ¡паковыми алгоритмам, и способами выполнения-. ЕПФ и СЛдл но ¡личными значениями. Ь. Для этого■ использовались величины -5_ и

с1

внеденные ранее.., а результате были, получены оптимальные пения параметра Х=£1-5> для. различных значений n. р и к, !Е0ЛЯК£К9 по сравнении, с использоЕзвапэгися ранее значениями жетра. Ь=(1 ,£} повысить эффективность параллельных ТАСН(Ь) -'оритмов на 20Ж-50Й. • - '

йторой этап заключался в нахоздевки эффективных ;Я(Ь)-алгоритмов среда алгоритмов, обладвщих дучикми ¡актеристиккли внутри групп. Для этого были, введены величины

-ф и з_=я 'о. глэ 'Г. - ееэмя выполнения лучиего

V ~р Р 1

¡ледователького алгоритма среди всех групп для фиксированного К,

4 — пуч2аго параллельного алгоритма з данной группе. Р й

На рисунке 3 изображены графини изменения величины - в

гисижсти от р для N=¿56 и к=1. На данных графиках, характери-

здих изменение величины £р целого семейства оптимальных ЗЙ^Ь) - алгоритмов, енделены области равных значений Ь.

На основе анализа величин 3„ и Е„ даны рекомендации по выбору

г е

наилучшего РАОЩЬ) - алгоритма:

для быстрых (к=0,25) и умеренных (к=1; каналов следу« ' .чменятъ алгоритмы, исполъзущие метод последовательной прогон последовательный способ выполнения БПФ 1РАСН(Ь)|Й, РАоа<1)р£>, тайне для небольших значений р>21о?2к~2 алгоритм ?АСН(Ь)^' пспользушсзЗ параллельное выполнение БПФ;

- при наличии каналов с низка! быстродействием (£=4) следу; использовать при люоых значениях р алгоритмы • ?АСЩЬ)рП

5 четвертом разделе была рассмотрена реализация лучш параллельных алгоритмов Ои страх прямых методов нв следущ; топологиях МВС: "кольцо", "матрица", "куб".

На рисунке 4 приведены графики изменения величины Зр п использовании параллельных РАСЕ (I)-алгоритмов на тополог] "кольцо" для N=4096 и различит значений параметров к и р.

Даются рекомендации по выбору количества процессоров д эффективной реализации параллельных алгоритмов быстрых, прям М9ТСД0В НЭ .Д5ННЫ2С ТЗИОЛОП'ЯХ"

- для топологии "кольцо" %ри использовании циклическ редукции 0НВН) и ?АСЯ(1) - алгоритмов (РАСЛ,^, РАСНр количество процессоров следует выбирать в диапазоне 6-256} зависимости от Ы, при использовании метода разложения по бази ',РАрра)- в диапазоне 116-1024}, а для РАрр- р - произвольно;

- для топологии "матрица" при использовании алгоритмов параллельным решением йШ (0йЖз, ЯАОЩЬ)^) р пршзма значения из множества С16-1024}, а для алгоритмов РАр

Р может принимать любые значения в зависимости от М;

- 'для топологии "куб" при использовании алгоритмов 0R.jp тгм"(р «т.-л ппоигаф тялЛутот- до ЯИЕПЗЗСКЗ {16—1024} ТОЛЬКО I медленншГканэлах 1к=4), для других алгоритмов и значений к вые р неограничен.

Рассматриваются Еопросы практического применения получеш результатов ка примере 'МВС с универсальной коммутацией: (процес< ЕС 2703) и с "жесткой" коммутацией (транспьютерная система топологией "ладейка"), а такке возможности испольпэвэ: разработанных параллельных алгоритмов, рекомендаций и наб^ программ при создании функционального и системного наполне: библиотек параллельных алгоритмов.

В заключении обобщаются теоретические и практпчес

л

Е*

Графики изменения велтини ^р для параллельных РАСЙСь)- алГОр'ЛМСП при П=1

N^256

ЛСКМр«

РАСРч(Ь)?

ра.

РАСЖ^йа

^аР

Графики изменения величины Бр для параллельных РАСЙ(Ь) - алгоритмов на топологии "кольцо"

N=4096 .

РАСй(дРЯск= о

РАСКОЛЫ)

рЭЗуЛЬТЗТЫу ПСЛУ™ЭННЫе 2 ДИ С С 6 р Т 2Ц510 ^^О Й р 2(30^6 п

т "ОСГЛЙТрЛЕЭЮТСЯ перспективы ИХ дальнейшего I!СПОЛЬ2СВаКИЯ.

В пралоазнкях приведены материалы по лее ледова! .:;р£ктерисгик параллельных алгоритмов быстрых прямых методов,

ТаКЛЗ ДСКУМЭК7Ы , ПОДТЕЭрХДЗЕЕЗ'О ЕН9Др9НК.в 11 И СПО ЛЬ2022£ резуЛЬТ2Т0В Д1*ССЭрТ2ЦИ0НН0«^ рЭООТЫ

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1 - Разработаны параллельные алгоритмы быстрых прямых мето; 'хЦнкдич&скоЗ редукции, разложения по базису и тжа РА&ЦЬ,

С59СП9тССЕ2К2Ц216 2К2Ч9НЙЯ КОЭф521ЦК&НТ2 ЭФФЕКТИВНОСТИ 0,5—0

ГЭ О г > М.-МЛ1*ЛОТТ* ПП» "ПООМОТУигЛ/ЧфТ/ ГЗПТТОТ7ТЛ ил Ш»110ртт3 0 ТТПГ\»1С1 Г»Г*ГУП/"<Т> г

123р2?ИЭТрЭ, Хар2КТврНЗУ1СДвГ0 ОЫСТрОДвЙСТЕНВ У 2Н2ЛСЕ С0®*3!! ¥

Предложены способы реализации параллельных злгорит? оыстрых прямых методов, характеризующиеся различными вариант; распределения сэ тот1Ной 2*ноорМ2ц*ш но ггооцбссорам рэаавдего гк и алгоритма?^ выполнения отдельных этапов, позволяют ^кратит1- ррдчттыо затраты К2 сретение сеточных эллпптичес?

о оттай о г* по тпт»*д и с» 1

3. С- учетом временных затрат нз выполнение зрифметичеа операций и операций обменов, получены оптимальные значэ: параметра 1 для различных значений размерностй задачи ипшшапФт5о ггг^тто ссОрОЕ р И быстродействия КВНиЛОВ СВЛ2И позволяющие по сравнению с использовавшимися ранее значена: параметра Ь={1;2> повысить эффективность использовэ] параллельных РАОН(Ь)—алгоритмов! на МВО с универсаль: коммутацией е среднем на 20%-50% и с кестксй комутацией на 50%-)

4. На осноеэ анализа коэффициентов абсолютного ускоренш ^Ф^ктив^ос11'!!, разработаны рекомендации по выбору наисЗо. эффективных быстрых прямых методов, в зависимости от эначе:

^очологки »ЕС . Разработан набор программ ка языке Фортран, позволяю 25{с1'-юнгля эффективности к ускорения при использова параллельных алгоритмов быстрых прямых датодов нз МВС с уче значений параметпов Н, р , к к типов топологий.

Основное содэ рхание диссертйции отражено в следуй

, Lb

v. Мскзревич О.Б.» БабенкогЛ.К., . Сухинов А.И., Озчврэтгко О.И. Параллельные алгоритм катода щйскг^вской 'рэдукцщг для решения ситочных эллиптических уравнений. —И., 1989. - 36с. - Деп. в ВИНИТИ ?б.04.89, JS28Q2-B89.

?.. Бабенко Л.Н., Макарйвич О.Б., Оухпнов A.M., Овчаренко О.И. Параллельные алгоритмы метода разложения по базису. - М., 1991, - 57С. - Деп. В ВИНИТИ t0.09.9J, » 3666 - В91.

3. BsosHKO Л.К., Манаревич O.E., Сухинов А.И., Овчарзнко О.И. Реализация FACR(L) г алгоритмов , на многопроцессорной вычислительной системе.- - М., 1991.- 35с. - Деп. в ВИНИТИ 26.07.91, JS3213 - В91.

4. Оухзшов А.И., Овчаренко О.И. Реализация быстрых прямых мэтодов на матрично- конвейерной вычислительной ctctpmsi ; > Tastreu докладов 2-го Всесозюного соведаraw "Ко'стй^рпыэ вычислительные системы". - Киев, 1938. - С. 50-51.

5. GyxiciOEA.il.,- Овчаренко О.И. Параллельный алгоритм метода циклической редукции, для решения сеточных эллиптических уравнений// Тезисы доклада i Всесатаной конференции "Проблемы создания суперЭВМ и эффективность их применения", Мн., 1987. -0. 51-52.

6. Вабенко Л.К., Макаревич о.В., Максимов М.М., Овчаренко О.И.', Рыбицкзя Л.П., Оухиноз А.И. Оценка производительности многопроцессорной вычислительной . системы с программируемой архитектурой. - М., 1990. - 28С. - Деп. в'ВИНИТИ 1S.03.9Q, JS1416-B90.

7. Бабенко Л.К., МакареЕкч O.S., Сухинов А.И., Овчаренко О.И. Способы реализации базовых операций вычислительной алгебры е мкогояроцз с сорных вычислительных системах// Управляющие системы И машины, 1989, J65. - С. 25-23.

Ô. Сухинов А.И., овчаренко О.И. Об алгоритмах решения трехмерного ■ уравнения теплопроводности на многопроцессорной вычислительной системе//Электроннов моделирование. - 1988, J610.'22-25.

9.' Сухинов А.И., Овчаренко О.И. Организация вычислений при . решения многомерных уравнений параболического и -гиперболического типов на ПВО//' Тезисы доклада Всесоюзной научно-технической конференции "Проблемы создания аппаратных средств вычислительной техники дам машинного моделирования". -Москва,' 1987. - С.66.

Ю. Николаев И.А., Сухинов А.И., Овчаренко О.И.

алгоритма решения трехмерного уравнения теплопроводности на основе, схем расщепления. - П., 1966. - Юс. - Дел: в ВИНИТИ ¡8.02:86, Ä1U6-B86.'

1' Сухинов А.И., Ов$арешо, О.И., Нестерова Г.Г. Параллельный алгоритм задачи обтекании трансзвуковым потоком е потенциальном приближении. - м., 19Ö7. - 11с. - Деп. в ВИНИТИ 16.09.8?, № 6710-В87.

!¿. Сухинов А.К., Нестерова Г.Г., Орчаренко О.И. Oö.одном подходе к распараллеливая™ метода- верхней релаксации (SOR)// Тезисы доклада научно-технической конференции молодых ученых и специалистов "Архитектура ЭВМ и машинное моделирование". -Таганрог, 1989. - 0.44-45.

13. Сухинов А.И., Овчаренко О.И. ОС оценке производительности многопроцессорной вычислительной системы на задачах матричной алгебры и. математической физики// Тезисы доклада ШП Всесоюзной научной сессии НТО РЭС им. А.С.Попоеэ, посвященной Дню радио. - Москва, 1988. - G.35.

14. Еабенко Л.К., Макаревич О.Б., Овчаренко О.И. Векторизации базовых крупных операций к^ногопроце с сорной вычислительно! системы// Тезисы доклада 2-го Всесоюзного соьещани* "Конвейерные вычислительные системы". - Киев, 1988. - 0.58-60,

15. Суханов А.И., Овчаренко О.И. О реализации базового наборЕ программ линейной алгебра на многопроцессорной системе// Тезисы доклада ill Всесоюзной школы молодых ученых "Численные метода механики сплошной среды".- Красноярск, 1991. - 0.35-36

16. Овчаренко O.K., Сухинов A.M., Хзрина О.Д., Черкасов A.A., Целых А.Н. Структура библиотеки параллельных алгоритмо! многопроцессорной вычислительной системы// Тезисы доклад! Республиканской научно-технической конференци "Функциснально-ориэктированные вычислительные системы". Харьков, 1986. - О. 57-58.

oil ТРИI. Зак.252

Тир JOS 19GjJ_ г.

МИНИСТЕРСТВО НАУКИ, ВЫСШЕЙ ШКОЛЫ/И ТЕХНИЧЕСКОЙ ПОЛИТИКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ НАУЧНО - ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ при Таганрогском радиотехническом институте им. В.Д.Калмыкова

На правах рукописи

/

ОВЧАРЕНКО Ольга Игоревна

УДК 681.324, 519.612

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ БЫСТРЫХ ПРЯМЫХ МЕТОДОВ ДЛЯ РЕШЕНИЯ РАЗНОСТНЫХ ЗАДАЧ МАТЕМАТИЧЕСКОЙ ФИЗИКИ

Специальность 05.13.13 - вычислительные машины, комплексы,

системы и сети.

Специальность 05.13.16 - применение вычислительной техники,

математического моделирования и математических методов в научных исследованиях (технические науки).

Диссертация Научный руководитель

на соискание ученой степени доктор технических наук

кандидата технических наук профессор О.Б.Макаревич

*

Таганрог - 1992

СОДЕРЖАНИЕ

ВВЕДЕНИЕ...........................4

1. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ МЕТОДА

ЦИКЛИЧЕСКОЙ РЕДУКЦИИ .........................13

1.1. Постановка задачи. Основные понятия . ..........13

1.1.1. Область применения быстрых прямых методов ... . . . . 13

1.1.2. Характеристики параллельных архитектур и алгоритмов . . 20

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

1.2.1. Параллельная реализация метода циклической редукции

Ф для решения систем скалярных трехточечных уравнений . . 32

1.2.2. Параллельная реализация метода циклической редукции для решения систем векторных трехточечных уравнений . . 43

1.3. Сравнение параллельных алгоритмов ... . . .......59

1.4. В ы в о д ы.......................74

2. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ МЕТОДА

РАЗЛОЖЕНИЯ ПО БАЗИСУ ............ ........ 85

2.1. Основные этапы метода разложения по базису........85

2.2. Алгоритмы быстрого преобразования Фурье......... 87

2.3. Параллельные алгоритмы метода разложения по базису ... 100

2.4. Сравнение характеристик параллельных алгоритмов ..... 106

2.5. Выводы....................... 121 *

3. РАЗРАБОТКА ПАРАЛЛЕЛЬШХ 5,А0Н(Ъ)-АЛГ0Р1ШЮВ ........132

3.1. Основные этапы комбинированного метода

Фурье-алгоритма и редукции ............... 132

3.2. Построение параллельных РАСЩЬ) - алгоритмов . . . . . . 142

3.3. Оптимизация РАСН(Ь) - алгоритмов............161

3.4. Выводы....................... 197

4. РАЗРАБОТКА ПАРАЛЛЕЯЬШХ АЛГОРИТМОВ БЫСТРЫХ

* ПРЯМЫХ МЕТОДОВ ДЛЯ НЕКОТОРЫХ ТОПОЛОГИЙ ШС........ 199

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

4.2. Параллельные алгоритма метода разлогения по базису ... 214

4.3. Параллельные РАЙ*(Ь)-алгоритмы ............. 224

4.4. фактическое использование результатов диссертационной работы . ...............................240

4.4.1. Реализация быстра прямых методов на вычислительном комплексе ЕС 1061 - ЕС 2703 ............. . 240

4.4.2. Реализация быстрых прямых методов на транспьютерной системе.................................245

4.4.3. Использование полученных результатов в библиотеках

• параллельных алгоритмов ................255

4.5. Выводы.......................259

ЗАКЛЮЧЕНИЕ ................. . . .......261

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ ...................263

ПРИЛОЖЕНИЕ 1 .......... ...............274

ПРИЛОЖЕНИЕ 2 ..... .......... ....................307

ВВЕДЕНИЕ

Актуальность работы. Прогресс в численном моделировании важных прикладных задач теории поля, гидродинамики стал возможен благодаря появлению быстрых прямых методов решения сеточных уравнений. К числу этих методов следует, в первую очередь, отнести циклическую редукцию, метод разложения по базису и типа facr, предназначенных для решения сеточных эллиптических уравнений, с оценками количе ства арифметиче ских операций о (Niog0N) или, даже ошю^ио^Ю).

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

Создание многопроцессорных вычислительных систем (IffiC) с производительностью 108-^ О10 операций в секунду определило один из важнейших путей повышения скорости решения крупномасштабных задач и открыло новые возможности для проведения вычислительного эксперимента в фундаментальных и научных исследованиях.

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

Значительный вклад в область исследований, связанной с совместным изучением параллельных вычислительных систем и алгоритмов, внесли работы Воеводина В.В., Ильина В.П., Котова В.Е., Кузнецова Ю.А., Марчука Г.И., Самарского A.A., Яненко H.H. и многих других ученых.

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

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

До появления параллельных вычислительных систем развитие быстрых прямых методов было обусловлено потребностью улучшить решение на однопроцессорных ЭВМ, что привело к алгоритмам, которые очень близки к оптимальным и дальнейшее их существенное улучшение практически неосуществимо /1-5/. Создание МВО открыло новый этап в развитии быстра прямых методов, характеризующийся совместным исследованием параллельных свойств данных методов и вычислительных систем /6-14/.

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

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

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

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

Однако исследования, проведенные в диссертации, показали, что временные затраты на обмены могут сильно влиять на эффективность параллельного алгоритма. Иллюстрацией данного факта является параллельный РАСЯ(Ь) - алгоритм, в котором время выполнения обменов влияет на выбор количества шагов циклической редукции.

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

Целью диссертационной работы является разработка параллельных алгоритмов для решения краевых задач математической физики быстрыми прямыми методами, обеспечивающих эффективное использование многопроцессорных вычислительных систем и исследование способов их реализации на МВО с различными топологиями и производительностями каналов обмена информацией.

Для достижения указанной цели в работе решались следующие задачи:

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

- разработка и исследование параллельныхалгоритмов прямых методов хцшьштаесжой редрсции, разложения по оазису и методов типа ?АОй;, предназначенных душ решения разностных уравнений, возникающих при аппроксимации многомерных уравнений эллиптического я лараооличе ского типов;

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

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

Научная новизна работы состоит в следующем:

- разработаны параллельные алгоритмы быстрых прямых методов (циклической редукции, разложения по базису и типа РАСН), являющиеся экономичными не только -ш . количеству арифметических операций, но и по количеству операций обменов;

- предложены способы реализации параллельных алгоритмов, характеризующиеся различав® вариантами распределения сеточной ута^ршкрту и алгоритмами выполнения отдельных этапов прямых методов, позволяющие уменьшить временные затраты на решение разностных задач на МВС в среднем на-12%-50%;

- получены1 оптимальные значения числа шагов циклической редукции I» (Ь={1 -6)) в ?АСН.(Ь)-алгоритме для различных значений размерности задачи Я, количества. процессоров р и параметра, характеризующего быстродействие каналов связи к, позволяющие по сравнению с использовавшимися ранее значениями повысить эффективность параллельных РАСЩЬ)1 - алгоритмов в среднем на 20%-50$ для МВС с универсальной коммутацией и на 50&-85& для МВС с

жесткой коммутацией;

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

Практическая ценность работы состоит:

- в разработке новых параллельных алгоритмов быстрых прямых методов, обеспечиваодих эффективность (Ер=3р/р) использования МВС в диапазоне С0.5 - 0.983 при решении разностных эллиптических уравнений;

в сокращении времени решения прикладных задач математической физики при использовании предложенных оптимальных значений параметра Ь;

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

На защиту выносятся следующие основные научные положения и практические результаты.

1. Параллельные алгоритмы быстрых прямых методоЕ (циклической редукции, разложения по базису и типа РАОН).

2. Способы распределения сеточной информации и алгоритмы, реализующие отдельные этапы быстрых пряшх методов.

3. Оптимальные значения параметра 1 ( количества шагов циклической редукции ) в параллельных ЗРАСН (Ь) -алгоритмах для различных значений параметров и топологий МВС.

4. Рекомендации по использованию параллельных алгоритмов быстрых прямых методов для различных топологий МВС.

5. Набор программ для оценки эффективности и ускорения параллельных алгоритмов быстрых црявшх методов на МВС с различными

топологиями.

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

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

"Разработка тестовых программных средств и оценка эффективности ЫВС" (А ГР 01824010461);

- "Разработка теории, принципов построения и организации универсальных и проблемно - ориентированных сверхвысокопроизводительных многопроцессорных вычислительных систем с программируемой архитектурой" (Л ГР 01870014199);

- "Разработка системной поддержки аппаратного компилятора с языка Фортран для многопроцессорной вычислительной системы с программируемой архитектурой" (* ГР 01900037567);

- "Разработка параллельных методов, алгоритмов и методик решения задач обработки спутниковой информации, САПР цифровой аппаратур! и методик моделирования в вычислительном эксперименте" <* ГР 01910053609).

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

- Республиканской научно-технической конференции "Функционально-ориентированные вычислительные системы", Харьков, 1986;

- Всесоюзной конференции "Проблемы создания суперЭВМ и суперсистем и эффективность их применения", Минск, 1987;

Всесоюзной научно-технической конференции "Проблемы создания аппаратных средств вычислительной- техники для машинного моделирования", Москва, 1987;

- 43-ей Всесоюзной научной сессии ШЮ РЗС им. А.О.Попова, посвященной да радио, Москва, 1968;

- 2-м Всесоюзном совещании "Конвейерные вычислительные систеш", Киев, 1 Ж;

- Научно-технической конференции молодых ученых и специалистов "Архитектура ЭВМ и машинное моделирование", Таганрог, 1989;

- 33-ей Всесоюзной школы молодых ученых "Численные методы механики сплошнойсреды", Красноярск, 1991;

- научно - технических конференциях профессорско-преподавательского состава ТРТИ им. В.Д.Калмыкова, г.Таганрог, 1966-1988.

Публикации. По материалам диссертац®! опубликовано 16 печатных работ. Кроме того, результаты исследований отражены в 4 отчетах по НИР.

Отруктурз и объем работы. Диссертационная работа состоит из введения, четырех разделов* заключения и приложений. Она содержит 129 страниц машинописного "текста, 133 страницы графического материала, 88 нашенований литературных источников.

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

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

На основании анализа современных архитектур выделяются

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

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

Рассматриваются параллельные алгоритмы для решения систем скалярных и векторных уравнений и их характеристики при реализации на МВС.

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

Рассмотрены основные алгоритмы вычисления быстрого преобразования Фурье (ЕПФ) и выделены наиболее эффективные для вычисления Фурье-преобразований, возникающих на отдельных этапах в быстрых прямых методах.

Проводится сравнение построенных параллельных алгоритмов по способу распределения данных по процессорам, способам и методам решения трехдиагональных систем, а также способам и алгоритмам реализации БПФ.

Даются рекомендации по выбору наиболее эффективных алгоритмов для реализации на МВС с различным быстродействием каналов связи.

В третьем разделе рассматриваются параллельные

расжю-алгоритмы представляющие • наибольший интерео в плане разнообразия вариантов.

Подробно описываются этапы поиска оптимальных

РАСй (Ь)-алгоритмов, характеристики/ которых зависят не только от размерности задачи числа процессоров и быстродействия каналов связи, но и от Ь - количества шагов редукции.

Определяются оптимальные значения параметра Ъ для различных значений остальных параметров.

На основе анализа коэффициентов абсолютного ускорения и

эффективности даются рекомендации по выбору оптимального РАОИ(Ь) -алгоритма.

В четвертом разделе рассматриваются эффективные реализации быстрых прямых методов на топологиях МВС: "кольцо", "матрица", "куб*.

Даются рекомендации по выбору количества процессоров для эффективной реализации построенных параллельных алгоритмов на некоторых топологиях МВС.

Рассматриваются вопросы практического применения полученных результатов для существующих МВС с универсальной и жесткой коммутацией.

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