20.Динамическое распределение фрагментов задач по элементарным машинам в вс

В ОУВС процесс решения прикладных задач можно разделить на 5 этапов:

1. формирование графа ИС на основе исходных алгоритмов решения задач

2. генерация исходного плана решения

3. синтез ДГ

4. Формирование расширенного плана решения с учетом проверок

5. загрузка ВС с учетом расширенного плана

В случае статического планирования выполнение этапов производится поочередно.

В случае динамического планирования возможны частичные совмещения и даже изменение порядка следования этапов.

• Синтез ДГ производится с учетом свойств прикладных алгоритмов:

• особенности проведения проверок,

• количество ЭМ в ВС и их тип

• накладываемые ограничения на меру диагностируемости.

• К ДГ всегда предъявляется ряд требований:

• он должен быть связным

• локальная степень вершин должна быть max ( для рядв диагностических моделей это не актуально ).

• В системах реального времени используется динамическое планирование. Поэтому и ДГ желательно формировать с учетом конкретной ситуации.

Пример: если в системе есть большое количество невостребованных ресурсов, то можно увеличить меру диагностируемости без ущерба для вычислительного процесса. При этом в системе реального времени время проведения любой процедуры следует минимизировать, поэтому трудоемкость формирования ДГ должна быть min. Решить данную ситуацию можно следующим образом: совместив формирование ДЗ P3 и ДГ. При этом соответствующий этим проверкам ДГ должен быть связным, а локальные степени вершин max большими и минимизировать разбор между локальными степенями врешин.

min(deg(U_i)) → max(deg(U_i))

То есть для каждого такта работы τ на основе исходного плана загрузки P1_τ получить расширенный план P3_τ обеспечивающий решение фрагментов прикладных задач.

W_i определенных исходным планом, а так же выполнение max количества элементарных проверок. При этом соответствующие данным проверки ДГ должен быть связным, а локальные степени вершин max близкими.

Алгоритм:

1. создать пустой ДГ: G(U,T)

2. τ = 1, все ЭМ пометить как свободные

3. пометить множество фрагментов задач W_τ которые предназначены для решения в момент τ. Данные фрагменты выбираются из исходного плана решения P1

4. если функция плотности загрузки F(τ) = n => все машины заняты, выполняем переход на шаг 8

5. если существует множество вершин U1 входящих в общее множество вершин и локальная степень данных вершин > 0, то выбирается вершина U_k є U_1 имеющим min локальную степень, если такой нет то берем U_1 deg(U_k) = min(U_l) deg(U_l) > 0

6. выбираем множество вершин U_test. Данное множество выбирается таким образом чтобы что вершины принадлежащие этому множеству имеют меньшую локальную степень вершин, чем вершины не входящие в это подмножество U_i є U \ U_test deg(U_i) >= deg(U_i)

7. всем ЭМ входящим в подмножество U_test и ЭМ U_k назначить 1 фрагмент w1_τ, который должен решаться на данном шаге работы системы. В ДГ достроить все возможные связи между вершинами входящими в подмножество U_test и вершин U_k, всем остальным ЭМ назначить на решение оставшиеся фрагменты прикладных задач

8. w_t = w_τ \ w_1

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

10. τ = τ+1

11. если τ =< τ_max, то переход на шаг 3, где τ_max — это длина ДЗ P1

12. конец алгоритма.

ДГ полученный в результате работы данного алгоритма — связный, помимо этого на каждом такте контроля происходит выравнивание локальных степеней вершин за счет введения между вершинами с min степенью.

Данный алгоритм позволяет получить ДГ с любым значением min локальной степени вершины. Min степень вершины может принимать значение n-1.

При этом для получения полного ДГ может потребоваться значение времени > Tцр_max.

Система которая обеспечит max степень диагностируемости целесообразно дешифрацию синдрома производить через определенный интервал времени от момента проведения первой элементарной проверки с единичным результатом.

Если к ВС предъявляется требование по минимизации цикла диагностики при ограничении на необходимую уровень диагностируемости, то дешифрация синдрома должна производится в тот момент, когда мера диагностируемости для формируемого ДГ достигает / превышает заданную величину.

t_д — заданная величина меры диагностируемости.

Для некоторых диагностических моделей значение меры диагностируемости однозначно связано с min локальной степенью вершин. Для таких моделей дешифрацию следует производить при достижении заданной min степени вершины.

min{deg(U_l)} >= deg_min

Точная структура полученная в результате работы алгоритма ДГ заранее не известна. Это накладывает ограничения на использование табличного метода дешифрации, так как его использование требует в данном случае очень большого объема памяти. Поэтому используется аналитический метод дешифрации.