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

МИНИСТЕРСТВО СВЯЗИ СССР Московский ордена Трудового Красного Знамени институт связи

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

Шишкина Ольга Викторовна

УДК 681.324

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

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

" комплексы, системы и сети .

Автореферат, диссертации на соискание ученой-'степени кандидата технических паук

Москва 1990

У А;

Работа выполнена на кафедре вычислительной техники и управляющих систем Московского ордена Трудового Красного Знамени института связи.

Научный руководитель - доктор технических наук, профессор Э.В.Евреинов.

Официальные -оппоненты -доктор технических наук, профессор С.Д.Пашкеев,

- кандидат технических наук, -' доцент Н.И.Дзегеленох.

Еедущая организация - Институт проблем моделирования в энергетике АН УССР.

Защита.диссертации состоится " ^ " QtdJKfix 1990 г. • в /fT" *-"часов на заседании специализированного совета - К 118.06.02 в -Московском ордена Трудового Красного Знамени институте'связи по адресу: ШС24,-~г.Москва,._Е-24, Авиамо-~ торная ул., -д. 8а. "

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

Автореферат разослан " Ш-iUCoL. 1990 г.

Учеши секретарь" - -

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

v _ Е.В.Демина

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

Среди перспективных архитектурных концепций построения высокоэффективных параллельных вычислительных средств важное место занимает концепция -вычислительных систем " (ВС) с программируемой структурой, предложенная З.В.Евреиновым. Построение таких ПС основано на принципах параллельности выполнения" операций, конструктивной однородности и програкмируемостк структуры.Вычислительная система с программируемо!" структурой представляет собо? совокупность элементарных кашш (%), соединенных регулярно!;,программно настраиваемой сетью сргзи.-

