2.5.4. Методика автоматической генерации тестов

Только совсем недавно исследователи приступили к изучению возможности использования показателей тестопригодности узлов схемы для целенаправленного улучшения алгоритмов автоматической генерации тестов, таких, как D-алгоритм или алгоритм, основанный на активизации пути. Практическая реализация таких алгоритмов усложняется проблемами выбора — выбора неисправности для обнаружения которой генерируется тест; выбора пути транспортировки неисправности; выбора входов устройства и их логических значений для поддержки или блокирования определенного активизированного пути. Традиционно выбор из некоторого числа возможных вариантов, удовлетворяющих установленному требованию, осуществляется либо произвольно, либо в соответствии с некоторым другим локальным или глобальным критерием выбора. В основу другого подхода может быть положен выбор значений управляемости, наблюдаемости и тестопригодности узлов схемы. Например, выбор начальной неисправности, обнаруживаемой тестом, может быть основан на выборе узла с наибольшим значением тестопригодности. Аналогично выбор решений на фазе прямого прохода вдоль активизированного пути может быть основан на более детальном анализе маршрутов с максимальной наблюдаемостью (с целью максимизации вероятности успешной транспортировки неисправности на наблюдаемый первичный выход). Кроме того, значения управляемости узлов могут быть использованы для определения «наилучшей» методики, удовлетворяющей требованию простоты установки фиксированных логических состояний на предопределенных узлах схемы, например в процессе согласования условий транспортировки в D-алгоритме или в процессе обратного прохода в алгоритме PODEM. Последний вариант более подробно анализируется в гл. 4.

2.6. О других системах анализа тестопригодности

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

2.6.1. СИСТЕМА ТМЕАS

В системе ТМЕАS, как и в САМЕLОТ, значения управляемости и наблюдаемости нормализуются в интервале от 0 (низкий уровень) до 1 (высокий уровень). Для вычисления значений управляемости схемы СY ее входам приписывают значения СY=1. Затем зависимость управляемостей остальных узлов схемы от состояний их входов представляется системой уравнений. В этих уравнениях используются коэффициенты передачи управляемости элементов СТF, которые определяют соотношение между значениями управляемостей входов и выходов элемента схемы. Коэффициенты передачи управляемости изменяются в зависимости от логической функции компонента схемы и являются функцией однородности вход – выходного отображения. Коэффициент СТF компонента схемы равен 1, если вход – выходное отображение однородно, и уменьшается до 0 по мере убывания однородности.

В отличие от САМЕLОТ в системе ТМЕАS при вычислении наблюдаемости схемы ОY сначала предполагается, что для первичных выходов OY=1. Затем значения ОY других узлов схемы связываются со значениями ОY выходов с помощью коэффициентов передачи наблюдаемости ОТF. Эти коэффициенты определяют меру вероятности того, что неисправность, появляющаяся на входах компонента схемы, будет распространяться на ее выходы, и вновь значения коэффициентов изменяются в пределах от 0 до 1 в соответствии с выполняемой логической функцией компонента. В системе ТМЕАS вычисление наблюдаемости не зависит от значений управляемости, вычисленной ранее. Для вычисления СY и ОY компонент схем, содержащих элементы памяти, тактовые шины и ветвления, разработаны специальные правила. Кратко они состоят в следующем. Элемент памяти представляется в виде элемента с дополнительными цепями связи, которые определяют зависимость последующего состояния элемента от его текущего состояния. Наличие шин тактовой синхронизации не учитывается. При вычислении управляемости в узлах ветвлений значение СY уменьшается но сравнению со значением СY при прямой передаче информации, отражая тот факт, что в точках ветвления нельзя установить различные логические значения, как зачастую требуется для активизации пути транспортировки неисправности. Эти правила отличаются от используемых в системе САМЕLОТ. Значение тестопригодности вычисляется как среднее геометрическое значений управляемости и наблюдаемости.

