Version abc90217

1 files changed, 430 insertions, 64 deletions

diff --git a/src/aig/gia/giaForce.c b/src/aig/gia/giaForce.c
index eae0a1cc..e5080e81 100644
--- a/src/aig/gia/giaForce.c
+++ b/src/aig/gia/giaForce.c
@@ -20,17 +20,221 @@
 
 #include "gia.h"
 
+/* 
+    The code is based on the paper by F. A. Aloul, I. L. Markov, and K. A. Sakallah.
+    "FORCE: A Fast and Easy-To-Implement Variable-Ordering Heuristic", Proc. GLSVLSI’03.
+*/
+
 ////////////////////////////////////////////////////////////////////////
 ///                        DECLARATIONS                              ///
 ////////////////////////////////////////////////////////////////////////
 
+typedef struct For_Obj_t_ For_Obj_t;
+struct For_Obj_t_
+{
+    int            iObj;
+    float          lNode;
+};
+
+typedef struct For_Man_t_ For_Man_t;
+struct For_Man_t_
+{
+    Gia_Man_t *    pGia;             // the original AIG manager
+    int            nObjs;            // the number of objects
+    int            iObj;             // the last added object
+    int *          pPlace;           // Placeing of objects
+    int *          piNext;           // array of next pointers
+    int *          piRoot;           // array of root pointers
+    float *        plEdge;           // edge coordinates
+    For_Obj_t *    pNodes;           // the array of nodes
+};
+
+static inline int  Gia_ObjPlace( For_Man_t * p, Gia_Obj_t * pObj )        { return p->pPlace[Gia_ObjId(p->pGia, pObj)];         }
+static inline int  Gia_ObjPlaceFanin0( For_Man_t * p, Gia_Obj_t * pObj )  { return p->pPlace[Gia_ObjFaninId0p(p->pGia, pObj)];  }
+static inline int  Gia_ObjPlaceFanin1( For_Man_t * p, Gia_Obj_t * pObj )  { return p->pPlace[Gia_ObjFaninId1p(p->pGia, pObj)];  }
+
+static inline int  Gia_ObjEdge( For_Man_t * p, Gia_Obj_t * pObj )         { return p->plEdge[Gia_ObjId(p->pGia, pObj)];         }
+static inline int  Gia_ObjEdgeFanin0( For_Man_t * p, Gia_Obj_t * pObj )   { return p->plEdge[Gia_ObjFaninId0p(p->pGia, pObj)];  }
+static inline int  Gia_ObjEdgeFanin1( For_Man_t * p, Gia_Obj_t * pObj )   { return p->plEdge[Gia_ObjFaninId1p(p->pGia, pObj)];  }
+
 ////////////////////////////////////////////////////////////////////////
 ///                     FUNCTION DEFINITIONS                         ///
 ////////////////////////////////////////////////////////////////////////
 
 /**Function*************************************************************
 
-  Synopsis    [This is implementation of qsort in MiniSat.]
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+For_Man_t * For_ManStart( Gia_Man_t * pGia )
+{
+    For_Man_t * p;
+    p = ABC_CALLOC( For_Man_t, 1 );
+    p->pGia   = pGia;
+    p->nObjs  = Gia_ManObjNum(pGia);
+    p->pPlace = ABC_ALLOC( int, p->nObjs );
+    p->piNext = ABC_ALLOC( int, p->nObjs );
+    p->piRoot = ABC_ALLOC( int, p->nObjs );
+    p->plEdge = ABC_ALLOC( float, p->nObjs );
+    p->pNodes = ABC_ALLOC( For_Obj_t, p->nObjs );
+    return p;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void For_ManStop( For_Man_t * p )
+{
+    ABC_FREE( p->pPlace );
+    ABC_FREE( p->piNext );
+    ABC_FREE( p->piRoot );
+    ABC_FREE( p->plEdge );
+    ABC_FREE( p->pNodes );
+    ABC_FREE( p );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Derives random ordering of nodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void For_ManSetInitPlaceRandom( For_Man_t * p )
+{
+    int i, Temp, iNext;
+    Aig_ManRandom( 1 );
+    for ( i = 0; i < p->nObjs; i++ )
+        p->pPlace[i] = i;
+    for ( i = 0; i < p->nObjs; i++ )
+    {
+        iNext = Aig_ManRandom( 0 ) % p->nObjs;
+        Temp = p->pPlace[i];
+        p->pPlace[i] = p->pPlace[iNext];
+        p->pPlace[iNext] = Temp;
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void For_ManSetInitPlaceDfs_rec( For_Man_t * p, Gia_Obj_t * pObj, int fRev )
+{
+    if ( pObj->fMark0 )
+        return;
+    pObj->fMark0 = 1;
+    if ( Gia_ObjIsCi(pObj) || Gia_ObjIsConst0(pObj) )
+    {
+        p->pPlace[ Gia_ObjId(p->pGia, pObj) ] = p->iObj++;
+        return;
+    }
+    if ( Gia_ObjIsCo(pObj) )
+    {
+        For_ManSetInitPlaceDfs_rec( p, Gia_ObjFanin0(pObj), fRev );
+        p->pPlace[ Gia_ObjId(p->pGia, pObj) ] = p->iObj++;
+        return;
+    }
+    assert( Gia_ObjIsAnd(pObj) );
+    if ( fRev )
+    {
+        For_ManSetInitPlaceDfs_rec( p, Gia_ObjFanin1(pObj), fRev );
+        For_ManSetInitPlaceDfs_rec( p, Gia_ObjFanin0(pObj), fRev );
+    }
+    else
+    {
+        For_ManSetInitPlaceDfs_rec( p, Gia_ObjFanin0(pObj), fRev );
+        For_ManSetInitPlaceDfs_rec( p, Gia_ObjFanin1(pObj), fRev );
+    }
+    p->pPlace[ Gia_ObjId(p->pGia, pObj) ] = p->iObj++;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Derives DFS ordering of nodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void For_ManSetInitPlaceDfs( For_Man_t * p, int fRev )
+{
+    Gia_Obj_t * pObj;
+    int i;
+    p->iObj = 0;
+    Gia_ManCleanMark0( p->pGia );
+    For_ManSetInitPlaceDfs_rec( p, Gia_ManConst0(p->pGia), fRev );
+    Gia_ManForEachCo( p->pGia, pObj, i )
+        For_ManSetInitPlaceDfs_rec( p, pObj, fRev );
+    Gia_ManForEachCi( p->pGia, pObj, i )
+        if ( pObj->fMark0 == 0 )
+            For_ManSetInitPlaceDfs_rec( p, pObj, fRev );
+    assert( p->iObj == p->nObjs );
+    Gia_ManCleanMark0( p->pGia );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Computes span for the given placement.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+double For_ManGetEdgeSpan( For_Man_t * p )
+{
+    double Result = 0.0;
+    Gia_Obj_t * pObj;
+    int i, Diff;
+    Gia_ManForEachAnd( p->pGia, pObj, i )
+    {
+        Diff    = Gia_ObjPlace(p, pObj) - Gia_ObjPlaceFanin0(p, pObj);
+        Result += (double)ABC_ABS(Diff);
+        Diff    = Gia_ObjPlace(p, pObj) - Gia_ObjPlaceFanin1(p, pObj);
+        Result += (double)ABC_ABS(Diff);
+    }
+    Gia_ManForEachCo( p->pGia, pObj, i )
+    {
+        Diff    = Gia_ObjPlace(p, pObj) - Gia_ObjPlaceFanin0(p, pObj);
+        Result += (double)ABC_ABS(Diff);
+    }
+    return Result;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Computes max cut of the given placement.]
 
   Description []
                
@@ -39,58 +243,133 @@
   SeeAlso     []
 
 ***********************************************************************/
