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

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

на правах рукописи ШШХИН Валерий Владимирович

:НИЕ ВЫЧИСЛИТЕЛЬНЫМ ПРОЦЕССОМ В СЛАБО СВЯЗАННЫХ [ЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ СТЕНДОВЫХ ИСПЫТАНИИ СЛОЖНЫХ ОБЪЕКТОВ

»ность 05.13.13. - Вычислительные машины,комплексы, системы и сети

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

МОСКВА - 1990

' У • ) ,' У <"- ' ,

У,л;';.га на ааХ^Дре Системотехник;; Иосковског«

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

а-У- ... , улсЕодкто;а - кандидат техничзских неук.

доцент 1!.3. Готоьский. С$'<едад:->ше опвоиектм - доктор технических наук.

вро*ос;ор 'З.П. Кутапов. кандидат технических наук, старший научный сотрудник Е-П. Кмылоз.

Ведущее нредпря-ттио - указало в роевник савцналкзирс Совета ¡-Г);!. п

Зад,га е,:тситоп Ж-19зэ г. в ,

О О Г-Зф

-мин. в ауд.------1—на засодаики ыюцкалигкро&енногс

К-05315 05 М:ск'Г'"!'орлоне Х&язжа и ордена Октл Рвеолкф«*. »иорипки^паго института.

Отзыеы < в д."у:-- зптемалярах, г&шрзкных яечатш ) направлять но адресу : "аа-Зо, ГСП, аоскса Е-2С0, у." араек; мелкая, д!<!. Уч.а;;:-: Уаа-

С Д;;ссортац"":: ;к-I б;;С;т;:ста; о а?;!

Дьгора^рат ¡'.азом:а: Уаина,: >а к; ;г;а;.:ъ

а'а<с:а "'.а- га К-Гарра.а р.;;

■ • -. • ?)

}■.....

? 1

; * - з -

I .-гг,3 ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

! ДОСЭДТСЦИЙ^

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

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

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

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

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

В соответствии с этой целью в диссертационной работе риыа-

- А -

ются следующие задачи:

1. Выбор логической структуры ССРВС стендовых испытаний.

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

3. Разработка метода декомпозиции сложных- систем с меньшей вычислительной сложностью.

4. Разработка алгоритма распараллеливания -задач на асинхронные участки с ограничениями по их числу и количеству взаимодействий между ними.

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

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

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

8. Реализация коммутационной сети ССРВС стендовых испытаний сложных объектов ка базе волоконно-оптических средств связи в стандарте КАМАК.

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

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

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

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

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

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

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

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

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

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

Разработана коммутационная сеть ССРВС на базе ЭВМ ряда РБР-п, волоконно-оптических средств связи в стандарте КАМАК и сетевого математического обеспечения ВЕСНЕТ.

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

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

Реализация результатов работы. Результаты диссертационной работы использовались при создании распределенной автоматизированной системы стендовых испытаний сложных объектов в НПО "Союз" МОП.

Апробация ваботы и публикации. Результаты работы докладывались ка конференциях молодых ученых и специалистов в НПО "Союз", на отраслевом семинаре по автоматизации научных и экспериментальных исследований, на II Всесоюзной конференции "Микропроцессорные системы", на III и IV Всесоюзных конференциях по автоматизации научных исследований в области ядерной физики и астрофизики.

Результаты диссертации нсивт отражение в 5 печатных работах.

Объем работы. Диссертация состоит из введения, пяти глав и заключения, приложений и библиографии, включающей 89 наименований. Основной текст диссертационной работы содержит 122 страницы, из которых 18 занимают рисунки, I - таблица. Приложение к диссертации выполнено на 75 страницах.

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

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

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

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

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

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

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

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

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

Наибольшее распространение получила классификация Флинна, затрагивающая только два первых признака. Потоки номманд и данных могут быть одиночными или множественными ( Single Instruction, Multiple Instruction, Single Bata,. Múltiplo Cata ).

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

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

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

