Примеры стратегий распределения ресурсов

Пример 6.1. Вновь вернемся к системе задач, информационный граф которой показан на рис. 1, а их априорные характеристики приведены в табл. 1. Положим, исходные данные те же, что и в примерах 4.1, 4.2 раздела 4 данной лекции. Необходимо при крайнем сроке построить стратегии распределения ресурсов, условно оптимальные по двум критериям – функции стоимости (2.6) и коэффициенту загрузки (2.7) процессора третьего типа (заметим, что при сравнении двух альтернатив распределения при прочих равных условиях предпочтение отдается альтернативе с меньшим значением или большим значением ). Для построения стратегии использовать обратную прогонку.

Пример 6.2. Пусть для тех же исходных условий, что и примере 6.1, необходимо найти Парето-оптимальную стратегию распределения ресурсов, формируемую критериями и . Использовать обратную прогонку.

Пример 6.3. Положим, что условия примера 6.1 дополнены возможностью разрешения коллизий с помощью процессора, введение которого сопровождается минимумом штрафной функции . Как было показано в примере 4.2 раздела 4, это процессор четвертого типа. Коллизии между конкурирующими задачами (в вариантах 8 и 13 это , а в варианте 10 – ) разрешаются за счет использования процессора именно этого типа (см. табл. 1 и 2). Диаграммы распределения ресурсов для вариантов 8 и 13 показаны на рис. 4, а и 4, в. В сравнении с вариантами 7, 9 и 12 это дает прирост значения в одну единицу стоимости.

Строго говоря, распределения 8, 10 и 13 не принадлежат оптимальной стратегии, поскольку функция стоимости должна рассчитываться по условно оптимальным значениям длительности. Однако, если определено понятие степени «близости» подобных вариантов к условно оптимальным, то они могут быть использованы для расширения стратегии. Так, в данном примере варианты 8, 13 ничем не уступают варианту 15, формально входящим в стратегию, условно оптимальную по критерию .

Заключение

1. В лекции изложен и обоснован подход к выбору состава (типов) и оптимизации распределения ресурсов в проблемно-ориентированных вычислительных системах, функционирующих в реальном времени.

2. Рассмотрены методы одно- и многокритериальной оптимизации распределения ресурсов, в основу которых положены аппараты динамического программирования и разрешения коллизий конкурирующих задач.

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

4. Нужно подчеркнуть, что непредсказуемость поведения окружения системы может быть причиной выбора неадекватной стратегии. Например, могут возникнуть такие отказы в системе, которые делают невозможным разрешение коллизий параллельных задач из-за отсутствия свободных процессоров. Однако это проблемы, требующие особого рассмотрения и выходящие за рамки данной лекции.

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

ПРИЛОЖЕНИЕ

Доказательство теоремы 1. Обозначим через множество допустимых значений переменных , определяемых соответствующими диапазонами изменения . Рассмотрим конечные последовательности из элементов вида

,

где – векторы длительностей выполнения задач в соответствующих работах.

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

Представим аддитивно-сепарабельный критерий (2.4) как монотонно-рекурсивный функционал, определенный на множестве :

(П.1) ( )

,

где ; – набор длительностей задач, соответствующих оптимальному планированию.

Последовательность или является оптимальной, если или .

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

Рассмотрим две допустимые последовательности такие, что имеет место . Это означает, что последовательность содержит меньше отрезков оптимального планирования для работ , чем последовательность . Это следует из свойства монотонной рекурсивности функционала (П.1). При этом очевидно, что , поскольку совокупность всех конечных допустимых отрезков, сопряженных с и , определяется диапазонами изменения переменных векторов независимо от их оптимальности. Тогда в соответствии с обобщенным принципом оптимальности динамического программирования последовательности множества не могут быть оптимальными. Это, в свою очередь, означает, что экстремум может быть достигнут тогда, когда , что и требовалось доказать.

Доказательство леммы. Введем обозначения: , . Предположим, что . Внешняя устойчивость исключает существование такой альтернативы распределения ресурсов. В общем случае . При этом

(П.2) .

Таким образом, из (П.2) следует

(П.3) .

Кроме этого,

(П.4) .

Следовательно, из (5.2), (П.3), (П.4) получаем, что

.

Теперь положим, что антисимметрично. Благодаря внешней устойчивости и антисимметричности , следующей из (5.2), имеет место:

(П.5) .

Поскольку внутренне устойчиво, то с учетом (П.5)

.

Лемма доказана.

РЕКОМЕДУЕМАЯ ЛИТЕРАТУРА

1. Топорков В.В. Модели распределенных вычислений. М.: Физматлит, 2004.

2. Таха Х. Введение в исследование операций: В 2 кн. М.: Мир, 1985.

3. Юдин Д.Б. Вычислительные методы теории принятия решений. М.: Наука, 1989.

4. Михалевич В.С., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983.