Applying ROBDDS for logical circuit delay testing.pdf Введение Надежность сложных физических систем зависит от надежности составляющих их компонент, в частности от надежности управляющих компонент, которые, как правило, являются логическими схемами высокой производительности. Высокая производительность - это, в первую очередь, высокая скорость выполнения операций, определяемая задержками критических путей, характеризующихся максимальной задержкой распространения сигнала от входа до выхода схемы. Эта задержка незначительно увеличивается и определяет тактовую частоту работы логической схемы. Однако в схемах высокой производительности часто возникают непредусмотренные емкости, индуктивности, сопротивления и т.д. Это приводит к дополнительным задержкам некоторых путей, которые невозможно рассчитать традиционными физическими методами. Такие задержки рассматриваются как неисправности схемы и находятся алгоритмами дискретной математики, то есть логическими методами. Одной из общепринятых на практике моделей таких неисправностей являются неисправности задержек путей (Path Delay Faults (PDFs)). Они обнаруживаются парами тестовых наборов (v1, v2). Среди неисправностей задержек путей выделяют робастно и не робастно тестируемые неисправности. Неисправность задержки пути (PDF) является робастно тестируемой, если существует пара тестовых наборов, на которой она обнаруживается независимо от наличия или отсутствия задержек других путей схемы. Неисправность задержки пути является не робастно тестируемой, если она может быть обнаружена на подходящей тестовой паре только в отсутствие задержек других путей. Обнаружение робастно тестируемых неисправностей позволяет однозначно определить путь в схеме, на котором эта неисправность проявляется. Выделение неисправных путей может быть использовано для коррекции схемы с целью устранения выявленных задержек, в том числе логическими методами за счет подключения дополнительных подсхем. Устранение задержек дает возможность повысить быстродействие схемы. В работе дается описание процедуры построения ROBDD-графа, представляющего все пары соседних тестовых наборов для робастно тестируемых неисправностей задержек путей, и отмечаются его свойства. Исследуются возможности пересечений графов, построенных для различных путей схемы. Результаты этих исследований используются для изложения основных принципов построения тестовых последовательностей для робастно тестируемых неисправностей задержек путей. 1. Построение ROBDD-графа, представляющего все тестовые пары для пути комбинационной схемы, и его свойства Опишем основные идеи, лежащие в основе получения всех тестовых пар соседних наборов, обнаруживающих робастно тестируемые неисправности задержек пути, и их компактного представления в виде ROBDD-графа Rrob. В работе [1] на основе анализа эквивалентной нормальной формы (ЭНФ) комбинационной схемы (комбинационной части последовательностной схемы) сформулированы требования к паре (v1, v2) тестовых наборов для робастно тестируемых неисправностей задержек путей, позволяющие строить эти наборы. Однако ЭНФ - громоздкая формула даже для простых логических схем. В работе [2] предлагается метод построения наборов v2 тестовых пар на основе анализа И, ИЛИ деревьев, более компактно задающих ЭНФ, и анализа Structural Synthesized Binary Decision Diagrams (SSBDD-графов). Тем не менее для реальных схем эти деревья и графы по-прежнему остаются громоздкими, а использование композиций этих деревьев и графов существенно усложняет алгоритмы поиска тестовых пар. В работе [3] предложен более эффективный в смысле вычислительных затрат подход к поиску тестовых пар для робастно тестируемых неисправностей задержек путей. Он основан на использовании операций над ROBDD-графами. Операции над такими графами характеризуются полиномиальной сложностью. Они выполняются над ROBDD-графами, построенными для фрагментов комбинационных схем (фрагментов комбинационных составляющих последовательностных схем). Сначала находится функция, задающая булеву разность (Boolean Difference) для рассматриваемого пути, компактно представляемая ROBDD-графом R(Dpath). R(Dpath) получается перемножением ROBDD-графов, задающих функции наблюдаемостей для подсхем, порожденных рассматриваемым путем. Речь идет о подсхемах, выход которых совпадает с выходом некоторого элемента рассматриваемого пути. Входами подсхем являются входы комбинационной схемы (комбинационной части последовательностной схемы) и вход этого же элемента пути. Полученный в результате перемножения ROBDD-граф представляет тестовые наборы (булевы векторы) v2 для обоих (противоположных) перепадов значений сигналов рассматриваемого пути. Противоположные перепады в англоязычной литературе называют rising transitions и falling transitions. Следует иметь в виду, что задержки противоположных перепадов одного и того же пути могут быть различными. Предлагается [3] отделить наборы v2 противоположных перепадов друг от друга и компактно представить их ROBDD-графами Rrise и Rfall соответственно. Далее из этих графов получаем [3] ROBDD-граф Rrob, компактно представляющий тестовые пары для робастно тестируемых неисправностей задержек данного пути: двух неисправностей, по одной для каждого из противоположных перепадов значений сигналов этого пути. Граф Rrob не содержит переменной xi, отмечающей начало рассматриваемого пути. Путь от корня графа Rrob до его 1-терминальной вершины представляет конъюнкцию (троичный вектор), такую, что булев вектор в пространстве (n-1) переменных: x1,…, xi-1, xi+1, …, xn, обращающий эту конъюнкцию в единицу, задает тестовую пару (v1, v2) в пространстве n переменных. Один из векторов пары получается приписыванием переменной xi значения 0, а другой - значения 1. Здесь n число входов комбинационной схемы (комбинационной составляющей последовательностной схемы). Известно [1], что если путь робастно тестируемый, то для него существует тестовая пара, образованная соседними булевыми векторами, отличающимися значением переменной, сопоставляемой началу рассматриваемого пути. Это значит, что для робастно тестируемого пути находится соответствующий непустой ROBDD-граф Rrob. Из тестовой пары соседних булевых векторов можно сформировать фрагменты тестовой последовательности, представленные тройками булевых векторов (либо (v1, v2 v1), либо (v2, v1, v2)). Речь идет о тестовой последовательности для заданного подмножества путей комбинационной схемы (комбинационной составляющей схемы с памятью). Каждый фрагмент обнаруживает задержки инверсных перепадов сигналов рассматриваемого пути и характеризуется минимальным потреблением мощности. Использование тестовых пар, не являющихся соседними векторами [4-9] (это имеет место в применяемых на практике методах сканирования), может приводить к фрагментам тестовой последовательности для одного пути из четырех векторов, то есть в целом к более длинным тестовым последовательностям для заданного подмножества путей. Отметим, что в этом случае для каждого из путей соответствующий ему фрагмент последовательности характеризуется большим потреблением мощности. 2. О пересечении ROBDD-графов Rrob различных путей комбинационной схемы Будем иметь в виду, что при тестировании неисправностей, в частности в процессе изготовления интегральной схемы, очень важно использовать тестовые последовательности, ориентированные на потребление, по возможности, меньшей мощности. Дело в том, что тестовые последовательности, как правило, потребляют большую мощность, чем последовательность примерно той же длины в рабочем режиме функционирования проектируемой схемы. Не учитывая этот факт, можно разрушить схему в процессе тестирования при ее изготовлении, в то время как схема могла бы корректно функционировать в рабочем режиме. В нашем распоряжении для каждого пути схемы имеется множество всех тестовых пар соседних булевых векторов, компактно представленных ROBDD-графом Rrob. В связи с этим естественно ожидать дополнительных возможностей по снижению потребляемой при тестировании мощности. Эти возможности связаны с пересечением ROBDD-графов различных путей схемы. Напомним, что ROBDD-графы порождают ортогональные ДНФ (ОДНФ), конъюнкции (троичные векторы) которых представляются простыми цепями, соединяющими корень графа с его 1 терминальной вершиной. Будем называть в дальнейшем конъюнкцию (троичный вектор) ОДНФ конъюнкцией (троичным вектором) соответствующего ROBDD-графа. Назовем два ROBDD-графа ортогональными, если их логическое произведение (их пересечение) пусто. Иначе графы не ортогональны. Если графы ортогональны, то любая конъюнкция (троичный вектор) одного графа ортогональна каждой конъюнкции (троичному вектору) второго графа. Напомним, что конъюнкции (троичные векторы) ортогональны, если хотя бы одна переменная одной конъюнкции встречается с инверсным знаком в другой конъюнкции (хотя бы в одной компоненте троичных векторов их определенные значения инверсны). Значения 0.1 называются определенными, а значения «-» - неопределенными. Рассмотрим сначала пути, сопоставляемые одному и тому же выходу схемы. Возможны две ситуации. Пусть два графа представляют множества всех тестовых пар соседних векторов, обнаруживающих робастно тестируемые неисправности задержек путей, исходящих из одного и того же входа схемы С, помеченного переменной xi. Обозначим эти графы R1(xi), R2(xi). В дальнейшем будем говорить, что пути этих графов отмечены переменной xi. Теорема 1. Пересечение ROBDD-графов R1(xi), R2(xi) путей, начала которых отмечены одной и той же переменной xi, пусто: R1(xi) & R2(xi) = Ø. Доказательство. Допустим противное. Пересечение графов не пусто. Это значит, что в графах R1(xi), R2(xi) найдется пара конъюнкций, по одной из каждого графа, таких, что их произведение не пусто: k1 & k2 ≠ Ø. Будем иметь в виду, что каждая из рассматриваемых конъюнкций представляет множество минимально покрывающих интервалов ранга (n-1) тестовых пар соответствующих путей схемы С. Следовательно, пересечение хотя бы одной пары таких интервалов, по одному из каждого графа, не пусто. Это означает возможность проявления задержки сразу на обоих путях, либо на одном из них, не известно, каком именно. Следовательно, порождаемые общими интервалами тестовые пары не обнаруживают робастно тестируемые неисправности рассматриваемых путей схемы С. Пришли к противоречию. Теорема доказана. Следствие 1. Троичные векторы (конъюнкции) графов R1(xi), R2(xi), по одному вектору из каждого графа, ортогональны, по крайней мере, по одной определенной компоненте (в соответствующих этим векторам конъюнкциях содержится хотя одна пара взаимно инверсных переменных). Теперь перейдем к рассмотрению графов, пути которых отмечены разными входными переменными. Обозначим их R1(xi), R2(xj). Теорема 2. Пересечение ROBDD-графов R1(xi), R2(xj) путей, начала которых отмечены различными переменными xi и xj, может быть непустым: R1(xi) & R2(xj) ≠ Ø, i ≠ j. Доказательство. Допустим, что пересечение ROBDD-графов R1(xi), R2(j) может быть непустым. Тогда существуют две простые цепи из корня в 1 терминальную вершину в графах R1(xi), R2(j), по одной для каждого графа, такие, что пересечение сопоставляемых им троичных векторов не пусто. Рассмотрим некоторые из возможных результатов их пересечений по переменным xi, xj: в частности, пересечения, порождающие булевы векторы по этим переменным из множества: {00, 01, 10, 11}. Выберем одно из них, например пересечение, порождающее вектор 11, сопоставив ему булев вектор α в пространстве n переменных схемы С, принадлежащий интервалу пересечения рассматриваемых троичных векторов. Схема С на этом векторе и соответствующем выходе принимает либо значение 0, либо значение 1. Допустим, что в нашем случае это значение 1. Построим тестовые пары, обнаруживающие робастно тестируемые неисправности задержек каждого из путей графов. Поскольку на соответствующем вектору 11 векторе α схема С обращается в единицу, то вектор α может быть сопоставлен только ap тестовому набору [1] v1, например, для пути, помеченного переменной xi. Тогда соответствующий ему bp тестовый набор содержит вектор 01 по переменным xi, xj., не отличаясь от α по остальным компонентам. В дальнейшем будем представлять векторы только их компонентами xi, xj, поскольку по остальным компонентам они не отличаются. Тройка векторов v1 v2 v1 (11, 01, 11) возвращает нас в вектор 11, который может быть сопоставлен только ap тестовому набору v1 для пути, помеченного переменной xj. Тогда вектор 10 сопоставляется bp тестовому набору для пути, отмеченного переменной xj. В рамках наших предположений с помощью последовательности из пяти векторов {11, 01, 11, 10, 11} мы проверяем задержки сначала rising transition, а потом falling transition пути, которому сопоставлен граф R1(xi), а далее rising transition, а потом falling transition пути, которому сопоставлен граф R2(xj). Из свойств ap, bp тестовых наборов [1] следует, что при непустых пересечениях графов R1(xi), R2(xj) порождаются последовательности соседних векторов, в которых порядок проверки инверсных перепадов сигналов для каждого из путей один и тот же и зависит от выбранного булева вектора, являющегося результатом пересечений графов. Сказанное справедливо для любого другого вектора из множества {00, 01, 10, 11}. Если результат пересечений содержит по переменным xi, xj одну неопределенную компоненту, то в этом случае мы имеем две возможности доопределить этот вектор и, следовательно, получить две последовательности из пяти векторов, которые могут отличаться лишь порядком перебора перепадов сигналов в рассматриваемых векторах. Действительно, рассматривая инверсные определенные значения вместо неопределенной компоненты в условиях сохранения второй определенной компоненты, мы имеем в качестве первого тестового набора либо ap, либо bp тестовые наборы одного и того же пути, отмеченного переменной xi. Пусть в результате пересечений получен вектор, состоящий только из неопределенных компонент. Доопределив его произвольным образом до полностью определенного вектора, получим последовательность из пяти векторов. В этой ситуации мы можем построить четыре последовательности из пяти векторов, в которых порядок обеспечения risng и falling переходов определяется значениями, принимаемыми схемой С на наборах, порождаемых непустыми пересечениями конъюнкций рассматриваемых графов. Теорема доказана. Пусть ROBDD-графы R1s(xi), R2t(xj) сопоставляются различным выходам схемы, а именно выходу s и t соответственно. Их входы могут быть отмечены как различными, так и одинаковыми входными переменными. Теорема 3. Пересечение ROBDD-графов R1s(xi), R2t(xj), сопоставляемых различным выходам схемы, может быть непустым: R1s(xi) & R2t(xj) ≠ Ø. Доказательство. Будем иметь в виду, что результат пересечения двух троичных векторов, по одному из каждого графа, содержит хотя бы один булев вектор размерности n, который содержится в минимально покрывающем интервале пары (v1, v2) для пути с выходом s, поглощаемом участвующим в пересечении троичным вектором, соответствующим ROBDD-графу R1s(xi). Этот минимально покрывающий интервал может пересекаться с участвующим в пересечении троичным вектором графа R2t (xj) для пути с выходом t. В этой ситуации возможно проявление неисправности задержки пути с выходом t. Однако соответствующие тройки булевых векторов, формируемые парами (v1, v2), поступают последовательно для различных путей, одна за другой, в тестовой последовательности. Если пара (v1, v2) используется для выявления задержки пути, сопоставляемом выходу s, то на путь t вообще не обращают внимание. Задержка второго пути, если она существует, проявится на тестовой паре графа R2t(xj). В связи со сказанным, начала путей рассматриваемых графов могут быть отмечены одной и той же переменной. Теорема доказана. На основании приведенных выше теорем формулируем следствие. Следствие 2. Если r графов, сопоставляемых путям из заданного множества, порождают непустое пересечение, то существует хотя бы одна последовательность из 2r+1 соседних булевых векторов, обнаруживающая неисправности обоих перепадов значений сигналов на соответствующих r графам путях. Отметим, что такая последовательность характеризуется минимальным потреблением мощности. 3. Общая стратегия построения тестовых последовательностей Задано множество Rrob1, …, RrobL ROBDD-графов, сопоставляемых L путям схемы С, схема может быть многовыходной. В графах отсутствует одна из n переменных, а именно: в каждом гра¬фе отсутствует переменная, отмечающая начало пути, соответствующего графу. Остальные переменные (входные переменные схемы) перечисляются для всех графов в одном и том же порядке. Например, в графе отсутствует переменная xi и входные переменные упорядочены по возрастанию индексов, тогда порядок переменных в графе представляется списком: x1, …, xi-1, xi+1, …, xn. Если xi = x1, тогда построение ROBDD-графа начинается с переменной x2. Желательно построить последовательность, содержащую как можно больше фрагментов длины более трех, сплошь состоящих из соседних векторов. При объединении фрагментов необходимо минимизировать, по возможности, расстояние по Хеммингу между смежными векторами соседних фрагментов, тем самым уменьшая пиковые потребления мощности. Будем считать, что графы Rrob1, …, RrobL упорядочены по невозрастанию числа вершин в них. Для построения тестовой последовательности предлагается выполнить следующие шаги: 1. С учетом теорем 1-3 находим пересечение как можно большего числа графов. Если графы попарно ортогональны, переходим к п. 4. Иначе выполняем следующий по порядку пункт. 2. Формируем для очередного пересечения графов фрагмент тестовой последовательности из соседних векторов. 3. Исключаем участвующие в пересечении графы из заданного множества, упорядочивая оставшееся множество по невозрастанию вершин в графах. Переходим к п. 1. 4. Объединяем полученные фрагменты так, чтобы смежные векторы предыдущего и последующего фрагментов были как можно ближе в смысле расстояния по Хеммингу. 5. Строим оставшийся фрагмент тестовой последовательности для множества попарно ортогональных ROBDD-графов. 4. Построение тестовой последовательности для множества попарно ортогональных графов Извлечение последовательности троичных векторов Имеем множество попарно ортогональных графов Rrob1, …, Rrobq. Выбираем среди них по возможности более короткий путь из корня в 1 терминальную вершину, исключив из дальнейшего рассмотрения граф, которому принадлежит выбранный путь. Для множества попарно ортогональных графов формируем последовательность троичных векторов так, чтобы соседние троичные векторы были как можно ближе в смысле расстояния по Хеммингу. Решение этой задачи сводим к поиску в очередном графе троичного вектора, по возможности, с меньшим числом определенных компонент и более близкого, в смысле расстояния по Хеммингу, к троичному вектору β, найденному на предыдущем шаге. Представляем троичный вектор β ROBDD-графом R1 и выбираем из оставшегося множества графов очередной ROBDD-граф R2. Оба графа получены с использованием одного и того же порядка переменных при разложении Шеннона. Далее находим троичный вектор, используя граф R2. Введем ряд определений. Дуги, заходящие в 0 терминальную вершину, назовем запрещенными дугами, а все другие дуги - допустимыми дугами. Дуги, заходящие в 1 терминальную вершину, назовем концевыми дугами, а вершины, из которых они исходят - концевыми внутренними вершинами графа. Заметим, что одна из дуг, исходящих из внутренней вершины графа R1, всегда является запрещенной дугой. Обходим пути графа R2, используя граф R1 с целью сокращения обхода. Двигаемся по пути графа R2, одновременно просматривая вершины графа R1 с тем, чтобы попасть в первую внутреннюю вершину R2, одноименную с вершиной графа R1. Обозначаем эти вершины w1 и w2 соответственно. Сопоставляемые пройденным фрагментам путей конъюнкции обозначаем k1, k2. Корректируем k2, добавляя в нее литеры k1, отсутствующие в k2, и отмечаем число µ взаимно инверсных переменных в этих конъюнкциях. Продолжаем аналогичное движение с целью попасть в следующую внутреннюю вершину графа R2, одноименную с вершиной графа R1, и т.д., пока не достигнем в одном из графов концевой дуги. Далее переходим в 1 терминальную вершину другого графа. Если другим графом является R2, переходим в эту терминальную вершину, по возможности, более коротким путем (в графе R1 существует только один путь в 1 терминальную вершину). Начинаем движение из вершины, которую отмечает переменная, ближайшая в упорядоченном ряду к переменной, отмечающей внутреннюю концевую вершину графа R1. Затем поступаем аналогично предыдущему: формируем конъюнкции k1 и k2, корректируем k2 описанным выше способом и запоминаем соответствующие k2 и µ. Возвращаемся в ближайшую точку ветвления графа R2. Если ресурс для поиска подходящего троичного вектора исчерпан или обход графа R2 завершен, выбираем конъюнкции k2, которым сопоставляется наименьшее значение µ, а среди них предпочтение отдаем конъюнкции наименьшего ранга. Выбранную конъюнкцию обозначаем . Она представляет искомый троичный вектор. Исключаем граф R2 из дальнейшего рассмотрения, конъюнкцию представляем троичным вектором β и выбираем очередной граф из множества попарно ортогональных графов. Как только множество таких графов оказывается пустым, последовательность троичных векторов построена. Проиллюстрируем алгоритм анализа графов R1 и R2 на примере. Схема С представлена на рис. 1. У нее пять входных переменных: e, b, a, c, d. Этот порядок используется для получения ROBDD-графов. На рис. 2, а представлен ROBDD-граф, задающий все соседние тестовые пары для робастно тестируемых неисправностей задержек пути e, 5, 9, а на рис. 2, б - ROBDD-граф, представляющий аналогичные тестовые пары пути a, 1, 4, 6, 8, 9. Выбираем кратчайший путь графа на рис. 2, a и получаем конъюнкцию . Эта конъюнкция порождает граф на рис. 2, в, то есть граф R1. ROBDD R2 представлен на рис. 2, б. Анализируя R2, пытаемся найти троичный вектор, как можно более близкий к вектору, представляющему конъюнкцию . Рис. 1. Схема C a б в Рис. 2. Путь e, 5, 9 (a); путь a, 1, 4, 6, 8, 9 (ROBDD R2) (б); ROBDD R1 (в) Итак, мы двигаемся в R2 из его корня по 1 дуге в вершину w2, отмеченную переменной b. Вершина w1 также отмечена переменной b. Для пары вершин имеем k1 = Ø, k2 = e. Следующая внутренняя вершина графа R1 является концевой, она отмечена переменной a. Теперь мы двигаемся из вершины w2 в 1 терминальную вершину графа R2 и формируем конъюнкции: k1 = , k2 = . Корректируя k2, получаем , µ = 1. Выбираем в R2 ближайшую точку ветвления, ей оказывается корень графа. Теперь двигаемся по 0 дуге и достигаем очередной вершины w2, отмеченной переменной b. Получаем конъюнкции: k1 = Ø, k2 = . Следующая вершина графа R1 является концевой, отмеченной переменной a. Двигаемся из w2 по 0 дуге к 1 терминальной вершине графа R2 и формируем конъюнкции: k1 = , k2 = . Корректируя k2, получаем , µ = 1. Выбираем ближайшую точку ветвления в графе R2: это вершина w2, отмеченная переменной b. Следующая вершина w1 в R1 является концевой вершиной. Теперь мы двигаемся из w2 по 1 дуге к 1 терминальной вершине графа R2 и формируем конъюнкции: k1 = , k2 = . Корректируя k2, получаем , µ = 0. Мы достигли минимального расстояния по Хеммингу между соответствующими конъюнкциям троичными векторами и поэтому прекращаем движение по графу R2: k1 & k2 = . Этой конъюнкции соответствует троичный вектор 010-0. Выделим из него булев вектор 01000. Булев вектор обращает схему C в 0. Это значит, что рассматриваемый вектор является bp [1] тестовым набором для обоих путей схемы C. Будем иметь в виду, что ap тестовый набор для пути e, 5, 9 представляется булевым вектором 11000, а ap тестовый набор для пути a, 1, 4, 6, 8, 9 - булевым вектором 01100. Для тестирования неисправностей задержек рассматриваемых путей мы получаем следующую последовательность соседних булевых векторов: 01000 11000 01000 01100 01000, которая позволяет обнаруживать неисправности обоих перепадов значений сигналов двух рассматриваемых путей и характеризуется минимально возможным потреблением мощности. Заметим, что если µ = 0, то графы пересекаются. Если мы рассматриваем непересекающиеся графы, то минимально возможное расстоянием по Хеммингу между троичными векторами этих графов равно единице. Извлечение тестовой последовательности из последовательности троичных векторов Для множества Rrob1, …, Rrobq получена соответствующая последовательность троичных векторов. Далее строим порождаемую ей последовательность троек булевых векторов, представляющую продолжение уже найденного отрезка тестовой последовательности, а именно заключительную ее часть. В результате получаем последовательность, обнаруживающую робастно тестируемые неисправности задержек обоих перепадов для L путей схемы С. Каждая тройка представляется одним булевым вектором, построенным доопределением соответствующего ему троичного вектора последовательности. Для этого сначала предлагается последующий троичный вектор подстраивать к предыдущему вектору. Если в последующем векторе i-я компонента имеет значение «-», то эта компонента принимает значение одноименной компоненты предыдущего вектора. Определенная компонента последующего вектора сохраняет свое значение. Проиллюстрируем это на примере. Пусть получена последовательность векторов для четырех путей, начала которых отмечены переменными x3, x4, x1, x2 соответственно: 01--10 -10-11 --10-1 0-0--1. Из этой последовательности получаем последовательность 01--10 010-11 011011 010011, которая, как и исходная троичная последовательность, порождает три смены значений определенных компонент. Если неопределенные символы остались в начальном отрезке построенной последовательности, то корректируем ее, сохраняя число смен значений определенных компонент. С этой целью анализируем последовательность по каждой из переменных. Ближайший по переменной xi определенный символ приписываем всем предшествующим членам последовательности по этой переменной. Для нашего примера имеем 010010 010011 011011 010011. Полученная последовательность порождает тестовую последовательность, обнаруживающую робастно тестируемые неисправности задержек обоих перепадов значений сигналов этих путей: 010010 011010 010010 010011 010111 010011 011011 111011 011011 010011 000011 010011. В тестовой последовательности длины 12 число смен значений сигналов равно 11. Заметим, что, изменяя порядок элементов исходной последовательности троичных векторов, можно добиться лучших результатов в смысле количества смен значений сигналов тестовой последователь- ности. 5. Экспериментальные результаты Таблица 1 Данные для наиболее длинных путей Схема Число входов схемы Число вентилей схемы Число выбранных путей Процент робастно тестируемых путей Число внутренних вершин графов Rrob Ранги интервалов, представляющих тесты min avg max min avg max s298 17 119 146 65.07 3 7.26 17 1 4.52 7 s344 24 160 159 69.81 4 10.5 45 1 9.01 12 s400 24 162 258 82.56 4 11.6 24 1 8.84 14 s444 24 181 237 59.92 4 9.04 15 2 7.84 13 s641 54 379 309 44.34 4 10.1 19 2 6.87 13 s820 23 289 232 99.14 6 8.96 28 2 7.01 13 s953 45 395 338 92.60 3 12.4 40 1 10.8 16 s1196 32 529 334 48.50 3 11.2 72 1 10.2 16 s1488 14 653 312 93.27 6 9.84 27 1 7.51 13 s1494 14 647 336 91.07 5 9.94 27 3 7.74 13 Приведем некоторые результаты экспериментов над контрольными примерами (схемы ISCAS’89). Для путей этих схем строились ROBDD-графы Rrob, представляющие множества всех тестовых пар соседних булевых векторов для робастно тестируемых неисправностей задержек рассматриваемых путей. Схемы имеют много выходов. Для каждого из выходов выбирались до десяти наиболее длинных и наиболее коротких путей. В табл. 1 и 2 представлены числа наиболее длинных и наиболее коротких путей для схемы в целом. Видно, что в среднем число вершин графов достигает одного-трех десятков. Процент робастно тестируемых путей довольно высок по сравнению с процентом путей, задержки которых обнаруживаются применяемыми на практике методами сканирования. Имеются в виду методы сканирования, в которых в качестве одного из наборов тестовой пары используется тестовый набор для константной неисправности линии (полюса) схемы при условии, что второй набор тестовой пары получается либо сдвигом первого, либо формируется из реакции на первый набор. Ясно, что это эвристический подход к формированию тестовой пары. Как известно, он позволяет обнаруживать задержки около 20 % путей схемы. В данной работе рассматривается точный метод, позволяющий найти тестовую пару, если она существует, отсюда и значительно лучшие результаты. Заметим, что графы могут компактно представлять огромное количество тестовых пар. Например, в схеме s641, имеющей 54 входа, интервал ранга 2 представляет 251 тестовых пар (число тестовых пар k = 2n-r, где n - число входов схемы, r - ранг интервала). Из табл. 1 и 2 следует, что в среднем графы для коротких путей содержат больше вершин и процент тестируемых путей у них выше. Предварительные эксперименты показали, что возможны непустые пересечения нескольких графов, вплоть до десяти. Таблица 2 Данные для наиболее коротких путей Схема Число входов схемы Число вентилей схемы Количество выбранных путей Доля тестируемых путей в процентах Число внутренних вершин графов Rrob Ранги интервалов, представляющих тесты min avg max min avg max s298 17 119 149 87.25 3 7.02 15 1 4.36 6 s344 24 160 161 91.30 4 13.3 77 1 8.92 12 s400 24 162 239 72.38 4 12.3 41 1 8.21 14 s444 24 181 234 67.09 4 11.4 30 2 8.74 13 s641 54 379 330 92.73 4 26.6 155 2 14.2 24 s820 23 289 229 100.00 6 26.4 928 2 16.3 20 s953 45 395 365 93.15 3 12.6 49 1 10.5 17 s1196 32 529 328 92.68 3 31.2 299 1 13.2 18 s1488 14 653 306 99.35 6 16.9 189 1 11 13 s1494 14 647 305 97.05 5 17.2 196 3 10.7 13

Скачать электронную версию публикации