- а -

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

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

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

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

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

Однако организация системы управления вычислительным процессом в системах типа КЕД) затрагивает сложные проблемы, подчас неразрешимые. Кз анализа эффективности функционирования систем М1Ш) и К1БЕ следует, что при многократной обработке множества задач система типа К1БЭ обладает неоспоримым преимуществом по показателям эффективности и инвариантности к классу решаемых задач. На базе тагах систем осуществляется конвейерная обработка однотипных массивов информации. Таковыми в ССРВС стендовых испытаний являются массивы экспериментальных данных, получаемых по разным измерительным каналам.

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

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

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

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

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

Как было уже отмечено, система управления ССРШ является децентрализованной и состоит из локальных систем управления отдельных ЭВМ. Взаимодействие этих систем определяет Функционирование всей ССРВС и управление распределенным вычислительным процессом.

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

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

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

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

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

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

к = Р~'АоР , (1)

где Р - перестановочная матрица.

Таким образом, необходимо найти перестановку вершин матрицы Ао, при которой все ненулевые элементы сгруппированны вдоль главной диагонали матрицы При этом, после разбиения изоморфного графа С1 на подграфы с^.а^ . . . ,й11Г1 с заданным количеством вершин »!°121 > - - - >1с1т1 полученное количество ребер, связывающих эти подграфы, было бы минимальным.

Данный метод декомпозиции сложных систем состоит из четырех процедур: а) поиск начального узла; б) построение остова исходного графа Со; в) упорядочение вершин графа ао с цель» получения искомой перестановки; г) выделение подграфов на изоморфном графе

а) Оптимальное преобразование исходной матрицы смежности в блоч-но-диагокальный вид сильно зависит от выбора начальной вершины пе-

рестановки. Для этого был про' . :он следующий алгоритм : Алгоритм X.Поиск начального узла.

Пусть ао=<то,Ео>, (г)

где -множество вершин, Ко-множество ребер. Этап I. < Инициализация ). Выбор из произвольного узла V,. Этап 2. ( Построение структуры уровней ). Построить структуру уровней с корнем в чг:

= {ьо(у ).Ь(уг).....о)

Ьо<7г> = < * >. '

Ь, = А«(Ьо(7)), (5)

где А<ШЬ0(*г)) - множество верпган смежных с ▼ Ь(у) = АсШЬ.^)) - Ь_г(Уг), з = 2.3. . . . -Д(^); (6)

1(уг) - эксцентриситет узла уг. Этап 3. Выбрать в ((уг )узел с минимальной степенью

(степенью узла V называется <3е.£;(у)= = |(V) |). Этап 4. Построить структуру уровней с корнем в

иук) = { Ъ0{\).\ю.....>• (7)

к

Если > положить vr и перейти к этапу 3.

Этап 5. < Финиш ). Узел является псевдопериферийным.

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

жествам , з > к, и находящихся от вериины ч^ т^на расстоянии, меньшим или равным г, г = 1, . . . .,( 1(ухо) - к ). Данное обозначение понадобится нам в дальнейкем.

Этап I. Построим корневую структуру уровней кз выбранного начального узла.

Этап 2. < Поиск в ширину ). Произведем упорядочение вершин графа.

Пусть начальный узел х = гх0. Обозначим через ух1 узол с наименьшим значением г при условии * о.

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

Упорядочим остальные узлы по уровням в зависимости от значений г и .Создадим множество ветвэй остова графа.

б) Произведем окончательное упорядочение вершин графа. На это»' шаге происходит поиск в глубину по остову графа по следующему алгоритму (алгоритм У) : . Этап I. Обозначим х =

Этап 2. Рассмотрим вершины следующего уровня. Если есть ребро х -где ^ е Ь(х), то обозначим V . Если таких вершин

