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

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

СОДЕРЖАНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ СОКРАЩЕНИЙ.

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

1.1. Методы распределения ресурсов при организации параллельных вычислений

1.1.1. Метод первый пришел, первый обслужен

1.1.2 Метод i обратного заполнения.

1.1.3. Метод краткосрочного планирования

1.2. Метод i комплектного планирования

1.3. Адаптивный метод управления потоком решения заданий в параллельной вычислительной среде

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

1.4.1. Традиционный алгоритм I.
1.4.2. Алгоритм ii i приоритетного обслуживания
1.4.3. Алгоритм взвешенных очередей
1.4.4. Алгоритм взвешенного справедливого обслуживания
1.5. Распределенные вычисления кластерные вычисления с использованием пакета параллельного программирования I.
1.6. Анализ существующих программных пакетов в кластерных системах
1.6.1. Кластеры высокой доступности.
1.6.2. Кластеры распределения нагрузки
1.6.3. Вычислительные кластеры
1.7. Анализ программног о обеспечения и средства его установки на кластер.
1.8. Кластерные системы управления пакетной обработкой СПО
1.9. Интегрированные программные средства для кластеров.
1 Проблемы параллельных вычислений, возникающие при использовании кластерного пакета II.
1 Выводы
ГЛАВА 2. РАЗРАБОТКА МОДЕЛИ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ НА ОСНОВЕ СЕМАНТИЧЕСКОЙ СЕТИ И СТОХАСТИЧЕСКИЙ ПОДХОД К ОЦЕНКЕ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ ЗАДАНИЙ В КЛАСТЕРНЫХ СИСТЕМАХ.
2.1. Модель кластера II на основе семантической сети в планировщике i
2.2. Управление очередями в кластерных системах
2.2.1.Выбор критериев оценки алгоритмов управления очередями.
2.2.2.Схема организации вычислений.
2.2.3.Аппаратное обеспечение
2.2.4.Менеджер ресурсов
2.2.5. Планировщик задач к менеджерам ресурсов, работающий по методу i.
2.2.6.Конкретизация положений теории очередей для кластерной системы
2.3. Основные положения теории Марковских процессов и стохастический подход к оценке управления очередями заданий.
2.4. Выводы
ГАЛАВА 3. РАЗРАБОТКА АЛГОРИТМОВ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ ЗАДАНИЙ И ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ ПРОВЕРКИ ЭФФЕКТИВНОС ТИ ПРЕДЛОЖЕННЫХ АЛГОРИТМОВ НА КЛАСТЕРНЫХ СИСТЕМАХ.
3.1. Алгоритмы управления очередями заданий для параллельных вычислений .
3.1.1. Алгоритм распределения ресурсов между процессами
3.1.2 Алгоритм управления запуском заданий для кластерных систем.
3.2. I Остановка задачи нахождением минимального остовного дерева для проверки предложенных алгоритмов управления очередями заданий на кластере.
3.2.1.Анализ и сравнительные характеристики алгоритмов нахождения минимального остовного дерева
3.2.2. Параллельный алгоритм нахождения минимального остовного дерева на
основе метода Борувки
3.2.3.Оценка вычислительной сложности параллельного алгоритма Борувки.
З.З.Алгоритмы нахождения опорного плана и оптимального решения транспортной задачи для проверки предложенных алгоритмов управления очередями заданий на кластере
3.3.1.Последовательные алгоритмы решения транспортной задачи методом Фог еля и методом потенциалов
3.3.2. Параллельный алгоритм нахождения опорного плана на основе метода Фогеля.
3.3.3. Параллельный алгоритм нахождения оптимального решения на основе метода потенциалов
3.3.4.Теоретическая оценка определения оптимального количества узлов кластерных систем и общего времени выполнения параллельного алгоритма нахождения опорного плана транспортной задачи.
3.4. Выводы.
ГЛАВА 4. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТАЛЬНОГО ИССЛЕДОВАНИЯ РАЗРАБОТАННЫХ МОДЕЛИ И АЛГОРИТМОВ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ ЗАДАНИЙ В КЛАСЕРНЫХ СИСТЕМАХ
4.1. Цель и средства экспериментальных исследований.
4.2.Экспериментальная оценка производительности предложенной модели управления очередями заданий
4.2.1. Использование модели в планировщике Маш для кластерного пакета МР1МР1СН.
4.2.2. Испытание и результаты экспериментальной проверки эффективности предложенной модели на основе транспортной задачи
4.3. Испытания и результаты экспериментальной проверки эффективности предложенных алгоритмов на основе нахождения минимального остовного дерева.
4.3.1. Алгоритм управления на основе параллельного алгоритма нахождения минимального остовного дерева по методу Борувки
4.3.2. Сравнительная характеристика экспериментальной и теоретической оценки эффективности параллельных алгоритмов нахождения минимального остовного дерева.
4.4. Испытания и результаты экспериментальной проверки эффективности предложенных алгоритмов управления на основе параллельного алгоритма решения транспортной задачи
4.4.1. Экспериментальная проверка предложенных алгоритмов управления очередями заданий
4.4.2. Сравнение экспериментального и теоретического времени работы параллельного алгоритма нахождения опорного плана транспортной задачи на основе метода Фогеля.
4.4.3. Экспериментальная проверка эффективности параллельного алгоритма нахождения оптимального решения транспортной задачи на основе метода потенциалов
4.5. Интерфейс программных стендов и работа с ними.
4.6.Вывод ы
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЯ
Приложение 1. Реализация описанных алгоритмов управления заданиями.
Приложение 1.1. Функция обработки фоновых заданий
Приложение 1.2. Функция, разметающая задачу в очереди
Приложение 1.3. Отображение информации о состоянии заданий в очереди
Приложение 2. Акты использования
риложение 3. Свидетельства о государственной регистрации программы для
риложение 3.1. Свидетельство о государственной регистрации программы для ЭВМ Программное средство для исследования алгоритмов
управления очередями заданий в кластерных системах.
Приложение 3.2. Свидетельство о государственной рег ис грации программы для ЭВМ Параллельная программа для решения транспортной
задачи на кластерных системах
Приложение 3.3. Свидетельство о государственной регистрации прог раммы для ЭВМ Параллельная программа для нахождения
минимального остовггого дерева на кластерных системах
Приложение 4. Сертификаты от российской академии естествознания.
ВВЕДЕНИЕ
Актуальность


