uzluga.ru
добавить свой файл
1

ОБ ОДНОМ АЛГОРИТМЕ ПОИСКА МАСОК

ДЛЯ СОКРАЩЕНИЯ ДИАГНОСТИЧЕСКОЙ ИНФОРМАЦИИ



С. В. Миронов, Н. В. Попов


Саратовский Государственный Университет, Саратов, Россия

Введение

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

Процесс диагностирования с использованием ДИ предполагает подачу на вход исследуемого ДУ диагностической последовательности, получения выходной последовательности и ее сравнение с реакциями в ДИ. Реакция в ДИ, идентичная полученной выходной последовательности, свидетельствует об исправности ДУ или о наличии в нем соответствующей неисправности.

Для современных ДУ объем ДИ, как правило, чрезвычайно велик и его сокращение представляет собой актуальную задачу.

К сокращению ДИ предложено множество подходов [1-10]. Большинство из них предполагает значительное сокращение словаря неисправностей за счет того, что вместо полной реакции на диагностический тест в словаре сохраняется некоторая компактная свертка этой реакции. В некоторых случаях компактная свертка заменяет и реакцию эталонного устройства. Некоторые из таких подходов связаны с использованием так называемых индивидуальных масок [8-10], когда в словаре неисправностей в качестве компактной свертки сохраняется маска и результат ее наложения на полную реакцию на диагностический тест.

Процесс диагностирования с использованием маски ДИ предполагает наблюдение выходной последовательности исследуемого ДУ, получение компактной свертки этой последовательности и сравнение последней со сверткой в ДИ.

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

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

^ 1. Определение основных понятий и постановка задач

Пусть рассматриваемое ДУ имеет выходов и множество есть множество его модификаций. Предполагаем, что на каждом выходе упомянутых ДУ может появиться только сигнал 0 или 1.

Пусть – диагностическая последовательность (тест) для рассматриваемого устройства, где , , – входные вектора. Тогда полную реакцию устройства на тест можно представить в виде бинарного вектора длины в котором на -ом месте стоит значение сигнала на выходном полюсе с номером после тестового воздействия с номером .

Представим ДИ для ДУ с множеством неисправностей в виде таблицы порядка , где строка с номером , , представляет полную реакцию устройства на диагностический тест . Не теряя общности будем предполагать, что все строки матрицы различны, т. е. нет ни одной пары устройств и , неразличимых с помощью представленной ДИ. В противном случае каждый класс неразличимых устройств можно заменить одним представителем.

Назовем точкой проверки пару номер тестового воздействия:номер выходного полоюса. Тогда маской назовем любую совокупность точек проверки.

Пусть имеется некоторое разбиение множества и пусть  – элементы этого разбиения. Поставим в соответствие каждому множеству некоторую маску . Множество всех обозначим . Построим по таблице и множеству масок таблицу следующим образом. Каждая строка таблицы соответствует элементу множества . Содержимое строки таблицы, соответствующей модификации , будут составлять значения точек проверки из , взятые из строки матрицы , соответствующей , в порядке их следования в . Построенную таким образом таблицу будем называть (по аналогии с [8]) «словарь неисправностей, построенный по маскам из ». Маску будем называть индивидуальной маской для каждого состояния из , а множество – совокупностью индивидуальных масок.

Нами будет исследована следующая задача [8]: для заданной ДИ требуется найти такую совокупность индивидуальных масок минимального объема, что словарь неисправностей, построенный по маскам из , обеспечивает для тестируемого ДУ ту же глубину диагностирования, что и исходная ДИ.

^ 2. Жадный алгоритм поиска совокупности индивидуальных масок

Поиск одной индивидуальной маски можно свести к задаче о покрытии множества следующим образом. Пусть задана диагностическая информация в виде СПР и требуется найти индивидуальную маску для устройства . Для каждой возможной точки проверки построим подмножество множества , в которое внесем все модификации , отличающиеся от состояния при использовании точки проверки . Таким образом, получим покрытие множества . Очевидно, что минимальному подпокрытию , , будет соответствовать минимальная индивидуальная маска .

Задача нахождения минимального подпокрытия множества является NP-полной. В [11] предлагается жадный алгоритм ее решения. Идея алгоритма состоит в следующем: строим , причем , а строится из добавлением элемента из , который покрывает наибольшее количество элементов множества , непокрытых элементами из . Временная сложность данного алгоритма составляет , емкостная сложность – .

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

Ниже предлагается алгоритм, который улучшит приведенную временную характеристику.

При описании алгоритма будем использовать следующие обозначения. Пусть  – некоторое подмножество множества , а  – высказывание, равное нулю (ложь) или единице (истина). Тогда через обозначим количество технических состояний из множества для которых значение в точке проверки равно . Обозначение будет соответствовать логической операции отрицания высказывания .


АЛГОРИТМ

Вход: Словарь полной реакции;  – множество технических состояний;  – максимальный объем одной индивидуальной маски.

