On the validation of embedded systems through functional ATPG

I. THESIS MOTIVATIONS Increasing size and complexity of digital designs have made essential to address critical verification issues at the early stages of design cycle. In this way, the verification of complex systems is more tractable and design errors can be early identified and removed, saving time and money. Thus, many functional automatic test pattern generators (ATPGs) have been proposed to generate effective test sequences. On the other side, gate-level ATPGs represent the stateof- the-art for digital system testing. However, they pay the achieved good fault coverage results in terms of time and required resources. In this context, a valuable solution for the functional validation is represented by dynamic verification which exploits simulation-based techniques to stimulate the design under verification (DUV). II. ATPG FRAMEWORK The author’s work is focused on the development of a functional deterministic test pattern generator which exploits extended finite state machines (EFSM) paradigm (Figure 1). A methodology has been defined to extract this model from different high level descriptions. First the design description (Verilog, VHDL, SystemC) is translated into an HDL intermediate format (HIF), then the models are automatically extracted and manipulated. Many EFSMs can be generated starting from the same description of a DUV. However, despite from their functional equivalence, they can be more or less easy to be traversed. Thus a set of theoretically-based automatic transformations has been proposed to generate a particular kind of EFSM, called event extended FSM (EEFSM). This model is suitable for represent process statements with a sensitivity list, typical of HDLs [1], and it allows the proposed ATPG to easily explore the state space of the corresponding DUV reducing the risk of state explosion [2]. Moreover, the use of EFSM model can be exploited to represent concurrency: a complex system can always be described with a certain number of interconnected EFSMs which communicate and interact. The proposed ATPG exploits multiple EFSMs by adopting two approaches: EFSM scheduling and EFSM composition. A EFSM scheduling algorithm has been proposed to allow a fair exploration of the DUV, by giving to each EFSM the possibility of deterministically fixing primary inputs to reach the desired destination state [3]. In the case the hierarchy of the modules introduces complexity due to multiple EFSM navigation, the EFSM composition methodology permits to reduce this complexity with a flat representation of the DUV, [1]. During test generation, EFSMs are deterministically explored by using learning, random walking and backjumping techniques [4]. First, in the learning phase, structural information and transition reachability are collected to be used in the following phases. Then, in the random walk phase, the ATPG pseudo-randomly walks across the transitions of the EFSMs representing the DUV through a constraint solver. Thus, easy-to-traverse transitions are very likely traversed. Finally, in the third phase, the information collected in the previous steps is exploited to traverse transitions that have not been activated yet, by means of a backjumping-based approach. The ATPG engine directly backjumps to the transition that updates the state of each hard-to-traverse transition to opportunely fix the values. This approach represents an effective advantage with respect to the use of techniques like backtracking in gate-level ATPGs which blindly rollbacks to a decision point before proceeding towards a different direction. Beside the EFSM-based engine, an efficient simulator for functional faults has been implemented and the framework measures the quality of generated test sequences according to the bit coverage and mutant fault models [5]. The fault simulator exploits both a serial simulation engine, at functional level, and a parallel simulation engine, at bit-level. In particular, the parallel simulation engine adopts bit-level techniques, like vectorization and concurrency, by applying them to a C-representation of the design at logic-level. The logic-level description is mapped on machine words, in order to use directly the machine instructions, avoiding the possible overhead of using more complex constructs. This mapping to a machine word allows switching from a 32-bit machine to a 64-bit one and more, to further increase performance, without any code changing. III. CONCLUDING REMARKS The integration of such strategies allows the proposed functional ATPG to more efficiently analyze the state space of the design under verification and to generate effective test sequences. Moreover, experimental results show that the deterministic test pattern generation and the simulation approaches achieve reduction of test generation time and improvement of fault and transition coverage with respect to other functional or gate-level ATPGs. REFERENCES [1] D. Bresolin, G. Di Guglielmo, F. Fummi, G. Pravadelli, and T. Villa. The impact of EFSM Composition on Functional ATPG. In In the Proc. of 12th IEEE Symposium on Design and Diagnostics of Electronic Systems. Liberec, Czech Republic, 2009. [2] G. Di Guglielmo, F. Fummi, C. Marconcini, and G. Pravadelli. EFSM Manipulation to Increase High-Level ATPG Efficiency. In Proc. of IEEE ISQED, pp. 57–62. 2006. [3] G. Di Guglielmo, F. Fummi, C. Marconcini, and G. Pravadelli. Improving Gate-Level ATPG by Traversing Concurrent EFSMs. In Proc. of IEEE VLSI Test Symposium. Berkeley, 2006. [4] G. Di Guglielmo, F. Fummi, C. Marconcini, and G. Pravadelli. Improving High-Level and Gate-Level Testing with FATE: a Functional ATPG Traversing Unstabilized EFSMs. Computers & Digital Techniques, IET, vol. 1:pp. 187–196, 2007. [5] G. Di Guglielmo, F. Fummi, M. Hampton, G. Pravadelli, and F. Stefanni. The Role of Parallel Simulation in Functional Verification. In Proc. of IEEE International High Level Design Validation and Test Workshop. 2008.