Содержание к диссертации
Введение
ГЛАВА 1. Анализ проблем маршрутизации в многопроцессорных вычислительных средах 11
1.1. Существующие многопроцессорные архитектуры 11
1.2. Задачи маршрутизации 20
1.3. Маршрутизация в отказоустойчивых самоорганизующихся системах 23
1.4. Обзор и классификация существующих алгоритмов маршрутизации 26
1.5. Выводы к главе 35
ГЛАВА 2. Разработка алгоритма маршрутизации в отказоустойчивом реконфигурируемом мультиконтроллере 37
2.1. Механизм взаимодействия среды самоорганизации и маршрутизации 37
2.2. Алгоритм самоорганизации мультиконтроллера 41
2.3. Алгоритм адаптивной маршрутизации 49
2.3.1. Содержательное описание алгоритма маршрутизации 49
2.3.2. Формирование таблиц достижимости 53
2.3.3. Графовая модель процесса маршрутизации 58
2.3.4. Клеточный алгоритм адаптивной маршрутизации 68
2.4. Пример применения алгоритма адаптивной маршрутизации 74
2.5. Выводы к главе 83
ГЛАВА 3. Устройство маршрутизации однородной среды процессорных элементов 84
3.1. Структурная организация процесса маршрутизации 84
3.2. Функциональная схема маршрутизатора 88
3.3. Организация однородной среды обмена сообщениями 104
3.4. Выводы к главе 106
ГЛАВА 4. Моделирование и исследование среды реконфигурации и маршрутизации 108
4.1. Моделирование среды реконфигурации мультиконтроллера 108
4.2. Исследование характеристик ячейки реконфигурации 110
4.3. Программная модель устройства маршрутизации 114
4.4. Исследование алгоритма маршрутизации при различных конфигурациях отказов МК 116
4.5. Исследование характеристик маршрутизации 124
4.6. Выводы к главе 128
Заключение 129
Список использованных источников 131
- Обзор и классификация существующих алгоритмов маршрутизации
- Пример применения алгоритма адаптивной маршрутизации
- Структурная организация процесса маршрутизации
- Исследование алгоритма маршрутизации при различных конфигурациях отказов МК
Введение к работе
Актуальность работы. Одним из перспективных направлений создания управляющих автоматов является разработка управляющих мультиконтроллеров, представляющих дискретную сеть, узлам которой соответствуют микроконтроллеры, а ребрам - связи между ними. При этом общий алгоритм управления разбивается на частные, размещаемые в виде программных модулей в микроконтроллерах. Использование мультиконтроллеров в авиакосмической технике для управления исполнительными устройствами узлов и контроля навигационных характеристик маршрута, а также применение в условиях, где скорая замена отказавших элементов невозможна, например, для управления сложными технологическими операциями в условиях агрессивной внешней среды, требует разработки мультиконтроллеров, ориентированных на непрерывное (безостановочное) функционирование в условиях отказов отдельных элементов.
Следует отметить, что существующие мультиконтроллерные устройства управления, спроектированные без учета возможных последствий отказов и даже построенные на основе высоконадежных элементов, не в полной мере удовлетворяют требованиям отказоустойчивости. Мультиконтроллер должен обеспечивать восстановление логической структуры на аппаратном (микроархитектурном) уровне организации, не затрагивая ни прикладное, ни системное программное обеспечение вычислительной системы. В случае увеличения числа и сложности технологических операций наращивание числа микроконтроллеров должно приводить только к изменению размещаемой в управляющей системе программы управления, не вызывая ее перепрограммирования для восстановления способности непрерывно функционировать в условиях отказов.
Обеспечение отказоустойчивости и непрерывного функционирования мультиконтроллера требует решения двух задач: восстановления логической структуры (реконфигурации) мультиконтроллера при отказах отдельных микроконтроллеров и взаимодействия работоспособных элементов в логической структуре мультиконтроллера. Известные алгоритмы и среды реконфигурации позволяют с высокой вероятностью восстановить логическую структуру мультиконтроллера на множестве работоспособных микроконтроллеров, тогда как вторая задача в настоящее время решена не в полной мере.
Алгоритмически распределённая организация мультиконтроллера обусловливает необходимость разработки средств межмикроконтроллерного взаимодействия как важнейшей компоненты в структуре функциональных подсистем мультиконтроллерного устройства управления. Указанные средства должны удовлетворять широкому кругу достаточно жёстких требований. С одной стороны, они должны обеспечивать согласованное функционирование отдельных микроконтроллеров в составе мультиконтроллера (функциональную целостность) в условиях отказов отдельных элементов, с другой стороны, обладать быстродействием систем с жесткой логикой и гибкостью программируемых управляющих устройств, обеспечивая оперативность управления независимо от свойств реализуемых алгоритмов.
Последние разработки в области адаптивной маршрутизации (А.В. Тимофеев, J. Duato, J. Wu, G. Wei) применительно к реконфигурируемому мультиконтроллеру требуют сбора информации о новых логических адресах микроконтроллеров и приведения в соответствие таблиц физических и логических адресов. Для этого необходимы дополнительные алгоритмические и аппаратные затраты, снижающие эффективность средств маршрутизации. К тому же, для выполнения указанных действий необходимо остановить функционирование мультиконтроллера. Снять противоречие между требованиями отказоустойчивой маршрутизации и невысоких временных и аппаратных затрат при обеспечении широкой области применения позволит разработка алгоритма и устройства адаптивной маршрутизации, не зависящих от применяемого алгоритма восстановления логической структуры, а также обеспечивающих доставку сообщения адресату, физическое местоположение которого может изменяться и, в общем случае, неизвестно.
В связи с вышесказанным актуальным является решение научно-технической задачи построения средств адаптивной маршрутизации, обеспечивающих поиск перемещаемого адресата в реконфигурируемом мультиконтроллере по его логическому адресу.
Диссертационная работа выполнена по гранту Федерального агентства по образованию А.04-3.16-701 "Разработка алгоритмов и сред обмена данными в мигрирующей логической структуре отказоустойчивого мультиконтроллера", договор подряда № 1.255.04/1.
Объектом исследования является отказоустойчивый мультиконтроллер со средствами восстановления логической структуры.
Предмет исследования - средства адаптивной маршрутизации мультиконтроллера, позволяющие осуществить поиск адресата, изменяющего свое местоположение.
Цель диссертационной работы состоит в обеспечении обмена сообщениями между адресатами в реконфигурируемой логической структуре мультиконтроллера путем создания алгоритма и устройства маршрутизации по логическому адресу приемника сообщения.
Для достижения поставленной цели в диссертационной работе решались следующие задачи:
Сравнительный анализ существующих алгоритмов, выработка подхода к адаптивной маршрутизации сообщений по логическому адресу приемника.
Разработка алгоритма адаптивной маршрутизации сообщений между адресатами, изменяющими свое месторасположение в мультиконтроллере с отказавшими элементами и связями между ними.
Разработка клеточного аппаратно-ориентированного алгоритма, реализующего построение множества потенциально допустимых маршрутов передачи сообщения и выбор маршрута его движения.
Построение функциональной схемы устройства адаптивной маршрутизации, обеспечивающего обмен сообщениями между микроконтроллерами без прерывания функционирования мультиконтроллера.
Исследование характеристик алгоритма адаптивной маршрутизации с помощью программных средств моделирования функционирования реконфигурируемого мультиконтроллера.
Методы исследования основаны на использовании математического аппарата и методов теории графов, теории надежности технических систем, теории топологического проектирования однородных структур, теории проектирования автоматов и дискретных систем.
Научная новизна результатов, полученных в диссертационном исследовании, определяется следующим:
Впервые разработаны правила построения множества потенциально допустимых маршрутов, обеспечивающие поиск адресата в восстановленной логической структуре реконфигурируемого мультиконтроллера за счет параллельного распространения информации об изменении логических адресов микроконтроллеров.
Разработан клеточный, аппаратно-ориентированный алгоритм адаптивной маршрутизации матричного отказоустойчивого мультиконтроллера, позволяющий сократить траекторию передачи сообщения путем непосредственного поиска приемника по логическому адресу в формате сообщения и не зависящий от способа восстановления логической структуры.
На основе элементного базиса реляторной схемотехники построена функциональная схема устройства адаптивной маршрутизации, позволяющего осуществить поиск адресата по логическому адресу независимо от его местоположения и не требующего прерывания функционирования мультиконтроллера. Особенностью устройства является наличие средств (совокупность блоков выбора максимального логического адреса, адресной селекции сигналов достижимости и выбора минимальной величины) выбора кратчайшего маршрута транзитной передачи сообщений.
Практическая ценность работы состоит в получении практически пригодного решения по функциональной организации средств адаптивной маршрутизации отказоустойчивого мультиконтроллера. Предложенный алгоритм адаптивной маршрутизации может найти широкое применение при построении управляющих мультиконтроллеров различного назначения, ориентированных на непрерывное функционирование, к которым предъявляются высокие требования по отказоустойчивости.
Результаты работы использованы в производственном процессе отдела информационных технологий ООО "Курский завод "Аккумулятор" (г. Курск) и в учебном процессе Курского государственного технического университета.
Апробация работы. Основные результаты диссертационной работы обсуждались на: Международной научно-технической конференции "Распознавание 2001" (г. Курск, 2001г.); 3-й Международной научно-технической конференции "Измерение, контроль, информатизация" (г. Барнаул, 2002г.); VII-й Международной научно-технической конференции "Медико-экологические информационные технологии - 2004" (г. Курск, 2004г.); ХХХІ-й Международной научной молодежной конференции "Гагаринские чтения" (г. Москва, 2005г.), ІХ-й Международной научно-технической конференции "Решетневские чтения" (г. Красноярск, 2005г.); V Международной конференции "Идентификация систем и задачи управления" (г. Москва, 2006г.)".
Публикации. Результаты диссертационного исследования опубликованы в 7 статьях, 5 тезисах докладов и защищены положительным решением о выдаче патента на изобретение.
Научные положения, выносимые на защиту.
Локальные правила обхода отказавших элементов и связей мультиконтроллера, построения множества допустимых маршрутов передачи сообщений и выбора одного из них, позволившие осуществить маршрутизацию сообщения независимо от применяемого в мультиконтроллере алгоритма реконфигурации за счет параллельного распространения информации об изменении логических адресов микроконтроллеров.
Клеточный, аппаратно-ориентированный алгоритм адаптивной маршрутизации в логической структуре реконфигурируемого мультиконтроллера, позволяющий сократить траекторию передачи сообщения путем непосредственного поиска приемника по логическому адресу в формате сообщения.
Функциональная организация устройства адаптивной маршрутизации в логической структуре реконфигурируемого мультиконтроллера, обеспечивающего поиск адресата по логическому адресу независимо от его местоположения, позволившего за счет разделения процессов ретрансляции сообщения и настройки таблиц достижимости осуществить обмен сообщениями без прерывания функционирования мультиконтроллера.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы включающего, 83 источника. Работа изложена на 139 страницах и содержит 67 рисунков и 4 таблицы.
В введении к диссертации обосновывается актуальность работы, ее научная новизна, формулируются цели и задачи диссертационного исследования, приводится краткое содержание глав диссертации и положения выносимые на защиту.
В первой главе проводится анализ существующих алгоритмов адаптивной маршрутизации, который показал их неработоспособность в условиях неизвестного положения адресата сообщения и применения произвольного алгоритма самоорганизации мультиконтроллера.
Во второй главе разрабатывается алгоритм адаптивной маршрутизации независящий от применяемого в ММК метода реконфигурирования логической структуры, формулируются правила построения множества допустимых маршрутов передачи сообщения, выбора одного из них и правила обхода отказавших узлов.
В третьей главе проводится разработка функциональной схемы устройства, реализующего предлагаемый алгоритм адаптивной маршрутизации, способного передавать сообщения в мультиконтроллере с отказами узлов и связей между ними.
В четвертой главе проводится исследование алгоритма маршрутизации на различных конфигурациях отказавших узлов, связей между ними и при различной размерности мультиконтроллера, приводится сравнение с существующими решениями.
В заключении приведены основные результаты, полученные в диссертационном исследовании.
Возможное применение. Результаты диссертационной работы могут найти применение при построении мультиконтроллера, отвечающего повышенным требованиям по отказоустойчивости.
Обзор и классификация существующих алгоритмов маршрутизации
В настоящее временя разработано большое число способов и алгоритмов маршрутизации сообщений, применение которых возможно в вычислительных системах различного функционального назначения и структурной организации и отличающихся по широкому спектру признаков. Одним из признаков, лежащих в основе классификации алгоритмов маршрутизации, является способ выбора маршрута (траектории) передачи сообщений. В настоящее время алгоритмы маршрутизации делят на два основных класса: алгоритмы фиксированной маршрутизации [29-31] и адаптивные алгоритмы [29, 32-40].
Особенностью алгоритмов фиксированной маршрутизации является наличие информации о маршрутах передачи сообщений между каждой парой модулей и неизменность этой информации в течении всего срока функционирования вычислительной системы. При использовании алгоритмов фиксированной маршрутизации траектория передачи сообщения выбирается при размещении реализуемых программ (алгоритмов) в модулях системы. Данный подход позволяет оптимизировать характеристики системы до ее фактического введения в действие, вместе с тем требует наличия полной информации, отражающей функциональные и топологические свойства выполняемых задач [3].
Алгоритмы адаптивной маршрутизации осуществляют выбор маршрута непосредственно в процессе передачи сообщений, никакой априорной информации о направлениях передачи сообщений данные алгоритмы не используют, вид маршрутов определяется динамически в процессе движения сообщений. Такими условиями могут являться: исправность каналов связи и их загрузка; число сообщений, пребывающих в очередях и ожидающих выдачи в тех или иных модулях. Локальные алгоритмы адаптивной маршрутизации выбирают направление выдачи сообщения с учетом информации о состоянии только топологически смежных (соседних) по отношению к текущему модулю узлов [41, 42]. Глобальные алгоритмы оперируют информацией о состоянии всех узлов и каналов распределенной системы, которая представляется в виде некоторых усредненных параметров системы [43].
Наиболее просто маршрутизация сообщений реализуется в системах, коммуникационные структуры которых имеют высокую степень регулярности [3, 34, 43-45]. Такой вычислительной системой является ММК с матричной структурой. Маршрутизация сообщений в таких ММК полностью базируется на специфике их топологического строения.
Каждый модуль матричной структуры имеет составной номер вида i.j, где / и j имеют смысл соответственно номера строки и номера столбца структуры, на пересечении которых находится данный модуль. Маршрутизация сообщений в матричном ММК предполагает реализацию двух фаз передачи. Первоначально сообщение передается вдоль строки, при достижении столбца, в котором находится модуль-приемник, направление продвижения сообщения меняется на перпендикулярное предшествующему и далее сообщение передается вдоль столбца ММК пока не достигнет модуля-приемника.
К настоящему времени разработано широкое разнообразие модификаций приведенного алгоритма, направленных на улучшение его характеристик [46, 47]. В тоже время описанный алгоритм имеет ряд недостатков. Наиболее существенных из них является единственность маршрутов взаимодействия для каждой пары модулей и невозможность их модификации даже при внешнем вмешательстве. Например, отказ модуля i.j (или даже коммуникационных средств модуля) обусловливает нарушение связей данного модуля с остальными.
Алгоритмы маршрутизации, использующие механизм таблиц достижимости (таблиц маршрутизации, таблиц трансляции и т.д.), в отличие от рассмотренных выше позволяют выбрать произвольную траекторию маршрута передачи сообщений [29, 48]. Указанная траектория может быть различной для разных сеансов взаимодействия одной и той же пары модулей. Это обеспечивает меньшую зависимость возможности передачи сообщений между одними модулями от состояния других модулей. Более того, имеется возможность модификации маршрутов путем перепрограммирования соответствующих таблиц трансляций.
Для обеспечения передачи сообщений при наличии отказавших МК, используется несколько способов: обход только отказавшего элемента и обход отказавшего элемента вместе с соответствующими ему линками (рис. 1.10) [49]. В статье Jie Wu "Отказоустойчивая, адаптивная, минимальная маршрутизация в сеточных соединениях мультикомпьютеров, использующая расширенный уровень безопасности" рассматривается проблема минимальной отказоустойчивой маршрутизации в сеточных соединениях мультикомпьютеров с отказавшими блоками [50]. Предлагаются достаточные условия для минимальной маршрутизации в двухмерных сетках с отказами. Согласно методу, описанному в данной статье, предполагается, что узлы владеют ограниченной информацией об отказах, т.е. имеют информацию о расположении отказов только в некоторой окружающей области. Интересной особенностью данного подхода является то, что автор объединяет все отказавшие узлы в выпуклые области, так называемая "Блочная модель отказов". Ко всем узлам применяется правило: если у данного узла есть два или более отказавших узла, то и данный узел помечается как отказавший. Данное условие позволяет достаточно просто провести маршрутизацию сообщения, двигаясь всего в двух направлениях, например, вправо и вверх. Однако в некоторых случаях распределения отказов после применения описанного правила выпуклыми блоками покрывается большая часть всей сети. В случае, если отказы возникли в узлах расположенных по диагонали, то все узлы сетки помечаются как отказавшие. Очевидно, что доставка сообщений к работоспособным узлам, расположенным внутри локализованной области отказов, невозможна. Так же данный алгоритм отказоустойчивой маршрутизации не обеспечивает доставку сообщения в сети после ее реконфигурации. Интересный подход применен в алгоритме маршрутизации, описанном Gul N. Fhan и Gu Wei в статье "Отказоустойчивая маршрутизация типа "wormhole", использующая подход распределенного блока восстановления" [51]. Рассматривается отказоустойчивая маршрутизация типа "wormhole", использующая разновидность распределенного блока (DRB группа). Область системы параллельного соединения узлов динамически разделена на накладывающиеся друг на друга DRB группы. Каждая DRB группа состоит из трех узлов: текущего, первичного и дополнительного. Формирование DRB групп показано на рисунке 1.11.
Пример применения алгоритма адаптивной маршрутизации
Структурно-функциональная организация отказоустойчивого мультиконтроллера отвечает требованиям, предъявляемым к клеточным автоматам (КА) [69, 74]. Каждый модуль распределенной системы является клеточным автоматом, функционирующим по определенному алгоритму в сообществе с соседними автоматами (модулями). Новое состояние любого клеточного автомата определяется его текущим состоянием, алгоритмом функционирования и текущим состоянием соседних клеточных автоматов [75] т.е.: тдеуи состояние клеточного автомата в момент времени /+1; Уц - состояние клеточного автомата в момент времени t; f- функция переходов клеточного автомата. Определим возможные состояния клеточного автомата. К1 - начальное (неподвижное) состояние клеточного автомата; К2 - активное неустойчивое состояние, характеризующееся неравенством логического и физического адресов; К2 - пассивное неустойчивое состояние, характеризующееся неравенством логического и физического адресов и присутствием на входах клеточного автомата более приоритетных, чем собственный, логических адресов; К4 - устойчивое состояние, соответствующее отказу микроконтроллера; К5 - пассивное состояние, характеризующееся равенством физического и логического адресов клеточного автомата. Из устойчивого состояния К4 клеточный автомат не может перейти в какое-либо другое состояние. Функционирование клеточного автомата начинается из начального состояния А4, в котором он удерживается до появления первого отказа какого-либо микроконтроллера. Если текущий КА изменил свой логический адрес, то его состояние меняется на активное состояние К , в котором он удерживается в течение времени достаточном для распространения сигналов достижимости по всей матричной структуре ММК. Если КА находясь в состоянии К2 получает сигналы достижимости с логическими адресами более приоритетными чем собственный, то состояние КА меняется на пассивное состояние К, в котором он находится до исчезновения на его входах более приоритетных логических адресов. После чего клеточный автомат переходит в активное состояние К . В любой момент времени, независимо от текущего состояния клеточного автомата, при возникновении отказа соответствующего микроконтроллера, КА переходит в устойчивое состояние отказа К4, в котором находится бесконечно долго. Рабочий цикл клеточного автомата может включать два набора состояний: { К\ К2, Кх) или { К1, К2, К3, К2, К1}. При этом в состояние К3 КА может перейти несколько раз. Из состояния К3 в устойчивое состояние К1 клеточный автомат может перейти только через активное состояние К2. В соответствии с классификацией, приведенной в статье [76], данный клеточный автомат относится к сбалансированному, т.е. выходы одной клетки соответствуют входам соседних клеточных автоматов. Входными воздействиями для каждой клетки являются: отказ текущего микроконтроллера; изменение логического адреса; появление на входах текущего микроконтроллера сигналов достижимости и логических адресов. Так как входные воздействия применяются неодновременно ко всем клеточным автоматам, то разработанный клеточный автомат является итеративным. Слово Sij состояния клетки представляется множеством переменных Sij={x//4 xT J, EkJ, dklJ, qkJ), где ke{ 1,2,3,4} - направления исходящих из вершины дуг графа Gl и графа G2; [1, если текущая вершина является источником хн - \ [0, если текущая вершина является транзитной , fl, если текущая вершина является адресатом хт - \ [0, если текущая вершина является транзитной , EklJe {0.1} - работоспособность/отказ линка в направлении к; dk J - вес дуги в направлении к графа G, - величина в диапазоне от 0 до MxN; MuN- число строк и столбцов соответственно; qk Je (0,1} - вес дуги в направлении к графа G2. Клеточный алгоритм адаптивной маршрутизации по логическому адресу приемника сообщения в соответствии с правилами 1 и 2 обработки моделей Gx и G2 представлен подстановками Q\ и Q2. , иначе; Адресатом сообщения может быть и МК, не изменявший своего логического адреса. В этом случае для такого МК граф достижимостей Gx не строится, а дуги графа G2 необходимо строить, основываясь на исходной информации о местоположении программных модулей. При этом сообщение необходимо передавать сначала горизонтально до достижения столбца адресата и далее вертикально до достижения строки адресата. Но тогда не учитывается местоположение отказавших МК и связей между ними. В результате процесс передачи сообщения может прерваться из-за отказавших связей или вершин. Для разрешения подобных ситуаций используется возможность передачи сообщения от других МК. Эта возможность реализуется следующим образом. В случае отказа линка или вершины в направлении передачи сообщения делается "шаг" в перпендикулярном направлении: направление 1 меняется на направление 2 или 3, направление 2 на 1 или 4, направление 3 на 1 или 4, направление 4 на 2 или 3 [70-73]. В таблице 2.3 приведены графические иллюстрации возможного изменения направления ретрансляции сообщения с соответствующими им подстановками.
Структурная организация процесса маршрутизации
Условно устройство маршрутизации можно разделить на три составных блока: блок построения графа достижимостей G, ; блок построения графа маршрута передачи сообщений G2; элемент памяти. Блок построения графа достижимостей служит для приема сигналов достижимости и логических адресов от соседних элементов мультиконтроллера, выбора наиболее приоритетного сигнала достижимости и формирования кода направления, а также передачи сигналов достижимости и логических адресов соседним элементам. Сформированный код направления записывается в память (в таблицу достижимости), в ячейку с адресом соответствующим максимальному из принятых логических адресов.
Блок построения маршрута передачи сообщения служит для приема входящего сообщения, выбор из него адресной части, далее по данному адресу из памяти выбирается код направления, в котором передается принятое сообщение соседнему устройству маршрутизации однородной среды процессорных элементов.
Особенностью построения цифровых устройств, входящих в состав мультиконтроллера, является необходимость взаимодействия каждой ячейки с четырьмя соседними элементами. Взаимодействие ячеек посредством многоразрядных цифровых кодов ведет к чрезмерному увеличению физических линий, что приводит к увеличению сложности устройства. Одним из способов уменьшения числа линий связи является применение континуальных (аналоговых) величин. В этом случае для передачи некоторого значения между соседними взаимодействующими ячейками достаточно одной физической линии связи. Однако, взаимодействие с помощью аналоговых величин с последующим аналого-цифровым преобразованием для цифровой обработки не является целесообразным, так как это приведет к чрезмерной сложности устройства. Для обхода данного недостатка применяются элементы континуальной алгебры логики [79, 80] позволяющие строить устройства обработки данных, представленных в континуальном (непрерывном, аналоговом) виде. Одним из таким элементов является элемент континуальной конъюнкции с одним выходом [79], показанный на рисунке 3.3. На рисунке 3.4 представлена функциональная схема устройства маршрутизации сообщений в однородной среде процессорных элементов [81,82].
Выходы устройства маршрутизации: SO, SI, S2, S3, S4, Rl, R2, R3, R4, Д\, Д2, ДЗ, Д4, ЛА 1, ЛА2, ЛАЗ, ЛА4 - соответствуют одноименным входам соседних устройств. Выход ФО - сигнал фатального отказа, равен логической единице, когда текущий модуль не может передать сообщение ни в одном из четырех направлений. Предлагаемое устройство совместно с другими аналогичными устройствами образует систему обмена сообщениями между процессорными элементами (ПЭ). Система представляет собой однородную матричную структуру из MxN ячеек (устройств), каждая ячейка которой соединена по четырем направлениям с соседними ячейками (устройствами). Передача ц? сообщений между любыми ячейками осуществляется через другие ячейки (транзитным способом). Местоположение ячейки маршрутизации и соответствующего ему ПЭ определяется ее физическим адресом (ФА) - (i,j) (где i = \,M - номер строки, j = \,N - номер столбца матрицы).
Принцип передачи сообщений между ПЭ заключается в следующем: при получении ячейкой сообщения сравнивается адресная часть сообщения (адрес приемника сообщения) и логический адрес текущей ячейки, если они равны, то сообщение считается принятым и передается в ПЭ соответствующий текущей ячейки маршрутизации однородной среды, в противном случае ячейка маршрутизации передает сообщение в направлении, извлеченном из собственной таблицы достижимости из ячейки по адресу приемника сообщения.
Ячейки маршрутизации однородной среды процессорных элементов, взаимодействуя между собой, настраивают таблицы достижимости таким образом, чтобы обеспечивалась передача сообщения необходимому ПЭ по кратчайшему пути в обход отказавших элементов и каналов передачи сообщений. При этом в начальный момент (до появления отказов) таблицы достижимости всех устройств маршрутизации настроены так, чтобы передача сообщения осуществлялась по кратчайшему пути без учета отказавших ПЭ (сначала горизонтально до достижения столбца приемника и далее вертикально до достижения строки приемника).
Исследование алгоритма маршрутизации при различных конфигурациях отказов МК
Целью создания программной модели устройства маршрутизации является необходимость проверки работоспособности разработанного алгоритма адаптивной маршрутизации и исследование характеристик предложенного алгоритма.
Программная модель разработанного алгоритма маршрутизации должна отвечать следующим требованиям: адекватность разработанному алгоритму; удобство задания параметров маршрутизации (положение источника и приемника); наглядное представление результатов маршрутизации сообщения. При моделировании алгоритма адаптивной маршрутизации осуществляется взаимодействие программных моделей клетки самоорганизации и модели алгоритма маршрутизации. С помощью компьютерной модели самоорганизации осуществляется создание мультиконтроллера, задание отказовой конфигурации микроконтроллеров и реконфигурирование ММК. Далее результат перестройки передается в программную модель алгоритма маршрутизации.
При построении программной модели было введено следующее допущение: если какой-либо микроконтроллер помечался как отказавший, то все окружающие его связи также помечались как отказавшие; вероятность определения отказа линии связи определялась с вероятность равной единице, таким образом, не учитывалась вероятность безотказной работы аппаратных средств определения отказов микроконтроллеров.
Модель среды коммутаций сообщений (набор устройств маршрутизации) предполагает: к существующим отказам микроконтроллеров добавление отказов произвольного числа межмодульных связей, запуск первого этапа работы алгоритма (перестройку таблиц достижимостей), задание положений источника и приемника сообщений. В диалоговом режиме есть возможность наблюдать по шагам маршрут передачи сообщения от источника к приемнику. Окно программной модели устройства маршрутизации показано на рисунке 4.3.
Как видно из рисунка 4.3 с помощью модели была создана сеточная структура, в которой крестиками отмечены отказы микроконтроллеров и межмодульных связей.
В приведенном примере источником сообщения является МК[4,5], а приемник был задан в МК[3,2]. МК-приемник является отказавшей вершиной (помечен крестиком) и в результате самоорганизации его программный модуль сместился в МК[2,2]. Как видно из приведенного примера в результате работы алгоритма (применение ранее разработанной системы параллельных подстановок маршрутизации) сообщение достигло адресата в МК[2,2]. Данный пример показывает, что применение разработанного алгоритма позволило найти кратчайший путь от МК-источника до МК-приемника сообщения в обход всех отказов вершин и связей между ними.
Нажатие кнопки "Автоматическая настройка ТД" приводит к запуску первого этапа работы алгоритма, а именно, подстройке таблиц достижимости. При этом, если таблицы подстраивать после ввода отказавших межмодульных связей, то отказы линков будут учтены, в противном случае-нет. Это свойство позволяет проверить работу алгоритма в различных ситуациях,возникающих в процессе функционирования мультиконтроллера.
С помощью разработанной программной модели среды обмена сообщениями в ММК исследуем разработанный алгоритм адаптивной маршрутизации на различных конфигурациях отказов узлов и связей между ними.
В процессе передачи сообщений могут возникнуть следующие ситуационные комбинации: сообщение необходимо передавать в отсутствии отказов МК; сообщение передается при отказах МК и связей между ними; передачи сообщения без построения графа достижимостей; передача сообщения в замкнутой области отказов. Минимальная длина маршрута передачи сообщения вычисляется по формуле: Zm/n=A/+Af; A/=min{///- іп\, М- \іи- іп\}; A/=min{/;/ -jn\, N - ]/// -jn\}; где Ми N- число строк и столбцов ММК соответственно; {Ubjid - координаты МК-источника сообщения; (inj n) - координаты МК-приемника сообщения. На рисунке 4.4 представлен пример передачи сообщения при отсутствии отказов узлов и наличии отказов линков. Из представленного примера видно, что сообщение из МК-приемника с физическим адресом [4,3] достигло МК-адресата с физическим адресом [7,8]. Так как в представленном примере нет отказов МК, то самоорганизация мультиконтроллера не проводилась, и логические адреса микроконтроллеров не изменялись, следовательно, программный модуль ПМ[7,8] располагается в МК[7,8], в котором процесс маршрутизации завершается. Сообщение достигло адресата в обход отказов всех линков. Траектория движения сообщения включает следующие микроконтроллеры: МК[4,3] — МК[4,4] — МК[3,4] —» МК[3,5] МК[2,5] МК[2,6] МК[2,7] - МК[2,8] -» МК[1,8] -+ МК[9,8] — МК[8,8] — МК[7,8]. Траектория движения сообщения, построенная разработанным алгоритмом маршрутизации, включает 11 транзитных узлов, следовательно, L=\. Минимально возможная длина маршрута для данного расположения источника и приемника вычисляется в отсутствии отказов и равняется: Lmin-S.