Наряду с созданием архитектуры ЕС необходимо такте разработать быстрые и э(тг>.кт::гные параллельные алгоритмы решения сложных научных и технических задач.Исследования в этой области стали особенно актуальная» с появлением разнообразных параллельных вычислительных средств, и здесь важное место занимает проблема построения быстрых и элективных параллельных алгоритмов решен::?; сложных сильносвязкых задач, т.е. таких, при реализации которых требуется интенсивный обмен информацией меяду Ш в ВС.

'¿.ель работы. Выработка рекомендаций по архитектур« и структуре ВС на основе анализа сложных сильносвягзных задач и глетолов. их решензя; разработка- быстрых и элективных методйв параллельного решения слоят« сильносвязных задач на.ВС с программируемой структурой; исследование и разработка параллельных алгоритмов решения модельных сложных сильносвязных задач и оценка их качества при. реализации на ВС типа ¡/нкронронессорной внчислигелвной системы МККРОС, созданной на базе мини- и ьикроЭБМ семейства ".Электроника',' 'Методы исследования. Б работе используются методы теории вычислительных систем, численные методы решения задач математической г|изики и линейной алгебры, методы теории разностных схем и статистического моделирования.

Новнэ научные результаты. На основе анализа сложных сильносвязных задач, являете« т-р&ег.ыки задачам математической физики, и методов их решения г?. -угокекы окгашыаге физические структуры

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

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

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

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

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

Построены параллельные алгоритмы решения на БС с программиру-

емой структурой модельных сложных сильносвязных задач (разностной задачи Дирихле для уравнения Пуассона и разностной первой краевой задачи для одномерного уравнения теплопроводности) на базе методов решения по явной схеме, Фурье, редукции, прогонки, дробных шагов, простой итерации, Якоби, Ричардсона, верхней релаксации, Зейделя, попеременно-треугольного, попеременно-треугольного с чебшевским набором итерационных параметров, переменных направлений.

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

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

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

Алробашя работы. Основные положения и результаты работы докладывались на ХШ Всесоюзной научной сессии, посвященной Дню радио (Москва, -1988, май), на Республиканской научно-технической конференции "Вопросы разработки вычислительной техники" (Кишинев, 1989, май),на Третьем региональном семинаре СО АН СССР и Сибирской .территориальной группы" Советского национального комитета IMACS (Улан-Удэ, 1989, июль), на ЮГУ областной научно-технической конференции, посвященной 60-и годовщине образования СССР и Дню радио (Новосибирск, 1982, май), на научно-технических конференциях профессорско-преподавательского состава МИС (I988-I9S0).

Публикации. По материалам диссертации опубликованы 12 научных работ.

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, трех приложений. Содержит 135 страниц машинописного текста, 18 таблиц, 28 рисунков, список литературы из 105 наименований.

Основные долоаения. внноотаив на защиту. Для решения одномерных сложных сильносвязных задач математической физики метода!,и Якоби, Ричардсона, простой итерации оптимальными являются струк-/рн ВС типа "линейка", двумерных - структуры типа "решетка". Ре-

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

Выведенные расчетные формулы временных затрат базовой К! на реализацию параллельных алгоритмов, полученных при естественном вложении алгоритмов решения сложных снльносвязных зарач в структуру ВС, позволяют упорядочить разработанные параллельные алгоритмы в порядке возрастания временных затрат К! на их реализацию следующим образом : алгоритм распараллеливания прогонки, параллельные алгоритмы методов £урье, Ричардсона, попеременно-треугольного с чебышевским набором ' итерационных параметров, верхней релаксации, переменных направлений, попеременно-треугольного, решения по явной схеме, простой итерации, Зейделя.

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

СОДЕИСАШЕ РАБОТЫ .

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

В первой главе рассмотрены вопросы выбора показателей качества параллельного алгоритма решения слогсной задачи на ВС; показана связь качества параллельного алгоритма со структурой ВС. -Описаны модельные сложные сильносвявные задачи и структура базовой ~ВС ЫИКРОС, на которой реализуются параллельные алгоритмы решения"этих задач. Разработан алгоритм выделения подсистем из ВС с- программируемой структурой для обеспечешшгмультйпрограмшого рекима функционирования ЕС при решении слонных сильносвязных задач.

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

Кроме времени реализации используется еще один показатель качества параллельного алгоритма. Величина £ _ 100°/

называется яффективностью параллельного алгоритма и показывает,насколько хорошо алгоритм распараллеливается на большое число ветвей (подзадач для каждой ЭД). Среди показателей.качества параллельного алгоритма основным является время реализации. Существуют примеры, когда один параллельный алгоритм выигрывает по эффективности, но проигрывает по времени реализации у другого параллельного алгоритма решения той же задачи. В последующих главах, в частности, рассматривается параллельные алгоритмы, приводящие к следующим оценкам: эффективности метода решения по явной схеке и метода зонального разбиения решения разностной первой краевой задали для одномерного уравнения теплопроводности относятся как 97$ к С5,9%, тогда как временные затраты на их реализацию на двумерной ВС с программируемой структурой относятся как 835 к I.

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

Оценки временных затрат ЕС на вычисление и ка обмен информацией, между 2М для решения некоторой сложной задачи каким-либо методом зависят от следующих параметров ЕС: <Э - времени выполнения ЭЛ одной скалярной арифметической операции и 1? - времени обмена одним словом информации между соседними ЗМ в ЬС.

В качестве модельных сложных сильносвязных задач выбраны разностная задача Дирихле для уравнения Нуяссога и разностная первая краевая задача для одномерного уравнения теплопроводности. На примере первой модельной задачи выявляются особенности реше-_ ния на ВС с программируемой структурой эллиптических многомерных задач, а на примере второй - способы решения на ВС различных одномерных краевых задач, а также параболических дву- и трехмерных задач ввиду возможности сведения последних при помощи схемы дробных шагов к дву-, трехкратному решению задач* подобных краевой задаче для одномерного уравнения теплопроводности.

В первой модельной сложной сипьносвязной задаче требуется найти {^¿у}, 1=1,,,., N-1 у»/,...,^-^3 соотношений

г = Л...,Л/-/, у = /„..,- /V-

%,о • = = Л-..., -/V, = ^у "О, //.^

Для решения второй модельной сложной сильносвязной задачи используются две разностные схемы:явная и неявная. В первом случае требуется найти '/ V. . I £ Л/-/<=/,...17г, из системы /с к -1 а ь »

- _ - * £к

т - " - + т г ,

- 1 = л/-/, к=о,...,т-1} Ал/= у ; тг=.