Ограниченность системы ТМЕАS, которая присуща и системе САМЕLОТ, заключается в том, что заданные формулы для вычисления значений СТF и ОТF по функциональным характеристикам элементов определяют тенденцию к получению чрезвычайно низких значений этих параметров для простейших схемных элементов (И, ИЛИ и т. д.), однако это не является серьезным недостатком, так как всегда при необходимости можно увеличить значения коэффициентов до требуемого уровня. Еще одно затруднение, общее для систем ТМЕАS и САМЕLОТ, возникает, когда встречаются узлы схемы, постоянно подключенные к одному из логических уровней. Возникает оно по той причине, что вычисление одного значения управляемости для каждого узла имеет тенденцию скрывать относительные трудности формирования двух возможных логических уровней. Решения этой проблемы предложены в следующих трех системах оценки тестопригодности.

2.6.2. СИСТЕМА ТЕSТ/80

В системе ТЕSТ/80 предлагается программа автоматической генерации тестов для цифровых схем. Подобно D-алгоритму в ней реализуется попытка установить множество путей, по которым неисправности внутренних узлов могут транспортироваться через схему и наблюдаться на ее выходах. Процедура выполняется за две фазы: определение пути от узла к выходу схемы и установление множества входных условий, способствующих активизации этого пути. В отличие от D-алгоритма в системе ТЕSТ/80 используется процесс, называемый анализом издержек, который позволяет идентифицировать оптимальный путь перехода в любое состояние. В действительности этот анализ представляет собой процедуру оценки свойств управляемости и наблюдаемости схемы.

Для каждого узла схемы вычисляются значения трех оценок сА — издержки на установку в узле А состояния 1; — издержки на установку в узле А состояния 0; dА—издержки на D-проход от узла А к выходу схемы. Издержки возрастают, когда возникают различные проблемы, усложняющие выполнение этих процедур.

В общем случае описываемые далее меры систем SСОАР ТЕSТSСREЕN позволяют вычислить значения управляемости узла отдельно для каждого логического уровня (в рассматриваемой системе сА и ). Если известна функция элемента, то оценки этих издержек на выходах некоторого элемента вычисляются суммированием следующих трех составляющих:

а) функции издержек управляемости входа;

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

в) составляющей, связанной с типом элемента.

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

Третья оценка, dА, является мерой наблюдаемости узла. Значение этой оценки на входе элемента вновь вычисляется суммированием трех составляющих:

а) оценки вероятности реализации D-распространения со входа элемента на его выход, которая является функцией сА и других входов элемента;

б) оценки издержек на D-распространение от выхода элемента до выхода схемы; если имеется несколько путей, то выбирается путь с наименьшими издержками;

в) оценки числа тактовых циклов, необходимых для передачи

значения D от узла на выход схемы.

Может показаться, что издержки dА равны 0, если А— выход схемы. Заметим, что принцип использования значений управляемости для вычисления наблюдаемости такой же, как в системе САМЕLОТ.

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

2.6.3. СИСТЕМЫ SСОАР И СОМЕТ

Система SСОАР является развитием системы ТЕSТ/80. Каждый узел схемы характеризуется шестью параметрами - комбинационными управляемостями 0 и 1, последовательностными управляемостями 0 и 1 и комбинационной и последовательностной наблюдаемостями. Они определяются следующим образом. Комбинационные управляемости, СС0 и СС1, определяются как минимальное число узлов, которые должны быть остановлены в определенное состояние, чтобы в заданном узле получилось логическое значение 0 или 1. Последовательностные управляемости SСО

и SС1 определяются аналогично как число «последовательностных узлов», которые необходимо остановить в определенное состояние. Последовательностный узел—это узел схемы, состояние которого фиксируется на один тактовый период. Таким образом узел, который необходимо поддерживать в состоянии логической 1 в течение шести тактов для транспортировки требуемого логического значения к заданному узлу, оценивается как шесть последовательностных узлов. Для входов схемы СС0=СС1==1, в то время как SС0=SС1=0 по определению.

