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

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

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

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

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

МЕДВЕДЕВА Мария Васильевна

?гв од

и-да-ж

УДК 681.3

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

КУРСК 1999

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

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

профессор Титов В.С.

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

доктор технических наук Атакшцев О.И.

кандидат технических наук, доцент Лопнн В.Н.

Ведущая организация: ОКБ "АВИААВТОМАТИКА"

Защита состоится 17. 11. 1999 г. в /г- часов на засела)» специализированного совета Д 064.50.02. при Курском государствен»» техническом университете по адресу: 305040 г. Курск, ул. 50 лет Октября, 9 С диссертацией можно ознакомиться в библиотеке университета. Отзывы на автореферат в двух экземплярах, заверенные печать просьба направлять по адресу: 305040 г.Курск, ул. 50 лет Октября, ' КурскГТУ, ученому секретарю специализированного совета Д 064.50.02 Автореферат разослан

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

кандидат технических наук, доцент £ В.М Дс^тлъ.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов в диссертационной работе.

Данная работа выполнена в соответствии с программой ПТ614 "Многопроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности" (приказ министерства общего и профессионального образования Российской Федерации № 572 от 03.03.98 г.) по направлению "Самоорганизующиеся отказоустойчивые многопроцессорные устройства".

Результаты работы внедрены в учебном процессе Курского государственного технического университета по дисциплине "Отказоустойчивые многопроцессорные платформы* в СКБ ПС ОАО "Счетмаш" (г. Курск).

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференция: XXV ГАГАРИН-СКНЕ ЧТЕНИЯ. Международная молодежная иаучная конференция (г. Мсск&а,

1999 г ), 1-я Всероссийская научно-техническая конференция "Компьютерные технологии и науке, проектировании и производстве" (г. Нижний Новгород, 1999 г.). Международная конференция "Методы и средства преобразования и обработки аналоговой информации" (г. Ульяновск ,1999 г.), 7-й Всероссийский семинар "Нейроинформатика и ее приложения" (г. Красноярск, 1999 г.), 2-я Всероссийская научно-техническая конференция "Новые информационные технологии и системы" (г. Пенза, 1993 г.), 2-я Всероссийская научно-техническая кож(>ереиш1Я с международным участием "Электроника и информатика- 97" (г. Зеленоград ,1997 г.), Российская научно-техническая конференция "Современные проблемы сварочной науки и техники" (г. Воронеж ,1997 г.), Научно-техническая конференция "Материалы и упрочняющие технологии" (г. Курск, 1998 г.), Международная конференция "Оптико-электронные приборы и устройства в системах управления в системах распознавания образов, обработки изображений и символьной информации" (г. Курск, 1997,1999 г.г.). Международная техническая конференция "Медико-экологические информационные гехнолопш-98" (г. Курск ,1998 г.).

Публикации. Основные результаты диссертационной работы опубликованы в 29 работах, в том числе в 9 статьях, п 7 тезисах докладов, в 10 докладах или их материалах, в 3 патентах на изобретение.

Основные научные положения, выносимые па "защиту:

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

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

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

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

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

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

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

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

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

Рассмотрению вопросов надежности и отказоустойчивости программируемых управляющих устройств, однородных многопроцессорных структур посвящены работы А. Авижениса (A. Avizienis), Д.К. Прадхана (Pradhan D.K.), И. Корена (J. Koren), С. Куна (S.Y. Kung), М. Сами (М. Sami), В. Мура (W.R. Moor), Р. Эванза (R. Evans), П.П. Пархоменко, А.П. Горяшхо, А.И. Галушкина, В.И .Варшавского, ВА Воробьева, Е.С. Согоазошша, М.О. Каравая, В.И. Максимова, А.Н. Мямлнна, К.И. Иыуду и других отсчесгастшх я зарубежных неследователей.

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

В работе рассмотрены принципы синергетической самоорганизации систем произвольной природы, исследуемые в работах Хакена Г. (Haken Н.), При-гожнна И. (Prigogin J.), Николиса Г. (Nikolis G.), Курдюмова С.П., Романовского Ю.М., Иваницкого Г.Р., Кадомцева Б.Б., Гапонова-Грехова A.B. и других авторов. Показано, что они отвечают требованиям по созданию однородных, отказоустойчивых, масштабируемых ММК с клеточным автоматом самоорганизации. 1>ыли выделены основные фазы коллективной самоорганизации в муль-тнмикроконтроллсрс, соответствующие эволюции ММК из неравновесного состояния с отказавшими микроконтроллерами в установившееся состояние с переразмещенными пршраммиыми модулями на множестве работоспособных микроконтроллеров.

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

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

• томат), обладающая именем (в виде набора координат узла) и состоянием (в виде данных из обрабатываемого массива). Связи каждой клетки с другими определяются алгоритмом обработки данных.

СПП предназначена для обработки множества данных, представляемого как совокупность пар: (данное, и.\ш) = (Уь т>). где К* - слово состояния клетки, тк - место VI в пространстве всех данных. Пара (Уь т>) называется клеткой, в которой К* е А (А - алфавит для описания слов клеток), тк - имя клетки {(тк } = М - множество имен клеток). В работе определены и конкретизированы понятия клеточного массива, именующей функции, шаблона, позволившие представить формализованное описание алгоритма параллельных вычислений клеточного автомата самоорганизации.

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

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

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

