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

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

Павлюченко Данила Владимирович

КЛЕТОЧНЫЕ АЛГОРИТМЫ МАРШРУТИЗАЦИИ В РЕКОНФИГУРИРУЕМЫХ МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ

Специальность 05.13.18 "Математическое моделирование, численные методы и комплексы программ"

АВТОРЕФЕРАТ

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

Москва-2014

005552938

005552938

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «МАТИ -Российский государственный технологический университет имени К.Э. Циолковского» на кафедре «Проектирование вычислительных комплексов».

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

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

Ведущая организация:

доктор технических наук, профессор Колосков Василий Александрович

доктор технических наук, профессор, руководитель университетской программы ЗАО «Интел А/О» Плоткин Арнольд Леонидович

кандидат физико-математических наук, зав. сектором НИИСИ РАН Торгашев Михаил Александрович

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Воронежский государственный университет»

Защита диссертации состоится «20» ноября 2014 г. в 14 ч. 00 мин. на заседании диссертационного совета Д 212.110.08 в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «МАТИ — Российский государственный технологический университет имени К.Э. Циолковского» по адресу 121552, г. Москва, ул. Оршанская, д.З, ауд. 612А.

С диссертацией можно ознакомиться в библиотеке, а также на сайте федерального государственного бюджетного образовательного учреждения высшего профессионального образования «МАТИ — Российский государственный технологический университет имени К.Э. Циолковского» http://www.mati.ru.

Автореферат диссертации разослан «18» сентября 2014 г.

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

кандидат физико-математических наук, Мо кряков А.В.

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

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

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

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

Разработке теории практики создания моделей и алгоритмов отказоустойчивой распределенной маршрутизации посвящено много работ (Duato J., Wu J., Khan G.N., Колосков В.А., Колоскова Г.П., Савенков H.A., Каравай М.Ф.), отличающихся стратегиями обхода неисправных компонент при поиске рациональных путей передачи сообщений. Так, известные модели маршрутизации

