Алгоритм и устройство маршрутизации в логической структуре отказоустойчивого мультиконтроллера

• Автор: Савенков, Николай Анатольевич
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Курск
• Количество страниц: 139 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

2.2. Алгоритм самоорганизации мультиконтроллера
2.3. Алгоритм адаптивной маршрутизации
2.3.1. Содержательное описание алгоритма маршрутизации
2.3.2. Формирование таблиц достижимости
2.3.3. Графовая модель процесса маршрутизации
2.3.4. Клеточный алгоритм адаптивной маршрутизации
2.4. Пример применения алгоритма адаптивной маршрутизации
2.5. Выводы к главе
ГЛАВА 3. УСТРОЙСТВО МАРШРУТИЗАЦИИ ОДНОРОДНОЙ СРЕДЫ ПРОЦЕССОРНЫХ ЭЛЕМЕНТОВ
3.1. Структурная организация процесса маршрутизации
3.2. Функциональная схема маршрутизатора
3.3. Организация однородной среды обмена сообщениями
3.4. Выводы к главе
ГЛАВА 4. МОДЕЛИРОВАНИЕ И ИССЛЕДОВАНИЕ СРЕДЫ РЕКОНФИГУРАЦИИ И МАРШРУТИЗАЦИИ
4.1. Моделирование среды реконфигурации мультиконтроллера
4.2. Исследование характеристик ячейки реконфигурации
4.3. Программная модель устройства маршрутизации
4.4. Исследование алгоритма маршрутизации при
различных конфигурациях отказов МК
4.5. Исследование характеристик маршрутизации
4.6. Выводы к главе
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Барнаул, г. УН-й Международной научно-технической конференции "Медикоэкологические информационные технологии - " (г. Курск, г. ХХХ1-Й Международной научной молодежной конференции "Гагаринские чтения" (г. Москва, г. Х-Й Международной научно-технической конференции "Решетневские чтения" (г. Красноярск, г. V Международной конференции "Идентификация систем и задачи управления" (г. Москва, г. Публикации. Результаты диссертационного исследования опубликованы в 7 статьях, 5 тезисах докладов и защищены положительным решением о выдаче патента на изобретение. Научные положения, выносимые на защиту. Локальные правила обхода отказавших элементов и связей мультиконтроллера, построения множества допустимых маршрутов передачи сообщений и выбора одного из них, позволившие осуществить маршрутизацию сообщения независимо от применяемого в мультиконтроллере алгоритма реконфигурации за счет параллельного распространения информации об изменении логических адресов микроконтроллеров. Клеточный, аппаратно-ориентированный алгоритм адаптивной маршрутизации в логической структуре реконфигурируемого мультиконтроллера, позволяющий сократить траекторию передачи сообщения путем непосредственного поиска приемника по логическому адресу в формате сообщения. Функциональная организация устройства адаптивной маршрутизации в логической структуре реконфигурируемого мультиконтроллера, обеспечивающего поиск адресата по логическому адресу независимо от его местоположения, позволившего за счет разделения процессов ретрансляции сообщения и настройки таблиц достижимости осуществить обмен сообщениями без прерывания функционирования мультиконтроллера. Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы включающего, источника. Работа изложена на 9 страницах и содержит рисунков и 4 таблицы. В введении к диссертации обосновывается актуальность работы, ее научная новизна, формулируются цели и задачи диссертационного исследования, приводится краткое содержание глав диссертации и положения выносимые на защиту. В первой главе проводится анализ существующих алгоритмов адаптивной маршрутизации, который показал их неработоспособность в условиях неизвестного положения адресата сообщения и применения произвольного алгоритма самоорганизации мультиконтроллера. Во второй главе разрабатывается алгоритм адаптивной маршрутизации независящий от применяемого в ММК метода реконфигурирования логической структуры, формулируются правила построения множества допустимых маршрутов передачи сообщения, выбора одного из них и правила обхода отказавших узлов. В третьей главе проводится разработка функциональной схемы устройства, реализующего предлагаемый алгоритм адаптивной маршрутизации, способного передавать сообщения в мультиконтроллере с отказами узлов и связей между ними. В четвертой главе проводится исследование алгоритма маршрутизации на различных конфигурациях отказавших узлов, связей между ними и при различной размерности мульти контроллера, приводится сравнение с существующими решениями. В заключении приведены основные результаты, полученные в диссертационном исследовании. Возможное применение. Результаты диссертационной работы могут найти применение при построении мультиконтроллера, отвечающего повышенным требованиям по отказоустойчивости. ГЛАВА 1. В настоящее время сфера применения многопроцессорных вычислительных систем (МВС) непрерывно расширяется, охватывая все новые области в самых различных отраслях науки, бизнеса и производства. Стремительное развитие кластерных систем создает условия для использования многопроцессорной вычислительной техники в реальном секторе экономики. Наряду с расширением области применения, по мере совершенствования МВС происходит усложнение и увеличение количества задач в областях, традиционно использующих высокопроизводительную вычислительную технику. В настоящее время выделен круг фундаментальных и прикладных проблем, эффективное решение которых возможно только с использованием сверхмощных вычислительных ресурсов.