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



ШСКОВСКИй ордона ЛЕНИНА л ордена ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ ЭНЕРГЕТИЧЕСКИЙ ИШТЙТУТ

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

ШАМАЕВА Охьга Юрьевна

УЖ 681.324.06:008.92

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

Специальность: 05.13.13 - "Взлезли тель низ шшшг, комплекса,

сястекя п сети"

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

Мостаа - 1990

Работа вклолнена на кафедре Прикладной матешткки toсковского ордена Ленина и ордена Октябрьской Револзцш энергетического института.

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

Официальные оппоненты: д.т.н., профессор И.В. Кузина,

к. т.н., нач. ОКБ "Мзркурий" М.А. 1востанцев

Ведущая организация: Институт Кибернетики АН УССР

Защита диссертации состоится " iZ " октяЗрЛ 1990 в аудитории час. 00 мин. на заседаЕ

Специализированного Совета K.053.I6.09 Московского opi Ленина * ордена Октябрьской Вэвохщии энергетического института.

Отзыва в двух экземплярах, заверенные печатью, црс присылать, по адресу: 105835, ГСП, Москва, Е-250, Красш зарменвая, 14, Ученый Совет ЮИ.

С диссертацией иохно ознакомиться в библиотеке ДО]

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

Учений секретарь Специализированного Совета

К.053.16.09 к.т.н., доцент ' А.Ф. Бочко

¡^.-viTEiiSiS

ОБЩАЯ ХАРАКТЕР® ТИКА РАБОТЫ •faef^flihqctb тема. Характерной особенностью совра.'.йеной

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

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

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

В связи с этим актуальными является исследования, направ-:енные на разработку методов ж алгоритмов параллельных вычис-:ений, использущих принципы декомпозиции; организацию эффективных процессов реализации параллельных алгоритмов на ПВС : ЭВМ; изучение вопросов эффективности методов в зависимости 1 параметров задачи (размерности -7/, объема данных - О,•чис-а подзадач - р, числа связей ыэлду подзадачами -Л/с и др.), араметров ПВС (числа вычислителей, их производительности, бъема оперативной памяти, структуры связей цэаду внчислите-ями и т.п.) и моделей вычислений.

Дель работы. Разработка и исследование иэтода параллель-ых вычислений на основе диакоптических принципов докомпозл-ии, построение параллельных алгоритмов и создание програм-

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

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

- исследование обжих и дпакоптических принципов декомпозиции в решении слозных задач л их классификация;

- формализация даакоптических процессов декомпозиции и композиции на языке топологии и, как результат, представление задачи расчета по частям сложных систем, моделируемых линейными сетями ила СЛАУ, на языке алгебраических диаграмм;

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

- разработка параллельного метода реиения задач на основе дкакоптики - параллельного метода диакоптики /ПЩ/; его алгоритмическая и программная реализации;

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

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

Научная новизна.

Разработан г формально обоснован параллельный метод решения задач расчета класса сложных систем, моделируемых ли-" найашш сетями и/или СЛАУ большой размерности с Ш коэффициентов, на основе диакоптики.

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

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

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

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

Практическая цзнпооть

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

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

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

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

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

Реализация результатов доследований. Диссертационная работа является составной частью ряда НИР по исследованию архитектур ПВЗ и разработке штематичзсхого обеспечении для организации параллельных вычислений, выполненных при участии автора на кафедре Прикладной математики ЮН согласно плану работ по развитию BD ЗВ'-i, приказу Минвуза СССР ü 1238 от 29.12.81. и координационному плану АН СССР 1.12.7.1., а также по договорам о научно-техническом содружестве: мзжду МЭИ и ЮТИ (г. Новосибирск) и между МЭИ и НИЧ МЭИС.

Результаты диссертационной работы внедрены и используются в ряде организаций, а такке в учебном процессе МЭИ, что подтверждается соответствующий акraier.