Выход: – множество индивидуальных масок.

  1. Положить .

  2. Выполнить рекурсивный алгоритм , описанный ниже.

  3. Вернуть множество в качестве результата.


Алгоритм функционирует следующим образом:

  1. Если или или , то закончить вызов, иначе перейти к шагу 2.

  2. Найти такую точку проверки и такое значение , для которых величина достигает наибольшего значения, не превышающего , при условии .

  3. Если такой точки проверки не найдено – завершить вызов, иначе перейти к п. 3.

  4. Составить множества , .

  5. Включить точку проверки в маски для всех устройств .

  6. Выполнить последовательно два обращения ; , после чего закончить вызов.

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

Формирование индивидуальной маски с помощью предложенного алгоритма для каждой в отдельности модификации исправного устройства повторяет работу жадного алгоритма для поиска минимального покрытия. Действительно, шаг 2 алгоритма повторяет шаг исходного жадного алгоритма, на котором выбирается подмножество исходного множества, покрывающего максимальное количество элементов. Первый рекурсивный вызов на шаге 5 алгоритма соответствует повторению алгоритма для подмножества непокрытых элементов.

Часто индивидуальные маски для разных технических состояний имеют одинаковые элементы. Основная идея предложенного алгоритма состоит в поиске индивидуальных масок одновременно для всех технических состояний. Например, когда на шаге 2 алгоритм находит точку проверки, по значению которой можно отличить все состояния из от всех состояний из , то эта точка проверки должна быть включена во все маски, соответствующие состояниям из (что и делается на шаге 4), после чего необходимо дополнить эти маски так, чтобы они отличали друг от друга состояния из (первый рекурсивный вызов на шаге 5). Так как в результате этих действий сформированные на текущий момент маски для состояний из еще не могут различать эти состояния между собой и отличать их от состояний из , то алгоритм повторяется с дальнейшим анализом всего множества состояний, но с учетом того, что маски для множества состояний уже сформированы (второй рекурсивный вызов на шаге 5).

При задании алгоритму значения , превышающего , гарантируется получение масок, сохраняющих глубину диагностирования исходной ДИ. Уменьшая значение можно регулировать объем отфильтровываемой ДИ за счет ухудшения глубины диагностирования. Устанавливая значение , не превышающее , мы отсекаем от получаемой маски те точки проверки, которые добавляются в последнюю очередь и, в силу характера алгоритма, отличают между собой малое количество модификаций устройства.

^ 3. Оценка эффективности предложенных алгоритмов

Оценка работы алгоритма была проведена на ДИ для ряда реальных схем, представленных в каталогах ISCAS’85 [12] и ISCAS’89 [13], сгенерированной с помощью наборов тестовых векторов HITEC [14]. Приводимые ниже данные получены в результате численных экспериментов на PC Pentium D, 2.8 GHz, 2 GB RAM. Программная реализация алгоритма, описанного в предыдущем разделе, была выполнена нами на языке .

В первой серии экспериментов для всех наборов ДИ запускался алгоритм получения индивидуальных масок без установки ограничений их объема. Затем по полученным маскам были построены словари неисправностей. Результаты экспериментов приведены в Табл. 1.



Таблица 1

Получение словарей неисправностей с помощью индивидуальных масок

без ограничений объема


Схема

Количество бит полной реакии на тест

Число модификаций

Объем полной ДИ, бит

Объем совокупности масок, бит

Объем максимальной маски, бит

Средний объем масок, бит

Объем словаря неисправностей, бит

Доля сокращенной ДИ от полной ДИ

1

2

3

4

5

6

7

8

9

C432

700

493

345100

2047

90

4,15

23996

6,95%

C1355

6336

931

5898816

4150

157

4,46

67836

1,15%

C1908

3450

1014

3498300

5032

124

4,96

75518

2,16%

C2670

14280

2196

31358880

10173

439

4,63

180336

0,58%

C3540

7700

2367

18225900

11063

197

4,67

177780

0,98%

S444

13440

192

2580480

717

40

3,73

12048

0,47%

S526

13548

139

1883172

513

17

3,69

8625

0,46%

S713

3979

344

1368776

1184

99

3,44

18296

1,34%

S820

21185

713

15104905

2737

204

3,84

50094

0,33%

S1196

6090

1164

7088760

5035

321

4,33

75146

1,06%

S1423

750

294

220500

1272

57

4,33

16146

7,32%

S1494

23655

1361

32194455

6329

317

4,65

114398

0,36%


Как видно из таблицы, полученные с помощью алгоритма маски позволяют сократить диагностическую информацию более чем на 90%.

В следующей серии экспериментов алгоритм запускался с установкой ограничения на объем получаемой маски. В Табл. 2 приведены результаты этих экспериментов при ограничении объема маски величиной .

Таблица 2

Получение словарей неисправностей с помощью индивидуальных масок

с ограниченным объемом


Схема

Объем совокупности масок, бит

Объем максимальной маски, бит

Средний объем масок, бит

Объем словаря неисправностей, бит

Доля сокращенной ДИ от полной ДИ

Ухудшение диагностического разрешения