несколько - смежных с х по остову - , то выберем вершину с наименьшим номером согласно перестановки предыдущего алгоритма . Этап 3. Продолжим поиск из вершины гх1 . Если существует новая ( непросмотренная ) вераина из то берем ее за базовую и продолжаем процесс. В противном случае возврат к предыдущей вершине. Этап 4. Если все вершины просмотрены, то конец поиска.

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

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

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

Алгоритм 4. Декомпозиция матрицы смежности изоморфного графа. Этап I. Сформируем список инцидентности вершин графа, в котором указаны все его вериикы.

Этап 2. Создадим список степеней смежности элементов матрицы

- (р^г ), где 1 = 1....... р^ - степень смежности элемента

матрицы а с предыдущими" элементами, г - степень'смежности с последующими элементами.

|а | |

Этап 3. Обозначим через (р 11 ,г ^ ) элемент списка степеней

смежности подматриц матрицы А.,, где PJ - степень смежности j - ой подматрицы мощности |А | с предыдущими подматрицами,

|а |

г 11 - степень смежности с последующими подматрицами.

' |* I 1\,1 кп

р," =2 к - г, = I где (8)

1=1 1=1

- степень смежности элементов подматриц А1 Этап 4. Положим 1 = 0, 3 = 1.

Этап 5. Увеличим значение 1: 1 = 1 + 1. Если 1 > п , то перейдем к этапу II.

Этап 6. Отнесем 1 - ый элемент матрицы А( к подматрице А . Если существуют элементы подматрицы А^, смежные с х -ым элементом А1, то удалим из спи««, инцидентности соответсвугаие ребра и .уменьшим на положенное число значения р и г из списка степеней смежности: (рк.гк) = (Р^Гу - 1), (Р^г) = - 1.Г ) , для V а,. « А. при условии е е Е .

I*. I I*, I

Этап 7. Вычислим значение р1 . Если Р] > 1, то все элементы отнесем к предыдущей подматрице. В противном случае перейдем к этапу 10.

К I

Этап 8. Положим з = 5 - 1- Если р ° > 1 , то отнесем элементы Л.^ к предыдущей подматрице. Повторим данный этап пока ке выполнится условие: pJ $ 1

Этап 9. Увеличим значение о: Л = 3 + 1 и перейдем к этапу 5.

К I К I

Этап 10. Если ( Р, + г ) ^ тс завершим Формиро-

вание подматрицы А^ и вернемся к этапу 9. В противном случае перейдем к этапу о. Этап II. Финиш.

Суммарная вычислительная сложность предложенных алгоритмов определяется выражением :

0(|Т||Е| + 2(|Т| + |Е|) + |У||Е|) = 0(2(|Т||Е| + |У| + ¡2!)) (9)

Для построения алгоритма распараллеливания задач на асинхронные участки сформулирована следующая задача : произвести декомпозицию исходного графа 0о информационных взаимодействий между компонентами заданной задачи на сбалансированные по времени выполнения подграфы а1(1 . . . . При этом были введены следующие ограничения :

1. У каждой подсистемы ( подграфа ) не должно быть более одного преемника или предаественника.

2. Количество подсистем не должно превышать общего числа процессоров в системе.

Для решения данной задачи предложена следующая процедура: Этап I. Построим корневую структуру уровней из начального узла с наибольшим эксцентриситетом.

Этап 2. С помощью алгоритмов базового метода декомпозиции получим необходимую перестановку вершин графа 0о.

Этап 3. Построим матрицу смежности графа в^Предстазим матрицу А в верхнедиагональном виде, при котором 1-я иирина ленты опре-

деляется следующим образом:

= - i, (10) где * (А-,) = mini л | a f О}. . (11)

Этап 4. Рассмотрим ширину ленты первого элемента матрицы Аг Объединим в первой подсистеме количество элементов равное данной ширине ленты.

