BC/NW 2010; №2 (17):5.1

 

 

СИСТЕМА ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ ПЛАНИРОВАНИЯ ПОТОКОВ НЕЗАВИСИМЫХ ЗАДАНИЙ  В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ

Бобченков А.В., Топорков В.В., Целищев А.С.

(Московский энергетический институт (технический университет), Россия)

 

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

 

Разработанная система позволяет моделировать инфраструктуру и поведение слоя управления в распределенных вычислительных средах (middleware). Центральным элементом модели является метапланировщик, функция которого заключается в распределении входящих независимых потоков заданий от внешних пользователей и создании расписания для имеющихся разнородных неотчуждаемых вычислительных ресурсов или планировщиков низшего уровня. Подобные системы (resource brokers) в настоящий момент широко используются в Grid-системах распределенных вычислений, примеры существующих систем описаны в [1-6]. Преимуществом разрабатываемой авторами модели является баланс загрузки ресурсов и оптимизация составления расписаний на основе экономических моделей (Commodity Market). Подход, использованный при разработке модели, развивает идеи, лежащие в основе метапланировщика Nimrod-G [6]. Предложенные в рамках модели алгоритмы планирования позволяют учитывать экономические интересы всех взаимодействующих сторон: пользователей виртуальной организации, владельцев используемых ресурсов, администраторов виртуальной организации.

 

Система полностью реализована на платформе Java без привлечения сторонних библиотек. Архитектура системы показана на рис. 1. Система состоит из 5 компонентов:

•    компонент генерации запросов (Request Generator),

•    компонент генерации среды (Environment Generator),

•    компонент отбора слотов (Slot Processor),

•    компонент оптимального поиска набора слотов (Alternative Solver),

•    компонент метапланировщика (Metascheduler).

 

Рис. 1. Архитектура системы имитационного моделирования

 

Компонент генерации запросов (Request Generator)

Основная функция компонента – генерация потоков независимых заданий, оформленных по принципу ресурсного запроса.

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

·        ID запроса (id),

·        строковое имя запроса (name),

·        максимальная цена слота (priceMax),

·        минимальная скорость ресурса (resourceSpeed),

·        необходимое количество ресурсов (resourceNeed),

·        время, на которое должны быть зарезервированы ресурсы (time),

·        время поступления запроса в систему (timeStamp),

·        пользователь, от имени которого поступил запрос (user).

Для удобства тестирования и моделирования различных начальных условий компонент Request Generator может формировать ресурсные запросы, отдельные параметры которых варьируются по заданному закону распределения. Предусмотрено два режима: равномерное и нормальное распределение.

Выходным результатом компонента служит пакет ресурсных запросов, передаваемый на вход метапланировщика.

 

Компонент генерации среды (Environment Generator)

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

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

Выходным результатом работы компонента Environment Generator служит объект VOEnvironment, содержащий всю необходимую информацию о вычислительной среде.

 

Компонент отбора слотов (Slot Processor)

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

Слотом в используемой модели называется промежуток времени, ассоциируемый с конкретной ресурсной линией, который можно использовать в планировании расписаний и во время которого ресурсная линия считается свободной. Собственных параметра у слота два: его начальный момент и длина, стоимость слота вычисляется с учетом схемы ценообразования, связанной с виртуальной средой. Конечная точность операций со временем в реальных системах моделируется путем округления длины слотов до ближайшего целого в большую сторону (с запасом).

На вход компонента приходит список ResourceRequests от компонента генерации запросов и объект VOEnvironment от компонента генерации среды. Кроме того, данный компонент использует два собственных параметра (SlotProcessorSettings):

·        время начала цикла планирования (CycleStart),

·        длина цикла планирования (CycleLength).

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

·        найденное «окно», содержащее список слотов,

·        время начала окна, совпадающее со временем начала самого раннего из слотов «окна»,

·        динамически рассчитываемая стоимость «окна».

Полное описание алгоритма сортировки и отбора слотов, предложенного в данной модели, выходит за рамки данного доклада.

 

Компонент оптимального поиска набора слотов (Alternative Solver)

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

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

В результате работы алгоритма на выходе составляется список условно-оптимальных планов, которые могут быть дополнительно обработаны в случае использования многокритериальной модели поиска. Тогда на их основе строится таблица, содержащая значения критериев из вектора критериев <C, D, T, I>, а также значение рассчитываемой скалярной функции полезности. Элементы вектора для каждого условно-оптимального плана si рассчитываются следующим образом:

 

 

,

где ci – вырученный бюджет, ti – общая загрузка слотов, B* и T* - соответственно, ограничения на бюджет и время в данном цикле планирования.

 

Компонент метапланировщика (Metascheduler)

Функции данного компонента:

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

·        поддержка различных режимов моделирования: распределение одного пакета в один цикл, автоматическое увеличение длины цикла для дораспределения, постепенное увеличение длины цикла.

В перспективе планируется реализация механизмов, отслеживающих характеристики и результаты распределения и варьирующих настройки служебных компонентов (Slot Processor, Alternative Solver) либо схему ценообразования для моделирования оптимизации доходов виртуальной организации и собственников ресурса. Кроме того, планируется расширение модели с включением N параллельных потоков заданий и возможностью переключать запросы между потоками.

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

Авторы выражают благодарность за содействие выполнению данной работы Совету по грантам Президента Российской Федерации для поддержки ведущих научных школ (НШ-7239.2010.9),  РФФИ (проект
№ 09-01-00095), а также Министерству образования и науки (проект 2.1.2/6718 и государственный контракт № П2227).

Литература

1.      Adaptive computing on the Grid using AppLeS Berman, F.; Wolski, R.; Casanova, H.; Cirne, W.; Dail, H.; Faerman, M.; Figueira, S.; Hayes, J.; Obertelli, G.; Schopf, J.; Shao, G.; Smallen, S.; Spring, N.; Su, A.; Zagorodnov, D. Parallel and Distributed Systems, IEEE Transactions on Volume 14, Issue 4, April 2003 Page(s): 369 – 382 Digital Object Identifier 10.1109/TPDS.2003.1195409.

2.      Practical Divisible Load Scheduling on Grid Platforms with APST-DV van der Raadt, K.; Yang Yang; Casanova, H. Parallel and Distributed Processing Symposium, 2005. Proceedings. 19th IEEE International Volume , Issue , 04-08 April 2005 Page(s): 29b - 29b Digital Object Identifier 10.1109/IPDPS.2005.351.

3.      Michael J. Lewis, Adam J. Ferrari, Marty A. Humphrey, John F. Karpovich, Mark M. Morgan, Anand Natrajan, Anh Nguyen-Tuong, Glenn S. Wasson and Andrew S. Grimshaw, "Support for Extensibility and Site Autonomy in the Legion Grid System Object Model," Journal of Parallel and Distributed Computing, Volume 63, Number 5, pp. 525-38, May 2003.

4.      Digital right management based on Grid Computing architecture (GC-DRM) Min-Jen Tsai; Yuan-Fu Luo Computer Supported Cooperative Work in Design, 2008. CSCWD 2008. 12th International Conference on Volume , Issue , 16-18 April 2008 Page(s):494 – 500 Digital Object Identifier 10.1109/CSCWD.2008.4537028.

5.     http://www.cs.wisc.edu/condor/condorg/

6.     http://www.csse.monash.edu.au/~davida/nimrod/nimrodg.htm