Введение к работе
Актуальность темы исследования
Вопросы, связанные с распределением трудоемких вычислений, поднимаются уже не один десяток лет. Современные требования и научный прогресс влияют как на объёмы обрабатываемых данных, так и на способы их обработки. Будь-то петабайты информации, получаемые физиками на Большом Адронном Коллайдере или огромное число комбинаций при поиске лекарства от тяжелой болезни - современные реалии таковы, что не позволяют осуществить выполнение поставленных задач в рамках одной, сколь угодно большой или влиятельной организации, и требуют совершенно иного подхода к их решению.
Распределённые вычислительные среды позволяют существенно увеличить эффективность использования конечных вычислительных ресурсов, а также обеспечивают необходимые вычислительные мощности для решения трудоёмких задач. Одной из самых актуальных задач для Грид-систем, являющихся одним из видов распределённых вычислительных сред, является задача эффективного планирования вычислений, сводящаяся к обеспечению оптимального баланса загрузки вычислительных ресурсов, а также соблюдению интересов различных участников вычислений. Известные на сегодняшний день методы и алгоритмы, использующиеся в системах управления ресурсами Грид и в планировщиках, не позволяют координировать и одновременно соблюдать следующие требования, возникающие в процессе работы виртуальных организаций:
Требования пользователей к минимизации времени выполнения и/или стоимости выполнения вычислений;
Требования администраторов и владельцев вычислительных ресурсов к загрузке подконтрольных узлов и к получаемой от участия в Грид-системе прибыли;
Требования организаторов Грид-системы к различным интегральным характеристикам работы виртуальной организации (например, к пропускной способности всей системы, либо к совокупной прибыли).
Существующие планировщики в общем случае позволяют соблюдать интересы лишь одной группы участников вычислений, а обеспечение оптимальной загрузки вычислительных ресурсов слабо коррелирует с задачами, решаемыми планировщиками Грид-вычислений.
С учётом подобной ситуации актуальность разработки и исследования методов планирования, позволяющих решить описанные проблемы, чрезвычайно высока.
Объектом исследований в представленной диссертации являются распределенные вычислительные среды, а предметом исследований -модели и методы планирования распределённых вычислений.
Основной целью диссертационного исследования является разработка и исследование модели планирования вычислений в распределенных системах на уровне приложений и её адаптация к предлагаемой концепции
комплексного планирования, совмещающей оптимизацию планирования в масштабе всей виртуальной организации и планирования в масштабе конечного задания.
Для достижения поставленной цели в диссертации решены следующие основные задачи:
Исследованы существующие методы и алгоритмы планирования вычислений в распределенных средах;
Предложена концепция решения задачи оптимального планирования вычислений на уровне приложений и потоков заданий;
Разработаны модели и алгоритмы, реализующие представленную концепцию в части уровня приложений, предложен оригинальный обобщённый метод критических работ;
Проведены эксперименты, позволившие дополнить и улучшить первоначально выбранную схему планирования;
Реализована система имитационного моделирования процессов планирования на уровне приложений, использующая оригинальный обобщённый метод критических работ. Проведены исследования, результаты которых подтвердили возможность составления оптимальных или близких к оптимальным планов по предложенным алгоритмам для широкого спектра сценариев распределённых вычислений;
Проанализированы полученные результаты и приведена оценка возможности применения разработанных методов и алгоритмов на уровне потоков заданий, их преимущества и эффективность.
Методы исследования
При решении задач диссертационного исследования использовались методы составления расписаний и планирования, методы дискретного анализа, теории графов, теории множеств, системного анализа и исследования операций. При реализации среды имитационного моделирования были применены методы компьютерной графики, объектно-ориентированного и динамического программирования. Для исследования разработанной модели планирования заданий сложной структуры использовалось имитационное моделирование на ЭВМ, а также методы статистического анализа.
Научная новизна диссертационных исследований определяется следующими результатами, которые выносятся на защиту:
Разработана модель организации планирования распределённых вычислений, отличие которой от имеющихся заключается в одновременном наличии следующих особенностей:
Иерархическая структура планирования и вычислительной среды;
Совмещение методов планирования уровня потоков заданий и методов планирования уровня приложений;
Использование экономических критериев и модели планирования;
Распределение ресурсов в два этапа: выбор домена вычислительных узлов и оптимизация выполнения задания с учётом его структуры.
Предложенная модель впервые позволяет одновременно соблюдать интересы пользователей Грид-систем (крайние сроки выполнения заданий), администраторов вычислительных узлов (эффективная загрузка) и организаторов Грид-систем (интегральные характеристики потока заданий) и совмещать преимущества различных методик планирования: Budget- и Deadline-constrained (ограничения на бюджет и на время) планирования, а также Best-effort планирования.
Разработаны и реализованы методы и алгоритмы планирования для менеджеров заданий, позволяющие реализовать предложенную иерархическую модель в части уровня приложений:
Разработаны алгоритмы генерации заданий в виде информационных графов, а также алгоритмы анализа их структуры;
Разработан обобщённый метод критических работ, основанный на переходе от концепции типов ресурсов к детерминированному домену узлов, предложен механизм обратной связи с узлами;
Разработан ряд эвристик для разрешения коллизий между фрагментами заданий, для осуществления динамического выбора ресурсов в модифицированном методе критических работ и др.
С помощью разработанной среды имитационного моделирования был проведён экспериментальный анализ предложенных методов при работе с широким спектром заданий, который показал их эффективность в получении планов, оптимальных по заданным критериям, отвечающих требованиям к крайним срокам выполнения и выделенному бюджету, а также позволяющих эффективно использовать вычислительные ресурсы.
Достоверность полученных результатов, положений и выводов наряду с эмпирическими рекомендациями, отражёнными в диссертационном исследовании, подтверждается совпадением данных, полученных при имитационном моделировании, с теоретическими выкладками, а также ссылками на авторитетные источники. Практическая значимость
Разработанная при проведении исследований среда имитационного
моделирования позволяет моделировать планирование
сложноструктурированного задания, представленного информационным графом, по заданной стратегии планирования и при заданных ограничениях. Допускается задание множества параметров как самого задания (структуры информационных связей составляющих его подзадач, требований компонентов задания к вычислительным ресурсам и т.п.), так и различных критериев и стратегий планирования, определяющих необходимую балансировку загрузки вычислительных ресурсов и обеспечивающих соблюдение интересов различных участников распределённых вычислений.
На основе среды имитационного моделирования были разработаны программные модули, оптимизированные с точки зрения производительности, которые возможно положить в основу реализации реальной системы управления ресурсами Грид-системы. Программное
обеспечение зарегистрировано в государственном реестре программ для ЭВМ: свидетельство №2011611541 от 10.03.2011 г.
Результаты исследования были использованы при подготовке лекционных курсов «Вычислительная техника» на кафедре ВТ НИУ ФГБОУ ВПО «НИУ МЭИ», а также лекционных курсов кафедры АИЛУ МИЭМ (ТУ), о чём имеются соответствующие акты.
На различных этапах проведения исследований работа автора была поддержана грантами РФФИ (№ 06-01-00027, № 09-01-00095), а также Советом по грантам Президента Российской Федерации для поддержки ведущих научных школ (грант НШ-7239.2010.9), Министерством образования и науки (проекты 2.1.2/6718; 2.1.2/13283 в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» и государственные контракты федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы № П2227, 16.740.11.0038) и Комитетом поддержки развития отечественных автоматизированных систем управления имени академика Семенихина (именная премия первой степени). Апробация и публикация результатов работы
Теоретические и практические результаты диссертационных исследований были представлены и обсуждались в рамках многочисленных российских и зарубежных научных конференций в период с 2007 по 2011 гг.
По теме диссертации опубликовано 27 печатных работ, из них 7 в зарубежных изданиях (в том числе глава в монографии в соавторстве) и одна работа в издании, рекомендуемом ВАК. Структура и объем диссертации
Диссертация состоит из введения, четырёх глав, заключения, списка источников из 130 наименований и шести приложений. Работа содержит 176 страниц машинописного текста содержательной части с таблицами и рисунками, 54 страницы приложений с таблицами, рисунками и листингами.
