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

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

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

Специальность 05.13.01 «Системный анализ, управление и обработка информации»

АВТОРЕФЕРАТ

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

Курск - 2003

Работа выполнена в Курском государственном техническом университете

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

Официальные оппоненты: доктор технических наук, профессор Сизов A.C.

кандидат технических наук, Старков Е.Ф.

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

Защита состоится 27 ноября 2003 г. в 14:00 часов на заседании диссертационного совета Д 212.105.03 при Курском государственном техническом университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94, конференц-зал.

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

Автореферат разослан 27 октября 2003 г.

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

Старков Ф.А.

1x272

Общая характеристика работы

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

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

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

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

Проблемы обеспечения отказоустойчивости управляющих систем рассмотрены в работах Пархоменко П.П., Варшавского ВД^ ^^ш^ишю В,Г., Ка-

ноналъная

библиотека

3 { С.Петерв

1 ОЭ 900"

разая М.Ф., Харченко В.Л., Авижениса А., Реннелса Д., Сами М„ Куна С. и др. авторов. Исследования показывают, что перспективным методом обеспечения отказоустойчивости масштабируемых мультиконтроллеров является их самоорганизация, заключающаяся в восстановлении (репродуцировании) программы управления технологическими операциями на множестве работоспособных микроконтроллеров, допускающих перенастройку на один из хранимых в них алгоритмов. Хранение в каждом микроконтроллере множеств алгоритмов физических соседей обеспечивает оперативное репродуцирование, необходимое для безостановочной работы в реальном времени.

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

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

Диссертационная работа выполнялась в рамках тематического плана госбюджетных НИР по Единому заказ-наряду Госкомвуза РФ Курского государственного технического университета.

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

Для достижения поставленной цели в диссертационной работе решались

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы обсуждались на: международном конгрессе "Искусственный интеллект" (Таганрог, 2001); III и IV Всероссийской научно-технической конференции "НЕЙРО-ИНФОРМАТИКА" (Москва, 2001, 2002); международной молодежной научной конференции "XXVII Гагаринские чтения" (Москва, 2001); международной конференции "Распознавание-2001" (Курск, 2001); IV международной научно-технической конференции "Медико-экологические информационные технологии - 2001" (Курск, 2001); II и IV Всероссийской научно-технической конференции "Информационные технологии в науке, проектировании и производстве" (Нижний Новгород, 2000, 2002); VI Всероссийском семинаре "Моделирование неравновесных систем" (Красноярск, 2003); XI Всероссийском семинаре "Ней-роинформатика и ее приложения" (Красноярск, 2003).

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы, включающего 101 источник, 36 из которых — отечественные, 65 — зарубежные. Работа изложена на 177 страницах, содержащих 86 рисунков и 6 таблиц.

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

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

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

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

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

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

Личный вклад автора. В работах, опубликованных в соавторстве и приведенных в конце автореферата, в [2, 5, 6, 1, 15] лично автором разработано устройство ячейки среды репродуцирования логической структуры отказоустойчивого мультиконтроллера на основе характеристики длины маршрута репродуцирования, в [3] автором разработаны клеточные алгоритмы самоорганизации слоя надежного репродуцирования отказоустойчивого мультиконтроллера на основе характеристики живучести, в [7] автором представлены принципы организации среды настройки отказоустойчивого мультиконтроллера, в [10, 8, 14, 13] представлены результаты исследований клеточных алгоритмов репродуцирования логической структуры мультиконтроллера, в [11, 12] автором представлена инструментальная среда моделирования и отладки клеточных алгоритмов, ориентированная на анализ характеристик отказоустойчивых однородных сред.

Основное содержание работы

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

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

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

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

7

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

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

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

Q

Ё min, Q<R, (1)

<7=1

где Cq,^ — длина маршрута программопереноса от отказавшего элемента q до резервного элемента rq, Q — общее число отказавших вершин, а R — общее число резервных вершин.

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

А min{£1Jtl}, (2)

где £] — длина маршрута от текущего элемента до наименее удаленного резервного элемента; — длина маршрута от текущего до резервного элемента в направлении k\\ k £ {1,2,3,4} — номер направления достижимого резервного элемента, 1 — горизонтально вправо, 2 — вертикально вверх, 3— вертикально вниз, 4 — горизонтально влево.

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

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