Этап 5- Просмотрим значения <\Ut) элементов, вошедших в первую подсистему. Если тах(.Ф^к1)-Ф1(А±))- т, где m > О, 2 < i < то отнесем к данной подсистеме следуюаде m элементов. Этап 6. Проведем аналогичную процедуру для остальной части матрицы At.

Если в итоге получаем количество подсистем больше, чем число процессоров, то перейдем к следующим этапам. В противном случае -Финиш.

Этап 7. Вычислим сумму времен выполнения ЗадДч еходяzyix в каждую подсистему.

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

Для реализации метода статической декомпозиции вычислительной системы на кластеры элементарных машин были введены понятия нечетких отношений элементарной машины к ступени макроконвейэра по заг-. рузке процессора - КР, по дополнительному ресурсу - RRt и по каналу связи с предыдущей ступенью - RN. Функции принадлежности данных нечетких отношений определяются следующими выражениями : гоах ( г?' - r>v - t , о )

---— , J t g-.где ■ (12)

sup max { г) ~ n ~ с )

j ■ r 1 T '

- константа отношения по процессорному времени . пг - коэф-. Фициент резерва процессорного времени, - коэффициент использования процессорного времени i-ой ступенью.

max ( -----* . 0 )

^ (j.i) = - ,(1Э>

зир шах ( --

где Rt(i) - необходимый t - ый дополнительный,ресурс, R^ -максимально возможный t - ый дополнительный ресурс , B|rt- сво-

R

бодный I -ый дополнительный ресурс, г* - константа отношения по дополнительному ресурсу. (14)

шах(тт(>7 .....о ) - -^ - *\,.0>

0.95

^„<3.1-1 )=-

зир шах(тш(и' .......т,г ) - -- е )

0.95

где коэффициент загрузки канала связи, коэффици-

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

Алгоритм статической декомпозиции вычислительной системы на кластеры элементарных машин состоит из следующих этапов : Этап I. Построение структуры уровней из узла первой ступени. Этап 2. Положим 1 = 2, к = 1.

Этап 3. Формирование множества узлов, для которых : (15)

^(3.1) топ ( ^„(дМ), ^М(ЗЛ~1), (3.1)..(3.1)) ^ О,

где ш - число дополнительных ресурсов, о с ^ .

Этап 4. Узлы , для которых ( 3, 1 ) = О , отнесем к множеству

узлов следующего уровня , если для всех узлов данного уровня

3. 1 ) = О , то исключим их из дальнейшего рассмотрения . Этап 5. Упорядочение полученных узлов по росту эксцентриситета и уменьшению степени смежности.

Этап 6. Увеличение общего количества уровней на единицу. Образование пустого уровня

Этап 7. Перенос узлов полученной последовательности кроме первого на дополнительный уровень!^.

Этап 3. Узел уровня 1«. принимается за узел к - ой ступени макроконвейера.

Этап 9. Если количество верхних уровней единичной мощности равняется количеству ступеней макроконвейера, то финщ., иначе переход на следующий этап.

Этап 10. Положим 1 = 1+1, к = к + 1. Переход на этап 3.

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

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

rurra. гак как коэффициенты загрузки вычислительных средств представлены нечеткими числами ( Ь - К ) - типа. Функции принадлежности нечетких отношения определялсиь следуюшдмк выражениями : ( tr.ax (0,1-1 (j,i)-^RB

С К» U»1» = I при 1 1 (16>

I га-ах (oH-K^ (äl,i)^BR (зД))/^'Ч)

при JJHR (з Д) ¿„„УД1)- 1

i t

Г шах (0,1-| (¿vÜ.ib^tj.i))/«^!) ^*r(^RP(3.i)) = ] при инг (эЛ)Фкг(зЛ). , (17)

( шах (0,1-| ^„„(j.D-^Cj.i))/^!) при (л,i) ^ ¿ВР(ЗД).

(10)

(шах (0,1-(j Д-1 )-MRN (О Д-1 ))/«(PRN (J Д-1 ) ) )

[¡пах (ЗД-1)))

при мкк CJ.i-1) ^ ¿„(З.Ы)

где р - моды нечетких отношений, а <v'"~ коэффициенты нечеткости.

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

i^U.i) = min +PBP(j.i))/(1+f?RP ),(^<MllN(j,I))+PitN(J,i))/

