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

РТБ ОД

7. I Ь и На правах рукспиа-;

СУХИНОВ АЛЕКСАНДР ИВАНОВИЧ

УДК 519.6:532.5

"ЭКОНОМИЧНЫЕ АДДИТИВНЫЕ АЛГОРИТМЫ ДЛЯ МНОГОПЮЦЕССОРНЫХ СИСТЕМ И ИХ ПРИМЕНЕНИЕ К ТРЕХМЕРНЫМ ЗАДАЧАМ ВОДНОЙ ЭКОЛОГИИ

СЬециальноаь 05.13.18-гесрешческие оснсвы масгематческсго моделирсвания, численные методы и ксмпжксы программ

АВТОРЕФЕРАТ

диссертации на соискание ученей степени доктора фиэиюн^агемашческих наук

Москва 1996г.

Работа вьлюлнена в Таганрогском государственном радюгехшческсм университете

Официальные оппанешы:

доктор фшкомакмашческих нзг/к, профессор Н.В. Арделян,

дскгэр физиксжагашическихнаук, вед)ОДЙ научный сотрудник, В. И. Грынь

доктор фиэикомагемашческих наук, грофессср В. Ф. Тишкин,

Ведущая организация - Инсзгауг 1рясладнсй матемашки и механики Рослжскш) государственного университета

Защита диссертации состоится "_"_1996г. в_часта

на заседании диссертационнсго совета Д 003.91.01 при Институте Магемашческсго Моделирования РАН , по адресу ; Москва, Миусская площадь, д .4г.

С диссертацией можно оанаксмипся в библиотеке ИММ Российской Академии Наук

Автореферат разослан " М " Яи £_ 1996 г.

Ученый секретарь диссертационного совета., доктор фшикомагемалиеских наук

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

Актуальность проблемы. Многое практически значимые пространственно - трехмерные постановки задан математической физики требуют для численного решетия прсизвсди-тельносгей и объемов памяти, недостижимых на ЭВМ с последовательней обрабслксй информации. В пралине матшазическсго моделирования реальностью стало использование многопроцессорных вычислительных' систем ( МВС ), содержащих • сотни - тысячи процессоров. Проекщруклся супер-ЭВМ, ссдфжащие десятки - сотни тысяч обрабаты-вакщих устройств ( процессоров ), с разнообразными таюлсшями связей между процессорами и различными грншодигельностлми каналов обмена информации между процессорами . В вычислительной магя-шике разработаны мощные дэедсша построения экономичных алгоршмсе решэия мнсгсмерных задач масгемашческсй физики , базирующиеся на методе раоцатления .Не представляется возможным дать развернутый обэср работ по схояам расщеплзмя , так как число работ в этой области чрежычайно велико . Одноксмпсненшые схемы расщепления, при распараллеливании сохраняют свойство экономичности по числу арифметических спфаций . Однако, как показывает анализ, они не являются жснсмичными при параллельной реализации на МВС по числу операций ойчаи , в особенности, в случае жесшсй коммутации между процессорами . Затраты на обманы информацией в ряде случаев становятся преобладающими по сравншию с " арифмешческими " затратами.

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

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

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

Пели работы . 1. Постродаие и анализ двухкемпененшых схем расщепления для аппроксимации р — мерных уравнений параболического типа (переменных направлений ( р = 3 ), фактсршванных и эддашшых ( р £ 3 )) в декартовых координатах и криволинейных ортогональных координатах ( цилиндрических, сферических и тороидальных ( р = 3 ) ) и для аппроксимации трехмерных уравнешш гиперболического типа ( факториэсванных и аддитивных) .

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

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

Методы исследования. Для построения двухкемпонентных схем переменных награвле-ний и факпризсеанных схем для уравнений параболического типа в декарятаых координатах использован метод регулярввации разностных ехш А. А. Самарского; исследование устойчивости базируется на теорш устаиивосш двуслойных схем, развитей в работах А. А. Самарского и A.B. Гулина. Исследсвание усгсйчивосш и сходимости аддитивных двухкомпонентьк схем для уравнений параболического и гапер-балического типсв в дасарговых координатах базируется на сеточном принципе максимума и следствиях из него (для параболического уравнения), а также на методе энергетических неравенств, предложенном А А Самарским . Получение оценок скорости сходимости для уравнения теплопроводности в случае криволинейных координат выполнено путем поэтапна! редукции разностных задач для погрешности к более простым , дапускакшим построение функций , мажорирующих решения, в явном виде и применении следствий из принципа максимума. В тороидальных координатах потребовалось дополнительно доказать лемму, являющуюся аналогом теоремы вложения для двумерней сеточной задачи специального нда.

Исследование параллельных алгорпмов основывается на применении некоторой обобщенной модели многагтродессорной вычислительной системы, с нежесткими требованиями к механизму обмена информацией между процессорами и с различными структурами связей между процессорами , большим диапазоном отноапельней производительности канале® обмена тиформациш, что позволяет охватить широкий класс многопроцессорных систем ( например, мультитранспьютерные системы, матричные вычислительные езкгемы, системы со связями nina " куб " ( "гиперкуб "), вьксксяроизводигельные системы с универсальной коммутацией и г. д.). Построение параллельных алгоршмев базируется на методе геометрического разрезания входной (сеточной) информации по числу процессоров, а также на параллельной (последовательной) реализации базовых процедур, лежащих в основе последовательного атлета соответствующего параалелжого алгоритма. Для построения разностных схем для гидродинамических процессе» циркуляции и динамики фитопланктона использовался метод суммарной аппроксимации . Исследование свойств полученных сеточных задач

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

Практическая значимость .Двухкомепсненшые аддщивные схвиы использовались при численном моделировании термически нагруженных трехмерных конструкций котельных агрзэтт, в частности , оребршных псверхностей нагрева с учегсм неоднородности материалов для стационарных и нестационарных режимов . Разработанные параллельные алгоритмы поеводяют выполнять проектирование библиотек решения сеточных эллипшческих ■ уравнений в пространств двух и трех измерений , а также трехмерных уравнений параболического зила, экономичных в смысле суммарных вро>1жных затрат, для МВС различней архигапуры. Двухксмпонешные аддтивные схемы и алгоритмы их реализующие , используются для расчета трехмерных циркуляционных потоков и эколсгачесюто протеза развития фиттланктшных популяций для мелководных протяженных водов*» типа Таганрогского залива. Апробация работы . Результаты работы неоднократно докладывались на международных, всесоюзных ( всероссийских) конференциях, школах и совоцаниях, в том числе : VI Всесоюзной школе " Теоретические основы и конструирование численных алгоритмов решения задач математической физтки", 1986 г ., I Всесоюзной кшффшцнн "Проблем создания супер-ЭВМ, суперсистем и эффективность их примдаения ", 1987 г., Школе по комплексам прарамм матаиашческой физики 1990г., IIIи IV Школах "Численные метлы механики сплашсм среды " , 1991 г . и 1992 г . , Международной научней ксифершции " Алгебра и анализ посаящатнсй 100- леппо со дня рождения Н. Г. Чебогарша , ( Казань , 1994 г . ), IX Международном Осяюзиуме " Супермик-рокемпыелеры, микропроцессоры и их применение ", (Будапешт, 1991 г .), Всеросатйсксй Школе "Ссвремзмые проблемы матшатическсто моделирования ", 1995 г . и других . Результаты диссертации опубликованы в 18 работах , вышедших в центральных или международных изданиях ; также несколько работ опубликовано в межвузовских сборниках и депонировано в ВИНИТИ.

Структура и обьач диссертации . Диссертация состоит из введения,четырех разделе© , заключения (перечня выводов по работе) списка литературы и трех приложений. Работа содержит 329 страниц основного таяла, 48 рисунков, 22 таблицы и список литературы из 99 наименований.

