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

• Автор: Абдель-Джалил Джихад Надир
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Курск
• Количество страниц: 229 с. : ил.

Введение

1. ЗАДАЧИ ОБРАБОТКИ СООБЩЕНИЙ В ПАРАЛЛЕЛЬНЫХ 8 ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

1.1. Архитектура современных вычислительных систем.

1.1.1. Классификация архитектур вычислительных систем.

1.1.2. Организация памяти вычислительных систем.

1.2. Организация коммуникационной сети вычислительных систем.

1.3. Задача и алгоритмы маршрутизации сообщений.

1.4. Отказоустойчивая маршрутизация сообщений.

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

2. ОТКАЗОУСТОЙЧИВАЯ МАРШРУТИЗАЦИЯ СООБЩЕНИЙ И ПРОЦЕДУРА ЕЕ РЕАЛИЗАЦИИ

2.1. Постановка задачи отказоустойчивой маршрутизации.

2.2. Процедура отказоустойчивой маршрутизации с поворотом системы координат.
2.3. Примеры применения процедуры маршрутизации.
2.4. Выводы по главе.
3. УСТРОЙСТВО ОТКАЗОУСТОЙЧИВОЙ МАРШРУТИЗАЦИИ СООБЩЕНИЙ
3.1. Структурнофункциональная организация устройства маршрутизации.
3.2. Анализ функционирования устройства маршрутизации.
3.3. Выводы по главе.
4. СРАВНИТЕЛЬНАЯ ОЦЕНКА СОЗДАННОГО АЛГОРИТМА 2 МАРШРУТИЗАЦИИ
4.1. Экспериментальная оценка потерь сообщений и времени 2 маршрутизации.
4.1.1. Экспериментальная оценка потерь сообщений и времени 2 маршрутизации.
4.1.2. Особенности языка имитационного моделирования.
4.1.3. Архитектура инструментальных программных средств.
4.1.4. Модель разработанного устройства маршрутизации.
4.1.5. Результаты вычислительного эксперимента.
4.2. Оценка аппаратной сложности устройства маршрутизации
4.3. Оценка времени построения маршрутов.
4.4. Выводы по главе.
Заключение.
Список литературы


Топология КС должна быть такой, чтобы минимизировать расстояние между парами взаимодействующих процессоров и обеспечивать множество альтернативных маршрутов между процессорами в целях повышения потенциальной отказоустойчивости ВС. В соответствии с принятой классификацией выделяются статические и динамические КС [7,9]. Главной отличительной особенностью статических КС является обеспечение непосредственной связи только между строго определенными модулями. Взаимодействие модулей, не имеющих общего канала, как правило, осуществляется через другие модули, называемые в этом случае транзитными. Для осуществления информационного взаимодействия между такими модулями формируется виртуальный канал связи, создаваемый в момент начала обмена информацией и разрушаемый в момент его окончания. КС осуществляет обработку информации на основании анализа некоторых признаков, содержащихся в формате сообщений. В основном статические КС работают по методу коммутации пакетов, заключающемся в том, что сообщение передается от передатчика к приемнику порциями (пакетами) фиксированного объема и через ряд КЭ. Динамические КС в противоположность статическим предполагают возможность непосредственного физического соединения всех пар модулей, при этом соединение заключается в коммутации некоторых модулей (в связи с этим динамические КС нередко называют перекрестными коммутаторами). Информационное взаимодействие происходит на основе построения физических линий связи между взаимодействующими модулями. Динамические КС используют централизованное управление, которое осуществляет специальное устройство. Оно, в зависимости от расположения модулей, формирующих запрос на организацию обмена, вырабатывает управляющий код, который поступает на входы коммутатора и обеспечивает формирование непосредственного физического соединения модулей. Межмодульный обмен начинается после установления соответствующего физического канала. Существуют также коммутаторы, использующие децентрализованное управление, формирование межмодульного канала в таких коммутаторах происходит так же как и в статических КС. Динамические КС нашли наиболее широкое применение при построении мультипроцессоров, в то время как в мультикомпьютерах применяются главным образом статические КС. В этой связи в дальнейшем рассматриваются только статические КС (далее - просто КС). В зависимости от сложности пространственного строения принято выделять простые и сложные топологии КС. Простые КС (одномерные и двумерные), как правило, представляются плоскими графами и имеют небольшой предел наращивания. При формализованном представлении КС обычно описывают следующими параметрами. Размер сети (network size) (N) - численно равен количеству узлов, объединяемых сетью. Число связей (number of links) (L) - суммарное количество каналов между всеми узлами сети. Диаметр сети (network diameter) (D), называемый также коммуникационным расстоянием, - длина минимального пути, по которому проходит сообщение между двумя наиболее удаленными друг от друга узлами сети. Порядок узла (d). Каждый узел сети связан с прочими узлами множеством каналов. Порядок узла я: равен числу узлов сети, с которыми данный узел связан напрямую. Например, в сети, организованной в виде матрицы, где каждый узел имеет каналы только к ближайшим соседям слева, справа, сверху и снизу, порядок узла равен четырем. Ниже рассматриваются наиболее распространенные топологии КС. В простейшей линейной топологии узлы сети образуют одномерный массив и соединены в цепочку (рис. Линейная топология характеризуется следующими параметрами: D = N - I; d = 2; I = N - . Линейная топология не обладает свойством полной симметричности, поскольку узлы на концах цепочки имеют только одну коммуникационную линию, то есть их порядок равен 1, в то время как порядок остальных узлов равен 2. Время пересылки сообщения зависит от расстояния между узлами, а отказ одного из них способен привести к невозможности пересылки сообщения. По этой причине в линейных КС используют отказоустойчивые узлы, которые при отказе изолируют себя от сети, позволяя сообщению миновать неисправный узел.