Последовательное и параллельное моделирование неисправностей

Данные моделирования этой схемы для одного входного набора ($$a=1, b=0, c=0, d=1, e=0$$) приведены в табл. 11.1, где строки таблицы соответствуют линиям этой схемы - машинным словам), а столбцы (биты) - моделируемым неисправным схемам. При этом в левом столбце приведены имена линий схемы (и логические выражения для внутренних линий), во втором слева столбце логические значения исправной схемы для каждой линии, и последующих столбцах (разрядах машинных слов) значения сигналов для каждой неисправной схемы. Например, третий слева столбец представляет значения сигналов на моделируемом входном наборе для схемы с неисправностью $$a\equiv 0$$. Очевидно, что для определения множества проверяемых неисправностей достаточно сравнить значения сигналов в последней строке, которая соответствует внешнему выходу схемы $$j$$. Поскольку исправная схема (второй столбец) имеет на внешнем выходе $$j=0 $$, то проверяются все неисправности, для которых $$j=1$$: $$b\equiv 1, c\equiv 1, e\equiv 1, f\equiv 1, g=1, h\equiv 1, i\equiv 1, j\equiv 1$$.

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

11.4 Параллельное моделирование в троичном алфавите

При параллельном методе моделирования можно использовать различные виды кодирования троичного алфавита $$E_{3}=\{0,1,u\}$$, которые были представлены в лекции 4. Рассмотрим для определенности дизъюнктивный метод кодирования, представленный в табл. 11.2. Напомним, что здесь каждая троичная переменная $$X^{*}$$ представлена двумя двоичными переменными $$X^0$$ и $$X^1$$. Соответственно моделирование одного вентиля в троичном алфавите выполняется с помощью двух булевых функций - компонент $$F^{0}$$, $$F^{1}$$, приведенных в табл. 11.3. При этом, например, моделирование вентиля И $$F=A^{*}\B^{*}$$ в троичном алфавите согласно табл.11. выполняется с помощью двух логических операций: $$F^{0}= A^{0}\vee B^{0}$$, $$F^{1}= A^{1}\ B^{1}$$ . Таким образом, фактически моделирование одного вентиля в троичном алфавите, как бы, заменяется моделированием двух вентилей в двоичном алфавите, что показано на рис. 11.4.

Допустим, что выполняется параллельное моделирование с 4-разрядными машинными словами. Пусть входы вентиля имеют текущие значения из троичного алфавита $$A^{*}=1$$, $$B^{*}=1$$. Тогда с учетом дизъюнктивного кодирования имеем:

Пусть в левом разряде моделируется исправная схема, во 2-м разряде - неисправность $$A 0$$, в 3-м разряде - $$B 0$$, в 4-м разряде -$$A 1$$ и в 5-м разряде - $$F 0$$. Тогда после внесения влияния неисправностей на входах имеем:

После выполнения логических операций $$F^0=A^0\vee B^0$$, $$F^1=A^1\ B^1$$ и внесения неисправности выхода вентиля получаем:

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

