Примеры формирования стратегии

П р и м е р 2.5.1. Рассмотрим применение параллельной схемы (2.4.2) к той же модели задания, что и в примере раздела 2.3 (см. рис. 2.1 и табл. 2.1).

Пусть отношение имеет вид (2.4.3), а векторный критерий включает функцию стоимости (2.1.5) и коэффициенты загрузки , базовых процессоров вида (2.1.6). Поскольку условные ветвления в графе задания отсутствуют (см. рис. 2.1), то – отношение суммарного времени использования процессора типа к сроку завершения выполнения задания. Стратегии, условно максимальные по критериям ; ; и , представлены в табл. 2.2 соответственно вариантами: 4-7; 8, 9; 10, 11 и 12-14. По (2.4.4) -оптимальная стратегия включает все 14 планов. Положим, динамика загрузки процессоров такова, что для задач может быть выделено не более трех единиц времени на первом и третьем процессорах (см. табл. 2.2). Метадиспетчер, просматривая совокупность планов, выбирает конкретный вариант распределения ресурсов, зависящий от фактической загрузки процессорных узлов. Тогда в качестве возможных вариантов распределения ресурсов метадиспетчер должен выбрать планы 1, 2, 4, 5, 12, 13. Конкретный же план должен быть оформлен в виде ресурсного запроса и реализован системой пакетной обработки в зависимости от состояния всех четырех процессоров и возможных времен запуска задач (см. табл. 2.2). В Парето-оптимальную стратегию также входят все планы, однако в общем случае должно выполняться (2.4.6), что иллюстрирует следующий пример.

П р и м е р 2.5.2. Пусть по параллельной схеме необходимо сформировать Парето-оптимальную стратегию распределения процессоров для модели, которой соответствует граф (см. рис. 2.1 и табл. 2.1).

Таблица 2.3

П Л А Н	Длительность	Назначение	Критерии
														0,40	0,20	0,15	0,20
														0,40	0,30	0,15
														0,40	0,20	0,30
														0,35	0,35	0,15
														0,60	0,10	0,15
														0,60		0,15	0,20
														0,60		0,15	0,25
														0,60	0,30
														0,60	0,10	0,15
														0,60		0,30
														0,60	0,10		0,20
														0,60	0,10	0,15
														0,30	0,40		0,30
														0,40	0,45
														0,40	0,50
														0,40	0,50
														0,35	0,50
														0,35	0,35	0,15
														0,40	0,20	0,35
														0,35	0,25	0,40
														0,30	0,40	0,30
														0,40	0,30	0,15
														0,40	0,20	0,30
														0,40	0,30	0,20
														0,35	0,35	0,15
														0,35	0,35	0,15
														0,40	0,20	0,15	0,20
														0,35	0,25	0,15	0,25
														0,30	0,40		0,30
														0,40	0,30	0,15
														0,40	0,20	0,30
														0,40	0,30		0,20
														0,35	0,35	0,15

Отношение Парето формируется вектором критериев , . Стратегия строится во всем диапазоне изменения длительности решения каждой из задач, а шаг изменения принимается не меньшим, чем нижняя граница диапазона (2.3.2). Остальные исходные условия те же, что и в предыдущих примерах.

Стратегии, условно оптимальные по критериям , , , и , представлены в табл. 2.3 планами 1-4, 5-12, 13-17, 18-25 и 26-33 соответственно. В Парето-оптимальную стратегию не попадают планы 2, 5, 12, 14, 16, 17, 22 и 30. Полученный результат согласуется с (2.4.6).

Планы для разных моделей задания

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

Обобщенная схема формирования стратегии для множества моделей задания – семейство схем вида:

, , , , (2.6.1)

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

Обозначим через стратегию распределения ресурсов по параллельной схеме . Формальным обоснованием обобщенной схемы (2.6.1) служит следующее утверждение.

Т е о р е м а 3. Положим, – квазипорядок на множестве опорных планов, формируемых по обобщенной схеме , в которой каждая из параллельных схем реализует модель выбора , где , а определяется согласно (2.4.1). Пусть – непустая -оптимальная стратегия в модели выбора . Тогда имеет место:

, (2.6.2)

где – отношение эквивалентности, порождаемое квазипорядком .

Д о к а з а т е л ь с т в о т е о р е м ы 3. Рассмотрим семейство . Справедливо следующее:

, (2.6.3)

поскольку . Это объясняется различием структуры и параметров моделей и задания в схемах .

Далее, имеет место

, . (2.6.4)

Из (2.6.3) и (2.6.4) следует, что квазипорядок порождает отношение эквивалентности, которое задает разбиение на классы , соответствующие параллельным схемам , .

Обозначим: . Можно утверждать, что , поскольку . Кроме этого, , поскольку и , где – отношение эквивалентности, порождаемое квазипорядком . Однако при этом не исключено, что . Значит, справедливо (2.6.2), что и требовалось доказать.

2.7. Пример формирования планов для разных моделей задания

Рассмотрим применение обобщенной схемы декомпозиции (2.6.1) ко множеству моделей, которые структурно представлены графами на рис. 2.1. Для модели исходные условия те же, что и в примере 5.1, для моделей принимаются условия примера 5.2 того же раздела 2.5. Требуется построить -оптимальную стратегию, где , а формируется одним из критериев , . В результате распределения ресурсов для модели задачи и оказываются назначенными на один и тот же процессор первого типа. Следовательно, могут быть исключены затраты на обмены данными . Поскольку конфликтов между задачами обработки в этом случае возникнуть не может (см. рис. 2.1), то планирование, полученное до исключения процедур обмена, может быть пересмотрено. Результаты распределения процессоров приведены в табл. 2.4. Планы 1-6 в табл. 2.4 соответствуют стратегии, условно минимальной по . При этом . Следовательно, нет смысла выполнять формирование условно максимальных планов по критериям . Таким образом, -оптимальная стратегия совпадает со стратегией, представленной в табл. 2.2, 2.3 и 2.4 для моделей , и (см. рис. 2.1) с точностью до отношения эквивалентности.

Таблица 2.4

П Л А Н

Длительность

Назначение

Критерии

3. ПАКЕТНАЯ ОБРАБОТКА ЗАДАНИЙ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