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

министерство общего и профессионального образования российской федерации

Шу(^ки{ШЬсударственнь1й технический университет

•2 2 :;.•:.;) —

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

КОЛОСКОВ , Василий Александрович

УДК 681.3

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

Специальность 05.13.05 "Элементы и устройства вычислительной техники н систем управления"

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

КУРСК 1998

Работа выполнена на кафедре "Вычислительная техника" Курского государственного технического университета

Научный консультант: доктор технических наук,

профессор, академик МАИ ВШ Титов B.C.

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

доктор технических наук, профессор Переделы;кий Г.И. доктор технических наук, профессор Рубанов В.Г. доктор технических наук, профессор Сизов A.C.

Ведущая организация: Тульский государственный университет

Зашита состоится_|__1998 г. в_часоз на заседании

специализированного совета Д 064.50.02. при Курском государственном техническом университете по адресу: 305040 г.Курск, ул. 50 лет Октября, 94. С диссертацией можно ознакомиться в библиотеке униБерситета. Отзывы из автореферат в двух экземплярах, заверенные печатью, просьба направлять по адресу: 305040 г.Курск, ул. 50 лет Октября, 94, КурскГТУ, ученому секретарю специализированного совета Д 064.50.02

Автореферат разослан "_"_1998г.

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

кандидат технических наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проолемы. Актуальной проблемой теории и практики :тройств группового логического управления является создание лсоконадежных отказоустойчивых мультимнкроконтроллеров.

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

Проектирование высоконадежных отказоустойчивых

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

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

Методы скользящего резервирования, применяемые в процессорны* тгрпцах и "являющиеся разновидностью метода динамическою ' кэширования, основаны на использовании встраиваемого в матричное трона во коммутатора для обхода 01 казавшпх элементов и перо 1:11 ру (ье юршмов в устроиаво после проведения перестройки с помощью фойава верхнею уровня управления Выполнение угнанной

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

Поэтому возникла необходимость в разработке основ теории I принципов построения мультимикроконтроллеров, обеспечивающие требуемую оперативную отказоустойчивость реализуемых функции ( минимальными аппаратурными затратами. Указанная откаюустончивосп достижима в функционально-избыточных мультимикроконтроллерпх путе\ виртуального переразмещения алгоритмов его модулей и перестроим логической структуры (самоорганизации) мультимикроконтроллера н; множестве основных и избыточных элементов, включающих исправные I отказавшие. Обеспечение автоматического перераспределения алгоритма без использования устройства верхнего уровня возможно при лсренастроикч функционально-избыточных микроконтроллеров, а автоматическая замен: отказавших модулей сети осуществима перенастройкой функционально-избыточного коммутатора мультимикроконтроллера без встраивать дополнительного коммутатора для обхода отказавших элементов.

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

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

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

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

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

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

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

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

1. Предложен подход к обеспечению операшвнон о1ка<о\сюнчшкч.тн мулыимнкроконгроллеров пугем структурной п ;lti оршмнческой самоорганизации ММК, заключающихся в виртуальном переразметеннп алгоритмов управления и пир iy алыми перестройке связей между микроконтроллерами на множестве работоа\особ)iых МК.

2. Для реализации подхода предложена модель и рафабоганм

принципы построения матричного структурно _ и фуикпионально-

тбыточпого мультимнкроконтроллера с ммогофункциона льнымн

динамическими микроконтроллерами, позволившие выполнить сколыяшсе

0

|>е копирование со едпитм и вирпа/н.ные переразмешсиия и перестроим ММК

3 Рафабогаиы основы ivojmih отказоустойчивы \

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

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

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

6. Определена операция виртуального сдвига как операция взвешивания вершин графа структуры ММК, обеспечивающая решение третьего заключительного этапа задачи самоорганизацин. и перераспределение номеров алгоритмов между ■ работоспособными микроконтроллерами и разработан «тлгоригм определения мнолсс! I алгоритмов управления, размещаемых в каждом щ микроконтроллеров основанный на применении введенной операции сцепления члеменмриых фигур, позволяющей вычислять вершины-предшественники на маршрута

¡шсстановлення.

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

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

Рештацня и внедрение пеп'льтатоа диссертационной работы

Лиссертационная работа является обобщением результатов, полученных автором в Курском государственном техническом университете в процессе выполнения в 1980-1997 годах научно-исследовательских рабог. в том числе Международного проекта «Технические системы обработки символьной информации и изображений» (распоряжение Госкомиу и РФ ш 19 02.93. №10), темы Г - 22 "Разработка методов обработки нсааннщмрныч сигналов фазовой информации и создание базовой информационной измерительной системы" (1992-1995 г.г.), темы Г - 16 "Создание базовой архитектуры для информационных гнпертехнологий и обработки изображении" (1993 г.), финансируемых по Единому заказу-наряду комитета по Bill № 10-36-63/10-02-11 от 15.05*92 г. и Комитета по ВШ № 10-36-67 HH/I0-02-II от 50 04.93 г. соответственно.

Результаты исследований прошли нпавмеимую экспертизу и включены в межпуювекую научно-техническу ю программу «Многопроцессорные 'ЖМ с параллельной структурой и системы риртуалыюй рехзьностн» (Прик.и по мннис1срству общею и профессионального обра мвания № 572 от 02 i)3 j

Результаты работы использованы при создании отказоустойчивы' средств программируемых логических систем управления в АО «Счетчаш» НИгорнорудный институт (Украина), АО «Прибор», в/ч 25714.

Теоретические и практические материалы диссертационной работа использованы в учебном процессе Курского государственного техническо! I университета при разработке курсов «Отказоустойчивая организации процессоров и ЭВМ», «Структурно-топологическое проектирование ")НМ» а также в лабораторном практикуме, практических занятиях и лекциопно\ курсе по дисциплине «Организация ЭВМ, комплексов и систем».

Материалы исследований нашли отражение в технических решениях защищенных авторскими свидетельствами и патентами РФ.

Апробация работы. Основные положения диссертационной район, докладывались и обсуждались на следующих симпозиумах и семинарах. V симпозиум «Логическое управление в промышленности» (г Тбилиси, 19К. г.), Всесоюзное научно-техническое совещание «Микроироцсссорньи средства вычислительной техники в системах связи и управления» (г. Рига 1984 г.). Всесоюзный семинар «Проектирование систем диагностики* (г.Ростов-на-Дону, 1984 г.), Всесоюзный семинар «Отказоустойчивое!I многопроцессорных вычислительных систем» (Ростов-Туапсе, 1985 г.) научно-технический семинар «Микропроцессорные системы для управление технологическими процессами» (г. Ленинград, 1985 г.), семина) «Помехоустойчивость автоматизированных систем управления» (г Киев РДЭНТП, 1986 г.), научно-технический семинар «Методы исследования г обеспечения надежности сложных технических систем» (г. Ростов-на-Дону 1989 г.), Всесоюзная конференция «Микропроцессорные комплексы дл» управления технологическими процессами» (г. Грозный, 19X9 г ) Международная конференция «Системный анализ, моделирование г управление сложными процессами и объектами на ба¡с ЭВМ» (г Ташкеш 149? г.), 7-я и 8-я Международные школы-семинары «Микропроцессорные системы связи и управления на железнодорожном транспорте» (Алушта

Харьков, 1994, 1995 гг.), 3-й Российский научно-технический семинар лНейроестевые н транспьютерные технологии и пути их использования в специальных технических комплексах» (г.Курск, 1994 г.), Международные конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г.Курск, 1993, 1995, 1997 гг.), Международные научно-технические конференции «Новые информационные технологии и системы» (г. Пета, 1994, 1997 гг.), научно-технические конференции «Вибрационные машины и технологии» (г.Курск, 1995,1997 гг.), 3-я Международная конференция «Измерение, контроль и автоматизация производствг'чнт процессов» (ИКАПП-94) (г. Барнаул, 1994 г.), Республиканская конференция «Приборы и приборные системы» (г. Тула, 1994 г.), 2-я Всероссийская научно-техническая конференция с международным участием «Электроника и информатика - 97» (г. Зеленоград, 1997 г.), 2-я Международная конференция по проблемам физической метрологии Р12МЕТ'-96 (г. Санкт-Петербург, Россия, 1996 г.), научно-технические конференции и семинары КурскГТУ (1980-1998 гг.).

