русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2013-12-23; просмотров: 793; Нарушение авторских прав


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

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

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

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

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

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

Если есть 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 количество эквивалентных проверок.

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

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



<== предыдущая лекция | следующая лекция ==>
Алгоритм формирования ДЗ P2 путем подбора количества доступных ЭМ | Алгоритм построения ДЗ P1


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.007 сек.