Построение ДЗ P3 в случае коллективных диагностических проверок.
Коллективные диагностические проверки
В случае коллективных проверок один из фрагментов назначенный на данный временной такт решается всеми свободными ЭМ. Далее происходит сравнение результатов.
[+]:суммарное количество эквивалентных становиться больше чем при проведении парных проверок.
Под эквивалентным количеством проверок подразумевается общее количество сравнений результатов.
[-] :более сложная организация проведения проверок и более сложная организация системы сравнения полученных результатов.
Если есть n — количество машин в ВС, F(τ) — функция плотности загрузки, k — количество машин участвующих в проверке ( коллективной ).
Алгоритм построения загрузки 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 количество эквивалентных проверок.
В качестве исходных данных выступает ДЗ P2 и ДГ. В целом построение ДЗ P3 аналогично построению такой диаграммы для парных диагностических проверок. Единственное отличие — после реализации проверок предусмотренных ДЗ P3 в ДГ добавляется не существующие реально связи, обусловленные алгоритмом проведения коллективных проверок.
В ОУВС процесс решения прикладных задач можно разделить на 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
Точная структура полученная в результате работы алгоритма ДГ заранее не известна. Это накладывает ограничения на использование табличного метода дешифрации, так как его использование требует в данном случае очень большого объема памяти. Поэтому используется аналитический метод дешифрации.
