Формирование стратегии вычислений 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Формирование стратегии вычислений



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

,   (2.4.1)

где стратегия  внутренне и внешне устойчива в модели выбора .

Параллельная схема формирования стратегии для модели задания – семейство последовательных схем:

, , , (2.4.2)

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

При этом планы из  отбираются путем сравнения по отношению (2.4.1). Согласно (2.4.2) условно оптимальная по  стратегия – семейство планов , а генерация , , может выполняться параллельно для всех критериев, входящих в .

Т е о р е м а 2. При формировании -оптимальной стратегии по параллельной схеме (2.4.2) имеет место следующее:

– если

, ,          (2.4.3)

то

;                                       (2.4.4)

– если отношение  таково, что

, ,      (2.4.5)

то справедливо:

,                                           (2.4.6)

где  – множество оптимальных по  планов в модели выбора ;

– если имеет место гомоморфизм  моделей выбора  и , такой что

, , , (2.4.7)

то выполняется:

,                                        (2.4.8)

где  – множество оптимальных по  планов в модели выбора .

Д о к а з а т е л ь с т в о т е о р е м ы 2. Рассмотрим следующие три случая.

Пусть имеет место (2.4.3). Поскольку  внешне устойчиво в модели выбора , то . Учитывая внутреннюю устойчивость  в , приходим к (2.4.4).

Отношение  в (2.4.5) является отношением Парето и представляет собой асимметричную часть отношения (2.4.3). Предположим, что . По определению отношения Парето это означает, что , где . Внешняя устойчивость  в модели выбора  исключает существование такого плана. В силу того, что ,  и  внутренне устойчиво в , получаем (2.4.6).

Пусть определены гомоморфизмы (2.4.7) моделей выбора  и . С учетом свойства внешней устойчивости  в модели выбора  можно утверждать, что имеет место и гомоморфизм дополнений ,  соответствующих моделей выбора:

,

где  – дополнения отношений  на множествах ,  альтернатив соответственно, т.е. «нелучшие» планы в  не могут быть представлены «лучшими» в . В свою очередь, в соответствии с (2.4.7) «лучшие» в  планы могут переходить в «лучшие» и в . Кроме этого, множество  является внешне и внутренне устойчивым в модели выбора . Значит, -оптимальную стратегию нужно отыскивать на семействе , откуда и следует (2.4.8). Теорема доказана.

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

П р и м е р 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

П Л А Н

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

Назначение

Критерии

 
1 2 3 3 4 4 3 1 1 3 2 4 1 39 0,40 0,20 0,15 0,20
2 4 3 3 2 2 3 2 1 3 1 2 1 41 0,40 0,30 0,15 0
3 4 3 3 3 3 2 2 1 3 1 3 1 40 0,40 0,20 0,30 0
4 5 3 3 2 2 2 2 1 3 1 2 1 43 0,35 0,35 0,15 0
5 2 3 3 2 2 5 1 1 3 1 2 1 43 0,60 0,10 0,15 0
6 2 3 3 4 4 3 1 1 3 1 4 1 39 0,60 0 0,15 0,20
7 2 3 3 5 5 2 1 1 3 1 4 1 41 0,60 0 0,15 0,25
8 2 6 6 2 2 2 1 2 1 1 2 1 42 0,60 0,30 0 0
9 4 3 3 2 2 3 1 1 3 1 2 1 41 0,60 0,10 0,15 0
10 4 3 3 3 3 2 1 1 3 1 3 1 40 0,60 0 0,30 0
11 4 4 4 2 2 2 1 1 4 1 2 1 41 0,60 0,10 0 0,20
12 5 3 3 2 2 2 1 1 3 1 2 1 43 0,60 0,10 0,15 0
13 2 6 6 2 2 2 1 2 4 1 2 1 43 0,30 0,40 0 0,30
14 4 3 3 2 2 3 2 1 2 1 2 1 41 0,40 0,45 0 0
15 4 3 3 3 3 2 2 1 2 1 2 1 40 0,40 0,50 0 0
16 4 4 4 2 2 2 2 1 2 1 2 1 41 0,40 0,50 0 0
17 5 3 3 2 2 2 2 1 2 1 2 1 43 0,35 0,50 0 0
18 2 3 3 2 2 5 1 1 3 1 2 2 43 0,35 0,35 0,15 0
19 2 3 3 4 4 3 1 1 3 2 3 1 39 0,40 0,20 0,35 0
20 2 3 3 5 5 2 1 1 3 2 3 1 40 0,35 0,25 0,40 0
21 2 6 6 2 2 2 1 2 3 1 2 1 42 0,30 0,40 0,30 0
22 4 3 3 2 2 3 2 1 3 1 2 1 41 0,40 0,30 0,15 0
23 4 3 3 3 3 2 2 1 3 1 3 1 40 0,40 0,20 0,30 0
24 4 4 4 2 2 2 2 1 3 1 2 1 41 0,40 0,30 0,20 0
25 5 3 3 2 2 2 2 1 3 1 2 1 43 0,35 0,35 0,15 0
26 2 3 3 2 2 5 1 1 3 1 2 2 43 0,35 0,35 0,15 0
27 2 3 3 4 4 3 1 1 3 2 4 1 39 0,40 0,20 0,15 0,20
28 2 3 3 5 5 2 1 1 3 2 4 1 40 0,35 0,25 0,15 0,25
29 2 6 6 2 2 2 1 2 4 1 2 1 42 0,30 0,40 0 0,30
30 4 3 3 2 2 3 2 1 3 1 2 1 41 0,40 0,30 0,15 0
31 4 3 3 3 3 2 2 1 3 1 3 1 40 0,40 0,20 0,30 0
32 4 4 4 2 2 2 2 1 4 1 2 1 41 0,40 0,30 0 0,20
33 5 3 3 2 2 2 2 1 3 1 2 1 43 0,35 0,35 0,15 0

Отношение Парето формируется вектором критериев , . Стратегия строится во всем диапазоне изменения длительности  решения каждой из задач, а шаг изменения принимается не меньшим, чем нижняя граница диапазона (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.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

П Л А Н

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

Назначение

Критерии

 
1 2 8 6 4 1 1 1 1 25 1 0 0 0
2 4 8 3 5 1 1 1 1 24 1 0 0 0
3 6 4 6 4 1 1 1 1 24 1 0 0 0
4 8 4 3 5 1 1 1 1 27 1 0 0 0
5 10 4 3 3 1 1 1 1 29 1 0 0 0
6 11 4 3 2 1 1 1 1 32 1 0 0 0

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



Поделиться:


Последнее изменение этой страницы: 2020-12-09; просмотров: 80; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.17.128.129 (0.03 с.)