Аггообакия работы. Отдельные результаты работы докладывалась и обсуждались на: П Всесоюзной школе молодых ученых и специалистов по проблемам теории систем и еа приложениям (Kay нас, 1978 г.); республиканском семинаре "Параллельные шшины и параллельная математика" (Киев, 1978 г.); П, У, Ш, М Всесоюзных семинарах "Паратлельное программирование и высокопроизводительные структуры" (Киев, 1978 г., 1982 г., 1986 г., Т988 г.); 17 и У Всесоюзных школах-семинарах "Распараллеливание обработки информации" (Львов, 1933 г., 1985 г.); ХХХШ, 2ХХЛП Всесоюзных научных сессиях, посвященных Дню Радио (Москва, 1978 г., 1983 г.); Всесоюзном научно-техническом совещании "Микропроцессорные средства вычислительной техники в системах связи и управления (Рига, 1984 г.); Всесоюзной кодере нции "Применение микропроцессорных вычислительных систем доя управления технологическими процессами" (Смоленск, ' 1979 г.); научно-технической конференции прсфессорско-црепо-' давательского состава и'сотрудников НИЧ МЭИС (Иэсква, 1984 г.

Научные публикации. Результаты исследований отражена в 15-ти печатных работах и 5-ти'отчетах по НИР.

Структура и объем работы. Диссертационная работа состой из введения, пяти глав, заключения, списка литературы из 152

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

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава посвящена исследованию свойств, методов и алгоритмов решения задач большой размерности /ЗБР/.

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

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

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

В качестве характерных моделей слабосвязашшх ЗБР исследуются задачи реиения СЛАУ и обращения матриц, к решению которых сводится порядка ЧЬ% всех расчетных математических задач. Матрицы коэффициентов таких задач являются разреженным и, в ряде случаев, плохообусловленныш.

Определены пути повышения эффективности вычислений при решении слабосвязэнных ЗБР, ориентированные, как на использо-

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

Проанализированы понятия декомпозиция и Декомпозиционный метод и случаи целесообразного их применения к решению ЗБР. Определена классификация методов декомпозиции по двум выделенным признакам: объекту и принципам декомпозиции. Установлено, что диапоктика^ является наиболее общим методом декомпозиции при реаении ЗБР, возникающих при анализе, исследовании и расчете сложных систем различной физической природы.

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

Методы диакоптики предполагают переход посредством декомпозиции СМ от исходной систем 5 к расчлененной системе Х> состоящей из совокупности подсистем = 1,р] менызей размерности и системы связи Зс этих подсистем (диапоктический принцип декомпозиции). Расчлененная система доказывается "проще" с точки зрения формирования математической модели /ММ/ и организации процессов исследования и расчета. Это соответствует переходу от исходной задачи 3 анализа и расчета системы 3 к задаче 3 для расчлененной системы £ , состоящей из совокупности подзадач {з;,, ¿= 1,р] расчета подсистем , С = 1,р] незадачи Зс для системы связи ¿с. Переход от решения Р задачи 3 к решению Р задачи 3 осуществляется путем "объединения" решений [Р;, I.р^ и Рс (диакопткческий принцип композиции)

£ декомпозиция £ с>

1 СМ | _ /I/

3 3 =<{ 31, С = 1,р]. Зс>

{ композиция 1 __

Р "решения- Р =<[Р£. ¿ = 1.р]. Рс>

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

Т7-

'Крон Г. Исследование сложных систем по частям - диакоптика. - М.: Науха. - 1972. - С. 544.

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

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

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

* « '1 _ 1

* 4 к У/, £

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

Расчленение СМ системы в соответствии с принципами диакоптики эквивалентно преобразованию ее ММ к следующему виду:

I

V/.

Я с X X _ 3

с* Ъс Хс £>с

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

структуру системы связи подсистем, С = { О,I - I}, с/гте = =.ЛхЛс, где-Л с - общее число связей меяду подсистемами; С2'-транспонированная матрица С; 2)с - диагональная матрица "весов" связей, е11т.2) с х .Лс; Хс - вектор, дополнительных не-

известных певе!ЕНЕ1К в ветвях системы связи, сЬЬт Хс =Лс; Вс - вектор воздействий, приложенных к ветвям связи, о1'ип7 Вс ■

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

Формальная постановка задачи анализа и расчета систем методами диакоптики опирается на исследование и преобразование СМ этих систем и осуществлена с помощь» построения известных в алгебраической топологии коммутативных диаграмм шрфизмов линейных пространств (Ш), порожденных связным одномерным ориентированным симшшциальным комплексом К, представлящим СМ исходной системы £, и несвязным комплексом К для расчлененной системы ¿Г. Алгебраическая диаграмма вида:

О'-*-Нт(К)---►С1(К)----По (К)-«-0

А *

г

¿1

1 1 / Iх- I /.

»/г /2/

1 -к £

О-«-Нд-СЮ—-С|(К) ———-По'ск)--О

связывает с помощью линейных отображений / , ¿> и Л следующие Ш: Ст[(К) - ЛП целей над полем комплексных чисел, порожденное множеством одномерных симплексов комплекса К; Н^(К) - ЛП циклов комиекса К; По(К) - ЛП образов комплекса К, изоморфное пространству независимых пар узлов комплекса К; н£(К), С^К) и По (К) - двойственные ЛП по отношения к Н-^СЮ, С-^СК) и По(К). В электротехнической интерпретации указанные ЛП имеют следущий смысл: ¿бН^ОС) (£6 Н|(К)) - ЛП контурных токов (напряжений)

