Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

ОБРАТНЫЙ АЛГОРИТМ ПАРАЛЛЕЛЬНЫХ ПРОЦЕДУР ДИАГНОСТИРОВАНИЯ ДИСКРЕТНЫХ ОБЪЕКТОВ

Тюлюш С.Т. 1
1 ФГБОУ ВО «Калмыцкий государственный университет имени Б.Б. Городовикова»
Современное общество не представить без цифровых вычислительных устройств. Стоимость дискретных объектов (цифровых плат, блоков, модулей) зависит от быстрого и качественного диагностирования, то есть от процесса обнаружения и устранения дефектов. Поэтому исправность объекта является важным этапом при производстве дискретных объектов. В статье предлагается новый алгоритм диагностирования дискретных объектов и проводится анализ этого алгоритма. Новый алгоритм назван обратным алгоритмом. Обратный алгоритм параллельных процедур диагностирования сравнивается с параллельным алгоритмом и ν-процедурой поиска дефектов с реверсированием теста. Для анализа эффективности обратного алгоритма рассматриваются примеры. В примерах анализируется диагностирование нескольких дискретных объектов одного типа, в каждом из этих объектов имеется дефект. Рассматриваются случаи, когда дискретные объекты имеют различное число дефектов и одинаковое число дефектов. Сравнивается обратный алгоритм с параллельной процедурой и ν-процедурой поиска дефектов с реверсированием теста. В результате рассмотренных примеров доказано, что обратный алгоритм дает возможность сокращения суммарных временных затрат на обнаружение дефектов, когда число дефектов больше во второй половине теста. И таким образом доказана эффективность нового алгоритма, по сравнению c ν-процедурой поиска дефектов с реверсированием теста, если число дефектов больше во второй половине теста.
дискретные объекты
параллельные алгоритмы диагностирования
диагностирование дискретных объектов
1. Бородин С.М. Основы технической диагностики электронных средств: учебное пособие. Ульяновск: УлГТУ, 2019. 48 с.
2. Ответчиков Н.Е. Надежность и диагностирование цифровых устройств и систем управления // Международный студенческий научный вестник. 2020. № 6. URL: https://eduherald.ru/ru/article/view?id=20330 (дата обращения: 12.12.2022).
3. Параллельные методы и алгоритмы: учебное пособие. М.: МАДИ, 2020. 176 с.
4. Гафаров Ф.М., Галимянов А.Ф. Параллельные вычисления: учебное пособие. Казань: Издательство Казанского университета, 2018. 149 с.
5. Добржинская Т.Ю., Рогова О.С., Алентьева Е.Р. Исследование современных методов тестирования и диагностики компьютерных систем // Технические науки в России и за рубежом: материалы VIII Международной научной конференции (Краснодар, июнь 2019 г.). Краснодар: Новация, 2019. С. 27–29. [Электронный ресурс]. URL: https://moluch.ru/conf/tech/archive/332/15128/ (дата обращения: 12.12.2022).
6. Никифоров С.Н. Теория параллельного диагностирования. Дискретные объекты. СПб.: Государственный архитектурно-строительный университет, 2009. 142 с.
7. Никифоров С.Н., Тюлюш С.Т. Эффективность параллельных алгоритмов диагностирования дискретных объектов // Вестник гражданских инженеров. 2011. № 2 (27). С. 187–190.

Жизнь современного человека тесно связана с различными цифровыми устройствами, элементами которых являются дискретные объекты (ДО). Важным этапом производства ДО является обнаружение и исправление дефектов, которое называется диагностированием.

Одним из основных понятий в диагностировании, где определяется исправность объекта, является понятие алгоритма диагностирования.

«Алгоритм диагностирования (АД) – это совокупность предписаний о проведении диагностирования. Он устанавливает состав и порядок проведения так называемых элементарных проверок» – определение из учебника С.М. Бородина «Основы технической диагностики электронных средств» [1].

Автором работы [2] отмечается: «C каждым днем происходит бурное усложнение процессов на автоматизированных системах управления, на сегодняшний день невозможно обойтись без использования контрольно-измерительных приборов. В основном используются дискретные устройства (цифровые устройства)».

Основной причиной параллелизма является «сокращение времени вычисления алгоритма. Поэтому для анализа эффективности алгоритмов диагностирования важна оценка времени выполнения алгоритма» [3]. Работы многих авторов уделяются распараллеливанию алгоритмов, которые базируются на математических методах параллельных вычислений. Например, авторы работ [3, 4] рассматривают методы и средства параллельных вычислений.

Исследованию методов тестирования и диагностирования компьютерных систем посвящена работа [5]. В ней говорится, что одним из способов «борьбы с неисправностями компонентов автоматизированных систем» являются «диагностические процедуры, позволяющие обнаруживать неисправность».