= £ йЧк), йЧь) = (1-если сг1к Ф ^

¿Г] [ 0, если = LX,

где ЬХ соответствует длине маршрута достижимости, большей, чем любая реальная длина маршрута для данной топологии сети.

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

= тт{Д"?} г* С = С и {(¿ь/1)(г,/)} (3)

где 1УЧ — живучесть узлов-предшественников для элемента (г,/); С — реальная длина маршрута репродуцирования; {(«ьДН»',/)} — дуга, инцидентная узлам (г'1,/1), («',/).

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

v{{p,?)^(¿^/•1)}=4•4? = lx (4)

где Сркч — длина входной дуги вершины (г,/) от узла-предшественника (р, ц) с направления к.

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

Определение I. Графом 0](У,£?1) достижимости называется ориентированная графовая решетка с замкнутыми или разомкнутыми границами, каждая вершина V £ = 1,2, ...,М;/ = 1,2, которой взвешена весом (х[{, х'/) (хЦ € {1.0} — работоспособность/отказ, х'/ е {1,0} — основная/резервная), а каждая исходящая дуга 1).....(щ, у<-1,/> имеет вес чг'(к, характеризующий длину маршрута от вершины и,у до резервной

. „ в £-ом направлении. Пример разметки графа дости-

Рис. 1. Пример построения ,

графа <5, жимости представлен на рис. 1.

9

1 - 2

Рис. 2. Пример построения графа Ог

о з

Определение 2. Графом <?9(1Л ¿4) живучести (см. рис. 2) называется ориентированная графовая решетка с замкнутыми или разомкнутыми границами, каждая вершина Уу е V которой взвешена весом (хЦ,х1/) (хо € {1,0} — работоспособность/отказ, х'/ € {1,0} — основная/резервная), а каждая исходящая дуга («¡у, у,имеет вес 01/\ равный числу исходящих дуг этой вершины на графе имеющих вес, не равный ЬХ. Определение 3. Графом 6з(У,£?з) репродуцирования называется ориентированная графовая решетка с замкнутыми или разомкнутыми границами, каждая вершина у(/ € У(£ = 1,2,...,М;] — 1,2, ...,А0 которой взвешена весом (хЦ, х1Г'), а каждая исходящая дуга (1%', ('-';/, -,-!,/) имеет вес характеризующий длину маршрута от отказавшей вершины до вершины у,/ в направлении Пример построения такого маршрута приведен на рис. 3.

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

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

Для критериев обеспечения живучести, исходящих из характеристик длин маршрутов программопереноса и расстояния до резерва, СПП приобретает вид:

02: У1! -»

Рис. 3. Пример графа <?з

построения

0з

**3 «ЗА

ЗА»

и"

РН^а,^})

| Р,(А, {^Г}), если = wf)

0, если Ф wf

если V/ < А, / € {1,2,3,4}, € {В},В) ф а если 3/ < Л.Ву = а, В/ € {В}. 10

1 14 14 " 1 0, если чг1(к ф ту?"1.

• ш^тТ"/ _» Л17 - / если > О) А (14 = 0),

\уГ + г, = о) л (4 = о) л ^ ьх) л (А1' = о),

ЬХ, (4 = 1) V «гп = ЬХ) V (А^ > 0),

( мя"1 + г, (п'4 ф о) л (х? = о)л = 0) л ф о),

^ = О, (П& = 0) V > 0) V = 0),

I Г /..'7 1 \ л /..И л\ » /ттМ /