ОёС^-СЮ (УбС^ОС)) - ЛП токов (напряжений) в ветвях

16 По(К) (Её По*(Ю) - ЛП узловых токов (напряжений)

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

Лдны: К - одномерный ориентированный симплициалный комплекс, Ш, определенные на К (указаны выше) и удовлетворяющие алгебраической диаграмме /2/. Необходимо определить множество элементов У<£ ^ (К) и ^£С1(К), таких, что , 6У--1.

Строится решение с. помощью диаграммы /2/ в виде:

э = Л СЮ * Л (') =¿-'6 * Г/z

V-- /л (I) > /V ^ = ,

доказывается, что оно искомое и единственное. Дается штрзчшй вариант задачи и ее репения.

Диакоптические принцип декомпозиция и ко;д:огнц:п фор:плъ-но обосновнвавтся как результат отображения алгебраических диаграмм. С этой целыэ "левой" части схеьзх /I/ со поставляется алгебраическая диаграмма /2/, построенная для связного комплекса К

Д =<Hj(K), CjÜC), По (К); L > а для "правой" - алгебраическая диаграмма /2/ для несвязного комплекса К

Д=<Н1(К), CjOC), По(К);Г> и задается морфпзм

Ч : Д — Л

соответствующий существованию дшнеЗннг отображений:

Rj-: Hj(K) -- Нд-СК); R : CjÜC) —^Gj(K); Po: По (К)—-Но QO,

который индуцирует линейную задачу 3 для К на диаграмме 'Д.

В результате формируется дзоЗная диаграммная схема, :s:-лящаяся модификацией дзойаой алгебраической диаграмма Рота"'.

В работе вводятся определения разрезания (г), узлового (-/- у) и контурного (■{:<) расчленений комплекса К как разновидности сишлищального отображения комплекса К в К. IIa основе введенных расчленений строятся соответствуйте им дзоГипе диаграммные схемы, явлшхдаеся средством формального получения решения Р задачи 3 через ресение Р задачи "3 при определенном расчленении связного комплекса в несвязный.

На рис. I приведена двойная диаграммная схема, построенная для узлового расчленения /у: К->К, с помощью которой фор-шльно получено решение исходной задачи 3 черзз решим индуцированной задачи 3 в виде:

У = R"1^ = <1 R''S¿7&

V = R й3 Г + R* 1} Х;1г ж доказано, что ренение задачи 3 для комплекса К мол:ет быть

Vjlotk J.P. Же. bv&c/ity OLjzom mcttcct tf

tiatinq. // Ръоалс/олд ¿¿¿л tfsac/zyw

У dcS&nczA. - V 4if Ws?, /3SS. SV?-¿со.

получено через реаенпе задачи 3 для комплекса К.

Осуществлено построение категорий сшгалициальных комплексов и даоЗкюс а.тебраическзх диаграмм с целью представления процессов аффективного расчленения комплекса К в К как результата композиции корфиз«!Св соответствующих категорий.

О

\

\

Ик'х)

¿1