Иногда число проходов $$]N/P-1[$$, необходимое при параллельном методе удается несколько уменьшить за счет того, что несколько независимых неисправностей могут моделироваться в одном и том же разряде. При этом неисправности должны располагаться на линиях схемы, не влияющих друг на друга.

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

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

11.5 Параллельное моделирование в многозначных алфавитах

До недавнего времени в многозначных алфавитах (со значностью больше 4) этот метод распространения не получил, так как при увеличении значности алфавита резко падает скорость моделирования в виду сложности многозначных моделей логических элементов. Метод кодирования и единая система моделей на базе четырех компонент $$f^{0}, f^{D'}, f^{D}, f^{1}$$ позволяют существенно повысить скорость параллельного метода моделирования в многозначных алфавитах и сделать ее приемлемой для практического применения. При параллельном методе моделирования влияние неисправностей распространяется параллельно для группы $$р-1$$ неисправностей ($$р $$- разрядность инструментальной ЭВМ). При этом каждой линии схемы ставится в соответствие несколько машинных слов, число которых определяется количеством компонент в применяемом методе кодирования многозначных алфавитов. Для кодирования, представленного в табл. 7.1 , каждой линии схемы ставится в соответствие четыре машинных слова, как это показано на рис. 11.5. При моделировании логических элементов (в данном случае конъюнкции $$f=ab$$) используются функции $$f^{0}, f^{D'}, f^{D}, f^{1}$$. На рис. 11.5 приведены закодированные значения $$a=(0\,1\,E\,1\,u\,0)$$, $$b=(1\,1\,1\,H\,1\,u)$$, из которых согласно функциям $$f^{0}, f^{D'}, f^{D}, f^{1}$$ для этого вентиля получаем значения, приведенные на рис. 11.5, что согласно данному методу кодирования соответствует $$\tilde{f}=(0\,1\,Е\,H\,u\,0)$$. При вычислении $$f^{0}, f^{D'}, f^{D}, f^{1}$$ значения всех разрядов обрабатываются параллельно с помощью соответствующих поразрядных булевых операций. Напомним, что функции $$f^{0}, f^{D'}, f^{D}, f^{1}$$ основных вентилей таковы, что при равенстве компонент входов $$a^{D'}, a^{D}, b^{D'}, b^{D}$$ нулю сами функции $$f^{D'}, f^{D}$$ также равны нулю. Это дает возможность не вычислять их в том случае, когда соответствующие компоненты входов нулевые. При этом, естественно, надо иметь эффективный способ проверки на равенство нулю компонент входов. Структура модели логического элемента в многозначном алфавите, учитывающей указанные свойства, представлена на рис. 11.6. Заметим также, что внесение константных неисправностей также снижает число логических элементов, имеющих ненулевые компоненты $$f^{D'}, f^{D}$$. Экспериментальные исследования показывают, что в процессе моделирования относительно небольшая часть логических элементов имеет ненулевые компоненты $$f^{D'}, f^{D}$$. Это позволяет проводить моделирование в многозначных алфавитах, в основном, вычисляя две компоненты $$f^{D'}, f^{D}$$, что существенно повышает скорость моделирования.

Внесение неисправностей при моделировании в многозначных алфавитах (включая троичный) обычно производится с помощью специальных масок. Для рассматриваемого метода кодирования это может быть выполнено по следующим формулам: $$x^{0}=x^{0}\M_{1}\vee M_{2}$$, $$x^{D'}=x^{D'}\M_{1}$$, $$x^{D}=x^{D}\M_{1}$$, $$x^{l}=x^{l}\M_{1}\vee M_{3}$$. Здесь все переменные векторные, их длина равна разрядности машинного слова. Маски $$М_{1}$$, $$М_{2}$$ и $$М_{З}$$ определяют номер разряда в машинном слове и тип вносимой неисправности. Допустим, что неисправность вносится в $$j$$-ом разряде. Тогда маска $$М_{1}(М_{2},М_{3})$$ содержит все единицы (нули) кроме $$j$$-го разряда. Значения $$j$$-х разрядов $$М_{1}$$, $$М_{2}$$, $$M_{3 }$$ определяются типом вносимых неисправностей. Для исправной линии $$М_{1}(j)=1, М_{2}(j)=0, М_{З}(j)=0$$; для неисправностей const0 - $$М_{1}(j)=0, M_{2}(j)=1, M_{3}(j)=0$$; и для неисправностей const1 - $$М_{1}(j)=0, M_{2}(j)=0, M_{3}(j)=1$$. Следует отметить, что техника внесения неисправностей с помощью масок достаточно удобна и для моделирования кратных константных и сложных логических неисправностей. Все неисправности, входящие в кратную, должны заноситься в один и тот же разряд.

Ниже представлен псевдокод алгоритма параллельного моделирования неисправностей. Здесь, прежде всего, внешнее описание схемы (текстовое или графическое) транслируется в основную структуру данных - систему связанных таблиц, которая описана в лекции 5. Далее выполняется трансляция внешнего описания тестовых воздействий и инициализация табличной модели ДУ. Затем формируется список неисправностей ДУ, подлежащих моделированию. При этом в случае первого сеанса в него заносятся все модельные неисправности данного ДУ с анализом и устранением эквивалентных дефектов. В противном случае список считывается с диска, куда он был записан во время предыдущего сеанса. Далее выполняется основной цикл по неисправностям, в начале которого формируется текущая группа неисправностей, которая затем моделируется на всех тестовых наборах. Функция "смена_набора" вводит следующий тестовый набор и заносит события (изменения сигналов на внешних входах ДУ) в очередь (QJ) на моделирование. Основной является функция "моделирование_набора". В ней реализован событийный алгоритм моделирования в многозначном алфавите.

Существенным ограничением является то, что при параллельном методе моделирования функционирование логических элементов должно быть описано с помощью булевых функций. Это связано с тем, что основной выигрыш во времени при этом методе получается при выполнении логических операций, которые практически во всех современных ЭВМ реализуются параллельно над всеми разрядами машинных слов. Если элемент описан на функциональном уровне, например, с помощью ЯРП, то нужно каждую сложную функцию (или оператор) описать с помощью булевых функций. Так мы поступали с условным оператором $$\text{If } A\text{ THEN }z<-X\text{ ELSE }s<-Y$$, заменяя его булевой функцией $$s= AX\vee\line{A}Y$$ . Аналогично можно описать и другие операторы или функции. Сложность модели при этом существенно увеличивается.

Параллельное_моделирование_неисправностей(схема,тест) 
{
Ввод_схемы(); 
Ввод_теста(); 
Инициализация_схемы ();
 Генерация_сниска_неисправностей(); 
while(есть неисправности) /* цикл по неисправностям*/ 
{
Формирование_группы_неисправностей(); 
while(есть тестовые наборы) /*цикл по тестовым наборам*/
 {
Смена_набора(); /* ввод следующего набора */ Внесение_неисправностей_на_внешних_входах(); Моделирование_набора();
Внесение_неисправностей_на_внешних_выходах();
Проверка_обнаружения_неисправностей();
}	/* конец цикла по наборам */
Печать_непроверенных_неисправностей(); 
}  /* конец цикла по группам неисправностей */ Печать_полноты_теста(); Запись_непроверенных_неисправностей();
}
Моделирование_набора(); 
{
Инициализация(); 
while(есть события) 
{
if(есть изменение сигнала) 
{
Занесение нового значения в текущий массив;
 Запоминание номера контакта первого последователя;
 while(циклический список последователей не пуст)
 { 
Занесение элемента-последователя в очередь QJ;
}
while(очередь QJ не пуста) 
{
Выбор элемента-последователя из очереди QJ;
Подготовка данных для моделирования элемента;
 if(элемент входит в текущую группу неисправностей)  
 { 
внесение неисправностей на входах элемента;
 }
моделирование_элемента(); 
/* цикл по выходным контактам */ 
while(есть необработанный выход элемента)
{
if(неисправность контакта входит в текущую группу) 
if(новое значение ? старому значению)
	{
занесение события в очередь QJ; 
} /* конец цикла по выходным контактам */ 
}   /* конец цикла по событиям */ 
}

11.6 Параллельное по входным наборам моделирование неисправностей

В разделе 11.2 мы рассмотрели метод последовательного моделирования неисправностей. Для комбинационных схем часто применяется параллельный по наборам метод моделирования неисправностей, где фактически комбинируется параллельный и последовательный метод моделирования. При этом подходе одна неисправная схема моделируется на многих наборах, то есть в каждом разряде машинного слова моделируется схема на своем входном наборе. Таким образом, в двоичном алфавите одна неисправная схема одновременно моделируется на $$p$$ входных наборах, где $$p$$ - разрядность машинного слова. В остальном техника вычислений идентична параллельному методу, изложенному в 11.3 и основана на использовании параллельных поразрядных логических операций. По сравнению с предыдущем методом выигрыш может быть достигнут за счёт того, что если неисправность проверяется на одном из входных наборов, входящих в текущую группу, то нет смысла моделировать эту неисправность на оставшихся входных наборах.

Отметим, что при таком подходе используется, в основном, сквозное, а не событийное моделирование, поскольку события могут случиться только в некотором из $$p$$ векторов, которые моделируются параллельно. Это ведет к тому, что значения элементов схемы вычисляются на каждом векторе в порядке уровней ранжирования. В этом случае целесообразно использовать компилятивный метод моделирования. Пусть $$a<1$$ означает среднюю активность моделирования в схеме, то есть долю элементов, на входах которых случаются события (изменения сигналов) на моделируемых входных наборах. Тогда при данном методе моделируется в $$1/p$$ больше элементов. чем в событийном методе. Однако, поскольку одновременно моделируется $$p$$ векторов, данный метод является эффективным при $$p>1/a$$. Например, для $$p\ge 20$$ он будет эффективным, начиная со значения $$a=5\%$$. Общее ускорение этого метода равно $$p\cdot a$$. Очевидно, что большая разрядность инструментального компьютера дает большую эффективность. Авторы метода [11.5] использовали компьютер с $$p=256$$. Отметим, что данный метод с успехом используется для моделирования больших схем (до миллиона вентилей) на случайных входных наборах.

Для повышения эффективности комбинационная схема предварительно разбивается на максимальные одновыходные подсхемы .

Определение11.1 Максимальная одновыходная подсхема - это комбинационная древовидная схема, не имеющая разветвлений, с одним выходом.

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

Очевидно, что в основе высокого быстродействия рассматриваемого метода лежит организация параллельных вычислений в процессе прямой и обратной фазы. Эффективность организации параллельных вычислений зависит от используемого алфавита и системы многозначных функций в нем. В различных работах применяются различные алфавиты: в большинстве случаев используются простейший двоичный алфавит $$B_{2}=\{0,1\}$$ или троичный алфавит $$E_{3}=\{0,1,u\}$$, хотя известно и применение алфавитов большей значности [11.1].

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

Ключевые термины:

Последовательное моделирование - процесс моделирования для каждой неисправности выполняется отдельно -последовательно.

Параллельное по неисправностям моделирование - процесс моделирования выполняется параллельно (одновременно) для группы неисправностей.

Параллельное по наборам моделирование - процесс моделирования выполняется параллельно (одновременно) для группы входных наборов.

Краткие итоги

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

В разделе 11.1 определяются основные задачи моделирования неисправных логических схем в системах автоматизации проектирования ЦУ и связь с остальными компонентами САПР.

В разделе 11.2 описан последовательный метод моделирования неисправностей, когда неисправности обрабатываются поселедовательно и независимо друг от друга.

Раздел 11.3 посвящен параллельному методу моделирования, где группа неисправностей обрабатываются одновременно в двоичном алфавите.

В разделе 11.4 параллельный метод обобщается на троичный алфавит, что позволяет повысить адекватность.

В разделе 11.5 параллельный по наборам метод моделирования неисправностей распространяется на многозначные алфавиты.

В разделе 11.6 представлен параллельный по входным наборам метод моделирования, где для данной неисправности одновременно моделируется группа входных наборов.

Вопросы и упражнения

Где используется моделирование схем с неисправностями?

Что необходимо для моделирования неисправных схем?

Какие действия необходимо выполнить при моделировании неисправностей?

Какие преимущества имеет метод последовательного моделирования?

Какие недостатки имеет метод последовательного моделирования?

Сколько неисправностей одновременно моделируется в параллельном методе?

Как вносится влияние неисправностей в этом методе?

Выполните параллельное моделирование всех одиночных константных неисправностей для приведенной схемы рис. 11.9 на тестовом наборе (11111). (рис 11.9) Схема для упражнения 8 (параллельное моделирование неисправностей).

Каким образом выполняется переход на троичный алфавит в параллельном алфавите?

Как при этом изменяются быстродействие и затраты памяти?

Приведите основной алгоритм параллельного по неисправностям.

Чем отличается параллельный по наборам метод от параллельного по неисправностям?

Какой вид моделирования, событийный или компилятивный, целесообразно использовать в параллельном по наборам методе?

Определите максимальную одновыходную подсхему.

Что дает структуризация схемы на максимальные одновыходные подсхемы?