СОДЕРЖАНИЕ РАБОТЫ . Во введении обоснована актуальность работы, указаны цели и задачи исследования, приведена краткая характеристика содержания работы. Раздел I носит название "Двух-кемпенеганые разностные схачы для аппроксимации многомерных уравнений параболического и гиперболического типов ".

В п .1.1 "Факгоргосванные двухксмпонешные схемы для уравнений параболического типа" рассматриваются абсолютно устойчивые аналога схем переменных направлений и схф1 типа предикторхсррасшр, аппрсксимирутацих смешанную задачу Ксши для трехмерного( р = з) уравнения тииспрсвсдносш с постоянными и переменными коэффициапами: д\х р

— = 1!1«и + (х'4)' е > и) = и(х,0) = и0(х),хе(т, ос а=1

где Г -храница оошеш С, 0<г®< к < с^ а = 1 о

а ос а ' '••-'г»

ЬаВ=^_|ка,Х1и^Е_1|в = 1Т5. • (О

° х а V "1а'

Аналог схемы Писмэна-Речфсрда имеет и щ :

у(х,0)=ио(х),хе©|1;уп+1=цп+1, хе7Ьч3; ^

у п+ 1 = + ц ■)_ 1А 3(ц п+ * - ц п),х £у м>2; п = 0,1.....п0,

гае со сетка с равномерным шагом , пшрывакшая область I у ^ ^-узлы

граничные по направлению Ох ; ^, . _ -узлы сетки, граничные по направлшиям

3 ' «.1.2

Ох,,Охг; Л а - разностные аппрсжсимадаи операторов Ь , а= 1,2,3. Для

устойчивости схемы (2) достаточно псяребавазъ выполнения равенств Л1Лз=Л3Л-1, Л->Лз= ЛзЛ,.1гг0 позволяет ослабить офаничения на форму области по сравнению с ошккомпоненшыми схемами переменных награвлений, а именно область с = с ^ может бьпь цилиндрвмесксй, с образукщаЗ, параллельной оси

О х 3 11 имеющей основанием область ^ , лежащую в плоскости О х, х ,с кусочнотлзд-

ксй границей г с =КохИ)<х < | .Л - В обшаи случае область о мсжег &пь р ор р [ -А3- Р]

односвязнсй , состоящей из объединения областет (-; ^: ( , ^ , где В -

реВ Р

конечное множество номеров и I [ р2'есяи Р1 * Р2 » Р1 е В,р2 еВ ■ Схша (2) сходится со скоростью о(|Ь|1 + хг) в норме гнергаическсго пространства II д,А= (Л ^ ( д.2+ Л3)1 ПР91 условии достаточной гладкости входных данных

задачи и искомой функции. Двухксмгкжншая факториэсванная схема, аппрасазмиругацая начала»- краевую задачу (1) для р - мерного (р>3) уравнаим

ттлспрсводносга в области в записывается в виде :

Г / >„«1+1_„11

Р

п (е+тКо)^-—+ Ау п=ф п, х есо^, п = 0,1.....п0;у°= и0(х), хе<оь,

1 = 1 р г

где КР = -0р(4?р-1Л2р-1 + 11-в2М1р«)«?рА2р].Р=1.-.г-1; (3)

где символ Га 1 означает целую часть числа а , я - символ Кронекера. а - весовой параметр, 0 < а < 1; - коэффициенты, выбираемые исхода из условий устойчивости

и точности .Для обеспечения устойчивости требуется перестановочность сперагорш ( для четного р, р 5 4 ищи а = 0 для нечетного р, р £ 3 ) :

• ••• II 1 1 п 4 4 - „ . ГА)

л2р_1лт = лгл2р_1;л2рЛ7=л7л2р;Р=1."»г-1;7 = 2р+1.....р.

Схема (3) сходится со сксросшоо(||1|(2+т) в НА -Для реализации систем ( 3 ) в случае

разделяющихся переменных можно применить быстрые прямые методы с затратами, не превосходящими о^ Р1п гч)' в слУчае неразделящихся пфеменных целеоообраяю использовать итерационный псюдзФкмю-треуголшый метэд с затратами о^Р^^Ь^/е))»

где е -требуемая точность, N -характерноечислоузлов оежитюсднсмугонаправлений . В п. 1 2 "Лскалню-двумериые схемы для уравнзшй параболического типа" для задачи(1) при самых общих предгюдожшиях относительно фермы области в построена аодшивная схема »названная лекально-двумерней схемой (ЛДС):

).)+Э/'=ц1+|1/>',же71ц:2р_мр,р = 1.....П] = 1.....)„!у°=п0(1),1е5ь. ®

Имеет место Теорэи. 1. ЛДС (5 ) устойчива по начальным и граничным условиям и по правей части в норме сеточного гроезранства С гак, что для задачи ( 1) 15« люСых

х, Ь= шах{ьа] вьпалнеио нф®®ство а

¡1 1м(х,.')|е *

О 7

1 о ~ 1 Г

шах |«р(х,1')1 *+ 2 * 2 О 5 Г £ т ^ с j=0 р = 1

Из последи® сценки и свойства суммарной аппросимации следует сходимость ЛДС со скоросшю о(ь2+ х) •

Подраздел 1 . 3 посвящен ЛДС в криволинейных ортогональных координатах : цилиндрических, сферических и тороидальных. ЛДС обладают лучшей точностно по сравнению с локально- одномерными схемами (ЛОС) , что достигается за счет способа расщепления трехмерней задачи на цепочку "двумерная задача-одномерная задача ", 15м кагором скорость роста функций, являющихся локальными погрешностями аппроксимации для разностных уравнений , входящих в цепочку, является наиболее медлоюой в особых точках для соответствующей системы координат.

В п. 1. 3. 1 для аппроксимации начально- краевой задачи дня уравнения теплопроводности в циливдре Сх(0<1<Т],С={0<г<К,0£ср<271,0<2<1}

*|п0|с4 мах И*.*'>|с -1т]дГ1 „о*

с с 0<1'<Ло 7 2-8 2р_ рШах \а,(1 - а)}

]+ РАН • <6>

'с0

5а

— = Lru4L(J)u + Lzu+f'x,t;;u= H'A",U,x еГ;и(х,0)= u0'x>,x gG,

гае

1 3

Lru=-— * ror

гМт u =—; Г -граница схЗласш G,G=GUr;

дт J 9 1" 2 Z я 2

\ r otp dz

U)

^r,<p4 27t,z,t) = u(r,<{i,z,t), lim r^Su/Sr) = 0,

r—>0

использовала^ ДДС вида

шЬ=»г>:<»фх<0ггае f = 'il)+f(2); и г,ш ф,ш г-<яки

координатным направлениям г, m , z соответственно ; Л , Л >Л -разностные

Z ф Г

аппроксимации опфазоров L > L и L соотвегсзвашо ;

Z ф Г

¡|h|2 = h р + h ф + h ; для кразкосш далее апгрсжазмацрш начальных и граничных условий опускаем .

Имеет место Теорема 2. Пусть в Gx!0<t<T) функция u(xi,x2,x3,t) имеет сфаничшньк пршзводные до четвертого порядка по xhXjiXj" декартовым переменным и ограниченную прсзпводную u/öf, а функция f -ограниченные производные второго порядка по Xl, х, t х Зи ограниченную прсижодную Sf /dt .Тогда poiErHie ЛД С (9) сходится в норме С к решшшэ задачи (8) со скоростью 0('|||,||г+

Для ЛОС оценка асорали сходимосш в Сесть o(jhj2+ ^Inil/t))- В п- 1-3-2 для

1 вчалы ю-дфасЕОЙ задачи для уравнения :тшлсерстазносш в области G={0<r<R,0< ф<2л,0<6< л}> Г-граница G , G = Gu Г ,х eG,0< t <Т: д и

