1 Харьковский национальный экономический университет, Харьков, Украина Институт сцинтилляционных материалов НАН Украины, Харьков, Украина НТК «Институт монокристаллов» НАН Украины, Харьков, Украина С.В. Минухин, С.В. Баранник, С.В. Знахур, Р.И. Зубатюк ЭФФЕКТИВНЫЙ АЛГОРИТМ ПЛАНИРОВАНИЯ ЗАДАНИЙ НА ГЕТЕРОГЕННЫХ КЛАСТЕРАХ НА ОСНОВЕ MAUI

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

3 Resource Broker Grid Resource Manager Information Services Monitoring Services Security Services Ядро Грид-сервисов Core Grid Infrastructure Services User/ Application Higher-Level Services Грид - промежуточное ПО PBSLSF… Resource Управление локальными ресурсами Общая схема управления ресурсами в Грид

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

5 Основные идеи подхода 1.Минимизировать на каждом этапе планирования количество задействованных (выделенных для планирования) ресурсов. 2.Максимизация (упаковка) количества заданий, которые планируются для их выполнения на ресурсах. 3.Разработка механизма планирования на основе компонент, позволяющих повышать эффективность результатов планирования на основе выбора значений соответствующих параметров.

6 Модель предлагаемой системы планирования

7 Математическая модель планирования на основе задачи о наименьшем покрытии (ЗНП)

8 Матрица соответствия задания/ресурсы для приведения к ЗНП

9 Определение единицы измерения времени имитационной модели В качестве единицы времени планирования и расчетов в программе используется внутреннее время имитационной модели ­1 такт, которое соответствует времени решения одного задания, имеющего сложность MI на ресурсе, производительность которого MIPS. Для вычислительных экспериментов, в которых учитывалась сложность заданий, задания малой сложности (трудоемкости) определялись в интервале от 10 до 300 тактов; средней – от 300 до тактов; высокой – от и выше тактов.

10 Состав и описание характеристик системы планирования

11 Интерфейс программы для имитационного моделирования работы планировщика

12 Метрики производительности системы

13 Зависимость времени выполнения заданий от количества заданий для методов MC и FCFS при экспоненциальном законе интенсивности входного потока заданий

14 Зависимость времени выполнения от количества заданий для методов MC и FCFS при равномерном законе интенсивности входного потока заданий

15 Зависимость коэффициента использования от количества заданий для методов MC и FCFS при экспоненциальном законе интенсивности входного потока заданий

16 Влияние периодичности планирования на коэффициент использования ресурсов (для заданий низкой сложности ) Влияние периодичности планирования на коэффициент использования ресурсов (для заданий низкой сложности ) Результаты эксперимента для заданий низкой сложности

17 Влияние интенсивности поступления сложных заданий (30000 тактов) на коэффициент использования ресурсов (при нормальном законе распределения заданий) для различных периодичностей планирования Влияние интенсивности поступления сложных заданий (30000 тактов) на коэффициент использования ресурсов (при нормальном законе распределения заданий) для различных периодичностей планирования Результаты эксперимента для заданий высокой сложности

18 Правила настройки параметров характеристик системы планирования для повышения эффективности работы системы Условия Система правил для получения лучших результатов показателей эффективности Интенсивность заданий Сложность заданияРазмер пула Размер пакета заданий Периодичность планирования Низкая (среднее количество посту­ пающих в систему заданий меньше количества ресурсов) Средняя сложность задания больше средней производительности ресурса Больше максимального значения интенсивности заданий Для нормального закона (M+3σ) Размер равен средней интенсивности. Определяется средним временем освобождения ресурса Средняя сложность задания меньше средней производительности ресурса Больше максимального значения интенсивности Размер равен средней интенсивности Определяется средним временем освобождения ресурса Высокая (среднее количество поступающих в систему заданий больше количества ресурсов) Средняя сложность задания больше средней производительности ресурса Больше среднего значения интенсивности Размер больше 1 Определяется минимальным временем освобождения ресурса Средняя сложность задания меньше средней производительности ресурса Больше среднего значения интенсивности Размер больше 1Планирование осуществляется на каждом такте работы системы

19 Исследование практической реализации метода в планировщике MAUI Реализация алгоритма MC и его адаптация к существующей системе планирования на кластерах осуществляется на базе планировщика MAUI, программная реализация которого имеет открытый код. Исходный код планировщика MAUI реализован на языке С. Структурно адаптация включает в себя процедуры: 1. Настройка конфигурации MAUI для работы с несколькими очередями и определение политик для работы с разными типами пользовательских заданий. 2. Создание пула заданий для алгоритма MC. 3. Заполнение пула теми заданиями, которые определены политиками и результатом работы MAUI. 4. Мониторинг свободных ресурсов и формирование массива соответствия заданий-ресурсов. 5. Запуск собственного алгоритма планирования МС. 6. Назначения заданий на ресурсы и передача указателей (назначений) локальному планировщику TORQUE. Функции заполнения пула пакетом заданий и вызов алгоритма реализуется в файле «*\maui-3-*-*\src\moab\MSched.c». Для включения и адаптации алгоритма МС в данном файле дополнительно созданы функции создания пула и вызов алгоритма планирования MC