3. Проектирование однородной автоматной сети клеточного пзтомата самоорганнзующей оболочки отказоустойчивого микроконтроллера.

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

5. Исследование статических и динамических характеристик автоматической сети самоорганнзующей оболочки муль-п[.микроконтроллера.

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

______________________ 11

Вторая глава "Разработка метода и алгоритма клеточной самоорганиза-иш ретрансляционного нрофаммопереноса" посвяшена разработке метода са-иооргатнапии, в котором для устранения неоднозначности программоперено-:а в критичных узлах решетки слоя самоорганизации вводится клеточная операция ретрансляции ПМ.

Для описания различных стадий процесса ретрансляционного програм-поперсиоса введены графовые модели, представляющие топологически эквивалентные взвешенные ор«рзфы Gi (V,Ut)> GtfV.U ¿1, G) (V,Uз), построенные ia ориентированных решетках и отличающиеся только весами дуг

j//,j - ji7 >j = jUa также взвешенный орграф GU4), содержащий дуги вир-гуальных связей.

Так, процесс формирования разрешений приема ПМ u ММК, задаваемом графом C,S(V.V) структуры с числом А/ строк и {N* 1) столбцов, описывается

;рафом (> ¡(l'A! i) потенциальных перемещений. Каадон исходящей из vtj<sG 1 о А-м направлении (к=--1,2, .К) дуге й'1 е U соотестствует вес е {у'1,/Ц }, отражающий возможность или запрет перемещения модуля в к-ом направлении.

Напраклеии?. реального перемещения между непосредственными соседями задаются ориентированным графом G}(V,UJ реальных перемещений. Каждой дуге й'1 е U : соответствует вес s? е fs'l.s^}, определяющий реально используемые (s'I) либо запрещенные (д ^ ) направления перемещения из множества к" 1,2.....К.

Для решения проблемы устранения "липших" ПМ в ситуациях захвата вершины vti предлагается использовать ретрансляцию избыточных модулей по направлению ближайших к уу соседей и разрешать прием в v9 только с одного из направлений. Состояние самоорганизующей решетки, задаваемой графом Gj(V,Uj). представляется совокупностью ситуаций хранения ПМ в узлах ре-

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

Последний этап самоорганизации описывается графом Сл(У,1) ^ виртуальных связей, в котором исключены конфликтные ситуации передачи ПМ в одну вершину с нескольких направлений введением виртуальных дуг ретрансляции модулей.

На графе С 4 задаются маршруты виртуального программопереноса модулей, которые в дальнейшем используются для перенумерации вершин графа 0$. При этом каждый такой маршрут из отмеченных весами (ц" '') дуг всегда начинается в одной из отказавших вершин решетки ~ -¡¡¿¡). а заканчивается в работоспособной вершине резервного столбца 1).

Для решения задачи самоорганизации разрабатываемым методом введены клеточные операции {О1*} (п=1, 2, ..., 5) преобразования графовых моделей

G1.G3.Gi , О <Ся, каждая из которых применяется ко всем вершинам соответствующего графа одновременно и продолжается до совпадения в графе результатов предшествующей и последующей итераций н сформулированы правила выполнения каждой операции.

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

Определение допустимого подмножества вариантов ретрансляции ПМ на заданном множестве направлений основано на выявлении пригодности наборов для разрешения любой конфликтной ситуации в решетке, а также обнаружения недопустимого "удлинения" дуг ретрансляции.

При решении данной задачи функцией Кя качества набора КО, е е 1.2....Х.....П) подопераций является Кя =|н/|.где - мощность множества виртуальных соседей для произвольной вершины по-

рождаемое набором N0, е Р Из всего множества !' наборов подопераций следует аыбирать покрывающий набор ¿\'Ог е Р, обеспечивающий минимальное

значение коэффициента Л', эффективности К,~тт{Кг}.

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

Для реализации клеточных операций предложена система Ф1 параллельных подстановок для построения маршрутов программопереноса и перенумерации вершин графа (а$ структуры: Ф/ = {0/, 0}. в* 0* ¿У, где {(\} - подстановки, обеспечивающие выполнение операций О'/ в графах О / - С <, (?<г. На примере решеток с двумя направлениями программопереноса с учетом ра1ра-ботаиных иравил выполнения операций О}'- 0%получены выражения для подстановок в,, 0;, 0}, в] Эволюцию программопсргиоса при реализации разработанной системы Ф1 параллельных подстановок иллюстрирует рис. 1, представляющий пошаговое выполнение алгоритма ретрансляционного программопереноса на фрагменте решетки.

оооо о о о о о о о о о е-о о о ©-оо о ©чю

О О ©-Ю О о ©-0 о О-Ф-О

Рис. I. Заалюши ретрансляционного программопереноса,

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

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

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

В)псп1снпий ф.тф О ¡(К и 0 описывает все возможные направления перемещения ПМ для каждой вершины с учетом отказопой ситуации. Для успешной самоориишзацни ни одна из отказавших вершин решетки не должна быть

изолирована, н п графе й ¡(1\и ¡) ей должна быть ннцмдентна хотя бы одна исходящая дуга.

Исключение лишпкх направлений приема ПМ выполняется на стадш формнрокшня графа С л номер направления соответствует его приоритету (1 горизонтально вправо, 2-всртикалыю вверх, З-всртикально вниз, 4 горизонтально влево).

. - 15

_____ В работе сформулированы правила распределенного построения и преобразования моделей О „ О'.-, в соответствии с которыми в графе реализуется перенастройка направлений приема/передачи при появлении очередного критичного узла и обеспечение блокировки перемещений в запрещенные области решетки. Рис. 2 поспронзвод1гг три последовательные итерации преобразования фрагмента решетки слоя самоорганизации по прездтзд адаптнгнего ярограы-мопереиоса.

оооо оооо о О Ф-О о р о-о-о о

О О €И1 о о А © о о оооо оооо о о о о

Рис. 2. Этапы адаптивного ирограммоперенсса

На основании сформулированных правил программоиерсноса разработана сгстсма Ф; ппраллатьны.х подстановок для построения маршрут« п-.-ремс-1;:с!!1!'.; ^рсграмм)1!.;х модулей и перенумерации зершнн структурного 1рафа: Ф} ~ {0}. 0), 0), 04. где Ои О} - подстановки, обсспечиааюч««<» г^пеление -- . ..,,,.;; (;,, (]: : - ;тогс; •!.

дл* каждой нз вершин структурного графа их новые номера; 04 -подстановка для вычисления вссоа вершин фафа О';.

!' зс.чсшчио.4» алгоршча .хглпкптою ••

• л. ; -::.'.;; й:ли ^¡¿¿¿глскы алфавиты «Т093 ссгтояшя к.;сгки с;о.т садкчрм-для двух, трех и чешрех направлений прсграчмонер<.;т,^а и скшезн--■'Оа^'.и соответствующие системы параллельных подстсшоадк.

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

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

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

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

В общем случае структурный синтез клетки КЛ самоорганизации для за данного множества допустимых направлений программоперсноса базируете

на результатах проектирования празнл выполнения операций O'j-O'j н сводится к следующей последовательности действий: гздтп;; алфавита клеточного автомата; построение структурной схемы автомата клетки; сшттгз выражений для функций реализации операций ¿>f-0/; синтез выражений для функции фатального отказа. Порядок структурного синтеза клетхи для разных истодов программоперсноса сохраняется татглима, различия хггсотса только числа и состава операций.

В работе выполнены все перечисленные этапы структурного синтеза клеточных автоматов для разработанных методов самоорганизации ретрансляционного (на 2 направления), адаптивного (на 2,3 а 4 направления) я комбинированного (на 2 направления) профаымопереносов.

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

Для ¡саясдого га мстодсэ c^ooprancscni разработаны базовые струк-лрные схемы клеточных автоматов, реализующих функции выполнения операций профамиопереноса, фунхшш отказа, а так»« функции запрета персые-цешй в приоритетных направлениях (для адаптивного н комбинированного 1етодов)

I

Разработайте функцисиааиа« реализации клеток КА адаптивной н стран слзщионкоЭ самоорганизации протраммоперепоса и настрой»! ыикро-ситроллеров позволили представить распределенный и сосредоточенный г-а-HKjrnj структурной организация устройства самоорганиззция иуг&пшикро-а;:троллерз. В перроч вгр::г:г72 гзтоыгт, реализующий клетку, ггслкуюстез з якрошпроллср. В результате iiiispo^mpccr.cp становится ааагггкгным и в Ш1СКМ0СТИ от состояния соседних МК перенастраивается на одни из возмояс-. ых профаммных модулей. • _

Выполнение клеточного аэтензтэ в вида автономного устройства приво-77 к сосредоточенному рзраакту. рездюгякн. Невысокая сдспхностъ одной тп ncii'tsrsT резлтзегеп. raiasa устроЗстао нз СБИС ПЛИС. Аятекаиксе

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

Предложенные технические решения на организацию клетки и отказоустойчивого мультимикроконтроллера обладают новизной и защищены патентами РФ {27-29].

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

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

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

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

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

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

рывиости функциоmipoвания, высокой корректирующей способности к отказам высокой кратности.

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

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

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

5. Выполнено исследование по ¿-отказоустойчивости, достигаемо! адаптивной и ретрансляционной самооргаиизующсй оболочками, в зависимо ait от числа v направлений программопереноса, топологии решетки и получе >/ы соотношения, связывающие ¿/-отказоустойчивость и число дополнительны: программных модулей с и

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

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

1. Медведева MB., Медведев A.B., Колосков В.А. Клеточиа нсКроннце вычисления в слое самоорганизации отказоустойчивого мультимик рокошроллсра // Теория н общие вопросы обработки аналоговой информации

Труди международной конференции "Методы и средства преобразования и обработки аналоговой информации" (8-10 июня 1999 г.) / Под рел. Л И. Волгина. - Ульяновск: УлГТУ, 1999. - том. 1. - С. 71-73.

2. Медведев A.B., Медведева М.В., Колосков В.А. 'Аналоговая нейронная коммутационная клетка самоорганнзующего слоя отказоустойчивого мультимикроконтроллера // Теория и общие вопросы обработки аналоговой информации. Труды международной конференции "Методы и средства преобразования и обработки аналоговой информации" (8-10 июня 1999 г.) / Под ред. Л И. Волгина - Ульяновск: УлГТУ, 1999. -том.1.-С. 68-70.

3. Медведев A.B., Медведева М.В. Клеточно-иейронный слой самоорганизации отказоустойчивого мультимикроконтроллера И ГАГАРННСК1Ш ЧТЕНИЯ. Тезисы докл. молодых ученых Международной научной конференции. Москва; 6-10 апреля 1999 г. - М.: Изд-во "ЛАТМЭС", 1999. T.l. - С.400.

4. Медведева М.В., Медведев A.B. Моделирование клеточных операций самоорганизации мультнмнкроконтроллерных сетей // ГАГАРИНСКНИ ЧТЕНИЯ. Тезисы докл. молодых ученых Международной научной конферсн цнн. Москва, 6-10 апреля 1999 г. -М.: Изд-во "ЛАТМЭС", 1999. T.I. -С.682.

5. Медведева М.В., Медведев A.B., Колосков В.А. Структурный синтез слоя самоорганизации отказоустойчивой мультимнкроконтроллерной сети /7 Компьютерные технологии в науке, проектировании и производстве. Тез. докл. I Всероссийской научно-технической конференции. В 19 частях. Ч. 17. Нижний Новгород: НГТУ, 1999 г. - С.39.

6. Медведева M.R., Медведев A.D., Колосков В.А. Сшпез алыритмон :змоорганнзацни мультимикроконтроллера на графовых моделях // Управление j сложных системах. Уфа. У Г АТУ. 1993.-С. 177-183.

7. Медведева М.В., Медведев A.B., Титов B.C. Операции самооргаии-ицин отказоустойчивого мультимикроконтроллера // Новые ииформационн'ые гсхнатогни и системы: Материалы II Международной научно-технической янфгрешшн. - Пенза. ПТУ, 1998. - С. 75-76.

8. Медведева М.В. Выбор набора операций самоорганизации отказоустойчивого мультимнкроконтроллера // Материалы и упрочняющие технологии. VI научно-техническая конференция с международным участием. Материалы докладов. - Курск: КГТУ. 1998 г. - С. 257-260.

9. Медведев A.B., Миневич Л.М., Медведева М.В. Моделирование самоорганизации отказоустойчивого мультимнкроконтроллера на графовых решетках // Материалы и упрочняющие технологии. VI научно-техническая конференция с международным участием. Материалы докладов. - Курск КГТУ. 1998 г. -С. 260-262.

10. Медведев A.B., Колоскова Г.П., Медведева М.В. Поиск оптималь пых решений с использованием клеточно-нейронного подхода // Материалы i упрочняющие технологии. VI научно-техническая конференция с международ ным yiacfncM. Материалы докладов. - Курск: КГТУ. 1998 г. - С. I69-) 71.

11. JI.M. Миневич, A.B. Медведев, М.В. Медведева, В.Л. Колоско Оперативное восстановление функционировании отказоустойчивых мульти процессоров // "Медико-экологические информационные технолопш". Мат< риалы международной технической конференции. - Курск: КГТУ, 1998. - ( »84-187.

12. М.В. Медведева, Л.М. Миневич, Г.П. Колоскова Виртуальная пер лагручка логической структуры в матрице мультипроцессора // "Медика экологические информационные технологии". Материалы международной те ннчсской конференции. - Курск: КГТУ, 1998. - С. 187-189.

13. Медведева М.В., Медведев A.B., Миневич J1.M., Колосков В. Принципы построения слоя самоорганизации на основе графоструктурно подхода // Изв. ТулГУ. Вып. 2. 1998.

14. Медведева М.В., Колосков В.А. Структурный сингсз слоя самос гашшцин отказоустойчивой мультнмикроконтроллерной сетн // Управлсши сложных снстсмзх.-- Уфа: УГТУ, 1999.

15» Медведева М.В., Медведев A.B., Колосков В.А. Синтез адаптиш го слоя самоорганизации мультимнкроконтроллера // Изв. ТулГУ. Вып. 3.19'.

16 Колосков В Л , Медведева М.В., Медведев A.B. Тсорстнко-грпфовые основы самоорганизации отказоустойчивых мультнмнкроконтролле-ров // Изв. Курского ГТУ. № 3. 1999. - С. 113-123.

17. Колосков В.А., Медведева М.В., Минсвич Л.И. Адаптивная настройка микроконтроллера процессора системы технического зрения // Распознавание - 97. Сб. материалов 3 Международной конференции. - Курск: КГТУ. 1597. - С. 200-203.

18. Медведева М.В., Медведев A.B., Колоскова Г.П. Размещение управляющего алгоритма в микроконтроллерной сети вибрационного стенда // Вибрационные машины и технологии. Сборник научных докладов III Международной научно-технической конференции. - Курск: КГТУ. 1997. - С. 248-250.

19. Колосков В.А., Медведева М.В. Организация перемещения алгоритмов з отказоустойчивой септ вибрационного стенда И Вибрационные машины и технологии. Сборник научных докладов III Международной научно-технической конференции. - Курск: КГТУ. 1997. - С. 251-253.

20. Колосков В.А., Медведева М.В., Тгггоз B.C. Организация средств обеспечения отказоустойчивости мнкроконтроллерных сетей И Электроника н информатика. Вторая Всероссийская научно-техническая конференция с международным участием. (Зеленоград, 25-26 ноября 1997 г.) Тез. докладов. - Мо-ска. 1997.-С. 31-32.

21. Медведева М.В., Медведев A.B. Метод логической перестройки программируемого микроконтроллера II Современные проблемы сварочной науки и техники "Сварка - 97". Материалы Российской научно-тсхннческой ¡^нферешши (16-1S сентября 1997 г.). - Воронеж. 1997.

22. Колосков В.А., Медведем М.В. Инвариантные преобразования логической структуры отказоустойчивого самоорганизующегося мультимнкро-контроллера // Методы и средства систем обработки информации. Сб. науч. статей. - Курск, КГТУ. 1997. - С. 59-64.

23. Колосков В .А., Мнневмч Л.М., Медведева М.В., Медведев A.B., Т:ггсз B.C. Гргфсетруетуриые основы построения отказоустойчивых самооргз-

низ}ющихся программируемых логических мультнмикроконтроллсров / Курск гос. техн. ун-т. Курск. 1997. - 33с. - Дсп. в ВИНИТИ. № 1600-В97.

24. Медведева М.В., Медведев A.B., Колосков В.А. Учебная системг автоматизированного надежностного проектирования // Новые информацион ные технологии в системах многоуровневого обучения. Материалы Всероссийской научно-методической конференции. - Нижний Новгород. 1996.

25. Медведева М.В., Колосков В.А. Инструментальные средства иссле дования самоорганизующихся отказоустойчивых матриц // Новые информационные технологии в системах многоуровневого обучения. Материалы Всерос сийской научно-методической конференции. - Нижний Новгород. 1996.

26. Медведева М.В., Колосков В.А. Самодиагностируемый логически} сопроцессор медицинской диагностической аппаратуры // Матералы и упрочняющие технологии - 94. Тезисы и материалы докладов Российской научно технической конференции. - Курск. 1994.

27. Патент РФ Кз 2103724. Ячейка однородной среды / Бабкин Г.В. Колосков В.А., Медведева М.В., Титов B.C. - Бюл. 1998. № 3.

28. Патент РФ Мз 2122229. Распределенная система для программное управления / Колосков В.А,, Миневич Л.М., Медведева М.В., Титов B.C.

29. Патент РФ № 2133054. Распределенная система для программно« управления / Миневич Л.М., Медведев A.B., Медведева М.В., Колосков В.А. Титов B.C.

Соискатель

Медведева М.В.

Подписано к печати /а /с 9.1_Формат 6084 1/16

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

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

ВВЕДЕНИЕ.

1. СИНЕРГЕТИЧЕСКИЙ ПОДХОД К ОБЕСПЕЧЕНИЮ ОТКАЗОУСТОЙЧИВОСТИ МУЛЬТИМИКРОКОНТРОЛЛЕРА.

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

1.2. Синергетический подход к построению алгоритмов самоорганизации - алгоритмов виртуального программопереноса.

1.3. Формальная модель алгоритма клеточных вычислений.

1.4. Постановка задач исследований по разработке клеточной самоорганизующей оболочки мультимикроконтроллера.

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

2. РАЗРАБОТКА МЕТОДА И АЛГОРИТМА КЛЕТОЧНОЙ САМООРГАНИЗАЦИИ РЕТРАНСЛЯЦИОННОГО

ПРОГРАММОПЕРЕНОСА

2.1. Математические модели и этапы программопереноса с ретрансляцией

2.2. Содержательная формулировка алгоритма программопереноса.

2.3. Определение допустимых вариантов ретрансляции

2.4. Клеточный алгоритм программопереноса с ретрансляцией.

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

3. РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ КЛЕТОЧНОЙ САМООРГАНИЗАЦИИ АДАПТИВНОГО

ПРОГРАММОПЕРЕНОСА.

3.1. Характеристика алгоритма адаптивного программопереноса

3.2. Построение клеточного алгоритма адаптивного программопереноса

3.3. Проектирование адаптивного алгоритма программопереноса с ретрансляцией.

3.4. Выводы к главе.

4. ФУНКЦИОНАЛЬНАЯ РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК КЛЕТОЧНЫХ АВТОМАТОВ

ПРОГРАММОПЕРЕНОСА.

4.1. Структурный синтез КА самоорганизации ретрансляционного программопереноса.

4.1.1. Задание алфавита и построение структурной схемы автомата клетки

4.1.2. Синтез выражений для функций реализации операции О/

4.1.3. Синтез выражений для функций реализации операции 0|

4.1.4. Синтез выражений для функций реализации операции 0|

4.1.5. Синтез выражений для функций выполнения операции

OÏOÏ.

4.2. Структурный синтез КА самоорганизации адаптивного программопереноса

4.2.1. Задание алфавита и построение структурной схемы клетки

4.2.2. Синтез выражений для функций реализации операции О].