(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 Международной конференции молодых ученых «Информационные технологии в науке, образовании, телекоммуникации и бизнесе 1Т + 8Е'2012». (Украина Ялта-Гурзуф, 2012 г.), 3-ей Российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» (Москва, 2012 г.), Международной конференции «Параллельные вычисления и задачи управления» РАСО'12 ИПУ РАН (Москва, 2012 г.), X Всероссийской школа-конференция молодых ученых «Управление большими системами» (Уфа, 2013 г.) ХЬ Международной молодежной научной конференции «Гагаринские чтения» (Москва, 2014 г.).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предлагаемый подход к клеточному поиску минимальных маршрутов в дискретном пространстве с отказами элементов и связей основан на определении характеристик доступности приемника для всех узлов пространства. Под доступностью приемника из элемента (¿,у) понимается значение вектора Ш^1 = дискретных величин {ю1^}, соответствующих минимальным расстояниям в шагах решетки от данного элемента до приемника, при движении через работоспособные каналы связи в направлениях ке{ 1,2,3,4}.

Введенная характеристика для любого узла клеточного пространства описывает все потенциальные маршруты к приемнику сообщения и является основой для распределенного решения задачи определения минимального маршрута от источника к приемнику в условиях произвольных отказов. Для описания маршрута передачи сообщения введены клеточные маршрутные переменные = {и^, и^. и'гз' 1^4}, где и/^ £ (ОД) соответствует отсутствию или наличию маршрута от узла (1,7) к смежному соседу в направлении к.

На основе анализа специфики решаемой задачи был определен состав переменных клетки СИ^ распределенной вычислительной среды маршрутизации

(рис. 1), описывающих состояние процессорного элемента (х„ Е {1,0} — отказ/работоспособность (¿,/')-ого ПЭ, Ь1' = Е {1,0} - состояния работоспособности линков узла (¿,у) в смежных направлениях к), параметры команды источника сообщения (хЦ 6 {1,0} - принадлежность узла (¡,7) к источнику сообщения, ЛхЦ е [0,1,2, ...,п}, Ау^ е {0,1,2, ...,т] - значения отклонений по осям X, К от узла (/,/) до приемника); текущее состояние

УК,1'', Дуи) и результат работы (У^, К2'7 е {1,0} - выбор входного и выходного каналов маршрутизатора) клетки СЯп.

Д ХЧ ДУУ

13 „«+1./

АуЧ

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

1. Локализация физического расположения приемника хЦ по значениям Ах1', Ау1> (операция 0!).

2. Определение характеристик доступности приемника Ш^1 в условиях отказов элементов и линков (операция 02).

3. Определение минимального маршрута передачи сообщения от источника {х\{ = 1) к приемнику (х^ = 1) (операция 03).

4. Формирование переменных , У^1 настройки коммутационных элементов процессоров (операция 04).

Все клеточные алгоритмы оперируют только с локальными данными о состоянии смежных соседей и (¿,/)- го ПЭ.

После выполнения клеточной операции в1 локализации узла-приемника (рсЦ = 1) вычислительная среда реализует клеточную операцию 02 определения доступности приемника в условиях произвольных отказов:

+ 1, если {х[{ = 0) Л ( хЦ = 0) Л (1?кч = 0) Л Л * IX);

IX, если(и']п'п = IX) V (1™ = 1) V ( х1> = 1); (1)

1,если(4ч = 0) Л (хЦ = 1); если иначе,

где ЬХ - значение, отмечающее запрещенное направление передачи сообщения.

В работе доказано утверждение о свойствах минимальных маршрутов из узлов дискретного пространства к приемнику, в соответствии с которым для любой дуги маршрута (¿„,/п)< Оп+кУп+1) справедливо: м1^'™ = тт{м1"'1П] и

5 = 1,4

1™'1П 1. Разработанная операция 03 клеточного поиска минимального маршрута от узла-источника (х[/ — 1) к приемнику (хЦ = 1) обеспечивает выбор последователя на маршруте в направлении разрешенной минимальной доступности приемника:

1, если (ыЦ = Л (и^" Ф IX) Л

= (2)

03= =

Д если иначе,

где — тах{]л>2£) - максимальное значение маршрутной переменной

смежных узлов.

На рис. 2. показан маршрут от источника (д^'5 = 1) к приемнику (х^2 = 1), полученный в результате выполнения разработанных клеточных операций 01( 02,0з и соответствующее решению итоговое состояние переменных

I/ I/ I/ (/ I/ ¿У ¿1 и п I / ¿/

клеточного массива:*,/,Хи.Хп^п' vv12,и/13, 1У14,и/21, и/22,1У23, 1У24.

ООО 33 33 1000 000 2 2 2 2 0010 100 0000 0000 00 0 4444 0000 000 4444 0000

ООО 22 2? 0000 001 1111 0000 000 2 2 "> ? 0000 000 3333 0000 000 3333 0000

ООО 3333 0000 000 2 2 2 2 0000 000 3333 0000 000 4444 0000 100 0000 0000

000 4444 0000 000 333 3 0000 000 4444 0000 000 5555 0000 000 55 55 0000

000 4444 0010 100 0000 0000 000 55 55 0000 000 5555 0000 ета...... 5555 1000

Рис. 2. Результат клеточного построения минимального маршрута Для настройки коммутационных элементов процессоров при формировании канала передачи разработаны клеточные операции 04, выполняющие замыкание определенных входов {5} (у\'3 = 1) с выходами [к] — 1):

1, если \л?2к > 0, ^

, 0, если иначе.

„ аеии<2_,>0, у,= 10, если иначе.

. О, если иначе,

где у['3,у2к ~ управление замыканием ¿■-го входа и -го выхода коммутационного элемента (¿,;)-го процессора, (5, к) £ (1,2,3,4) - направления приема и передачи сообщения.

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

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

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

В работе обоснованы универсальные закономерности изменения значений Дх';, Ду1' для источника сообщений и координат физического расположения приемника (хЦ — 1) в реконфигурированной тороидальной структуре т х п на основании данных о реконфигурации. Попадание любого элемента (¿,7) в волну

АхЧ =

(4)

реконфигурации описывается переменными текущей реконфигурации узла Мч = [м'к'} Е {1,0}, где М]' - наличие/отсутствие перемещения логического адреса в узел (1,7) со смежного направления к е (1,2,3,4). Сформулированы и доказаны утверждения, определяющие клеточные правила изменения значений Ах'1, Ау1] и хЦ зависимости от текущих значений {м'к]].

С учетом закономерностей виртуального перемещения программных модулей при реконфигурации в состав переменных клетки маршрутизатора дополнительно включены переменные М1> (поступающие из клетки реконфигуратора) и х^ (внутренняя переменная маршрутизатора). Аналитическое представление разработанных клеточных операций коррекции значений Ах4, Ау4 для источника (05) и определения реальной позиции приемника = 1) (@6) в реконфигурированной структуре имеет вид:

( 0, если (Дх" = п - 1 )Л(М[; = 1), АхЧ - 1, если (,И\> = 1)Л(Дх" Ф 0), Ах1' + 1,если (М^' = 1)Л(Дх1> фп- 1),

- 1, если (АхЧ = 0 )Л(м{';' = 1), ^Ах1', если иначе. '0,если (Ду1' =т- 1 = 1),

Ду1' - 1, если (МЧ = 1)Л(Ду'7 Ф 0), АуЧ + 1, если (Мз'У = 1)Л(Ду'; * тп - 1) т - 1, если ( АуЧ = 0) = 1),

. АуЧ, если иначе. 1, если (ХЧ = 1 )Л(у4к=1мЧ = 0) • хЧ V

V ((*£' = 1) Л (мЦ = 1)) = 1.

. 0, если иначе,

где (р, <7) е {(¿,7 - 1), (1 + 1,/), (/ - 1,;'), (¿,У + 1)} - номера смежных вершин для узла (¿,У).

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

1. Коррекция значений АхЧ, АуЧ в формате сообщения источника (хЦ = 1) по результатам реконфигурации (65).

2. Поиск первоначального расположения приемника реконфигурации (б^.

3. Определение реальной позиции приемника х реконфигурации (06).

Д у1-

О г.'. х,

ПК

(5)

с1

до

1 по результатам

4. Определение характеристик Ш^1 доступности приемника = 1 для текущей отказовой ситуации (0г).

5. Определение минимального маршрута передачи сообщения от источника (л:^ = 1) к приемнику (х1^к = 1) (03).

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

Отказ

Резерв

1 2 3 4

1 0001 -> оооо 0000 0001 ->

2 0000 0000 1000 0000 п

3 0000 II 0000 0000 1000 <—

4 0001 -> 0000 0100 , У 0001 ->

б)

Рис. 3. Маршруты реконфигурации (а) и состояние переменных {М1к}} (б)

а) Корректировка смещений источника (05)

При передаче сообщения от программного модуля с логическим адресом (ЗД), перемещенного при реконфигурации в позицию (3,4), исходные значения смещений (Дх3,1, Ду3,1) = (3,3) в соответствии с 05 получат новые значения (Дх3'4, Ду3'4) = (0,3).

б) Поиск первоначального расположения приемника (б^)

В соответствии с Ог при (Дх3,4, Ду3,4) = (0,3) фиксируется позиция (2,4) со значениями (Дх2,4, Ду2,4) = (0,0), соответствующая первоначальному расположению приемника до реконфигурации и устанавливается хд4 = 1 (рис. 4,а).

в) Определение позиции приемника с учетом реконфигурации (06)

В соответствии с клеточным правилом @6 реальная позиция приемника сообщения для известных значений {М^} и х^'4 = 1 будет равна (2,3): (х^д = 1),

т.к.(*^ = 1)л(Д^3 = 1).

г) Определение характеристик МУ^1 доступности приемника и минимального маршрута передачи сообщения на их основе.

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

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

Дх1>,Ьу1' (00

(02)

44 44 44 0 1

40 40 40 00

44 44 44 0 3

44 44 44 02

4444 3 3 3 3 0000 5 5 5 5

3 3 3 3 2222 1111 0000

0000 3 3 3 3 0 0 0 0 777 7

5 5 5 5 4444 5 5 5 5 6 6 6 6

а) б) в)

Рис. 4. Результаты выполнения клеточных операций 0а (а), 02 (б), 03 (в)

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

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

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

При сравнительном анализе длин маршрутов выполнено моделирование разработанного клеточного алгоритма (№1) и алгоритмов для трех известных базовых стратегий распределенной маршрутизации: адаптивного выбора направления на основе распределенных блоков восстановления (№2); обхода произвольных областей отказов на основе кольца отказовой области (№3);

обходом произвольных областей отказов на основе адаптивной ремаршрутизации (№4). Результаты моделирования показали:

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

б) обход невыпуклых областей отказов вокруг огибающего кольца в алгоритме №3 приводит к ремаршрутизации и удлинению маршрута;

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

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