А в работе [6] автор рассмотрел множество алгоритмов диагностирования дискретных объектов. «В это множество входят алгоритмы-процедуры, которые являются элементами этого множества: например, к элементам множества относятся параллельная процедура с повторными запусками теста, параллельная процедура с продолжением теста, параллельная процедура с неполными возвратами теста, ν-процедура, ν-процедура с неполными возвратами теста и другие. Каждый алгоритм-процедура диагностирования дискретных объектов описывается аналитической формулой, которая вычисляет суммарные временные затраты» [6]. Автором было доказано, что параллельные алгоритмы имеют выигрыш в суммарных временных затратах (СВЗ) в отличие от последовательных алгоритмов диагностирования.

При параллельном диагностировании одновременно подается тест длиной T. Тест подается в некоторое множество дискретных объектов, и сравниваются выходные сигналы с идентичными выходами «с целью вычисления функции неравнозначности (ФН)» [6].

Выше сообщалось, что в процессе диагностирования группы однотипных ДО параллельная и v-процедура, позволяет повысить быстродействие [6, 7].

Цель исследования – описать новый алгоритм диагностирования дискретных объектов и доказать, что новый алгоритм является более выигрышным в СВЗ, чем параллельные алгоритмы-процедуры диагностирования ДО. Новый алгоритм назовем обратным алгоритмом.

Для того чтобы доказать, что обратный алгоритм имеет выигрыш по сравнению с параллельной и ν-процедурой диагностирования ДО, приведем примеры.

Сравним обратный алгоритм с параллельной процедурой поиска дефектов с реверсированием теста.

Пусть диагностируется три ДО (N = 3), с разными дефектами μ1 = 4 – количество дефектов первого объекта, μ2 = 2 – количество дефектов первого объекта, μ3 = 6 – количество дефектов первого объекта. Длина теста T = 200, t0 и tk – начальный и конечный векторы теста соответственно. Пусть missing image file, missing image file, missing image file, missing image file – время поиска дефектов в первом объекте, missing image file, missing image file, missing image file – время поиска дефектов в первом объекте, missing image file, missing image file, missing image file, missing image file, missing image file, missing image file – время поиска дефектов в первом объекте.

Временная диаграмма параллельной процедуры изображена на рис. 1. На основании рисунка имеем следующее аналитическое выражение [6]:

missing image file

или, в общем виде,

missing image file, (1)

где обозначили N – количество объектов, missing image file – время поиска i-го дефекта в j объекте, μ – количество дефектов в ДО. Следовательно, согласно полученной формуле (1)

missing image file

условных единиц.

Временная диаграмма обратной параллельной процедуры представлена на рис. 2.

Согласно рис. 2 сначала тест подается одновременно на несколько ДО, в примере три ДО, и после того, как был обнаружен первый дефект в каждом объекте, через время missing image file, missing image file, tk, возвращается в состояние t0. После того, как был устранен обнаруженный первый дефект, тест запускается в обратном порядке (рис. 2), в отличие от параллельного, который повторяется заново (рис. 1).

missing image file

Рис. 1. Временная диаграмма параллельной процедуры поиска дефектов с реверсированием теста (N = 3, μ1 = 4, μ2 = 2, μ3 = 6)

Основываясь на рис. 2, СВЗ для обратного алгоритма-процедуры диагностирования трех объектов определяются с помощью выражения

Тобрат. missing image file

Тобрат. missing image file

missing image file

условных единиц или, в общем виде,

Тобрат. missing image file. (2)

missing image file

missing image file

Рис. 2. Временная диаграмма обратного алгоритма диагностирования ДО (N = 3, μ1 = 4, μ2 = 2, μ3 = 6)

Очевидно, что имеет выигрыш обратный алгоритм по сравнению с параллельным алгоритмом и составляет

w = 1288 / 1208 = 1.07,

в общем виде:

missing image file. (3)

Во временной диаграмме (рис. 2) обратного алгоритма заметим, что чем больше дефектов обнаруживаются во второй половине теста, тем меньше СВЗ, то есть чем меньше величина missing image file.

Итак, число всех обнаруживаемых дефектов μ можно разбить на два подмножества:

− μ1 – множество дефектов, обнаруженных в первой половине теста;

− μ2 – множество дефектов, обнаруженных во второй половине теста;

Пусть tсредμ1 = Т / 4 – это среднее время обнаружения всех дефектов подмножества μ1, tсредμ2 = 3Т / 4 – среднее время подмножества μ2. Тогда формулу (3) можно преобразовать:

missing image file. (4)

missing image file

Рис. 3. Изменение коэффициента соотношения w между СВЗ параллельной процедуры диагностирования ДО и СВЗ при обратном алгоритме параллельного алгоритма в зависимости от величины