' = и о (Ч&Л г=0,..., А/, ' во втором случае - из "системы

1" " - /I-1---,

■ г=Л'...,//'-■/, -С = С, 7--У, тт=

- К'1 < ((^1) V, ир1 * = ¿V-, 7--/,

. ^ ~ и0 (Ш, 1=0, ..., /V, ;

где - < обозначаег'номер временного слоя.

При решении второй модельной задачи по явной схеме, в отличие от решения по неявной схеме, шаг по времени (?") берется достаточно мелким, в соответствии с условием устойчивости явной схемы: 0,5Яг. Поэтому решать вторую модельную сложную сильносвязную задачу на ВС'с программируемой структурой выгоднее, как правило, по неявной схеме с точки зрения минимума временных затрат ВС на решение задачи.

Дяя построения и опенки качества параллельных алгоритмов решения на ВС сложных сплыюсвязннх задач рассматривается естественное вложение алгоритмов решения задач в структуру ВС, приводящее к эффективным, соответствующим методике крупноблочного распараллеливания, "параллельным алгоритмам. Естественным вложением алгоритма отыскания (по явным формулам или путем решения систем уравнений) вектора 11= в структуру ЕС, состотцек из

- - ¡"1 соединенных в цепочку ЭМ, является такая организация вычислений в ЕС, при которой ЗМ^> - элементарная машина с номером р ,

вектора

для кото-

, отыскивает те элементы лс^ рых i~ ¡-(i0 • Вторая модельная слокная сильносвяз-

ная задача решается fio времешщм слоям, начиная с первого. При " этом для нахождения искомого вектора ZC£ на /с -м временном слое рассматривается естественное вложение алгоритма отыскания вектора" И*- в структуру базовой ВС.

1 " | í

mP,tг Stt/Wf

1 "' i..... i

— Шp-i,t)

Рис.1. Значения у в точках В™ вычисляет ¿глр л

Для параллельного решения первой модельной задачи __пршзняет-ся следущее естественное вломите алгоритма решения в структуру " базовой ЕС: -вычислэшю всех элементов ' • искомой матрицы

для которых {£&-<)+<,...,#(),

выполняется ЗЛр.е}, - элементарной малиной с ивдексоМ (/>,£), " , I 40 /1 г (рис.1). Если процесс решения сложной силв-

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

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

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

Рассматривается ВС с программируемой структурой, состоящая из П. ЭЛ. На ВС поступает поток задач без приоритетов, являющихся сложными сильносвязными задачами. Распределения времени по-■ ступления и рангов задач являются равномерными. Задано соотношение между интенсивностью поступления задач и интенсивностью их .обслуживания в ВС.- Требуется организовать стохастически оптимальный мультипрограммный режим функционирования БС.

Показано, что параллельное решение сложных сильносвязных задач типа модельных целесообразно осуществлять на подсистемах с организацией структуры связей типа "решетка". Предложен быстрый ж достаточно эффективный алгоритм выделения таких подсистем в ВС. Смоделирована работа ЕС, состоящей из 64 3, соединенных по типу ."решетка", для случая раЕНо? интенсивности поступления задач и их обслуживания в ВС. Методом Монте-Карло получено распределение вероятности времени ожидания выполнения задачи.

Во второй главе строятся параллельные алгоритмы решения сложных сильносвязных задач типа модельных на основе известных численных методов: решения по явной схеме, Фурье, редукции, прогон-, ки, Якоби, простой итерации, Ричардсона, Зейделя, верхней релаксации, попеременно-треугольного, попеременно-треугольного с ■чебы-шевским набором итерационных параметров, переменных направлений.

Для.каждого из параллельных алгоритмов дано описание вычислительной работы элементарных машин при осуществлении решения сложных сильносвязных задач указанными методами на базовой ВС,- а также описан процесс обменных взаимодействий между Щ при естественном вложении: алгоритма в структуру ВС; приведаш &гз?оритмы вычислений ж схемы обменных взаимодействий между Ш.

Б тех случаях, когда параллельные алгоритмы, построенные на основе известных методов, являются неэффективными при реализации на базовой ВС (что объясняется нехватко? связей между Ж в ВС), указываются оптимальные структуры ВС, обеспечивающие минимум временных затрат ЕС на реализацию алгоритма и максимум эффективности параллельного алгоритма при отсутствии неиспользуемых связей между ЭМ.

Для каждого из методов получены оценки временных затрат 6п к эффективности 6Л при реализации параллельных алгоритмов этих методов на базовой ВС. Эти опенки зависят от числа неизвестных в задаче - для первой модельной слож.ой сильносвязноЯ задачи и Т> А/ для второй, модель ной задачи, от числа ЕМ в ВС, от параметров ЕС <о и V- , а также от точности ¿Г" получаемого решения. В частности, найдены следующие расчетные формулы для нахождения временных затрат базовой ЕС при решении сложных сильносвязных задач типа первой модельной задачи методами:

1) распараллеливания прогонки