По результатам статистического моделирования четырех алгоритмов (№1-ь№4) при переборе К комбинаций отказов из п отказавших узлов и фиксированном размещении источника и приемника для каждого из алгоритмов были получены значения максимальных длин маршрута Ьп\

1п = тах{1^к}, (6)

к=1,к

где Ьк — длина маршрута для к-ой комбинации отказов; К - число комбинаций отказов из п элементов (узлов или линков).

Рис 5. иллюстрирует графики зависимости Ьп от п, полученные для тора 10 х 10.

отказов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Римский Д.С, Павлюченко Д.В., Колосков В. А. Построение среды самовосстановления автономной системы // Труды X Международная научно-методическая конференция «Информатика: проблемы, методология, технологии». Воронеж, 2010.

2. Римский Д.С., Павлюченко Д.В. Моделирование клеточной реконфигурации мультиконтроллера // Тезисы докладов XXXVI Международной молодежной научной конференции «Гагаринские чтения». М.: МАТИ. 2010.

3. Павлюченко Д.В. Самонастраиваемая среда управления реконфигурацией мультиконтроллеров // Тезисы докладов XXXVII Международной молодежной научной конференции «Гагаринские чтения». М.: МАТИ. 2011.

4. Колосков В.А., Динь Туан Лонг, Павлюченко Д.В. Клеточные алгоритмы адаптивной маршрутизации отказоустойчивых мультиконтроллеров. // Труды XI Международной научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике». Пенза, 2011. С. 24-26

