Информационная система "Конференции"

Тезисы докладов

Информационные технологии

Эффективность использования вычислительных систем высокой производительности, таких как гетерогенные вычислительные системы (к которым можно отнести GRID), существенно зависит от методов планирования заданий. Планирование ― процесс распределения вычислительной работы между процессорами с целью уменьшения общего времени их выполнения. Частью указанного процесса является решение задачи составления расписаний, которое в общем случае является NP-полным. Для составления расписаний нашел применение генетический алгоритм (ГА).

При адаптации ГА к указанной предметной области возникает ряд проблем, одной из которых является учет ограничений на составление расписаний. К таким ограничениям относятся: запрашиваемые пользователями на этапе постановки заданий в очередь списки необходимых для запуска заданий ресурсов (размер оперативной и виртуальной памяти, свободное пространство на жестких дисках, архитектура процессора, тип операционной системы и др.), группировка процессов одного задания (если задание того требует) в пределах одной вычислительной группы (вычислительного кластера, SMP-системы), указанные пользователем конкретные узлы для расчета, эксклюзивное владение вычислительными ресурсами и др. Классические варианты генетических операторов (ГО) не могут учитывать данные ограничения. Таким образом, в процессе эволюции, расписания быстро становятся некорректными. Для сохранения корректности расписаний предлагается модифицировать ГО с использованием маски ресурсов (МР). МР — дополнительная структура данных, представляющая собой вектор идентификаторов процессоров GRID, доступных на данный момент для размещения задания. Заполняется МР отдельно для каждого задания в каждой конкретной ситуации. В общем случае, для изменения тем или иным ГО хромосомы, необходимо сначала выбрать для гена процессор на МР этого гена, таким образом заранее исключая неподходящие процессоры из участия в процессе применения ГО. Например, в процессе генерирования начальной популяции при выборе позиции гена в хромосоме достаточно выбрать идентификатор процессора на МР, составленной с учетом вышеописанных ограничений. Для оператора мутации обмена генов необходимо после выбора первого гена составить для него МР и, перебирая процессы, сопоставленные с процессорами из данной маски, строить для них отдельные МР. Если идентификатор процессора первого гена присутствует во второй МР, то можно производить обмен данных генов местами. Аналогичные алгоритмы использования МР применяются и в других подобных ситуациях.

Адаптация ГА для учета ограничений на расписания является частью работы по исследованию ГА составления расписаний для GRID.

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

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:48:14)