Алгоритм формирования ДЗ P2 путем подбора количества доступных ЭМ

Алгоритмы построения ДЗ P2

F(τ) — функция плотности загрузки, которая показывает количество ЭМ задействованных в решении прикладной задачи на такте τ.

График зависимости количества элементарных проверок от функции плотности загрузки:

В качестве исходных данных выступает ДЗ P1. Величина Tцр_max и количество машин в ВС.

1й шаг: присвоить ДЗ P2 = P1

2й шаг: проверить значение Tцр, сравнить с Тцр_max, если он = либо >, то переходим в шаг 8

3й шаг: найти в ДЗ P2 такой такт τ в котором функция плотности загрузки принимает max значения и это значение > n/2

4й шаг: если такой такт τ не найден, то выполнить переход в шаг 8

5й шаг: добавить в ДЗ P2 такт τ+1 сразу за тактом τ

6й шаг: половина фрагментов задач с такта τ переносится на такт τ+1

7й шаг: выполнить переход на шаг 2

8й шаг: конец алгоритма.

[+]:

· min набор необходимых исходных данных

· простота реализации

· низкая трудоемкости

При большом количестве задействованных в решении машин, гарантируется заполнение ДЗ до Tцр_max.

То есть система разгружается max возможным образом.

[-]: высокая неравномерность функции плотности загрузки по всем тактам. Данное явление вызвано отсутствием анализа графа ИС.

В качестве исходных данных выступает граф ИС, количество доступных ЭМ и Tцр_max. В данном алгоритме k (количество ЭМ) используемых для решения прикладной задачи.

1й шаг: присвоить k = n

2й шаг: сформировать ДЗ P2 выбранным алгоритмом А. P2 → А

3й шаг: k = k-1

4й шаг: если k <= n/2, то переход на шаг 9

5й шаг: если Тцр < Tцр_max, то переход на шаг 2

6й шаг: если Тцр = Тцр_max, то переход на шаг 9

7й шаг: k = k+2

8й шаг: сформировать ДЗ P2 выбранным алгоритмом А

9й шаг: конец алгоритма.

Сложность алгоритма определяется алгоритмом А.

[+]: высока равномерность значений функции плотности загрузки

[-]:

· высокая трудоемкость

· невозможность задействовать всю доступную временную избыточность

Комбинированный алгоритм:

На первом этапе ДЗ строится путем подбора доступного количества ЭМ.

На втором такте ДЗ корректируется путем применения алгоритма заполнения свободных временных тактов.

[+]:max качественная ДЗ, так как обеспечивается высокая равномерность функции плотности по тактам. При этом используется вся доступная временная избыточность.

[-]:высокая сложность реализации, так как она определяется сложностью 1го и 2го алгоритмов.