ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2012, № 1, с. 50-66
= КОМПЬЮТЕРНЫЕ МЕТОДЫ =
УДК 519.85
АНАЛИЗ УПРАВЛЕНИЯ СПЕЦИАЛЬНЫМИ ВЫЧИСЛИТЕЛЬНЫМИ ЗАДАНИЯМИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
© 2012 г. П. Е. Голосов, М. В. Козлов, Ю. Е. Малашенко, И. А. Назарова, А. Ф. Ронжин
Москва, Институт точной механики и вычислительной техники РАН, ВЦ РАН Поступила в редакцию 19.05.11 г., после доработки 16.06.11 г.
Рассматриваются различные стратегии управления заданиями в проблемно-ориентированном вычислительном комплексе. Реализуемые алгоритмические процедуры имеют переборный характер, требуют большого и, в общем случае, неизвестного объема вычислений. Проблема состоит в выборе динамических стратегий перераспределения ресурсов между задачами в условиях неопределенности. Анализ возможных диспетчерских правил проведен с использованием методов теории вероятностей и имитационного моделирования.
Введение. В последние годы существенно возрос интерес к созданию проблемно-ориентированных вычислительных и информационных систем, предназначенных для выполнения специальных работ. С появлением программно-аппаратных реализаций, позволяющих проводить распараллеливание вычислений [1—5], с новой остротой встала проблема отыскания эффективных способов распределения вычислительных ресурсов. Практическая задача управления процессом коллективного использования является ключевой для специализированных вычислительных систем, но зачастую решается без подробного исследования особенностей предлагаемых задач, временных рамок и содержательных целей, стоящих перед пользователями.
В данной работе проводится анализ характеристик различных диспетчерских стратегий управления прохождением специализированных заданий, которые по сути являются переборными, достаточно трудоемкими и одинаково важными для пользователей. Время выполнения отдельного задания заранее неизвестно и может быть очень велико, кроме того, соответствующая содержательная задача может не иметь решения [6]. В настоящей работе продолжены исследования, начатые авторами в [7].
1. Общее описание модели. Пользователи предъявляют диспетчеру специализированные задания для обработки вычислительной системой. Для формализации процесса анализа предположим, что процедура выполнения каждого задания может быть описана теоретико-вероятностной моделью — случайной выборкой без возвращений. В рамках стандартной модели представим каждое задание как урну с черными и белыми шарами, а процесс его выполнения — как извлечение шаров из урны и определение их цвета. Под специализированной элементарной вычислительной операцией (СЭВО) будем понимать вытягивание из урны одного шара и идентификацию его цвета.
Если урна содержит только белые шары, то процесс прекращается после извлечения последнего шара. В этом случае задание объявляется завершенным, а задача — не имеющей решения. Если в урне содержится хотя бы один черный шар, то после извлечения первого черного шара задача считается решенной и выполнение задания прекращается. Пусть известно Ж — общее число шаров в урне, а также вычислительная трудоемкость каждой СЭВО. Тогда можно определить максимальное время, требующееся для завершения задания, однако время решения реальной прикладной задачи остается неизвестным.
Рассмотрим модель проблемно-ориентированной поисковой вычислительной системы (далее М-система). Пусть М-система состоит из центрального управляющего вычислительного устройства (ЦУВУ) и набора единичных исполняющих вычислительных устройств (ЕИВУ). ЦУВУ координирует работу всех ЕИВУ, организует и контролирует процесс выполнения заданий, поступающих от пользователей. Каждое ЕИВУ будем рассматривать как некий абстрактный безотказный вычислитель со своим блоком управления и памятью, но с неизвестной архитектурой и конструктивными особенностями. Производительность ЕИВУ определим как число выполняемых СЭВО в единицу времени.
Считается, что М-система может одновременно обрабатывать как одно, так и несколько заданий на всех работоспособных в данный момент ЕИВУ. В свою очередь предполагается, что от-
дельное задание может быть разделено на подзадания, каждое из которых может выполняться независимо от других на отдельном ЕИВУ. При этом на каждом ЕИВУ в единицу времени может обрабатываться только одно задание или его часть.
Диспетчер осуществляет управление М-системой: анализирует поступившие задания и определяет порядок их выполнения; планирует распределение ресурсов; прогнозирует и контролирует ход вычислительного процесса; сообщает пользователю об окончании обслуживания. Рассмотрим ситуацию, когда задания поступают от пользователей одновременно в виде некоторого набора, без каких-либо признаков или отношений предшествования между ними. Считается, что каждое задание из набора может быть поставлено на обработку в любое определенное диспетчером время. Далее при обсуждении проблемы там, где это возможно, будут использованы классические обозначения теории расписаний [8], в некоторых случаях обобщенные или модифицированные.
2. Постановка задачи. Под М-системой М = {М0,Р1...,Р, ..., Рт} будем понимать набор ЕИВУ
РЬ1 = 1, т, каждое из которых выполняет определенное число СЭВО в единицу времени,
I = 1,т; и устройство ЦУВУ — М0, распределяющее задания для обработки по имеющимся ЕИВУ и осуществляющее контроль их выполнения. В рамках данной модели будем считать, что все ЕИВУ являются идентичными и имеют равную мощность V. Обозначим через V суммарную мощность М-системы
Пусть в момент времени г = 0 в вычислительную систему одновременно поступило множество J, состоящее из п заданий, т.е. / = {1Ъ ..., /у,... /п}, где у = 1,п,п > 2. Предполагается, что обработка ^ описывается случайной выборкой без возвращений из урны, содержащей wу, у = 1, п, шаров, т.е. «у- — максимально возможное число СЭВО, необходимое для выполнения J ..
Введем следующие обозначения: Ту — нормативное время выполненияу-го задания в монопольном режиме, т.е. при условии, что вся мощность М-системы была направлена на его обработку и был осуществлен полный перебор всех шаров урны, т.е. Ту = wу/V; X — абсолютная длительность — время, затраченное на решение у-й задачи в монопольном режиме, X — реализация случайной величины с неизвестной функцией распределения на [0; Ту ] для конкретного задания у и мощности V. Значение X становится известно только после завершения ^ и, поскольку для его выполнения был задействован весь имеющийся вычислительный ресурс, то X — минимальное время решения у-й задачи в данной М-системе; X — множество значений X для фиксированного набора I, т.е. X = {Ху},у = 1, п;
Будем считать, что процесс обслуживания может начаться с выполнения как одного, так и нескольких заданий из имеющегося множества J, а перераспределение ресурса производится только в момент завершения хотя бы одной задачи. Выполненное задание покидает систему.
Определение. Планом или стратегией выполнения заданий будем называть набор к(1, г) из п векторов г{ = (г1'\ ..., г(\I = 1,п, в котором г(),у = 1,п, — доля ресурса, выделенная у-й задаче при постановке набора J на обработку, а г(+1), у = 1, п, — доля ресурса, выделенная Jj после того, как завершено решение / задач, / = 1, п - 1.
Таким образом, стратегия п(/, г) однозначно определяет порядок выполнения заданий из множества J и долю г() общего ресурса V, т.е. число устройств ЕИВУ, выделенных для каждой у-й задачи в момент времени I. Обозначим через {Л время пребыванияу-й задачи в системе, т.е. длительность временного интервала от момента поступления задания в систему до момента, когда оно выполнено, согласно плану п(1, г), и покидает систему.
Сравнение различных стратегий п(/, г) проведем на основании анализа некоторых характеристик выполнения заданий, описанных ниже. Для их формализации рассмотрим конкретный набор заданий /. Предположим, что для всех Jj из набора I значения Xу, {Л и др. стали известны заранее, зафиксированы и остаются неизменными в серии последующих умозрительных экспериментов. Тогда для данного фиксированного набора I можно вычислить:
т
1 = 1
суммарное абсолютное время обработки всех заданий, которое не зависит от плана J, t)
n
S = E ч
j=i
среднее абсолютное время выполнения одного задания из набора J
s = ±S = 1 j^Xj.
n n
j = i
Рассмотрим следующие отношения:
S = 4j, j = П%, (2.1)
где t^k — время пребывания у-го задания из множества J в М-системе, согласно плану п, при условии, что J покинуло ее k-м по порядку.
Назовем безразмерную величину 2j показателем относительной длительности исполнения задания J для набора J, njk — коэффициентом относительного времени запаздывания для J для плана n(J, t). Действительно, численное значение 2j показывает, насколько время обработкиу-го
«-» т» П
задания отличается от средней длительности исполнения задания из J, а n jk — во сколько раз время пребывания в системеу-го задания при использовании плана n(J, t) оказывается больше его абсолютного времени решения, т.е. минимального времени, за которое его можно завершить в монопольном режиме при использовании всей имеющейся мощности М-системы.
Одним из простейших критериев оценки стратегий является математическое ожидание (среднее значение) среднего времени пребывания заданий в системе Tп = -(¿П + ... + tn). Цель данной работы — исследование того, как стратегия, выбранная диспетчером для выполнения заданий, т.е. распределение вычислительных ресурсов, влияет на значения vjk,T™ для конкретной заявки из фиксированного набора. Далее рассмотрим две простейшие стратегии — последовательную и параллельную. Их описание помещено ниже (в разд. 4). Сравнение будем производить на одних и тех же наборах заданий, при этом будем полагать, что все задания имеют одинаковый объем
wj = w и для всех J из набора J численные значения Xj, tj и др. известны заранее, например,
определены в ходе предварительных тестов. В частности, Xy для каждого j = 1, n, является конкретной реализацией случайной величины, имеющей неизвестную функцию распределения Fj(x) на отрезке [0; T].
Прежде чем перейти непосредственно к обсуждению стратегий выполнения заданий, кратко остановимся на те
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.