Основные допущения при распределении ресурсов и постановка задачи

Положим, – совокупность частично упорядоченных задач, выполнение которых должно быть закончено до наступления крайнего временного срока . Отношение частичного порядка на задается с помощью ориентированного бесконтурного графа (рис. 1), множество вершин которого представляет задачи обработки и доступа к памяти, а множество дуг – информационные и логические связи (условные ветвления процессов вычислений). Переход от исходной модели программы, содержащей циклы, к эквивалентной ей ацикличной модели может быть осуществлен с применением формального аппарата М-сетей, адекватно описывающего распределенные программы с буферным обменом сообщениями (см. Топорков В.В. Модели распределенных вычислений. М.: Физматлит, 2004. – 320 с.). Далее будем считать, что ресурсы вычислительной системы включают в себя процессоры и коммуникационную среду, хотя при необходимости в могут быть выделены операции обращения к памяти и предусмотрены соответствующие ресурсы.

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

Для каждой из задач обработки , , имеется априорная оценка длительности ее выполнения на процессоре типа (табл. 1). Дополнительно может задаваться объем вычислений , приведенный к конкретному типу или всем типам доступных процессоров. Априорные оценки , могут быть получены в результате статико-динамического анализа комплекса задач, решаемых системой реального времени (см. Топорков В.В. Модели распределенных вычислений. М.: Физматлит, 2004. – 320 с.). Задача монопольно занимает соответствующий экземпляр процессора -го типа в течение всего времени , отведенного для ее выполнения, причем в общем случае и . Через обозначим параметр, соответствующий назначению -й задачи на процессор того или иного типа. Будем полагать, что число процессоров ограничено некоторым базовым уровнем , зависящим от степени распараллеливания системы работ, стоимости использования процессоров -го типа и ряда других факторов. В случае возникновения коллизии параллельных задач, конкурирующих за один и тот же базовый процессор типа , необходимо ввести процессор типа . В зависимости от целей, преследуемых при выборе состава ресурсов, это может быть дополнительный процессор того же типа либо незадействованный базовый процессор типа такой, что , где – априорная оценка длительности выполнения задачи . Таким образом, параметр может быть равен (базовый процессор) либо (вводимый процессор).

Любая из задач передачи данных от задачи к задаче также характеризуется априорной оценкой длительности при использовании коммуникационной среды типа . Значение зависит от латентности, пропускной способности каналов связи и объема передаваемых данных. Будем полагать, что коммуникационная подсистема является масштабируемой, а число одновременно выполняемых обменов данными согласовано с верхней границей масштабируемости. Так, например, для сетевой технологии Myrinet этот показатель составляет 1024 процессорных узла. Фактическое время, отводимое для информационного обмена, . Если последовательно выполняемые задачи обработки назначаются на один и тот же процессор, то соответствующее время обмена и параметр назначения полагаются равными нулю.

Обозначим через и соответственно момент начала и длительность решения задачи . Формально распределение ресурсов вычислительной системы между задачами определим следующим образом:

(2.1) .

При этом в (2.1) назначение может быть равно , если – задача обработки. Пусть – множество задач обработки, выполняемых в момент времени , а – потребность задачи в процессоре типа , т.е. , если -я задача назначается на процессор -го типа, – в противном случае.

Необходимое условие разрешения коллизий параллельных задач можно записать так:

(2.2) .

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

Положим, что, помимо крайнего срока завершения задания, определены крайние сроки и завершения отдельных задач и работ:

(2.3) , , ,

где , – длительность выполнения задач , .

Распределение ресурсов (2.1) будем называть допустимым при соблюдении условий (2.2), (2.3). Поиск допустимого распределения подразумевает, естественно, и выбор состава ресурсов.

Введем критерии эффективности состава и распределения ресурсов (2.1). Каждый из вариантов допустимого распределения в критерии представим вектором , поскольку при заданном отношении частичного порядка (предшествования задач) и известном времени выполнения , задачи однозначно определяется момент ее начала.

Предположим, задачи , принадлежат одной работе. Обозначим через частные функции для оценки эффективности выполнения -й и -й задач на ресурсах, типы которых определяются назначениями .

Критерий называется аддитивно-сепарабельным, если его можно представить в следующем виде:

(2.4) , ,

.

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

(2.5) ,

(2.6) ,

где обозначает ближайшее не меньшее целое число; – число задач обработки; – объем вычислений.

В (2.5) частная функция – «экспоненциальный штраф» за назначение -й задачи на процессор, более производительный чем процессор типа . В (2.6) при вычислении значения берется ближайшая к априорная оценка длительности . Тем самым определяется и тип используемого процессора. Если распределение ресурсов оптимизируется по одному из критериев (2.5) или (2.6), то отыскивается минимум функции стоимости или .

Другой пример аддитивно-сепарабельного критерия – коэффициент загрузки ресурсов -го типа:

(2.7) ,

где – коэффициенты использования -й или -й задачей в работах экземпляра ресурса типа ; – число работ, выполняемых независимо от условных ветвлений процесса обработки; – число -компонентных наборов альтернативных работ; – число задач в работах .

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

Предположим, задан вектор аддитивно-сепарабельных критериев , , вида (2.4). Пусть – множество альтернатив, каждая из которых соответствует допустимому распределению ресурсов (2.1). Назовем стратегией. Вектор критериев формирует бинарное отношение для сравнения альтернатив множества . Множество оптимальных по отношению альтернатив в модели выбора будем называть -оптимальной стратегией распределения ресурсов.

Общая постановка задачи выбора состава и распределения ресурсов в вычислительной системе реального времени заключается в том, чтобы при заданных крайнем сроке завершения выполнения системы задач и связывающих (активных) ограничениях (2.3) из стратегии , соответствующей допустимым вариантам распределения ресурсов (2.1), выделить -оптимальную стратегию, где формируется вектором аддитивно-сепарабельных критериев эффективности , , вида (2.4).