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

• Автор: Трунов, Дмитрий Алексеевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Курск
• Количество страниц: 154 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.
1. РАСПРЕДЕЛЕННАЯ РЕКОНФИГУРАЦИЯ ОДНОРОДНЫХ ОТКАЗОУСТОЙЧИВЫХ МНОГОПРОЦЕССОРНЫХ СИСТЕМ

1.1. Реконфигурирование мультипроцессоров с сетями прямых связей

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

1.3. Анализ способности систем к реконфигурированию и основные задачи исследований

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

2. АЛГОРИТМ АДАПТИВНОЙ РЕСТРУКТУРИЗАЦИИ ОТКАЗОУСТОЙЧИВЫХ МУЛЬТИКОНТРОЛЛЕРОВ

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

2.2. Алгоритм адаптивной реструктуризации мультиконтроллера

2.3. Примеры реализации алгоритма

2.4. Выводы к главе
3. РЕСТРУКТУРИЗАЦИЯ ПРОЦЕССОРНЫХ МАТРИЦ МЕТОДОМ СЛИЯНИЯ СЕГМЕНТОВ
3.1. Принципы адаптивной реструктуризации методом слияния сегментов.
3.2. Определение базовой линейки ресегментации.
3.3. Алгоритм ресегментации методом слияния сегментов
3.4. Примеры реализации алгоритма
3.4. Выводы к главе
4. РЕСТРУКТУРИЗАЦИЯ ПРОЦЕССОРНЫХ МАТРИЦ МЕТОДОМ ПЕРЕМЕЩЕНИЯ РЕЗЕРВА
4.1. Характеристика метода перемещения резервных линеек
4.2. Алгоритм адаптивной реструктуризации .
4.3. Аппаратная реализация среды реструктуризации.
4.4. Выводы к главе.
5. ИССЛЕДОВАНИЕ АЛГОРИТМОВ АДАПТИВНОЙ РЕСТРУКТУРИЗАЦИИ
5.1. Среда моделирования алгоритмов управления реструктуризацией
5.2. Исследование алгоритмов реструктуризации
матричных процессоров и мультиконтроллеров.
5.3. Выводы к главе.
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Объектом рассмотрения в диссертации являются мультиконтроллерные системы и матричные процессоры, относящиеся к классам MIMD и SIMD-архитектур и использующие коммуникационные сети с прямыми и косвенными связями соответственно. Для современных областей применения таких систем (управление технологическими процессами в реальном времени; обработка изображений; машинное зрение; структурный анализ; обработка речевых, гидролокациоиных, радиолокационных, сейсмических, метеорологических, астрономических, медицинских и других данных) решаются все более ответственные задачи, и ущерб от их отказа может быть очень значительным, что ставит задачу обеспечения отказоустойчивости мультипроцессорных систем и матричных процессоров в разряд первоочередных [-]. В следующих разделах рассмотрен перспективный подход к повышению отказоустойчивости, основанный на введении избыточных элементов и средств управления реконфигурацией систем для обхода возникающих отказов [-]. В отказоустойчивых многопроцессорных системах и мультиконтроллерах для повышения отказоустойчивости широко используют различные методы резервирования: статического, динамического, гибридного []. При этом с целью сокращения дополнительных затрат оборудования и времени разрабатываются к-отказоустойчивые многопроцессорные структуры для различных топологий и разных вариантов загрузки систем [,]. Так, большой интерес исследователей вызывает организация многопроцессорных систем в виде гиперкубов, обладающих достаточно широким диапазоном связей элементов. Методология гибкого распределения функций между основными и резервными элементами в гиперкубовой архитектуре, позволяющая выполнять перезагрузку и восстановление системы дана в работе []. Для данного подхода отсутствует возможность оперативного восстановления работоспособности из-за перезагрузки системы, и характерна большая избыточность из-за дублирования элементов. В работе [] рассматривается гиперкуб, в котором за каждым элементом закреплен дублирующий процессор с загруженными задачами основного. При восстановлении работоспособности системы в случае отказа основного элемента выполняется автоматическое переключение на резервный процессор с сохранением отношений смежности, поддерживающих принятую схему реконфигурации. Для данного подхода характерны большая аппаратурная избыточность и незначительная гибкость метода, не позволяющая варьировать число резервных элементов. Алгоритм переназначения логических адресов в многопроцессорной системе с отказами с последующей централизованной перезагрузкой системы предложены в []. Для рассмотренных подходов кроме перечисленных недостатков характерна необходимость перепроектирования систем при увеличении размерности гиперкубов, либо при корректировке логической структуры решаемой задачи (изменении программы управления). Эффективным решением задачи обеспечения отказоустойчивости мультиконтроллерных и мультипроцессорных систем, свободным от перечисленных выше недостатков, является создание активной среды самоорганизации, интегрируемой в систему [-] с произвольным запасом резервных элементов. Для оперативного восстановления функций каждый МК отказоустойчивого ММК кроме своего программного модуля хранит копии модулей физических соседей []. Это позволяет оперативно восстанавливать логическую структуру при отказах отдельных МК путем перенастройки микроконтроллеров, принадлежащих маршрутам от отказавших до резервных узлов. Активная среда самоорганизации ММК, обеспечивающая управление восстановлением, повторяет топологию сети ММК, и также представляет решетку или тор, узлам которых (Су) соответствуют автоматы настройки микроконтроллеров, а ребрам - связи между ними (рис. Возникающие конфигурации отказавших элементов ММК проецируются на активную среду, инициирующую репродуцирование логической структуры ММК. Таким образом, активная среда самоорганизации обеспечивает оперативное восстановление логической структуры при отказах отдельных процессорных элементов путем нереразмещения программных модулей на множестве работоспособных процессоров (рис.