— = Lru+L(pu+Leu+f(x,t);u=n(x,t),x еГ;и(х,0) = ц,(х),х eG,

■2" 1

1 d I гди\т 1 ö и_ 13

„и = ——I Ti— ! L„u= —-----'LqU =

sinQ-56

r ~r2ör{ 8 rj V r2sin203<p2 « ^дв

ur,cp+27i,Q,tj=T<r,cpiG,t), lim r^siiÖctySe; = lim r (siifl дц'дв), вчШ в->п-0

lim v2(öu/Sr) = 0, u(x,t) = un(x\x eG,x =(r,<p,Q), ««P««1 ДДС вша r—> 0 u

vj-l/2_vj-l \ i-1'2 - vJ-vJ-1'2 , | , (10)

•-^-= 1Л g+ A <pjy ■» 1~+r[i] r-^-=AryJ+f(2);xe<ah,

® h=® гх®<рх®е'ГДе ш Г, ffl{p »® e ~ Се1КИ 110 К00РДИ1ШНЬ1М направлениям

Г,Ср.9 соотегствешю; Д у гу-Л ду- аппрскспмаццц операторов

L , L р, L g соответственно; f = f + f

Имеет место Теорема 3 . При ограничениях на функции u(Xi t), f(x,t)> указанных в Теореме 2, ранение ЛДС ( 10) сходится в норме С к решению задачи (9) со скоростно oí jjhj2 + Ji InílVj) .Отметим, что для ЛОС в случае сферических координат

оценка скорости сходттмосш в норме сеточного пространства С отсутствует.

В п. 1.3.3 построены ЛДС .для случая горсяшалшых координат, которые связаны с

декартовыми координатами соогнош&шями:

ashQcosm ashGsinq) asina . _ _ _ „

х--—, v =-—, i =-,0 < 8< +oo,0< G < 2л, 0< q> < 2л.

ch6-cosо * ch8-cosa ch9-coso

Вводится новая пространственная переменная р, sinf}=1/chO, 0 < р < тс/2,0 < G <+<ю. Начальнокражая задача для уравнения тшлопрсеодноста в торсвдальных координатах с учегсм введенной замены записывается :

Lpn+LoU+L^+fíi.t), х €G,0< t<T,

G = [х = (р,о,ф )|0 < р < р тах < я/2,0 < a <2я,0 < <р < 2я},

j.l-sinp* cosa)3 д ( sin р * cos ft t 5u'¡, P a2sinp*cosp 5pil-sinp*coso Эр)

Ц _ i .1 - sinp* coso,)3 д( ctgP „ cu), L Ц _ 11 - sin p * coso)3 д2и, ° a2sinp*co«p SoU-sinP* cosa даJ Ф a2cos2P ¿<p2

r={x=(fta,<p)|p=pmaxD<a<23i,0<(p<2n];G=GUr;t e(QT];u|r=^t}; ^х,0)=и^х),х eQ

u!o ^0+0- и!о = 2я-0-^!<у = 0+0- ^ a = 2я-0'и1ф = 0+ 0 ~ u! <p = 2*-0, Ul)

n, limf dnP'«»P *£Н)~ 0.

аф!Ф = о+о 5ч»!Ф = 2я-°'рТои-^Р*«»^ ар

Построим ЛДС:

0<ч<1, лс. Л ф! Л р -разностные аналога операторов Ь 0 >Ь ф >Ь р соопзетсженда

Справедлива Теорема 4 . При ограничениях на функции щ х , I), Т(х , О, указанных в Теореме 2, решение ЛДС- (12) сходится к ранению задачи (11) в дарме С со ^роспю о(т + ||Ь|:+ чр) !п(уь р)), ||Ь|г= 1.ДРУПК

ЛДС могут сьпь символически представлены так чЛр + Аф->(1-Ч)Лр-»Аа <•«>; чАф+Лр-*(1-ч)Аф+Ла

. Дтя ЛДС вида (13) оценка скорости сходимости совпадает с приведенной выше; для схемы (14), а также для ЛОС следует ожидать сходимости со скоростью О (т + Ц Ь|" + т/ И р 1п( 1/ Ь р)). Подраздел 1.4 " Двухкомионешные схемы для

гиперболических уравнений" посвящен факториэованным и аддитивным схаим для р— мерных (р> 3) уравнений. Рассматривается начально - краевая задача еидд:

X ее; Мг=КхД);|Ц<£0; <*,())=и^.хе^

где Г -граница области в ,о< с£> < к а < а = 1,...,р. <15)

Конструкция факторшованнсй двухксмпснентнсй схвял аналогична тш , что была построена для параболических уравнений ( см. соотношения ( 3 ) ) :

П (е+ г 2Кр)у Ау п= <р п, х ещ п= 0,1.....п0;у0=и0(х)) (1б)

Р=1

у1(х,0)=и0+{^51^ | Лд^+ГСх.О^.хеа,,; у(х,еп)=ц(1»1п).1е7Ь'п=1.....п0>

где смысл используемых обозначений такой же, что и для параболического уравнения . При соответствующей гладкости входных данных задачи (15) схема (16) сходится со скоростью о(||Ц|2+12) в Нд> если каждое из выражений Лау,у^>Я>

аппроксимирует соответсгвумцее непрерывное выражение со вторым порядком, и выполнены условия ( 5 ) перестановочности операторов . Аддшивная

даухксмпснапная сха^а (ДДС) для трехмерного гиперболического уравнения имеет вид:

уИ1_2у^1/24у]л , , ^

т2

у(х,0)= и0(х),

:= 4Лз(у]+1 + У])+2<р1,х еагь> Л =1.....Лог

2 "Ч 2

Е-1р(л1 + Д2)1у1/2=и0+^0+^-(л1 + Л2)и0 +

+12(*(1Г^КЛ1+Л2+Лз)и+О}|1=0'хе®ь;

