Тема магистерской работы:
Глава содержит описание основных приемов и методов генерациии тестов комбинационных схем. В ней рассматриваются следующие вопросы: алгоритмы и представления; структурное и функциональное тестирование; определение автоматического генерирования тестовых последовательностей; абстракции поискового пространства; результативность алгоритма; АГТП алгебра; типы алгоритмов.
Статья содержит описание D-алгоритма. D-алгоритм является дальнейшим развитием концепции активизации путей проверяемой схемы. В отличие от метода одномерной активизации данный алгоритм основан на возможности одновременной активизации всевозможных путей (как одномерных так и многомерных ) от места возникновения неисправности ко всем выходам схемы. Формальное описание алгоритма базируется на D-исчислении – модифицированном кубическом исчислении булевых функций .
Empirical observation shows that practically encountered instances of ATPG are efficiently solvable. However, it has been known for more than two decades that ATPG is an NP-complete problem. This work is one of the first attempts to reconcile these seemingly disparate results. We introduce the concept of circuit cut-width and characterize the complexity of ATPG in terms of this property. We provide theoretical and empirical results to argue that an interestingly large class of practical circuits have cut-width characteristics which ensure a provably efficient solution of ATPG on them.
Automatic Test Pattern Generation (ATPG) is one of the core algorithms in testing of digital circuits and systems. Due to recent advances in algorithms to solve Boolean Satisfiability (SAT), there is a renewed interest in SAT-based ATPG. While the early approaches only used two-valued logic, modern tools have to use multiple values to model unknown values and tri-state elements for buses. In this paper we present a detailed study on how to chose the multi-valued encoding for SAT-based ATPG. The techniques have been implemented and evaluated on large industrial benchmarks.
A well-known problem in timing verification of VLSI circuits using static timing analysis tools is the generation of false timing paths. This leads to a pessimistic estimation of the processor speed and wasted engineering effort spent optimizing unsensitizable paths. Earlier results have shown how ATPG techniques can be used to identify false paths efficiently, as well as how to bridge the gap between the physical design on which the static timing analysis is based and the test view on which ATPG technique is applied to identify false paths. In this paper, we will demonstrate efficient techniques to identify more false timing paths by utilizing information from an ordered list of timing paths according to the delay information. More than 10% of additional false timing paths out of the total timing paths analyzed are identified compared to earlier results on the MPC7455, a Motorola processor executing to the PowerPCTM 1 instruction set architecture.
Effective high-level ATPG tools are increasingly needed, as an essential element in the quest for reducing as much as possible the designer work on gate-level descriptions. We propose a new set of benchmark circuits targeted to researchers working in the area of RT-level automatic test sequence generation. The developed benchmarks share the characteristics of typical synthesizable blocks, are available as both RTL VHDL descriptions and gate level netlists, and allow the evaluation of the quality of test sequences generated from RT-level descriptions in terms of attained coverage of gate-level stuck-at faults. Exploiting these benchmarks, we analyzed the effectiveness of a prototypical ATPG tool (called ARTIST) suitable to generate test sequences starting from synthesizable RT-level VHDL descriptions.
In this survey, we outline basic SAT- and ATPGprocedures as well as their applications in formal hardware verification. We attempt to give the reader a trace trough literature and provide a basic orientation concerning the problem formulations and known approaches in this active field of research.
The developments of efficient SAT solvers have attracted tremendous research interest in recent years. The merits of these solvers are often compared in terms of their performance based upon a wide spread of benchmarks. In this paper, we extend an earlier-proposed solver design concept called (SCGL) Signal Correlation Guided Learning that is ATPG-based into a family of heuristics.
Combinatorial problems in Electronics Computer Aided Design (ECAD), namely in the field of Automatic Test Pattern Generation (ATPG), have usually been handled either by specific tools or by mapping them into a general problem solver, requiring the consideration of (at least partially) a duplication of the circuits. Constraint Logic Programming (CLP) with special domains was proposed as an useful alternative. In this paper we define an 8-valued logic for modelling the problem of diagnosis, and show that set constraints can generalise it to handle ATPG optimisation problems.