Метод, алгоритмы и аппаратные средства оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах

• Автор: Борисенко, Юлия Васильевна
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Курск
• Количество страниц: 128 с. : ил.

СОДЕРЖАНИЕ
Введение
1 Анализ методов и средств обеспечения отказоустойчивости мультикомпыотерных систем

1.1 Методы, модели и алгоритмы обеспечения отказоустойчивости в

мультикомпютерпых системах

1.2 Модели отказоустойчивых мультикомпьютеров

1.3 Методы и алгоритмы размещение задач в параллельных системах

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

1.3.2 Методы и алгоритмы размещения подпрограмм в мультипроцессорных системах

1.4 Анализ путей аппаратной реализации размещения подпрограмм в

мультикомпыотерных системах
1.5 Выводы
2 Метод оперативного переразмещения программ в отказоустойчивых мультикомпыотерных системах
2.1 Обобщенная постановка задачи переразмещения подпрограмм в
отказоустойчивых мультикомпьютерах
2.2 Математическая постановка задачи переразмещения подпрограмм в
отказоустойчивых мультикомпьютерах
2.3 Алгоритмы переразмещения подпрограмм с учётом отказов
процессоров и межпроцессорных связей
2.3.1 Алгоритм замены отказавшего процессора резервным
2.3.2 Алгоритм переразмещения с учётом отказа процессора
2.4 Выводы
3 Устройство оперативного переразмещения подпрограмм в отказоустойчивых мультипроцессорных системах
3.1 Принцип аппаратной реализации переразмещения подпрограмм в
отказоустойчи вых мул ьтиком п ьютерах
3.2 Структурная организация акселератора переразмещения
3.3 Алгоритмы функционирования акселератора
3.4 Устройство замены отказавшего модуля резервным
3.5 Оценка производительности и быстродействия акселератора
3.6 Устройство поиска кратчайшего пути обхода межпроцессорной связи
3.7 Оценка аппаратной и временной сложности устройства поиска кратчайшего пути обхода отказавшей межпроцессорной связи
3.8 Выводы
4 Моделирование алгоритмов оперативного переразмещения в отказоустойчивых мультипроцессорных системах
4.1 Программная модель процедур переразмещения с учётом отказа
процессора и/или отказа линка
4.2 Результаты исследования эффективности алгоритма планирования размещения
4.3 Результаты исследования эффективности алгоритма переразмещения с учётом отказа процессора и/или отказа линка
4.4 Выводы
Заключение
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Приложение

Введение
Актуальность темы. Отказоустойчивые мультикомпыотерные системы (ОМС) - одно из перспективных направлений развития параллельной вычислительной техники. ОМС способны непрерывно функционировать в условиях отказа отдельных узлов и каналов связи без необходимости проведения восстановительного ремонта за счет наличия в их архитектуре специальных аппаратно-алгоритмических средств, позволяющих автоматически обнаруживать отказы, выполнять их изолирование (и замещение резервными ресурсами) и обеспечивать восстановление логической целостности коммуникационной среды. Благодаря этим свойствам ОМС могут успешно применяться в качестве основы для создания критических важных объектов (критических систем, а именно: бортовые системы управления, системы управления опасными производствами и технологическими процессами и т.п.).
Теория отказоустойчивой организации мультикомпыотерных систем достаточно хорошо разработана. Большой вклад в эту область внесли работы отечественных ученых: С.И. Баранова, Вл.В. Воеводина, В.В. Воеводина, Ю.Ю. Громова, A.B. Каляева, И.А. Каляева, И.И. Левина, В.Г. Хорошевского, И.В. Зотова, а также зарубежных ученых: М. Флинна, К. Ванга, Р. Лонг-боттома, Д. Скилликорна и др. Однако вопросы, связанные с распределением резервных ресурсов в структуре системы, локализации отказов модулей и связей, а также перераспределения множества выполняемых подпрограмм в поле работоспособных модулей в этих работах рассмотрены недостаточно.
Отказы процессорных модулей и связей ОМС приводят к появлению неоднородностей в ее физической структуре. В результате уменьшается количество возможных маршрутов передачи данных, при этом возрастает их средняя длина, что усложняет маршрутизацию данных между работоспособными модулями после реконфигурации системы. Как следствие, увеличивается среднее время межпроцессорного обмена и снижается реальная производительность системы. Одним из путей преодоления указанных послед-

1.4 Анализ путей аппаратной реализации размещения подпрограмм в мультикомпыотерных системах
Как было показано выше, рассмотренные известные методы и алгоритмы требуют больших затрат времени на выполнение перебора значительного числа вариантов размещения. В мультикомпыотерных критических системах вариант размещения должен быть получен за минимальное время. В случае отказа одного из процессоров системы и оперативной замене его резервным, как было показано в п.п. 1.1.-1.3 изменяется топология, что приводит к необходимости оперативного переразмещения ранее назначенных подпрограмм. Реализация этого вопроса программным способом приводит к высоким временным издержкам и вызывает необходимость привлечения аппаратных средств. Рассмотрим варианты реализации этой задачи с помощью аппаратных средств.
В [41] предложено устройство поиска нижней оценки размещения в матричных системах по критерию минимизации интенсивности взаимодействия процессов и данных.
Идея предложенного критерия заключается в следующем. Согласно теории метода ветвей и границ при поиске нижней оценке дуги исходного графа задачи назначаются на процессорные модули так, что дуги с наибольшей интенсивностью (объемах информации, количества передаваемых данных и т.д.) назначаются па соседние процессоры не обращая внимания при этом на ограничения, которые накладывает исходных граф задачи.
Это предположение было решено использовать при проектировании устройства, представленное на рисунке 1.13.