Клеточные алгоритмы маршрутизации в реконфигурируемых многопроцессорных системах

• Автор: Павлюченко, Данила Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 144 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. МЕТОДЫ И АЛГОРИТМЫ МАРШРУТИЗАЦИИ В
РЕКОНФИГУРИРУЕМЫХ МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ
1Л. Модели реконфигурации многопроцессорных систем
1.2. Алгоритмы маршрутизации в многопроцессорных системах с отказами
1.3. Концепция клеточной маршрутизации в реконфигурируемых многопроцессорных системах
1.4. Выводы к главе
ГЛАВА 2. КЛЕТОЧНЫЙ АЛГОРИТМ ОТКАЗОУСТОЙЧИВОЙ МАРШРУТИЗАЦИИ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ
2.1. Клеточно-автоматная модель отказоустойчивой передачи сообщений.
2.2. Клеточный алгоритм локализации приемника
2.3. Клеточный алгоритм определения доступности приемника
2.4. Клеточный алгоритм поиска минимального маршрута
2.5. Выводы к главе
ГЛАВА 3. КЛЕТОЧНЫЙ АЛГОРИТМ АДАПТИВНОГО УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ В РЕКОНФИГУРИРУЕМОЙ СИСТЕМЕ
3.1. Подход к передаче сообщений при перемещении абонентов
3.2. Клеточный алгоритм коррекции смещений источника в реконфигурируемой структуре
3.3. Клеточный алгоритм поиска приемника в реконфигурируемой структуре.
3.4. Примеры вычисления маршрутов при перемещении абонентов
3.5. Выводы к главе
ГЛАВА 4. ИССЛЕДОВАНИЕ КЛЕТОЧНЫХ АЛГОРИТМОВ МАРШРУТИЗАЦИИ РЕКОНФИГУРИРУЕМЫХ СИСТЕМ
4.1. Описание программы моделирования клеточных алгоритмов маршрутизации
4.2. Исследование алгоритма маршрутизации при фиксированном расположении абонентов
4.3. Исследование алгоритма маршрутизации при перемещении абонентов.

4.4. Сравнительный анализ алгоритмов маршрутизации
4.5. Выводы к главе
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЕ 1. Клеточные массивы

ВВЕДЕНИЕ
Актуальность работы. Параллельные и распределенные вычисления являются эффективным средством повышения производительности вычислительных и управляющих многопроцессорных систем (МПС). Разрабатываемые модели и алгоритмы параллельных и распределенных вычислений, реализуемых в сетевых структурах с большим числом процессорных элементов (ПЭ), позволяют исследовать множество природных и социальных явлений, управлять множеством объектов, обрабатывая огромные потоки информации. Учитывая важность и сложность решаемых задач, оперативность их решения, отказы отдельных элементов не должны влиять на коллективные вычисления и приводить к срыву моделирования или управления.
Для обеспечения нечувствительности вычислений к отказам элементов и связей необходима разработка моделей, алгоритмов автоматической адаптации структуры и межпроцессорных взаимодействий к возникающим отказовым ситуациям. При этом они должны отвечать требованиям масштабируемости и оперативности, позволяющим сохранять реконфигурационные свойства системы при изменении размеров системы, комбинаций отказов и обеспечивать автоматическое восстановление без прерывания процесса вычислений.
Широко используемой моделью структуры МПС является решетка с замкнутыми границами, эффективно вкладываемая в матричные структуры на СБИС. Одним из путей обеспечения масштабируемости адаптивных отказоустойчивых МПС с решетчатой структурой является создание в них статических сетей, использующих неизменяемые при реконфигурации непосредственные связи между ПЭ. Наращивание многопроцессорных систем с непосредственными связями выполняется подключением новых элементов прямыми связями в соответствии с реализуемой топологией. Автоматическая реконфигурация в отказоустойчивых масштабируемых системах достигается за счет взаимного резервирования программных модулей смежных процессорных
ГЛАВА 2. КЛЕТОЧНЫЙ АЛГОРИТМ ОТКАЗОУСТОЙЧИВОЙ МАРШРУТИЗАЦИИ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ
2Л. Клеточно-автоматная модель отказоустойчивой передачи сообщений
Рассмотрим создание клеточного автомата маршрутизации, основанного на обработке новых типов переменных, описывающих оптимальные маршруты к приемнику сообщения. Клеточная обработка введенных переменных позволила реализовать новый принцип обхода областей отказов в МПС, свободный от недостатков известных решений.
В соответствии с [87] проектирование клеточного автомата отказоустойчивой маршрутизации состоит в задании для узла клеточного пространства:
а) множества имен клеток автомата;
б) шаблона связей с другими клетками;
в) алфавита обрабатываемых данных;
г) клеточных правил смены состояний.
Для рассматриваемого клеточного пространства имена клеток соответствуют координатам узлов тора {£,у} (£ = 1,2,..., т_/ = 1,2,..., п).
Ограничения на структуру связей клетки задаются шаблоном соседства со смежными узлами в ортогональных направлениях ГЦ,/) = {(£,_/), (£,_/'— 1), (£ +
1, Д (1 - 1, Д (ХУ + 1)}-
Алфавит клеточного автомата для решаемой задачи и включает переменные, описывающие состояние процессорного элемента, текущее состояние клетки маршрутизатора и переменные управления коммутацией каналов передачи сообщения.
Состояние ПЭ описывается следующими переменными:
Хд Е {1,0} — отказ/работоспособность (ХДого ПЭ;