Однокритериальная оптимизация распределения ресурсов
В.В. Топорков
ВЫБОР СОСТАВА И РАСПРЕДЕЛЕНИЕ РЕСУРСОВ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ ПО МЕТОДУ КРИТИЧЕСКИХ РАБОТ
Излагается подход к выбору состава и распределению вычислительных ресурсов в системах, функционирующих в реальном времени. Предлагаемые решения позволяют оптимизировать состав ресурсов и планирование выполнения заданного набора задач в зависимости от наступления определенных событий в вычислительной системе реального времени с масштабируемой архитектурой.
Введение
Выбор состава и распределение вычислительных ресурсов, реализующих заданный набор алгоритмов (работ), является одной из наиболее сложных проблем в проектировании систем управления, функционирующих в реальном масштабе времени. При этом распределение ресурсов и планирование работ представляют два взаимосвязанных аспекта этой проблемы. В рамках парадигмы совместного проектирования синтез структуры аппаратных и программных средств выполняются одновременно с планированием.
Для систем жесткого реального времени типичны следующие задачи. Заданы: крайние сроки завершения выполнения как отдельных работ, так и всей их совокупности. Необходимо: минимизировать функцию стоимости, отражающую затраты на аппаратные ресурсы, либо максимизировать загрузку процессоров и, тем самым, минимизировать затраты на заказные, вновь разрабатываемые аппаратные компоненты системы, либо обеспечить надежное выполнение работ с требуемой вероятностью.
|
|
|
Сложность обеспечения гарантированного завершения работ до наступления крайних сроков обусловлена тем, что необходимо учитывать динамику окружения вычислительной системы реального времени. Сюда включаются изменения параметров объекта управления, количества заявок на обслуживание и объемов вычислений, зависящих от значений входных данных, и т.п. Таким образом, возникает необходимость не в одном-единственном, а во множестве возможных вариантов состава и распределения ресурсов, т.е. в стратегии. Конкретный же вариант выбирается из стратегии в зависимости от параметров контрольных событий, наступающих в системе, например, времени, оставшегося для завершения выполнения отдельных работ. Когда структура вычислительной системы задана, то стратегия может быть сформирована с использованием методов математического, в том числе и статического, прогнозирования времени выполнения задач.
Рассмотрим подход к выбору состава и распределению ресурсов в проблемно-ориентированных вычислительных системах реального времени с масштабируемой архитектурой.
Под масштабируемостью понимается возможность наращивания числа процессоров, памяти и независимость пропускной способности коммуникационной подсистемы от количества процессорных узлов, участвующих в вычислениях. Излагаемый подход допускает выявление структуры, типов ресурсов и возможных вариантов их распределения для завершения заданной системы работ до наступления крайних сроков. При этом предполагается использование априорных оценок времени и объемов вычислений, а также ориентация на соответствующие классы составляющих задач. В зависимости от конкретных целей, преследуемых при распределении ресурсов, оценки могут представлять собой предельные (наихудшие) значения либо числовые характеристики соответствующих случайных величин. В основу методов выбора стратегии распределения ресурсов положен аппарат, составляющий суть метода критических работ. В данной лекции он дополняется и конкретизируется с учетом особенностей функционирования вычислительных систем реального времени.
|
|
|
Основные допущения при распределении ресурсов и постановка задачи
Положим, 
– совокупность частично упорядоченных задач, выполнение которых должно быть закончено до наступления крайнего временного срока 
. Отношение частичного порядка 
на 
задается с помощью ориентированного бесконтурного графа 
(рис. 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).
Однокритериальная оптимизация распределения ресурсов
Сначала рассмотрим подход к решению задачи выбора состава и распределения ресурсов при использовании одного критерия эффективности.
Критическую работу определим как путь в орграфе , имеющий наибольшую априорную оценку длительности выполнения и содержащий задачи, еще неназначенные на ресурсы. При расчете длительности работы для входящих в нее задач обработки выбирается наилучшая комбинация базовых процессоров, т.е. берется 
, 
, 
.
Понятия критической работы и критического пути в общем случае необходимо различать. Лишь до начала распределения ресурсов критические работа и путь совпадают.
Дата добавления: 2020-11-15; просмотров: 271; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!