j j

1 1 i

(19)

mm m

где m- количество дополнительных ресурсов

Для оценки неопределенности получаемой информации в алгоритме использовались понятия возможности и необходимости высказывания ?(j,i) : " значение останется отличным от нуля на про-

тяжении времени Т(п) где 5(п) - время Функционирования макроконвейера. Возможность высказывания P(j,i) определялась из выражения :

П(ШД),П) = аур min «К)) - (20)

а необходимость • (21)

N(FU,I),n) = igi шах (^F(J_U Н ) .1-п Ц )), <о е О ,

где n - множество событий , влияющих ка загрузку вычислительных средств. Исходя из значений возможности и необходимости, определялась истинность высказывания ?(j,i) - ¡-■(?(3,i).n) :

y(P(J,I).n) = (n(?(j,i),n)4N(P(jIi),n))/2 . (22)

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

Работоспособность предложенных методов и алгоритмов проверена на примерах, где проиллюстрирована их хорошая сходимость.

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

Модель построена по модульному принципу и оформлена з виде пакета программ на алгоритмическом языке C'JRBO pascal v.5.5 для ЭВМ PC АГГ.

Целями имитационного моделирования явились:

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

б) оценка показателей эффективности выполнения макроконвэйерной обработки экспериментальных данных на конкретной РВС; определения -ограничений на класс решаемых задач ; принятие решения о целесообразности проведения макреконвейерной обработки на конкретней РВС стендовых испытаний сложных объектов;

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

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

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

трсцзссом позволит увеличить вычислительную мощность системы на 25 -30 й при использовании 6-8 элементарных машин. При дальнейшем увеличении количества вычислителей уровень производительности системы снижается из-за роста непроизводительных расходов системы управления, которые определяются по экспоненциальному закону. Данный Факт подтверждает результаты теоретических исследований.

По результатам моделирования можно отметить, что использование отдельных элементарных машин в нескольких кластерах дополнительно повышает об!Дую производительность системы на 5-10 X, а суммарная загрузка процессоров в этих элементарных машинах приближается к максимальной, то есть к единице.

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

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

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

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

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

Модуль ВОС-1 был доработан и адаптирован под сетевой процесс Ий СЕСЮТ и прошел опытную проверку в составе коммутационной сети на базе ЭВМ СМ - 1420 расширенной конфигурации.

Выбор сетевого пакета ЮКСКЕГ был определен наличием в нем широкого набора сетевых услуг, в том числе транзита и межзадачного обмана. необходимых прк организации распределенной обработки данных.

На Саг.е созданной кгммут.чгщсчкой сйти Смла оргаикзогаиз рлспрадллнннит сораСот;.а эксперимент 1Л:на;": пнрормащ«;. Нз данной сот:- Силл яолучонн кес^хидт» характеристики, когорш ксполгзо-р<шгл. при киктацпонком кидвлиродонкз РнраРчнло предложенных методе*? и алгоритмов позволило увеличить производительность вычислите льиоЯ с»сто».*ы ¡¡а :о-:Т> к, что практически совпадает с результатами имитационного у?долирсвчккя

рнволи

1- ГЬ реау;И'тагам овализа осс^нксстпа проведения стеидогых испытаний сладких г.лтектсв. типовых структур автоматизированных систем, не:^ааату:а: трюмилеанх вычислитесредств и оалач по:-л;::?!;а:л о'л.';:й лрллзгеднтел! лглтп с'ла-аплл: лкспариа-нталлкой ;',:*ор:".;и;н:т показана актуальность солда.чол; и применения а ал'.под-г:: а ■'ргалазацни и уярлвл^икк гллголлта лы:>::.; ;;рсл~с!'0'.' автсиа-та^-'Г"- а;нах ол;л'оаа\ гтанд^галс испытали;:.

