Formal Verification of Behavioural Transformations during Embedded System Design
Chandan Karfa
Abstract
     

Application of behavioural transformations for obtaining optimal performance, energy and/or area on a given platform during embedded system design is now a common practice. Verifying correctness of these transformations is an important step in ensuring dependability of embedded systems. This thesis addresses verification methodologies, primarily by way of equivalence checking, for six behavioural transformations that are applied during embedded system design. The transformations considered cover code motion, generation of register transfer level (RTL) design after carrying high-level optimizations and also RTL transformations, loop and arithmetic transformations on array based programs, transformations on array based programs leading to the generations of Kahn process networks (KPN) to achieve high degree of parallelism and also transformations applied at the KPN level. Verification methods for the first three transformations on programs not involving arrays employ the model of finite state machines with datapaths (FSMD). FSMDs are generalizations of FSMs to capture data transforma- tions taking place between control states. FSMD based equivalence checking method consists in introducing cutpoints in one FSMD, visualizing its computations as concatenation of paths from cutpoints to cutpoints and finally, identifying equivalent finite path segments in the other FSMD; the process is then repeated with the FSMDs interchanged. Verification methods for the last three transformations involving arrays employ the array data dependence graphs (ADDG). The ADDG model primarily captures computation of a range of elements of an array from ranges of elements of other arrays. ADDG based equivalence checking attempts to show that the overall computations depicted in the ADDG to define the final ADDG nodes in terms of the initial ADDG nodes are equivalent, both in terms of computation and range of array elements, with respect to those in the ADDG being compared. The FSMD based methods developed handle both uniform and non-uniform code motion transformations. For non-uniform code motions model checking of some data-flow properties is also carried out. A rewriting mechanism covering both pipelining and multicycling is used to construct an FSMD from register transfer operations for RTL related equivalence checking. In our ADDG equivalence checking method we have introduced the notion of slices to guide the checking along the sequences in which operations are used to define array elements in the original behaviour. Normalized representation of arithmetic and conditional expressions play a central role in handling arithmetic transformations for both FSMD and ADDG based equivalence checking. Our ADDG based checking has been extended to check the equivalence of KPN networks derived by parallelizing sequential array based programs. Potential deadlocks in the KPN are also detected through the ADDG based modelling. Correctness and complexity of the all the developed methods have been treated formally. The methods have been implemented and tested on several benchmarks. This work represents useful application of equivalence checking as a verification method for verification to several aspects of the embedded system design flow.

     
     
     
Keywords: Keywords: Embedded System, Formal Verification, Equivalence Check- ing, Behavioural Transformation, Code Motion, Loop Transformation, Regis- ter Transfer Level (RTL), Kahn Process Network, Finite State Machine with Datapath (FSMD), Array Data Dependence Graph (ADDG)


     
chitta@iitkgp.ac.in [Publications list]