В соотношениях (18) каждое из разносшых выражений лау,а=1,2)3{у^>ф^ ,а=1,2;

аппроксимирует соответствующее непрерывное выражение со вторым порядком. При соответствующей гладкости вхсшых данных задачи ( 16 ) схема (17) сходится в со

сксРосшоо(|Ь|5+ т) ВНД

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

раллелытах алгоритмов решали сеточных уравнений. Будем предполагать, что: имеется рзшкщее поле (РП) , состоящее из р процессоров ( Пр ); процессоры связаны между собсй посредством ксммуташкннсй ошш (КС) по полному графу связей (системы с универсалы кй коммутацией) или только с "соседними" жестким образом (системы с жесткой коммутацией); работу процессоров координирует управляющий процессор (УП), на который возложены глобальные, функции управления и обмаи информацией; каждый процессор имеет а|мфмеаико-логическое устройство (АЛУ), собственную оперативную память (ОП), объем которой достаточен для хранения всей информации, обратываемой данным Пр, блек межпроцессорной связи (БМС); передавать информацию можно к m процессорам однекрематно, где Ш ^галичесгво связей данного процессора с другими; принимать информацию процессор может только от одного процессора, прат этом тркм и передача одновременно не допускаются. Для актом с жесткой коммутацией в работе рассматриваются следующие шпы связей между процессорами : " линейка"," матрица " куб ". Для анализа алгоршмев используются две характеристики прсясюшпельност собственно процессора и каналов связи, а именно: t ^ характерное время выполнения одной арифмешческсй операции, t ^ -врача выполнения операции о£мена одним словом

между процессорами, включающее время доступа к ОП, синхронизации и непосредственно пересылки. Вводится параметр k=t(J/ta, щшщятз^тшап! <Ътстродействпе канале» евлзт

по отешаию к произзодтелшости процессора, который для широкого класса МВС имеет диапазонзначжия 0,1 < к < 10 ■ Пусть 7^^ремя Еыпатнения гюследовательного

алгоритма на одногродасщэной вычислительной сист®1е, j - вре^я выполнения его

параллельного аналога на р - процессорной акгготе. Для характеристики алгоритмов используются коэффициенты: ускорения Sp=TjyTpH абсолютного ускорения

- _т /mjn|j |»где Т pj - время выполнения i - ого параллельного алгоритма ,

1 < i < m из семейства m "родственных" в опредатенном смысле алгорпмов. Базовыми процедурами параллельных реализаций алгоритмов ранения двумерных сеточных уравнений эллиптического пита являются: роиение систем трехгочечных скальных уравнений , а также транспонирование в общем случае прямоугольных массивов на РП МВС. В п . 2 .1 зля МВС с универсальной коммутацией рассмотрены параллельньк алгоритмы: прогонки (алгоритм H.H. Яненко- АН. Коновалова), циклической редукции для решения актем скалярных трехточечных уравнений с изменяющейся матрицей коэффициентов и в случае серии систем с одном и той же матрицей и изменяющимися правыми частями и получены соответствующие временные оценки. Для траноюирсвания выбран атгоршм Паркинсона, обладающий естественным параллелизмом . В п. 2 . 2 "Параллельная реализация метод а циклической редакции на МВС с униЕфсачшсй коммутацией" рассматршются параллельные варианты метода циклической редукции для решения систш трехтотечных ватерных уравнений виза

-Y ; i+CYrYui = Fi. l,.i,N-l,Y0=F0. YN=FN, <l»

к которым сводятся двухксмпсавпные схемы рааштления в случае разделяющихся переменных и областш специального вида . Основой для параллельных алгоритмов , в частности, быстрых прямых методов ( CR,FA, FACR) являются ставшие уже "клаоат-

ческими" их пос.адоеат1?льньте аналоги , хорошо Зсрекамендовавилге себя в вычислительной практике. Этот подход, позволяет получать семяктва параллельных атгоршмов, с такими же как и у их последовательных аналогов харшаеркгпвсами точности и запасом

устсйч1 шоспI , обладающие сесйстеом „ _ -полней распарадледтваемосш

lim £. _ = 1

N -» в

в асимптотическом смысле и имекшие приемлемые значения Е рдля реальных сегак. В работе истальзукяся два основных способа распределения сеточной информации по процессорам. Первый способ предполагает распределение двумерных массивов исходных данных х . . <j < Nj,l< j< N-> вфпкальными полосами! по Г N j/р*| xNj элементов;

если N j не делится надело на р , то дсюолним исходный массив нулевыми столбцами до

раз>кра ["Nj/p"|-p столбцов. В процессор номеращ 1<т<р загружаются элементы

исходных массивов со значениями индексе® [Nj/p'|'(m-l)+l < i <j~N1;/p~j' т,

1 < j < N •> -Пра1 втором способе дЕумерньк сеточные ыасашы исходных данных

распределяются горизонтальными полосами по процессорам. В процессор номера т, 1<М<р, загружаются элемдаты »сходных массивов с индексами i . i^i^jy

j : (m-1) • [Nj/p]+1 < j 2 ш- [n ■ Первый аюсоб распределения сеточной информации будем назыЕагь также "способом разрезания по i ", автором -" способом разрезания по j". Для получения параллельных вариадгов циклической редукции, используется алгоршм с пониженными затратами арифметических операций, описанный в монографии A.A. Самарского и Е.С. Нггколаева "Методы решзгия сеточных уравнений", М., Наука , 1978, с . 139-144 . Совокупность параллельных варианте® наряду со способами распределения сеточной информации по процессорам определяется выбором последовательных или параллельных алгоритмов решения систем 1рехточбчных уравнений - прогонкой (последовательной или параллельной) или скалярным вариантом цшслгтческой редукции (последовательным или параллельным). Пр1 разрезанш по I в случаз использования последсвагелшых алгоритмов решения скатярных трехточечных уравнений до их решения и после выполняется транспонирование на РП МВС соответствующих сеточных массивов, составлящих ранения и правые части систем. Возможное чисто параолельных атгеритмов с учетом сказанного равно восьми. Анализ построенных алгоршмо© показывает, что во всем диапазоне значений параметра к наиболее экономичными латаются атгоришы, исполь-зукиие последовательную прегенку, для обоих способен рааределения информации. Для сравнения введена плоскость параметров ( к, а )) гдеа = N/p. Выявлена достаточно слабая

завиатмостьог р границ, разделяющее обитает значений (к, а)(области эффективности),

для которых един из ашгершмов экономичнее другого. На рк. 1 область эффективности алгоритма cr( j; prs) расположена справа и сверху ог граничных линий, а для атгориг-

ма j. pr5 ) - слева и снизу. На рисунке 2 приедены графики абсатюшсй эффективности

построенных параллельных атгорптмов метода циклической редукции для к=1. В целом параллельные атгсрпмы CR обладают приемлемой эфсфаспшностью (g >0,5) ш BceNI

диапазоне значений параметра к если log2a > ß„ я 1kIog2(log2 p)/I0 ■

Рисунок 1. Рисунок 2 .

В п. 2 .3 " Параллельные алгтрямы метода циклической редукции для МВС с жесжсй коммутацией " проанализированы построенные параллельные вариагаы метода CR применительно к МВС nina" куб", "матрица " и "линейка". Это потребовало, в свою очередь, разработки экономичных варвганкв алгоритма травспснирсватпм Паркинссна , а также п^аллельнш циклической редукции для решэия актом скалярных трехточечных уравнений на МВС с данными структурами связей. Для параллельной прогонки реализация алгсрпма и временные оцетки приблизительно одинаковы для всех типов связей между процессорами. Приведем крапам итог анализа алгоритмов. Наиболее экономичными также, как и в случае универсальной коммутации, являются алгоритмы CF[i,PR$ uCKj, PR$> прием при переходе от универсальной коммутации к "кубу", "матрице" и

"линейке" происходит явно выраженное сужение областей эффективности д ля алгоритма CK(i,PR$ с одновременным расширением области эффективности 'кял<урирух1цего" алгсргама. На рисунке 3 схематически изображала области эффективности данных алгоритмов д ля МВС с жесшсй коммутацией. Другой эффект, наблкщэшй при дзрадации структуры связей между процессорами,-сдвиг границ областей эффективностей с ростом числа процессоров, приводящий к преимуществу алгсргама CI(¿PR$» наиболее явно выраженный для МВС шла "линейка".

В подразделе 2.4 "Параллелытые алгсрпмы метода разложения по базису для МВС с универсальной и жесткой коммутацией "рассмотрены возможные параллельные варианты метода разложения по базису, (далее сокращенно FA ), которые наряду со способами распределения сеточной информации и методами решения систем трехточечных уравнений зависят от выбора алгоритмов быстрого преобразования Фурье (далее сокращенно FFT) применительно к различным структурам связей в МВС. В качестве основных рассмотрены две группы алгоритмов FFT-первая, с лснюкшными затратами арифметических операций, описана в монографии А .А . Самарского , Е. С. Николаева "Методы ранения

сеточных уравнений", ктсрая ipyrma базируется на алгоритме Доллимсра и отличаете* регулярной процедурой вычислений, позволяющей грсвсошь их распараллеливание нг МВС типа SIMD Др>тае алпрпмы, оснсжанные на комплексных атгсршмах FFT МВС типа "линейка". МВС типа "матрица". МВС типа "куб'

07

035

аэ 026 02 315 01 аж о

\

\

\

\ —4—0-4

\ —

г \

\ ч

N

>

1

—*-Р-М —о—pee

\\

\\

\ \ \ >ч к \

\ \ t

-

loga

Рисунш 3.

не имеют, как показывает проведенный анализ, преимуществ по сравнению с указаннымт выше. Поскольку первая ф)ппа алгоритмов характеризуется нерегулярной процедура' вычислений ,чю летает троатемаличным распараллеливание атгоршма на МВС таге SIMD . ю в дальнатшем рассматривается их последовательная реализация в одном про цесссре. Ниже в таблице 1 приведены условные обозначения алгоритмов FFT используемых далее.

Алгернм с пониженными затратами арифшческих операций ПослеасеагельньБ! алгоршм До.плимора Параллельный апгерпм Додлимора

fftj fft2 fft3

Таблица 1.

В результате сравнительного анализа установлено , что наиболее экономичным для всех стукгур связей между процессорами является алгсршм, испатьзугаций разрезание по I , последс®ательную прогонку и для быстрого преобразования Фурье-алгоритм рр^

Присвоим этому атгоршму обозначаете рд( ГРТ^) • Для данного атгоршма эффективность имеет значение более 0, 5 дтя значший параметра к < к о ~ 5 для широкого диапазона значений параметров р и а в случае МВС с универсальной коммутацией .

Подраздел 2.5" Описание и сценка последовательных алгоритмов метода неполной редукции" носит вспомогательный характер. В нем для разностной апгрокшмашй : задачи Дирихле для уравнения Пуассона, и шчачжо- кражей задачи для двумерного уравнения тшлопршэдностн, рассмотрены в^зинты метода неполной редукции в случае

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

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

- (т)4.Г U j_! + C

(m) - (и)

■1.

.(mi

un = -(m) 0 U.. /.

= 0.

(19)

- Ira) _ ч. (m) ,= 12.....

Пщ-fj > "

J+1 1 lJN2/2m

Тогда набор возможных параллельных алгоритмов неполной редукции определяется набором е^яиншв реализации основных этапов метода в соответствии с таблицей 2. В результате анализа параллельных реализаций метода неполной редукции (далее сокращенно обосв1ача0.их как FACRI) > гДе I -число шагов редукции ) были выделены четыре наиболее экономичных в смысле суммарных временных затрат и выполнена их оптимизация за счет выбора параметра 1 . Крапга опишем Еыбранные параллельные реализации fACK'1) -Алгсрлм 1 использует 2 способ храншия входной информации -"разрезание по j ", последовательный атгортпм решения аггач трехгочечных уравнений -

Этап 1.Форм!фсеание коэффициенте» матрицы с 2.Вычисление вектора правых частей Fi 3. Расчет коэффициашж Фурье векторов правых час-rai(прямоеFFT) ^^

Варзшгаы ^Последовательный расчет. 2. Параллельный расчет. 1. Последовательный расчет. 2. Параллельный расчет. fft j 2 • fft2 3 • fft3

Этап 4.Вешение серит трехточечных систем определение векторов (j) ч2 5. Восстановлен! к сеТОЧНОЙ фуНКЦИИ (1) " i.j (обрашое FFT ) б. Гашение систем трехточечных уравнений-опре дедаьие векторов -» . yj

Варианты 1. Последовательная прогонка. 2. Параллельная прогонка. 3. Последжателытый алгсрпм CR . 4. Параллельный алгсрпм CR . t fftj 2 ■ fft2 3fft, 1. Последовательная прогонка. 2. Параллельная прогонка. 3. Последовательный алгсрпм CR . 4. Параллельный алгоритм CR .

Таблица 2.

прогонку, а также также последовательный алгоритм FFT с пониженными затратами арифмептческих операций (FFTj* и последовательную методику расчета коэффициентов

I гг»\ ->

матриц С ' и векторов правых частей т1 . Для этого потребуется четыре раза осу-

J

гцесшляш транспонирование сеточных массивов на решающая поле процессоров: 1) после рЕСчетаЕсех р<т>, ttl = 1,2,...,/ , j=l,2,...,N/2m-l , сеточного массива , столбцами

которого являются векторы и ; 2 ) после раэтега коэффициентов Фурье

J

2(I) к СО» '-1, массива згах коэффициают ; 3 ) по окончании расчета,

коэффициентов Gtypte ^^ ^^ ^ массиваиз них образованнсго; 4)после

обратного FFT, позволяющего восстановил» одну из искомых сеточных функций u(I)(j,j), lsisN, IsJsn/z1-! -Алгоритм 2 использует второй способ хранения

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

FFT

паралжльный алгоритм Доллимэра, аначегшерпж и шестом этапах в качестве метода раштия систем трехточечных уравнений применяется последовательная прогонка . Алгсршм 3 использует 1 способ хранения сеточной информации (массивы "разрезаются по индексу I" ) . Первые три этапа 3 алгоршма аналогичны соответствующим этапам 1 алгоритма с той лишь раэздцей, что никаких транспснтдхваний массивов на решающем поле не выполняется. В качестве метода решетия сисга^ трехютечных уравнший на 4 и б этапах используется параллельный алгсрлм циклической редукции .Последний -четвертый го " кскуреншоспособных " алгоритмов FACR отличается от алгоршма 3 методом решения СЛАУ с трехдаагснальными матрицами , в качестве которого использу-егся пфаллельиая прогонка.

Затем для вьщелаиых 4 алгоритмов для каждого набора значений (N, р)> N = 2 г, р = 2q< г; r,q- целые числа,в широком щшаэсне ихэачший, охватывающем реальные семи ^ < N <2выполнено определение интерваловэффективности

параметра к (г. е. областей зшчатий) и определение оптимальных значений параметра I , который в зависимости ог( N, р) принимает знамения от 1 до 5.

В п. 2 .7 " Параллельная реализация тхэтеремжно-треугольнсго метода" рассмотрен вараинг данного метода, пртгодный для реализации ЛДС в о&ца* случае (область, в которой ставится краевая задача - непрямоугольною формы , уравнения с нфазделяющи-мнся переменными). Вначале рассматривается последовагелшьш вгриит модифицированного жперематно-треутодьнсго метода, методика сгределения априорной информации которого адагпирсюана д ля разностных аппроксимаций двумерных уравнении тзт лопроводносш, характеризующихся существенным диагональным преобладанием матриц систем разностных уравнений. Рассмотренный параллельный алгсрлм МГТГМ характер» зуегся приемлемым гначаад©«! коэффициента, эффективности Е ^ > 0.5 äimN > 32 и

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

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

разработку параллельных алгоршмся решения , в частности , трехмерных уравнэлй теплопроводности, для аппроксимации которых используются ЛДС, а также параллельные алгоргамы решения сеточных уравнений, рассмотрамые во втором разделе работы. В п. 3 .1 "Алгоритмы параллельного ранения трехмерных уравнатий тшлспрсвсдаоаи, использующие Л ОС, на МВС с универсальней коммутацией" рассмотрена параллельная реализация разностной задачи У п+о/3_у11+а-1/3

\ а ^

*а

уи+в£ = р(хЛ, хеТь , а= 1,2,5; п= 1,2,...,пг1; у°(хД) = и0(х), Хе5ь> ^ где^ -множество узловсешИд, граничныхпонаправлашюох а>а = 1,2,3.

Далее рассматриваются три случая: 1) максимальное число процессоров р в МВС "мало" по сравнению с общим числом узлов N 3 сепки ю ^ ,т. е. р < N ;2) максимальное количество процессоров р является Умеренным" по сравнению с обидим числом узлов сегки , т. е. р< N3) максимальное количество процессоров "велико" по отношению к общему числууздав сежи, т.е.р ^ р*