20 Описание структуры типов данных, которыми описываются задания и ресурсы в MAUI Структура (тип данных), описывающая mcres_t *Ares (Доступные ресурсы) typedef struct { int Procs; int Mem; /* (in MB) */ int Swap; /* (in MB) */ int Disk; /* (in MB) */ mnuml_t PSlot[MAX_MCLASS]; mnuml_t GRes[MAX_MGRES]; } mcres_t;

21 Фрагмент функции «MLocalQueueScheduleIJobs» для вызова функции, реализующей метод планирования МС. Функция находиться в файле maui-3.3.*\src\moab\MLocal.c #include "../../contrib/sched/MC_Alg.c" Подключение файла с алгоритмом МС int MLocalQueueScheduleIJobs( int *Q, mpar_t *P) { mjob_t *J; int jindex; if ((Q == NULL) || (P == NULL)) { return(FAILURE); } /* NOTE: insert call to scheduling algorithm here */ for (jindex = 0;Q[jindex] != -1;jindex++) { J = MJob[Q[jindex]]; /* Вызываем функцию формирования пакета. В параметры передаем переменную работы(массив работ, елементы которого задачи в очереди) и вторым параметром передаем поле ARes к которому получаем доступ из набора параметров (mpar_t *P)*/ MJobMass(J,P->ARes); /* Call MC Algorithm */ DBG(7,fSCHED) DPrint("INFO: checking job '%s'\n", J->Name); } /* END for (jindex) */ return(SUCCESS); } /* END MLocalQueueScheduleIJobs() */

22 Функция заполнения пула пакетом заданий и вызов алгоритма в файле «*\maui-3-*-*\src\moab\MSched.c». int MJobMass( mjob_t *J, /* job ID */ mcres_t *ARes) /* available resources */ { mjob_t PackJ[5]; /* package including five jobs*/ mcres_t PackR[5]; /* package including five resources */ int i = 0; /* переменная для движения по массивам */ int j = 0; /* переменная для обнуления массивов */ for(i; i < 5; i++) { if(PackJ[i] == NULL && PackR[i] == NULL) /* check for completeness of the package ; / { PackJ[i] = *J; /* push jobs in first column of package */ PackR[i] = *ARes; /* push available resources in second column of package */ } else /* if package fully */ { MShed_MC(*PackJ,*ParkR); /* send package to our algorithm */ for(j; j

23Выводы 1. Предложенный подход и модель позволяют достичь лучших показателей производительности работы системы, а именно, уменьшения времени выполнения всех заданий и увеличения среднего коэффициента использования ресурсов за счет максимальной загрузки ресурсов на каждом шаге планирования и выбора периодичности планирования в условиях динамического изменения сложности и интенсивности потока заданий. Выбор периодичности планирования позволяет уменьшить время простоя ресурсов. 2. Эффективность предложенного механизма планирования зависит от взаимодействия и настройки компонент: пула, блока планирования, пакетов заданий на ресурсы. Оптимально выбранная периодичность планирования позволяет уменьшить влияние роста интенсивности и сложности поступающих заданий – уменьшить время выполнения всех заданий. 3.Сравнительный анализ использования алгоритма МС и FCFS показывает выигрыш эффективности (выполнения всех заданий) до 60 % в тех случаях, когда пул планировщика выбирается больше величины средней интенсивности заданий, пакет заданий выбирается большим 1, а периодичность – меньше среднего времени освобождения ресурсов. 4.Разработан вариант подключения алгоритма МС в модуль планирования (MLocal.c) планировщика MAUI.

24 Литература 1.Петренко А.І. Компютерне моделювання грід-систем // Электроника и связь 5 Тематический выпуск «Электроника и нанотехнологии», – С. 40–48. 2.Грушин Д.А., Поспелов А.И. Система моделирования Grid: реализация и возможности применения. [Электронный ресурс] – Режим доступа 3.Кореньков В.В., Нечаевский А.В. Пакеты моделирования DataGrid // Электронный журнал «Системный анализ в науке и образовании». – – 1. – С. 21. – Листровой С.В. Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин. // Электронное моделирование. – – Т. 34. – 1. – С. 29 – Grid Resource Management: State of the Art and Future Trends. - // Jarek Nabrzyski, Jennifer M. Schopf, Jan Weglarz. - Kluwer Publishing, p. 6.PBS, PBS pro: LSF, CSF: 8.Globus: 9.Global Grid Forum: SRM area.