Содержание к диссертации
Введение
Глава 1. Методы и алгоритмы маршрутизации в реконфигурируемых многопроцессорных системах 11
1.1. Модели реконфигурации многопроцессорных систем 11
1.2. Алгоритмы маршрутизации в многопроцессорных системах с отказами 15
1.3. Концепция клеточной маршрутизации в реконфигурируемых многопроцессорных системах 29
1.4. Выводы к главе 33
Глава 2. Клеточный алгоритм отказоустойчивой маршрутизации в многопроцессорных системах 35
2.1. Клеточно-автоматная модель отказоустойчивой передачи сообщений 35
2.2. Клеточный алгоритм локализации приемника 39
2.3. Клеточный алгоритм определения доступности приемника 43
2.4. Клеточный алгоритм поиска минимального маршрута 49
2.5. Выводы к главе 53
Глава 3. Клеточный алгоритм адаптивного управления маршрутизацией в реконфигурируемой системе 55
3.1. Подход к передаче сообщений при перемещении абонентов 55
3.2. Клеточный алгоритм коррекции смещений источника в реконфигурируемой структуре 61
3.3. Клеточный алгоритм поиска приемника в реконфигурируемой структуре 64
3.4. Примеры вычисления маршрутов при перемещении абонентов 67
3.5. Выводы к главе 75
Глава 4. Исследование клеточных алгоритмов маршрутизации реконфигурируемых систем 76
4.1. Описание программы моделирования клеточных алгоритмов маршрутизации 76
4.2. Исследование алгоритма маршрутизации при фиксированном расположении абонентов 80
4.3. Исследование алгоритма маршрутизации при перемещении абонентов 86
4.4. Сравнительный анализ алгоритмов маршрутизации 98
4.5. Выводы к главе 110
Заключение 112
Список использованных источников
- Алгоритмы маршрутизации в многопроцессорных системах с отказами
- Клеточный алгоритм локализации приемника
- Клеточный алгоритм коррекции смещений источника в реконфигурируемой структуре
- Исследование алгоритма маршрутизации при фиксированном расположении абонентов
Введение к работе
Актуальность работы. Параллельные и распределенные вычисления
являются эффективным средством повышения производительности
вычислительных и управляющих многопроцессорных систем (МПС).
Разрабатываемые модели и алгоритмы параллельных и распределенных вычислений, реализуемых в сетевых структурах с большим числом процессорных элементов (ПЭ), позволяют исследовать множество природных и социальных явлений, управлять множеством объектов, обрабатывая огромные потоки информации. Учитывая важность и сложность решаемых задач, оперативность их решения, отказы отдельных элементов не должны влиять на коллективные вычисления и приводить к срыву моделирования или управления.
Для обеспечения нечувствительности вычислений к отказам элементов и связей необходима разработка моделей, алгоритмов автоматической адаптации структуры и межпроцессорных взаимодействий к возникающим отказовым ситуациям. При этом они должны отвечать требованиям масштабируемости и оперативности, позволяющим сохранять реконфигурационные свойства системы при изменении размеров системы, комбинаций отказов и обеспечивать автоматическое восстановление без прерывания процесса вычислений.
Широко используемой моделью структуры МПС является решетка с
замкнутыми границами, эффективно вкладываемая в матричные структуры на
СБИС. Одним из путей обеспечения масштабируемости адаптивных
отказоустойчивых МПС с решетчатой структурой является создание в них
статических сетей, использующих неизменяемые при реконфигурации
непосредственные связи между ПЭ. Наращивание многопроцессорных систем с непосредственными связями выполняется подключением новых элементов прямыми связями в соответствии с реализуемой топологией. Автоматическая реконфигурация в отказоустойчивых масштабируемых системах достигается за счет взаимного резервирования программных модулей смежных процессорных элементов и клеточного решения задачи перенастройки работоспособных элементов системы (включая резервные) на новые функции. Подобная клеточная реконфигурация не требует предварительного сбора глобальных данных о состоянии элементов системы, формирования и хранения таблиц соответствия логических и физических адресов ПЭ, а также перезагрузки программ по новым местам размещения. Однако при этом возникают задачи разработки моделей и алгоритмов оптимальной передачи сообщений между ПЭ в реконфигурированной системе с произвольными отказами компонент при отсутствии данных о новом расположении программных модулей.
Разработке теории практики создания моделей и алгоритмов
отказоустойчивой распределенной маршрутизации посвящено много работ (Duato J., Wu J., Khan G.N., Колосков В.А., Колоскова Г.П., Савенков Н.А., Каравай М.Ф.), отличающихся стратегиями обхода неисправных компонент при поиске рациональных путей передачи сообщений. Так, известные модели маршрутизации
(Chen C.L., Chiu G.M.), основанные на обработке специальных данных об отказавших областях произвольной конфигурации и их последующем обходе, допускают ремаршрутизацию и не гарантируют поиск минимальных маршрутов. Известные стратегии обхода выпуклых областей отказов при ограничениях на структуру областей (Wu J.) не обеспечивает доставку сообщений к работоспособным узлам, расположенным внутри локализованной области отказов, и позволяет эффективно строить только минимальные пути, если они существуют. Для моделей распределенной маршрутизации с динамическим адаптивным формированием локальных решений по маршрутизации (Duato J., Khan G.N., Wei G., Suh Y.J., Dao B.V.) выбор направления передачи сообщения выполняется на основе установленных приоритетов направлений и отслеживания состояния смежных узлов и линков, что может приводить к блокированию сообщений в промежуточных вершинах и выбору более длинных путей. Все перечисленные подходы к отказоустойчивой маршрутизации используют глобальные обновленные данные о текущем расположении источников и приемников сообщений по результатам реконфигурации.
Известные клеточные модели маршрутизации в реконфигурируемых
системах без прерывания обеспечивают поиск перемещаемого при
реконфигурации приемника, но либо допускают отклонения от минимальных маршрутов при кольцевых обходах областей отказов, либо требуют существенных временных затрат на формирование вспомогательных данных о последствиях реконфигурации.
Таким образом, актуальным является решение научно-технической задачи поиска новых локальных характеристик элементов реконфигурируемой многопроцессорной системы и разработки на их основе модели и алгоритмов клеточных вычислений для отказоустойчивой распределенной маршрутизации, поддерживающих масштабируемость и оперативность обмена сообщениями и обеспечивающих выбор минимальных маршрутов между изменяющими свое расположение абонентами.
Объектом исследования являются модели и алгоритмы распределенной и параллельной маршрутизации в многопроцессорных системах с отказами компонент.
Предметом исследования в диссертационной работе являются клеточные
алгоритмы маршрутизации, использующие локальные характеристики
доступности приемника в условиях отказов и данные о результатах реконфигурации и позволяющие передавать сообщения адресатам, изменяющим свое местоположение.
Целью диссертационной работы является поиск новых информационных характеристик распределенной маршрутизации и разработка на их основе модели и алгоритмов клеточных вычислений для отказоустойчивой передачи сообщений, обеспечивающих выбор минимальных маршрутов между мигрирующими абонентами.
Для достижения поставленной цели в диссертационной работе решались следующие задачи:
Разработка клеточной модели и алгоритма маршрутизации на основе локальных данных о состоянии элементов и связей многопроцессорной системы.
Разработка новой стратегии обмена сообщениями между перемещаемыми абонентами на базе локальных данных о реконфигурации.
Разработка клеточной модели и алгоритма адаптивной маршрутизации в реконфигурируемой системе с перемещаемыми абонентами на основе локальных данных об отказах и результатах реконфигурации.
Создание программных средств моделирования алгоритмов маршрутизации и экспериментальное исследование разработанного клеточного алгоритма и известных алгоритмов на программных моделях.
Методы исследования основаны на использовании математического аппарата и методов теории графов, языков программирования, численных методов, теории вероятностей и математической статистики, теории надежности технических систем, математического моделирования, теории топологического проектирования однородных структур, теории проектирования автоматов и дискретных систем.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
Клеточный алгоритм определения маршрута передачи сообщения в условиях произвольных отказов элементов и связей многопроцессорной системы, отличающийся формированием распределенных данных о доступности приемника и гарантирующий получение минимального маршрута.
Метод клеточной локализации получателя сообщения в реконфигурированной многопроцессорной системе, отличающийся использованием локальных данных о результатах реконфигурации, и позволяющий определять физическое расположение приемника, изменяющего местоположение в процессе реконфигурации.
Клеточная модель и алгоритм адаптивной маршрутизации сообщений, отличающиеся использованием распределенных данных об удаленности узлов от приемника и результатах реконфигурации и позволившие получать минимальные маршруты передачи сообщений между перемещаемыми абонентами при произвольных отказах элементов и каналов связи.
Практическое значение работы определяется возможностью применения разработанных клеточных алгоритмов для создания распределенных вычислительных сред маршрутизации в составе отказоустойчивых масштабируемых реконфигурируемых многопроцессорных систем различного назначения и в созданных программных средствах моделирования клеточных алгоритмов.
Результаты работы использованы: в учебном процессе при обучении студентов по направлению магистерской подготовки 230100 «Информатика и вычислительная техника» в дисциплине «Надежность проектных решений» и в
научно-исследовательской работе кафедры по теме «Разработка и исследование распределенных моделей и алгоритмов реконфигурируемых многопроцессорных систем», что подтверждено соответствующими актами. Научные положения, выносимые на защиту:
Метод клеточного поиска минимального маршрута на основе распределенных локальных данных о работоспособности элементов и связей многопроцессорной системы.
Клеточный алгоритм локализации приемника в реконфигурированной многопроцессорной структуре на основе распределенных локальных данных о результатах реконфигурации.
Клеточная модель и клеточный алгоритм адаптивной минимальной
маршрутизации между перемещаемыми абонентами в реконфигурированной
многопроцессорной структуре с произвольными комбинациями отказавших
элементов и связей.
Результаты моделирования клеточных алгоритмов маршрутизации
реконфигурируемых многопроцессорных систем.
Соответствие паспорту научной специальности. Содержание диссертации соответствует п. 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий», п. 5 «Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента» и п. 8 «Разработка систем компьютерного и имитационного моделирования» паспорта специальности 05.13.18 -Математическое моделирование, численные методы и комплексы программ.
Апробация работы. Основные результаты диссертационной работы обсуждались на: X Международной научно-методическая конференция «Информатика: проблемы, методология, технологии» (Воронеж, 2010 г.), XXXVI Международной молодежной научной конференции «Гагаринские чтения» (Москва, 2010 г.), XXXVII Международной молодежной научной конференции «Гагаринские чтения» (Москва, 2011 г.), XI Международной научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике» (Пенза, 2011 г.), IX Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2011 г.), X Международной конференции молодых ученых «Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT + SE’2012». (Украина Ялта-Гурзуф, 2012 г.), 3-ей Российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» (Москва, 2012 г.), Международной конференции «Параллельные вычисления и задачи управления» PACO’12 ИПУ РАН (Москва, 2012 г.), Х Всероссийской школа-конференция молодых ученых «Управление большими системами» (Уфа, 2013 г.) XL Международной молодежной научной конференции «Гагаринские чтения» (Москва, 2014 г.).
Публикации. Результаты диссертационного исследования опубликованы в 15 печатных работах, среди них 12 тезисов докладов и 3 статьи в журналах, входящих в Перечень ведущих изданий, рекомендованных ВАК.
Личный вклад автора. Все научные результаты диссертационного
исследования получены автором лично. В основных научных работах по теме
диссертации, опубликованных в соавторстве и приведенных в конце
автореферата, личный вклад соискателя состоит в следующем: в [1]
сформулированы требования к автономной самовосстанавливающейся среде; в [2]
приведены результаты моделирования клеточных алгоритмов реконфигурации
самовосстанавливающейся среды; в [3] разработаны алгоритм определения
минимальных множества перенастраиваемых контроллеров и алгоритм
перекодирования логических адресов в ходе реконфигурации; в [4] рассмотрено
построение клеточных алгоритмов среды адаптивной маршрутизации в
микроконтроллерной сети с отказами; в [5] представлены клеточные правила и
функции среды, обеспечивающие восстановление логической структуры; в [6]
представлены дискретная и континуальная модели поиски оптимального
маршрута; в [7] проведено моделирование, подтвердившее корректность
алгоритма, являющегося основой для создания автоматной сети
реструктуризации; в [8] рассмотрены клеточные алгоритмы и правила обработки локальных данных, обеспечивающие восстановление логической структуры сети при многократных отказах; в [9] представлена клеточная модель самоорганизация среды; в [10] представлен подход к организации маршрутизации сообщений на основе данных о результатах реконфигурации; в [11] представлен алгоритм отказоустойчивой маршрутизации на базе естественно-подобной среды; в [12] представлены правила обработки локальных данных при поиске маршрутов передачи сообщений для перемещаемых абонентов в реконфигурированной системе в условиях произвольных отказов; в [13] представлен распределенный децентрализованный клеточный алгоритм маршрутизации сообщений в реконфигурируемой структуре МПС, обеспечивающий построение минимальных маршрутов передачи сообщений; в [14] рассмотрены правила обработки локальных данных при определении характеристик доступности приемника сообщений и поиска маршрутов в условиях произвольных отказов; в [15] описаны функции определения значений длин потенциальных минимальных маршрутов к приемнику в условиях отказов элементов и линков.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы включающего, 87 источников, а также одного приложения. Работа изложена на 144 страницах, включая приложение, содержит 71 рисунок и 1 таблицу.
Алгоритмы маршрутизации в многопроцессорных системах с отказами
Под маршрутизацией в общем случае понимается передача сообщения от одного ПЭ другому с максимальной производительностью, согласно заданному методу или алгоритму [40]. Алгоритм маршрутизации реализуется в программно-аппаратной части маршрутизатора - устройства, отвечающего за формирование адресата, которому должен быть передано сообщение [41]. Для поддержки масштабируемости реконфигурируемой МПС алгоритмы маршрутизации должны быть распределенными и решать следующие задачи: сбор и распределение информации о состоянии элементов и коммуникационной среды МПС; локализация приемника сообщений с учетом его перемещения на этапе реконфигурации; формирование оптимальных маршрутов передачи сообщений; передача сообщения по выбранному маршруту. Ключевой характеристикой для распределенных алгоритмов маршрутизации является способ построения маршрута передачи сообщения. Выделяют три основных класса алгоритмов маршрутизации [42–44]: 1. алгоритмы фиксированной и статической маршрутизации; 2. алгоритмы простой маршрутизации; 3. алгоритмы адаптивной маршрутизации. Принципиальная разница между этими классами алгоритмов заключается в степени учета изменения топологии, что в конечном итоге приводит к формированию различных по длинам маршрутам передачи сообщений. Исследуемый в данной работе класс систем относится к системам с архитектурой МКМД, представляемой в виде ортогональной матрицы (решетки) из узлов, где – число узлов по оси ординат, – число узлов по оси абсцисс. При свертывании границ решетки по вертикали и горизонтали она превращается в открытый тор. Расстояние между соседними узлами по всем направлениям постоянно и равно шагу решетки, расстояние между произвольными двумя узлами определяется в ортогональной метрике. Узлы системы представлены однотипными процессорными элементами (ПЭ), реализующими функции вычисления, реконфигурации и маршрутизации. ПЭ МПС является универсальным элементом замены, позволяющим перестраивать его на функции любого из четырех соседних элементов.
Наиболее простой при описанной топологии является локальная маршрутизация с передачей от источника через ПЭ по оси абсцисс пока до достижения столбца, содержащего приемник, затем направление меняется на перпендикулярное, и сообщение передается по оси ординат, пока не достигнет приемника – XY-маршрутизация (рис. 1.3.) [45, 46]. При таком подходе нет необходимости формировать таблицы маршрутизации, поскольку в каждом узле в любой момент времени всегда можно вычислить направление передачи сообщения из координат источника и приемника. Рис. 1.3. Локальная маршрутизация в матричной структуре Однако представленный алгоритм, несмотря на то, что позволяет сформировать самый короткий маршрут от источника к получателю сообщения, имеет существенный недостаток – безальтернативность при формировании маршрута. В случае возникновении отказа в одном из промежуточных узлов и/или каналов связи приводит к потере передаваемого сообщения.
Одним из способов устранения этого недостатка является использование таблиц маршрутизации (достижимости), использование которых позволяет корректировать маршрут передачи сообщения с учетом текущего состояния структуры МПС. В МПС с решетчатой структурой возможны возникновения двух типов отказов: отказ элемента и отказ каналов связи. В связи с этим существует два подхода к маршрутизации в отказоустойчивых МПС: использование коммутации отказавшего узла и полное исключение отказавшего узла из маршрута. Способы обхода отказов а) обход отказавшего ПЭ б) обход отказавшего ПЭ и его связей Естественным подходом к организации отказоустойчивой маршрутизации является перенастройка таблиц маршрутизации при возникновении отказов [47, 48]. Для повышения надежности маршрутизации некоторыми авторами предлагается перенастройка таблиц маршрутизации в оффлайн режиме [49]. Этот подход позволяет достигать надежность в 99.99% при возникновении до 10% отказов узлов в системе. Подход, предложенный в статье [49], реализует поиск всех возможных маршрутов с учетом отказов в оффлайн режиме с последующим выбором оптимального из них. Существенным недостатком таких подход является необходимость использования центрального маршрутизатора, а также перезагрузка системы при перенастройке таблиц маршрутизации, что не позволяет добиться безостановочной работы МПС.
Обход произвольных областей отказов в соответствии с распределенной стратегией маршрутизацией [4] предусматривает динамическое адаптивное формирование текущей информация о статусе передаваемого сообщения, которая используется для выбора локального решения по маршрутизации. При этом не известна глобальная информация об отказах, обрабатываются данные о состоянии только соседних линков и узлов. Существо правил обхода отказовых областей состоит в следующем: если в направлении уменьшения расстояния в направлении X или Y сообщение встречает отказ, оно ремаршрутизируется в том же измерении (X или Y), но в противоположном направлении; если отказ встречается повторно, сообщение передается в ортогональном измерении и реализует попытку обойти вокруг отказавшей области.
Клеточный алгоритм локализации приемника
Функционирование клетки маршрутизатора инициируется при появлении запроса на передачу сообщения от произвольного ПЭ системы. Для клеточного определения физического расположения приемника по значениям отклонений разработаны клеточные операции вычисления координат узла с нулевыми значениями смещений. Инициальные значения клеточных переменных: ( ) , . При появлении запроса на передачу сообщения от ПЭ-источника клетка маршрутизатора фиксирует значение . В соответствии с правилами операции вычисляются координаты физического размещения приемника поиском узла с нулевыми значениями смещений.
Разработанная клеточная операция обеспечивает локализацию приемника путем уменьшения отклонений при перемещениях по горизонтали вправо (пока ), и вниз до достижения . Результат выполнения операция для решетки с отказавшими узлами (отмечены на рис. 2.3. слева черным цветом) представлен исходными и итоговыми значениями переменных клеточного массива: .
Эволюция клеточных переменных Таким образом, разработанный клеточный алгоритм обеспечивает определение физического расположения источника путем итерационной обработки локальных данных смежных узлов. Полученные данные используются для клеточного формирования характеристик доступности приемника и вычисления на их основе маршрута передачи сообщения с учетом отказов узлов и линков МПС.
В отличие от известных подходов к адаптивной маршрутизации, использующих данные о конфигурации областей отказов и характеристики близости узлов к отказовым областям, в диссертационной работе предлагается подход к поиску потенциальных маршрутов разрешенной транзитной передачи сообщений к приемнику на основе новой информационной характеристики: доступности приемника из любого узла при произвольных комбинациях отказов в тороидальной структуре.
Транзитная передача через элемент запрещается только при отказе-го ПЭ , что равносильно отказу 3-х или 4-х линков работоспособного элемента. Множество обрабатываемых переменных включает переменные состояния ПЭ:, переменные доступности приемника и переменную физического размещения приемника . Введем обозначения: n j – минимальное значение доступности приемника при движении в направлении ; - номера смежных для узла вершин; - переменные состояния линков (работоспособный / отказавший) для узла в смежных направлениях .
В соответствии с правилом значения вектора доступности любого узла по входным работоспособным каналам отличаются от минимального выходного значения вектора доступности смежного соседа на единицу: . Очевидно, исходящая из любого узла ( ) решетки дуга указывает на минимальное значение шагов до приемника ( ) при движении в направлении k {1,2,3,4}. Если для любой транзитной вершины выбирать направление маршрута с минимальным значением , то это обеспечит фиксацию маршрута к приемнику с минимальной длиной пути, что и требовалось доказать. Очевидно, если существуют кратчайшие пути, равные Хеммингову расстоянию, то они всегда будут зафиксированы, что иллюстрирует рис. 2.6.
Только наличие отказавших компонент исключают возможность перемещений в соответствующих направлениях и минимальный путь для некоторых может отличаться от Хеммингова расстояния, как показывает рис. 2.6. для узлов и . Из-за отказов в смежной вершине и канале связи с приемником минимальные маршруты от : и от узла : на один шаг превышают расстояние по Хеммингу.
Таким образом, правило определяет длины потенциальных минимальных маршрутов через работоспособные узлы, фиксируя направления с минимальной длиной маршрута до приемника. В работоспособные транзитные узлы перемещения разрешаются с любого направления, в отказавшие вершины перемещения запрещаются. Пример реализации операции представлен на рис. 2.7. итоговым состоянием переменных клеточного массива, соответствующего состоянию решетки, показанной слева (черным отмечены отказавшие узлы). Пример определения доступности при отказах узлов и линков Примеры клеточного определения доступности приемника по правилу для различных вариантов расположения приемника и отказавших элементов представлены в виде весов дуг на графовых решетках (рис. 2.9).
Разработанный клеточный алгоритм всегда определяет минимальные значения доступности, которые в большинстве случаев совпадают с Хемминговым расстоянием. Только при блокировании перемещений отказавшими вершинами минимальная доступность превышает расстояние по Хеммингу (вершина на рис. 2.9.). Таким образом, клеточный алгоритм определения доступности приемника обеспечивает вычисление кратчайших расстояний от любого узла тора до приемника с учетом отказов компонент (элементов и линков) МПС при движении в смежных направлениях. Полученные значения являются основой для клеточного поиска минимального маршрута передачи сообщения.
Клеточный алгоритм коррекции смещений источника в реконфигурируемой структуре
Если источник и приемник сообщений не участвуют в реконфигурации, локализация приемника выполняется в соответствии с операцией (см. раздел 2.2). Если в процессе реконфигурации один из абонентов или оба одновременно изменяют свое расположение, необходима разработка клеточных операций по локализации перемещаемых в пространстве абонентов.
В соответствии с источник может перемещаться по горизонтали и в зависимости от направлений перемещений ( ) горизонтальное смещение может увеличиться или уменьшиться. При этом учитывается топология многопроцессорной структуры и смещение принимает нулевое значение при перемещении источника в позицию столбца приемника , либо максимальное значение при смещении вправо от позиции столбца приемника . Если элемент не вовлечен в реконфигурацию , значение сохраняется неизменным. При вертикальном перемещении относительно первоначального расположения значение также корректируется с учетом направления перемещения ( ) и взаимного расположения источника и приемника: при – абоненты расположены в одной строке, при – размещены в максимально удаленных строках. Коррекция смещения по вертикали выполняется в соответствии с положениями Утверждения 3.2. При отсутствии перемещений не изменяется. Так, для варианта реконфигурированной структуры (см. рис. 3.1.) с координатами источника и приемника первоначальные значения смещений По значениям переменных (рис. 3.1.) в позиции перемещенного узла-источника видно, что при реконфигурации источник переместился в позицию с правого направления
Корректировка смещений отражает реальное расположение перемещенного источника относительно приемника. Клеточное правило обеспечивает изменение заданных значений для перемещаемого источника. Правило , обеспечивает локализацию приемника до реконфигурации . Поскольку в результате реконфигурации возможно изменение расположения приемника, необходима разработка клеточного алгоритма определения реальных физических координат приемника. На основе положений доказанного
В соответствии с значение переменной в реконфигурированной структуре может совпадать со значением , если приемник не охвачен реконфигурацией. Это возможно только при нулевых значениях переменных для работоспособного узла . Если в позиции первоначального размещения приемника выявлен отказ , то при нулевых значениях узел всегда участвует в реконфигурации, являясь источником маршрута восстановления. В то же время по правилу любая позиция клеточного пространства, для которой может стать приемником сообщения в результате перемещения в нее приемника из смежной вершины. При этом значение формируется с учетом статуса перемещаемой в вершины: если в перемещаемой вершине локализован приемник { Л ), то значения становятся координатами физического расположения приемника в реконфигурированной структуре.
Пример перемещения приемника при реконфигурации Передача сообщения в реконфигурированной структуре с перемещаемыми абонентами, реализуется после коррекции значений смещений источника (правило ) в позицию приемника со значением (правило ). Разработанные клеточные правила и обеспечивают локализацию перемещаемого приемника из перемещаемого источника для произволных комбинаций отказов на основании клеточной обработки локальных данных о результатах реконфигурации многопроцессорной структуры.
Рассмотрим примеры клеточного поиска минимальных маршрутов в реконфигурируемой структуре для произвольных комбинаций отказов. Пример 1. Вычисление маршрута при перемещении источника. Рассмотрим случай передачи сообщения от программного модуля с логическим адресом к программному модулю с адресом . а) Корректировка смещений источника Исходные значения смещений координат принимают значения , . По результатам реконфигурации источник переместился из позиции в позицию . При этом корректировка первоначальных смещений и производится по правилу и принимает вид , т.к. ( ) , а , т.к. . б) Поиск первоначального расположения приемника
В позиции , в которой значения смещений принимают значения , является первоначальным расположением приемника. Значение переменной принадлежности узла приемнику до реконфигурации принимает значение . Корректировка расположения приемника происходит только в случае включения узла в маршрут реконфигурации. в) Определение позиции приемника с учетом реконфигурации
Минимальный маршрут передачи сообщения Приведенный пример демонстрирует применимость разработанных клеточных правил для нахождения минимального маршрута передачи сообщения при перемещении в результате реконфигурации среды источника сообщения.
Вычисление маршрута при перемещении приемника. Теперь рассмотрим случай передачи сообщения передачи сообщения от источника с логическим адресом к переместившемуся в результате реконфигурации программному модулю с адресом а) Корректировка смещений источника Исходные значения отклонений принимают значения , . В результате реконфигурации приемник переместился из позиции из ячейки в позицию , источник при этом не изменил расположение .
После локализации реальной позиции приемника сообщения последовательно выполняются клеточные операции определения характеристик минимальной доступности приемника и построения минимального маршрута от источника к приемнику в условиях текущей отказовой ситуации. г) Определение характеристик доступности приемника
Минимальный маршрут передачи сообщения Приведенный пример демонстрирует применимость разработанных клеточных правил для определения минимального маршрута передачи сообщения даже в случае перемещения источника и приемника в результате реконфигурации в среде.
Исследование алгоритма маршрутизации при фиксированном расположении абонентов
Одним из основных показателей эффективности алгоритмов маршрутизации является длина маршрута от источника до приемника, так как она определяет время передачи сообщения и загруженность транзитных каналов. В работе выполнен сравнительный анализ длин маршрутов между парами элементов в многопроцессорной структуре с заданными свойствами (размерностью, размещением абонентов и отказавших узлов), вычисляемых для трех известных распределенных алгоритмов и разработанного клеточного алгоритма маршрутизации.
Пронумеруем сравниваемые разновидности алгоритмов маршрутизации: 1 – разработанный клеточный алгоритм маршрутизации; 2 – алгоритм с выбором направления передачи на основе распределенных блоков восстановления [3]; 3 – алгоритм с обходом произвольных областей отказов на основе кольца отказовой области [1]; 4 – алгоритм с обходом произвольных областей отказов на основе адаптивной ремаршрутизации [4].
Ниже в графическом виде представлены результаты сравнения пар алгоритмов (разработанного и одного из известных), полученные при моделировании алгоритмов на множестве одинаковых комбинаций отказов и вариантов размещения отправителя и получателя сообщения. Клеточные массивы, соответствующие приведенным решениям для разработанного клеточного алгоритма представлены в Приложении 1. а) Сравнение алгоритмов №1 и №2 На рис. 4.19. представлены примеры моделирования алгоритмов №1 и №2 на различных комбинациях отказов. Для первой отказовой комбинации оба алгоритма дают оптимальный результат, поскольку в приоритетных направлениях (в направлениях уменьшения значений смещений по осям ) каналы связи работоспособны. Во второй и третьей комбинациях алгоритмом №2 выполняется обход области отказов с удлинением маршрута. Если по двум осям в приоритетных направлениях перемещений каналы неработоспособны, то алгоритм №2 отмечает как запрещенные пройденные отрезки пути, выполняет возврат к ранее пройденным узлам и переходит в режим обхода неисправности, что удлиняет путь, т.к. возвраты и обходы могут быть многократными.
Так, сначала в свободном режиме выполняются два шага в направлении уменьшения смещений (п.1). Далее очередные два шага в направлении уменьшения смещений приводят к зацикливанию в узле отправителе (в п.2 длина пути – 4), и алгоритм переходит в режим обхода (возврат с запретом повторных входов в ранее пройденные узлы и поиск новых направлений). В режиме обхода выполняются два шага возврата к ранее пройденным узлам с запретом перемещений в них по входному линку (в п.3 длина пути – 6). От промежуточного узла (3,4) выполняется переход в свободный режим. В свободном режиме строится маршрут по работоспособным каналам в направлении уменьшения смещений (еще 7 шагов). Итоговая длина маршрута – 13. Для сравнения: разработанный клеточный алгоритм позволил получить минимальный маршрут длиной 5 шагов (рис. 4.21.).
Таким образом, адаптивный выбор приоритетного направления в текущем узле сетчатой структуры не позволяет в известном алгоритме №2 гарантировать оптимальную маршрутизацию на последующих шагах. Разработанный алгоритм свободен от этого недостатка и для любого узла обеспечивает выбор рационального направления к приемнику для любой комбинации отказов.
В то же время для алгоритма №3 длина маршрута во многом определяется конфигурацией отказовой области, а попытка обхода области отказов приводит к ремаршрутизации и последующему перемещению по неперспективным направлениям, что удлиняет маршрут. Так, для второй комбинации отказов на рис. 4.22. в течение первых 7 шагов сообщение огибает по кольцу отказовую область сверху до достижения в столбце с отказа линка. Далее выполняется возврат (12 шагов) в обратном направлении до достижения получателя сообщения в строке с .
Таким образом, формирование данных о конфигурации областей отказов в известном алгоритме №3 обеспечивает обход областей вокруг огибающего кольца, но не гарантирует получение минимальных маршрутов.
Разработанный клеточный алгоритм свободен от этого недостатка, так как выбор направления перемещения в произвольном узле основан не на конфигурации запрещенной области, а на распределенных данных о возможных последствиях обхода любых отказавших компонент при движении к приемнику. в) Сравнение алгоритмов №1 и №4 Результаты моделирования сравниваемых алгоритмов №1 и №4 для комбинаций отказов, при которых оптимальные направления передачи свободны от отказов, показали эффективность обоих алгоритмов (рис. 4.23.). При отсутствии отказов в направлениях уменьшения отклонений , маршрутизация в алгоритме №4 эквивалентна построению маршрута при полном отсутствии отказов. В то же время при появлении отказов на пути передаваемого сообщения известный адаптивный алгоритм всегда меняет направление обхода либо на противоположное, либо на ортогональное (при повторном отказе), что приводит к удлинению маршрута даже при малом количестве отказов .
Анализ результатов моделирования алгоритмов на множестве отказовых комбинаций показал, что известная стратегия маршрутизации [4] обеспечивает адаптивный поиск приемника, но получаемые маршруты близки или совпадают с минимальными только при свободных от отказов направлениях уменьшения значений отклонений. Если на пути передачи сообщения встречаются отказы, то применяемые правила не позволяют выбирать рациональные направления, и сообщение многократно «огибает» препятствия, пока не достигнет цели. Разработанный клеточный алгоритм всегда обеспечивает поиск оптимального маршрута для текущей комбинации отказов благодаря использованию распределенной характеристики доступности адресата сообщения.
