Еналиев А.М.
Институт проблем управления РАН
Одной из важнейших задач эффективного функционирования РВС является поиск оптимального способа распределения задач по процессорам (в математической модели – по обслуживающим устройствам - ОП) РВС. Сложность задачи состоит в том, что искомый алгоритм должен обеспечивать наиболее полную загрузку всех компьютеров РВС и в то же время - уменьшение накладных расходов на пересылки данных между процессорами.
Для исследования математической модели (на основе аппарата СМО) выполнения комплекса взаимосвязанных работ (КВР) в РВС с динамическим распределением работ по процессорам системы, был разработан специальный (и не имеющий прототипа) алгоритм динамического распределения работ КВР со случайными временами выполнения работ КВР, в основу которого положены следующие правила, используемые непосредственно в процессе выполнения КВР: 1). После окончания выполнения любой работы, все ее преемники помечаются как “ожидающие распределения” и остаются на том же ОП, где завершилась работа-предшественник, после чего запускается процедура распределения работ. 2). Каждая работа ai подлежит распределению только тогда, когда распределены по ОП все её предшественники. 3). Если при распределении работы ai оказалось, что необходимо пересылать данные на какой-либо другой ОП, и при этом устройство пересылки данных занято обслуживанием другой заявки, то результат распределения работы ai аннулируется, и эта работа остаётся в режиме ожидания распределения. 4). Если у работы ai имеется несколько предшественников, то эта работа распределяется на ОП только тогда, когда выполнились все её предшественники, кроме одного, а именно - на тот ОП, на который был распределён последний предшественник. 5). Если работу ai не удалось распределить в данном цикле распределения, то эта работа остаётся ожидать распределения на том же ОП, где выполняется работа-предшественник (по п. 1).
Основой метода является правило выбора “свободного” ОП для работы ai (хотя, может быть, на этот ОП были распределены и другие работы). Это правило выбора определяется, главным образом, соотношением среднего времени выполнения работы на ОП (процессоре РВС) ко времени пересылки данных от работы-предшественника к работе-приемнику на другой ОП. Для простоты эксперимента было использовано правило выбора по наименьшему количеству работ во входном буфере ОП - с учетом количества работ, распределенных на выполнение на этом ОП, и количества пересылок на этот ОП.
Предложенное правило продемонстрировало преимущество динамического распределения работ по отношению к статическому распределению при условиях, когда время выполнения работы каждой работы является случайной величиной.
