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

Шаэ \

¡¡в !Ь'/ •

. МИНИСТЕРСТВО СВЯЗИ СССР

Московский ордена Трудового Красного Знамени институт связи

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

- -Мансуров Тофик Магомед оглы

УДК 681.324.

РАЗРАБОТКА МЕТОДА. .ДИСКРЕТНО-ТРАЕКТОРНОКГОТОБРАЖЕНИЯ ЛОГИЧЕСКИХ СХЕМ АЛГОРИТМОВ В ОТКАЗОУСТОЙЧИВУЮ ОДНОРОДНУЮ ВЫЧИСЛИТЕЛЬНУЮ. СТРУКТУРУ

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

*

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

А в т о р е ф е р а т

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

Москва 1990 -

Работа выполнена в Московском ордена Трудового Красного Знамени институте связи на кафедре вычислительной техники и управляющих систем. _ - " - _ • Научный руководитель - кандидат технических наук, доцент 1. . - ~ ~ М.Ю.АРТЕМЬЕВ ' Официальные оппоненты - доктор.технических наук, профессор - М.И.ПЕСКОВ - ' - " --* . кандидат технических наук, доцент

" - . И.С.ПОТЕМКИН - „ •

Ведущая организация' - ЦНИИ "Циклон". .

• ' " " ■ 4 -1? Защиту состоится -*[990 г.' в

1С-'

ч на

заседании специализированного совета КЛ18.06.02;в Московском ордена Трудового Красного-Знамени институте.связи.по адресу: . "_ПШ<41 Москва, Авиамоторная ул.,.д.~8а,-- ^ -.

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

-.- Автореферат равослан 4."__К90 г.. ! '

Ученый секретарь^"

специализированного, совета. " ••

К 11^.06.02, к. т.н. /доцент-_ . п> ~лт —К В. Демина-

0Б1ГАЯ УАРЛКТйРИСТйКА РАБОТЫ

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

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

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

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

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

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

В соответствии с поставленной целью в диссертационной работе решаются следующие основные задачи:

исследование и обоснование выбора формальное модели представления структуры логических схем алгоритмов;

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

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

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

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

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

2. Разработан метод дискретно-траекторного отображения логических схем алгоритмов произвольной структуры в отказоустойчивую Ох>С, отличагсвцийся от известных быстродействием и дискретным характером построения траектории ■Т.ункпии оптимального отображения алгоритмов, учетом отказов олементарных «одуле?

на этапах планирования и реализации вычислительного процесса. Кетод включает в себя следующие основные теоретические результаты:

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

разработана процедура оптимального отображения логических схем алгоритмов произвольной структуры в ОЬС с учетом отказов модулей на этапах планирования и реализации вычислительного процесса;

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

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

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

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

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

Реализация результатов работы. Диссертационная работа выполнялась на кафедре вычислительной техники и управляющих систем Московского института связи в соответствии с хоздоговорной НИР с Центральным научно-исследовательским институтом "Центр", а также по договору о творческом содружестве между отделом АСУ АН Азерб. ССР и МИС.

Результаты диссертационной работы реализованы при проведении научно-исследовательских работ и включены в научно-технический отчет (гос. per. № 01890034386).

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на Всесоюзной научно-технической конференции "Микропроцессорные средства локальной автоматики" (Гродно, j£S89), на Всесоюзном научно-техническом семинаре "Качество функционирования и надежность систем автоматической коммутации и сетей электросвязи" (Новосибирск, Ьбо), на Республиканской научно-технической конференции "Достижение науки - производству" (Баку, 1988), на IX научно-технической конференции молодых ученых и специалистов ЦНЯИС (Москва, I9S0), на научно-технических конференциях профессорско-преподавательского состава и аспирантов МИС (Москва, 1989, 1990) .

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

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

0 с но в. ные и о л о i е я и я , выносимые на защиту: - '

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

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

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

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

.тройки ОВС при одновременном планировании нескольких вычислительных процессов..

~ КРАТКОЕ СОДЕРКАШЕ РАБОТЫ

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

В первом разделе работы обоснована кон- _

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

