From bc504219287b22898d5e7c6e1d5756265b957eca Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 1 May 2013 12:45:34 -0700 Subject: Minor changes and improvement in PO partitioning (command &popart). --- src/aig/gia/giaCone.c | 53 +++++++++++++++++++++++++-------------------------- src/base/abci/abc.c | 13 +++++++------ src/misc/vec/vecHsh.h | 14 ++++++++++++++ 3 files changed, 47 insertions(+), 33 deletions(-) diff --git a/src/aig/gia/giaCone.c b/src/aig/gia/giaCone.c index 06ef73f5..d35aefb8 100644 --- a/src/aig/gia/giaCone.c +++ b/src/aig/gia/giaCone.c @@ -20,6 +20,8 @@ #include "gia.h" #include "misc/extra/extra.h" +#include "misc/vec/vecHsh.h" +#include "misc/vec/vecWec.h" ABC_NAMESPACE_IMPL_START @@ -384,7 +386,15 @@ Vec_Int_t * Gia_ManFindPivots( Gia_Man_t * p, int SelectShift, int fOnlyCis, int ABC_SWAP( int, vWeights->pArray[i], vWeights->pArray[j] ); } // sort - pPerm = Abc_QuickSortCost( Vec_IntArray(vWeights), Vec_IntSize(vWeights), 1 ); + if ( SelectShift == 0 ) + pPerm = Abc_QuickSortCost( Vec_IntArray(vWeights), Vec_IntSize(vWeights), 1 ); + else + { + Vec_Int_t * vTemp = Vec_IntStartNatural( Vec_IntSize(vWeights) ); + pPerm = Vec_IntReleaseArray( vTemp ); + Vec_IntFree( vTemp ); + } + // select Limit = Abc_MinInt( 64, Vec_IntSize(vWeights) ); vResult = Vec_IntAlloc( Limit ); @@ -471,29 +481,23 @@ Vec_Wrd_t * Gia_ManDeriveSigns( Gia_Man_t * p, Vec_Int_t * vPivots, int fVerbose ***********************************************************************/ 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 ); + Vec_Wec_t * vClasses; + Vec_Wrd_t * vSignsPo; + Vec_Int_t * vPriority, * vBin; + Gia_Obj_t * pObj; + int i; + // collect PO signatures + vSignsPo = Vec_WrdAlloc( Gia_ManPoNum(p) ); Gia_ManForEachPo( p, pObj, i ) - { - word Sign = Vec_WrdEntry( vSigns, Gia_ObjId(p, pObj) ); -// int Offset = (int)(Sign % nBins); - int Offset = (int)(((Sign & 0xFFFF) * 709 + ((Sign >> 16) & 0xFFFF) * 797 + ((Sign >> 32) & 0xFFFF) * 881 + ((Sign >> 48) & 0xFFFF) * 907) % 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_WrdPush( vSignsPo, Vec_WrdEntry(vSigns, Gia_ObjId(p, pObj)) ); + // find equivalence classes + vPriority = Hsh_WrdManHashArray( vSignsPo, 1 ); + Vec_WrdFree( vSignsPo ); + vClasses = Vec_WecCreateClasses( vPriority ); + Vec_IntFree( vPriority ); + vBins = (Vec_Ptr_t *)Vec_WecConvertToVecPtr( vClasses ); + Vec_WecFree( vClasses ); Vec_VecSort( (Vec_Vec_t *)vBins, 1 ); if ( fVerbose ) @@ -502,10 +506,6 @@ Vec_Ptr_t * Gia_ManHashOutputs( Gia_Man_t * p, Vec_Wrd_t * vSigns, int fVerbose printf( "Listing partitions with more than 100 outputs:\n" ); Vec_PtrForEachEntry( Vec_Int_t *, vBins, vBin, i ) { - // remove the first item - ABC_SWAP( int, vBin->pArray[0], vBin->pArray[Vec_IntSize(vBin)-1] ); - Vec_IntPop( vBin ); - Vec_IntSort( vBin, 0 ); assert( Vec_IntSize(vBin) > 0 ); if ( fVerbose || Vec_IntSize(vBin) > 100 ) { @@ -521,7 +521,6 @@ Vec_Ptr_t * Gia_ManHashOutputs( Gia_Man_t * p, Vec_Wrd_t * vSigns, int fVerbose printf( "\n" ); } } -// printf( "\n" ); return vBins; } diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index eb5aa001..e533e1ad 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -380,7 +380,7 @@ static int Abc_CommandAbc9CexInfo ( Abc_Frame_t * pAbc, int argc, cha static int Abc_CommandAbc9Cycle ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Cone ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9PoPart ( Abc_Frame_t * pAbc, int argc, char ** argv ); -static int Abc_CommandAbc9PoPart2 ( Abc_Frame_t * pAbc, int argc, char ** argv ); +//static int Abc_CommandAbc9PoPart2 ( Abc_Frame_t * pAbc, int argc, char ** argv ); //static int Abc_CommandAbc9CexCut ( Abc_Frame_t * pAbc, int argc, char ** argv ); //static int Abc_CommandAbc9CexMerge ( Abc_Frame_t * pAbc, int argc, char ** argv ); //static int Abc_CommandAbc9CexMin ( Abc_Frame_t * pAbc, int argc, char ** argv ); @@ -877,7 +877,7 @@ void Abc_Init( Abc_Frame_t * pAbc ) Cmd_CommandAdd( pAbc, "ABC9", "&cycle", Abc_CommandAbc9Cycle, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&cone", Abc_CommandAbc9Cone, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&popart", Abc_CommandAbc9PoPart, 0 ); - Cmd_CommandAdd( pAbc, "ABC9", "&popart2", Abc_CommandAbc9PoPart2, 0 ); +// Cmd_CommandAdd( pAbc, "ABC9", "&popart2", Abc_CommandAbc9PoPart2, 0 ); // Cmd_CommandAdd( pAbc, "ABC9", "&cexcut", Abc_CommandAbc9CexCut, 0 ); // Cmd_CommandAdd( pAbc, "ABC9", "&cexmerge", Abc_CommandAbc9CexMerge, 0 ); // Cmd_CommandAdd( pAbc, "ABC9", "&cexmin", Abc_CommandAbc9CexMin, 0 ); @@ -30164,9 +30164,10 @@ int Abc_CommandAbc9PoPart( Abc_Frame_t * pAbc, int argc, char ** argv ) usage: Abc_Print( -2, "usage: &popart [-S num] [-imvh]\n" ); Abc_Print( -2, "\t partitioning of POs into equivalence classes\n" ); - Abc_Print( -2, "\t-S num : selection point shift to randomize the solution [default = %d]\n", SelectShift ); - Abc_Print( -2, "\t-i : toggle using only CIs as support pivots [default = %s]\n", fOnlyCis? "yes": "no" ); - Abc_Print( -2, "\t-m : toggle selecting the largest cluster [default = %s]\n", fSetLargest? "yes": "no" ); + Abc_Print( -2, "\t-S num : random seed to select the set of pivot nodes [default = %d]\n", SelectShift ); + Abc_Print( -2, "\t : (if the seed is 0, the nodes with max fanout counts are used)\n" ); + Abc_Print( -2, "\t-i : toggle allowing only CIs to be the pivots [default = %s]\n", fOnlyCis? "yes": "no" ); + Abc_Print( -2, "\t-m : toggle using the largest part as the current network [default = %s]\n", fSetLargest? "yes": "no" ); Abc_Print( -2, "\t-v : toggle printing verbose information [default = %s]\n", fVerbose? "yes": "no" ); Abc_Print( -2, "\t-h : print the command usage\n"); return 1; @@ -30186,7 +30187,7 @@ usage: int Abc_CommandAbc9PoPart2( Abc_Frame_t * pAbc, int argc, char ** argv ) { extern 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 ); - Gia_Man_t * pTemp; + Gia_Man_t * pTemp = NULL; Vec_Ptr_t * vPosEquivs = NULL; int c, iStartNum = 0, nDelta = 10, nOutsMin = 100, nOutsMax = 1000, fSetLargest = 0, fVerbose = 0; Extra_UtilGetoptReset(); diff --git a/src/misc/vec/vecHsh.h b/src/misc/vec/vecHsh.h index 04f1e9f2..5d9d2e9f 100644 --- a/src/misc/vec/vecHsh.h +++ b/src/misc/vec/vecHsh.h @@ -184,6 +184,20 @@ static inline Vec_Int_t * Hsh_IntManHashArray( Vec_Int_t * vData, int nSize ) Hsh_IntManStop( p ); return vRes; } +static inline Vec_Int_t * Hsh_WrdManHashArray( Vec_Wrd_t * vDataW, int nSize ) +{ + Hsh_IntMan_t * p; + Vec_Int_t Data = { 2*Vec_WrdCap(vDataW), 2*Vec_WrdSize(vDataW), (int *)Vec_WrdArray(vDataW) }; + Vec_Int_t * vData = &Data; + Vec_Int_t * vRes = Vec_IntAlloc( 100 ); + int i, nEntries = Vec_IntSize(vData) / (2*nSize); + assert( Vec_IntSize(vData) % (2*nSize) == 0 ); + p = Hsh_IntManStart( vData, (2*nSize), nEntries ); + for ( i = 0; i < nEntries; i++ ) + Vec_IntPush( vRes, Hsh_IntManAdd(p, i) ); + Hsh_IntManStop( p ); + return vRes; +} /**Function************************************************************* -- cgit v1.2.3