РЕФЕРАТ 3
ВВЕДЕНИЕ 5
1 Применение 6
2 Постановка задачи 7
3 Основные понятия 8
4 Поиск тестового набора для константных неисправностей литер ЭНФ 12
4.1 Построение bp тестового набора 13
5 Представление схемы размеченным И-ИЛИ деревом 17
5.1 Поиск концевой вершины И-ИЛИ дерева, сопоставляемой заданному пути 19
5.2 Коррекция И-ИЛИ дерева относительно выделенной концевой вершины 20
6 Построение всех тестовых наборов 22
6.1 Построение всех тестовых наборов для bp неисправности 22
6.2 Построение всех тестовых наборов для ap неисправности 24
7. Программная реализация 25
7.1 Общее описание программы 25
7.2 Описание методов и функций 26
8 Экспериментальные результаты 30
ЗАКЛЮЧЕНИЕ 33
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 34
Для увеличения быстродействия схем высокого уровня интеграции необходимо обнаружение их ложных путей. Ложными путями в схеме являются пути, для которых изменение значения сигнала на входе пути не приводит к изменению значения сигнала на выходе схемы (комбинационной составляющей схемы с памятью). Ложные пути могут оказаться среди путей, характеризующихся самыми большими задержками. Эти задержки вычисляются по характеристикам элементов, составляющих путь. Самые большие задержки путей в схеме определяют ее быстродействие: время между синхроимпульсами в схеме с памятью немного больше самой большой из задержек путей. Исключение ложных путей может привести к сокращению времени между синхросигналами и, следовательно, к повышению быстродействия схемы. В работе [1] проблема поиска ложных путей в схеме с памятью сведена к нахождению всех тестовых наборов, обнаруживающих константные неисправности литер эквивалентной нормальной формы (ЭНФ), сопоставляемых рассматриваемым путям. ЭНФ строится по комбинационной составляющей схемы с памятью. Далее находится последовательность, обеспечивающая доставку одного из тестовых наборов для константных неисправностей исследуемого пути. В данной бакалаврской работе предлагается метод нахождения всех тестовых наборов для константных 0,1 неисправностей соответствующего пути литеры эквивалентной нормальной формы (ЭНФ) с использованием И-ИЛИ деревьев и ROBDD-графов.
1 Применение
При разработке цифровых управляющих компонент, как правило, добиваются максимально возможной тактовой частоты, при которой управляющая компонента может работать корректно. Определение максимальной тактовой частоты сводится к учету влияния различных физических параметров, таких, как индуктивность, емкость, сопротивление, меняющихся с изменением частоты и, в конечном счете, приводящих к искажению предписанного схеме поведения. Однако для обеспечения максимально возможного быстродействия схемы анализа физических параметров ее элементов недостаточно. Требуется привлекать математические модели, используемые при тестировании логических схем. Находятся пути с самыми большими задержками сигналов, среди них выделяется критический путь, характеризующийся максимальной задержкой. Эта задержка определяет быстродействие управляющей компоненты. Однако некоторые из выбранных путей (их число может достигать 80 %)
оказываются ложными, не влияющими на работу компоненты. Выделение таких путей с целью исключения из рассмотрения может повысить скорость выполнения операций проектируемых управляющих компонент и, следовательно, эффективность работы физических систем в целом.
Реализована программа, позволяющая представлять комбинационную схему (Benchmarks), описанную в BLIF формате, в виде размеченного И- ИЛИ дерева, находить нужную концевую вершину в дереве, соответствующую заданному пути, отыскивать все конъюнкции, которые могут порождать тестовые наборы для bp неисправности литеры. Далее, используя CUDD (пакет для осуществления операций над BDD-графами), строятся соответствующие ROBDD-графы, и при их перемножении получается множество всех тестовых наборов для константных неисправностей литеры.
