Примеры стратегий распределения ресурсов
Пример 6.1. Вновь вернемся к системе задач, информационный граф которой показан на рис. 1, а их априорные характеристики приведены в табл. 1. Положим, исходные данные те же, что и в примерах 4.1, 4.2 раздела 4 данной лекции. Необходимо при крайнем сроке построить стратегии распределения ресурсов, условно оптимальные по двум критериям – функции стоимости (2.6) и коэффициенту загрузки (2.7) процессора третьего типа (заметим, что при сравнении двух альтернатив распределения при прочих равных условиях предпочтение отдается альтернативе с меньшим значением или большим значением ). Для построения стратегии использовать обратную прогонку.
Построим стратегии, последовательно применяя оба критерия и уравнения (5.3) - (5.6). В табл. 2 варианты 1-6 представляют стратегию , условно оптимальную по , а варианты 7, 9, 11, 12, 14-17 соответствуют стратегии , условно оптимальной по . Напомним, что в соответствии с теоремой 3 в условно оптимальные стратегии попадают лишь те варианты распределения ресурсов, в которых коллизии разрешаются за счет процессоров тех же типов, что и базовые. В табл. 2 это – варианты 7, 9 и 12, в которых для разрешения коллизий вводится дополнительный процессор типа 3.
Стратегия строится с помощью процедур обратной прогонки и прямой раскрутки по уравнениям (5.3) - (5.5). Каждое значение длительности выполнения задачи (см. рис. 2) является условно оптимальным и определяет значение запаса по времени к началу запуска задачи . Так, при , а условно оптимальная длительность второй задачи равна . При этом и , . Условно оптимальные значения и рассчитываются по аналогии с тем, как это делается в примере 4.1. Для условно оптимальных длительностей по (5.6) находятся условно оптимальные назначения . Отношение , формируемое критерием , таково, что для любой альтернативы, не принадлежащей , значение функции стоимости не меньше, чем значение для любой из альтернатив в . При этом стратегия внутренне устойчива: в нее включаются варианты 1-7, каждый из которых является условно оптимальным по (см. табл. 2). При расчете коэффициента загрузки берутся условно оптимальные длительности задач, использующих базовый процессор третьего типа.
Аналогично строится стратегия , условно оптимальная по критерию , с помощью которого формируется соответствующее отношение . Для любой из альтернатив, не входящей в , значение не больше, чем значение этого критерия для любой из альтернатив из . Так же, как и , стратегия внутренне и внешне устойчива.
Положим, что и имеет место (5.2). Тогда -оптимальная стратегия совпадает с .
Пример 6.2. Пусть для тех же исходных условий, что и примере 6.1, необходимо найти Парето-оптимальную стратегию распределения ресурсов, формируемую критериями и . Использовать обратную прогонку.
Очевидно, что отношение Парето представляет собой асимметричную часть отношения из примера 6.1. В табл. 2 Парето-оптимальная стратегия представлена вариантами 2, 3, 7, 12.
Соответствующие структуры вычислительной и коммуникационной сред показаны на рис. 5, а-г. Вариант 2 представляет распределение с минимальным значением функции стоимости (см. пример 4.1 и диаграмму на рис. 3).
Как уже говорилось, практически оправданным может быть ослабление требований к отношениям и . Так, -оптимальная стратегия, полученная в примере 6.1 и состоящая из 14 вариантов распределения ресурсов, охватывает больший диапазон временных параметров возможных контрольных событий в системе, чем Парето-оптимальная стратегия из четырех вариантов. Предположим, что фактическая динамика загрузки процессоров такова, что для задач (см. рис. 1 и табл. 2) может быть использовано не более пяти единиц времени при том же крайнем сроке завершения всех работ. Тогда из -оптимальной стратегии может быть выбран любой из вариантов распределения ресурсов следующей совокупности: 1, ..., 6, 9, 11, 14, ..., 17. Кроме этого, стратегия может быть расширена за счет вариантов распределения, «близких» к оптимальным.
Рассмотрим следующий
Пример 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.
Дата добавления: 2020-10-01; просмотров: 234;