4.2.3. Синтез выражений для функций реализации операции

4.2.4. Синтез выражения для функционального отказа.

4.2.5. Структурный синтез КА самоорганизации комбинированного программопереноса.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов в диссертационной работе.

Данная работа выполнена в соответствии с программой ПТ614 "Многопроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности" (приказ министерства общего и профессионального образования Российской Федерации № 572 от 03.03.98 г.) по направлению "Самоорганизующиеся отказоустойчивые многопроцессорные устройства".

Результаты работы внедрены в учебном процессе Курского государственного технического университета по дисциплине "Отказоустойчивые многопроцессорные платформы", в СКБ ПС ОАО "Счетмаш" (г. Курск).

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: XXV ГАГ АРИЙСКИЕ ЧТЕНИЯ. Международная молодежная научная конференция (г. Москва,

1999 г.), 1-я Всероссийская научно-техническая конференция "Компьютерные технологии в науке, проектировании и производстве" (г. Нижний Новгород, 1999 г.), Международная конференция "Методы и средства преобразования и обработки аналоговой информации" (г. Ульяновск ,1999 г.), 7-й Всероссийский семинар "Нейроинформатика и ее приложения" (г. Красноярск, 1999 г.), Международная научно-техническая конференция "Новые информационные технологии и системы" (г. Пенза ,1998 г.), 2-я Всероссийская научно-техническая конференция "Новые информационные технологии и системы" (г. Пенза, 1998 г.), 2-я Всероссийская научно-техническая конференция с международным участием "Электроника и информатика- 97" (г. Зеленоград ,1997 г.), Российская научно-техническая конференция "Современные проблемы сварочной науки и техники" (г. Воронеж ,1997 г.), Научно-техническая конференция "Материалы и упрочняющие технологии" (г. Курск, 1998 г.), Международная конференция "Оптико-электронные приборы и устройства в системах управления в системах распознавания образов, обработки изображений и символьной информации" (г. Курск, 1997,1999 г.г.), Международная техническая конференция "Медико-экологические информационные технологии-98" (г. Курск, 1998 г.).