5. Колосков В.А., Динь Туан Лонг, Павлюченко Д.В. Самоорганизующаяся среда реконфигурации отказоустойчивого мультиконтроллера // Труды XI Международной научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике». Пенза, 2011. С. 26-28.

6. Павлюченко Д.В., Динь Туан Лонг, Колосков В.А. Клеточные модели оптимальной маршрутизации в многопроцессорных системах с отказами // Труды IX Всероссийской научной конференции «Информационные технологии, системный анализ и управление». Таганрог, 2011. Т.1. С. 196-207.

7. Павлюченко Д.В., Динь Туан Лонг, Колосова Г.П. Клеточные модели поиска непесекающихся подсеток в многопроцессорных системах // Труды IX Всероссийской научной конференции «Информационные технологии, системный анализ и управление». Таганрог, 2011. Т. 1. С. 207-215.

8. Колосков В.А., Динь Туан Лонг, Павлюченко Д.В. Самореконфигурация в решетчатых структурах многопроцессорных систем // Труды конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» УКИ' 12. М. ИПУ РАН, 2012.

9. Колосков В.А., Динь Туан Лонг, Павлюченко Д.В. Клеточные модели самореконфигурации отказоустойчивых многопроцессорных систем // Труды международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» IT + SE' 2012. Приложение к журналу «Открытое образование». 2012.

10. Колосков В.А., Динь Туан Лонг, Павлюченко Д.В. Клеточные алгоритмы реконфигурации и маршрутизации на базе естественно-подобной среды // Труды международной конференции «Параллельные вычисления и задачи управления» РАСО' 12. М. ИПУ РАН, 2012.

11. Павлюченко Д.В., Динь Туан Лонг. Самонастройка функций и связей в отказоустойчивой многопроцессорной системе // Управление большими системами: материалы X Всероссийской школы-конференции молодых ученых. Том 3/ Уфимск. гос. авиац. тех . ун-т. - Уфа УГАТУ, 2013. С.228-232.

12. Колосков В. А., Колоскова Г.П., Павлюченко Д.В., Динь Туан Лонг. Адаптивное сетевое управление маршрутизацией в реконфигурируемых системах // «Мехатроника, автоматизация, управление». 2013. №8. С. 39-46.

13. Колосков В.А., Павлюченко Д.В., Динь Туан Лонг. Передача сообщений в реконфигурируемой отказоустойчивой многопроцессорной системе // Информационные технологии. 2013. №10. С. 29-35.

14. Павлюченко Д.В., Колосков В.А. Клеточный подход к отказоустойчивой маршрутизации в многопроцессорных структурах // «Наука и бизнес: пути развития». 2014. №2. С. 52-56.

15. Павлюченко Д.В. Алгоритм маршрутизации в многопроцессорных системах с отказами элементов и линков // XL Гагаринские чтения. Научные труды Международной молодежной научной конференции в 9 томах. Том 4. М.: МАТИ, 2014. Т. 4, С. 143-145.

Подписано в печать: 05.09.2014 Объем: 1,0 п.л. Тираж: 100 экз. Заказ № 2023 Отпечатано в типографии «Реглет» 119526, г. Москва, Мясницкие Ворота д. 1, стр. 3 (495)971-22-77; www.reglet.ru