Комбинационная и последовательностная наблюдаемости, С0 и S0, определяются как минимальное число узлов или последовательностных узлов соответственно, которые должны быть установлены в определенное состояние, чтобы неисправность транспортировалась от ее источника к выходу схемы. По определению, наблюдаемости выходов схемы равны 0.

Как и в системе ТЕSТ/80, управляемости и наблюдаемости входов и выходов элементов схемы связаны логической функцией, реализуемой этим элементом. Кроме того, их значения обратно пропорциональны вычисляемым параметрам узлов схемы.

В зарубежной литературе был описан модифицированный вариант алгоритма SСОАР, который удовлетворяет требованиям проектирования устройств на вентильных матрицах. Эта система, называемая СОМЕТ (Controllability and Observability MEasure for Test), включает дополнительный параметр тестопригодпости, называемый предсказуемостью. Предсказуемость является производной управляемости и характеризует меру способности или неспособности схемы к начальной остановке в известное состояние.

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

2.6.4. СИСТЕМА ТЕSТSСRЕЕN

Один из недостатков системы SСОАР состоит в том, что для цепи из n инверторов управляемость выхода равна n – 1. Однако реально управлять выходом n-го инвертора не намного труднее чем выходом первого. Для исключения этого недостатка в системе ТЕSТSСRЕЕN изменены определения наблюдаемости, значение которой определяется числом входов схемы, которые должны быть установлены в определенное состояние для достижения желаемого результата. Так, например, комбинационная управлявляемость определяется как число входов схемы, которые должны быть остановлены в определенное состояние для получения требуемого логического значения на заданном узле. Следовательно, для цепочки инверторов комбинационная управляемость выхода равна теперь 1.

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

2.6.5. СИСТЕМА V1СТОR

Программа анализа тестопригодности VICTOR (VLSI Indentifier of Controllability, Testability, Observability and Rrdundancy) была разработана с целью идентификации избыточных узлов схемы до начала процесса генерации тестов. Узел схемы является логически избыточным, если значения на выходах схемы не зависят от состояния узла для всех входных наборов или последовательности состояний. На практике это означает, что определенные неисправности на логически избыточном узле не могут быть обнаружены. Необходимо ли обнаруживать такие неисправности? Этот вопрос обсуждается в разд. 5.1. Предметом дискуссии, связанной с таким анализом, является вопрос о том, необходимо ли идентифицировать потенциально избыточные элементы схемы перед процедурой генерации тестов. Этот путь позволяет исключить ненужные затраты времени и, в конечном счете, бесполезные вычисления.

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

2.6.6. ЭНТРОПИЙНЫЕ МЕРЫ ТЕСТОПРИГОДНОСТИ

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

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

2.6.7. СРАВНИТЕЛЬНЫЙ АНАЛИЗ

Как обсуждалось, каждый из описанных здесь методов анализа тестопригодности в некоторых отношениях отличается от метода САМЕLОТ. Если эти различия направлены на увеличение точности предсказания тестопригодности, то достигается это ценой увеличения теоретической сложности процедуры анализа. Примером является вычисление отдельных показателей тестопригодности для двух логических уровней в системах ТЕSТ\80, SСОАР и ТЕSТSСRЕЕN, которое основано на анализе логического поведения элементов в процессе вычислений.

Другие особенности, как, например, независимость вычислении наблюдаемости от предварительно вычисленных значений управляемости в системе ТМЕАS, обусловливают уменьшение точности предсказания.

Ясно, что выбор соотношения между сложностью и точностью должен осуществляться разработчиком, в соответствии с его умением принять правильное решение и предназначением вычисляемых параметров тестопригодности. Система САМЕLОТ представляет одно из таких решений, которое рассматривается как удовлетворительное для практического использования в процессе проектирования. В других методах анализа выбраны иные соотношения между сложностью и точностью.