Публикации. Основные результаты диссертационной работы опубликованы в 29 работах, в том числе в 9 статьях, в 7 тезисах докладов, в 10 докладах или их материалах, в 3 патентах на изобретение.

Основные научные положения, выносимые на защиту:

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

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

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

158

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

160

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

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

1. Игнатьев В.М., Колосков В.А., Титов B.C. Проектирование самоорганизующейся дефектоустойчивой микроконтроллерной сети. Тула: ТГУ, 1995. - 140с.

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

3. Функционально-топологическая организация микропрограммных мультимикроконтроллеров группового логического управления / И.В. Зотов,

4. B.А. Колосков, B.C. Титов, И.В. Абузова, Тул. гос. ун-т. Тула. 1997- 226с.

5. Иыуду К.А. Надежность, контроль и диагностика вычислительных машин и систем. М.: Высшая школа, 1989. - 216с.

6. Методы анализа и синтеза структур управляющих систем / Б.Т. Во-лик, Б.Б. Буянов, Н.В. Лубков и др.; Под ред. Б.Т. Волика. М.: Энергоатомиз-дат, 1988. -296с.

7. Пакулов Н.И., Уханов В.Ф., Чернышев П.Н. Мажоритарный принцип построения надежных узлов и устройств ЦВМ. М.: Советское радио, 1974,-184с.

