Повышение эффективности кластерных систем обработки информации при решении оптимизационных задач

Актуальность проблемы. Системный анализ это динамично развивающийся подход к исследованию сложных объектов и явлений, широко применяемый в различных областях науки. Стремительный переход вычислительных систем на новую параллельную архитектуру порождает проблему их эффективного использования. Приложения, созданные для одноядерных процессоров, могут использовать при работе на современном многоядерном процессоре только одно ядро, т. е. они используют ресурсы системы крайне неэффективно. А если речь идет о работе на кластерных многопроцессорных системах, то положение будет еще сложнее. Выход состоит в том, чтобы создавать программные комплексы, которые учитывают архитектурные особенности кластерных вычислителей, разрабатывать новые и совершенствовать существующие методы и алгоритмы анализа и обработки информации. Такой метод системного анализа как декомпозиция, позволяет рассматривать кластерный вычислитель как совокупность подсистем и оптимизировать работу приложений исходя из их характеристик. Этот подход сможет обеспечить повышение эффективности работы современных кластерных систем при решении актуальных ресурсоемких практических задач в различных областях. Многокритериальные задачи синтеза структуры и определения характеристик систем управления для сложных технических систем, часто также решаются методами оптимизации. С ростом размерности вычислительная сложность алгоритмов оптимизации существенно возрастает, что делает актуальной их реализацию на кластерных системах.

Одним из примеров задач многокритериальной оптимизации может служить задача составления расписания занятий в ВУЗе, которая относится к классу вычислительно сложных. Как правило, она решается вручную человеком, имеющим большой опыт работы в конкретном университете. При составлении расписания занятий необходимо учитывать достаточно большое количество критериев, назначаемая степень важности которых оказывает существенное влияние, как на процесс, так и на качество составляемого расписания. Процесс составления расписания занятий в ручном режиме занимает несколько недель. Безусловно, полностью повторить работу человеческого мозга при решении многокритериальных задач пока невозможно. Однако это не означает, что автоматические решения, будут уступать им по качеству. Вычислительные мощности современных компьютеров позволяют за небольшое время синтезировать множество вариантов расписаний, опирающихся на разные показатели.

Актуальность работы определяется выбором в качестве объекта исследований методов и алгоритмов решения задач многокритериальной оптимизации, эффективно использующих вычислительные ресурсы кластерных систем. В качестве примера оптимизационной задачи рассматривается задача составления расписания, которая существенно осложняется включением в новые образовательные стандарты принципа вариативности.

Цель работы и задачи исследования. Работа посвящена исследованию методов повышения эффективности кластерных систем при решении оптимизационных задач за счет адаптации алгоритмов к особенностям их архитектуры.

Для достижения поставленной цели в работе решаются следующие основные задачи:

1. Анализ переносимости методов решения задач многокритериальной оптимизации на параллельную платформу.

2. Постановка и формализация задачи составления расписания занятий в ВУЗе.

3. Разработка критериальных оценок качества решения задачи составления расписания.

4. Разработка алгоритма решения задачи составления расписания занятий.

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

6. Разработка метода распределения нагрузки для алгоритма оптимизации, повышающего эффективность кластерных вычислителей с распределенной памятью.

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

8. Экспериментальное исследование эффективности предложенного алгоритма.

Объект и предмет исследования. Объектом исследования являются методы и алгоритмы решения оптимизационных задач.

Предметом исследования являются параллельные алгоритмы многокритериальной оптимизации, повышающие эффективность кластерных вычислителей с распределенной памятью.

Методы исследования. При решении указанных задач были использованы положения теории принятия решений, теории множеств, методы многокритериальной оптимизации и языки параллельного программирования.

Научная новизна. Основной результат диссертационной работы состоит в теоретической разработке и практической реализации нового подхода к решению задач многокритериальной оптимизации, адаптированного для параллельных вычислительных систем с распределенной памятью, позволяющего повысить эффективность вычислений за счет минимизации коммуникационных накладных расходов, который был опробован на примере решения задачи составления расписания занятий. Положения, выносимые на защиту.

