Примеры выбора состава и распределения ресурсов
Пример 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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!