л

Н<(зс)

¿

£' I

б 6 Лг.

V

С< (ж)

С?(х)\

я?

V

КОС)

(ЯУ я*

с*(х)

л1

н;ос)

Есс. I. -

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

дов ж алгоритмов расчета указанного масса систем л паз-чапо основном методом диакоптиля /0:'Л/.

Определены правила фор!.яровангл коьяонент фаг.торнсогзп-ных выражений. исходя из сетевого представления и 'из матс:.атз-ческой модели систем. Аналогично форглулпруется 0;."Д и его параллельно-последовательные модификации.

Пусть имеем класс систем ,1, уравнения состояния которых в символической форме имеют вид АХ = В, где А - Р.5 поопТагентов, описыващая систему ^ размерности Лг и обладавшая спл-мэтричной структурой относительно, в обцем случае, плотно заполненных диагональных блоков. Элементами матрицы А мэгут быть функции времени, операторы дифференцирования и интегрирования. Система расчленена на р подсистем с обеим числом -'/'с и вектором Бесов 3)о связей мовду ними и уразленгпщ состояния либо! из них в вида А^Х-^ B¿ . Матричное выражение для определения вектора X в соответствии с ОЩ имеет вид:

= (5 -'БС СБе + С " Ъ СУ1 С'Ъ) В, /3/

тае ъ - сиа%[к'1 , Ар'] ? I)-.//*//, а''л; М^п^Щ'

С - матрица связей подсистем, построенная как матрица ¿ац::дгн-' ций ориентированного графа без потель на ■Аг вешипах и ребрах.

Для систем с об:дпм возбуждением матричное заражение метода диакогггики шлее? вид^ _

X = ( Ъ-ЪоЪе.С^Ъ) (В - ЪС2>С оС) /4/

где 6 - 6 + 6с - вектор внутреннего эозбундекня система £ - вектор внутреннего возбуздения расчлененной систем 6$ - воктор внутреннего возбуждения в системо связи |':с; Р - { Р^ гг>..Рр Рс ~ матрица, описывающая структуру 1 -ой подспстемы, построенная как усеченная матрица инциденций ориентированного графа_без петель па веражах и всех ветвях ¿-ой подсистемы; Ъ^ - (+ С-'ЪСУ; X - диагональная матрица весов всех ветзей расчлененной системы £ без ветгей системы связи ¿с.

Анализ выражений /3/ и /4/ с целью выявления возможностей максимального распарал-Ч-зллвания процесса его вычисления, позволил разработать параллельно-последовательные модификации мзтодов диаяоптнки, объединенные и названные по цели модификации пмд..

Этапы ПЦЦ для расчета систеи с внешним воздействием:

1. Построение К.1 расчлененной сложной система:

- составление совокупности угавнений состояния для подсистем

А¿¿¿= В:

- описание систоьн связи подсистем с помощью структурной матрицы связей С и штрицы "весов" связей Ъс.

2. Фокдроваппе для всех подсистем матриц связей С;.

С -(Ср С2,..., Ср] и векторов внешних воздействий B¿

^ в2"--» ^} ^ . _ "

3. Независимое вычисление матриц A¿ для всех ¿.= 1,р. •

4. Независимое вычпслешге матриц Асе = С ^Ъ^ С для всех I =17р.

5. Вычисление штрицы 1)с = ( 1>с.+.£ Асе

6. Независимое вычисление штриц 2)-1= С Ъс для всех

[ = Г'р г ±

7. Независимое вычисление штриц \ = С;. для всех ¿=1,р.

8. Независимое вычисление штриц • = Г Ц-1 Ю-'2 ¿-^У

— ^ I 4 ^ / т, г • •

для всех ¿,у = 1,р. (. - I),; -О- , __ •

9. Независимое вычисление векторов = для всех ¿=1,р.

Д.тя расчета систем с общим возбуждением этапы 2 и 9 в ШЩ дополняются следующими вычислениями:

2. йормпроваяае векторов общего воздействия ва каждую подси- ' стему в'фр В^..., Вр})где В-= В;- В; = В;- £ = 1,р._'

