18-760 VLSI-CAD:Logic to Layout
               Project 2:Transistor Level Equivalence Checking
 
 

                   Vikas Chandra (vchandra@ece.cmu.edu)
                   Suraj Sudhir (ssudhir@ece.cmu.edu)

Table of Contents

Approach and Implementation

Introduction
Formulation
Optimization Goals
Implementation
Results
Comparison of Transistor- and Gate-level netlists
Explanation
Post-Mortem
Code!!!

Level 0
Level 1
Level 2
Level 3
Level 4

Approach and Implementation

Introduction

         The objective of this project is to analyse transistor- and gate-level netlists and to extract the boolean logic function it implements. The transistor level netlist is read in  and a model of the individual nodes in the MOS circuits is made using using 2 bit signal encoding as [a.0 a.1]where 'a' is the signal variable.
         This pair of formulas (depicted as BDDs in our case) is used to describe the steady state response of the circuit on the inputs. BDDs were implemented using the CUDD package [1]. Each input of the circuit is depicted as two BDDs for a.0 & a.1 and BDD structure of the output will give us the boolean function it represents, in terms of the BDDs for the inputs. Computing the steady state response is a three step process for transistor level netlists, involving

• solution for zero - Here the solution is for the case when the inputs are such that  the NMOS devices are conducting  and the output is pulled down to logic zero.
• solution for one  - Here the solution is for the case whe the inputs are such that the PMOS devices are conducting and the output is pulled up to logic one.
• solution for indefinite case -  Here both PMOS and NMOS devices are non conducting and hence the ouput is possibly indefinite (i.e. floating).

Formulation:

        There are some assumptions in this project to make the analysis of the transistor level netlist simpler-

•          All devices have same "strength", as do all storage nodes in the circuit.
•          There are no ratio tricks, no overriding of values at contended nodes etc. for eg, when both the p-MOS tree

         and n-MOS tree are on in the circuit, the output is X (unknown). We do not analyze the strength of the trees
         to get a value at the output.
•         Also, this analysis will not work for some dynamic circuits which operate by storing charges at the node

         capacitance.
•         When any of the pass transistor is conducting, we assume that its able to pass a "0" or "1" logic value correctly.
•         The netlist description of pass gates looks like this:

        P1 <channel-graph-id> <diffusion_node_1> <poly_gate_node> <diffusion_node_2>
       where <diffusion_node_1> is the signal input node
                       <diffusion_node_2> is the signal output node

Optimization Goals:

        The iterative solution routine solveIter was written as efficiently as possible since it is a critical component in the implementation of this project. Each net in the netlist is described by a data structure that holds information on all the FETs or logic gates connected by that net.
        This allows us to efficiently implement the solveIter routine where all the nets within a channel graph are traversed and the steady state response computed by simply walking the list for each net and computing the results for the channel graph node that the net represents.

Implementation:

    Data Structures

          Each FET or logic gate is described by the following data structure:
            int graph;         // defines the graph number
            int type;            // what type - PFET, NFET, NAND, OR...
            int *inp;            // array holding inputs of this FET/gate
            int out;              // output of the FET/gate
            int ins;               // number of inputs
            BDD Abdd;    // BDD for A

          Each net in the circuit was represented as :
             int node;                 //FETs connected by this net; a linked list of all FETs/gates connected to this net is maintained
             int num;                  //this net's number
             int x;                        //x value
             BDD bdd;               // bdd of this net
             int created;           // this is set to current graph order number when this net's BDD is created
             struct net *next;  //next node in linked list

    Topological Sorting

         We used the DFS topological sorting algorithm from [2]. It is as follows:

          initiate all graph nodes as untouched
         for each variable n that is not touched
            call DFS(n)

          DFS(n)
                 {
               if n is null
                            return;
               if (n.touched = 1)
                    return;
               temp = node adjacent to n in unsorted graph;
               while (temp != null)
                 {
                       if there is a definite order between n and temp
                           DFS (temp);
                                temp = temp.next;
                          }
                        n.touched = 1;
                        put n at the head of sorted list;
                         return;
                  }

   Solution

             Solution of the transistor level netlist was done using a routine solveIter which implements the iterative sort.  However we implemented the gate-level netlist solution also using 2-variable encoding of the inputs. This was done using the following formulae:
 