к 1*0 = а; (.л/ = и; м Vlljfe 7= и/.

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

08 : О1' О™", ГГп = тш{4'_1,¿?и, С'''. 4/+1>-

09 : - в\ = 4 = ( I'

I

При этом подстановка Оз приобретает вид:

а . гут« ^РЯ _ пц п</ _ I о™, {¿У"}), если (</? = £>""'") ^->11», о, если ¿'V Я™,

Вариант алгоритма, опирающийся при разрешении конфликтов как на метрические характеристики клеточного массива, так и на характеристику живучести, описан на основе системы подстановок {0], .,.&)}, рассмотренных в предыдущем подпункте. Для обеспечения выбора направления приема и передачи сигналов программопереноса по гибридному критерию модифицированы подстановки 03 и

Р2(Л, гфтп, {О'1}, {Щя})), если = ВШп

0, если 4чфОтт,

где {В}, {С}) — функция, результатом которой является множество весов выходных дуг графа 63, в котором элементы, соответствующие весам

если Ф ЬХ, если — ЬХ.

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

г (а, {В}, {с}) = {С\а, Ви с,), I = 1,4}, С(вЛс) =

если а ф Ь, если а = Ь.

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

ЫШ-

[1, если V/ е {1.2,3,4} <к,В)> В*, [О, если 3/€ {1,2,3,4} < к, В/ <Вк

Аналогичным образом модифицирована подстановка 9ц:

04:

п., = Г Ык,г{чГ,{ч'{к},{4})), если V/=

1

ЬХ, если уг{к ^ VI

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

Характер взаимодействия ячеек однородной среды между собой и с мультиконтроллером определяет структурно-функциональную организацию каждой из ячеек (см. рис. 4). Укрупненно в составе подобного устройства можно выделить 3 подсистемы:

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

1. Подсистема, управляющая передачей сигналов достижимости ближайшим соседним ячейкам, на основе информации о значениях сигналов достижимости W'/ = {w'/j.-.w^} и сигналов репродуцирования W3' = {w^.-.w^J, поступающих от соседних ячеек, а так же сигналов хг и xq, поступающих от соответствующего ячейке МК.

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

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

Помимо перечисленных подсистем, в структуру ячейки необходимо ввести также блок-формирователь сигналов 5 и LX (RSG, reference signal generator).

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

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

К функциональным возможностям пакета относятся:

□ визуальный ввод конфигурации резервов и отказов на модели произвольной размерности, с возможностью ее сохранения и загрузки в файл;

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

□ пошаговое выполнение клеточного алгоритма с визуальным контролем обмена сигналов в системе;

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

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

□ форматирование отчетов в виде гипертекстовых документов в формате HTML и ЮеХ.

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

13

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

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

2. Максимальная длина маршрута репродуцирования.

Стах = тах{\^}, \IVij € ¿?з,

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

Для выполнения сравнительного анализа алгоритмов репродуцирования были рассмотрены 12 вариантов правила выбора направлений приема и 4 варианта правила передачи сигналов репродуцирования. В дальнейших рассуждениях варианты правил приема сигналов программопереноса обозначены соответственно как /1 4-/12, а варианты правил передачи этих сигналов — как 0\ 4-О4. Приведенные выше показатели были рассчитаны для всех 48 алгоритмов на матрице 7 х 7 с фиксированным размещением резервных элементов. После отборочной оценки характеристик, из рассмотренных алгоритмов были выбраны, как показавшие наилучшие предварительные результаты, следующие их варианты:

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

О Для алгоритмов, использующих только характеристику живучести высокие значения К показали варианты (/9,01) и (/9,Ог), использующие для. выбора направления приема сигналов репродуцирования критерий минимума показателя живучести, а для выбора направления их передачи — направление ближайшего резерва, соответственно с совпадающим и обратным порядком > назначения приоритетов.

□ Из множества вариантов гибридных алгоритмов, также на основе значения корректирующей способности, были выбраны варианты (/11,04), (/12, Ог), учитывающие при приеме сигналов программопереноса как значения длин маршрутов репродуцирования, так и их показатели живучести, а при передаче этих сигналов в первом случае — обе характеристики, а во втором — только расстояние до резерва.

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

л- 1 л = 2 л = 3 л = 4 л-5 л-6 я-7

№..од ад ¿яах[л) т 00% 30% -0.1% 08% 4.1% 9 1% 1.9% 106% 19.6% 26% 13 9% 26 9% 6 5% 215% 27.7% 22.3% 31.5% 30.2% 74.7% 30 6% 18.2%

(/9,0,) К(п) £ми:М Пп) 00% 2.1% 19 5% 0 8% -0 4% 14 0% 2.5% 4 3% 10.2% 5.3% 2 6% 45% 14 0% 72% 2.9% 35 1% 11.4% 13 2% 103 4% 23.9% 23.5%

(Л, ОД ад ¿»«(л) П") 0.0% 3.8% 19.1% 0.8% 1 0% 14.0% 2.5% 3.1% 106% 47% 3.6% 27% 13 6% 4 2% 29% 33.1% 98% 5.7% 108 4% 18.7% 15.0%

!/ц.о,) т ¿яииг(я) т 00% 10% 19.7% 0.8% 0.4% 148% 2.6% 44% 10 9% 49% 6.9% 76% 14.6% 118% 93% 33.1% 18 9% 15.2% 117.1% 33.5% 21.4%

(/12.ОД ад Г(Л) 00% 38% 19.4% 08% 0.7% 14 4% 2.5% 6.6% 12 2% 45% 60% 10 1% 14 0% 12.9% 9 5% 33 5% 22 6% 21 0% 115.5% 37.9% 27.9%

Для сравнения с базовым вариантом рассмотрены относительные значения полученных экспериментальных данных К, Стах и Т, вычисленные по формуле:

—хо Хо

100%,

где Х{ — значение соответствующего показателя для <-го отобранного варианта алгоритма, хо — значение показателя для базового ва-

Рис. 5. Изменение показателей К, Стсх и Т выбранных клеточных алгоритмов по отношению к базовому варианту (/2, Ог)

рианта алгоритма. Значения перечисленных показателей для кратности отказов п — 1 ч- 7 сведены в таблицу на рис. 5.

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

тц{п)

1-К0(п)

1-ВД'

Рис.

6. Зависимость доли некорректируемых отказов ту от их кратности

где /Со — корректирующая способность ¿-го варианта алгоритма, Ло — корректирующая способность базового алгоритма репродуцирования, п — количество отказов. Зависимость 77 от кратности отказов проиллюстрирована графически на рис. 3, из которого видно, что в предельном случае эта величина варьируется от 2 до 4, что позволяет сделать вывод о существенном повышении эффективности использования резерва при реализации клеточных алгоритмов репродуцирования на основе предложенных принципов и правил.

Основные результаты работы

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

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

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

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

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

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

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

Список РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Патент РФ №2197745. Ячейка однородной среды / Родионов A.B. и др. // Бюлл. 2003. №3.

2. Колосков В.А., Родионов A.B., Мииевич JI.M. Континуально-логическая самоорганизующая сеть // Телекоммуникации. — 2001. — № 9. — С. 24-29.

3. Колосков В.А., Родионов A.B., Медведева М.В. Клеточные алгоритмы обеспечения живучести микроконтроллерных сетей // Телекоммуникации. — 2002. - № 3. - С. 20-26.

4. Родионов A.B. Моделирование клеточной оболочки отказоустойчивых муль-тимикропроцессоров // Материалы международного конгресса "Искусственный интеллект". — М.: Физматлит, 2001, — С. 746-750.

5. Родионов A.B., Медведев A.B. Континуально-логические операции самоорганизации отказоустойчивого мультимикроконтроллера // Сборник научных трудов III всероссийской научно-технической конференции "НЕЙРОЙНФОРМАТИКА-200Г. — М.: МИФИ, 2001,- С. 125-131.

6. Родионов A.B., Миневич JI.M. Ячейка распределенной однородной среды самоорганизации управляющей системы // Тезисы докладов международной молодежной научной конференции "XXVII Гагаринские чтения". — М.: МАТИ, 2001,- С. 87-88.

7. Родионов A.B., Малышев A.B., Миневич JI.M. Самоорганизующаяся коммуникационная среда отказоустойчивого мультимикроконтроллера // Тезисы докладов II всероссийской научно-технической конференции "Информационные технологии в науке, проектировании и производстве". — Нижний Новгород: НГТУ, 2000. - С. 2.

8. Родионов A.B., Медведева М.В. Клеточные алгоритмы обеспечения живучести в однородных системах // Научная сессия МИФИ — 2002. IV Всероссийская научно-техническая конференция "Нейроинформатика-2002": Сборник научных трудов. - М.: МИФИ, 2002. - С. 181-188.

9. Родионов A.B. Живучесть в отказоустойчивых клеточных системах // Информационные технологии в науке проектировании и производстве: Материалы четвертой Всероссийской научно-технической конференции. В 3-х частях. Часть 3. — Н. Новгород: Межрегиональное Верхне-Волжское отделение Академии технологических наук РФ, 2002. — С. 2.

10. Родионов A.B., Колосков В.А. Исследование самоорганизующегося муль-тимикроконтроллера с программируемым резервом // Материалы международной конференции "Распознавание-2001".— Курск: КГТУ, 2001. — С.211-212.

11. Родионов A.B., Колосков В.А. Интегрированный подход к описанию, моделированию и анализу клеточных алгоритмов // Тезисы докладов IV международной научно-технической конференции "Медико-экологические информационные технологии - 2001". - Курск: КГТУ, 2001. - С. 249-250.

12. Колоскова Г.П., Родионов A.B. Моделирование высоконадежной клеточной среды восстановления мультиконтроллеров // "Моделирование неравновесных систем": сборник трудов VI Всероссийского семинара. — Красноярск, 2003, - С. 73-74.

13. Родионов A.B., Колоскова Г.П. Повышение корректирующей способности клеточных алгоритмов восстановления мультиконтроллеров // "Нейроин-форматика и ее приложения": материалы XI Всероссийского семинара . — Красноярск, 2003. - С. 84-85.

14. Родионов A.B., Колоскова Г.П. Высоконадежное репродуцирование логической структуры мультиконтроллеров // Проблемы специального машиностроения. - Тула, ТГУ, 2003. - С. 56-60.

15. Родионов A.B., Миневич Л.М. Континуально-логическая самоорганизующая сеть. В кн. Волгин Л.И. Релятор и реляторная схемотехника: Логико-алгебраические основы и применения / Отв. за выпуск Абрамов Г.Н. — ТГИС, 2003. - С.121-132.

Подписано в печать 21.10.2003 г. Формат 60x84 1/16 Печ. листов 1,0. Тираж 100 экз. Заказ 124 Издательско-полиграфический центр Курского государственного технического университета 305040, г. Курск, ул. 50 лет Октября, 94

18272 p 18 272

I

Введение

1 Параллельная децентрализованная организация репродуцирования программ мультиконтроллеров

1.1 Структурно-функциональная организация отказоустойчивых многопроцессорных систем.

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

1.3 Анализ способности к репродуцированию и основные задачи исследований.

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

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

2.1.1 Принцип минимизации искажения логической структуры мультиконтроллера.

• 2.1.2 Принцип достижимости.

2.1.3 Принцип живучести.

2.1.4 Принцип устранения конфликтов репродуцирования

2.2 Математические модели надежного репродуцирования . 50 2.2.1 Графовая модель самоорганизации мультимикроконтроллера

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

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

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

2.3.3 Клеточный алгоритм гибридного репродуцирования . . 76 2.4 Выводы к главе.

3 Структурно-функциональная организация сред надежного репродуцирования

3.1 Ячейка однородной среды репродуцирования по удаленности

3.1.1 Структурная организация ячейки.

3.1.2 Функциональная организация блоков ячейки.

3.1.3 Примеры функционирования среды репродуцирования

3.2 Ячейка однородной среды репродуцирования по живучести

3.2.1 Структурно-функциональная организация среды репродуцирования

3.2.2 Режимы функционирования среды.

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

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

4.1 Характеристика среды моделирования.

4.1.1 Главное окно программы.

4.1.2 Режим вычисления интегральных характеристик клеточного алгоритма.

4.1.3 Режим вычисления относительных характеристик

4.1.4 Режим вычисления характеристик для заданной конфигурации резерва.

4.1.5 Интерактивный режим. 4.2 Исследование и сравнительный анализ алгоритмов репродуцирования

4.2.1 Отбор вариантов клеточных алгоритмов для проведения сравнительного анализа.

4.2.2 Сравнительный анализ отобранных вариантов клеточных алгоритмов

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

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

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

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

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

Проблемы обеспечения отказоустойчивости управляющих систем рассмотрены в работах Пархоменко П.П., Варшавского В.И., Хорошевского В.Г., Каравая М.Ф., Харченко В.Л., Авижениса А., Реннелса Д., Сами М., Куна С. и др. авторов [1-14]. Исследования показывают, что перспективным методом обеспечения отказоустойчивости масштабируемых мульти-контроллеров является их самоорганизация, заключающаяся в восстановлении (репродуцировании) программы управления технологическими операциями на множестве работоспособных микроконтроллеров, допускающих перенастройку на один из хранимых в них алгоритмов. Хранение в каждом микроконтроллере множеств алгоритмов физических соседей обеспечивает оперативное репродуцирование, необходимое для безостановочной работы в реальном времени.

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

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

Диссертационная работа выполнялась в рамках тематического плана госбюджетных НИР по Единому заказ-наряду Госкомвуза РФ Курского государственного технического университета.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы обсуждались на: международном конгрессе "Искусственный интеллект" (Таганрог, 2001); III и IV Всероссийской научно-технической конференции "НЕЙРОИНФОРМАТИКА" (Москва, 2001, 2002); международной молодежной научной конференции "XXVII Гагаринские чтения" (Москва, 2001); международной конференции "Распознавание-2001" (Курск, 2001); IV международной научно-технической конференции "Медико-экологические информационные технологии - 2001" (Курск, 2001); II и IV Всероссийской научно-технической конференции "Информационные технологии в науке, проектировании и производстве" (Нижний Новгород, 2000, 2002); VI Всероссийском семинаре "Моделирование неравновесных систем" (Красноярск, 2003); XI Всероссийском семинаре "Нейроинформатика и ее приложения" (Красноярск, 2003).

Публикации. Результаты исследований отражены в 15 печатных работах [15-29], в число которых входят 3 публикации в центральных печатных изданиях, и защищены патентом Российской Федерации.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы, включающего 101 источник, 36 из которых — отечественные, 65 — зарубежные. Работа изложена на 177 страницах, содержащих 86 рисунков и 6 таблиц.

4.3 Выводы к главе

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

1. Пархоменко П.П. Гиперкубовая архитектура многопроцессорных вычислительных систем с реберным расположением процессорных элементов // Известия АН СССР. - Техническая кибернетика. — 1994. — № 2.- С. 170-182.

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

3. S.Y. Kung, S.N. Jean, C.W. Chang. Fault-tolerant array processors using single-track switches // IEEE Trans. Computers. — Apr. 1989. — Vol. 38, no. 4,- Pp. 501-504.

4. Каравай М.Ф. Инвариантно-групповой подход к исследованию k-отказоустойчивых систем // Автоматика и телемеханика,— 2000.— № 1.- С. 145-156.

5. Каляев И.А. Принципы организации децентрализованных систем управления коллективов микророботов // Механотроника. — 2000.— № 6.

6. Каляев И.А., Гайдук А.Р. Однородные нейроподобные структуры в системах выбора действий интеллектуальных роботов. — М.:«Янус-К», 2000.-С. 280.

7. Макаров И.М., Рахманкулов В.З. Групповое управление роботами-манипуляторами с распределенно-централизованной организацией обработки информации // Микропроцессорные системы управления в робототехнике. — М.Наука, 1984.

8. Сироткин У.С., Подураев Ю.В., Богачев Ю.П. Механотронные технологические машины в машиностроении // Механотроника, автоматизация, управление. — 2003. — № 4.

9. Дж. By, К. Хуанг. Сбалансированный гиперкуб и устойчивые к отказам вложения колец // Программирование. — 1995,— № 1.— С. 5562.

10. Wu, Gao, Li and Min. Optimal iault-tolerant routing in hypercubes using extended safety vectors // ICPADS: International Conference on Parallel and Distributed Systems, National Tsing Hua University, Hsinchu, Taiwan, Republic of China. — 2000.

11. Wu J. On finding a Hamiltonian path in a tournament using semi-heap // Parallel Processing Letters. 2000. - Vol. 10, no. 4. - P. 279.

12. Wu J. Fault-tolerant adaptive and minimal routing in mesh-connected multicomputers using extended safety levels // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11, no. 2. - P. 149.

13. Зонкевич С.Л., Ющенко А.С. Управление роботами. Основы управления манипуляционными роботами. — М.: МГТУ им. Н.Э. Баумана, 2000.

14. Юревич Е.И. Системы управления роботами. — С-Пб.: СГТУ, 2000.

15. Патент РФ №2197745. Ячейка однородной среды / Родионов А.В. и др. // Бюлл. 2003. №3.

16. Колосков Б.А., Родионов А.В., Миневич JI.M. Континуально-логическая самоорганизующая сеть // Телекоммуникации. — 2001.— № 9. С. 24-29.

17. Колосков В.А., Родионов A.B., Медведева М.В. Клеточные алгоритмы обеспечения живучести микроконтроллерных сетей // Телекоммуникации. 2002. - № 3. - С. 20-26.

18. Родионов A.B. Моделирование клеточной оболочки отказоустойчивых мультимикропроцессоров // Материалы международного конгресса "Искусственный интеллект". — М.: Физматлит, 2001. — С. 746-750.

19. Родионов A.B., Медведев A.B. Континуально-логические операции самоорганизации отказоустойчивого мультимикроконтроллера // Сборник научных трудов III всероссийской научно-технической конференции "НЕЙРОИНФОРМАТИКА-2001". М.: МИФИ, 2001. - С. 125131.

20. Родионов A.B., Миневич J1.M. Ячейка распределенной однородной среды самоорганизации управляющей системы // Тезисы докладов международной молодежной научной конференции "XXVII Гагарин-ские чтения". М.: МАТИ, 2001. - С. 87-88.

21. Родионов A.B., Медведева М.В. Клеточные алгоритмы обеспечения живучести в однородных системах // Научная сессия МИФИ — 2002. IV Всероссийская научно-техническая конференция "Нейроинформатика-2002": Сборник научных трудов. — М.: МИФИ, 2002,- С. 181-188.

22. Родионов A.B., Колосков В.А. Исследование самоорганизующегося мультимикроконтроллера с программируемым резервом // Материалы международной конференции "Распознавание-2001". — Курск: КГТУ, 2001.-С. 211-212.

23. Колоскова Г.П., Родионов A.B. Моделирование высоконадежной клеточной среды восстановления мультиконтроллеров // "Моделирование неравновесных систем": сборник трудов VI Всероссийского семинара. Красноярск, 2003. - С. 100-101.

24. Родионов A.B., Колоскова Г.П. Повышение корректирующей способности клеточных алгоритмов восстановления мультиконтроллеров // "Нейроинформатика и ее приложения": материалы XI Всероссийского семинара . — Красноярск, 2003. — С. 84-85.

25. Родионов A.B., Миневич JI.M. Континуально-логическая самоорганизующая сеть. В кн. Волгин Л.И. Релятор и реляторная схемотехника:

26. Логико-алгебраические основы и применения / Отв. за выпуск Абрамов Г.Н. ТГИС, 2003. - С.121-132.

27. Родионов А.В., Колоскова Г.П. Высоконадежное репродуцирование логической структуры мультиконтроллеров // Проблемы специального машиностроения. — Тула, ТГУ, 2003. — С. 56-60.

28. K.J.R. Liu and К. Yao. Real-Time Algorithm-Based Fault-Tolerance for QRD Recursive Least-Squares Systolic Array: A Graceful Degradation Approach // Technical Report of System Research Center. — University of Maryland, USA, 1991.

29. C. Ortega-Sanchez and Andrew Tyrrell. MUXTREE revisited: Embryon-ics as a Reconfiguration Strategy in Fault-Tolerant Processor Arrays // In Proceedings of ICES98. — Lauzanne, Switzerland, 1998.

30. A.M. Tyrrell, G.S. Hollingworth, S.L. Smith. Evolutionary Strategies and Intrinsic Fault Tolerance // in proceedings of 3rd NASA/DoD Workshop on Evolvable Hardware. — Long Beach, California, USA, 2001.

31. P. Layzell. Reducing hardware evolution's dependency on FPGAs // In Proceedings of MicroNeuro '99, 7th International Conference on Microelectronics for Neural, Fuzzy and Bio-inspired Systems. — 1999.

32. G. Ochoa. On Genetic Algorithms and Lindenmayer Systems // In Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature. — Springer-Verlag, 1998.

33. K. Ohkura, K. Sera and K. Ueda. A learning multi-agent approach to dynamic scheduling for autonomous distributed manufacturing systems // In Proceedings of 15th International Conference on Computer-Aided Production Engineering (CAPE 99). — 1999.

34. Ушаков И.А. Построение высоконадежных систем. — М.: Знание, 1974.

35. Ю.К. Беляев, В.А.Богатырев и др. Надежность технических систем: Справочник / Под ред. Ушакова И.А. — М.: Радио и связь, 1985.

36. A. Thompson. Evolutionary techniques for fault tolerance // In Proceedings of the UKACC International Conference on Control (CON-TROL'96). 1996.

37. A. Thompson and P.Layzell. Evolution of Robustness in an Electronics Design // In Proceedings of the 3rd International Conference on Evolv-able Systems. — 1999.

38. A. Thompson and C.Wasshuber. Evolutionary design of single electron systems // In Proceedings of the 2nd NASA/DoD workshop on evolvable hardware (EH2000). 1999.

39. T. Horita, I. Takanami. Fault-tolerant processor arrays based on the Ц-track switches with flexible spare distributions // IEEE Trans. Computers. Jun. 2000. - Vol. 49, no. 6. - Pp. 542-552.

40. Колосков В.А., Титов B.C. Метод самоорганизации отказоустойчивой мультимикроконтроллерной сети // Автоматика и телемеханика. — 1998.-№ 3.-С. 173-183.

41. Медведева М.В., Медведев А.В., Колосков В.А., Старков В.А. Клеточная самоорганизация программируемых отказоустойчивых муль-тимикроконтроллеров. — Курский гуманитарно-технический институт, 2000.

42. Su C.-C., Shin K. G. Adaptive fault-tolerant deadlock-free routing in meshes and hypercubes // IEEE Transactions on Computers. ■— 1996.— Vol. 45, no. 6. Pp. 666-683.

43. Soon Cheol Baeg, Sang Kyu Park, Joong Min Choi, Myung Wuk Jang, and Young Hwan Lim, Cooperation in Multi-agent Systems, Intelligent Computer Communications (ICC '95), Cluj-Napoca, Romania, pp. 1-12, June 1995.

44. Bradley D. W., Tyrell A. M. Immunotronics: Hardware fault tolerance inspired by the immune system // ICES. — 2000. — Pp. 11-20.

45. C.Ortega and A.M.Tyrrell. Biologically Inspired Real-Time Reconfiguration Technique for Processor Arrays // In Proceedings of 5th IFAC Workshop on Algorithms and Architectures for Real-Time Control. — Elsevier Science Ltd., Oxford, 1998.

46. C.Ortega and A.M.Tyrrell. Design of a Basic Cell to Construct Embryonic Arrays // IEE Proceedings on Computers and Digital Techniques. — 1998.

47. C.Ortega and A.M.Tyrrell. Evolvable Hardware for Fault-Tolerant Applications // IEE Colloquium on Evolvable Hardware Systems. — London, 1998.

48. C.Ortega and A.M.Tyrrell. Self-Repairing Multicellular Hardware: A Reliability Analysis // in Floreano D. et al. (Eds.), Advances in Artificial Life, Procs. of the 5th European Conference, ECAL. — Lausanne, Switzerland, 1999.

49. Jonathan Ledlie, Jacob Taylor, Laura Serban, and Margo Seltzer. Self-organization in peer-to-peer systems. In 10th EW SIGOPS, September 2002.

50. Колосков В.А., Медведева М.В., Медведев А.В. Клеточная самоорганизация отказоустойчивого мультимикроконтроллера // "Автоматика и вычислительная техника". — 2000. — № 2. — С. 64-73.

51. Колосков В.А., Медведева М.В. Механизм клеточной самоорганизации отказоустойчивого мультимикроконтроллера // Труды III всероссийской научно-технической конференции "Нейроинформатика-2001". М.: МИФИ., 2001.- Т. 2. - С. 131-139.

52. А.Н. Jackson, A.M. Tyrrell. Asynchronous Embryonics // in proceedings of 3rd NASA/DoD Workshop on Evolvable Hardware. — Long Beach, California, USA, 2001.

53. A.M.Tyrrell. Computer Know Thy Self! : A Biological Way to Look at Fault-Tolerance // In Proceedings of the 25th Euromicro Conference. — 1999.

54. Chalasani S., Boppana R. V. Communication in multicomputers with nonconvex faults // European Conference on Parallel Processing. —■ 1995.- Pp. 673-684.

55. Dubacq J.-C., Durand B., Formenti E. Kolmogorov complexity and cellular automata classification // Theoretical Computer Science. — 2001.— Vol. 259, no. 1-2.- Pp. 271-285.

56. D. Bradley, C. Ortega-Sanchez and A. Tyrrell. Embryonics + Im-munotronics: A Bio-Inspired Approach to Fault Tolerance // In Proceedings of 2nd NASA/DoD Workshop on Evolvable Hardware. — Silicon Valley, USA, 2000.

57. D.W. Bradley, A.M. Tyrrell. The Architecture for a Hardware Immune System // in proceedings of 3rd NASA/DoD Workshop on Evolvable Hardware. — Long Beach, California, USA, 2001.

58. S. Hagg, F. Ygge, R. Gustavsson, H. Ottosson, DA-SoC: A Testbed for Modelling Distribution Automation Applications Using Agent-Oriented Programming, Proceedings of the MAAMAW '94 Workshop, Odense, Denmark, August 1994.

59. I. Harvey, P. Husbands, D. Cliff, A. Thompson and N. Jakobi. Evolutionary Robotics: the Sussex approach // Robotics and Autonomous Systems. 1996,- no. 20.

60. I.Harvey. Artificial evolution and real robots // Artificial Life and Robotics. 1996.- no. 1 (1).

61. P. Husbands. Evolving robot behaviours with diffusing gas networks // In Proceedings of the First European Workshop on Evolutionary Robotics (EvoRobot98).- Springer Verlag, 1998.

62. Колосков В.А. и др. Построение клеточных алгоритмов самоорганизации отказоустойчивых мультимикроконтроллеров // "Автоматика и телемеханика". 2000. - № 7. - С. 171-182.

63. P. Husbands, Т. Smith, М. O'Shea, N. Jakobi, J. Anderson and A. Philippides. Brains, gases and robots //In Proceedings of the 8th International Conference on Artificial Neural Networks (ICANN98). — London: Springer Verlag, 1998.

64. P. Husbands, T. Smith, N. Jakobi, and M. O'Shea. Better living through chemistry: Evolving GasNets for robot control // Connection Science 10 (4).- 1998.

65. D.W.Bradley and A.M. Tyrrell. Immunotronics : Hardware Fault Tolerance Inspired by the Immune System // In Proceedings of the 3rd International Conference on Evolvable Systems. — Springer-Verlag, 2000.

66. M. J. Katchabaw, H. L. Lutfiyya, A. D. Marshall, and M. A. Bauer. Policy-driven fault management in distributed systems. In preparation., 1996.

67. Kim Y. S., Kim H. S., Kwon W. H. Design of a network-based robot control system using fip // Asian Control Conference. — 2000. — Pp. 22292234.

68. Колосков В.А., Медведева M.B., Медведев А.В. Клеточная самоорганизация отказоустойчивых мультимикроконтроллеров с программируемым резервом // "Автоматика и вычислительная техника". — 2000. — № 6.

69. P. Kuntz, P. Layzell, and D.A.Syners. A Colony of Ant-like Agents for Partitioning in VLSL Technology // In Proceedings of the Fourth European Conference on Artificial Life. — MIT Press, 1996.

70. Kutrib M. Efficient universal pushdown cellular automata and their application to complexity // Lecture Notes in Computer Science. — 2001. — Vol. 2055. P. 252.

71. Lacy W. S., Cruz-Rivera J. L., Wills D. S. The offset cube: A three-dimensional multicomputer network topology using through-wafer optics // IEEE Transactions on Parallel and Distributed Systems. — 1998. Vol. 9, no. 9. - P. 893.

72. P. Layzell. The 'Evolvable Motherboard'. A test platform for the research of intrinsic hardware evolution // Cognitive Science Research Paper 479. — University of Sussex, 1998.

73. Волгин JI.И. Элементный базис предикатной алгебры выбора // Известия АН СССР. Техническая кибернетика. — 1987. — № 5. — С. 7579.

74. Волгин Л.И. Релятор и реляторная схемотехника // Измерения, контроль, автоматизация. выпуск 2(70). — М.: ИНФОРМПРИБОР, 1989.- С. 61-78.

75. Волгин Л.И. Представление функций непрерывной логики в предикатной алгебре выбора и синтез реляторных процессоров // "Электронное моделирование". 1998. - № 2. - С. 3-21.

76. Волгин Jl.И. Элементный базис реляторной схемотехники. — Тольятти: ПТИС, 1999.- С. 71.

77. Т. C. Lueth and T. Laengle. Fault-tolerance and error recovery in an autonomous robot with distributed controlled components. In H. Asama, T. Fukuda, T. Arai, and I. Endo, editors, Distributed Autonomous Robotic Systems. Springer-Verlag, 1994.

78. T. Lueth and T. Laengle. Fault-tolerance and error recovery in an autonomous robot with distributed controlled components // Distributed Autonomous Robotic Systems. — Springer-Verlag, 1994.

79. Efficient adaptive routing in networks of workstations with irregular topology // Communication, Architecture, and Applications for Network-Based Parallel Computing. 1997. - Pp. 46-60.

80. Software based fault-tolerant oblivious routing in pipelined networks // Proceedings of the 24th International Conference on Parallel Processing. Oconomowoc, WI: 1995.- Pp. 1:101-105.

81. A. Thompson and P. Layzell. Analysis of unconventional evolved electronics // Communications of the Association of Computing Machinery, Vol 42, No. 4.- 1999.

82. A. Thompson. On the automatic design of robust electronics through artificial evolution // In Proceedings of the 2nd International Conferenceon Evolvable Systems: From Biology to Hardware (ICES98), Lausanne, Switzerland. — Springer-Verlag, 1998.

83. Thottethodi M., Lebeck A. R., Mukherjee S. S. Self-tuned congestion control for multiprocessor networks // HPCA. — 2001. — P. 107.

84. Wooldridge M. Intelligent agents // Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence / Ed. by G. Weiss. — Cambridge, MA, USA: The MIT Press, 1999,- Pp. 27-78.

85. Zakrevski L., Karpovsky M. G. Fault-tolerant message routing for multiprocessors // IPPS/SPDP Workshops. 1998. - Pp. 714-730.

86. L. Zakrevski, M. G. Karpovsky, Fault-tolerant message routing in computer networks, Proc. Int. Conf. on Parallel and Distributed Processing Techniques and Applications, 1999, pp. 2279-2287.

87. R.S. Zebulum, M.A. Pacheco and M. Vellasco. Comparison of different evolutionary methodologies applied to electronic filter design // In Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC98), Anchorage, Alaska. 1998.

88. Thomas Worsch. Programming environments for cellular automata. Technical report 37/96, Universität Karlsruhe, Fakultat fur Informatik, November 1996.

89. Christian Hochberger and Rolf Hoffmann. CDL — a language for cellular processing. In Giacomo R. Sechi, editor, Proceedings of the Second International Conference on Massively Parallel Computing Systems, pages 41-46. IEEE, 1996.

90. Skillicorn D. B., Talia D. Models and languages for parallel computation // ACM Computing Surveys. 1998. - Vol. 30, no. 2. — Pp. 123169.

91. Giandomenico Spezzano and Domenico Talia. CARPET: A programming language for parallel cellular processing. In Proc. 2nd European School on Parallel Programming Environments (ESPPE 96), pages 71-74, Alpe d'Huez, April 1996.

92. Spezzano and D. Talia, A high-level language for programming cellular algorithms on parallel machines, in: Proc. 2nd Conference ACRI96 (Springer-Verlag, Workshop in Computing Series, London, 1996).

93. G. Spezzano and D. Talia, A high-level cellular programming model for massively parallel processing, in: Proc. 2 nd Int. Workshop on High-Level Programming Models and Supportive Environments (HIPS97) (IEEE Computer Society, 1997) 55-63.

94. Telford S. D. A cellular automata simulation environment for modelling soil bioremediation // HPCN Europe. 1999. - Pp. 1143-1146.

95. Wooldridge M., Ciancarini P. Agent-Oriented Software Engineering: The State of the Art // First Int. Workshop on Agent-Oriented Software Engineering / Ed. by P. Ciancarini, M. Wooldridge. — Springer-Verlag, Berlin, 2000. Vol. 1957. - Pp. 1-28.