Федеральной службе по интеллектуальной собственности, патентам и товарным знакам. Реализация и внедрение результатов работы. Полученные результаты использованы при выполнении фундаментальной госбюджетной научноисследовательской работы тематического плана года ИЭиМ Донского государственного технического университета ДГТУ на кафедре Вычислительные системы и информационная безопасность ВС и ИБ по теме Разработка и исследование моделей, методов и алгоритмов решения нелинейных транспортных задач, основанных на эволюционном моделировании, выполняемой по тематическому плану Минобрнауки. Материалы диссертации использованы в научноисследовательской работе, выполняемой по гранту 1 а на тему Развитие теории и практики применения интеллектуальных методов в распределительных системах управления базами данных , финансируемой Российским фондом фундаментальных исследований 1. Кроме того, результаты выполненной работы, используются в учебном процессе на кафедре ВС и БС при чтении лекций и проведении практических занятий но дисциплинам Автоматизированное управление. Многопроцессорные системы и параллельное программирование, Высокопроизводительные вычислительные системы,Основы оптимальною управления,Системное программирование, Вычислительные машины, системы и сети. Акты об использовании прилагаются. Апробация диссертационной работы. Интеллектуальные САПР СЛОг. Геленджик, г. Математические методы в технике и технологиях ММТТ, СГТУ, г. Саратов,г. XXIV Международная научная конференция Математические методы в технике и технологиях ММТТг. Киев, г. IX Международная научная техническая конференция Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства ИнЭРТ, ДГТУ, г. Ростов нД,г. XVI Международная открытая научная конференция Современные проблемы информатизации ,СПИАС ВГТУ, г. Воронеж , г. Российская Академия Естествознания. Международная научная конференция Новые информационные технологии и системы ,г. Паттайя Таиланд , г. Международный научнометодический симпозиум Современные проблемы многоуровневою образования , г. Дивноморск . Публикации. По материалам диссертации опубликовано печатных работ, в том числе 8 статей в изданиях, входящих в Перечень ведущих научных журналов и изданиях, выпускаемых в Российской Федерации, утвержденных ВАК РФ. По теме исследования получено 3 свидетельства об официальной регистрации программ для ЭВМ. Структура и объм работы. Рукопись диссертационной работы состоит из введения, четырех глав, заключения, библиографического списка из 6 наименований, изложенных на 3 страницах машинописного текста и приложений, содержит рисунок, таблиц. Во введении обоснована актуальность темы, определены цель и задачи диссертационной работы, объект и предмет исследования, указаны методы исследования, научная новизна, основные положения, выносимые на защиту, приведены сведения о практической значимости, об использовании результатов работы, апробации диссертационной работы, дано краткое содержание основных разделов диссертации. Отмечены достоинство, недостатки и перспективы развития этих алгоритмов. По результатам проведенного анализа обосновывается необходимость разработки модели и алгоритмов, применяющихся в кластерных системах, для повышения производительности параллельных вычислений, обеспечения ускорения решения задач в кластерных системах и уменьшения времени ожиданий заданий в очереди. Вторая глава посвящена разработке модели управления очередями на основе семантической сети и стохастического похода к оценке управления очередями заданий для параллельных вычислений на кластерах, с использованием Марковских процессов, с целью повышения производительности параллельных вычислений, обеспечения ускорения решения задач в кластерных системах и уменьшения времени ожидания заданий в очереди. В этой главе показано, как теоретические положения теории массового обслуживания ТМО теории очередей и семантическая сеть применяются к практическим задачам управления очередями заданий в кластерной системе.