Примеры выбора состава и распределения ресурсов
Пример 4.1. Пусть необходимо выбрать состав и распределение процессоров для реализации задания (системы задач), представленного информационным графом на рис. 1.
Априорные оценки длительности выполнения задач обработки
и объемы вычислений
для четырех типов базовых процессоров приведены в табл. 1, где
;
. Число базовых процессоров каждого типа равно 1.
Длительности всех обменов данными , в коммуникационной среде типа
одинаковы и равны одной единице времени.
Состав процессоров и их распределение между задачами должны быть такими, чтобы обеспечить минимум функции стоимости обработки (2.6) при заданном крайнем сроке завершения выполнения задач.
Проведем распределение ресурсов, последовательно применяя уравнения (3.1) - (3.6) для каждой из четырех критических работ:
;
;
;
.
Напомним, их максиминная длительность равна соответственно 12, 11, 10 и 9 единицам времени.
Иллюстрация процедур обратной прогонки и прямой раскрутки, осуществляемых в соответствии с уравнениями (3.1) и (3.2), для нахождения минимума стоимости завершения первой из критических работ дана на рис. 2, где приняты следующие обозначения:
– длительность задач
;
– запасы времени к моменту запуска задач
;
– частные функции стоимости выполнения задач
, входящие в критерий (2.6) и вычисляемые через отношение объема вычислений к длительности решения соответствующей задачи;
– суммарная стоимость выполнения задач
;
и
соответственно.
|
|
Обратной прогонке на рис. 2 соответствуют сплошные стрелки, а прямой раскрутке – пунктирные.
Так, чтобы найти длительность , обеспечивающую минимум
, необходимо в соответствии с (3.1) отыскать условно оптимальные значения функций
и
в зависимости от запаса по времени
и
к моменту запуска соответствующей задачи.
Например, при условно минимальное значение
равно 8, оно обеспечивается тремя парами значений
и
: 4, 8; 6, 6; 8, 4.
Для :
,
,
и т.д.
В значения входят лишь условно минимальные
.
Наконец, когда найдены условно минимальные значения для соответствующих запасов по времени
, строится зависимость
.
Далее начинается прямаяраскрутка согласно уравнению (3.2) для того, чтобы определить оптимальные длительности решения задач и
(см. рис. 2).
Минимум стоимости достигается при
и
. Для
:
при
и
. Для
:
при
,
.
По (3.3) с учетом априорных оценок (см. табл. 1) и вида функции стоимости (2.6) определяются типы используемых процессоров.
Так, задача назначается на процессор типа 2, поскольку именно этот процессор обеспечивает ближайшую к
априорную оценку
, не превышающую
. Таким образом, получаем следующие оптимальные назначения:
,
,
,
.
|
|
Результат распределения процессоров между задачами первой критической работы представлен диаграммой Ганта на рис. 3, где рядом с символом, обозначающим задачу, указан тип используемого ею ресурса. Поскольку задачи и
последовательно выполняются на одном и том же процессоре, то нет необходимости в затратах на обмены данными
и
. Поэтому соответствующий параметр назначения
полагается равным нулю. Тем не менее, как отмечалось, достигнутый план выполнения задач не должен изменяться для обеспечения сходимости процедуры распределения ресурсов на основе применения уравнений (3.1) - (3.6).
Аналогично вышеизложенному выполняется распределение ресурсов между задачами трех остальных критических работ.При этомнеобходимо учитывать информационные связи между задачами, обуславливающие введение дополнительных временных ограничений.
Так, длительность выполнения задачи , входящей во вторую критическую работу, должна удовлетворять неравенству
и зависит от позднего срока окончания решения задачи
, входящей в третью критическую работу. При этом ее длительность
. Задачи
и
входят также и в четвертую критическую работу, причем
. Минимальные значения частных функций стоимости выполнения этих задач
и
достигаются при
и
.
|
|
Задачи и
назначаются на один и тот же процессор типа 4 (см. рис. 3 и табл. 1). Следовательно, отсутствуют затраты на обмен данными
.
Таким образом, минимум функции стоимости (2.6) равен
и достигается при использовании процессоров типов 1, 2, 4 и распределении ресурсов, показанном на рис. 3.
Дата добавления: 2020-11-15; просмотров: 146; Мы поможем в написании вашей работы! |
![](/my/edugr4.jpg)
Мы поможем в написании ваших работ!