Методы и алгоритмы организации функционирования распределенных вычислительных систем в мультипрограммных режимах

• Автор: Седельников, Максим Сергеевич
• Шифр специальности: 05.13.15
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Новосибирск
• Количество страниц: 150 с. : ил.

СОДЕРЖАНИЕ

СПИСОК СОКРАЩЕНИЙ

ВВЕДЕНИЕ.

Глава 1. РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ С ПРОГРАММИРУЕМОЙ СТРУКТУРОЙ

1.1. Понятие о вычислительных системах с программируемой, структурой

1.1.1. Модель коллектива вычислителей

1.1.2. Классификация ВС

1.1.3. Особенности ВС с программируемой структурой.

1.2. Основные режимы функционирования ВС

1.2.1. Монопрограммный режим .

1.2.2. Мультипрограммные режимы

1.3. Организация функционирования ВС в мультипрограммных режимах
1.3.1. Алгоритмы организации функционирования ВС .
1.3.2. Обзор средств поддержки мультипрограммных режимов
1.4. Выводы.
ГЛАВА 2. АЛГОРИТМЫ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ В РЕЖИМЕ ОБРАБОТКИ ЗАДАЧ НАБОРА
2.1. Оптимизация загрузки ВС при обработке задач набора.
2.2. Точный алгоритм распределения задач набора по элементарным машинам ВС
2.3. Эвристические алгоритмы распределения задач набора с фиксированными параметрами
2.3.1. Формирование пакетов задач
2.3.2. Минимизация времени решения задач набора на ВС
2.3.3. Параллельный алгоритм минимизации времени решения задач набора на ВС .
2.3.4. Минимизация штрафа за задержку решения задач набора на ВС.
2.3.5. Параллельный алгоритм минимизации штрафа за задержку решения задач набора на ВС .
2.4. Эвристические алгоритмы распределения набора задач с нефиксированными параметрами .
2.4.1. Минимизация времени решения задач набора на ВС
2.4.2. Минимизация штрафа за задержку решения задач набора на ВС7
2.5. Выводы.
ГЛАВА 3. АЛГОРИТМЫ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ В РЕЖИМЕ ОБСЛУЖИВАНИЯ ПОТОКА ЗАДАЧ7
3.1. Создание многопроцессорного расписания для потока параллельных задач
3.2. Децентрализованный алгоритм организации подсистем в ВС7
3.3. Децентрализованный алгоритм создания многопроцессорного расписания
3.4. Механизмы обеспечения отказоустойчивости при формировании подсистем в ВС
3.6. Выводы
ГЛАВА 4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ РАСПРЕДЕЛЕННОЙ МУЛЬТИКЛАСТЕРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ.
4.1. Архитектура мультикластерной ВС Центра Параллельных Вычислительных Технологий СибГУТИ .
4.2. Моделирование алгоритмов распределения параллельных задач набора с постоянными параметрами
4.3. Моделирование алгоритмов распределения набора параллельных задач с нефиксированными параметрами
4.4. Моделирование алгоритмов организации подсистем
и создания многопроцессорного расписания
4.5. Программное обеспечение распределенной мультикластерной ВС.
4.5.1. Состав программного обеспечения. Стандартные компоненты .
4.5.2. Программное обеспечение для поддержки мультипрограммных режимов
4.6. Выводы.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Алгоритмы обработки набора задач, позволяющие распределять параллельные задачи с нефиксированными параметрами . Децентрализованные алгоритмы организации подсистем в случае функционирования ВС в режиме обслуживания потоков параллельных задач, учитывающие возможные отказы ресурсов. Программные компоненты поддержки режимов параллельного мультипрограммирования для распределенных ВС, основанные на предложенных алгоритмах. Практическая ценность работы. Разработанные в диссертации модели, методы и алгоритмы представляют основу для эффективной организации функционирования большемасштабных распределенных ВС в мультипрограммных режимах. Оригинальные параллельные алгоритмы распределения задач набора по элементарным машинам ВС позволяют получать (суб)оптимальные значения целевых функций. Применение отказоустойчивого децентрализованного алгоритма создания подсистем из ЭМ в вычислительных системах позволяет организовать обслуживание интенсивных потоков параллельных задач в условиях их конкуренции за ресурсы. Разработан и внедрен в распределённую мультикластер-ную ВС программный комплекс для диспетчеризации параллельных задач и осуществления мониторинга технического состояния системы. Реализация и внедрение. Основные результаты диссертационной работы получены в рамках проекта № 3. Разработка методов анализа и алгоритмов организации функционирования большемасштабных распределенных вычислительных систем и создание аппаратно-программного инструментария параллельного моделирования» федеральной целевой программы К* фундаментальных исследований Президиума РАН. Диссертационная работа поддержана грантами Российского фонда фундаментальных исследований (РФФИ) № 9, 0, 1, 9. Кафедре вычислительных систем СибГУТИ по дисциплинам «Теория функционирования распределенных вычислительных систем», «Высокопроизводительные вычислительные системы» и «Сетевое программное обеспечение». Внедрение научных результатов диссертационной работы подтверждено соответствующими актами. Апробация работы. Международной научно-технической конференции "Информационные системы и технологии" ( г. Всероссийской научной конференции молодых ученых «Наука. Технологии. Инновации» (, гг. Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (, гг. Международной научно-технической конференции «Информатика и проблемы телекоммуникаций» ( г. International scientific conference «Automation, Control and Information Technology - Software Engineering» ( г. Всероссийской научной конференции «Методы и средства обработки информации» ( г. Москва). Публикации. По теме диссертации опубликовано работ, включая 3 статьи в центральных изданиях. Объем и структура диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы, изложенных на 3 страницах, а также приложений на 7 страницах. Содержание работы. В первой главе описывается архитектурная и программная организация современных распределённых ВС с программируемой структурой, описываются основные режимы их работы. Произведен краткий анализ известных методов организации функционирования распределенных ВС в мультипрограммных режимах, рассмотрены наиболее распространенные средства их поддержки. Во второй главе описаны модели функционирования распределённых ВС в режиме обработки наборов задач с постоянными и нефиксированными параметрами, предложены параллельные и последовательные алгоритмы минимизации времени решения и штрафа за задержку решения набора, проведен их анализ. В третьей главе предложен децентрализованный алгоритм создания подсистем из ЭМ в вычислительной системе и, разработанный на его основе, алгоритм составления многопроцессорного расписания для обслуживания потоков параллельных задач. Предложены и проанализированы средства обеспечения устойчивости данных методов к отказам ресурсов ВС. В четвертой главе описана архитектура распределенной мультикластерной ВС и реализованные на базе предложенных алгоритмов средства поддержки мультипрограммных режимов. Приведены результаты моделирования разработанных алгоритмов.