8. Чернышев Ю.А., Аббакумов И.С. Расчет и проектирование устройств ЭВМ с пассивным резервированием. М.: Энергия, 1979. - 119 с.

9. Авиженис А. Отказоустойчивость свойство, обеспечивающее постоянную работоспособность цифровых систем // ТИИЭР. - 1978. - №10. - т.661. C. 5-25.

10. Авиженис А., Лапри Ж.-К. Гарантоспособные вычисления: от идей до реализации в проектах // ТИИЭР. 1986. - №5. - т.74. - С. 8-21.

11. Согомонян Е.С., Каравай М.Ф. Самопроверяемые вычислительные устройства и отказоустойчивые системы // Измерение, контроль, автоматизация. 1980. - №9. - С.173-181.

12. Согомонян Е.С. Отказоустойчивые избыточные структуры // Автоматика и телемеханика. 1986. - №10. - С. 135-143.

13. Согомонян Е.С. Аппаратурное и программное обеспечение отказоустойчивых вычислительных систем // Автоматика и телемеханика. -1988. -№2. С.3-59.

14. Гавзов Д.В., Сапожников В.В., Сапожников Вл.В. Методы обеспечения безопасности дискретных систем // Автоматика и телемеханика. 1994. -№8. - С. 5-50.

15. Гройсберг Л.Б. Методы обеспечения надежности микропроцессорных управляющих систем // Вопросы технической диагностики. Межвуз. сб. -Ростов-на-Дону: РИСИ, 1985. С. 3-18.

