Модель и методы выбора неотчуждаемых ресурсов для планирования заданий в распределенных вычислительных средах Емельянов, Дмитрий Михайлович

Введение к работе

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

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

Среди различных подходов к планированию в РВС можно выявить следующие тенденции. Одна из них основывается на использовании доступных ресурсов и планировании вычислений на уровне приложений (проекты X-Com, AppLeS, APST, Legion, DRM, Condor-G, Nimrod/G и другие). Другая тенденция связана с образованием виртуальных организаций (ВО) пользователей и предполагает планирование на уровне потоков заданий (комплексы GrAS, GrADS, GARA, Ursala, Silver). В рамках первого из направлений системы планирования и управления ресурсами являются хорошо масштабируемыми и адаптируемыми к особенностям пользовательских приложений. Однако использование независимыми пользователями различных критериев для оптимизации планов выполнения своих заданий (в условиях возможной конкуренции с другими заданиями) может ухудшать такие интегральные характеристики РВС, как время выполнения пакета заданий и уровень загрузки ресурсов. Образование ВО естественным образом ограничивает масштабируемость систем управления заданиями. Однако наличие определенных правил предоставления и потребления ресурсов, основанных, в частности, на экономических моделях, позволяет повысить эффективность планирования и разделения ресурсов на уровне потоков заданий, контроль над которыми осуществляют различного рода метапланировщики, менеджеры, грид- диспетчеры и т.п. Как правило, в основе планирования лежит циклическая иерархическая схема.

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

Таким образом, актуальной является проблема разработки модели и методов управления выполнением независимых заданий в рамках ВО на основе

экономических принципов.

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

Объектом исследования является управление выполнением потоков заданий на неотчуждаемых ресурсах РВС.

Предмет исследования - модель и методы повышения эффективности использования ресурсов и планирования параллельных заданий в виртуальной организации РВС на основе экономических принципов.

Цель диссертации - разработка модели и методов выбора неотчуждаемых ресурсов на основе развития и обобщения иерархической циклической схемы управления потоками заданий в виртуальной организации РВС.

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

1. анализ и исследование циклической схемы управления потоками заданий и ресурсами виртуальной организации РВС с неотчуждаемыми ресурсами, основанной на иерархической модели диспетчеризации;

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

3. разработка алгоритмов согласованного выделения ресурсов для параллельных заданий (коаллокации) и повышения эффективности их выполнения в соответствии с заданным критерием;

4. разработка имитационной модели выбора ресурсов в пределах виртуальной организации;

5. экспериментальное исследование модели и алгоритмов предоставления и потребления неотчуждаемых ресурсов ВО.

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

Научная новизна работы состоит в следующем:

5. 1. исследован комплексный подход к процессу планирования в рамках циклической схемы, позволяющий реализовать разделение ресурсов с учетом интересов пользователей, администраторов ВО и собственников ресурсов;

   2. предложена общая схема коаллокации ресурсов для параллельного задания согласно ресурсному запросу и заданному пользователем критерию эффективности;

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

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

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

   Положения, выносимые на защиту:

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

         2. метод планирования потоков заданий с разбиением на подпакеты на основе циклической модели управления заданиями;

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

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

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

         Достоверность научных результатов подтверждается соответствием теоретических выкладок и результатов экспериментов, а также сопоставлением полученных результатов с результатами, приведёнными в научной литературе.

         Реализация результатов. Работа выполнялась в рамках проектов Совета по грантам Президента Российской Федерации для поддержки ведущих научных школ (шифры НШ-7239.2010.9, НШ-316.2012.9); РФФИ (проекты 09-01-00095, 12-0700042); Минобрнауки России, ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы (государственные контракты № 16.740.11.0038, 16.740.11.0516).

         Материалы исследования внедрены в учебный процесс подготовки специалистов с высшим образованием по направлению «Информатика и вычислительная техника» специальности 230104.65 «Системы автоматизированного проектирования» по дисциплине «Технология проектирования информационных систем», специальности 230102 «Автоматизированные системы обработки информации и управления» по дисциплине «Информационные технологии» в МИЭМ НИУ ВШЭ, а также были использованы при подготовке курса «Вычислительные системы» кафедры ВТ НИУ «МЭИ».

         Апробация работы и публикации. Основные положения и научные результаты докладывались и обсуждались на международных научных конференциях Parallel Computing Technologies PaCT-2009, 31 августа-4 сентября 2009 г., г. Новосибирск; «Научный сервис в сети Интернет: экзафлопсное будущее», 19-24 сентября 2011 г., г. Новороссийск; «Научный сервис в сети Интернет: поиск новых решений», 17-22 сентября 2012 г., г. Новороссийск; ACS/IEEE International Conference on Computer Systems and Applications, Тунис, Хаммамет; International Conference on Computational Science ICCS 2011, Сингапур, 1-3 июня 2011 г.; ICCS 2012, Омаха, США, 2-6 июня 2012 г.; 7-й международной конференции Dependability and Complex Systems DepCoS-RELCOMEX, Брунов - Вроцлав, Польша, 24-30 июня 2012; «Распределенные вычисления и грид-технологии в науке и образовании», г. Дубна, 16-21 июля 2012г.

         Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 28 печатных работах: 27 статьях, включая 3 статьи в изданиях из перечня ВАК, и одну главу в монографии (в соавторстве).

         Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения и списка использованной литературы. Текст работы изложен на 170 страницах. Список литературы включает 76 наименований. В работе содержится 33 рисунка и 33 таблицы.

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

         

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

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

         Математические модели и методы оказания ориентационной поддержки экономического выбора индивидуума в сфере личного потребления продуктов питанияБондаренко, Юлия Валентиновна

         Математические модели задач вычислительной электродинамики неоднородных средБыков, Алексей Александрович

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

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

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

         МЕТОДЫ, МОДЕЛИ И ТЕХНИЧЕСКИЕ РЕШЕНИЯ ПО ПОВЫШЕНИЮ ЭФФЕКТИВНОСТИ ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСОВ И КОМПЬЮТЕРНЫХ СЕТЕЙШабанов, Александр Петрович

         Математические модели, методы и базовые средства для перспективных плановых расчетов в сфере обслуживания населенияАлексеев, Анатолий Арсеньевич

         Исследование и разработка моделей, методов и алгоритмов экстенсионального подхода в компьютерной психодиагностикеДюк, Вячеслав Анатольевич