В сосяветсшии с указанными тремя случаями рассмотрим следующие способы распределения информации по прсцессорам, считая для простоты, что область в, в которой поставляй смешанная задача Коши для уравнения ттлспрсвсдносш, является кубом . 1. Разрежем плоскую сеточную область (сеточный 'прямоугольник ") са 1 х «о 2 ш Р тлос а ^ равней величины, например, перпендикулярно оси Ох2 >

построим сеточные "паралжлзтпеды" р в д х ш .Информацию, относящуюся ко множеству р ^разместим вгамяга 3 - ого процессора. 2 . Для умеренного числа процессоров , т. е. когда р < N ^ разрежем плоскую сеточную область га х а на р равных

л* £

подобластей . при дополнительном предположении, что р = а 2, где д - целое

число , 1 < 1 ^ л|р1 1 < } < ^р, являющихся квадратами и построим трехмерные сеточные параллелепипеды р . . = д . . х ю 1 ; сеточную информацию^ относящуюся к па-

раллелешшзур. ., разместим в памяти одного процессора. 3. Число процессоров может 'О

быть "велико", г. е. р < N ^ .Будем для простоты считать, что р = д ^ , где ц —целое число. Каждую из одномерных сепж ш ш ^ и разобьем на 3/^ равных сеточных