Публикации. Основные результаты диссертационной работы опубликованы в трех монотрафиях, 37 статьях, в том числе в журналах РАН «Автомашка и телемеханика», Сиб. отд. АН «Автометрия», Латв. АН «Автоматика и вычислительная техника», «Изв. вузов. Приборостроение» и защищены 8 авторскими свидетельствами на изобретение, б патентами и 3 решениями на их выдачу.

Оспиднш' научные положат», «ыносюше на ющиту

1. Подход . к обеспечению оперативной, отказоустойчивости мультимикроконтроллерол путем структурной и алгоритмической самоорганнзании ММК, заключающихся и виртуальном переразмещении алгоритмов упрлпленмч ■ и виртуальной перестройке связей микроконтроллеров.

2. Модель м.нрпчнош е|р\кт\рно- и функционально избыточного

мультимнкроконтроллера с многофункциональными динамическими микроконтроллерами.

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

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

5. Операции разметки, поворота стрелки. Поиск и исследование преобразований графа перемещений и критичных фигур.

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

7. Каноническая структура элемента самоорганизующсго слоя. Принципы построения слоя самоорганизации.

8. Структурно-функциональная организация отказоустойчивого мультимикрокошроллсра, реализующего виртуальное переразмещение алгоритмов управления и виртуальную перестройку связей элементов ММК.

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

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

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

В главе I «Особенности организации отказоустойчивых :амоорганиз\1ошихся мулы »микроконтроллеров» рассмотрены топлении и » .цианизации устройств группового логического управления, к нелепы xiumiii.ie понятия и определения в области отказоустойчивых ММК. лапа карамериегнка задачи ноароения отказоустойчивою ММК н рассмофены особенности распределения слоя самоорганизации в ММК.

Проектированию логических управляющих устройств посвящено большое число работ М. А. Гаврилова, И. П. Прапппмпидн, А Л Закрекского, Д А. Поспелова, Ii. А о Горбатова, В. Г. Лазарева, В. II варшавского, С. A Юдиикого, К. П. Балашова, В Е Хазацкого, В Н Захарова, А. А Амбарцумяиа, К). И. Арсеньева и других авторов Лнадш icineiniiiii ¡viiiiiiihh uipoiicui групповою логического управления помыл, ■по >ффек1ншшй opi ашкачией его основного блока, ycipoiieiBa pca.ni мини юшческич алюрнтмов. является сеть пространственно сосредоточенных и а.н оригчнчеекм распределенных программируемых ло) ичееких микрокон |ролле|)ов, названная мулыимикроконтроллером, нос ipoeime которою башруется на принципах параллельности, модульности, однородности. Передача сообщений в сети хшкрокошроллерои осушеовляси-я ipainniin.im способом.

l'accMoipeiiiiio вопросов обеспечения надежное! и npoiраммируемых управляющих \cipoiiein, однородных многопроцессорных с гр\ к > > j1 посвящены работы II. И Пархоменко, А. И. Горяшко, А. П Галушкина. В. И. Варшавского, В. А Воробьева, И. В. Лаходмпоиой. А Н Мямлина. Г С Согомоняна, Л. Ь. Гронсберга, В. П Максимова, В. JI. Харченко. М Ф Каравая, Ii. П. Туруш, А. К. Ьаумса, Л Апнжениса, Д К Прадхана, И Корена, С. Куна, М. Сами, Р. Стефапелдн,'' Эван ¡а, Дж. MaKxyjpia и ;ip\i их автров Проведенный об top состояния и 1снленций ра штия в органнмиин ожаюусюичивых .ьчпческцх ycipoiicin по ¡водил выявим, основные особениосш. на котрых должно ба шровак.ся построения отказоустойчивых м>. и. I им и кром 411 роллеров

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

В работе определены понятия надежности, бсчотказиост работоспособности, отказа мультимикроконтроллера. Самоорганизаш мультимикроконтроллера основана на его адаптации к отказа многофункциональных микроконтроллеров путем перераспределен) функций работоспособных МК (алгоритмическая самооргашмация) перестройкой связи ММК (структурная самоорганизация). Самоорпипнаш достигнута с помощью так называемого слоя самоорганизаннн Сто самоорганизации представляет собой совокупность алгоритмических аппаратурных средств, обеспечивающих перераспределение функций в ММ1 и перестройку его связей. Для мультимикроконтроллера, обладпющо свойством оперативной отказоустойчивости, предложена модель сами устройства, в виде графовой решетки замкнутыми границами й его члемеш - настраиваемого многофункционального микроконтроллера. Введенн дополнительной строю! или столбца элементов ММК, размещение вполн< определенных копий алгоритмов управления в каждом н микроконтроллеров позволили реализовать скользящее резервирование I статическое переразмещение при отказах элементов. Замена отказавши:« элементов путем перенумерация работоспособных микроконтроллеров дл> восстановления связей МК и перенастройки каждого из них выбором соответсвующей копни алгоритма для перераспределения функции выполняется средствами самоорганизации. Сохранение сияшосш и ММК с отказавшим)! элементами достигается при условии выполнения неисправным микроконтроллером функции соединительного элемента, обеспечивающею трансляции управляющего сообщен)»! одному из соседним ММК Таким образом, обеспечивается ыфтуалыюг персразмсшснис апорт меч; управления и ьиртуалыш перестройка сквсй в ММК. Поло; приемник,;

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

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

Самоорганизация мультимнкрокоитроллера возможна, если распределение П частных алгоритмов управления между требуемым числом микроконтроллеров для размещения общего алгоритма управления, являющихся исправными, осуществлено таким образом. чю при любой допустимой комбинации отказавших процессоров, отображаемо!) на микроконтроллер, частный алгоритм и," принадлежит ограниченном) нодмножеиву II,. хранимых в микроконтроллере алгоритмов II {И......П,.....П„,П„и.....П,,.^ п,-!»,,^,....,!!^}, и" е П,. где а,.....ак

номера алюршмо» управления, выполняемых т м микрокошроллером в тависимости от ожшовой ситуации при 1> м методе самоорганизации; К|, • число программных модулей алгоритмов управления (число динамических млороск микроконтроллера при смене огказопых ситуации) дт* метода самоорганизации I),

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