16. Харченко В.Л., Литвиненко В.Т. Обеспечение устойчивости управляющих и вычислительных систем к физическим дефектам и дефектам проектирования программно-аппаратных средств // Зарубежная радиоэлектроника. -1992. -№6.-С. 18-35.

17. Кулинич A.A., Максимов В.И. Архитектура вычислительных систем с контуром обеспечения отказоустойчивости // Измерения, контроль, автоматизация. 1993. - №1-2. - С. 64-77.

18. Гуляев В.А., Додонов А.Е., Пелехов С.П. Организация живучих вычислительных структур. Киев: Наукова думка, 1982. - 140с.

19. Коваленко А.Е., Гула В.В. Отказоустойчивые микропроцессорные системы. Киев: Техника, 1986. - 150с.

20. Березюк Н.Т., Гапунин А.Я., Подлесный Н.И. Живучесть микропроцессорных систем управления. Киев: Техника, 1988. - 143с.

21. Согомонян Е.С., Слабаков Е.В. Самопроверяемые и отказоустойчивые системы. М.: Радио и связь, 1989. - 208с.

22. Введение в теорию живучести вычислительных систем / Додонов А. Г., Кузнецова М. Г., Горбачик Е. С.; Отв. ред. Гуляев В. А. Киев: Наукова думка, 1990. - 184с.

23. Кузнецова В. Л., Раков М. А. Самоорганизация в технических системах. Киев: Наукова думка, 1987. 200с.

24. Евреинов Э.В. Однородные вычислительные системы, структуры и среды. М: Радио и связь, 1981. - 208с.