Графически w представлен на рис. 3. График показывает соответствие w между СВЗ параллельной процедуры и СВЗ при обратном алгоритме параллельной процедуры с реверсом в зависимости от величины μ1 / μ2. То есть соответствие между μ1 и μ2, при этом длина теста T = 100, количество обнаруживаемых дефектов μ = 20, missing image file, а N = 5 – число ДО.

Анализируя график рис. 3, можно сделать выводы о том, что обратный алгоритм параллельной процедуры обнаружения дефектов в дискретных объектах:

1. Имеет выигрыш в СВЗ по сравнению с параллельным алгоритмом, когда μ2 > μ1.

2. При μ2 = μ1 алгоритмы с точки зрения временных затрат адекватны.

3. При μ2 < μ1 применение обратного алгоритма неэффективно, то есть не имеет выигрыша в СВЗ.

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

Сравним обратный алгоритм с ν-процедурой поиска дефектов с реверсированием теста.

Пусть даны три ДО (N = 3 – количество объектов) с одинаковым количеством дефектов μ2 = μ1 = 2, длина теста T = 30, t0 и tk – начальный и конечный векторы теста соответственно, missing image file, missing image file, missing image file, missing image file, missing image file, missing image file, где missing image file – время поиска i-го дефекта в j-м ДО, missing image file, missing image file.

Временная диаграмма для ν-процедуры, которая может быть интерпретирована как ориентированный граф, вершины которого соответствуют состояниям ДО в моменты обнаружения дефектов, а на дугах задана числовая функция значений времен поиска обнаруженного дефекта, приведена на рис. 4.

Суммарные временные затраты (СВЗ), на поиск всех дефектов в ДО по ν-процедуры, в соответствии с формулой (1):

missing image file

где missing image file – максимальное время поиска 1-х дефектов

missing image file – максимальное время поиска 2-х дефектов

Временная диаграмма обратной алгоритма ν-процедуры показана на рис. 5. Из рисунка видно, что, в отличие от ν-процедуры, тест на ДО подается в обратном порядке, и после обнаружения первых дефектов во всех трех ДО, через время missing image file (это максимальное время поиска дефекта), реверсируется в исходное состояние t0 (рис. 5). После устранения обнаруженного дефекта тест также подается в обратном направлении и также после обнаружения дефектов реверсируется в исходное состояние t0, через время missing image file. Последний прогон теста из состояния tк в t0, на котором не обнаруживается ни одного дефекта, свидетельствует об исправности ДО.

missing image file

Рис. 4. Временная диаграмма ν-процедуры с реверсом обнаружения дефектов (N = 3,μ = 2)

missing image file

Рис. 5. Временная диаграмма обратной процедуры диагностирования поиска дефектов (N = 3,μ = 2)

Суммарные временные затраты обратного алгоритма, согласно рис. 5 получим выражение

missing image file.

Заметим, что missing image file.

Следовательно, для вычисления суммарных временных затрат обратного алгоритма используем следующую формулу:

missing image file

missing image file. (5)

Согласно формуле (5) суммарные временные затраты обратного алгоритма

missing image file

missing image fileу.е.

Соответственно, выигрыш во времени от применения обратного алгоритма по сравнению с v-процедурой:

w = 79 / 71 = 1,11 у.е.

В общем виде:

missing image file. (6)

Найдем предел w между временными затратами при v-процедуре и временными затратами при обратном алгоритме. Пусть max t, min t → T

missing image file.

Предел w равен 1 + μ, т.е. выигрыш от применения обратного алгоритма по сравнению с v-процедурой всегда есть.

missing image file

Рис. 6. Выигрыш обратного алгоритма по сравнению с v-процедурой

На риc. 6 построен график w в зависимости от количества дефектов.

Как показывает график рис. 6, обратный алгоритм обнаружения дефектов в ДО обеспечивает выигрыш, когда дефекты обнаруживаются в конце теста. Поэтому если дефекты обнаруживаются во второй половине теста, то использование обратного алгоритма поиска дефектов является эффективнее ν-процедуры поиска дефектов с реверсированием теста.

Таким образом, новый алгоритм более эффективный по сравнению с параллельной процедурой и ν-процедурой поиска дефектов с реверсированием теста, когда число дефектов, обнаруживаемых во второй половине теста, больше числа дефектов, обнаруживаемых в первой половине теста. Поэтому обратный алгоритм более эффективен, чем параллельная процедура и ν-процедура, то есть имеет наименьший СВЗ, когда наибольшее число дефектов обнаруживается в конце теста.


Библиографическая ссылка

Тюлюш С.Т. ОБРАТНЫЙ АЛГОРИТМ ПАРАЛЛЕЛЬНЫХ ПРОЦЕДУР ДИАГНОСТИРОВАНИЯ ДИСКРЕТНЫХ ОБЪЕКТОВ // Современные наукоемкие технологии. – 2022. – № 12-1. – С. 69-75;
URL: https://top-technologies.ru/ru/article/view?id=39439 (дата обращения: 23.06.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674