9. Независимое вычисление векторов X" = Ъ1&с для всех ¿=1,р. 9'. Независимое вычисление векторов 1; = Ау"X"Для всех £ =1,р.

ПЩ дает возможность получения обратной штрицы всех системы по частям - блокам } ¿,у = 1,р. Изменяя вектор В возйшшо исследовать поведение слокной системы.

Для получе1шя численных оценок разработанного метода в работе вводятся характеристики трудоемкостей вычисления -Т = '/У^р, представления данных - О =У/С-^р, )

и реализации алгоритма, построенного на основе 1Щ (аналог временной вычислительной сложности программ), которые исследуются относительно трех моделей вычислений:

- модель М1 - последовательные вычисления матричного выражения для СВД на некоторой абстрактной ЭВМ, состоящей из злеи.'^--тарного вычислителя /ЭВ/ и памяти с произвольным доступом;

- модель М2 - асинхронное вычисление всех этапов ПМД в классе

ПВС, состоящих из.произвольного числа 03, снаб.-зпнкх памятью;

- модель 1.!3 - последовательное выполнение параллельных вычислений на ЭБМ, состоящей из ЭЗ и памяти.

В работе также введены и исследозагщ характеристики эи$с::-тивностей всех моделей вычислений в форме зависимостей

§ = (-А', Р, сС ) где = - коэффициент связанности подсистем;л:-"г'с'-/р -

- среднее значение числа внешних связей ¿-ой подсистемы.

В результате доследования моделей, во-первых, доказала оТ>— фектизность методов диакоптикн (ОВД и 1ГДД) для решения слабосвязанных задач как на одной ЭЕМ, так и на ПВД; зо-вторцх, сформулированы критерии оффективной применимости моделей вычпсленд2, определякцие связь параметров решаемой задачи с плрамзтра-.гд ПВС; в-третьих, разработаны алгоритмы взаимной настройки задачд и ПВС, позволяющие, например, для заданных размерности задачи и параметров ПВС определить допустимые диапазоны изменения значений параметров р и Л'с, при которых возможно достижение наибольшей (либо требуемой) эффективности.

Исследования модельных характеристик осуществлялись с помощью пакета прикладных программ математической оптампзагтг'. ЕиИКА на ПЭЕМ 1ВГ.1 РС; алгоритмы взаимной настройся для моделей Ж, М2 и МЗ реализованы на языке Си в среде МЗ-ЕО? Собьем текста программа - 5 кб).

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

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

Разработаны и экспериментально исследованы в рамках опера-пдонно-матричной технологии и СПП на базе монитора параллельной обработки для ВС ЭВМ последовательный и параллельный программные комплексы на языке ПД/1 с использозанием введенных шкрооаераторов (ПОСЛАТЬ) и АЕСЗГСЕ (ПОЛУЧИТЬ) для орга-

низации обшнпых взаимодействий.

С помощью асннхронно-шкроконвейерной технологии разрабо-

таг.а г. рзалязозлна в СПП па основа модели асинхронной вычисли-телгг.сг сети (АБС) АХЙ-програыг.и рекения задач ГОИ. Средства С7х:,:::о^1>ункцг:оцаль':ой иэтодля использованы для представления процессов рс^эпия задач методами длакоятики в форме функцио-пальццх схом, а такг.е сценок сложности последних.

Прздлогена система показателей сложности параллельных программ /ПП/, включающая группу статических показателей сложно. проектирования ЛП (сложность модулей, структурная сложное": а др.) и грушу динамических показателей сложности функ-цаок,..'рс22пия ПП (временная, программная и информационная вычис-лителылдо сложности и др.). По этой системе оценены разработанное ПП. Определены границы эффективного использования шделеА и спетом параллельного программирования для реализации ШДЦ.

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

В пятой главе исследованы вопросы организации параллельных вычисления при реализации ШД в ПВО различных структур, в которых кокплексирование осуществляется на уровне внешней памяти и предполагает разделение во времзни как процессов приема и передачи информации, так и процессов записи/считывания и собственно вычислений. К таким систешм можно отнести многомашинные комплексы, например, создаваемые па базе моделей ЕС ЭВМ путем кошлеяспрования с~помоцью ЩД с двухканальными переключателями.

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

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

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

Программная модель позволяет ропать задачи расчета г.т.г ;са сложных систем, а также СЛАУ большое размэрностзй с циентов параллельным методом диакоптлки, моделировать повелительный процесс и определять модельные времена резпол:;:-.: Пи на одиночной ЭВМ я на ИБС с кольцевой и радиальной

Программная модель включает 30 модулей па язи"о П"/1 с общим числом операторов 1С50 (объем загрузочного модуля - ¿СО использует компактные схемы хранения разреженных структур входных и промежуточных данных, сродства дина1ячеоксго расцгедсле-ния памяти и обеспечивает возможность сбора временной статистики.

Для моделирования параллельных процессов кспользога;.-;: средства файловой организации данных и хранения па

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

Приводятся результаты экспериментального исследован::." модели, проведенного на ЭВМ ВС-1045 в среде 03 ЕС, котерпз подтз-зр-дили полученные теоретические оценки и выводы, а та:с.:з позволили выработать рекомендации по эф]>з:<тпвнсп организации в^гне-лений в зависимости от параметров за-л га и хараптерцетнх 20.

Машинный эксперимент доя систем размерности -''/= 16,32,64 и различных значений р.^/с,^ в частности, показал: че.м боль-пе значения М при заданной связанности между подсистзма.'.л, тем выше эффективность параллельных вычислений на ПЗС независимо от вида ее структуры и шире допуеттпй диапазон оптимального расчленения; чем меньше Ж и меньше , тем более' эффективна кольцевая структура; чем больше связанность п меньше значения р, тем более эффективна радиальная структура; для случаев предельно допустимой связанности эффективности структур соизмеримы.

В приложениях приведены модельные характеристики, АБС-реализация ПЭД, программная шдель и примеры результатов ее экспериментального исследования, а также акты об использовании

я внедрен;:;; результатов диссертационной работы. ОСНОВЕ^ РЕЗУЛЬТАТЫ РАБОТЫ

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

пг -л елы ш х в ычи с л е ния х.

2. '¡.'.'рмулкрована топологическая постановка задачи расчета по час1.ч>: сложной системы, моделируемой линейной сетью или СЛАУ с К.!, формализована диакоптические принципы декомпозиции и композиции с помощью алгебраических диаграмм. Доказано, что решение исходной задачи может бить получено через совокупность решений для подзадач меньшей сложности с помощью введенных понятий узлового и контурного расчленений симплициального комплекса.

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

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

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

6. Выбраны и исследованы операционно-матричная, потоковая и функциональная модели параллельных алгоритмов, для которых:

- предложены технологии решения задач 1ВД;

- осуществлены и оценены алгоритмические реализации ПМД, а также программные для первых .двух моделей;

- построенные параллельные программы аттестированы на множестве сгенерированных сетевых моделей размерностью^=<14 + 64 >;

- определены границы эффективного использования в зависимости от параметров задачи и ПВС.

7. Предложены показатели сложности параллельных ттрогря:?.: и перехода от последовательной программа к парзллельноЛ з пр^м^по-ны для оценок программных продуктов.

8. Разработана, реализована на языке ПЛ/1 и исследована на ОЗ.! ЕС-1045 в среде ОС ЕС адаптируемая к структуре ЛВС и классу сложных систем программная модель, обеспечиваггая:

- моделирование и исследование параллельных процессов, протекающих при реализации ГИД на различных струкг/рах П5С, в том числе, на одиночной ЭВМ, на кольцевых и радиальных ПВС;

- отладку, тестирование параллельна* програ:.?.!, решение задач с помощью ПМД на одной ЭК.'..

9. Разработанные !.'етод, алгоритг/ы, програ;.г/нь'е продукты, а также технологии организации вычислений для реализации Г2.'Д внедрены на 3-х предприятиях и в учебный процесс МЭИ.

Основные положения диссертации отражены в следующих печатных работах:

1. Котарова И.Н., Еемаева О.Ю. Параллельный метод диакоптпкя для реиения сложных задач на распределенных вычислит ель ных системах //Кибернетика. - 1979. - Л I. - С. 112-119.

2. Котарова И.П., Еамаеза О.Ю. Декомпозиция сложных систем при их решении параллельным методом диакоптяки //Труды Моск. ^норг. ин-та. - М.: МЭИ, 1979. - вып. 415. - С. 81-68.

3. Котарова И.П., Шамаева О.Ю. Диакоптика как метод декзг/пезн-циа сложных задач при их решении на распределенных вычислительных системах //Применение микропроцессорных вычислительных систем для управления технологическим процессам: Тез. докл. и сообщ. - Смоленск, 1930. - С. 29-31.

4. Беркович М.Е., Котарова И.Н., Максимов Н.С., Шамаева О.Ю. Квазираспределенные вычислительные системы на основе 33,5 третьего поколения //Вычислительные системы. Сб. статей/ Под ред. Евреинова Э.З. - М.: Статистика, 1380. - С. 73-87.

5. Котарова И.Н., Шамаева 0.0. Эффективное распараллеливание процесса решетя сложных задач для РВС //Распараллеливание обработки информации: Тез. докл. и сооб'д. 1У Всесосзн. сколы -семинара, часть Ш. - Львов, 1983. - С. 94-95.

6. Шамаева О.Ю. Программное обеспечение квазлраспрецеленной вычислительной системы для решения класса слабосвязанных задач , большой размерности //ХХХУШ Всесосзн. научн. сессия, посвящ.

Дню Радио: Тез. докл., часть 2. - М.: Г&дио и связь, 1983. -С. 47—48.

7. Самаева О.Ю. Организация параллельных вычислительных процессов при реиекик одеого класса слоеных задач методом даакоптжкк //'.^крспроцоссорные средства вычислительной техники в системах связи z управления: Тез. докл. Всесоюзн. научн-техн. совещания. - М.: Радио и сачзь, 1934. - С. 77-78.

8, Ел:аева О.Ю. Организация функционирования параллельного про-

комплекса GKClVb вычислительной системе на базе ЕС Эй/ //Кд'еглтаческое обеспечение вычислительных систем: Межвуз. сб. научных трудов. - IL : ШРЭА, 1984. - С. II&-I26. S. Самаева О.Ю. Реализация параллельного метода диакоптики на шогокаппннцх комплексах ЕС ЭВМ. Оценки слоено сти и критерии эффективной организации вычислений. //Распараллеливание обработки информации: Тез. докл. и сообц. У Всесоюзн. школы-семинара, часть I. - Львов, 1985. - С. 87-89.

10. Борздова Т.В., Шалаева О.Ю. Решение задачи обращения катрпц декомпозиционными методами в системе функционального параллельного программирования дая комплексов ЕС 3B.V/TaM хв. - С.30-31.

11. Панаева О.Ю. Схемно-функциональное представление процессов реализации методов диакоптики на комплексах ВС ЭК.: //Параллельное программирование и высокопроизводительные системы: Тез; докл. 7-й Всесоюзн. ВС, - Киев, ИК АН УССР, 1986. - С. 185^187.

12. Еутепов В.П., Вахрушева М.Б., Протасов Е.А., Шамаева О.Ю. Лабораторные работы по курсу "Структуры вычислительных машга и систем". Системы параллельного программирования. - Москва, МЭИ,

1987. - 36 с. '

13. Борздова Т.В., Шамаева О.Ю. Схемно-функциональный подход к реализации декомпозиционных методов обращения матриц больших размеров //Кибернетика. - 1988. - № 2. - С. 39-42.

14. Еамаева О.Ю. Макроконвейерная схема реализации методов диакоптики //Конвейерные вычислительные системы: Тез. докл. и со-общ. второго Всесоюзн. совещания. - Киев, 1988. - С. 94-96.

15. Шалаева О.Ю. Схемно-фунхциональяая методика распараллеливания решения задач обращения разреженных матриц методами диакоптики //Парсшлельное программирование и высокопроизводительные структуры: Тез. докл. Ж Всесоюз. семинара. - Киев. Ж АН УССР,

1988. - С. 84-85. ,./

(■(//я.им**-----

п ......................а с г

■ ■/.^з 1 1 ~ tco ■ кС-зс, ■ ■■