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

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

Савенков Николай Анатольевич

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

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

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

Курск-2006

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

Научный руководитель: д.т.н., профессор Колосков В. А.

Официальные оппоненты: д. т. н., профессор Кореневский H.A.,

к. т. н., доцент Жмакин А.П.

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

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

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

Автореферат разослан « 27 » марта 2006г.

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

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

^Рятенко Е.А.

Д,00&й з

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

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

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

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

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

Последние разработки в области адаптивной маршрутизфДО^АГОШЗДМфМЗДя |

с. о»

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

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

Диссертационная работа выполнена по гранту Федерального агентства по образованию А.04-3.16-701 "Разработка алгоритмов и сред обмена данными в мигрирующей логической структуре отказоустойчивого мультиконтроллера", договор подряда № 1.255.04/1.

Объектом исследования является отказоустойчивый мультиконтроллер со средствами восстановления логической структуры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы обсуждались на' Международной научно-технической конференции "Распознавание 2001" (г. Курск. 2001г.); 3-й Международной научно-технической конференции "Измерение, контроль, информатизация" (г Барнаул, 2002г.); УТТ-й Международной научно-технической конференции "Медико-экологические информационные технологии - 2004" (г. Курск, 2004г.): ХХХ1-Й Международаой научной молодежной конференции "Гагаринские чтения" (г. Москва, 2005г.), 1Х-й Международной научно-технической конференции "Решетневские чтения" (г. Красноярск, 2005г.); V Международной конференции "Идентификация систем и задачи управления" (г. Москва, 2006г.)".

Публикации. Результаты диссертационного исследования опубликованы в 7

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

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

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

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

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

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

Объем и структура работы диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 83 источника. Работа содержит 139 страниц текста, 67 рисунков и 4 таблицы.

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

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

В первой главе рассматриваются многопроцессорные архитектуры (8150, \tISD, Б1МО, МЕМО), проведен анализ их достоинств и недостатков. Рассмотрение различных топологий соединения множества процессорных элементов выявило основные преимущества регулярных структур (куб, гиперкуб, плоская решетка): полная регулярность структуры, простота наращивания вычислительной

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

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

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

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

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

Предложена трехуровневая модель ячейки настраиваемого мультиконтроллера (рис. 1).

Мулыиконтролгар

Рис. 1. Уровни взаимодействия ячеек ММК

Составными частями уровня управления являются МК, образующие ядро

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

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

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

123456789

Рис. 2. Настройка микроконтроллеров на новые ПМ