-static int num_cmp ( int * x, int * y) { return ((*x) < (*y)) ? -1 : 1; }
-// Returns a random float 0 <= x < 1. Seed must never be 0.
-static inline double drand(double* seed) {
-    int q;
-    *seed *= 1389796;
-    q = (int)(*seed / 2147483647);
-    *seed -= (double)q * 2147483647;
-    return *seed / 2147483647; }
-// Returns a random integer 0 <= x < size. Seed must never be 0.
-static inline int irand(double* seed, int size) {
-    return (int)(drand(seed) * size); }
-static inline void selectionsort(int* array, int size, int(*comp)(const void *, const void *))
+int For_ManGetMaxCut( For_Man_t * p )
 {
-    int     i, j, best_i;
-    int     tmp;
-    for (i = 0; i < size-1; i++){
-        best_i = i;
-        for (j = i+1; j < size; j++){
-            if (comp(array + j, array + best_i) < 0)
-                best_i = j;
+    Gia_Obj_t * pObj;
+    int i, iObj, iFan, * pTemp;
+    int nCutCut, nCutMax;
+    pTemp = ABC_CALLOC( int, p->nObjs );
+    Gia_ManForEachAnd( p->pGia, pObj, i )
+    {
+        iObj = Gia_ObjPlace(p, pObj);
+        iFan = Gia_ObjPlaceFanin0(p, pObj);
+        if ( iObj < iFan )
+        {
+            pTemp[iObj]++;
+            pTemp[iFan]--;
+        }
+        else
+        {
+            pTemp[iObj]--;
+            pTemp[iFan]++;
+        }
+        iObj = Gia_ObjPlace(p, pObj);
+        iFan = Gia_ObjPlaceFanin1(p, pObj);
+        if ( iObj < iFan )
+        {
+            pTemp[iObj]++;
+            pTemp[iFan]--;
         }
-        tmp = array[i]; array[i] = array[best_i]; array[best_i] = tmp;
+        else
+        {
+            pTemp[iObj]--;
+            pTemp[iFan]++;
+        }
+    }
+    Gia_ManForEachCo( p->pGia, pObj, i )
+    {
+        iObj = Gia_ObjPlace(p, pObj);
+        iFan = Gia_ObjPlaceFanin0(p, pObj);
+        if ( iObj < iFan )
+        {
+            pTemp[iObj]++;
+            pTemp[iFan]--;
+        }
+        else
+        {
+            pTemp[iObj]--;
+            pTemp[iFan]++;
+        }
+    }
+    nCutCut = nCutMax = 0;
+    for ( i = 0; i < p->nObjs; i++ )
+    {
+        nCutCut += pTemp[i];
+        nCutMax = ABC_MAX( nCutCut, nCutMax );
     }
+    ABC_FREE( pTemp );
+    assert( nCutCut == 0 );
+    return nCutMax;
 }
-static void sortrnd(int* array, int size, int(*comp)(const void *, const void *), double* seed)
+
+/**Function*************************************************************
+
+  Synopsis    [Computes hyper-edge centers.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void For_ManEdgeCenters( For_Man_t * p )
 {
-    if (size <= 15)
-        selectionsort(array, size, comp);
-    else{
-        int *  pivot = array + irand(seed, size);
-        int    tmp;
-        int    i = -1;
-        int    j = size;
-        for(;;){
-            do i++; while(comp(array + i, pivot)<0);
-            do j--; while(comp(pivot, array + j)<0);
-            if (i >= j) break;
-            tmp = array[i]; array[i] = array[j]; array[j] = tmp;
+    Gia_Obj_t * pObj;
+    int i;
+    memset( p->plEdge, 0, sizeof(float) * p->nObjs );
+    Gia_ManForEachObj( p->pGia, pObj, i )
+    {
+        p->plEdge[i] = Gia_ObjPlace(p, pObj);
+        if ( Gia_ObjIsAnd(pObj) )
+        {
+            p->plEdge[Gia_ObjFaninId0p(p->pGia, pObj)] += Gia_ObjPlace(p, pObj);
+            p->plEdge[Gia_ObjFaninId1p(p->pGia, pObj)] += Gia_ObjPlace(p, pObj);
+        }
+        else if ( Gia_ObjIsCo(pObj) )
+        {
+            p->plEdge[Gia_ObjFaninId0p(p->pGia, pObj)] += Gia_ObjPlace(p, pObj);
         }
-        sortrnd(array    , i     , comp, seed);
-        sortrnd(&array[i], size-i, comp, seed);
     }
+    Gia_ManForEachObj( p->pGia, pObj, i )
+        p->plEdge[i] /= 1.0 + Gia_ObjRefs( p->pGia, pObj );
 }
-void minisat_sort(int* array, int size, int(*comp)(const void *, const void *))
+
+/**Function*************************************************************
+
+  Synopsis    [Computes object centers.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void For_ManObjCenters( For_Man_t * p )
 {
-    double seed = 91648253;
-    sortrnd(array,size,comp,&seed);
+    Gia_Obj_t * pObj;
+    int i;
+    Gia_ManForEachObj( p->pGia, pObj, i )
+    {
+        p->pNodes[i].lNode = Gia_ObjEdge(p, pObj);
+        if ( Gia_ObjIsAnd(pObj) )
+        {
+            p->pNodes[i].lNode += Gia_ObjEdgeFanin0(p, pObj);
+            p->pNodes[i].lNode += Gia_ObjEdgeFanin1(p, pObj);
+            p->pNodes[i].lNode /= 3.0;
+        }
+        else if ( Gia_ObjIsCo(pObj) )
+        {
+            p->pNodes[i].lNode += Gia_ObjEdgeFanin0(p, pObj);
+            p->pNodes[i].lNode /= 2.0;
+        }
+    }
 }
 
 /**Function*************************************************************
 
-  Synopsis    []
+  Synopsis    [Sorts objects by their new centers.]
 
   Description []
                
@@ -99,14 +378,60 @@ void minisat_sort(int* array, int size, int(*comp)(const void *, const void *))
   SeeAlso     []
 
 ***********************************************************************/
-int * Gia_SortGetTest( int nSize )
+int For_ObjCompare( For_Obj_t ** pp0, For_Obj_t ** pp1 )
 {
-    int i, * pArray;
-    Aig_ManRandom( 1 );
-    pArray = ABC_ALLOC( int, nSize );
-    for ( i = 0; i < nSize; i++ )
-        pArray[i] = (Aig_ManRandom( 0 ) >> 2);
-    return pArray;
+    if ( (*pp0)->lNode < (*pp1)->lNode )
+        return -1;
+    if ( (*pp0)->lNode > (*pp1)->lNode )
+        return 1;
+    return 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Sorts objects by their new centers.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+ 
+***********************************************************************/
+void For_ManSortObjects( For_Man_t * p )
+{
+    For_Obj_t * pNode, * pPrev;
+    Vec_Ptr_t * vArray;
+    int i, k, iPlace;
+    // link the nodes into lists by cost
+    memset( p->piRoot, 0xff, sizeof(int) * p->nObjs );
+    for ( i = 0; i < p->nObjs; i++ )
+    {
+        p->pNodes[i].iObj = i;
+        iPlace = (int)p->pNodes[i].lNode;
+        assert( iPlace >= 0 && iPlace < p->nObjs );
+        p->piNext[i] = p->piRoot[iPlace];
+        p->piRoot[iPlace] = i;        
+    }
+    // recostruct the order
+    p->iObj = 0;
+    pPrev = NULL;
+    vArray = Vec_PtrAlloc( 100 );
+    for ( i = 0; i < p->nObjs; i++ )
+    {
+        Vec_PtrClear( vArray );
+        for ( k = p->piRoot[i]; ~((unsigned)k); k = p->piNext[k] )
+            Vec_PtrPush( vArray, p->pNodes + k );
+        Vec_PtrSort( vArray, (int (*)())For_ObjCompare ); 
+        Vec_PtrForEachEntry( vArray, pNode, k )
+        {
+            p->pPlace[ pNode->iObj ] = p->iObj++;
+            assert( !pPrev || pPrev->lNode <= pNode->lNode );
+            pPrev = pNode;
+        }
+    }
+    Vec_PtrFree( vArray );
+    assert( p->iObj == p->nObjs );
 }
 
 /**Function*************************************************************
@@ -120,11 +445,28 @@ int * Gia_SortGetTest( int nSize )
   SeeAlso     []
 
 ***********************************************************************/
-void Gia_SortVerifySorted( int * pArray, int nSize )
+void For_ManPlaceByForce( For_Man_t * p )
 {
-    int i;
-    for ( i = 1; i < nSize; i++ )
-        assert( pArray[i-1] <= pArray[i] );
+    int clk, Iter, fUseCut = 1;
+    double iCostThis, iCostPrev;
+    iCostThis = fUseCut? For_ManGetMaxCut(p) : For_ManGetEdgeSpan(p);
+    printf( "Init = %12.0f. \n", iCostThis );
+    Iter = 0;
+    do {
+        Iter++;
+        iCostPrev = iCostThis;
+clk = clock();
+        For_ManEdgeCenters( p );
+//ABC_PRT( "Time", clock() - clk );
+clk = clock();
+        For_ManObjCenters( p );
+//ABC_PRT( "Time", clock() - clk );
+clk = clock();
+        For_ManSortObjects( p );
+//ABC_PRT( "Time", clock() - clk );
+        iCostThis = fUseCut? For_ManGetMaxCut(p) : For_ManGetEdgeSpan(p);
+        printf( "%4d = %12.0f. \n", Iter, iCostThis );
+    } while ( iCostPrev > iCostThis );
 }
 
 /**Function*************************************************************
@@ -138,23 +480,47 @@ void Gia_SortVerifySorted( int * pArray, int nSize )
   SeeAlso     []
 
 ***********************************************************************/
-void Gia_SortTest()
+void For_ManExperiment( Gia_Man_t * pGia )
 {
-    int nSize = 1000000;
-    int * pArray;
+    For_Man_t * p;
     int clk = clock();
-    pArray = Gia_SortGetTest( nSize );
+    p = For_ManStart( pGia );
+    Gia_ManCreateRefs( pGia );
+
+    // use DSF order
 clk = clock();
-    qsort( pArray, nSize, 4, (int (*)(const void *, const void *)) num_cmp );
-ABC_PRT( "qsort  ", clock() - clk );
-    Gia_SortVerifySorted( pArray, nSize );
-    ABC_FREE( pArray );
-    pArray = Gia_SortGetTest( nSize );
+    For_ManSetInitPlaceDfs( p, 0 );
+    printf( "Tot span = %12.0f  ", For_ManGetEdgeSpan(p) );
+    printf( "Max span = %8d  ", For_ManGetMaxCut(p) );
+ABC_PRT( "Time", clock() - clk );
+
+clk = clock();
+    For_ManPlaceByForce( p );
+ABC_PRT( "Time", clock() - clk );
+
+    // use modified DFS order
+clk = clock();
+    For_ManSetInitPlaceDfs( p, 1 );
+    printf( "Tot span = %12.0f  ", For_ManGetEdgeSpan(p) );
+    printf( "Max span = %8d  ", For_ManGetMaxCut(p) );
+ABC_PRT( "Time", clock() - clk );
+
 clk = clock();
-    minisat_sort( pArray, nSize, (int (*)(const void *, const void *)) num_cmp );
-ABC_PRT( "minisat", clock() - clk );
-    Gia_SortVerifySorted( pArray, nSize );
-    ABC_FREE( pArray );
+    For_ManPlaceByForce( p );
+ABC_PRT( "Time", clock() - clk );
+
+    // use random order
+clk = clock();
+    For_ManSetInitPlaceRandom( p );
+    printf( "Tot span = %12.0f  ", For_ManGetEdgeSpan(p) );
+    printf( "Max span = %8d  ", For_ManGetMaxCut(p) );
+ABC_PRT( "Time", clock() - clk );
+
+clk = clock();
+    For_ManPlaceByForce( p );
+ABC_PRT( "Time", clock() - clk );
+
+    For_ManStop( p );
 }
 
 ////////////////////////////////////////////////////////////////////////