Version abc80326

1 files changed, 353 insertions, 0 deletions

diff --git a/src/aig/ntk/ntkTiming.c b/src/aig/ntk/ntkTiming.c
new file mode 100644
index 00000000..f57c7987
--- /dev/null
+++ b/src/aig/ntk/ntkTiming.c
@@ -0,0 +1,353 @@
+/**CFile****************************************************************
+
+  FileName    [ntkTiming.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Netlist representation.]
+
+  Synopsis    [Manipulation of timing information.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - June 20, 2005.]
+
+  Revision    [$Id: ntkTiming.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "ntk.h"
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+extern void * Abc_FrameReadLibLut();   
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NtkPrepareTiming( Ntk_Man_t * pNtk )
+{
+    Ntk_Obj_t * pObj;
+    int i;
+    Ntk_ManForEachObj( pNtk, pObj, i )
+    {
+        pObj->tArrival = pObj->tSlack = 0.0;
+        pObj->tRequired = AIG_INFINITY;
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Sorts the pins in the decreasing order of delays.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Ntk_ManDelayTraceSortPins( Ntk_Obj_t * pNode, int * pPinPerm, float * pPinDelays )
+{
+    Ntk_Obj_t * pFanin;
+    int i, j, best_i, temp;
+    // start the trivial permutation and collect pin delays
+    Ntk_ObjForEachFanin( pNode, pFanin, i )
+    {
+        pPinPerm[i] = i;
+        pPinDelays[i] = Ntk_ObjArrival(pFanin);
+    }
+    // selection sort the pins in the decreasible order of delays
+    // this order will match the increasing order of LUT input pins
+    for ( i = 0; i < Ntk_ObjFaninNum(pNode)-1; i++ )
+    {
+        best_i = i;
+        for ( j = i+1; j < Ntk_ObjFaninNum(pNode); j++ )
+            if ( pPinDelays[pPinPerm[j]] > pPinDelays[pPinPerm[best_i]] )
+                best_i = j;
+        if ( best_i == i )
+            continue;
+        temp = pPinPerm[i]; 
+        pPinPerm[i] = pPinPerm[best_i]; 
+        pPinPerm[best_i] = temp;
+    }
+    // verify
+    assert( Ntk_ObjFaninNum(pNode) == 0 || pPinPerm[0] < Ntk_ObjFaninNum(pNode) );
+    for ( i = 1; i < Ntk_ObjFaninNum(pNode); i++ )
+    {
+        assert( pPinPerm[i] < Ntk_ObjFaninNum(pNode) );
+        assert( pPinDelays[pPinPerm[i-1]] >= pPinDelays[pPinPerm[i]] );
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+float Ntk_ManDelayTraceLut( Ntk_Man_t * pNtk, int fUseLutLib )
+{
+    int fUseSorting = 1;
+    int pPinPerm[32];
+    float pPinDelays[32];
+    If_Lib_t * pLutLib;
+    Ntk_Obj_t * pNode, * pFanin;
+    Vec_Ptr_t * vNodes;
+    float tArrival, tRequired, tSlack, * pDelays;
+    int i, k;
+
+    // get the library
+    pLutLib = fUseLutLib?  Abc_FrameReadLibLut() : NULL;
+    if ( pLutLib && pLutLib->LutMax < Ntk_ManGetFaninMax(pNtk) )
+    {
+        printf( "The max LUT size (%d) is less than the max fanin count (%d).\n", 
+            pLutLib->LutMax, Ntk_ManGetFaninMax(pNtk) );
+        return -AIG_INFINITY;
+    }
+
+    // initialize the arrival times
+    Abc_NtkPrepareTiming( pNtk );
+
+    // propagate arrival times
+    vNodes = Ntk_ManDfs( pNtk );
+    Vec_PtrForEachEntry( vNodes, pNode, i )
+    {
+        tArrival = -AIG_INFINITY;
+        if ( pLutLib == NULL )
+        {
+            Ntk_ObjForEachFanin( pNode, pFanin, k )
+                if ( tArrival < Ntk_ObjArrival(pFanin) + 1.0 )
+                    tArrival = Ntk_ObjArrival(pFanin) + 1.0;
+        }
+        else if ( !pLutLib->fVarPinDelays )
+        {
+            pDelays = pLutLib->pLutDelays[Ntk_ObjFaninNum(pNode)];
+            Ntk_ObjForEachFanin( pNode, pFanin, k )
+                if ( tArrival < Ntk_ObjArrival(pFanin) + pDelays[0] )
+                    tArrival = Ntk_ObjArrival(pFanin) + pDelays[0];
+        }
+        else
+        {
+            pDelays = pLutLib->pLutDelays[Ntk_ObjFaninNum(pNode)];
+            if ( fUseSorting )
+            {
+                Ntk_ManDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
+                Ntk_ObjForEachFanin( pNode, pFanin, k ) 
+                    if ( tArrival < Ntk_ObjArrival(Ntk_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] )
+                        tArrival = Ntk_ObjArrival(Ntk_ObjFanin(pNode,pPinPerm[k])) + pDelays[k];
+            }
+            else
+            {
+                Ntk_ObjForEachFanin( pNode, pFanin, k )
+                    if ( tArrival < Ntk_ObjArrival(pFanin) + pDelays[k] )
+                        tArrival = Ntk_ObjArrival(pFanin) + pDelays[k];
+            }
+        }
+        if ( Ntk_ObjFaninNum(pNode) == 0 )
+            tArrival = 0.0;
+        Ntk_ObjSetArrival( pNode, tArrival );
+    }
+    Vec_PtrFree( vNodes );
+
+    // get the latest arrival times
+    tArrival = -AIG_INFINITY;
+    Ntk_ManForEachPo( pNtk, pNode, i )
+        if ( tArrival < Ntk_ObjArrival(Ntk_ObjFanin0(pNode)) )
+            tArrival = Ntk_ObjArrival(Ntk_ObjFanin0(pNode));
+
+    // initialize the required times
+    Ntk_ManForEachPo( pNtk, pNode, i )
+        if ( Ntk_ObjRequired(Ntk_ObjFanin0(pNode)) > tArrival )
+            Ntk_ObjSetRequired( Ntk_ObjFanin0(pNode), tArrival );
+
+    // propagate the required times
+    vNodes = Ntk_ManDfsReverse( pNtk );
+    Vec_PtrForEachEntry( vNodes, pNode, i )
+    {
+        if ( pLutLib == NULL )
+        {
+            tRequired = Ntk_ObjRequired(pNode) - (float)1.0;
+            Ntk_ObjForEachFanin( pNode, pFanin, k )
+                if ( Ntk_ObjRequired(pFanin) > tRequired )
+                    Ntk_ObjSetRequired( pFanin, tRequired );
+        }
+        else if ( !pLutLib->fVarPinDelays )
+        {
+            pDelays = pLutLib->pLutDelays[Ntk_ObjFaninNum(pNode)];
+            tRequired = Ntk_ObjRequired(pNode) - pDelays[0];
+            Ntk_ObjForEachFanin( pNode, pFanin, k )
+                if ( Ntk_ObjRequired(pFanin) > tRequired )
+                    Ntk_ObjSetRequired( pFanin, tRequired );
+        }
+        else 
+        {
+            pDelays = pLutLib->pLutDelays[Ntk_ObjFaninNum(pNode)];
+            if ( fUseSorting )
+            {
+                Ntk_ManDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
+                Ntk_ObjForEachFanin( pNode, pFanin, k )
+                {
+                    tRequired = Ntk_ObjRequired(pNode) - pDelays[k];
+                    if ( Ntk_ObjRequired(Ntk_ObjFanin(pNode,pPinPerm[k])) > tRequired )
+                        Ntk_ObjSetRequired( Ntk_ObjFanin(pNode,pPinPerm[k]), tRequired );
+                }
+            }
+            else
+            {
+                Ntk_ObjForEachFanin( pNode, pFanin, k )
+                {
+                    tRequired = Ntk_ObjRequired(pNode) - pDelays[k];
+                    if ( Ntk_ObjRequired(pFanin) > tRequired )
+                        Ntk_ObjSetRequired( pFanin, tRequired );
+                }
+            }
+        }
+        // set slack for this object
+        tSlack = Ntk_ObjRequired(pNode) - Ntk_ObjArrival(pNode);
+        assert( tSlack + 0.001 > 0.0 );
+        Ntk_ObjSetSlack( pNode, tSlack < 0.0 ? 0.0 : tSlack );
+    }
+    Vec_PtrFree( vNodes );
+    return tArrival;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Determines timing-critical edges of the node.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+unsigned Ntk_ManDelayTraceTCEdges( Ntk_Man_t * pNtk, Ntk_Obj_t * pNode, float tDelta, int fUseLutLib )
+{
+    int pPinPerm[32];
+    float pPinDelays[32];
+    If_Lib_t * pLutLib;
+    Ntk_Obj_t * pFanin;
+    unsigned uResult = 0;
+    float tRequired, * pDelays;
+    int k;
+    pLutLib = fUseLutLib?  Abc_FrameReadLibLut() : NULL;
+    tRequired = Ntk_ObjRequired(pNode);
+    if ( pLutLib == NULL )
+    {
+        Ntk_ObjForEachFanin( pNode, pFanin, k )
+            if ( tRequired < Ntk_ObjArrival(pFanin) + 1.0 + tDelta )
+                uResult |= (1 << k);
+    }
+    else if ( !pLutLib->fVarPinDelays )
+    {
+        pDelays = pLutLib->pLutDelays[Ntk_ObjFaninNum(pNode)];
+        Ntk_ObjForEachFanin( pNode, pFanin, k )
+            if ( tRequired < Ntk_ObjArrival(pFanin) + pDelays[0] + tDelta )
+                uResult |= (1 << k);
+    }
+    else
+    {
+        pDelays = pLutLib->pLutDelays[Ntk_ObjFaninNum(pNode)];
+        Ntk_ManDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
+        Ntk_ObjForEachFanin( pNode, pFanin, k )
+            if ( tRequired < Ntk_ObjArrival(Ntk_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] + tDelta )
+                uResult |= (1 << pPinPerm[k]);
+    }
+    return uResult;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Delay tracing of the LUT mapped network.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Ntk_ManDelayTracePrint( Ntk_Man_t * pNtk, int fUseLutLib, int fVerbose )
+{
+    Ntk_Obj_t * pNode;
+    If_Lib_t * pLutLib;
+    int i, Nodes, * pCounters;
+    float tArrival, tDelta, nSteps, Num;
+    // get the library
+    pLutLib = fUseLutLib?  Abc_FrameReadLibLut() : NULL;
+    if ( pLutLib && pLutLib->LutMax < Ntk_ManGetFaninMax(pNtk) )
+    {
+        printf( "The max LUT size (%d) is less than the max fanin count (%d).\n", 
+            pLutLib->LutMax, Ntk_ManGetFaninMax(pNtk) );
+        return;
+    }
+    // decide how many steps
+    nSteps = fUseLutLib ? 20 : Ntk_ManLevel(pNtk);
+    pCounters = ALLOC( int, nSteps + 1 );
+    memset( pCounters, 0, sizeof(int)*(nSteps + 1) );
+    // perform delay trace
+    tArrival = Ntk_ManDelayTraceLut( pNtk, fUseLutLib );
+    tDelta = tArrival / nSteps;
+    // count how many nodes have slack in the corresponding intervals
+    Ntk_ManForEachNode( pNtk, pNode, i )
+    {
+        if ( Ntk_ObjFaninNum(pNode) == 0 )
+            continue;
+        Num = Ntk_ObjSlack(pNode) / tDelta;
+        assert( Num >=0 && Num <= nSteps );
+        pCounters[(int)Num]++;
+    }
+    // print the results
+    printf( "Max delay = %6.2f. Delay trace using %s model:\n", tArrival, fUseLutLib? "LUT library" : "unit-delay" );
+    Nodes = 0;
+    for ( i = 0; i < nSteps; i++ )
+    {
+        Nodes += pCounters[i];
+        printf( "%3d %s : %5d  (%6.2f %%)\n", fUseLutLib? 5*(i+1) : i+1, 
+            fUseLutLib? "%":"lev", Nodes, 100.0*Nodes/Ntk_ManNodeNum(pNtk) );
+    }
+    free( pCounters );
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+