Работа предлагаемого алгоритма адаптивной маршрутизации основывается на применении таблиц достижимостей (ТД), находящихся в каждом модуле распределенной системы. В ячейке ЗДоД/У] таблицы достижимостей модуля с физическим адресом (//) хранится числовой код ЛГЛ^е [1,2,3,4], показывающий направление, в котором текущему модулю необходимо передать сообщение для достижения модуля-приемника с логическим адресом (¿70-

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

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

При передаче сообщения элементу с логическим адресом [/'/] каждый транзитный модуль [/,/) системы обращается к своей таблице достижимости к ячейке ЗДгуЛ' ^Х из которой извлекает код направления, в котором и передает принятое сообщение. При наличии отказа линии связи в направлении указанном в таблице достижимости, направление ретрансляции сообщения меняется на ортогональное. При использовании алгоритма адаптивной маршрутизации не используется физический адрес приемника (программного модуля), т.е. его физическое местоположение в общем случае не известно и в процессе функционирования мультикон-троллера может измениться.

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

дуг графов С?2 и 02 .

Правило 1. Вершина в! соединяется исходящими ненулевыми дугами с

соседними вершинами Уу.1, у^+ь у,.^, уж>/ если выполняется одно из следующих условий:

- существует хотя бы одна входящая в вершину Уд дуга графа С?1 и для дуги е и в направлении & графа структуры Св выполняется условие 0;

- для текущей вершины у^ выполняется условие и для дуги и^е и графа 0$ в к-ом направлении выполняется условие £* М).

Правило 2. Вершина уу графа 02 соединяется исходящей дугой с весом qkJ=*\ с соседней вершиной в к-ом направлении только, если для данной вершины выполняется условие или существует хотя бы одна входящая дуга графа

С2 с весом отличным от нуля и в данном направлении входящая дуга графа имеет минимальный ненулевой вес <1$ среди всех входящих дуг.

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

С?! и 02 (подстановки (¿1 и и изменение направления ретрансляции сообщения в случае отказа линии связи в соответствующем направлении (подстановка взУ __

пипЦ-Ч с1[]+1)+\, приХу &

((4~1,; ?4 0)У(4+1'/ фЩЧУ'^*1 *0));

1, 1фи

МхЫ, ЩлЕ^ =1

0, при ((4-и =0)& ~0)& =0)& (с/{'->+1 = 0));

01: 4'«

Яг

Я? =

й:

где хн

Ж]" ^ —

1,еслиv9{J+1 vqi+1'■, чд^-^&уу *0);

0, иначе;

V V ¿'ЕрЕ? V д^Е^Е^Е^)

V ^^ V д^Е^Е^Е^ V

V д^Е^Е^ ч^БрЕ? V ->

1, если текущая вершина является источником,

0, если текущая вершина является транзитной;

1, ¿сувд текущая вершина является адресатом, 0, если текущая вершина является транзитной;

£4Уе{0,1} - вес дуги графа йц (определяет работоспособность/отказ линии связи в направлении/:);

[0.. .МхЩ - вес дуги в направлении к графа С), М и N - число строк и столбцов ММК;

д^е {0,1} - вес дуги в направлении к графа С2 ;

ке {1,2,3,4} - направления исходящих из вершины дуг 1рафа Оу и графа й2 ;

- номер строки и столбца ММК на пересечении которых находиться текущий микроконтроллер.

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

1 123456789

дуги графа достижимости; траектория перемещения сообщения. Рис. 3. Маршрут передачи сообщения

Из рисунка 3 видно, что сообщение из МК[5,6] достигло адресата, изменившего в результате реконфигурации свое местоположение (рнс. 2), с логическим адресом [4,5] в МК[3,5] по кратчайшему пути в обход отказавших элементов и линий связи между ними.

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

ЛА1, ЛА2, ЛАЗ, ЛА4 - группа входов/выходов логических адресов; Д1, Д2, ДЗ, Д4 - группа входов/выходов сигналов достижимости;

Rl, R2, R3, R4 - группа входов/выходов сигнала сброса;

JIA, ФА - логический и физический адреса текущего устройства маршрутизации;

Ттах - время распространения сигнала достижимости;

ER1, ER2, ER3, ER4 - сигналы отказа окружающих линий связи;

SO, SI, S2, S3, S4 - группа входов/выходов передаваемых сообщений;

ФО - сигнал фатального отказа.

Основными блоками устройства являются: блок 1 выбора максимального логического адреса, блок 2 сброса, блок 3 адресной селекции, блок 4 выбора минимальной величины, блок 5 формирования кода направления, таблица достижимости 6, блок 7 коррекции направления, блок 8 коммутации сигналов достижимости, блок 9 коммутации логического адреса, блок-сумматор 10, блок И источник опорных напряжений, буферный блок 12 сообщений, блок 13 коммутации сообщений.

suu-i)"

S20-1J). S3(I+1J> S4(1J+1> S0(ij).

АЦП 16

Q

CF

гг

- SI

- S2

- S3 -S4

- SO

- ФО

■ Rl

■ R2 -R3 • R4

-Д1

-да

.до ■ ДА

-ЛА1 -ЛА2 -ЛАЗ -ЛА4

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

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

Блок 2 служит для сравнения физического и логического адресов текущего

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

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

Совместная работа блоков 4 и 5 позволяет сформировать код направления ретрансляции сообщения, который записывается в таблицу достижимости (блок 6) по адресу, сформированному в блоке 1.

Блок 7 коррекции направления необходим для изменения направления ретрансляции сообщения на ортогональное в случае отказа линии связи в исходном направлении.

Блок 8 служит для передачи сигналов достижимости (вес й^ дуг графа достижимости) соседним устройствам маршрутизации и формирования сигнала отказа линии связи в соответствующем направлении.

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

Блок 10 (сумматор) необходим для увеличения значения принятого сигнала достижимости на минимальную ненулевую величину с1, задаваемою источником опорных напряжений (блок 11).

Блок 11 служит для формирования двух величин (с! - минимальная ненулевая величина, ~ максимальная возможное значение для заданной размерно-

сти ММК), задающих интервал изменения значения сигнала достижимости и логического адреса.

Блоки 12 и 13 предназначены для приема передаваемых сообщений от соседних элементов, выбора одного из них, и его ретрансляции в направлении, извлеченном из таблицы достижимости и скорректированном в блоке 7.

Новизна технического решения определяется следующим:

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

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

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

DI\,ecnu Wj > w2 DI2, если й W2 ' где DO - выход элемента; Wj, м>2 - первая группа входов; Dlit DI2 - вторая груши входов.

Принцип передачи сообщений между МК заключается в следующем: при получении устройством сообщения (входы 50(1,Л 57(/,/-1), Б20-1/), &?(г+1,/), сравнивается (в блоке 13 коммутации сообщений) адресная часть сообщения и логический адрес текущего устройства маршрутизации. Если они равны, то сообщение считается принятым и передается на выход 50, в противном случае сообщение передается в направлении, код которого извлекается из таблицы достижимости из ячейки с логическим адресом приемника сообщения (выходы .57, £2, 5У). В случае невозможности маршрутизации (отказ линий связи во всех направлениях) на выходе ФО устройства формируется единичное значение.

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

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

н

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

2 - маршрутизация с использованием расширенных уровней предосторожностей (от узла назначения к источнику);

3 - маршрутизация с использованием расширенных уровней предосторожностей {смешанный подход);

4 - двухфазная маршрутизация;

5 - маршрутизация при неизвестном начальном состоянии среды (маршру-

газация перекоммутацией);

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

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

Из представленных на рисунке 5 графиков следует, что лучший из известных алгоритмов при максимальном числе отказов обеспечивает вероятность маршрутизации равную 0,74, в то время как разработанный алгоритм дает вероятность маршрутизации 0,91. Вероятность маршрутизации при максимальном числе отказов микроконтроллеров увеличена не менее чем в 1,2 раза.

На рисунке 6 представлены графики зависимости относительных длин маршрутов от числа отказов. Относительная длина маршрута вычисляется по формуле:

¿п - '"!; -; где I, - длина ¿-ого маршрута.

Л

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

где с1п - средняя длина маршрута при п отказах; р„ - вероятность маршрутизации при п отказах. к

I'.

в

А

40

35

30

25

20

15

10

6

5

число отказов

123456789 Рис. 6. Зависимость относительной длины маршрутов от числа отказов

« >•

ю

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

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

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

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

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

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

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Савенков, H А Исследование самоорганизации мультимикроконгроллера с плавающим столбцом резервных элементов [Текст] / H.A. Савенков, В А. Колосков // Материалы 5-й Междунар. конф «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» («Распознавание - 2001»), Курск, 2001. Ч. 2. С. 213-214.

2. Савенков, H А. Алгоритм отказоустойчивой маршрутизации [Текст] / H.A. Савенков, В. А. Колосков // Материалы 3-й Междунар. науч.-техн. конф. «Измерение, контроль, информатизация - 2002». Барнаул, АГТУ, 2002. С. 24-25.

3. Савенков, H.A. Алгоритм маршрутизации в самоорганизующихся управляющих структурах [Текст] / H.A. Савенков, A.B. Малышев, В.А. Колосков // Сборник статей «Сварка и родственные технологии в машиностроении и электронике». Курск, КГТУ, 2003.

4. Савенков, H.A. Алгоритм адаптивной маршрутизации в мультиконгрол-лере с репродуцируемой программой поведения [Текст] / H.A. Савенков, М.В. Медведева, В.А. Колосков // Телекоммуникации. 2003. №6 С. 20-24.

5. Савенков, H.A. Адаптивная маршрутизация в реконфигурируемом муль-тиконтроллере [Текст] / H.A. Савенков, В.А. Колосков // Материалы VII-й Междунар. науч.-техн конф. «Медико-экологические информационные технологии -2004». Курск, КГТУ, 2004. С. 153-157.

6. Савенков, H.A. Маршрутизация по логическому адресу в реконфигурируемом мультиконтроллере [Текст] / НА. Савенков, В.А. Колосков, MB. Медведева // Сборник статей молодых ученых ТулГУ «Приборы и управление». Выпуск 2. Тула, 2004. С. 47-51.

7. Колосков, В.А. Разработка реконфигурируемых мультиконтроллеров с отказоустойчивым функционированием [Текст] / В.А. Колосков, М.В. Медведева, H.A. Савенков // Известия ТулГУ. Серия. Проблемы машиностроения. Вып.7. Часть 2. Тула, 2004. С. 296-302.

8. Савенков, Н.А Алгоритм обмена в реконфигурируемых многопроцессорных структурах [Текст] / Н А Савенков, В.А. Колосков // Материалы IX Междунар. науч. конф., посвящ 45-летию Сиб. гос аэрокосмич. ун-та имени акад. М.Ф. Решетнева «Решетневские чтения». Красноярск, Сиб гос аэрокосмич. ун-т., 2005. С. 268-269

9. Савенков, H.A. Организация маршрутизации в реконфигурируемом муль-

тикотроллере [Текст] / H.A. Савенков, В. А. Колосков // Известия Курского государственного технического университета. Курск, 2005. №1(14). С. 93-98.

10. Савенков, Н А. Алгоритм передачи сообщений в реконфигурируемом мультиконтроллере [Текст] / H.A. Савенков, П.Ю. Калинин // Тезисы докладов XXXI Междунар. молодежной конф. «Гагаринские чтения». М., МАТИ, 2005. Т.4. С. 72-73.

11. Савенков, H.A. Алгоритм адаптивной маршрутизации в многопроцессорных управляющих сетях [Текст] / H.A. Савенков, В А. Колосков // Труды V Междунар. конф. «Идентификация систем и задачи управления» SICPRO'06. М,, Институт проблем управления им. В.А. Трапезникова РАН, 2006. С. 1312-1329. ISBN 5-201-14984-7.

12. Савенков, Н А Клеточная модель адаптивной маршрутизации в среде с мигрирующими программными модулями [Текст] / H.A. Савенков, В.А. Колосков // Известия ТулГУ. Серия "Вычислительная техника, информационно-технологические системы управления". Выл 3. Тула, 2005г. С. 93-101.

13. Положительное решение о выдаче патента на изобретение (Россия), МПК 7 G 06 F. Ячейка маршрутизации однородной среды процессорных элементов. / Савенков H.A., Колосков В.А., Колоскова Г.П (Россия). Заявка № 2004132649, приоритет от 9 ноября 2004г.

Соискатель , ' НА Савенков

Подписано в печать 21 марта 2006г. Формат 60x84 1/16

Печ. л. 1^0. Тираж 100 экз. Заказ _.

Курский государственный технический университет. Издательско-полиграфический центр Курского государственного технического университета. 305040, г. Курск, ул. 50 лет Октября, 94.

!

\

г i

I

ДООбА

692 1

ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМ МАРШРУТИЗАЦИИ В

МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ

1.1. Существующие многопроцессорные архитектуры

1.2. Задачи маршрутизации

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

1.4. Обзор и классификация существующих алгоритмов маршрутизации

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

ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМА МАРШРУТИЗАЦИИ В ОТКАЗОУСТОЙЧИВОМ РЕКОНФИГУРИРУЕМОМ

МУЛЬТИКОНТРОЛЛЕРЕ

2.1. Механизм взаимодействия среды самоорганизации и маршрутизации

2.2. Алгоритм самоорганизации мультиконтроллера

2.3. Алгоритм адаптивной маршрутизации

2.3.1. Содержательное описание алгоритма маршрутизации

2.3.2. Формирование таблиц достижимости

2.3.3. Графовая модель процесса маршрутизации

2.3.4. Клеточный алгоритм адаптивной маршрутизации

2.4. Пример применения алгоритма адаптивной маршрутизации

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

ГЛАВА 3. УСТРОЙСТВО МАРШРУТИЗАЦИИ ОДНОРОДНОЙ

СРЕДЫ ПРОЦЕССОРНЫХ ЭЛЕМЕНТОВ

3.1. Структурная организация процесса маршрутизации

3.2. Функциональная схема маршрутизатора

3.3. Организация однородной среды обмена сообщениями

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

ГЛАВА 4. МОДЕЛИРОВАНИЕ И ИССЛЕДОВАНИЕ СРЕДЫ РЕКОНФИГУРАЦИИ И МАРШРУТИЗАЦИИ

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

4.2. Исследование характеристик ячейки реконфигурации

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

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

4.5. Исследование характеристик маршрутизации

4.6. Выводы к главе 128 ЗАКЛЮЧЕНИЕ 129 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

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

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

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

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

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

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

Диссертационная работа выполнена по гранту Федерального агентства по образованию А.04-3.16-701 "Разработка алгоритмов и сред обмена данными в мигрирующей логической структуре отказоустойчивого мультиконтроллера", договор подряда № 1.255.04/1.

Объектом исследования является отказоустойчивый мультиконтроллер со средствами восстановления логической структуры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы обсуждались на: Международной научно-технической конференции "Распознавание 2001" (г. Курск, 2001г.); 3-й Международной научно-технической конференции "Измерение, контроль, информатизация" (г. Барнаул, 2002г.); VII-й Международной научно-технической конференции "Медико-экологические информационные технологии - 2004" (г. Курск, 2004г.); XXXI-й Международной научной молодежной конференции "Гагаринские чтения" (г. Москва, 2005г.), IX-й Международной научно-технической конференции "Решетневские чтения" (г. Красноярск, 2005г.); V Международной конференции "Идентификация систем и задачи управления" (г. Москва, 2006г.)".

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

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

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

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

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы включающего, 83 источника. Работа изложена на 139 страницах и содержит 67 рисунков и 4 таблицы.

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

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

2. Исследована способность алгоритма самоорганизации противостоять различному числу отказавших МК. Проведены исследования характеристик самоорганизации (вероятность восстановления, время самоорганизации, число перестроенных МК).

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

4. Исследованы основные характеристики маршрутизации (вероятность маршрутизации, относительная длина маршрута).

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

1. В. Корнеев Будущее высокопроизводительных вычислительных систем // Открытые системы. 2003. №5.

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

3. Организация и синтез микропрограммных мультимикроконтроллеров / И.В. Зотов, В.А. Колосков, B.C. Титов, К.А. Сапронов, А.П. Волков, Курск: Изд-во «Курск», 1999. 368 с.

4. Колосков В.А. Основы теории и принципы построения отказоустойчивых самоорганизующихся логических мультимикроконтроллеров / Дисс. на соискание учёной степени д-ра техн. наук. Курск, КГТУ, 1998. 367 с.

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

6. Д. Кефарт, Д. Чесс Концепция саморегулирующихся вычислений // Открытые системы. 2003. №5.

7. Адаптивные системы от Fujitsu Siemens // Открытые системы. 2003. №10.

8. В. Воеводин, М. Филамофитский Суперкомпьютер на выходные // Открытые системы. 2003. №5.

9. Савенков Н.А., Колосков В.А. Исследование самоорганизации мультимикроконтроллера с плавающим столбцом резервных элементов // Сборник материалов 5-й международной конференции "Распознавание 2001". - КГТУ, Курск, 2001

10. В.А. Колосков, М.В. Медведева Модели активной среды самоорганизации отказоустойчивого мультиконтроллера // Программирование. 2001. №6. с. 67-76.

11. А. Савельев Современные протоколы маршрутизации // LAN/Журнал сетевых решений. 1998. №12.

12. А. Богданов, В. Мареев, Е. Станкова, В. Корхов Архитектуры и топологии многопроцессорных вычислительных систем // Электронный учебник http://www.informatika.ru

13. Э. Таненбаум, Архитектура компьютера. СПб, Из-во "Питер", 2002 г.

14. К. Хамахер, 3. Вранешич, С. Заки, Организация ЭВМ. СПб, Из-во "Питер", 2003г.

15. JT. Черняк Ревизия первооснов конец застой? // Открытые системы. 2003. №5.

16. И.В. Зотов, В.А. Колосков, B.C. Титов, К.А. Сапронов, А.П. Волков организация и синтез микропрограммных мультимикроконтроллеров. Курск: Изд-во Курск, 1999. 368 с.

17. М. Кульгин На перекрестках сетей // LAN/Журнал сетевых решений. 1996. №8.

18. И. Труб Алгоритмическое обеспечение распределенных WEB-серверов // открытые системы. 2003. №5.

19. Хелеби С., Мак-Ферсон Д. Принципы маршрутизации в Internet: Пер. с англ. 2-е изд. М.: Издательский дом "Вильяме", 2003. 448с.

20. S. Cheung, М. LAU Routing with Locality on Meshes with Buses // Journal of parallel and distributed computing. 1996. P.84-90.

21. В. Митрофанов, А. Слуцкин, К. Ларионов, JI. Эйсымонт Направления развития отечественных высокопроизводительных систем // Открытые системы. 2003. №5.

22. Колосков В.А., Медведева М.В., Малышев А.В. Клеточная самоорганизация и отказоустойчивость // Сборник материалов Международной н.-т. конф. «Интеллектуальные САПР». Таганрог, 2002. С. 525-531.

23. Колосков В.А., Малышев А.В. Нейронная сеть самоорганизации мультимикроконтроллера // Тез. докл. второй Всероссийской н.-т. конф. «Информационные технологии в науке, проектировании и производстве». Н.Новгород, 2000. С. 1.

24. Малышев А.В., Миневич JI.M., Колосков В.А. Метод маршрутизации сообщений в отказоустойчивом мультимикроконтроллере // Сборник материалов н.-т. конф. «Медико-экологические информационные технологии». Курск, 2001. С. 216-217.

25. Малышев А.В., Миневич Л.М., Колосков В.А. Маршрутизация сообщений в отказоустойчивом мультимикроконтроллере // Сборник материалов н.-т. конф. «Распознавание». Курск, 2001.

26. Савенков Н.А., Колосков В.А. Клеточная модель адаптивной маршрутизации в среде с мигрирующими программными модулями // Известия ТулГУ. Серия "Вычислительная техника, информационно-технологические системы управления". Вып. 3. Тула, 2005г. С. 93-101.

27. Савенков Н.А., Медведева М.В., Колосков В.А. Алгоритм адаптивной маршрутизации в мультиконтроллере с репродуцируемой программой поведения // Телекоммуникации. 2003. №6. С. 20-24.

28. Савенков Н.А., Колосков В.А. Алгоритм отказоустойчивой маршрутизации // Материалы 3-й международной научно-технической конференции "Измерение, контроль, информатизация 2002", -Барнаул, АГТУ, 2002, 144с.

29. Апраксин Ю.К., Запевалин А.А., Кирюхин В.В. Алгоритмы маршрутизации для сетей с коммутацией сообщений // А и ВТ.- 1982. -№2.-С. 87-92.

30. Herbordt М.С., Corbett J.C., Weems С.С. Practical algorithms for online routing on fixed and reconfigurable meshes // J. Paral. Distrib. Comput. -1994.-vol.20, No.3. -PP.341-356.

31. Kunde M. Packet routing on grids of processors / Lecture Notes in Computer Science. New York: Spinger-Verlag. - 1988. - Vol.401. -PP.129-136.

32. Лукьянов A.B., Первозванский A.A. Адаптивное управление маршрутизацией в коммуникационных сетях с коммутацией пакетов // А и ВТ. 1983. - №1. -С.60-65.

33. Шеметов В.В. Гибридный алгоритм маршрутизации для информационно-вычислительных сетей // А и ВТ. 1984. - №1. - С50-53.

34. Kaufmann М., Sibeyn J.F. Randomized multi-packet routing and sorting on meshes //Algorithmica. 1997. - Vol. 17. - P. 224-244.

35. Jia W., Zhao W., Xuan D., XuAn G. Efficient Fault-Tolerant Multicast Routing Protocol with Core-Based Tree Techniques // IEEE Transactions on Parallel and Distributed Systems. 1999. - Vol. 10. - № 10. - P. 9841000.

36. Choi Y., Pinkston T.M. Evaluation of Crossbar Architectures for Deadlock Recovery Routers // Journal of Parallel and Distributed Computing. 2001. -Vol. 61.-№ 1,-P. 49-78.

37. Chiu G.-M. The Odd-Even Turn Model for Adaptive Routing // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11. - № 7.-P. 729-738.

38. Seo S.-W., Feng T.-Y., Lee H.-I. Permutation Realizability and Fault Tolerance Property of the Inside-Out Routing Algorithm // IEEE Transactions on Parallel and Distributed Systems. 1999. - Vol. 10. - № 9.-P. 946-957.

39. Sum J., Shen H., Young G.H., Wu J., Leung C.-S., Analysis on extended ant routing algorithms for network routing and management // The Journal of Supercomputing. 2003. - Vol. 24. - № 3. - P. 327-340.

40. Вишневский В.М., Пороцкий С.М. Динамическая маршрутизация в ATM сетях проблемы и решения //Автоматика и телемеханика. 2003. №6.

41. Dao B.V., Duato J., Sudhakar Y. Dynamically Configurable Message Flow Control for Fault-Tolerant Routing // IEEE Transactions on Parallel and Distributed Systems. 1999. - Vol. 10. - № 1. - P. 7-22.

42. Shin K.-G., Chou C.-C., Kweon S.-K. Distributed Route Selection for Establishing Real-Time Channels // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11. - № 3. - P. 318-335.

43. Chen C.-L., Chiu G.-M. A Fault-Tolerant Scheme for Meshes with Nonconvex Faults // IEEE Transactions on Parallel and Distributed Systems. 2001. - Vol. 12. - № 5. - P. 467-475.

44. Bock S., Meyer F., Scheideler C. Optimal Wormhole Routing in the (n,d)-Torus // Proceedings of the 11th International Parallel Processing Symposium. 1997. - P. 326-332.

45. Suh Y.-J., Shin K.G. All-to-All Personalized Communication in Multidimensional Torus and Mesh Networks // IEEE Transactions on Parallel and Distributed Systems. 2001. - Vol. 12. - № 1. - P. 38-59.

46. Valiant L.G., Brebner G.J. Universal schemes for parallel computation / Proc. 13th ACM Symp. Theory of Comput. 1981. - PP.88-92.

47. Leighton F.T., Makedon F., Tollis I. A2n-2 step algorithm for routing in nxn array with constant size queues / Proc. 1th ACM Symp. Parallel Alg. and Archit. 1989. - PP.328-335.

48. H. Олифер Маршрутизация в составных сетях // LAN/ Журнал сетевых решений. 2001. №5.

49. Савенков Н.А., Колосков В.А. Адаптивная маршрутизация в реконфигурируемом мультиконтроллере // Медико-экологические информационные технологии 2004: Сборник материалов VII

50. Международной научно-технической конференции / Курск, гос. техн. ун-т. Курск, 2004. 207с.

51. 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. ll.-№2.-P. 149-159.

52. Khan G.N., Wei G. Fault-tolerant Wormhole Routing using a Variation of Distributed Recovery Block Approach // IEE Proceeding Computers and Digital Techniques. 2000. - Vol. 147. - № 6. - P. 397-402.

53. Малышев A.B., Медведева M.B., Колосков В.А. Поиск абонента в мультиконтроллере с репродуцированной программой поведения // Телекоммуникации. 2002, №5.

54. Патент Российской Федерации №2185656. Распределённая система для программного управления // А.В. Малышев, М.В. Медведева, JI.M. Миневич, В.А. Колосков. Изобретения, 2002.

55. Малышев А.В. Адаптационный алгоритм самоорганизации обменных взаимодействий в мультимикроконтроллерной сети // Тез. докл. Международной научной конференции «XXVIII Гагаринские чтения». Москва, 2002.

56. Малышев А.В. Клеточные алгоритмы и среды отказоустойчивой маршрутизации самоорганизующегося мультиконтроллера / Дисс. на соискание ученой степени кандидата технических наук. Курск. КГТУ, 2003, 148с.

57. Протокол состояния связей OSPF. http//www.psati.ru

58. А.В. Тимофеев, А.В. Сырцев Модели и методы маршрутизации потоков данных в телекоммуникационных системах с изменяющейся динамикой // Приложение к журналу "Информационные технологии". № 8. 2005г.

59. Басанер Р., Саати Т. Конечные графы и сети. М.: Наука, 1973. 368с.

60. Вишневский В.М., Левнер Е.В., Федотов Е.В. Математические модели исследования алгоритмов маршрутизации в сетях передачи данных // Информационные процессы. 2001. Т.1. № 2. С. 103-126.

61. Timofeev А. V. Intelligent control applied to non-linear system and neural networks with adaptive architecture // International Journal on Intelligent Control, Neurocomputing and Fuzzy Logic. 1996. P. 1-18.

62. Технология параллельных вычислений в распределённых средах реструктуризации мультикомпьютеров / В.А. Колосков, М.В. Медведева, Ф.А. Старков, Курск, гуманит-техн. ин-т. Курск, 2002.

63. Choo Н., Yoo S.-M., Youn H.-Y. Processor Scheduling and Allocation for 3D Torus Multicomputer Systems // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11. - № 5. - P. 475-484.

64. Moh S., Yu C., Lee В., Youn H.Y., Han D., Lee D. Four-Ary Tree-Based Barrier Synchronization for 2D Meshes without Nonmember Involvement // IEEE Transactions on Computers. 2001. - Vol. 50. - № 8. - P. 811823.

65. W.J. Dally, C.L. Seitz The torus routing chip // Journal of distributed computing. Vol. 1. No. 3, pp. 187-196, 1986.

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

67. Савенков Н.А., Малышев А.В., Колосков В.А. Алгоритм маршрутизации в самоорганизующихся управляющих структурах //

68. Сварка и родственные технологии в машиностроении и электронике, Курск: КГТУ, 2003г.

69. Г.Г. Стецюра Возможность технической реализации клеточных автоматов с дальними связями и групповыми операциями // Автоматика и телемеханика. № 8, 2004. С. 174-184.

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

71. Савенков Н.А., Колосков В.А., Медведева М.В. Маршрутизация по логическому адресу в реконфигурируемом мультиконтроллере // Приборы и управление / Сборник статей молодых ученых ТулГУ. Выпуск 2. Издательство ТулГУ, г. Тула, 2004г.

72. Савенков Н.А., Колосков В.А., Медведева М.В. Разработка реконфигурируемых мультиконтроллеров с отказоустойчивым функционированием // Известия ТулГУ. Серия. Проблемы машиностроения. Вып.7. Часть 2. Тула: Изд-во ТулГУ, 2004. - 419с.

73. Савенков Н.А. Алгоритм передачи сообщений в реконфигурируемом мультиконтроллере // XXXI Гагаринские чтения. Тезисы докладов Международной молодежной конференции. Москва, 5-9 апреля 2005г. М.: МАТИ, 2005. Т.4, 134 с.

74. Савенков Н.А. Алгоритм обмена в реконфигурируемых многопроцессорных структурах // Решетневские чтения: материалы IX Междунар. науч. конф., посвящ. 45-летию Сиб. гос. аэрокосмич. ун-т. Красноярск, 2005. - 392 с.

75. Однородные структуры / Варшавский В.И., Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я., М., 1973г.

76. JT. Наумов, А. Шалыто Клеточные автоматы реализация и эксперименты // Мир ПК, 2003. №8.

77. Sarkar P., A brief history of cellular automata // ACM Comput. Surveys. 2000. V. 32. № 1. P. 81-107.

78. Патент Российской Федерации №2175144 Устройство для формирования маршрута сообщения // П.В. Сусин., И.В. Зотов, B.C. Титов. 2001.

79. Титов B.C., Колосков В.А., Зотов И.В. Организация средств ретрансляции сообщений в алгоритмически распределенных системах // Изв. КГТУ. 1998. - №2. - С. 69-77.

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

81. Волгин Л.И., Зарукин А.И. Развитие элементного базиса реляторной схемотехники // Датчики и системы. 2002, №3.

82. Савенков Н.А., Колосков В.А. Организация маршрутизации в реконфигурируемом мультиконтроллере // Известия КурГТУ. 2005. №1(14) Курск. Изд-во КурГТУ, 2005г.

83. Положительное решение о выдаче патента на изобретение (Россия), МПК 7 G 06 F. Ячейка маршрутизации однородной среды процессорных элементов. / Савенков Н.А., Колосков В. А., Колоскова Г.П. (Россия). Заявка № 2004132649, приоритет от 9 ноября 2004г.

84. Suh Y.-J., Dao B.V., Duato J. Software-Based Rerouting for Fault-Tolerant Pipelined Communication // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. ll.-№3.-P. 193-211.