Введение к работе
Актуальность темы исследования. Решение многих важных практических задач требует использования многопроцессорных систем. Важность вопросов оптимизации в них вычислительных процессов, в том числе организации параллельных вычислений на кластерах, сегодня не вызывает сомнений. В июле 2009 года на заседания Совета безопасности России, президент РФ Д.А.Медведев говорил о важности кластеров для страны. При организации параллельных вычислений возникает проблема обеспечения ускорения решения задач. Общая производительность вычислений на кластере во многом зависит от применяемых способов управления очередью заданий, поступающих на кластер. Использование эффективных алгоритмов управления очередью -это универсальный способ повышения скорости решения задачи, повышения производительности параллельных вычислений. В настоящее время к разработке новых моделей, методов, алгоритмов и технологий управления очередями проявляется очень большой интерес со стороны научного исследования. Повышению эффективности управления очередями в параллельных вычислениях посвящены работы таких ученых, как: Kelly P.P., Limic V., Chen L.,Norros I. Bhaskar T.R, Jeffrey M.K, Hai Jin,Daniel A, Wenbin Jiang, Jia-Shiang , Baras, John S, Коваленко B.H., Корягин Д.А., Семячкин Д.А и других. Описанная проблема достаточно хорошо исследована в зарубежной литературе. К сожалению, на русском языке редко встречаются даже переводы зарубежных работ по данной тематике. В известных и широко применяемых алгоритмов существует ряд недостатков, Как правило, планировщики рассматривают задания из очереди по порядку, одно за другим. Однако, порядок, в котором задания планируются, может вести к фрагментации ресурсов (большая часть процессоров занято мелкими заданиями); по этой причине, даже если задание имеет самый высокий приоритет, необходимый ему объём ресурсов может никогда не образоваться и задание может никогда не стартовать — возникнет эффект «зависания» (starvation). Основная проблема методов планирования, основанных на разделении времени процессоров, при обслуживании параллельных заданий, состоит в том, что процессы одного задания могут быть прерваны и перезапущены в разные моменты времени, что приводит к снижению общей эффективности использования ресурсов, так как некоторое время тратится на ожидание одним процессом перезапуска другого. Эти обстоятельства делают актуальным теоретическое и практическое исследование применения алгоритмов управления очередями заданий при организации параллельных вычислений для повышения эффективности производительности параллельных вычислений, обеспечения ускорения решения задач в кластерных системах.
Цель диссертационной работы состоит в исследовании и разработке алгоритмов управления очередями при организации параллельных вычислений для повышения эффективности производительности вычислений, обеспечения ускорения решения задач в кластерных системах.
Основные задачи исследования. Для достижения данной цели необходимо решить следующие задачи:
Проанализировать существующие методы и алгоритмы управления очередями и пакетами, обеспечивающими параллельные вычисления.
Разработать модель на основе семантической сети и стохастический подход к оценке управления очередями в кластерных системах, с использованием Марковских процессов.
Разработать алгоритмы управления очередями заданий при параллельных вычислениях на кластерных системах.
Разработать параллельный алгоритм нахождения минимального остовного дерева и параллельный алгоритм решения транспортной задачи для проверки предложенных алгоритмов управления очередями заданий в кластерных системах.
Разработать комплекс программ для экспериментального исследования и проверки эффективности предложенных модели и алгоритмов управления очередями заданий на кластерных системах.
Объект и предмет исследования. Объектом исследований являются высокопроизводительные вычислительные системы.
Предметом исследования являются модели, методы и алгоритмы управления очередями заданий в кластерных системах.
Методы исследования. Для решения поставленных в диссертации задач использовались теория вычислительных систем, системного анализа, вероятности, массового обслуживания, математического программирования, графов и параллельного программирования.
Научная новизна результатов исследования, заключается в следующем:
Разработан стохастический подход к оценке управления очередями заданий с использованием Марковских процессов, и модель кластера MPI/MPICHNEW на основе семантической сети для управления очередями заданий, при организации параллельных вычислений на кластере. Предложенный подход и модель отличаются от известных, таких, как методы разделения ресурсов (FCFS, Backfill, SJF) и методы разделения времени (Gang scheduling), по строению и структуре, тем, что они могут устранять проблемы старвации (зависания) заданий, требующих большого количества ресурсов, определять параметры планировщика Maui и обеспечивать эффективное использование свободных вычислительных ядер всех узлов кластера, среднего времени, которое задание проводит в очереди, для различного числа узлов.
Разработаны алгоритмы обслуживания очередями заданий, при параллельных вычислениях, в кластерных вычислительных системах: алгоритм распределения ресурсов между процессами и алгоритм управления порядком запуска заданий , которые отличаются от известных по структуре построения и тем, что они позволяют значительно снизить ресурсы в ходе работы планировщика за счёт применения специального алгоритма планирования запуска заданий и снизить расход процессорного времени при преждевременной остановке заданий за счёт постоянной корректировки резервирования ресурсов и др.
Разработаны параллельные алгоритмы и теоретические оценки оптимального количества вычислительных узлов кластерных систем, общего времени выполнения параллельных алгоритмов решения транспортной задачи, вычислительной сложности параллельного алгоритма, нахождения минимального остовного дерева на кластере для проверки предложенных алгоритмов управления очередями заданий, которые отличаются от известных алгоритмов по строению и структуре тем, что они обладают более глубоким распараллеливанием и эффективностью в кластерных системах.
Разработан комплекс программ для исследования и проверки эффективности предложенных модели и алгоритмов управления очередями заданий на кластерных системах, отличающийся от известных кластерных пакетов по интегрированию и схемы работы и позволяющий обеспечить более глубокие параллельные вычисления в многопроцессорных, кластерных системах.
На защиту выносятся следующие основные результаты и положения:
Стохастический подход к оценке управления очередями заданий с использованием Марковских процессов для параллельных вычислений на кластере, и модель кластера MPI/MPICH_NEW на основе семантической сети для управления очередями заданий в планировщике Maui, что позволяет определять параметры планировщика Maui, обеспечивать эффективное использование свободных вычислительных ядер всех узлов кластера, повысить эффективность производительности параллельных вычислений и уменьшить время ожидания заданий в очереди.
Алгоритмы обслуживания очередями в кластерных вычислительных системах: алгоритм распределения ресурсов между процессами, алгоритм управления порядком запуска заданий. Это позволяет в совокупности получить более высокие показатели эффективности параллельных вычислений, обеспечить ускорение решения задач в кластерных системах и, уменьшить время ожидания заданий в очереди.
Параллельные алгоритмы для нахождения опорного плана в транспортной задаче на основе метода Фогеля; нахождения оптимального решения транспортной задачи на основе метода потенциала; нахождения минимального остовного дерева, на основе метода Борувки для выполнения в кластерных системах, которые позволяют увеличить производительность и в том числе при использовании нескольких тысяч процессоров, повысить эффективность параллельных вычислений и, обеспечить ускорение решения задач в кластерных системах.
Теоретические оценки оптимального количества вычислительных узлов кластерных систем, общего времени выполнения параллельных алгоритмов решения транспортной задачи на кластере, а также, теоретическая оценка вычислительной сложности параллельного алгоритма нахождения минимального остовного дерева, на основе метода Борувки, которые повышают эффек-
тивность параллельных вычислений, обеспечивают ускорение решения задач в кластерных системах.
5. Комплекс программ для исследования и проверки эффективности предложенных модели и алгоритмов управления очередями заданий на кластерных системах, позволяющий обеспечить более глубокие параллельные вычисления в многопроцессорных, кластерных системах.
Практическая значимость диссертационной работы заключается в следующем:
Использование стохастического подхода, модели и алгоритмов управления очередями в кластерном пакете MPI/MPICH путем расширения его до MPI/ MPICHNEW, т. е создание программной модели кластера, на основе VmWare (виртуальных машин), пакета Torque и пакета MPI/MPICH (использовался OpenSourse) с целью повышения эффективности производительности параллельных вычислений.
Зарегистрированное в Реестре программ для ЭВМ, Федеральной службы по интеллектуальной собственности, патентам и товарным знакам (Роспатент) от 29 июля 2011 г. " Программное средство для исследования алгоритмов управления очередями заданий в кластерных системах", повышает эффективность производительности параллельных вычислений и уменьшает время ожидания заданий в очереди. Свидетельство о государственной регистрации программы для ЭВМ №2011615951.
С целью проверки эффективности модели и алгоритмов управления очередями заданий в кластерном пакете MPI/MPICH, разработаны две параллельные программы и зарегистрированы в Реестре программ для ЭВМ, Федеральной службы по интеллектуальной собственности, патентам и товарным знакам (Роспатент) от 27 июля 2011г.:
«Параллельная программа для решения транспортной задачи в кластерных системах». Свидетельство о государственной регистрации программы для ЭВМ № 2011615890;
«Параллельная программа для нахождения минимального
остовного дерева в кластерных системах». Свидетельство о государственной регистрации программы для ЭВМ № 2011615889
4. Комплекс программ реализован на языке C++ под Windows ХР на ЭВМ типа ШМ PC.
Эксперименты проводились на кластере следующей конфигурации:
8 вычислительных узлов (Intel Pentium 4 2,4 ГГц);
управляющий узел (Intel Pentium 4 2,4 ГГц).
узлы объединены между собой сетью Infiniband (пропускная способность 4 Гбит/с). Отличительная особенность разработанного программного комплекса - это эффективное
использование многоядерной вычислительной системы, обеспечивающей более высокие параллельные вычисления в многопроцессорных, кластерных системах, что позволило сократить время ожидания заданий в очереди.
Достоверность научных положений, выводов, строгих математических алгоритмов и практических рекомендаций, полученных в диссертации, подтверждается корректным обоснованием постановок задач, а также результатами экспериментов по использованию предложенных в диссертации модели и алгоритмов управления очередями заданий, параллельных алгоритмов, при этом, разработанных программных средств, для проверки работы, зарегистрированных в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам.
Реализация и внедрение результатов работы. Полученные результаты использованы при выполнении фундаментальной госбюджетной научно-исследовательской работы тематического плана 2011 года ИЭиМ Донского государственного технического университета (ДГТУ) на кафедре «Вычислительные системы и информационная безопасность» («ВС и ИБ») по теме: «Разработка и исследование моделей, методов и алгоритмов решения нелинейных транспортных задач, основанных на эволюционном моделировании», выполняемой по тематическому плану Минобрнауки. Материалы диссертации использованы в научно-исследовательской работе, выполняемой по гранту № 10-01-00481-а на тему «Развитие теории и практики применения интеллектуальных методов в распределительных системах управления базами данных », финансируемой Российским фондом фундаментальных исследований (1.01.2010-31.12.11). Кроме того, результаты выполненной работы, используются в учебном процессе на кафедре «ВС и БС» при чтении лекций и проведении практических занятий по дисциплинам «Автоматизированное управление», «Многопроцессорные системы и параллельное программирование», «Высокопроизводительные вычислительные систе-
мы», «Основы оптимального управления», «Системное программирование», «Вычислительные машины, системы и сети».
Акты об использовании прилагаются. Апробация диссертационной работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международном конгрессе: " Интеллектуальные системы "(AIS-11) и " Интеллектуальные САПР "(CAD-2011)(r. Геленджик,2011г.) и на Международных научно-технических конференциях: XXIII Международная научная конференция " Математические методы в технике и технологиях " (ММТТ-23), (СГТУ, г. Саратов,2010г.); XXIV Международная научная конференция " Математические методы в технике и технологиях " (ММТТ-24)(г. Киев,2011г.); IX Международная научная техническая конференция "Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства" (ИнЭРТ), (ДГТУ, г.Ростов н/Д,2010г.); XVI Международная открытая научная конференция " Современные проблемы информатизации ",(СПИ-АС)( ВГТУ, г.Воронеж , 2011г.); Российская Академия Естествознания. Международная научная конференция " Новые информационные технологии и системы ",(г. Паттайя - Таиланд , 20 Юг.);VI Международный научно-методический симпозиум "Современные проблемы многоуровневого образования" , (г. Дивноморск - 2011).
Публикации. По материалам диссертации опубликовано 20 печатных работ, в том числе 8 статей в изданиях, входящих в «Перечень ведущих научных журналов и изданиях, выпускаемых в Российской Федерации», утвержденных ВАК РФ. По теме исследования получено 3 свидетельства об официальной регистрации программ для ЭВМ.
Структура и объём работы. Рукопись диссертационной работы состоит из введения, четырех глав, заключения, библиографического списка из 136 наименований, изложенных на 163 страницах машинописного текста и 10 приложений, содержит 52 рисунок, 12 таблиц.
Похожие диссертации на Разработка и исследование алгоритмов управления очередями заданий при организации параллельных вычислений в кластерных вычислительных системах