Доля словаря с ограничениями от словаря без ограничений

1

2

3

4

5

6

7

8

C432

1482

4

3,01

17781

5,15%

0,18%

74,10%

C1355

3052

5

3,28

51366

0,87%

0,07%

75,72%

C1908

3668

5

3,62

56422

1,61%

0,07%

74,71%

C2670

7437

6

3,39

136560

0,44%

0,03%

75,73%

C3540

8061

6

3,41

132750

0,73%

0,03%

74,67%

S444

486

4

2,53

8352

0,32%

0,20%

69,32%

S526

353

4

2,54

6065

0,32%

0,18%

70,32%

S713

870

4

2,53

13900

1,02%

0,18%

75,97%

S820

1914

5

2,68

36103

0,24%

0,09%

72,07%

S1196

3723

5

3,2

56778

0,80%

0,07%

75,56%

S1423

859

4

2,92

11190

5,07%

0,24%

69,31%

S1494

4034

5

2,96

75383

0,23%

0,05%

65,90%


В качестве количественной меры глубины диагностирования была использована величина «диагностическое разрешение» [15] – количество различимых между собой пар модификаций устройства к общему числу пар модификаций. Как показали эксперименты, дополнительное сокращение объема словаря неисправностей почти на четверть приводит к потере диагностического разрешения не более чем на 0.3%.

Заключение

Приведенные в предыдущем разделе данные решения задачи сокращения ДИ с помощью предложенного жадного алгоритма свидетельствуют о его достаточной эффективности. В самом деле, как следует из табл. 1, отфильтрованная с помощью найденных алгоритмом масок ДИ составляет от 0.5% до 8% (в среднем 4.3%) от объема исходной ДИ. Таким образом, в среднем 95% объема исходной ДИ является избыточным, т.е. его удаление не влияет на глубину диагностирования тестируемого ДУ.

Таким образом, найденные с помощью предложенного алгоритма маски дают значительный эффект по сокращению ДИ. Что касается времени работы ГА для рассмотренных схем, то оно составляло от нескольких миллисекунд до полутора часов на PC, характеристики которого приводились в разделе 3. В практическом плане такие затраты вполне приемлемы.

Список литературы

  1. Ярмолик В. Н. Контроль и диагностика цифровых узлов ЭВМ. Мн.: Наука и техника, 1988.

  2. Pomeranz I., Reddy S. M. On the generation of small dictionaries for fault location // Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design (ICCAD ’92), 1992. - P. 272-279.

  3. Ryan P. G., Fuchs W. K., Pomeranz I.  Fault dictionary compression and equivalence class computation for sequential circuits // Proceedings of IEEE International Conference on Computer-Aided Design (ICCAD’93), 1993. - P. 508-511.

  4. Boppana V., Hartanto I., Fuchs W. K. Full fault dictionary storage based on labeled tree encoding // Proceedings of 14th VLSI Test Symposium, 1996. - P. 174-179.

  5. Chess B., Larrabee, T. Creating small fault dictionaries // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 1999. - Vol. 18. - № 3. - P. 346-356.

  6. Arslan B., Orailoglu A. Fault dictionary size reduction through test response superposition // Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers (ICCD’02), 2002. - P. 480-485.

  7. Шаршунов С. Г. Особенности диагноза технического состояния многовыходных объектов с использованием таблиц неисправностей // Автоматика и телемеханика. - 1973. - № 12. - С. 161 - 168.

  8. Чипулис В. П. Методы предварительной обработки и формы задания диагностической информации для поиска неисправностей дискретных устройств // Автоматика и телемеханика. - 1977. - № 4. - С. 165-175.

  9. Сперанский Д. В. Об одном подходе к решению задач сокращения объема диагностической информации // Автоматика и телемеханика. - 1984. - № 3. - С. 151-160.

  10. Миронов С. В., Сперанский Д. В. Генетические алгоритмы для сокращения диагностической информации // Автоматика и телемеханика. - 2008. - № 7.- С. 146-156.

  11. Chvatal V. A greedy heuristic for the set-covering problem // Mathematics of operations research. - 1979. -  Vol. 4, № 3. - P. 233-235.

  12. Brglez F., Bryan D., Kozminski K. Combinational profiles of sequential benchmark circuits // Proceedings of 1989 International Symposium on Circuits and Systems. - Portland, OR, USA: 1989. - P. 1929-1934.

  13. Brglez F., Fujiwara H. A neutral netlist of 10 combinational benchmark circuits and a target translator in fortran // Proceedings of 1985 International Symposium on Circuits and Systems. - Kyoto, Japan: June 1985. – P. 663-698

  14. Niermann T. M., Patel J. H. HITEC: A Test Generation Package for Sequential Circuits // Proceedings of the European Design Automation Conference (EDAC). - 1991.- P. 214-218.

  15. Rudnick E. M., Fuchs W. K., Patel J. H. Diagnostic fault simulation of sequential circuit // Proceedings of 1992 International Test Conference. - Baltimore, ML, USA: 1992. - P. 178-186.