Максимова Е.Н. Мамойленко С.Н. Ефимов А.В.
Параллельный генетический алгоритм формирования расписаний решения масштабируемых задач на распределенных вычислительных системах
Докладчик: Максимова Е.Н.
Распределённые вычислительные системы (ВС) относятся к перспективным средствами обработки информации. Одной из актуальных проблем организации функционирования ВС в мультипрограммных режимах является формирование расписаний решения пользовательских задач. Описывая задачу, пользователь задает допустимые значения как минимум для двух её параметров: ранга (т.е. количества ЭМ, необходимых для её решения) и требуемого (максимально допустимого) времени её решения. Если для задачи задается больше, чем одно допустимое значение для её параметров, то такую задачу называют масштабируемой (moldable). Исследования пользовательских запросов показывают, что свойством масштабируемости обладают более 80\% задач. Пользователь также может указать предпочтение выбора допустимых значений параметров задачи. Эти предпочтения определяются природой решаемой задачи или иными соображениями пользователя. Кроме этого, могут задаваться и другие параметры (например, штраф за задержку решения задачи, дополнительные характеристики ресурсов ВС и т.п.).
В данной работе представлен параллельный генетический алгоритм формирования расписаний решения масштабируемых задач на распределённых ВС, учитывающий пожелания пользователей на выбор значений параметров. В основу алгоритма положен методы формирования укрупненных задач (пакетов) и перетасовки генов (Exon shuffling). Представлены результаты моделирования алгоритма, которое проводилось с использованием ресурсов пространственно распределенной мультикластерной ВС Центра параллельных вычислительных технологий Сибирсого государственного университета телекоммуникаций и информатики и Института физики полупроводником им. А.В. Ржанова СО РАН.
Работа выполнена в рамках междисциплинарного проекта № 113 СО РАН, при поддержке РФФИ (гранты № 08-07-00022, 09-07-00095) и Совета по грантам Президента РФ (ведущая научная школа НШ 5176.2010.9
К списку докладов
