On the validation of embedded systems through functional ATPG

L’aumento delle dimensioni e della complessit´a dei dispositivi digitali ha reso essenziale anticipare le attivit´a di verifica alle fasi iniziali del flusso di progettazione. In questo modo la verifica di sistemi complessi risulta essere pi´u trattabile e gli errori di progetto posso essere identificati anticipatamente e rimossi, salvando tempo e denaro. Pertanto, molti ATPG (Automatic Test Pattern Generator) a livello funzionale sono stati proposti per generare sequenze di test che siano efficaci. Alternativamente, gli ATPG a livello gate rappresentano lo stato dell’arte per la verifica di sistemi digitali. Essi, per´o, pagano i buoni risultati di copertura di guasto in termini di tempi di esecuzione e risorse necessarie. In questo contesto, una soluzione vantaggiosa per la validazione ´e rappresentata dalla verifica dinamica che sfrutta tecniche basate sulla simulazione per stimolare il DUV (Design Under Verification). II. STRUTTURA DELL’ATPG Il lavoro di ricerca dell’autore si focalizza sullo sviluppo di un generatore di test deterministico a livello funzionale che frutti il paradigma delle EFSM (Extended Finite State Machine). (Si veda Figura 1). Una metodologia ´e stata definita per estrarre questo modello da differenti descrizioni ad alto livello. Dapprima la descrizione del design (Verilog, VHDL, SystemC) ´e tradotta in un linguaggio intermedio di descrizione dell’hardware (HIF), quindi i modelli sono estratti automaticamente e manipolati. Differenti EFSM possono essere generate a partire dalla stessa descrizione del DUV. Comunque, a prescindere alla loro equivalenza funzionale, esse posso essere attraversate in modo pi´u o meno semplice. Pertanto un insieme di trasformazioni automatiche (avvalorate da un’analisi teorica) sono state proposte per generare un particolare tipo di EFSM detta estesa agli eventi (EEFSM). Questo modello ´e adatto per rappresentare processi di una descrizione hardware con sensitivity list [1], e ci´o permette all’ATPG proposto per esplorare facilmente lo spazio degli stati del corrispondente DUV riducendo il rischio di esplosione del numero di stati e transizioni [1]. Inoltre, l’utilizzo del modello EFSM viene utilizzato per rappresentare la concorrenza: un sistema complesso pu´o essere sempre rappresentato mediante un certo numero di EFSM interconnesse che comunicano e interagiscono. L’ATPG proposto sfrutta le EFSM concorrenti adottando un duplice approccio: la schedulazione di EFSM e la composizione di EFSM. L’algoritmo di schedulazione di EFSM ´e stato proposto per permettere una semplice esplorazione del DUV, fornendo a ciascuna EFSM la possibilit´a di fissare deterministicamente gli ingressi primari per raggiungere determinati stati [2]. La presenza di gerarchie nella descrizione del sistema implica la necessit´a di dover navigare durante la generazione del test un numero elevato di EFSM. La composizione di EFSM permette pertanto di ridurre tale complessit´a introducendo una rappresentazione appiattita del DUV [1]. In entrambi i casi, le EFSM sono deterministicamente esplorate mediante tecniche di learning, random walking e backjumping [3]. Per prima cosa, durante la fase di learning, le informazioni strutturali e la raggiungibilit´a delle transizioni vengono raccolte per essere utilizzate durante le fasi successive. Quindi, durante la fase di random walk, l’ATPG attraversa in maniera pseudo-casuale le transizioni delle EFSM rappresentanti il DUV sfruttando un risolutore di vincoli. In questo modo le transizioni easy-to-traverse vengono attraversare semplicemente. Infine, nella terza fase, le informazioni raccolte nelle fasi precedenti sono sfruttate per attivare transizioni che non siano ancora state attivate, mediante un approccio basato sul backjumping. Il motore dell’ATPG salta direttamente sulle transizioni che aggiornano glo stato di ciascuna transizione hard-to-traverse per fissarne opportunamente i valori. Questo approccio rappresenta un vantaggio effettivo rispetto all’utilizzo di tecniche come il backtracking tipico di ATPG a livello gate che si muovo indietro verso i punti pi´u prossimi di decisione per poi proseguire in una direzione differente. Oltre al motore basato su EFSM, un efficiente simulatore per guasti funzionali ´e stato implementato e l’architettura misura la qualit´a delle sequenze di test generate in accordo con i modelli di guasto bit coverage e operatori di mutazione [4]. Il simulatore di guasto sfrutta sia un motore di simulazione seriale, a livello funzionale, che un motore si simulazione parallelo, a livello bit. In particolare, il motore parallelo di simulazione adotta tecniche a livello bit, come la vettorizzazione e la concorrenza, applicandole a una rappresentazione C del design a livello logico. La descrizione a livello logico ´e mappata direttamente sulle parole della macchina sottostante, al fine di utilizzare direttamente le istruzioni macchina, evitando il possibile carico dovuto all’utilizzo di costrutti pi´u complessi. La mappatura sulle parole di macchina permette di aumentare le prestazioni senza modifiche al codice semplicemente utilizzando macchine con architetture a 32-bit, a 64-bit o superiori. III. CONCLUSIONI L’integrazione di tali strategie permette all’ATPG funzionale proposto di analizzare in modo pi´u efficiente lo spazio degli stati del DUV e di generare sequenze di test efficaci. Inoltre, i risultati sperimentali dimostrano come gli approcci di generazione deterministica del test e di simulazione permettono la diminuzione del tempo di generazione del test e il miglioramento della copertura sia dei guasti che delle transizione rispetto ad altri ATPG sia a livello funzionale che a livello gate. 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. Improving Gate-Level ATPG by Traversing Concurrent EFSMs. In Proc. of IEEE VLSI Test Symposium. Berkeley, 2006. [3] 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. [4] 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.

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.