Исследование принципов построения и эксплуатации, многомодульных систем позволило сделать вывод" о том, что эффективность -и надежность функционирования во многом определяется представ--. лением решения-сложных ^задач в параллельной форме, системным и прикладным программным обеспечением. В работе проведен анализ -существующих формальных моделей представления структуры логических схем алгоритмов в параллельной форме. К их. числу." относятся: ярусно-параллельная форма, впервые предложенная Д.А.Поспеловым и развитая в работах С.Д.Пашкеева; параллель- ■ ные алгоритмы, получаемые" на основе методики крупноблочного и функционального распараллеливания, впервые предложенные Э.В.Евреиновым и Ю.Г.Косаревым; формализация параллельных алгоритмов в терминах "сетей Петри; функционально-потоковая модель параллельных вычислений. ~ - - ■ • /_ -'

На основе проведенного анализа существующих формальных" ' моделей представления, структуры логических^схем алгоритмов и особенностей их реализации на ОВС обоснован _шбор функционально-потоковой модели-"логических схем алгоритмов, по своей функциональной структуре адекватно соответствующий топологию ОВС и позволяющий выявить естественный параллелизм задачи..7

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

Во. "в т о р~о м "разделе решается задача-изоморфного отображения логических"схем алгоритмов в отказоустойчивую ОЙС аналитическим способом. - " - ~ "

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

литических.. расчетов до данной процедуре введена вектор-функция -структурно-топологическо:" уив;лгеота

^^{^.БД)]• и) -

" каждая компонента которой.определяется-по формуле: .

О^^Д) = |](г, $',{); г = 2~м-; \ = 5^7, г 2 Г ~..

где Р^ (^Э1, £) - вероятность того, что. в любой момент времени Ъъ 0 в однородной вычислительной структуре кз_М модулей, объединенных" в топологию Б и находящихся-в начальном состоянии ^ (число отказавших-модулей) может быть-образована связанная подструктура из Ъ модулей, объединенных в топология S .

Процедура расчета показателя &(£) сводится по с^еству к расчету вероятности" Р: Б', {) , которая представляется в "м^е произведения двух независимых вероятностей '

.^■'■•О'Рн.^М-Р,^), О)'

где' щ^(^) - вероятность .того, что в~лтобой момент 'сре^ени

0 в ОВС из N модулей, находящейся в начальном состоянии ^ исправно П- модулей; вероятность того, что.из-Р^

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

Отказоустойчивый характер-функционирования ОйО учитывается -на этапе расчета вероятности Р. .,;({),- а учет топологических

-™>1»Л) 4 п / ч\

характеристик проводится при расчете вероятности гг(ь ].. Расчет вероятности проводится на основе методов

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

= л^) + £(-¿) 7 ■ -: 44) .

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

- модулей; .А^ (О интенсивность переходов^ обусловленных отказами модулей ;_£ - малый параметр, с помощью которого обеспе--чиаается^требуемая точность вычислений; - -порядок точности^ вычислений. В процессе вычисления-интенсивности отказов малый параметр £ определяется в зависимости от требуемой точности расчетов. _ _ _

адя расчета вероятности .

в работе получены аналитические зависимости для различных "структур-логических схем ал-горитмов-и для ОВС-с различной/топологией.

Ддя магистральной макроструктуры "расчет вероятности ■ зависит от соотношения между количеством модулей в образуемой, '-- подструктуре и количеством исправных модулей в ОВС. Отказъле-~ ментарного; модуля приводит к_ отключению его от единой магист--рали и связность всех оставшихся модулей сохраняется неизменной. " ■ • ■ - -

¿¿я одномерной" КАИОструктуры-. и линейно;; макроструктуры -вероятность Р^(Ь') определяется по формуле:

ск . д-С*"' " - ~

^ ' ' - ~ Л

где К - количество отказавших модулей; А - число -различных ■

- положений образуемой подструктуры и для одномерной ХАИС-струк-туры А-1 .»" а для линейной макроструктуры"

Г м-г , пру..''Ы/г < Я , , ч

АН--; , - - ' -(6)

I 1 , лр и. н/г * 1.

- Для матричной макроструктуры из модулей расчет

ьероятности "образования связанной/подструктуры иа Х -модулей проводится для двух случаев:- . _ .'„".

Случай I. Когда отношение 2, ,

. .р>) =

Л

„ о. «к-л ' „ а. к-о. \

С