fi)2J^ ш Зли 1-ю-л/р И П0С1Рам сеточные 'Ьтарап-

лелепипеды" о . ю 1.х<в 2^Х(Й Зт равных размеров, число которых-р.

Информацию, принадлежащую к узлам одного параллелепипеда . . разместим в

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

слсяутацне обозначения : первая цифра каждой ячейки -номер , грквоенный соответствующей параллельной реализации ЛОС ; а=1, а-2, а-3- обозначения дробных шагсв по времени и метода решения трехгочечных СЛАУ - PRS - последовательная прогонка, PRP - параллельная прогонка, CRP - параллельный алгершм скалярной циклической редукции . В згам же подразделе получены временные оценки с учетом обменов, в частности, транспонирования оеточных массивов, выделшы нашалее женомичные алпршмы (8, 4, 9 м2) и определены их облает эффективности. Установлено, что для "большого" числа процессоров алгоритмы, базирующиеся на однокомпсиеншых схемах расщепления, имеют чрезвычайно низкую эффективность. В п. 3.2 "Алгсргамы параалельного решения трехмерных уравнший татлспрсводности, использующие ЛОС, на МВС с жесткой коммутацией " Еыполнен анализ алгсрлмш, построенных в п. 3.1 применительно к МВС пота "линейка" , "матрица " и 'куб". Оредеяены области эффекшшюсш наиболее экономичных алпршмов, в число которых

Количество процессоров Методы решения трехгочечных СЛАУ на дробных временных шагах

"мадае" 1. а = 1 - PRS а = 2- PRS а = 3 - PRS 2 . а = 1 - PRS а = 2 - PRP а = 3 - PRS 3 . а = 1 - PRS а = 2 - CRP а = 3 - PRS

"умеренное" 4. а = 1- PRS а= 2-PRP а = 3-PRP 5. а = 1 - PRS а ■= 2-NRP а = 3 - SRP 6. а = 1 - PRS а = 2 - PRS а = 3 - PRP 7. I 8. а = 1 - PRS 1а = 1-PRS а = 2 - PRS J а = 2 - PRS а = 3 - CRP | а = 3 - PRS 1

" большое" 9 . а = 1 - PRP а = 2 - PRP а = 3 - РКР 10 . а = 1 - CRP а = 2 - CRP а = 3 - CRP

Таблица 3.

Другой вывод - алгоритмы имеют низкую эффапивность для р > N , в особенносш для МВС шла "линейка".

Подраздел 3 . 3 "Параллельные аттршмы решения трехмерного уравнения ташзпроводноам, основанные на ЛДС, в случае неразделягацихся переметных "носит методический характер . Для ЛДС вида (частный случай ЛДС вида (б)) : . п+1/2 ,л , , ,.п+1 ,,п +1/2

* Члг+Аг'у" 5-^--=ДзУа+1+Г» Х€»,„ п= 1,...п1-1;

уп-Ц'2=цгх1) хе7 = ; у °(х)=ц0(х), хеш,,, (21)

1м *

рассмотрены отсосы распределения сеточной информации по процессорам и параллельные алгоритмы, использующие реализацию МПТМ на МВС, рассмотренную в п.2.7.П<жазано, что алгоритмы, базирующиеся на однокомпонетных схемах расщепления являются , в основном,более экономичными. В п . 3.4 "Параллельные алгоритмы решения трехмерного уракнегам тоиспрсшсаноспт, основанные на ЛДС, в стучае разделяющихся переменных" для аппроксимации задачи (1),

где область С , в = Пх [о< х 3< 13}> П - двумерная (плоская) область ступенчатой

формы, допускающая построение сетки, равномерней, по крайней мере, по одному направлению, а коэффициента^ к2=к2(х3_а.х5). а= [1,2], используется ЛДС-вида (21) .В качестве методов решения двумерной разностной задачи используются параллелжыеалгортпмьт С К , а также РАСЫ (1)> исследованные во 2 разделе. Рассматриваются случаи "малого" и "умеренного" числа процессоров .1 . Пусть

р < N . Тогда способ разрезания сеточной облает а х т на р полос д . равней

1 2 j

величины (вдоль направлемя Ох| или вдоль Ох определяется тт, какой из способов

оптимален для данного набора параметров р, к) применительно к параллельным

алгоритмам СКили РАСК(1)- Далеестроим сеточные параллелепипеды Р .= СЗ .х со •

.1 J

Для решения систем трехгочечных скалярных уравнений используется последовательная прогонка. При р< N возможно использование другого семейства алгершмов, в котором для решали двумерной разностной задачи прмзшются последовательные алгорвпмы методов СИ для решали трехгочечных разюстных задач - последователь-

ные или параллельные алгоритмы ттрегонки или циклической редукции. В гтсм случае целесообразно использовать иное распределение информации по процессорам. Разрежем одну из плоских сеточных областей <в ^ х щ ^ или щ^хса^ ш Р пслос О j равной величины перпендикулярно оси ох г > построим сеточные "шраллелептптеды'р хи .

з j j 1

Информацию относящуюся к параллелепипеду р ^ разместим в памяга процессора номера 1 < ] < р • Для МВС с жесткой коммутацией разработаны с этой целью рациональные способы нумерации и распределяли 1 «формации по процессорам. 2 . Пусть р< N Распределение информации аналошчно тому, что использовалось в п. 3. 1 .Варианты параллельных алгоршмш решашя, базирующихся на двухкемпенентных схемах расшт-ления в случае разделяющихся пфеменных определяются в соответствии с таблицей 4. .Определены наиболее экономичные алтертгмы (8, 12, 14,7,1,2) и установлены их облает эффективное™. Проведен сравнительный анализ параллельных алгоргамов , базирующихся на двухкамгюнеганых схемах расщепления и алгоритмов, использующих одда-компененшые схемы расшепления,в результате которого установлено, что в целом первые являются более экономичными. Преимущество алгоритмов, базирующихся на двухкомпгнентньк схемах расщепленш и быстрых прямых методах, их реализующих, по сравнению с алпоримами, основанными на однокомпоненшьк схемах становится подавляющим ( 2-10раз) при деградации системы коммугащш и с ростом к • На рисунке 4 приведены графами для абсалзошсй эффективности в зависимости от числа процессоров для к =1 • Завершает третий раздел п. 3 . 5 "Локально-двумерный шдэационный метод решения разностных аппроксимаций краевых задач для трехмерных уравнений эллштшчес-кого типа ", в котором построен дЕухкомпонентный аналог итерационного метода переменных направлений (МПН) с оптимальным по Жсрдану набором параметров. Последо-вательньл"! шртанг метода на реальных сетках < 512) уступает итерационному МПН по общему числу арифметических операций в 1-1,44 раза. В отношении параллельных