25. Корнеев В.В. Архитектура вычислительных систем с программируемой структурой. Новосибирск: Наука, 1985. - 176с.

26. Доманицкий С.М. Построение надежных логических устройств. М.: Энергия, 1971. -280с.

27. Корен И., Прадхан Д.К. Избыточность как средство повышения надежности и выхода годных мультипроцессорных систем с интеграцией на уровне кристалла и пластины // ТИИЭР. 1986. -№5. - С.93-107.

28. Кун С. Матричные процессоры на СБИС: Пер. с англ. М.:Мир, 1991.672с.

29. Сами М., Стефанелли Р. Перестраиваемые архитектуры матричных процессорных СБИС// ТИИЭР. 1986. - №5. - С.107-118.

30. Эванз Р., Макхуэртер Дж. Иерархическая стратегия тестирования самоорганизующихся отказоустойчивых матриц /Систолические структуры: Пер. с англ./ Под ред.У.Мура, Маккейба, Р. Уркхарта. М.:Радио и связь, 1993.-С.264-276.

31. Корен И., Померанц И. Распределенное структурирование процессорных матриц, содержащих отказавшие процессоры / Систолические структуры: Пер. с англ. / Под ред. У. Мура., Э.Маккейба, Р.Уркхарта. -М.: Радио и связь, 1993. -С.276-291.

32. Koren J. A reconfigurable and fault-tolerant multiprocessor array // Proc. 8th Annu. Symp. Comput. Architecture. -1981. P.425-442.

33. Mangir Т., Avizienis A. Fault-tolerant design for VLSU: Effect of interconnect requirements on yield improvement of VLSI design // IEEE Trans. Comput. -July. 1982.

34. Abraham J.A., Banerjee P., Chien Chien Yi. Fault-tolerant techniques for systolic arrays // Computer. July. - 1987.

35. Pradhan D.K. Dynamically restructurable fault-tolerant processor network architectures // IEEE Trans. Сотр. 1985. - V.34. - №5. - P.841-848.

36. Donianst V.N., Lori S. Fault-tolerant reconfigurable processoring arrays using bi-directional switches // Microprocessing and Microprogamming. -1984. -V.14. P.109-115.

37. Kuo S.Y. Fuches W.K. Efficient spare allocation in reconfigurable arrays// IEEE Design Test. Feb. - 1987.

38. Kung Sun Yuan, Jean Shiann Ning, Chang Chin Wei. Fault-tolerant array processors using single-track switches // IEEE Trans. Comput. April. - 1989.

39. Hosseini S.H. On Fault-tolerant Structure Distributed Fault-Diagnosis, Reconfiguration and Recovery of the Array Processors // IEEE Trans. Comput. -July.- 1989.

40. Горяшко А.П., Шура-Бура А.Э. Методы оценки отказоустойчивых структур СБИС // Изв. АН СССР. Техническая кибернетика. 1988. - №6. -С.133-142.

41. Горяшко А.П., Шура-Бура А.Э., Метод построения отказоустойчивых процессорных решеток // Изв. РАН. Техническая кибернетика. 1991. -№2,- С. 180-189.

42. Горяшко А. П. Специализированные вычислительные структуры / Искусственный интеллект: В 3-х кн. Кн. 3. Программные и аппаратные средства: справочник / Под ред. В. Н. Захарова, В.Ф. Хорошевского. М.: Радио и связь, 1990,- С. 258-284.

43. Воробьев В. А., Лаходынова Н. В. Пределы надежности однородных вычислительных структур. Известия АН. Техническая кибернетика. 1989. -№3. - С. 110-114.

44. Воробьев В. А., Лаходынова Н. В. Процессорная матрица с перестраиваемой структурой и перестраиваемым резервом. // Автометрия. 1994. -№5. - С.90-98.

45. Воробьев В. А., Еремина Н. Л. Программная реализация реконфигурации отказоустойчивой процессорной матрицы. // Автометрия. 1996. - №2. -С. 111-121.

46. Галушкин А. И., Грачев Л. В., Толстых М. М., Точенов В. А. Оценка алгоритмов реконфигурации структуры вычислительной системы с МШГО-архитектурой // Кибернетика. 1990. - №2.- С. 35-41.

47. Мямлин А. Н., Поздняков Л. А., Котов Е. И., Задыхайло И. Б. Об одном методе повышения надежности матричных многопроцессорных систем.// Электронная вычислительная техника. 1988. - Вып. 2. - С. 26-37.

48. Мямлин А. Н., Поздняков Л. А., Котов Е. И., Задыхайло И. Б. Об одном методе повышения надежности матричных многопроцессорных систем. -М. : ИПМ АН СССР. Препринт №78. 1985. 18с.

49. Головко В. А. Методы обеспечения отказоустойчивости линейных систолических процессоров. // Микроэлектроника. 1995. - Т. 24. - №3. - С. 229-240.

50. Долгушев С. А., Донианц В. Н., Стефанелли Р. Алгоритмические методы реконфигурации однородных процессорных матриц. Препринт. М. : ИППН АН СССР, 1988. - 26с.

51. Петров А. Б. Толерантные матрицы процессорных элементов // Изв. вузов. Приборостроение. 1994. - №2. - С. 79-83.

52. Кухарев Г. А., Шмерко В. П., Зайцева Е. Н. Алгоритмы и систолические процессоры для обработки многозначных данных. Мн. : Наука и техника, 1990. 300 с.