дРпП + Чг^-О + зи^)*;

2) Фур1е -

3) Ричардсона -а...*

^ ¿п(£/д)Н г(Г1 п

ип ~ Юг ' г '

4) попеременно-треугольным с чебышевским набором итерационных па-

+ (П.л * Аг -2X3 С/г,

5) верхней релаксации

6) переменных направлений

пн ёп (11$) , -

7) попеременно-треугольным 2

С* Щг^ м^ь-о^б* л/

8) простой итерации

п. 71*-П

9) Зейделя

а^ И, ,-ъХ5ы6+г(п1+пл)»)

"я. /г1 *

В конце главы проводится сравнительный анализ построенных параллельных алгоритмов. Для 'числовых оценок качества алгоритмов рассматриваются две тестовые задачи. Одна из них является первой модельной задачей с параметром N =10£4, решаемой на ВС, состоящей из п = п,*пл ш, П-1 = <Чг , И = 4, 16, 64, ¿56, 1024.

Другой тестовой задачей выбрана вторая модельная задача с -параметрами Т = N =1024, решаемая на ЕС, состоящей из П. ЗМ, а =2, 4, 8, 16, 52. Обе задачи решаются с точностью . ¿^=10 на ВС о варьируемым параметром ^ =1, ДО, 100, 1000. Для этих тестовых модальных задач получены числовые оценки временных затрат и эффективности построенных и описанных ранее параллельных алгоритмов и приведены е соответствующих таблицах и графиках. В частности, на рис.2 приведены ^эс^ у^ фективности параллельных алго-

Екс.2. Эффективности параллельных алгоритмов решения тестовой первой модельной задачи на базовой Б2,= 100, кетодаик: 1)распарадлеливания прогонки; 2)бурье; 3)Р,: с,-'ЗЬгошро-кенво-треугольным с чебншевскЕЫ набором гов^ьдиошсс пара-Шатров; 5)верхней релаксацки; 6)переменных направлений; 7)по-пэрекэнно-треугольЕым; 8)простой итерации; 9)3ейделя

ритмов решения тестовой первой модельной сложной сильносвязнои задачи на базовой ВС с параметром ^¡<6 = 100. Параллельные алгоритмы на рисунке пронумерованы в порядке возрастания временных затрат базовой ВС на их реализацию. Отсюда видно, что эффективный параллельный алгоритм не всегда является быстрым; примером монет служить параллельный алгоритм метода простой итерации.

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

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

