Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Формирование стратегии вычисленийСодержание книги
Поиск на нашем сайте
Пусть имеется модель задания, используемая в схемах
где стратегия Параллельная схема формирования стратегии для модели задания – семейство последовательных схем:
где При этом планы из Т е о р е м а 2. При формировании – если
то
– если отношение
то справедливо:
где – если имеет место гомоморфизм
то выполняется:
где Д о к а з а т е л ь с т в о т е о р е м ы 2. Рассмотрим следующие три случая. Пусть имеет место (2.4.3). Поскольку Отношение Пусть определены гомоморфизмы (2.4.7) моделей выбора
где Примеры формирования стратегии П р и м е р 2.5.1. Рассмотрим применение параллельной схемы (2.4.2) к той же модели задания, что и в примере раздела 2.3 (см. рис. 2.1 и табл. 2.1). Пусть отношение П р и м е р 2.5.2. Пусть по параллельной схеме необходимо сформировать Парето-оптимальную стратегию распределения процессоров для модели, которой соответствует граф Таблица 2.3
Отношение Парето формируется вектором критериев Стратегии, условно оптимальные по критериям 2.6. Планы для разных моделей задания Рассмотрим семейство параллельных схем, каждая из которых Обобщенная схема формирования стратегии для множества
где Обозначим через Т е о р е м а 3. Положим,
где Д о к а з а т е л ь с т в о т е о р е м ы 3. Рассмотрим семейство
поскольку Далее, имеет место
Из (2.6.3) и (2.6.4) следует, что квазипорядок Обозначим: 2.7. Пример формирования планов для разных моделей задания Рассмотрим применение обобщенной схемы декомпозиции (2.6.1) ко множеству моделей, которые структурно представлены графами
Таблица 2.4
3. ПАКЕТНАЯ ОБРАБОТКА ЗАДАНИЙ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Последнее изменение этой страницы: 2020-12-09; просмотров: 96; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 52.15.173.197 (0.008 с.) |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
, каждая из которых 
позволяет сформировать стратегию 
, условно оптимальную по критерию 
, входящему в вектор 
. По аналогии с (2.2.7) критерий 
, (2.4.1)
.
, 
, 
, (2.4.2)
– множество условно оптимальных планов (2.2.5) для 
-й работы, выделенное из стратегии 
, полученной на этапе 
последовательной схемы 
.
отбираются путем сравнения по отношению (2.4.1). Согласно (2.4.2) условно оптимальная по 
, а генерация 
, может выполняться параллельно для всех критериев, входящих в 
.
-оптимальной стратегии по параллельной схеме (2.4.2) имеет место следующее:
, 
, (2.4.3)
; (2.4.4)
, (2.4.5)
, (2.4.6)
– множество оптимальных по 
;
моделей выбора 
и 
, такой что
, 
, 
, (2.4.7)
, (2.4.8)
– множество оптимальных по 
.
, то 
. Учитывая внутреннюю устойчивость 
. По определению отношения Парето это означает, что 
, где 
. Внешняя устойчивость 
, 
и 
. С учетом свойства внешней устойчивости 
, 
соответствующих моделей выбора:
,
– дополнения отношений 
на множествах 
, 
альтернатив соответственно, т.е. «нелучшие» планы в 
планы могут переходить в «лучшие» и в 
является внешне и внутренне устойчивым в модели выбора 
, откуда и следует (2.4.8). Теорема доказана.
(2.1.5) и коэффициенты загрузки 
, базовых процессоров вида (2.1.6). Поскольку условные ветвления в графе задания отсутствуют (см. рис. 2.1), то 
– отношение суммарного времени использования процессора типа 
к сроку 
завершения выполнения задания. Стратегии, условно максимальные по критериям 
; 
; 
и 
, представлены в табл. 2.2 соответственно вариантами: 4-7; 8, 9; 10, 11 и 12-14. По (2.4.4) 
может быть выделено не более трех единиц времени на первом и третьем процессорах (см. табл. 2.2). Метадиспетчер, просматривая совокупность планов, выбирает конкретный вариант распределения ресурсов, зависящий от фактической загрузки процессорных узлов. Тогда в качестве возможных вариантов распределения ресурсов метадиспетчер должен выбрать планы 1, 2, 4, 5, 12, 13. Конкретный же план должен быть оформлен в виде ресурсного запроса и реализован системой пакетной обработки в зависимости от состояния всех четырех процессоров и возможных времен запуска задач 
(см. табл. 2.2). В Парето-оптимальную стратегию также входят все планы, однако в общем случае должно выполняться (2.4.6), что иллюстрирует следующий пример.
(см. рис. 2.1 и табл. 2.1).
. Стратегия строится во всем диапазоне изменения длительности 
решения каждой из задач, а шаг изменения принимается не меньшим, чем нижняя граница диапазона (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) служит следующее утверждение.
, где 
, а 
определяется согласно (2.4.1). Пусть 
– непустая 
-оптимальная стратегия в модели выбора 
. Тогда имеет место:
, (2.6.2)
– отношение эквивалентности, порождаемое квазипорядком 
. Справедливо следующее:
, (2.6.3)
. Это объясняется различием структуры и параметров моделей 
и 
задания в схемах 
.
, 
. (2.6.4)
, соответствующие параллельным схемам 
.
. Можно утверждать, что 
, поскольку 
. Кроме этого, 
, поскольку 
и 
, где 
– отношение эквивалентности, порождаемое квазипорядком 
. Значит, справедливо (2.6.2), что и требовалось доказать.
на рис. 2.1. Для модели 
исходные условия те же, что и в примере 5.1, для моделей 
принимаются условия примера 5.2 того же раздела 2.5. Требуется построить 
-оптимальную стратегию, где 
, а 
формируется одним из критериев 
задачи 
и 
оказываются назначенными на один и тот же процессор первого типа. Следовательно, могут быть исключены затраты на обмены данными 
. Поскольку конфликтов между задачами обработки в этом случае возникнуть не может (см. рис. 2.1), то планирование, полученное до исключения процедур обмена, может быть пересмотрено. Результаты распределения процессоров приведены в табл. 2.4. Планы 1-6 в табл. 2.4 соответствуют стратегии, условно минимальной по 
. Следовательно, нет смысла выполнять формирование условно максимальных планов по критериям 
. Таким образом, 
, 
и 