53. Надежность технических систем: СправочникЯО.К. Беляев, В.А. Богатырев, В.В. Болотин и др.; Под ред. И.А. Ушакова. М.: Радио и связь, 1985-608с.

54. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах /Под ред. В.И. Варшавского. М.: Машиностроение, 1986. -400с.

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

56. Haken H. Advanced Synergetics. Springer Series in Sinergetics, Vol. 20. Berlin: Springer-Verlag, 1983.

57. Романовский Ю.М. Принципы самоорганизации в физике, химии, биологии. М.: Знание, 1981.

58. Николис Г., Пригожин И. Познание сложного. Введение. М.: Мир,1990.

59. Синергетика: Сб. статей / Под ред. Б.Б. Каданцева. М.: Мир, 1984.

60. Haken Н. Principles of Brain Functioning. Springer Series in Sinergetics, Vol. 67. Berlin Springer.

61. Глушков B.M. Синтез цифровых автоматов. M.: Физматгиз, 1962.

62. Кобринский Н.Е., Трахтенброт Б.А. Введение в теорию конечных автоматов. М.: Физматгиз, 1962.

63. Лупанов О.Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики, вып. 10. М.: Физматгиз, 1963. С. 63-97.

64. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем. М.: Наука, 1969.64. von Neumann J. Theory of Self-Reproducing Automata. Urbana: University of Illinois Press, 1966.

65. Wolfram S. Cellular Automata and Complexity. New York: Addison-Wesley, 1994.

66. Тоффоли Т., Марголус H. Машины клеточных автоматов. М.: Мир,1991.

67. Codd Е. Cellular Automata. New York, London: Academic Press, 1968.

68. Achasowa S., Bandman O., Markova V., Piskunov S. Parallel substitution algorithm. Theory and application. Singapore: World Scientific. 1994.

69. Основы теории дискретных логических и вычислительных устройств. Шоломов Л.А. М.: Наука. Главная редакция физико-математической литературы. 1980.-400с.

70. Медведева М.В., Медведев A.B., Колосков В.А. Синтез алгоритмов самоорганизации мультимикроконтроллера на графовых моделях // Управление в сложных системах. Уфа: УГАТУ. 1998. С. 177-183.

71. Медведева М.В., Медведев A.B., Титов B.C. Операции самоорганизации отказоустойчивого мультимикроконтроллера // Новые информационные технологии и системы: Материалы II Международной научно-технической конференции. Пенза, ПГУ, 1998. - С. 75-76.

72. Медведева M.B. Выбор набора операций самоорганизации отказоустойчивого мультимикроконтроллера // Материалы и упрочняющие технологии. VI научно-техническая конференция с международным участием. Материалы докладов. Курск: КГТУ. 1998 г. - С. 257-260.

73. М.В. Медведева, JIM. Миневич, Г.П. Колоскова Виртуальная перезагрузка логической структуры в матрице мультипроцессора // "Медико-экологические информационные технологии". Материалы международной технической конференции. Курск: КГТУ, 1998. - С. 187-189.

74. Медведева М.В., Медведев A.B., Миневич Л.М., Колосков В.А. Принципы построения слоя самоорганизации на основе графоструктурного подхода // Изв. ТулГУ. Вып. 2. 1998.

75. Медведева М.В., Колосков В.А. Структурный синтез слоя самоорганизации отказоустойчивой мультимикроконтроллерной сети // Управление в сложных системах. Уфа: УГТУ. 1999.

76. Медведева М.В., Медведев A.B., Колосков В.А. Синтез адаптивного слоя самоорганизации мультимикроконтроллера// Изв. ТулГУ. Вып. 3. 1999.

77. Колосков В.А., Медведева М.В., Медведев A.B. Теоретико-графовые основы самоорганизаций: отказоустойчивых мультимикроконтроллеров // Изв. КурскогоГТУ.№3. 1999.-С. 113-123.

78. Колосков В.А., Медведева М.В., Миневич Л.И. Адаптивная настройка микроконтроллера процессора системы технического зрения // Распознавание 97. Сб. материалов 3 Международной конференции. - Курск: КГТУ. 1997. -С. 200-203.

79. Медведева М.В., Медведев A.B. Метод логической перестройки программируемого микроконтроллера // Современные проблемы сварочной науки и техники "Сварка 97". Материалы Российской научно-технической конференции (16-18 сентября 1997 г.) - Воронеж. 1997.

80. Колосков В.А., Медведева М.В. Инвариантные преобразования логической структуры отказоустойчивого самоорганизующегося мультимикро-контроллера // Методы и средства систем обработки информации. Сб. науч. статей. Курск, КГТУ. 1997. - С. 59-64.

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

82. Патент РФ № 2103724. Ячейка однородной среды / Бабкин Г.В., Колосков В.А., Медведева М.В., Титов B.C. Бюл. 1998. № 3.

83. Патент РФ № 2122229. Распределенная система для программного управления / Колосков В.А., Миневич JIM., Медведева М.В., Титов B.C.

84. Патент РФ № 2133054 Распределенная система для программного управления / Миневич Л.М., Медведев A.B., Медведева М.В., Колосков В.А., Титов B.C.

85. Ope О. Теория графов. М.: Наука. Главная редакция физико-математической литературы, 1980. - 336с.

86. Зыков A.A. Основы теории графов. М.: Наука, 1987. - 382с.