17. Алгоритмы построения дз p2

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

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

Критерии построения: Tцр <= Тцр_max, max{F(τ)} ->n/2

В качестве исходных данных выступает ДЗ 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 возможным образом.

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

18. Алгоритм формирования дз p2 путем подбора количества доступных эм

В качестве исходных данных выступает граф ИС, количество доступных ЭМ и 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го алгоритмов.

19. Коллективные диагностические проверки

В случае коллективных проверок один из фрагментов назначенный на данный временной такт решается всеми свободными ЭМ. Далее происходит сравнение результатов.

[+]:суммарное количество эквивалентных становиться больше чем при проведении парных проверок.

Под эквивалентным количеством проверок подразумевается общее количество сравнений результатов.

[-] :более сложная организация проведения проверок и более сложная организация системы сравнения полученных результатов.

Если есть n — количество машин в ВС, F(τ) — функция плотности загрузки, k — количество машин участвующих в проверке ( коллективной ).

k = n — F( τ) + 1

Nэкв — количество эквивалентных проверок

Nэкв = ( k*(k-1) )/2. Nэкв = [(n - F( τ)+1)*(n-F( τ)) ]/2

Алгоритм построения загрузки P2 в случае коллективных диагностических проверок. В качестве исходных данных выступают ДЗ P1. В период цикла решения Tцр_max.

1й шаг: P2 = P1

2й шаг: если Tцр >= Tцр_max, то переходим к шагу 8

3й шаг: в ДЗ P2 выбираем такой такт τ, на котором решается множество фрагментов w_τ

4й шаг: добавляем в ДЗ P2 новый такт решения τ+1

5й шаг: из множества w_τ выбирается подмножество w1_τ

6й шаг: w_τ+1 = w1_τ

7й шаг: переход к шагу 2

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

Nэкв = Nэкв_τ + Nэкв_τ+1

Задача: выбрать такой такт τ, перенос с которого определенной части фрагментов обеспечит max количество эквивалентных проверок.

Построение ДЗ P3 в случае коллективных диагностических проверок.

В качестве исходных данных выступает ДЗ P2 и ДГ. В целом построение ДЗ P3 аналогично построению такой диаграммы для парных диагностических проверок. Единственное отличие — после реализации проверок предусмотренных ДЗ P3 в ДГ добавляется не существующие реально связи, обусловленные алгоритмом проведения коллективных проверок.