DOC PREVIEW
Recording Synthesis History for Sequential Verification

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Recording Synthesis History for Sequential Verification Alan Mishchenko Robert Brayton Department of EECS, University of California, Berkeley {alanmi, brayton}@eecs.berkeley.edu Abstract Performing synthesis and verification in isolation has two undesirable consequences: (1) verification runs the risk of becoming intractable, and (2) strong sequential optimizations are not applied because they are hard to verify. This paper develops a methodology for sequential equivalence checking using feedback from synthesis. A format for recording synthesis information is proposed. An implementation is described and experimentally compared against an efficient general-purpose sequential equivalence checker that does not use synthesis information. Experimental results confirm expected substantial savings in runtime of equivalence checking for large designs. 1 Introduction In this paper, we propose a methodology shift to a synthesis transparent process, which records and uses the synthesis history in an efficient way. It can promote the use of sequential synthesis and enable a scalable verification of the result. Sequential synthesis can result in considerable reductions in delay (e.g. see [19]) and area; however, it is mostly avoided for reasons of non-scalability of both synthesis and verification. To circumvent this, we believe that sequential synthesis and verification must go hand-in-hand to make sequential synthesis acceptable, and propose a way to make this happen. General sequential equivalence checking (GSEC) of two FSMs is PSPACE complete; however, if synthesis is restricted by one set of combinational transformations followed by one retiming or vice versa, the problem is provably simpler. On the other hand, iterating retiming and combinational transformations makes the problem again PSPACE complete [12], even though this is a very restricted set of sequential transformations. Also, as in the case of combinational equivalence checking (CEC) [18], in practice the problem becomes simpler if there are structural similarities between the two circuits to be compared. The current work has similarities with the following two approaches in the literature. Van Eijk [9] derived an inductive invariant, constructed by a fixed point process, consisting of a set of equivalences between signals in the two circuits. This invariant characterizes a superset of the reachable states of the product machine. Bjesse [4] and Case [7] extended this to an invariant composed of implications, which can give tighter approximations. Such methods are dependent on the particular implementation structures of the two machines being compared because equivalences or implications can be stated only between existing signals. To overcome this limitation, Van Eijk proposed creating additional signals, without any fanout, which might be useful in establishing additional equivalences. His proposal involved adding nodes which could be obtained by retiming. These signals approximate the reachable state space, thereby simplifying SEC, but do not guarantee that the invariant derived is sufficient to prove sequential equivalence. Mneimneh et. al. [22] looked at the problem of one retiming and one set of combinational logic transformations (in either order) and proposed a retiming invariant composed of a conjunction of functional relations among latch values derived from atomic retiming moves. We address the problem when one machine is derived from the other by a sequence of more general transforms, which may include retiming, combinational synthesis, merging sequentially equivalent nodes, and performing window-based sequential synthesis with don’t-cares. We propose to record the synthesis history which will provide the extra signals to aid verification. In contrast to van Eijk, our history aided verification approach (HSEC) can be characterized as follows: • All nodes created during synthesis are recorded, instead of adding a set of ad-hoc signals. • Each synthesis step records a sequential equivalence that should hold if the implementation of the synthesis algorithm is correct. A side benefit is that if an equivalence does not hold, the implementation is incorrect and the source of the error can be isolated. • The invariant is the set of all equivalences recorded. • The invariant is sufficient to prove sequential equivalence of the two machines by induction without counter-examples. • The invariant can be proved easily by proving each equivalence, one at a time. The proofs are local and hence fast, and can be done in parallel. Section 2 surveys the background. Section 3 shows how to efficiently record the history of synthesis by integrating two AIG managers. Section 4 details the use of the recorded history in sequential verification. Section 5 discusses other uses of a recorded history. Section 6 reports experimental results and Section 7 concludes the paper and outlines future work. 2 Background 2.1 Boolean networks A Boolean network is a directed acyclic graph (DAG) with nodes corresponding to logic gates and directed edges corresponding to wires connecting the gates. The terms Boolean network and circuit are used interchangeably in this paper. If the network is sequential, the memory elements are assumed to be D-flip-flops with initial states. Terms memory elements, flop-flops, and registers are used interchangeably in this paper. A node n has zero or more fanins, i.e. nodes that are driving n, and zero or more fanouts, i.e. nodes driven by n. The primary inputs (PIs) are nodes without fanins in the current network. The primary outputs (POs) are a subset of nodes of the network. If the network is sequential, it contains registers whose inputs and output are treated as additional PIs/POs in combinational optimization and mapping. It is assumed that each node has a unique integer called its node ID. A fanin (fanout) cone of node n is a subset of all nodes of the network reachable through the fanin (fanout) edges from the given node. A maximum fanout free cone (MFFC) of node n is a subset of the fanin cone, such that every path from a node in the subset to the POs passes through n. Informally, the MFFC of anode contains all the logic used exclusively by the node. When a node is removed, the logic in its MFFC can be removed. Merging node n onto node m is a structural transformation of a network that transfers the fanouts of n to m and removes n and its MFFC. Merging is often


Recording Synthesis History for Sequential Verification

Download Recording Synthesis History for Sequential Verification
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recording Synthesis History for Sequential Verification and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recording Synthesis History for Sequential Verification 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?