Метод зонального разбиения для систем трехточечных уравнений ■ вида Ьи1 - аиг =

-аи1ч + би1 - аии1 = /(- , 1=л'-г, -сии^ + ви^ , тъЬа/.

сводится к следующему. Сначала, не требуя обмена между 31, сводим систему к аналогичной,•но с разревенной правой частью, т.е. нулевой везде, кроме И -I точки. Затем за шагов находим решение полученной системы, на каадом шаге уменьшая вдвое количество ненулевых значений правой части.

Первый алгоритм метода зонального разбиения применим для ре. шения систем трехточечных уравнений на маломощных ЕС, т.е. на ВС с малым числом П- элементарных машин ( И ^ 16 ). При реализации этого алгоритма потребуются временные затраты базовой ВС, равные ^ = (п-1)Ъ.

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

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

.296

ся метод матричного зонального разбиения, для реализации которого на базовой ЕС при решении первой модельной сложной сильносвязной задачи потребуются временные-затраты БС, равные

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

Таблица I

Относительные временные затраты базовой ВС при решении тестовой первой модельной задачи на базовой ВС, 100

•Метод 4 16 64 256 1024

Матричного зона- I X х х т

льного разбиения X

Распараллеливания 21 30 29 26 7

прогонки

Фурье 22 40 .50 37 14

Ричардсона 1082 1006 721 373 69

Чебышевсюш попе- 402

ременно-треуголь- 216 577 596 214

ный

Верхней 3246 3018 2235 тт. 235

релаксации

Переменных направлений 2273 3622 4331 4694 1663

Попеременно- 3000 6533 9734 9909 3560

треугольный

Простой итерации, Зейделя 3,9-Ю5 3,8 -Ю5 2,9-Ю5 1,7-Ю5 3,4-Ю4

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

Таблица 2

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

- 4 - 8 16 32

I 2,80 2,34 2,05 1,93 2,20

10 2,81 2,36 2,09 2,06 2,48

100 2,85 2,49 2,43 2,67 2,95

1000 3,33 - 3,16 3,14 3,12 3,08

80

60-

40-

-го

оЗР у с„ ,/а

Кроке того, метод зонального разбиения выигрывает по эффективности у алгоритма распараллеливания прогонки и параллельного алгоритма метода Фурье. Таким образом, рассмотренные в главе Ш параллельные алгоритмы нового метода зонального разбиения для параллельного решения сложных сильносвязных задач типа модельных

(разностных эллиптических, параболических и _гиперболических задач) на вычислительных системах с программируемой структурой являются наиболее"быстрыми и-зффективными из построенных в работе параллельных алгоритмов численных методов решения сложных сильносвязных задач.

-г ч »

1в

ъз.

ЧУ/б = 1

туб =т у/б=то

п ' ~

Рис.3. Эффективность параллельного алгоритма решения тестово;; второй модельной задачи методом зонального разбиения на базовой ЪС-

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

Смоделирована работа базовой ВС, состоящей из П. ЗМ, при решении тестовой первой модельной сложной сильносвязной задачи ( П. =£, 4 ) и тестовой второй модельной задачи ('П. =1, 2., 4, 81 Приведены экспериментальные оценки временных затрат базовой ВС на вычисление решения первой и второй тестовых задач указанного типа при помощи метода зонального разбиения для систем трехточечных уравнений и метода матричного зонального разбиения. Лия эгих задач вычислены погрешности получаемых методом зонального разбиения решений.

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

, ЗАНИЖЕНИЕ

Основные результаты диссертационной работы заключаются в следующем.

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

2. Разработаны параллельные аналоги прямых и итерационных численных методов решения сложных сильносвязных задач, являющихся разностными краевыми задачами математической физики. Построены параллельные алгоритмы решения модельных сложных сильносвязннх задач (разностной задачи Дирихле для уравнения Пуассона и разностной первой краевой задачи для одномерного ураьг-1-*ч;! теплопроводности) на базе методов: решения по явной схеме, «.д^увпв*, прогонки, дробных шагов, простой итерации, Яко'би, Ричардсона, Зейделя, верхней релаксации, попеременно-треугольного, попеременно-треугольного с чебышевсккм набором итерационных параметров, переменных направлений.

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

4. Предложен параллельный метод матричного зонального разбиения для решетя многомерных сложных сильносвязных задач на ЕС с программируемой структурой, позволяющий сократить временные затраты ВС более чем в 2,72 раза по сравнению с комбинированным методом 5у-рье и прогонки, являющимся наиболее быстрым из ранее известных.

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

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

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

1. Хорошевская О.В. Сеточные методы параллельного решения уравнения теплопроводности на однородной вычислительной системе // ХШ Всесоюзная научная сессия, посвященная Дно радио: Тез.докл.-М.: Радио и связь, 1988.- 4.1.- С.76.

2. Хорошевская-О.В. Организация дискретного быстрого преобразования £урье на параллельных вычислительных системах // Электрон, моделирование.- 1989.- Т.II, 1®.- С.106-107.

. 3. Хорошевская О.В. Параллельный многосеточный метод решения первой краевой задачи уравнения теплопроводности на однородных вычислительных системах// Электрон, моделирование.- 1989.- Т.II,£6.

- С. 73-77.

4, Хорошевская О.В. Сеточные методы решения уравнения теплопроводности на однородной вычислительной системе / Моск.ин-т свд-зи.-М. ,1988.- 37 с.-Деп. в ЦНТИ "Информсвязь" 5.12.88, М443-св88.

296

5. Шишкина O.B. Метод матричного аинального разбиения для параллельного решения разностных эллиптических задач // Третий региональный семинар СО АН СССР и Сибирской территориальной группы Советского национального комитета IMACS : Тез.докл.- Улан-Удэ, 1989.

- С.48.

6. Шишкина О.В. Параллельный многосеточннй метод решения уравнения теплопроводности // Третий региональный семинар СО АН СССР и Сибирской территориальной группы Советского национального комитета IMACS : Тез.докл.- Улан-Удэ, 1989.- С.47.

7. Шишкина О.В. Программные средства организации мультипрограммного режима функционирования однородных вычислительных систем для решения краевнх задач математической физики // Республ. каучно-

- техн. конференция "Вопросы разработки вычислительной техники": Тез. докл.- Кишинев, 1989,- C.S6-97. -

8. Шишкина О.В. Анализ параллельных: алгоритмов решения разностных задач на вычислительных системах с программируемой структурой // "Районные распределенные вычислительные системы": Тез. докл.- М. ,1990.

9. Шишкина О.В. Разработка программных средств фуккционирова-. кия вычислительных систем с программируемой структурой для решения

. сложных сильносвязных задач // "Районные распределенные вычисли--тельные системы."Тез.докл.- М., 1990.

10.'Шишкина О.В..Параллельный метод зонального разбиения для" решения на однородных вычислительных системах"параболических задач на примере уравнения теплопроводности // Электрон, моделирование.-1990.- Т. 12, .V.;.

11. Шишкина О.В. Метод зонального.разбиения для решения на однородных вычислительных системах" разностной" задачи Дирихле для уравнения Пуассона V/ Электрон, моделирование.- 1990,- Т. 12, JC5.

. 12.-Шишкина О.В. Организация мультипрограммного режима функционирования однородных вычислительных систем для решения краевнх . задач математической физики // Методы к средства параллельной od- -работки данных в системах связи / Моск. ин-т. связи.- 1,1/, 1989.5 е.- Деп. в ЦНТИ "Информсвязь" "9.4.90, № 1671

Подписано в печать 3I.05.90ri Л-38184. Формат"60x84/16. Печать офсетная. Объем 1,0 усл.п.л. Тир.100 sks. Заказ 296. Бесплатно.

Отдел оперативной полиграфии, ШС. Москва, ул. Азвпвтоторная, 8.