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

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

Содержание
Введение.

Глава 1. Задачи обработки сообщений в параллельных системах.

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

1.2. Межпроцессорное взаимодействие в параллельных системах.

1.3. Задача маршрутизации сообщений и подходы к ее решению

1.4. Алгоритмы отказоустойчивой маршрутизации.

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

Глава 2. Процедура маршрутизации сообщений с обходом отказов

2.1. Модель параллельной системы и представление процесса маршрушзашш4

2.2. Характеристика предлагаемой процедуры маршрутизации

2.3. Примеры использования процедуры маршрутизации
2.4. Выводы по главе
Глава 3. Устройство маршрутизации на основе созданной процедуры
3.1. Функциональная организация устройства маршрутизации
3.2. Анализ работы устройства маршрутизации.
3.3. Выводы по главе.
Глава 4. Оценка эффективности разработанной процедуры и устройства динамической маршрутизации сообщений.
4.1. Оценка допустимости и длины маршрутов.
4.2. Оценка вероятности правильной передачи сообщения
4.3. Аналитическая оценка аппаратной сложности устройства маршрутизации
4.4. Определение предельной длины таблиц .маршрутизации
4.5. Оценка длины формата сообщения
4.6. Экспериментальная оценка созданной процедуры
маршрутизации
4.6.1. Постановка эксперимента.
4.6.2. Архитектура экспериментальных программных средств
4.6.3. Осхемы моделируемой системы.
4.6.4. Результаты эксперимента
4.7. Выводы по главе
Заключение
Список литературы


Однако такие ВС, аналогично кольцевым, не позволяют объединять значительное (N> - ) число ПЭ. Это обусловлено критичностью системы к рост}' межпроцессорного обмена, а также ограничениями электрического характера. Другим недостатком шинных структур является низкая надежность, которая фактически определяется надежностью общей шины. Одним из путей совершенствования структур с общей шиной является использование ВС с мультишинной организацией, включающих N’>1 шин (рис. Однако, несмотря на повышенную надежность, мультишинная организация обладает высокой удельной сложностью. Например, при использовании N = N общих шин затраты на каналы связи зависят от размерности ВС как О(^). Обмен информацией между ПЭ, входящими в различные подмножества таких систем, производится за счет транзитной передачи сообщений через общие для этих подмножеств элементы. Структуры с иерархической шинной организацией имеют несколько разновидностей и иногда называются кластерными структурами [7]. Кроме описанных выше структур при небольших значениях N применяются звездообразные структуры (рис. Однако, такие структуры также критичны к увеличению значения N и к росту интенсивности потока межпроцессорных сообщений, поскольку значительная часть этого потока проходит через центральный ПЭ звездообразной структуры. Более того, звездообразные структуры не обладают конструктивной однородностью, так как требует двух типов ПЭ с различным числом внешних выводов - для центрального узла и остальных узлов системы. При построении статических коммутационных ВС средней (N= -0) и большой (N>0) размерности описанные выше структуры не подходят и свое применение нашли структуры, изображенные на рис. Главной чертой этих топологических структур является обеспечение простого механизма наращивания размерности, кроме того, практически все позволяют формировать системы повышенной живучести, так как имеют возможность организации обхода отказавших ПЭ и линий связи. В ВС с топологией дерева (рис. ПЭ разбивается на Б подмножеств, образующих соответствующие уровни. Уровень 1 содержит единственный ПЭ, называемый корневым; элементы ^го уровня дерева, у = 2,Л-1, имеют по одной связи с элементами (д-1 )-го (верхнего) уровня и по Ь связей с элементами (]-И)-го (нижнего) уровня; корневой ПЭ связан только с Ь элементами второго уровня; элементы, соответствующие листьям дерева (элементы Б-го уровня или висячие узлы), имеют связь только с элементами (Б-1)-го уровня. Ь=2 [8]). Важным свойством дерева является логарифмический рост среднего времени передачи сообщений т при линейном увеличении размерности системы N. Однако топология дерева имеет ряд недостатков, которые обусловлены передачей сообщений между элементами поддеревьев через единственный соответствующий узел дерева. Таким образом, основным критическим участком дерева является корневой элемент - ПЭ первого уровня. Отказ данного ПЭ фактически приводит к разделению исходной структуры на b не связанных между собой поддеревьев с L-1 уровнями. Кроме того, значительная часть потока сообщений проходит через корневой ПЭ, что может привести к перегрузке данного ПЭ и потери работоспособности. Устранение указанных недостатков обеспечивается введением в дерево дополнительных каналов, связывающих узлы одинаковых уровней. Получаемая структурно-топологическая организация называется Х-деревом (рис. Другой вариант структурно-топологической организации ВС, устраняющий недостатки дерева получил название «толстое» дерево (fat tree) (рис. Реализация заключается в соединении нескольких деревьев в одно дерево, при этом множество ПЭ также разбивается на L подмножеств, образующих соответствующие уровни. Уровень 1 содержит s ПЭ, образующих корневой уровень; элементы j-ro уровня дерева, j-2,/,-1, имеют по одной связи с каждыми s элементами (j-l)-ro (верхнего) уровня и по bxs связей с элементами (j-H)-ro (нижнего) уровня; корневые s ПЭ связаны только с bxs элементами второго уровня; элементы, соответствующие листьям дерева (элементы L-ro уровня или висячие узлы), имеют связь только с элементами (L-l)-ro уровня []. Рис.