где I~ 0— ^ - число различных положений образуемой подструктуры; (Х- - дополнительная переменная.

Случай 2. Когда отношение >,' 2. ,

* , „

Гк ¿9-Е

■V

гк

к .а К

Г1

^ к

, при ;

кри К ^.

(8)

{,0

Б,г = :7

На основе полученных аналитических выражений для расчета ■ ¡-ероятностек и Рг(>') построены кривые,, показывающие за-

висимость" & - от различных парш.{етров,' графическая интерпретация которых показана, на рис. I.

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

Уменьшение значение-вектор-функции структурно-топологической тздву-чести &({) в первой области происходит за счет ■ уменьшения вероятности до минимума в интервале времени 0 < 1/р и ■ уменьшения вероятности Рг(Л') в- зависимости от количества отказавших модулей. С момента -

' - — _ п .

н— . 1 ■• - к.= К т^г^

1 1 к- К ¿Р-

! I . 1 ч к - К та.к

1/г

Рис., I

и ввиду выполнения неравенство у* >> £ -.А^СО вычислительная" структура входит в стационарный-режим функционирования, соот-" ветствутощий второй области графической интенпретации.

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

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

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

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

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

О п р. еделение I. Логические схемы алгоритмов &1 и называются оптимально отображенными по заданному направлении на ОВС, если выполняются следующие условия

си п а, = Ф ,

(9) -

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

В качестве функции цели оптимального отображения логических схем'алгоритмов выбрано количество занятых модулей ОБО для реализации вычислительного процесса. Тогда маге?латическая модель задачи состоит в отыскании значения - -

' Ы - тс* 1Ъ , "(КО

.... Г

где Г -область допустимых решений,•задаваемая условиями:

а) условие взаимного непересечения алгоритмов 0-1 и ^ при их отображении на ОВС

б) условие отображения алгоритма 0-1 на ОБО

^(эсг,^) > о , Ы

к 1*1,%) <-'- (12) *

т, - , 1-- 17Я ,

- где - координаты граничных верягин алгоритмов

0-1 и ; - абсцисса наиболее удаленно!; от оси ординат вершины алгоритма - после его отображения на ОЕС; не-

- обходимое количество модулей для реализации алгоритма О..

- Для получения системы условий (II) и (,12) , используется ■ функция оптимального отображения (300) , траектория функции оптимального отображения (ТЮО) и метод последовательно-одиночного отображения, позволяйте строить варианты оптимального отображения и провести целеналравле;гный перебор по методу значимых переменных.

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

Метод дискретно-траекторного отображения логических схем

- 13 -

алгоритмов в отказоустойчивую ОВС включает в себя процедуру "разбиения алгоритма произвольной структуры на выпуклые части, ;остроение^ТЮО "выпуклых частей алгоритмов и построение границы области объединения, являющейся ТЖЮ заданной пары логических схем алгоритмов.

. В работе определены опорные функции оптимального отображения необоснован выбор полюса траектории функции-оптимального отображения. Если логические схемы алгоритмов имеют невыпуклую структуру, то неправильный выбор полюса может привести к многозначности функции"оптимального отображения. Поэтому в качестве критерия местоположения полюса выбирается любая внутренняя вершина выпуклой области ТФОО, где 300 логических схем алгоритмов определяется однозначно.

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

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

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

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

Определение 2. Необходимым частичным сдьигом логических схем алгоритмов в заданном направлении на ОВС называется одновременный сдвиг минимального количества веригин, при котором происходит освобождение строки, или стлбц.ч с от- 14 - - ~

казавпшм модулем.

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

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

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

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

Для реализации предлагаемых решений по вопросу оптимального отображения разработан алгоритм построения траектории функции оптимального отображения, включающий в себя: алгоритм разбиения логических схем алгоритмов произвольной структуры на выпуклые части; алгоритм построения Ж)0 выпуклых частей; алгоритм построения границы области объединения ТФОО выпуклых частей.

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

, си)

где , - алгоритм разбиения, применяемый соответственно к логическим схемам алгоритмов и Л/ ;