Boolean Function

out.0 Value

out.1 Value

AND	a.0 + b.0	a.1 & b.1
NAND	a.1 & b.1	a.0 + b.0
OR	a.0 & b.0	a.1 + b.1
NOR	a.1 + b.1	a.0 & b.0
XOR	(a.0 + b.1) & (a.1 + b.0)	a.0 & b.1 + a.1 & b.0
XNOR	a.0 & b.1 + a.1 & b.0	(a.0 + b.1) & (a.1 + b.0)
NOT	a.1	a.0

     This allows us to generate the checker output thats useful for BOTH gate- and transistor-level netlists, and also simplifies the final checking to a mere equivalence check (==) in CUDD.

    Overall Strategy

Results:

       We ran all benchmarks from levels 0 through 4 in the project benchmarks directory and results are reported in the Results and Analysis section. All of these gave proper results.

Comparision of Gate- and Transistor-level netlists:
             Since our solution technique gave us identical checker output files for both transistor- and gate-level netlists, it was a simple matter   of diff-ing the files to check whether they were the same. Further if there were differences, an input pattern that differs is printed. To do this we checked the out.0 and out.1 outputs for each output and if one of these differed, then we XOR the respective output (out.0 or out.1) - we dont print both if both differ, only one - and the XORed term holds those minterms that are different. We then print one of these.

Explanation of Results:
           The program generates a BDD representation of the steady state response of the system defined by the transistor- or gate-level netlist. The 2-bit encoding enables us to separately indicate the effect of logic high and logic low values of the inputs on the outputs. The main motivation behind the two-bit encoding is the modelling of dont-cares in the circuit. While this is not present in gate-level netlists, it can be present in transistor level netlists where a non-conducting gate may cause an undefined (or dont-care) output. Modelling the rest of the circuit based on this dont-care is an important aspect of achieving a proper steady state behavioral description.
            In real applications, the actual logic output can be computed from the BDDs by simply traversing the path for the specific input combination. For each input a, if its at logic 1, then a.0 becomes 0 and a.1 becomes 1. For a logic 0 input, the a.0 and a.1 values are interchanged.

Post Mortem:
         We would probably have chosen to make things a bit more modular than have huge functions and everything in one file. It made debugging more difficult since we had to go thru the code with a fine-toothed comb at times to figure out what broke. Implementation was satisfactory but the way of coding could have been more planned.

Code:
     The code for the project is at http://www.ece.cmu.edu/~ssudhir/760Web760Code/trans.cc

Results and Analysis

Level 0:
     Inv Tran
        Input         Output
     Inv Gate
        Input         Output
     2 input NAND (Transistor level)
        Input         Output
     2 Input NAND (Gate level)
        Input         Output

Level 1:

     2 Inverters (Transistor level)
        Input         Output
     2 Inverters (Gate level)
      Input           Output
     3 Inverters (Transistor level)
       Input          Output
     3  Inverters (Gate level)
       Input          Output
     4 Inverters (Transistor level)
       Input          Output
     4 Inverters (Gate level)
       Input           Output
     5 Inverters (Transistor level)
       Input           Output
     5 Inverters (Gate level)
       Input           Output
     C17 (Transistor level)
       Input           Output
     C17 (Gate level)
       Input           Output

Level2:

    InvPN (Transistor level)
        Input           Output

Level 3:

      a1 (Transistor level)
        Input          Output
      a2 (Transistor level)
        Input           Output
      The comparision result is  here

Level 4 :

    C432.TRAN and c432.GATE
        Input1         Input2
        The comparision report is here

    C432b.TRAN and c432b.GATE
        Input1         Input2
        The comparision report is here
 

    mix17.TRAN and mix17.GATE
        Input1        Output1
        Input2        Output2
        The comparision report is here

    mix17b.TRAN and mix17b.GATE
        Input1        Output1
        Input2        Output2
        The comparision report is here

    mix17c.TRAN and mix17c.GATE
        Input1        Output1
        Input2        Output2
        The comparision report is here
 

References
[1] Colorado University Decision Diagrams v2.0, vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html
[2] R.L.Rivest, C.E.Leiserson, T.H.Cormen, "Introduction to Algorithms", Prentice Hall Intl.