Г сюллл: показателей ивнссти Функапенпговааил

лааалл а:;а' л-: !>!:ч;:о л аа-л;ла.:х систем ;;рп;; локона логлоаская структура О'ОГ'ал ?.то;;д а" ох иеггатаний. как коалззпллл саолаол ■>< тала а

, ,.г,:...... сг.__);акрсксн?е;:орк г.'г-а'атаа зкепориа-лн-

л лакал /аллах

о. Г; аал .а от; ;л тта снстэ::!: :-'::раол'л;ля вычислительны'! ;та (ХРРС ст"-н;'?1а:х нспытанлл Ллнлля структура управления 0р;ал:тлуслала к \ ■: лл лла^л.нс1 а.ллоллглаллэ "таклзрткогоеллтал-¡■'тп та:"''1",-"-'"С!'а;'о о'-спече;:;'а

' : -у у . т.'-.'""а а:: аллгпа а'; гтздсистг:::', а лаллл"л:ал; а,а; олчлеллгеЛаоса 'ал < 7 ааа г лл реализации алгоритма ; -а;а'> аа;^ал-каа а пгада; лааал ;а"> л-:::;:( ро'от

1 р.,- -г-и •алаорллл т'логаллллоллллнл л задач на оенкхролкло участ-:л л а 'лте: ггтл;::;л~л'л: на ах члола а лгл;л";оет:'0 взоигодрлетала а:аа: " "у лгл- л ал аллорила л л л л : а-а; у о-'рляочаклол ;а:с: "ство

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

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

9. Приведены результаты опытной эксплуатации коммутационной сети на базе ЭВМ ряда РИР-11, волоконно-оптических средств связи в стандарте КАМАК и сетевого пакета ШСККР.

10. Результаты диссертационной работы использовались при создании ССРВС стендовых испытаний сложных объектов в НПО "Союз" МОП, что позволило увеличить производительность системы на 20-25 х.

По теме диссертации опубликованы следующие работы :

1. Илюхин В.В., Кощеев В.А. Проблемы создания распределенной операционной системы в микропроцессорных комплексах // Микропроцессорные системы : Тез. докл. II Всесоюз. науч.-техн. конф. 2224 сентября 1988 г.-Челябикск, 1983-С.46.

2. Илюхин ВВ. Распределенная обработка экспериментальных данных в автоматизированных системах стендовых испытаний п Передовой производственный опыт.-1989.-М 5.-С..20-23.

3. Виноградов ВИ, Иванов В.М., Илюхин ВВ., Ключник О.В.,

Сркин С.В. Организация распределенной обработки экспериментальной информации стендовых испытаний на основе ШСКЕР и волоконно- оптических средств связи // Автоматизация исследований в ядерной Фиэи- . ке и астрофизике : Тез. докл IV Всесоет- шк. 8-13 октября 1990 г. -Ужгород,1990.-С.г4-2б.

4. Кощеев В.А., Илюхин ВВ. Методы реализации системы управления

в слабо связанных распре ленных вычислительных комплексах // Автоматизация испытаний объектов машиностроения : Тез. докл. науч.-техн. сем. 17-19 декабря 1990 Г.-Челябинск.1990-С22-23.

5. Кощеев В-А., Иванов В.М., Илюхин ВВ. Распределенная обработка информации при испытаниях сложных конструкций // Автоматизация испытаний объектов машиностроения : Тез. докл. науч.-техн. сем. 17-19 декабря 1990 г.-Челябинск.1990.-С.30 31.

{ Ь>ЛИ>ПЧ)»1И К 1Н"П1И .1 - ' г ж , —

) п у/, 1м|>м* /¿'С * 2--/3 Псу» <атио.

гм ¡мфчч крит«.,и;||>чм»раи. iv