Примеры выбора состава и распределения ресурсов

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