Количество процессоров Методы рзизптя векторных л асаллрплх трехточечных СЛАУ на дробных временных шагах

" малое" (I группа алгоритмов) 1. Т-СК'Р^'К.р") 2-РБЮ 2- РШ*1 3. 1- СЙ <*> 1 - С11Р I N.pl 4. 1 - СК (5) г - рйб

"умеренное" ( Ифуппа алгершмш) 5. 6. 1-сн (р)(л.,ур) 1- ся ( 2-ТВР\Я 12 - КМ' 1 - СК (р)(!Ч.,/Р) 2 - Р1«

" малое" (I фулиа алгоритмов) 8. 2-РЫ8 9. 1 - ГАСИ 1« ' 2- ГЕР VI* ,р) 10. 1- ГАСЯ (5) 2- СИР (14, р) и. 1 - РАСЯ 2 - №8

умеренное" (Птрутлта алгоритмов) 12. 1 - ГАСИ ' р ( N , -,/р) 2 - РНР !>' ,-у'р) 13. 1-ГАСК 1 2-&КР(]Ч.,ур) 14. 1- ГАСК ! Р)(]У.-/Р) 2- РИБ

Таблица 4.

ДЕухкомпонеганые схезы. Одноксмпонешные схемы .

: Р 'о? 2 Р

Рисунок 4.

алгсрпмов методе® и их сравнительного анализа остаются справедливыми вывода, сделанные для одно и двухкгагонелных схем раацяттения .

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

Внимание к фитспланктонным сообществам обусловлено их исклютшельнсй рапыо как основного первичного продуцента в водных экосистемах, а также их высокой чувствительностью к ашрспсгшнсму воздействию на водоемы. Можно утверждать, что эволюция фгашлангашных сообществ водоэяв является одним из самых важных, хотя далага и не единсгвшным показателем жолсяическсго "здоровья" заливсв. В качестве природных систем, д ля которых рассматриваются постановки модельных задач водной эколсапи, выбраны Таганрогский и Мобижкий заливы, у которых много общего в тдрофиаиеских и (иолсгаческих процессах. Оба залива мелководные и достаточно гротажшнью - отнашгие характерных размеров по гориэсшальным направламям к д^едгам глубинам составляют »5 х 10^ -Вода в заливах хорош прогревается, подвергается активному перемешиванию; круговорот биогенных веществ достаточно интенсивен. В п. 4 2 'Пространственно-трехмерная модель пщродинамики для заливсв и ее

численная реализация" в предполсакшии постоянства пжтюсш, температуры и солзюсш -» _

для функции скорости и = [|и,у,\*Ц и вожышения ^ = ^(х.уд) рассматривается система уравнений:

да

—-г

л Зи Зи Зи , ЗЕ д( Зи

-+и—ь V—1-ТУ--+— V—

I дх ду дг дх 01 \ дг

КА,

-2 А 3* и

дх2 ду'

ЗУ ЭУ ЗУ ЗУ ,

-+ Ц-+ V--н-уу—Нц =

дг Зх ду Зг

Ч Щ дг. А -в—4— V— +А в3у дг '

/

I Зх2Ч2

31

_3 дх

Н

/иЛг

1-5 .

д_ ду

Зи Зу Зуу „

—+—+-= 0,

Зх ду дг

Н

-5

(22)

в С —области, представляющей собой замкнутый бассейн, «раниченный невозмупкн-нсй поверхностью водоема 2 = 0, днем н = Н(х,у) и цилиндрической бсксвсй поверхностью (5 .К системе необходимо добавшь начальные условия

и(х,у,г10) = и0(х,у,1)> \<х,у,х, 0) = \'0(х, у, г), ? (х ,у, г, 0) = £ 0(х,у, г), (х,у,г)с-0д = 0, (23) го которым восстанавливается начальное поле для вертикальней компоненты скоросш и граничные условия, которые формулируются следующим образом. Для горизонтальных компонент скорости: на жидкой части боковых границ должны быть заданы координаты функции скорости И и V , а на твердой-услсеия прилипания; на поверхности с использованием составляющих касательного трения ветра

и=у=Ор()уги.

Зу

31

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

V— =

дг

гае С.

ЗУ

V— =

дг

(24)

(25)

у,

коэффвдкнг

х

трения

временном интервале 1

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

(22)425), полученная расщетлением, имеет вид,

1 Зи „Зи п3и . 1 Зи п3и . 1 Зу пЗу .

-—+ ип— + V — = 0, +лг"—=0, -——ьи -—ьу — = О,

4 31 дх ду 4 31 дг 4 дг дх Зу

с 1 » \ .. с ч '>^

4дХ дг 4дt

-и д'

— 4 —

и

Зх ду'

1д\ А

--= А

431

V 3'

Зх Зу'

18 4 51

I дг) ё8у ,цаГзх

н 8 н |ийх +— [УЙХ ,

а { дг) гь ах \ 8у \

у

с соогоетсгоукщими начальными и граничными условиями . Далее одномерные и двумерные уравнения конвекции аппроксимируются явными схэими с разностями, ориентированными прошв потока, двумерные и одномерные уравнения даффузии-неяЕными схемами, уравнение д ля урсвеннсй поверхности- неявней схакй, а для замены ингаралсв пользуемся формулой прямоугольников. Затем из систем разностных уравнений , аппроксимирующих диффузию по вершкали, обращая трехдиагональные матрицы, и подставляя выражения для сеточных функций и114 * и уп+* в разностное уравнзме для урсвалкй поверхности, получаем сисгму разностных уравнений для функции ^п+1 с

симметричной , бшчно-трехдиарснальнсй и положительно определенней матрицей, которая эффективно может бьпъ ралша МПТМ. Двумерные сеточные уравнения, аппрск-симирукгцие диффузию в гориэсгаальных направлениях допускают реализацию быстрыми прямыми методами. Значения ременных шагов являются приемлемыми и в (3-10) раз превосходят те шага, что допустимо выбирать в редовзмом данному полуявном алгоритме , предложением р . Чеисм и В. Касулли. В целом рассмотренный двухкемпонеганый алпоршм сказывается существенно гкснсмичнее алгоритма Р . Чена и по затратам арифметических операций.

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

ах 61

ам ав

их

= цхДХ + Л*ХаЕ

ах^

+ к.

им

д( ам'1!

8-аХ,

+к3Х-5М,

31

+ сШ

ив

(27)

где X, в, М — концентрации фитспданктсна, биогенного вещеава и метаболита соответственно;^ х I й в > Н м диФФ1Уэиса1Ные коэффициент для данных субстанций в геризен-

• диффузионные коэффициенты в вертикальном

талшых направлениях , \ ^

награвлении;к1 -удельная скорость роста фвпшланктеш ос - удельная смертность фитопланктона; ^ -удельная скорость потребления биогенного вещества; к ^ -коэффициент жскреции; 5 -коэффициент распада метаболита; р -удельная скорость поступления (исгзокго вещества; Б' —предельно возможная концентрация биогенного вещества ;

к2= к0+тМ

бх бу 2

К системе присоединяются соответствующие граничные и начальные условия .При у > 0 возможно ветвление решений системы , что соответствует "пятнистому" распределению фитопланктона Двухксмпенеганая схема строится исходя из условий

« V где отличие от других диф-

/

фузюнных коэффициашж может составлять 3-4 порядка, а также с учетом того, что как и для системы (22) , в системе (27) наблюдается значительное различие в коэффициентах диффузии субстанций в горизонтальных и вертикальном направлениях. Дрючка линеаризованных дифференциальных задач , последовательно решаалых на вроутеннсм интервале t < ^^ ^соответствующая сисгок (27) ,имеетввд

isx + un+i/2£X + vn!i/zsxI0( lax п+1/2ах

4dt Зх 0у 4 flt 5z

1ЁЁ+ип+ 1/255 + v 1Д ЁЁ = о, wn+ ^ = о,

4 St Зх ву 4 St Зг

^ = ^AX+Px(kO+TlMn)snX-pxocX'

i||=^sAS-px(k0+TriM,1)xnS+Ppx(s'-s)'

-Iff^zhD-il-P^iM^Xns.pd-pxXs'-S).

^^МДМ+РМкЗхП-РМ8М' ism а/

(28)

v М

f^+(l-pM)k3X«-8(,-pM)s.

4 31 01

где р и р -весовые коэффициенты..

Уравнения конвективного переноса субстанций системы (28) аппроксимируются явными схемами, с разностями, сришшрсванными против штша. Двумерное уравнение даффузти для функции X атотрскшмируется явной схэкй, остальные уравнамя диффузкнного типа, входящие в отстану (28) даскрешзируются неявными схемами. Разностные аппроксимации двумерных уравнений даффузш допускают реализацию быстрыми прямыми методами. В п. 4.4 приведены результаты численных экспериментов, проведенные для модельных входных данных применительно к Таганрогскому и Мобилсксму (США) заливам, которые дали результаты качественно согласующиеся с реально наблюдаемыми течениями, а также продемонстрировали образование устойчивых даэсипазивных структур -пятен повышенной канцалрации фигспланктша (метаболита) . В п . 4 . 5 " Вькхкстраллелшый алгоритм решения модельной задачи динамики фитопланктона на сугерпроцессоре" рассмотрена реализация алгоршма решения модельной задачи динамики фитопланктона в отсутсшие механизма экшкринного регултфсвания на МВС со структурной реализацией вычислений и нейрснсподобнсй организациа! вычислительного процесса, разработаннсй в НИИ Многопроцесссрньк Вычислигелшых Октем при Гаганрсгсксм радиотехническом университете. Был построен итерационный алгоритм совместного решзмя систем сеточных уравнений, аппроксимирующих модельную систему уравнений для концентрации биогатного воцес-тва и фитшланктсна который продемшстрирсвал приемлемую эффзоивность использования оборудования.

Основные результаты и выводы . 1. Для п — мерных (в 5 3 ) параболических и шперболических уравнений построены двухкомпсналные схемы : леремашых направлений (п = 3) и фактсриэованные ( п > 3 ), применимые , по сравнению с сдакксмпснэяными схемами, 15м менее жестких ограничениях, а стоке аддшикные схемы, имеющие в криволинейных координатах лучшие дю сравнению с лжальнскиншерными схемами, сцзяда скорости сходимости . В случае, когда переменные двумерных разюсшых задач разделяются, схэ-зы допускают реализацию быстрыми прямыми методами с затратами операций не более чем

о(тЧ "к^р^) операций, где N — характерное число узлов сетки по одному из направлатий.

2 . Для мнсгспрсцессорных вычислительных снстш (МВС) о&цш архигапуры с универсально! и жесткими (типа "куб 'Матрица", "линейка") структурами связей между процессорами построены экономичные в смысле суммарных временных затрат алгоритмы быстрых прямых методов решения двумерных сеточных аллигаичеошх уравнашй: циклической редукции ( СК)< разложения по базису ( ГА )» а также их комбинации (ГАСИ(1), где I -число шагов редукции). Для набора параметре® (1Ч,р,к), где р- количество процессоров, к -параметр слносигельнсй производительности , ^—^ а ' 1 а ' 1 о 'хЧ5актеГНЬ1е времена соответственно выполнения арифметической операции и операции обмена одним словом между процессорами, определены области эффективности построенных алгоргамов для реальных сеток и в ширсксм даапаэсне значений р и к, , схватывающая обширные классы совремшных МВС.

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

N < р < N ^ и большего числа ^ 2 р < N ^ процессоров . Установлено, что в целом для случая неразделякщихся переменных наиболее экономичными являются параллельные алгоритмы , базирующиеся на однсксмтснешных ехз-их расщшлзтия для случаев, относительно малого и умеренного числа процессоров. Для разделяющихся пфеменных наиболее экономичными являются алгоршмы , использующие двухкемпонешные схемы расщепления и (ькярые прямые методы, преимущество которых становится существатным при переходе отуниверсалшойк жалкой коммутации и от относительно малого к умеренному числу процессоров.

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

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

1. Nicolaeyew LA.,. Sukhinov A.I. Symm^rizied difference schemes for solving multidimensional partial differential equations on array computers .//Proc. of The IV-th IMACS International Symposium on Computer Methods for Partial Differential Equations , USA, Befclefchem, 1981, pp. 239-241.

2. Сухинсв А.И. Лскально-даум^рные схемы для решения мнсгсмерньах параболических уравнений на вычислительных системах матричного типа. //Известия вузов, Математика .-

3. Сухинж А.И. Об аппроксимации трехмерного уравнаэдя тепясжрсвсиносги лскалию-двумериыми схемами в цилиндрических и сферических координатах. //Известия вузов , Математика .-1987, №8.-с. 66-74.

4 Николаев И.А., Сухинсв А.И. Аддашвные схемы для моделирования трехмерных уравнений тшлспроводности в цилиншричеашх и сферических координатах . //Дифференциальные уравнения.-1987, т. 23 ,№ 12.- с. 2122-2132 .

5. Сухинсв А.И.,. Овчаренко. О.И Об алгоритмах решения трехмерного уравнения тшшятрсводаосштмнсгароцессорньах системах.// Электронное моделирование - 1988, №1.-с. 22-25.

6. Сухинсв А.И. Реализация мсдафицированнаго штеремадао-треугольисго метода для задач ттяопрсвсдаости и филырашм.//Вычислшелшые системы и алгсршмы. Ростш-на-Дону: изднво РГУ.-1985с. 52-59.

7. Николаев ИА, Сухинсв А.И., Харика О.Д. О распараллеливании треугольных итерационных методов на слециализирсванной вычислительной системе.//Автоматика и телемеханика .-1986, № 6.- с. 135-142 .

8. Оухинсв А.И., Овчараяоо. О.И. Параллельный алгсршм мегсда циклически редукции для решения сеточных эллиптических уравнений . I Всесоюеиая кснффенвдя "Проблемы создания супер-ЭВМ ", суперсистем и эффасшвность их прнмакния ", Тезисы докладов, ч. 2 , Минск - 1987.-е. 51-52 .

9. Сухинсв. А И. Л<жашйо-де)мер№1е схемы для аппроксимации уравнения гатло-прсводносш в криволинейных координагах.//Труцы Школы - семинара по комплексам прарамм математической физики. Вычислительные технологии, т. 1, часть 2, Новосибирск, ИВТ СО РАН.-1992.- с. 303-312.

10. Сухинсв А.И. Теорема единственности для системы уравнений динамики фитопланктона. //Численные методы механики сплошной среды. Тезисы докладов IV Всероссийской школы, Красноярск,-1992.- с . 37-38.

11. Сухинсв АИ., Васильев B.C. Применение алгоритмов построения кваэнепшмальных сетш для областей сложной формы. // Там же, с. 100-101.

12. Сухинсв А.И., Васильев. B.C. Гидродинамическая модель мелководных прогяжш-ных водоемов и ее численная реализация. //.Алгебра и анализ. Тезисы докладов международной научней конференции, чаль 2, Казань.- 1994 .-с. 127.

13. Sukbínov А. I. , Babenko L К. Parallel realisation of the fast direct methods ftr solving medí elliptic equatkns.//Proc. The 11-th Sympcáum en Supennkrocomputer and Microprocessor implications. Budapeá., Htmgaiy.-1994 , v. 1 140-149 pp.

1984 , M911.- c. 4553.