1. Результаты анализа переносимости алгоритмов решения задачи составления расписания занятий на параллельную платформу.

2. Итерационный алгоритм решения задачи составления расписания. 1.

3. Метод распределения нагрузки между узлами кластерной вычислительной системы для алгоритма решения задачи составления расписания, учитывающий архитектурные особенности параллельных вычислительных систем с распределенной памятью, обеспечивающий динамическую балансировку загрузки узлов кластера и повышающий эффективность их использования.

4. Параллельная программа автоматического решения задачи составления расписания для многопроцессорных вычислительных систем с распределенной памятью.

5. Результаты практического исследования эффективности алгоритма и программы.

Практическая значимость. Предложенный в диссертации подход к построению параллельных программ для решения оптимизационных задач на кластерных системах, обеспечивает повышение их эффективности и может быть использован для широкого круга приложений — логистика, экономическое планирование, управление персоналом и ряд других.

Внедрение результатов. Параллельная программа, разработанная в ходе выполнения диссертации, внедрена в отделе автоматизированных информационных систем МИЭТ. В компании «Разум — технологии» предложенный в диссертации подход к решению оптимизационных задач используется для активного управления трафиком в узлах сети.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика — 2007, 2008», «Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем — 2007», IV Международной научно-практической конференции «Современные информационные технологии и ИТ-образование» — 2009, Международной научно-практической конференции ГГЕ08'2010 «Информационные технологии. Электронные приборы и системы».

Публикации. По материалам диссертации опубликовано пять тезисов докладов и две статьи, одна из которых в журнале, рекомендуемом ВАК. Получены два свидетельства РФ на программу для ЭВМ.

4.4. Выводы.

1. Проведенные эксперименты подтвердили, что параллельная программа позволяет решать оптимизационную задачу составления расписания занятий в автоматическом режиме. Разработанные алгоритмы и найденные коэффициенты важности критериев и параметров позволяют получить полностью корректное расписание со 100% расстановкой занятий в автоматическом режиме.

2. Использование параллельных алгоритмов дает возможность варьировать коэффициенты важности в уравнении свертки и генерировать различные решения, отвечающие предпочтениям Л ПР.

3. Эффективность кластера при решении оптимизационной задачи зависит от числа используемых узлов и находится в интервале от 0,94 — 0,23. Ее снижение при увеличении числа узлов определяется латентностью системы коммутации.

4. Загруженность каждого ядра при выполнении счетных операций составляет 96%, что говорит об эффективном использовании вычислительной мощности узла и правильной стратегии балансировки.

Заключение

.

Краткая характеристика выполненных исследований:

1. Проведен анализ существующих методов решения задач многокритериальной оптимизации и обоснована необходимость их переноса на параллельную платформу.

2. Формализована задача составления расписания занятий в ВУЗе, как задача многокритериальной оптимизации.

3. Разработан последовательный алгоритм составления расписания занятий в ВУЗе, основанный на минимизации целевой функции, вычисленной по методу линейной свертки.

4. Разработан параллельный алгоритм решения задачи составления расписания занятий, учитывающий архитектурные особенности кластерных систем обработки информации, обеспечивающий 90% загрузку узлов кластера и ее динамическую балансировку.

5. На языке С++ с использованием библиотеки MPI разработан программный модуль автоматического составления расписания занятий в ВУЗе, адаптированный для кластерных вычислительных систем с распределенной памятью и обеспечивающий 100% расстановку занятий в автоматическом режиме. На указанный программный модуль получено свидетельство об официальной регистрации.

6. Исследования предложенного алгоритма и разработанной на его основе программы, проведенные на вычислительном кластере МИЭТ-2008, подтвердили, что эффективность использования узлов кластера в процессе решения оптимизационной задачи достигает величины 90−96%.