PO partitioning algorithm.

1 files changed, 291 insertions, 2 deletions

diff --git a/src/aig/gia/giaCone.c b/src/aig/gia/giaCone.c
index da4918ed..56dae32a 100644
--- a/src/aig/gia/giaCone.c
+++ b/src/aig/gia/giaCone.c
@@ -19,6 +19,7 @@
 ***********************************************************************/
 
 #include "gia.h"
+#include "misc/extra/extra.h"
 
 ABC_NAMESPACE_IMPL_START
 
@@ -271,7 +272,42 @@ int Gia_ManConeMark( Gia_Man_t * p, int iOut, int Limit )
   SeeAlso     []
 
 ***********************************************************************/
-Gia_Man_t * Gia_ManConeExtract( Gia_Man_t * p, int iOut, int nDelta, int nOutsMin, int nOutsMax )
+int Gia_ManCountFlops( Gia_Man_t * p, Vec_Int_t * vOuts )
+{
+    int Limit = ABC_INFINITY;
+    Vec_Int_t * vRoots;
+    Gia_Obj_t * pObj;
+    int i, RetValue, iOut;
+    // start the outputs
+    vRoots = Vec_IntAlloc( 100 );
+    Vec_IntForEachEntry( vOuts, iOut, i )
+    {
+        pObj = Gia_ManPo( p, iOut );
+        Vec_IntPush( vRoots, Gia_ObjId(p, pObj) );
+    }
+    // mark internal nodes
+    Gia_ManIncrementTravId( p );
+    Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) );
+    Gia_ManForEachObjVec( vRoots, p, pObj, i )
+        if ( Gia_ManConeMark_rec( p, pObj, vRoots, Limit ) )
+            break;
+    RetValue = Vec_IntSize( vRoots ) - Vec_IntSize(vOuts);
+    Vec_IntFree( vRoots );
+    return RetValue;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Gia_Man_t * Gia_ManFindPoPartition3( Gia_Man_t * p, int iOut, int nDelta, int nOutsMin, int nOutsMax, int fVerbose, Vec_Ptr_t ** pvPosEquivs )
 {
 /*
     int i, Count = 0;
@@ -283,11 +319,264 @@ Gia_Man_t * Gia_ManConeExtract( Gia_Man_t * p, int iOut, int nDelta, int nOutsMi
 
     // add other outputs as long as they are nDelta away
 */
-    Opa_ManPerform( p );
+//    Opa_ManPerform( p );
 
     return NULL;
 }
 
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Int_t * Gia_ManFindPivots( Gia_Man_t * p, int SelectShift, int fVerbose )
+{
+    Vec_Int_t * vPivots, * vWeights;
+    Vec_Int_t * vCount, * vResult;
+    int i, j, Count, * pPerm, Limit;
+/*
+    Gia_Obj_t * pObj;
+    // count MUX controls
+    vCount = Vec_IntStart( Gia_ManObjNum(p) );
+    Gia_ManForEachAnd( p, pObj, i )
+    {
+        Gia_Obj_t * pNodeC, * pNodeT, * pNodeE;
+        if ( !Gia_ObjIsMuxType(pObj) ) 
+            continue;
+        pNodeC = Gia_ObjRecognizeMux( pObj, &pNodeT, &pNodeE );
+        Vec_IntAddToEntry( vCount, Gia_ObjId(p, Gia_Regular(pNodeC)), 1 );
+    }
+*/
+    // count references
+    Gia_ManCreateRefs( p );
+    vCount = Vec_IntAllocArray( p->pRefs, Gia_ManObjNum(p) ); p->pRefs = NULL;
+
+    // collect nodes 
+    vPivots  = Vec_IntAlloc( 100 );
+    vWeights = Vec_IntAlloc( 100 );
+    Vec_IntForEachEntry( vCount, Count, i )
+    {
+        if ( Count < 2 ) continue;
+        Vec_IntPush( vPivots, i );
+        Vec_IntPush( vWeights, Count );
+    }
+    Vec_IntFree( vCount );
+
+    if ( fVerbose )
+        printf( "Selected %d nodes (out of %d) with more than one fanout.\n", Vec_IntSize(vWeights), Gia_ManPiNum(p) + Gia_ManAndNum(p) );
+
+    // permute
+    Gia_ManRandom(1);
+    Gia_ManRandom(0);
+    for ( i = 0; i < Vec_IntSize(vWeights); i++ )
+    {
+        j = (Gia_ManRandom(0) >> 1) % Vec_IntSize(vWeights);
+        ABC_SWAP( int, vPivots->pArray[i], vPivots->pArray[j] );
+        ABC_SWAP( int, vWeights->pArray[i], vWeights->pArray[j] );
+    }
+    // sort
+    pPerm = Abc_QuickSortCost( Vec_IntArray(vWeights), Vec_IntSize(vWeights), 1 );
+    // select    
+    Limit = Abc_MinInt( 64, Vec_IntSize(vWeights) );
+    vResult = Vec_IntAlloc( Limit );
+    for ( i = 0; i < Limit; i++ )
+    {
+        j = (i + SelectShift) % Vec_IntSize(vWeights);
+        if ( fVerbose )
+            printf( "%6d : Pivot = %6d  Weight = %6d\n", j, Vec_IntEntry(vPivots, pPerm[j]), Vec_IntEntry(vWeights, pPerm[j]) );
+        Vec_IntPush( vResult, Vec_IntEntry(vPivots, pPerm[j]) );
+    }
+
+    Vec_IntFree( vPivots );
+    Vec_IntFree( vWeights );
+    ABC_FREE( pPerm );
+
+    return vResult;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Wrd_t * Gia_ManDeriveSigns( Gia_Man_t * p, Vec_Int_t * vPivots, int fVerbose )
+{
+    Vec_Wrd_t * vSigns;
+    Gia_Obj_t * pObj, * pObjRi;
+    int i, fChange = 1, Counter;
+
+    Gia_ManFillValue( p );
+    Gia_ManForEachObjVec( vPivots, p, pObj, i )
+        pObj->Value = i;
+
+    if ( fVerbose )
+        printf( "Signature propagation: " );
+    vSigns = Vec_WrdStart( Gia_ManObjNum(p) );
+    while ( fChange )
+    {
+        fChange = 0;
+        Gia_ManForEachObj( p, pObj, i )
+        {
+            if ( ~pObj->Value )
+            {
+                assert( pObj->Value >= 0 && pObj->Value < 64 );
+                *Vec_WrdEntryP( vSigns, i ) |= ( 1 << pObj->Value );
+            }
+            if ( Gia_ObjIsAnd(pObj) )
+                *Vec_WrdEntryP( vSigns, i ) |= Vec_WrdEntry(vSigns, Gia_ObjFaninId0(pObj, i)) | Vec_WrdEntry(vSigns, Gia_ObjFaninId1(pObj, i));
+            else if ( Gia_ObjIsCo(pObj) )
+                *Vec_WrdEntryP( vSigns, i ) |= Vec_WrdEntry(vSigns, Gia_ObjFaninId0(pObj, i));
+        }
+        Counter = 0;
+        Gia_ManForEachRiRo( p, pObjRi, pObj, i )
+        {
+            word Value = Vec_WrdEntry(vSigns, Gia_ObjId(p, pObj));
+            *Vec_WrdEntryP( vSigns, Gia_ObjId(p, pObj) ) |= Vec_WrdEntry(vSigns, Gia_ObjId(p, pObjRi));
+            if ( Value != Vec_WrdEntry(vSigns, Gia_ObjId(p, pObj)) )
+                fChange = 1, Counter++;
+        }
+        if ( fVerbose )
+            printf( "%d ", Counter );
+    }
+    if ( fVerbose )
+       printf( "\n" );
+    return vSigns;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Ptr_t * Gia_ManHashOutputs( Gia_Man_t * p, Vec_Wrd_t * vSigns, int fVerbose )
+{
+    Gia_Obj_t * pObj;
+    Vec_Ptr_t * vBins;
+    Vec_Int_t * vBin;
+    int i, nBins = Abc_PrimeCudd( Gia_ManPoNum(p) );
+    int * pBins = ABC_FALLOC( int, nBins );
+    // create hash table of outputs
+    vBins = Vec_PtrAlloc( 1000 );
+    Gia_ManForEachPo( p, pObj, i )
+    {
+        word Sign = Vec_WrdEntry( vSigns, Gia_ObjId(p, pObj) );
+        int Offset = (int)(Sign % nBins);
+        if ( pBins[Offset] == -1 )
+        {
+            pBins[Offset] = Vec_PtrSize( vBins );
+            vBin = Vec_IntAlloc( 4 );
+            Vec_IntPush( vBin, Offset );
+            Vec_PtrPush( vBins, vBin );
+        }
+        vBin = (Vec_Int_t *)Vec_PtrEntry( vBins, pBins[Offset] );
+        Vec_IntPush( vBin, i );
+    }
+    ABC_FREE( pBins );
+    Vec_VecSort( (Vec_Vec_t *)vBins, 1 );
+
+    if ( fVerbose )
+        printf( "Computed %d partitions:\n", Vec_PtrSize(vBins) );
+    Vec_PtrForEachEntry( Vec_Int_t *, vBins, vBin, i )
+    {
+        if ( fVerbose )
+        {
+            int Offset = Vec_IntEntry( vBin, 0 );
+            word Sign = Vec_WrdEntry( vSigns, Offset );
+            printf( "%6d : Support ", i );
+            Extra_PrintBinary( stdout, &Offset, 64 );
+            printf( "   " );
+        }
+
+        // remove the first item
+        ABC_SWAP( int, vBin->pArray[0], vBin->pArray[Vec_IntSize(vBin)-1] );
+        Vec_IntPop( vBin );
+        Vec_IntSort( vBin, 0 );
+
+        if ( fVerbose )
+        {
+            printf( "PO = %7d  ", Vec_IntSize(vBin) );
+            printf( "FF = %7d", Gia_ManCountFlops(p, vBin) );
+            printf( "\n" );
+        }
+    }
+//    printf( "\n" );
+    return vBins;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Gia_Man_t * Gia_ManFindPoPartition2( Gia_Man_t * p, int iStartNum, int nDelta, int nOutsMin, int nOutsMax, int fSetLargest, int fVerbose, Vec_Ptr_t ** pvPosEquivs )
+{
+    return NULL;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Gia_Man_t * Gia_ManFindPoPartition( Gia_Man_t * p, int SelectShift, int fSetLargest, int fVerbose, Vec_Ptr_t ** pvPosEquivs )
+{
+    Gia_Man_t * pGia = NULL;
+    Vec_Int_t * vPivots;
+    Vec_Wrd_t * vSigns;
+    Vec_Ptr_t * vParts;
+    Vec_Int_t * vPart;
+    vPivots = Gia_ManFindPivots( p, SelectShift, fVerbose );
+    vSigns = Gia_ManDeriveSigns( p, vPivots, fVerbose );
+    Vec_IntFree( vPivots );
+    vParts = Gia_ManHashOutputs( p, vSigns, fVerbose );
+    Vec_WrdFree( vSigns );
+    if ( fSetLargest )
+    {
+        vPart = Vec_VecEntryInt( (Vec_Vec_t *)vParts, 0 );
+        pGia = Gia_ManDupCones( p, Vec_IntArray(vPart), Vec_IntSize(vPart), 1 );
+    }
+    if ( pvPosEquivs )
+    {
+        *pvPosEquivs = vParts;
+        printf( "Partitioning algorithm divided %d POs into %d groups.\n", Gia_ManPoNum(p), Vec_PtrSize(vParts) );
+    }
+    else
+        Vec_VecFree( (Vec_Vec_t *)vParts );
+    return pGia;
+}
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////