(¿г - алгоритм построения ТЮО выпуклых частей;

- алгоритм построения границы области объединения ТЮО выпуклых частей;

- операторы, выполняющие вспомогательные действия а лроцессе реализации алгоритма построения ТЗОО логических схем алгоритмов; _ -

Л - условие проверки ^ > ¡п. ; - условие проверки с > 1ь ; где ^ , (л - соответственно количество граничных вершин алгоритмов С^ , .

На основе формальной записи алгоритма (13) разработан программный комплекс, предназначенный для автоматизации процесса оптимального отображения логических схем алгоритмов в отказоустойчивую ОБО. Результаты эксперимента на основе данного программного комплекса по оптимальному отображению логических схем алгоритмов произвольной структуры показали, что характер полученных зависимостей для вектор-функции структурно-топологической живучести (т({) совпадает с характером зависимостей, показанные на рис. I.

Далее в разделе показано, что процедура настройки вычислительной структуры является основной составляющей при аппаратной реализации метода дискретно-траекторного отображения логических схем алгоритмов в отказоустойчивую ОВС. С учетом проведенного анализа параметров элементарных модулей ОВС с решетчатой топологией была предложена организация элемента вычислительной структуры, обеспечивающая уменьшение количества занятых в процессе настройки модулей в ^■^/(с^ + И;-*) раз, где

» •Ч " размерность подструктуры, ограниченная модулем-передатчиком и модулем-приемником. Кроме этого предложенный модуль обеспечивает сокращение времени настройки ОВС при одновременном планировании нескольких вычислительных процессов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

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

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

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

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

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

8. Разработана архитектура модуля ОЕС с решетчатой топологией, обеспечиъа'ощая уменьшение количества занятых в процессе настройки модулей в /"¿«¿Дл^-раз и тем самым сокращение времени настройки вычислительной структуры при одновременном планировании нескольких вычислительных процессов.

•лисок 11 жжацш

I. Артемьев У.Ю., Мансуров Т.Н. Метод расчета показателей надежности функционирования отказоустойчивых вычислительных структур для управления объектами в реальном масштабе времени //Микропроцессорные средства локальной автоматики: Тез. докл. Зсесоюз. научно-техн. конференции. -Гродно, 1989. -с.168,169.

2. Артемьев М.Ю., Мансуров Т.М. функционально-структурная модель отображения алгоритмов решения задач на однородных вычислительных структурах. -М., 1989. -18с. -Деп. в ЦНТИ "Информсвязь", Р 1615.

3. Артемьев М.Ю., Мансуров Т.М. Отказоустойчивые управляющие структуры цифровых систем коммутации //Системы коммутации с программным управлением: Сб. научных трудов ЦНИИС. -М., 1989. -с. ,52-59.

4. Артемьев М.Ю., Мансуров Т.М. Исследование взаимосвязи между алгоритмами решения задач и топологией однородных вычислительных структур. -М., 1990, -32с. -Дел. в ЦНТИ "Информсвязь", № 1632.

5. Мансуров Т.М., Артемьев М.Ю. Анализ редких событий при оценке надежности распределенных управляющих систем //Достижение науки - производству: Тез. докл. Респуб. научно-техн. конференции. -Баку, 1988. -с. 45,46.

6. Мансурод Т.М. Разработка алгоритма оптимального отображения ЛСА при автоматизации процесса проектирования программного обеспечения специализированных ОВС. -М., 1990. -16с. -Деп. в ЦНТИ "Информсвязь", Г'1657.

7. Мансуров Т.М. Анализ управляющих устройств в системах коммутации с программным управлением //Качество функционирования и надежность систем автоматической комь?утации и сетей алектросвязи: Тез. докл. Всесоюз. научно-техн. семинара. -Новосибирск, 1988. -с. 34,35.

8. Мансуров Т.М. Управляющее устройство системы коммутации с программным управлением //Методы и устройства передачи информации по каналам связи: Сб. научн. трудов Азерб. политехи. ин-та. -Баку, 1988. -с. 37-41.

9. Мансуров Т.М. Разработка алгоритмов функционирования специализированных однородных вычислительных структур //IX научно-техническая конференция молодых ученых и специалистов ЦНИИС : Тез. докл. -М., 1990. -I с.

10, Артемьев М.Ю., Мансуров Т.М. Математические методы структурного моделирования задач на отказоустойчивых управляющих вычислительных структурах. -М., 1990. -22с. -Деп. в ЦНТИ "Информсвязь", К- 1671.

■Му