Чюбы выполнялась неренаоройка микроконтроллеров для всех лот с (iimi.iv кнмбшмций (нкаюв. необходимо предварите "(.но. перед применением мч.тынмпкрнкишроллерл.' 'наши мощность и соски:

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

Вычисление кодов абонентских адресов многофункциональных микроконтроллеров и адресов памяти частных алгоритмов управления осуществляется с помощью слоя самоорганизации в период смены состояния ММК: Uso: А(МГ) А(МР), где Uso - алгоритм вычисления колов адресок микроконтроллеров, А(МР) - коды адресов исправных элементов Mi мультимнкроконтроллера до смены состояния, A(M¡ ) - коды адресов исправных микроконтроллеров Mj. ММК после смены состояния.

Алгоритм поиска Un сводится к отображению управляющею сообщения Us с виртуальным адресом приемника А в микроконтроллер ш. имеющий тот же виртуальный адрес A: Un'. Us(A) -» ni (А).

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

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

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

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

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

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

Для описания структурных и алгоритмических ресурсов ММК'. а также управления восстановлением структур! их связей н персразмешениеч алюрщмоп введены графовые модели, являющие .я разновидностями пеориен|ированны\ и ориентированных графовых решеток, опрелелепи нопшия |рафов струюурм, перемещений, маршрута восстановления, дерен.) и сет восстановлений самиор! ¡ннкукнией сет.

и

Графоструктурный подход к решению задачи елмоорганнзпшн основан на выполнении распределенных операций Оч преобразовать введенных графовых моделей: Оя = <Ор, Оцс, Ос>, где Оч - совокупноси распределенных операций преобразования графовых моделей ММК. О, операция единичной разметки дуг графа би перемещении; Оц< операция поворота стрелки в графе бП перемещений; Ос - операция виртуальною сдвига логических адресов в графе вм структуры.

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

Операция Ос разметки состоит в единичном взвешивании дуг II фафа 6,, =(\\0) перемещений, выделяющем самоорганизующую сеть (¡, еа 1( перемещений с единичными дугами.

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

Операция Оцс поворота стрелки состоит в выделении из деревьев и сетей восстановления, образующих самоорганизующую сеть ¿¡.еО,,. связных изолированных подграфов е<35 <к= 1,К), соответствующих непересекающимся маршрутам восстановления.

Сформированные в результате выполнения операции 01а- подграфы Сд(к = 1,К) однозначно определяют варианты устранения последствии каждого из К отказов в решетке б п.

Операция Ос виртуального сдвига состоит в изменении песо» вершин графа 0>., структуры,-топологически соответствующим вершинам графов* бд еб5(к = ПК).

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

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

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

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

Конфигурации кратчайших маршрутов и возможность их построения тя конкрешыч огказовых ситуаций в ММК зависят от правил выбора [шранлеиня перемещения. (метода перерлзмешення) Задача (чооркннпанни сводится к поиску такого метода переразмещення, который .хво.тяе! получим, максимальное значение; коэффициента исправляющей

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

Топология самоорганизующих сетей определяется метолом с построения, учитывающим число направлений перемещения алгоритмов, н состав и приоритетность направлений при разметке дуг графа псрсмещенш В работе выполнена классификация методов построения самоорганизующн сетей и выделены две группы: локальных и глобальных методов Метод глобатыюго построения самоорганизующей сети разделены на статические динамические. Анализ рассмотренных методов показал, что компромт между требованиями на количество хранимых в элементах ММК кони алгоритмов достигается при выборе методов глобального линамичссмх направленного поиска самоорганизующей сети. Среди предложоннь методов в работе разработаны и исследованы методы динамическо! построения самоорганизующей сети с анализом комбинаций отказов в crpoi графовой решетки (MDV), строках (MDK), смежных вершинах (MDS) двумя (1ц), тремя (Iq), четырьмя (lj) направлениями перемещен! алгоритмов. Указанные методы имеют гибкие правила разметки дуг rpat] перемещений и не требуют значительной алгоритмической избыточное! при их реализации. В дальнейшем для простоты изложения будем назыпа" самоорганнзующие сети, построенные с учетом отказов смежных верпп<

(методы MDSIi)NE-ccTHMn,T.e. сетями с просмотром соседних (neiyhhourn examination) вершин, а сети с просмотром комбинации отказов в граф< решетке (методы MDVI£, MDKI,J,) назовём ВЕ-сетями, т.е. сетями расширенным просмотром (broadened examination) вершим, сети беспрноритетной разметкой (MDSGI/,) графа перемещений назовем W; сетями (without priorities).

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

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

Для учета состояний («работоспособен / отказал») вершин графа С,,перемещений введены операции Ор1 разметки исходящих дуг вершин строки графа и сформулированы правила их выполнения.

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

Утверждение ' I . Если хотя бы для одной вершины \-чеб„

(| = 1.М. | = I, N = |) с состоянием работоспособности г„ и числами (.','. входных и [.")4Ч единичных дуг справедливо соотношение +гп >1.'!ыч. ю псрер;пмс(ценне алгоритмов невозможно.

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

В общем случае операция 0'к разметки 1-ой строки вершин

{\'„! с би 0 = I, N1) сводится к отображению состояний и входных дуг вершин в область значений весов их выходных луг:

где - набор значении весов входных дуг вершин ¡-ой строк» графа б,,; У.' - набор значений весов вершин ¡-ой строки графа О,,; /.'1 набор значений весов вершин (¡-1)-ой строки глзфа б,,;

- набор значении весов першнн 0 Ц-ой строки графа й„ . - набор шачешш весов выходных дуг вершин ¡-ой строки графа О ,

Операция разметки строки (О^) может быть представлена к;н композиция элементарных операций разметки выходных дуг для каждой и вершин:

Ore

i-i

где OJ! - операция разметки выходных ребер для вершины v„ е Gn

В общем виде 0¡¡ независимо от метода построения саморганн iviomei сети можно представить в виде: OJj. :S)j, , , k ¡—, k „, где S¡' S"

набор значений весов входных и выходных дуг для вершины v„ е G,,; Z"

набор значений весов вершин, смежных вершине Vy е G„; K1J+i, k„ -значения переменных, характеризующих изменение правила разметки выходных дуг вершины v(J и v,j.] для разных методов самоорганизации.

Синтез операции О* распределенной разметки вершин графа G„.

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

1. Разработка представлении функция отображения операции разметки Oj, на основании правил (О,., -г- 0,.6) разметки выходных дуг для различных методов построения самоорганизующих сетей. На данном этапе определяется состав входных и выходных переменных функции отображения.

2. Выделение допустимых комбинаций входных дуг вершины v„ е Gn .для выбранного метода построения самоорганизующей сети.

3. Получение правил отображения для на основании допустимыч комбинаций входных ребер Бсршины v .

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

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

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

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

О и р е д е л е и и с 1 . Вершины (v,,} е самоорганизующен сети, для ;оторых полустепени захода и исхода единичных дуг имеют значение 1)л(р(у,,)> 1), называются критичными.

Определение 2. Подграф Ф^.О) графа 011> состоящий щ

>дной критичной вершины <3$ со множествами (у,, ,,. %•„!, {у,„ \'„ ,г)с0 инцидентных си по входам и выходам дуг, называется крнтнчноН^игурой

Определение 3. Операцией Оцс поворота сделки для критичной |>нгуры Ф(Уу,0)сО!{, имеющей вершину V,, ,„ предшественник и вершину V,/>.,!» последователь ;пя критичной вершины у(|, называется преобразование

•>пс-. Ф(у,.Г))-2^Ми(КМ1л-,),(у,л>.#)К гдсМ = {М,.....М......м„;

множество дуг им да (у„ „Л,, „), порождаемых заменой пар дуг (у.1)Г, V,,)

(v.rv.t,j<)> выполняемой для всех v^j, е {\ via ja} при значении вес

и для всех e{Vi) прик.й«1 и для всех \й >jt e{V*„ \viWP).

Каждую отдельную замену пар дуг критичной фигуры одной дуго будем называть, соответственно, подоперацией поворота стрелки критично фигуры, при этом операция Опс поворота стрелки интерпретируете набором подопераций: Gr)c=NOI.

В диссертационной работе сформулирована и решена задач определения оптимального множества подопераций OIK: дл

самоорганизуются сета Gs с фиксированным множеством критичны: фигур.

Эффективное решение находится среди множества Р решений отличающихся составом и мощностью подмножеств подопераций:

P=NO„...,NO„...,NOn.

Из множества Р допустимых решений выбирается решение i минимальным значением КЭ1 коэффициента эффективности покрытия

КЭ1 = min{Klx}, х = 1,2,...,П,

где Юг -функция качества покрытия, соответствующая мощност» подмножества N0, подопераций, обеспечивающих покрытие все? критичных фигур сети.

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

Так, если выполнение операции О^ преобразования Gs состоит i реализации подмножества элементарных подопераций, составляюши>

некоторое оптимальное покрытие N0« = {О^.-.О^.-.О^} (т,е (0,1,...ДЛ), го для произвольной вершины уые 65 справедливо следующие утверждение.

Утверждение 2. Предшественниками вершины уыеОх могут стать все некритичные вершины из множества V,,. а также вершины V,, |Ге Сц. инцидентные по выходам дугам (у^г,уы), порождаемым при выполнении подопераций преобразования (Уй^^Х^.Уц)—2й—*(у„.£,уц) из покрывающего (38 набора N0, подопераций: N0, = }.

Согласно утверждению, общее число вершнн-предшественников определяется не только множеством виртуальных входных "соседей", появляющихся в результате преобразования 6;. с помощью набора МО, подопераций, но и множеством некритичных вершин с , которые не участвуют в преобразованиях, но изначально присутствуют в сети Для таких вершин У^еУ", справедливо1

((2н = 1)Л(р(У„) = 0)^((г,) = 0)л(р(у^)=1)), поэтому состав множества V,1,' будет определяться ориентацией исходящих из некритичных вершин дут ллч фиксированного метода построения самоорганизуюшей сети С!ч.

Множества V," всршин-предшествспников для произвольной верингм учеб8 определяется как Ч" = Уп„''I) V,4, где V;' - множество вершин-предшественников, порождаемое преобразованием с помощью набора N0, подопераций.

В работе рассмотрено решение задачи определения множества вершин-

предшественников для фиксированного метода иостроенич

самоорганизуюшей сечи с учетом покрывающего критичные фигуры набор.)

в

подопераций. Для этого были.введены понятия э.тсмсшарных юришншльиыч Ф,-, Ф»с <;ч. вертикальных Фн.Фнс(*1ч. диагональных Ф_,,ФЛ с (¡ч,

фд„фд)с08 фигур, самоорганизующей сети, а также фигур Ф" , Ф|' .

Ф°(Ф°1,), порождаемых подоперацией О, еЫО,,, и операций горизонтального [>, вертикального Х7 и диагональных с^

сцеплений элементарных фигур <35.

В работе разработан алгоритм определения множеств У,",. »У* вершин-предшественников, основанный на введенных понятиях элементарных фигур и операций сцепления.

Множество Уу = У^, и V* вершин-предшественников для каждой из

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

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

Для выбора среда множества Р, £ Р равноценных по числу подопераций (с одинаковым значением КЭ() наборов введена функция К.2, качества покрытия: К2, =|уЯ, Р, ={N0 },уе{1,2,...,я,...,П), где У," -

О

множество вершин-предшественников для произвольной вершины V, е

Выбирается покрывающий набор К07еР, (уе {1,2,____тг,...,П}> из

множества решений Р, £ Р, обеспечивающий минимальное значение коэффициента эффективности КЭ2: Кэ, = гтп{К2е).

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

следующие основщае этапа:

1. Формирование множества Ф = {Фр)(р = ГР) критичных фигур ддч фиксированного метода построения самоорганиз; тощей сети Сх.

2. Генерация множества 0={0,}(1=Ш подопераций преобразования критичных фигур Ф .

3. Формирование множества Р = {НОя}(и = 1,П) наборов подопераций, применимых к преобразованию каждой критичной фигуры

ФреФ(р = ГР).

4. Поиск оптимальных по критерию К-„ покрытий Р, с Р множества Ф= Ф,,Ф2,...,Фр фигур наборами подопераций из множества

о=о„о2.....(V

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

В работе рассмотрена реализация алгоритма синтеза операции Оцс для разновидностей ВЕ-сетей, построенных с использованием методов N11)1']' (ВЕУ-сетн), МОК1* (ВЕК-сети), (ВЕО-сети), ИЕ-сетей, построенных

с использованием методов МБ31д п М051о, а также для У/Р-сетей (метод ;\Ш5С1о). Показано,

что операция Оцс для ВЕ-сетен состоит из одной подоперации, а множество V,] вершин-предшественников для ВЕУ-сётн включает ={у;для ВЕК-сети это множество состоит

Аналогично это множество описывается для \УР-сетей. Операция 0Пс для КЕ-сетн (метод М051(3|) реализована тремч подоперациями, при этом множество вершин-предшественников состой!

из следующих вершин У^3 = ¿-г}- Синтез операции

Опс ДДя ИЕ-сети (метод МОБ^) привел к набору, состоящему из шест и подопераций, и множеству У^, вершин-предшественников, включающему восемь вершин: У^ =

Четвертая глава «Исследование предельных возможностей методов самоорганизации» посвящена рассмотрению завершающего зтапа самоорганизации ММК и оценке возможностей операций самоорганизации В работе предварительно определена операция Ос- виртуального сдвига

Определение 4. Операцией 0( виртуального сдвига называется ишсшиванис вершины \'иеОм (I = 1,М, ] = I.N + I) графа См структуры носом ау=(10), если соответствующая ей вершина \',,еС,, в графе перемещений С!п имеет вес либо весом а,,-0оуа). если соответствующая вершина \„с б,, имеет единичную входную дугу вида: (у,,,.,,,, у„), либо весом а„= <*> в остальных случаях.

Реализация операции Ос виртуального сдвига предполагает прием номера (»а.огх) вершины-предшественника для v,, со вполне определенною направления (горизонтального (Г), вертикального (В), диакшадмичо (Д. Д1)). Для максимального набора направлений перемещения I,' множество У," включает: V,'1 = V,'! и У/{ и У;'| и У;{,.

Па этапе построения маршрутов в с помощью операции (),г для произвольной вершины ууе Оч определяются номера вершин-предшественников для множества вершин УД1^, а также ориентация (направление) дуги, но ко горой осуществляемся спя п. \„ со своим предшественником \-„1>м. '

Возможные варианты реалиинпи операции О, для прои шотмюп вершины 'V,, с учетом результатов выполнения операции 01Л д/и

исследуемых разновидностей самоорганизующих ВЕ и ЫК-сетей представлены а работе таблицами. Пример табличного описания операции

Ос для ВЕО-сети (метод МОК1о) показан в таблице 1.

Таблица I

Операция сдвига для вершины Vjj ВЕ-сети (метод MDKI;')

Наборы вершин-предшественников 3ii

фг ф„

V* U-1 - -

-• 1+1 j -

- i+lj-1 -

V'j - - i+lj-1

v-j=0 •j

На рис. 1 приведен пример выполнения операции Ос самоорганизации для метода MDKIq . Результат преобразования графа Gn с помощью операции Ор распределенной разметки представлен на рис. 1а. На рис. 16 показан результат применения операции Оцс поворота стрелки, а на рис. 1в иллюстрируется выполнение операции Ос сдвига.

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

В работе исследована ¿-безотказность, достижимая в <

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

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

тостроенин самоорганизующей сети методом МП\Ч(2,, позволяет создавал, '-безотказные структуры мультимикроконтроллеров.

Методы виртуального перемещения алгоритмов .управления.

основанные на построении самооргаиизующнх сетей методами МОК!,,.

КГОК^. МОБ^, МОБ^о, позволяют создавать 3-безотказные структуры Метод виртуального перемещения алгоритмов управления, основанный на построении самоорганизующей сети методом МОЯ^, позволяет создавать I-безотказные структуры мультимикроконтроллеров.

Анализ значений показателя ^безотказности для операций Ом, (Ь номер операции самоорганизации) показал, что показатель с!^ связан с числом 1|, допустимых направлений перемещения алгоритмов соотношениями

¿2 = Ь + 1 для метода МОК1ц построения самоорганнзующей сети и с!ь

(Ь=1,3,4,5) для остальных методов (МОУ^, МОК1о, МОБО^, МО.Ч1о. МОБ!® соответственно).

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

Результаты исследования алгоритмической избыточности Кь и <1-безотказности (1), для каждого из методов •самоорганизации по (полили с помощью коэффициента эффективности оценить относительные алгоритмические затраты на обеспечение отказоустойчивости И;,:

V _ КЬ Як

зс

Покачано, что наименьшее значение коэффициента КэЬ, те наименьшие относительные затраты для 11 2 обеспечивает мею.

самоорганизации, основанный на методе МО\П(2, попросит самоорганизукпией еетн с К) = 2.

Для при максимальной коррекции отказов большей крат нос и

наиболее эффективен по КэЬ метол МОК!;1,. При нежестких требованиях » исправляющей способности (кратности ошибок большей трех) выбор метол, самоорганизации зависит от затрат на реализацию элемента с. и г. самоорганизации. Вопросы построения элемента слоя самооргашпацш Г>\.1\1 рассмогрены «пятой сыне

Досшжение 01кашустйчии0сп! с ЛЫ свжано с увеличением чпе.1. используемых напранлений перемещения алгоритмов и принолш I существеннсчу росту относительных алгоритмических затр;н н. обеспечение отказоустойчивости, которые для самоориннпующих К'Н-сскч составляют, как показано, дне относительные единицы для чеп.фе допус шмых направлений перемещения.

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

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

Наибольший шлнгрыш в исправляющей способности дики мскм( самоорглни <лиии, использующие модель (»„" (рафокой решегкн ¡лмкнчтымн (рашшлчк.

Среди мс1о:нш сачооргашшшш нанлучтие ре плыли.! и

^флшин.'сш^ н исправляющей способное!и пошодяе! доешчь мею основанный на посфоенпи В!'1)-ее1сй (М1Ж1,',). >41)11.111.1101111111 н|

реализации Ор как комбинации отказавших вершин сети, зак и состянич смежных вершин.

Обеспечение отказоустойчивое и мулътимикроконтроллера для малой кратности отказов реализуется примерно с одинаковой эффективностью методами самоорганизации, основанными на построении ВП V-. В1-К-. Н1.П-. ЫЕ( ]', )-сетей. Поэтому окончательный выбор зависит ог сложности построения слоя самоорганизации для каждого из методов.

Эффект от применения методов самоорганизации проявляется при значении вероятности отказа элемента мультимикроконтролдера. меньшем значения 0.4 (я<0.4) (КЯь>0). Наибольшее приращение • верояшосш безотказной работы за счет исправления отказов методами самооргашманнн достигается в диапазоне значении вероятности отказа элемента ММК [0.08;0.12].

Реализация методов самоорганизации в мультимикроконтроллере позволяет выполнять в нем до семи (1<1<7) реконфигураций с сохранением значений Р;ь большим нуля (Р|,>0), и в среднем три-четыре коррекции отказовых ситуаций до наступления потерн самоорганизации.

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

г.

отказоустойчивого самоорганизующегося мультимикоконтроллера и ею элемента - настраиваемого многофункционального микроконтроллер;!

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

композиционного (объединенного) алгоритма для »деменк самооришизуюшсго слоя, синтеза функциональной схемы >лемеш. самоорганизующего слоя.

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

и" к"

П II ,.» ..'I

Рис 2 Канонически;! 11р\к1\ра иемеша самоорынн (Мчтею е.юз

Автомат А| (указатель возможных перемещений) выполняет размет кл 1афа перемещений и указание возможных виртуальных перемещений 1горнтма соответствующего автомату микроконтроллера. С помощью ¡томата Л; осуществляется выбор направления виртуальной тратит :редачи и направления, с которого виртуально принимается алгоритм аким образом, автомат А: (определитель направления приема и передачи) ормирует маршрут восстановления, включающий виртуальное гремещение алгоритма между двумя соседними (передатчиком и риемником) автомату А; микроконтроллерами. Автомат Л; иасфанине! гязаиный с ним (у) - и микроконтроллер на соответствующий биоритм. 1 е. галнзует виртуальный сдвиг и является настройщиком ногофункцнонального автомата.

Основными этапами синтеза таблицы функционирования автомата темента самоорганизующего слоя являются: описание входного и ыхолного алфавитов элемента самоорганнзующего слоя для осматриваемого метода; кодирование входных и выходных сигналов темента самоорганнзующего слоя; составление таблицы функционирования тя автомата элемента самоорганнзующего слоя.

Автомат А) вычисляет функции 5-'ич, К"цх, РО„ на основании значений тгументов К^, глг Б^» {б|', множество выходных

¡¡ременных, характеризующих направления возможного виртуальною гречешення алгоритма (у) - го микроконтроллера; выходные

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

икроконтроллера и заканчивая (у) - м микроконтроллером включительно: Оч- выходные переменные, индицирующие возможность самоо^пшнаннм г< появившейся конфигурация отказоп; ¡х1,1"1, к',*1..)- миол.еет,".; шдных переменных, х.чракт ернзуюшнх созмонсные псрс'ч-шсш- <

алгоритмов смежных микроконтроллеров; = |/и, г,,, 11 - множссп входных переменных, указывающих состояния «рибоюснособсн <нка¡а. смежных мнкрокотроллеров; К^ - входные переменные, фиксируют! наличие критичной конфигурации откачавших мнкрокотроллеров в с (роке начиная с крайнего правого микроконтроллера и заканчивая 0, ¡11 многофункциональным автоматом включительно.

Связь между входными и выходными неременными в автоматах А|, <л Л^ определяется правилами построения самооргапизующей сет д. операций разметки 0|!, ||)ормироиан((я маршруток восстановления (л. операций поиоро1а стрелки О",,.) и выполнения виртуального сдвша (д. операции сдвига П|' (соответственно:

п'ь с" 7" к-" Ч'1 к'" го

и,,. л к„х -» л„т 1ч„11Ч ти„,

Ф и;; рц, -> ю„,

<х'а - {о(> о3____" множескю переменных. характерн (\ юше

направление иир|уал1>но1о п|)иема алгоршма о) смежно! микрокои(роллера, а,, а1 - переменные, укатывающие на внр1уа.н>пы прием соответственно с горизонтальною и вертикальною паиранленш Р»и\ множество подмножеств , |К иир|\а.н.н

перемешаемых »и ^ершины (у) алгоритмов. >. !

подмпожесшо виртуально перемещаемых алюрншов в юрничиа.и.по направлении; |5И- а'И'оршм, принял,ш для перемещения с юринииалмкн направления. алгоршм. IтриияI¡1 для перемещения е вершкалмкч н.трапленпч, Рм-- " нодмноже». мю онрпально перемещаема

¡горитмов в вертикальном направлении; Р2г алгоритм, принятый ¿тля

гремещення с горизонтального направления; Р22- алгоритм, принятый лля

¡ремещення с вертикального направления; а[|- множество переменных.

Зеспечивающих настройку микроконтроллера на соответствующий 1горнтм и соответствующий адрес микроконтроллера в сети.

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

Рис. 3. Фрагмент структуры самоорганнзующего слоя мультамикроконтроллера

В работе рассмотрено построение аппаратурных средств с; к самоорганизации для операций О, самоорганизации, основанных на метла формирования и преобразования В12-, ЫЕ-, \УР- сетей.

Техническое решение на ячейку самоорганнзуюшего слоя затишен патентом Р.Ф. ("Ячейка однородной среды").

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

самосннхронизирусмости.

Рс<ии'.иния перечисленных свойси: мнкрокошроллера обеспечиваете средствами самонастранваемости и самосинхронизации, выполняющим функции выбора: алгоритма управления (программы или мпкронротраммы СОСП1ЯННИ ал три 1м в управления, синхронною сосюянию обьекта. адрес внр| уа. н.ною микроконтроллера. направления передачи пршшмаюти управляющих сообщений.

Первые две функции с.ынолшшнся устройством обработки. а фен.я четвертая - коммуникационным устройством.

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

I{ас(ройка коммуникационного устройства многофункниопалыкк' микроконтроллера помимо реалшации функции выбора виртуальною адрес мпкрокошроллера пь'/оочаст ад.зшивнын выбор алюршма вычнелени н.шр.шзеннм передаваемою иди ретранслируемою И) мнкрокош роллер сообщения в мг.нсимостп о( опюшенни кодов инр|уалы1ою и (|ш »песком | :'|\чт1\!!!е!пешим о) адресов мнкрокошролдера п кода нирпалыюю адрес \:нчр,.м>м им I К'рд !- с1-0'чцении

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

0 виртуальному адресу в сообщении. Такой поиск позволяет в случае ¿обнаружения абонента по адресу, соответствующему физическому адресу сообщении, осуществить просмотр всех микроконтроллеров, которые мот ыть настроены на искомый виртуальный микроконтроллер. Выбор аправлення перемещения сообщения при таком просмотре выполняется с омощью кода настройки в сообщении. Код настройки обеспечивает выбор лгоритма вычисления направления перемещения ретранслируемою »общения. Для каждого из методов самоорганизации известно множество икроконтроллеров резервирующих микроконтроллер_(ц). Полому нетрудно айти маршрут просмотра соседних микроконтроллеров и пос!роить лгоритм вычисления направлений перемещения сообщений.

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

Разработанные структурные организации микроконтроллеров нашли

тра-хенне в технических решениях на модули микроконтроллерной сети и

*

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

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

с'о-1

и

Рис. 4. Функциональная схема ')(.'()

р.еслишкасал модуль (| - I, ¡)и.ш пижеа о расположенный.

■ -- если не (ик;иал ни один п) модулей фр;н мен га

^ 1

(столона, включая (I - I, ¡). 11еремепная описывает состояние ¡-1 о столона мнкрокон(роллеров П. если отка ¡ал модуль сюлбца у.

V;

О, сели все модули сюлбца работоспособны.

Па технические разработки по оркипнаипн мультнмпкроконфил а-р прелетиплеино! о дискретом мнкроконфоллерной сен.ю. и г лк х мулмнмпкроконфо.мернон скисмон, получены решении о выли1 шиенюв I' Ф.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ В диссертационной работе мешена научи».-техническая проблема строения отказоустойчивых самоорганизующихся логических льтнмикроконтроллеров для создания высоконадежных и оизводительных вычислительных и управляющих систем в омышленности, транспорте, энергетике, связи, научном экснеримете ганочные комплексы, гибкие модули механообработки, коллскшвы орочных н сортировочных манипуляторов, мафнчные мультипроцессоры томатн шрованиые средства проведения научного эксперимента и т д ).

При решении проблемы в диссертационной работе получены едующне результаты.

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

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

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

4. Разработан графоструктурный подход к построению основ icopi откаun с(ойчиимч н самооргапи {уюшихея мулыпмикроконфоллср! заключающийся в последовательных преобразованиях (онерлцп еамоор! апн шиш) графовых моделей.

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

(>. Определены правила выполнения онерлшш распределен)! pa-Aieiun, построения самооргашнуюшнх cejen. 1рафа перемещении i 1Лобад1л1ы\ направленных динамической и оашстической cipaiciiiii комбинаций отказов, пошоляющие решим. «адачу первою >ы самоорганизации - распределенного построения cent

7. Введены понятия кригичпой п '»лемешарнои фш>р и операп сцепления, позволившие выполним» шорой пап самоорпнпнлнин построение непересекающихся маршруток и с целью их выделен upe пожени операция новорша стрелки для рленроде. jciijioj о нреойра ¡oisaii casioopi ami линией сети, состоящая hi оиельных подопераи реконфигурации спяten кришчпы.х фшур.

8. Сформулирована и решена задача определения опшмальною пабо подоперации операции поворот стрелки для нокрьппя множест кртичныч фшур са.мооркнппуюшем ест и, обладающею мниимальн мощностью и урождающею минимальное число верши предшественников, что muBoniei спиши. а.п ортмичесьуы н юьмочтч п c.moopiiwji !>ющемся м\ лынмш.рокои (роллере.

Определена onep.uin-i нщталмюю елвша как оперт распределенною ь тепппыннч ьерншн i ip\ к i \ pnoi и i рафа pea iu .-м применением операции сцепления t. ue\ic!i)a¡»ju\i фш>рлм н п>м\чс

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

10. Обоснованы условия потери самоорганизации в ре ту.плат с шолнения операции разметки и поворота стрелки и показано, чт «образование BEV ВЕК -, BED - самоорганнзуюшнх сетей не приводи i ix возникновению.

П. Сформулированы условия потери перемещаемого алгоритм ¡равления для самоорганнзуюшнх NE - сетей, позволившие выявлям. Л!кционалышй отказ мультимикрокоитроллера при выполнении операции торота стрелки.

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

13. Разработаны каноническая структурная схема элемента

>

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ 110 МАТЕРИАЛАМ ДИССЕРТАЦИИ

1. Diиатьсв В.M., Колосков. В.А, Tino» B.C. Проекшровл! самоорганизующейся микроконтроллерной сети - Тула ТГУ, 1095 -с.

2. Колосков В.А., Титов B.C. Архитектура отказоустойчивых се самонастраинасмых микроконтроллеров. ~ Курск: КГТУ, 1995. • ПОе

3. Функционально-топологическая организация микропрограмм! мультимнкроконтроллеров группового логического управления 1 Зотов, В.А. Колосков, B.C. Титов, И.В. Арбузов; Гул гос. ун-г Гула IS - 226 с.

-1 Колосков В А. Титов ВС. Методы caMoopi анишнии oi каючеюйчн мультнмнкроконтроллернон сети // Автоматика и те \ - 1998 - № Я

5. Колосков В.А., Титов В С. Управляющая система с самооркиитюи слоем // Автометрия. - 1997. - № 4. - С. 113-120.

6. Колосков В.А., Колоскова Г.П., Титов В С. Саморемош самосннхрпзлция логических мнкроконтроллерных ceieii н И ni н\ Приборостроение. - 1997.2. - С. 43-46.

'7. Колосков В.А. Метод восстановления логической струму мультнмнкрокопфоллерной сегн П Изв. Курск ГГУ - 1997 - Л'" I - С 89.

.8. Колосков В.Л. Медведева М.В. Инвариантные преобразования ло1 нчеа структуры отказоустойчивого самооргани »yioiuei

мультимикроконтроллсра сети // Методы и средства систем обрабо информации. - Курск : Курск ГГУ, 1997. - С. 59-64.

9. Зотов И.В., Колосков В.А. Синхронизация параллельных iipoiieeeoi дискретных мнкроконтроллерных сетях h И ni ТГУ. - 1997 - 1ом Вып. Г- С. 35-39.

10 Колосков ВА. Гитов ВС Построение oik.i ¡оит^нчт самооргашиуюшнхся мулы имнкрокош роллеров систем клнначк

зрения // Сборник материалов 3-й Международной конференции «Распознавание - 97». - Курск, 199?. - С. 19-25.

Зотов И.В., Колосков В.Л., Tirror B.C. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных eeieit Автоматика и вычислительная техника. - 1997. - №5. - С. 51-62 Колосков В.А., Мнневнч JIM. Маршрутизация сообщений к отказоустойчивой микроконтроллерной сети вибрационного стенда Вибрационные машины и технологии. Сб. докл. 3-й Международной научно-технической конференции. - Курск: Курск ГТУ, 1997. - С 243-М(> Колосков В.А., Медведева MB., Миневич JIM. Адаптивная настройка процессора системы технического зрения // Сборник материалов .'-и Международной конференции «Распознавание - 97». - Курск.: Курск ГТУ, 1997.-С. 200-204.

¡.Колосков В.А., Останков Б.Л. Логические мнкроконтроллерные сети с оперативной перестройкой // Информационные процессы, tcxho.ioi ни, системы, коммуникации и сети. - М.: МАИ, 1995. - С. 76-80.

¡.Колоскоа В.А. Концепция построения самоорганизующейся мнкронтроллернон септ // Алгоритмы и системы обработки информации. -Тула: ТГУ, 1995.-С. 150-155.

> Колосков В.А.,Титов B.C. Адаптивная логическая мнкроконтроллерЛая сеть // Ненросстевыс и транспьютерные технологии и пути их использования в специальных технических комплексах. Материалы 3-го научно-технического семинара. - Курск: 1994. - С. 92-97.

7.Колосков В.А..Титов B.C. Распределенная самоорганизация однородной управляющей системы // Изв. вузов. Приборостроение. - 1994. - № 11-12. -С, 20-23.

S Колосков В А. Подход к обеспечению дефектоустойчивости микрокон фоллернен сети // Сборник научных трудов Том 5 Орел Орловский государственный политехнический институт, 1')9$. - С 79-Х5

19.Колосков В.А. Принципы обеспечения дефектоуетойчиноети сна управления // Новые информационные технологии, распознавание обра и анализ изображения. Сб. докладов семинара. Курский иолтехничео институт. - Курск, 1992. - С. 80-85.

20. Колосков В.А., Колоскова Г. II. Перераспределение ресурсов отказоустойчивой мультимикроконтроллернон сети // Труды юбилей! научной конференции. 4.2. Курск ГТУ. - Курск, 1995. - С. 55-59.

21.Колосков В.А., Колоскова Г.П., Типикин И.П. Обеспечсч отказоустойчивости микропроцессорной управляющей системы

, Алгоритмы и структуры систем обработки информации. Сборник научи трудов. - Тула: Тул. ПИ, 1987. - С. 87-94.

22.Колосков В.А., Колоскова ГЛ., Типикин И.П. Архитектура программные средства отказоустойчивых мультипроцессорных систем Вопросы технической диагностики. Межвузовский сборник - Ростов Д. Рост, ннж-строит. нн-т, 1986. - С. 3-7.

23 Бабкин Е.А., Колосков В.А., Колоскова Г.П., Типикин А.II Орпинмам программируемых логических микроконтроллеров И Алгоритмы

■ структуры специализированных вычислительных систем, Сборн научных трудов. - Тула. ТЛИ, 1986. - С.98-103.

24 Колосков В.А., Титов B.C., Бабкин Т.Н. С'амоорышпап дсфектоустойчнвой ситсмы логического управления /Курск гос. тс.чн у

• т. - Курск, 1993. - 27с. - Деп.в ВИНИТИ 21.04.93, №1068-1193.

25.Колосков В.А., Медведева М.В., Медведев A.B., Мнневич JI M , Tin B.C. Графоструктурные основы построения отказоустойчив! рамоорганИзующихдт мультнмикрокоптроллеров / Курск, юс. техн. уты Курск, 1997. - 33с. - Деп.в ВИНИТИ 14.05.97, №1600-1197.

26.Колосков В.А., Титов B.C. Проектирование адаптивной лошчеем м п кро ко и т род л ер! ю и сети / И Международная научно-icxmriec к конференция "Новые информационные icxiuvioihh и системы " (.'борт мак-риалов. ПГГУ. - Пенза, 1994. - С.70-72.

Колосков В.А., Титов B.C. Проектирование адаптивной сети программно-логического управления / III Международная конференция Измерение, контроль, автоматизация производственных процессов (111СЛ1 II 1-94) Сборник докладов. -Барнаул, 1994.- С.20-22.

Колосков В.А. Матричный процессор самоорганизации управляющей сет // Алгоритмы и структуры систем обработки информации. Сборник научных трудов,-Тула: ТГУ, 1994. -С.104-110.

Колосков В.А., Колоскова Г.П., Титов B.C. Отображение адгорш мои отказоустойчивой микроконтроллерной сети / Сборник материалов 2-й Международной конференции "'Распознавание^". - Курск. КГТУ, -1995 - С.233-235.

Колосков В.А. Статическая самоорганизация однородной управляющей системы / Сборник материалов 1-й Международной конференции "Распознавамие-93". - Курск: КПИ, 1993,-С. 138-140. Колосков В А., Бабкин Т.В. Имитационная модель однородной дефектоустойчивой управляющей сети / Сборник материалов 1-й Международной конференции "Распознавание-93". - Курск: КПИ. 1993. -С.143-145.

Колосков В.А., Колоскова Г.П. Перестройка логической структуры

»

микроконтроллерной сети // Перспективные системы управления на ж/д, промышленном транспорте: Материалы 8-й Международной школы-семинара (г.Алушта 7-18 сентября, 1995г) -Харьков, 1995. -С. 19-21. Колосков В.А., Титов B.C. Надежностный анализ дефектоустойчивосш однородных управляющих систем / Системный анализ, моделирование и управление сложными процессами и с.Гп.сктами на öase 'Ш'Д Те>, докладов III Международной конференции ""Системный аиализ-93". Ташкент, 1993. -С.81-82.

Колосков В.А., Бабкин Т В., Титов B.C. Моделирование распределен"» реконфигурации мш.ро контроллерной сети .'/ Приборы и прмГмфные системы. Тезисы докладов научно-технической конференции. ¡у;п.

1994.-C.49-S0.

35. Колосков П Л. Автоматизация проектирования самодиагностируюшеп микроконтроллерной сети // Приборы и приборные системы. Тени докладов научно-технической конференции. - Тула, 1994. - С.51-52.

36.Колосков В.Л., Бабкин Т В. Распределенный алгоритм рсконфшураш микроконтроллерной сети // Материалы и упрочняющие технолог iiii-'J Тезисы и материалы докладов Российской научно-техн. конференции Курск, 1994.-С. 138-141.

37.Колосков В.А., Титов B.C. Самосинхронизация адаптивной логнчеекч мпкроконгроллерной сети // Новые информационные icuio.ioi ни системы : Материалы докладов международной конф. llenw III П. 1994. - С 71-72.

38.Колосков В.А. Принципы саморсмонта oi казоустомчивс микроконтроллер»«» сети // Вибрлшюннме машины и технодоип Сб.докладов и материалов 11-й начно-тсхн. конференции. - Курск, 1995 С.121-125.

39.Колосков В.А., Колоскова М.В. Распределенные среден; - cauoopiашпацпи мудьтимнкроконтроллериой сеш // Вибрационны

машины и технологии. Сб.докладов и маюрналов 11-й па\'iiio-icm конференции. - Курск, 1995.-C.139-I42.

40.Колосков В.А., Медведева М.В., Титов B.C. Организация обеспечат • отказоустойчивости . мнкрокоптроллерных сетей // Электроника i

информатика 97. Вторая Всероссийская НТК с международным учаанех (Зеленоград 25-26 ноября 1997.).Тсзисы докладов. - Москва, 1997. - С 31

32. • ' е-'-":.;.-

41.А С. 575654, МЮГ, G06I-" 15/00. Управляющая логическая машина Колосков В.А. и др. -ДСП.

42 Л С. 622316, МКл3, C106F 15/00. Управляющая логическая машина Колосков В. А и др - ДСП

4 7

i.A. С. 711573, МКл\ G06F 9/14, G06F 11/00. Микропрограммное устройство с контролем переходов / Колосков В. А. и др. - Бюл. 1980. -

т.

».А. С. 807289, МКл\ G06F 9/22, G06F 11/00. Микропрограммное устройство с контролем переходов. / Колосков В. А. и др. - Бюл. 1981. -№7.

S.A. С. 985789, МКл3, G06F 9122, G06F 11/00. Микропрограммное устройство управления с исправлением ошибок / Колосков В. А. и др. -Бюл. 1982.-№48.

З.А. С. 711267, МКл2, G06F 9/16, G06F 11/00. Микропрограммное устройство управления с исправлением ошибок / Колосков В. А. и др. -Бюл. 1980. -№22.

'.А. С. 932495, МКл3, G06F 9/22, G06F 11/08. Микропрограммное устройство с восстановлением при сбоях переходов / Колосков В.А. й др. -Бюл. 1982.-№20.

I.A. С. 985787, МКл3, G06F 9/22, G06F 11/16. Микропрограммное устройство управления с контролем'переходов / Колосков В .А. и др. -Бюл. 1932.-№43.

».Патент РФ №2103724, МПК GC6F 15/16. Ячейка однородной среды / Колосков В. А. и др. -Бюл. -1998. 1

•.Патент РФ № 2Л0827, MX G05B 19/13, G06F 9/28. №97102528. Дискретная микрокоитроллерная сеть / Колосков В.А. и др. - Бюл. -1998,- №3.

.Патент РФ № 2110831, МК G06F 15/16. №96108448. Модуль матричного коммутатора I Колосхрв В.А. и др. - Бюл. - 1998. - №13. .Пзтс1гг РФ № 2112272, МК G06F 9/22. №97104368. Модуль матричной сети / Колосков В.А. и др. - Бюл. - 1998. - №15.

.Патент РФ № 2111528, МК G06F 9/22. №97104623. Микропрограммное устройство управления / Кслоскол В.А. и др. - Бгал. - 1993. - №14. .Патент РФ № 2112269, МК G05B 19/13. №97105566. Модульное

устройство для программного управления / Колосков В.А. и др. - Бю; 1998. -№15.

55.Заявка, МК G06F 15/16. №96108431. Модуль матричного коммутатс

Решение о выдаче патента от 5.01.98 /Колосков В.А. и др. 56.3аявка, МК G05B 19/18. №97104702. Мультимикроконтроллер

система. Решение о выдаче патента от 20.03.98 /Колосков В.А. и др. 57.3аявка, МК G06F 9/22. №97102631. Модуль мультимикропрограмм! системы. Решение о выдаче патента от 5.01.98 /Колосков В.Д. и др.

Соискатель

Колосков В.А.

Подписано к печати йЛ K.9f Формат 60 х 84 1 /16

Печатных листов X Тираж 100 экз. Заказ ¿$

Курский государственный технический университет. 305040, г. Курск, ул. 50 лет Октября, 94.

а

I ъ

Л

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

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

КОЛОСКОВ Василий Александрович

УДК 681.3

ОСНОВЫ ТЕОРИИ И ПРИНЦИПЫ ПОСТРОЕНИЯ ОТКАЗОУСТОЙЧИВЫХ

САМООРГАНИЗУЮЩИХСЯ ЛОГИЧЕСКИХ МУЛЬТИМИКРОКОНТРОЛЛЕРОВ

Специальность 05.13.05 «Элементы и устройства вычислительной техники и систем управления»

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

Научный консультант: доктор технических наук,

профессор Титов B.C.

Курск — 1998

СОДЕРЖАНИЕ

ВВЕДЕНИЕ...................................................5

ГЛАВА 1. ОСОБЕННОСТИ ОРГАНИЗАЦИИ ОТКАЗОУСТОЙЧИВЫХ САМООРГАНИЗУЮЩИХСЯ МУЛЬТИМИКРОКОНТРОЛЛЕРОВ......................... 16

1.1. Тенденции в организации мультимикроконтроллеров устройств группового логического управления...................... 16

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

1.3. Характеристика задач построения отказоустойчивого мультимикроконтроллера............................................................41

1.4. Распределение слоя самоорганизации отказоустойчивого мультимикроконтроллера............................................................49

1.5. Выводы к главе..............................................................................53

ГЛАВА 2. РАЗРАБОТКА ТЕОРЕТИЧЕСКИХ ОСНОВ РАСПРЕДЕЛЕННОГО ПОСТРОЕНИЯ САМООРГАНИЗУЮЩИХ СЕТЕЙ.................................................. 58

2.1. Графоструктурный подход к решению задачи самоорганизации 5 8

2.2. Классификация методов виртуального перемещения алгоритма 73

2.3. Характеристика методов глобального направленного поиска самоорганизующих сетей............................... 83

2.4. Разработка операций распределенной разметки..................97

2.5. Выводы к главе..............................................................................133

ГЛАВА 3. СИНТЕЗ ОПЕРАЦИЙ РАСПРЕДЕЛЕННОГО ФОРМИРОВАНИЯ МАРШРУТОВ ВОССТАНОВЛЕНИЯ.......... 135

3.1. Постановка задачи преобразования самоорганизующих сетей. . 135

3.2. Преобразование самоорганизующих ВЕ-сетей............... 150

3.3. Преобразование самоорганизующих NE-сетей.............. 164

3.3.1. Разработка операции преобразования NE-сетей с набором

103 направлений перемещения......................... 164

3.3.2. Разработка операции преобразования NE-сетей с набором

104 направлений перемещения......................... 178

3.4. Формирование маршрутов восстановления в самоорганизующих WP-сетях............................................ 199

3.5. Выводы к главе......................................... 207

ГЛАВА 4. ИССЛЕДОВАНИЕ ПРЕДЕЛЬНЫХ ВОЗМОЖНОСТЕЙ МЕТОДОВ САМООРГАНИЗАЦИИ............................ 209

4.1. Распределенное виртуальное перемещение алгоритмов на

графовой модели мультимикроконтроллера.................. 209

4.2. Графоструктурные исследования d-безотказности мультимикроконтроллера................................ 221

4.3. Результаты исследования методов самоорганизации на имитационной модели.................................. 247

4.4. Выводы к главе......................................... 255

ГЛАВА 5 . ПРИНЦИПЫ ПОСТРОЕНИЯ ОТКАЗОУСТОЙЧИВОГО САМООРГАНИЗУЮЩЕГОСЯ МУЛЬТИМИКРОКОНТРОЛЛЕРА. . 257 5.1. Принципы построения распределенных аппаратурных средств

самоорганизующего слоя отказоустойчивого

мультимикроконтроллера............................... 257

5.2. Организация настраиваемого многофункционального

микроконтроллера..........................................................................294

5.3. Функциональная организация отказоустойчивого самоорганизующегося мультимикроконтроллера......................304

5.4. Выводы к главе..............................................................................330

ЗАКЛЮЧЕНИЕ....................................................................................332

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ..................................336

ПРИЛОЖЕНИЕ......................................................................................363

ВВЕДЕНИЕ

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

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

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

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

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

ления СБИС - автоматы объединяются в регулярную сеть, представляющую собой мультимикроконтроллер (ММК) и служащую для реализации сложных логических алгоритмов.

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

Удовлетворение требований по производительности мультимикроконтроллера, вызванных ростом числа одновременно управляемых объектов, усложнением алгоритмов управления, ускорением протекающих в объектах процессов, приводят к усложнению мультимикроконтроллера и росту числа элементов, СБИС-автоматов или микроконтроллеров (МК). Обеспечение непрерывного управления дискретными технологическими процессами в реальном масштабе времени при достоверной обработке данных возможно в высоконадежном мультимикроконтроллере. С усложнением мультимикроконтроллера его надежность падает, увеличивается частота отказов, а также возрастает вероятность передачи ложных управляющих сигналов на объект вследствие отказов элементов мультимикроконтроллера.

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

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

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

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

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

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

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

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

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

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

3. Реализация виртуального переразмещения алгоритмов в мультимик-роконтроллере и исследование предельных возможностей операций самоорганизации.

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

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

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

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

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

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

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

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

5. Синтезированы операции поворота стрелки, реализующие второй

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

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

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

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

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

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

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

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

- программные средства имитационного моделирования основных этапов самоорганизации.

Реализация и внедрение результатов диссертационной работы. Диссертационная работа является обобщением результатов, полученных автором в Курском государственном техническом университете в процессе выполнения в 1980-1997 годах научно-исследовательских работ, в том числе Международного проекта «Технические системы обработки символьной информации и изображений» (распоряжение Госкомвуза РФ от 19.02.93. №10), темы Г - 22 "Разработка методов обработки нестационарных сигналов фазовой информации и создание базовой информационной измерительной системы" (1992-1995 г.г.), темы Г - 16 "Создание базовой архитектуры для информационных гипертехнологий и обработки изображений" (1993 г.), финансируемых по Единому заказу-наряду Комитета по ВШ № 10-36-63/10-0211 от 15.05.92 г. и Комитета по ВШ№ 10-36-67 ИЕУЮ-02-11 от 50.04.93 г. соответственно.

Результаты исследований прошли независимую экспертизу и включены в межвузовскую научно-техническую программу «Многопроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности» (Приказ по министерству общего и профессионального образования № 572 от 02.03.98).

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

НИ Горнорудный институт (Украина), АО «Прибор», в/ч 25714.

Теоретические и практические материалы диссертационной работы использованы в учебном процессе Курского государственного техниче