Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Вычислительные машины, системы и сети

Диссертационная работа:

Целищев, Алексей Сергеевич. Модели и методы планирования сложноструктурированных заданий в распределённых вычислениях : диссертация ... кандидата технических наук : 05.13.15 / Целищев Алексей Сергеевич; [Место защиты: Нац. исслед. ун-т МЭИ].- Москва, 2011.- 238 с.: ил. РГБ ОД, 61 12-5/497

смотреть введение
Введение к работе:

Актуальность темы исследования

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

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

Требования пользователей к минимизации времени выполнения и/или стоимости выполнения вычислений;

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

Требования организаторов Грид-системы к различным интегральным характеристикам работы виртуальной организации (например, к пропускной способности всей системы, либо к совокупной прибыли).

Существующие планировщики в общем случае позволяют соблюдать интересы лишь одной группы участников вычислений, а обеспечение оптимальной загрузки вычислительных ресурсов слабо коррелирует с задачами, решаемыми планировщиками Грид-вычислений.

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

Объектом исследований в представленной диссертации являются распределенные вычислительные среды, а предметом исследований -модели и методы планирования распределённых вычислений.

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

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

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

Исследованы существующие методы и алгоритмы планирования вычислений в распределенных средах;

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

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

Проведены эксперименты, позволившие дополнить и улучшить первоначально выбранную схему планирования;

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

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

Методы исследования

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

Научная новизна диссертационных исследований определяется следующими результатами, которые выносятся на защиту:

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

Иерархическая структура планирования и вычислительной среды;

Совмещение методов планирования уровня потоков заданий и методов планирования уровня приложений;

Использование экономических критериев и модели планирования;

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

Предложенная модель впервые позволяет одновременно соблюдать интересы пользователей Грид-систем (крайние сроки выполнения заданий), администраторов вычислительных узлов (эффективная загрузка) и организаторов Грид-систем (интегральные характеристики потока заданий) и совмещать преимущества различных методик планирования: 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 страницы приложений с таблицами, рисунками и листингами.


© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net