diff options
-rw-r--r-- | abclib.dsp | 4 | ||||
-rw-r--r-- | src/aig/gia/giaPolyn.c | 289 | ||||
-rw-r--r-- | src/aig/gia/module.make | 1 | ||||
-rw-r--r-- | src/base/abci/abc.c | 8 | ||||
-rw-r--r-- | src/misc/vec/vecInt.h | 7 |
5 files changed, 305 insertions, 4 deletions
@@ -4347,6 +4347,10 @@ SOURCE=.\src\aig\gia\giaPf.c # End Source File # Begin Source File +SOURCE=.\src\aig\gia\giaPolyn.c +# End Source File +# Begin Source File + SOURCE=.\src\aig\gia\giaQbf.c # End Source File # Begin Source File diff --git a/src/aig/gia/giaPolyn.c b/src/aig/gia/giaPolyn.c index 56c9a541..4e8d7378 100644 --- a/src/aig/gia/giaPolyn.c +++ b/src/aig/gia/giaPolyn.c @@ -21,6 +21,7 @@ #include "gia.h" #include "misc/vec/vecWec.h" #include "misc/vec/vecHsh.h" +#include "misc/vec/vecQue.h" ABC_NAMESPACE_IMPL_START @@ -218,6 +219,294 @@ void Gia_PolynTest( Gia_Man_t * pGia ) } + + + +typedef struct Pln_Man_t_ Pln_Man_t; +struct Pln_Man_t_ +{ + Gia_Man_t * pGia; // AIG manager + Hsh_VecMan_t * pHashC; // hash table for constants + Hsh_VecMan_t * pHashM; // hash table for monomials + Vec_Que_t * vQue; // queue by largest node + Vec_Flt_t * vCounts; // largest node + Vec_Int_t * vCoefs; // coefficients for each monomial + Vec_Int_t * vTempC[2]; // polynomial representation + Vec_Int_t * vTempM[4]; // polynomial representation + int nBuilds; // builds +}; + +/**Function************************************************************* + + Synopsis [Computation manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Pln_Man_t * Pln_ManAlloc( Gia_Man_t * pGia ) +{ + Pln_Man_t * p = ABC_CALLOC( Pln_Man_t, 1 ); + p->pGia = pGia; + p->pHashC = Hsh_VecManStart( 1000 ); + p->pHashM = Hsh_VecManStart( 1000 ); + p->vQue = Vec_QueAlloc( 1000 ); + p->vCounts = Vec_FltAlloc( 1000 ); + p->vCoefs = Vec_IntAlloc( 1000 ); + p->vTempC[0] = Vec_IntAlloc( 100 ); + p->vTempC[1] = Vec_IntAlloc( 100 ); + p->vTempM[0] = Vec_IntAlloc( 100 ); + p->vTempM[1] = Vec_IntAlloc( 100 ); + p->vTempM[2] = Vec_IntAlloc( 100 ); + p->vTempM[3] = Vec_IntAlloc( 100 ); + Vec_QueSetPriority( p->vQue, Vec_FltArrayP(p->vCounts) ); + // add 0-constant and 1-monomial + Hsh_VecManAdd( p->pHashC, p->vTempC[0] ); + Hsh_VecManAdd( p->pHashM, p->vTempM[0] ); + Vec_FltPush( p->vCounts, 0 ); + Vec_IntPush( p->vCoefs, 0 ); + return p; +} +void Pln_ManStop( Pln_Man_t * p ) +{ + Hsh_VecManStop( p->pHashC ); + Hsh_VecManStop( p->pHashM ); + Vec_QueFree( p->vQue ); + Vec_FltFree( p->vCounts ); + Vec_IntFree( p->vCoefs ); + Vec_IntFree( p->vTempC[0] ); + Vec_IntFree( p->vTempC[1] ); + Vec_IntFree( p->vTempM[0] ); + Vec_IntFree( p->vTempM[1] ); + Vec_IntFree( p->vTempM[2] ); + Vec_IntFree( p->vTempM[3] ); + ABC_FREE( p ); +} +void Pln_ManPrintFinal( Pln_Man_t * p ) +{ + Vec_Int_t * vArray; + int k, Entry, iMono, iConst, Count = 0; + Vec_IntForEachEntry( p->vCoefs, iConst, iMono ) + { + if ( iConst == 0 ) + continue; + + Count++; + + if ( Vec_IntSize(p->vCoefs) > 1000 ) + continue; + + vArray = Hsh_VecReadEntry( p->pHashC, iConst ); + Vec_IntForEachEntry( vArray, Entry, k ) + printf( "%s%s2^%d", k ? " + " : "", Entry < 0 ? "-" : "+", Abc_AbsInt(Entry)-1 ); + + vArray = Hsh_VecReadEntry( p->pHashM, iMono ); + Vec_IntForEachEntry( vArray, Entry, k ) + printf( " * %d", Entry ); + printf( "\n" ); + } + printf( "HashC = %d. HashM = %d. Total = %d. Used = %d.\n", Hsh_VecSize(p->pHashC), Hsh_VecSize(p->pHashM), p->nBuilds, Count ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Gia_PolynMergeConstOne( Vec_Int_t * vConst, int New ) +{ + int i, Old; + assert( New != 0 ); + Vec_IntForEachEntry( vConst, Old, i ) + { + assert( Old != 0 ); + if ( Old == New ) // A == B + { + Vec_IntDrop( vConst, i ); + Gia_PolynMergeConstOne( vConst, New > 0 ? New + 1 : New - 1 ); + return; + } + if ( Abc_AbsInt(Old) == Abc_AbsInt(New) ) // A == -B + { + Vec_IntDrop( vConst, i ); + return; + } + if ( Old + New == 1 || Old + New == -1 ) // sign(A) != sign(B) && abs(abs(A)-abs(B)) == 1 + { + int Value = Abc_MinInt( Abc_AbsInt(Old), Abc_AbsInt(New) ); + Vec_IntDrop( vConst, i ); + Gia_PolynMergeConstOne( vConst, (Old + New == 1) ? Value : -Value ); + return; + } + } + Vec_IntPushUniqueOrder( vConst, New ); +} +static inline void Gia_PolynMergeConst( Vec_Int_t * vConst, Pln_Man_t * p, int iConstAdd ) +{ + int i, New; + Vec_Int_t * vConstAdd = Hsh_VecReadEntry( p->pHashC, iConstAdd ); + Vec_IntForEachEntry( vConstAdd, New, i ) + { + Gia_PolynMergeConstOne( vConst, New ); + vConstAdd = Hsh_VecReadEntry( p->pHashC, iConstAdd ); + } +} +static inline void Gia_PolynBuildAdd( Pln_Man_t * p, Vec_Int_t * vTempC, Vec_Int_t * vTempM ) +{ + int iConst, iMono = vTempM ? Hsh_VecManAdd(p->pHashM, vTempM) : 0; + p->nBuilds++; + if ( iMono == Vec_IntSize(p->vCoefs) ) // new monomial + { + iConst = Hsh_VecManAdd( p->pHashC, vTempC ); + Vec_IntPush( p->vCoefs, iConst ); + Vec_FltPush( p->vCounts, Vec_IntEntryLast(vTempM) ); + Vec_QuePush( p->vQue, iMono ); +// Vec_QueUpdate( p->vQue, iMono ); + return; + } + // this monomial exists + iConst = Vec_IntEntry( p->vCoefs, iMono ); + if ( iConst ) + Gia_PolynMergeConst( vTempC, p, iConst ); + iConst = Hsh_VecManAdd( p->pHashC, vTempC ); + Vec_IntWriteEntry( p->vCoefs, iMono, iConst ); +} +void Gia_PolynBuildOne( Pln_Man_t * p, int iMono ) +{ + Gia_Obj_t * pObj; + Vec_Int_t * vArray, * vConst; + int iFan0, iFan1; + int k, iConst, iDriver; + + assert( Vec_IntSize(p->vCoefs) == Hsh_VecSize(p->pHashM) ); + vArray = Hsh_VecReadEntry( p->pHashM, iMono ); + iDriver = Vec_IntEntryLast( vArray ); + pObj = Gia_ManObj( p->pGia, iDriver ); + if ( !Gia_ObjIsAnd(pObj) ) + return; + + iConst = Vec_IntEntry( p->vCoefs, iMono ); + if ( iConst == 0 ) + return; + Vec_IntWriteEntry( p->vCoefs, iMono, 0 ); + + iFan0 = Gia_ObjFaninId0p(p->pGia, pObj); + iFan1 = Gia_ObjFaninId1p(p->pGia, pObj); + for ( k = 0; k < 4; k++ ) + { + Vec_IntClear( p->vTempM[k] ); + Vec_IntAppend( p->vTempM[k], vArray ); + Vec_IntPop( p->vTempM[k] ); + if ( k == 1 || k == 3 ) + Vec_IntPushUniqueOrder( p->vTempM[k], iFan0 ); // x + if ( k == 2 || k == 3 ) + Vec_IntPushUniqueOrder( p->vTempM[k], iFan1 ); // y + } + + vConst = Hsh_VecReadEntry( p->pHashC, iConst ); + for ( k = 0; k < 2; k++ ) + Vec_IntAppendMinus( p->vTempC[k], vConst, k ); + + if ( Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) ) // C * (1 - x) * (1 - y) + { + Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[0] ); // C * 1 + Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[1] ); // -C * x + vConst = Hsh_VecReadEntry( p->pHashC, iConst ); + for ( k = 0; k < 2; k++ ) + Vec_IntAppendMinus( p->vTempC[k], vConst, k ); + Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[2] ); // -C * y + Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[3] ); // C * x * y + } + else if ( Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) ) // C * (1 - x) * y + { + Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[2] ); // C * y + Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[3] ); // -C * x * y + } + else if ( !Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) ) // C * x * (1 - y) + { + Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[1] ); // C * x + Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[3] ); // -C * x * y + } + else + Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[3] ); // C * x * y +} +int Gia_PolyFindNext2( Pln_Man_t * p ) +{ + Gia_Obj_t * pObj; + Vec_Int_t * vArray; + int Max = 0, iBest = 0, iConst, iMono, iDriver; + Vec_IntForEachEntryStart( p->vCoefs, iConst, iMono, 1 ) + { + if ( iConst == 0 ) + continue; + vArray = Hsh_VecReadEntry( p->pHashM, iMono ); + iDriver = Vec_IntEntryLast( vArray ); + pObj = Gia_ManObj( p->pGia, iDriver ); + if ( !Gia_ObjIsAnd(pObj) ) + continue; + if ( Max < Vec_IntEntryLast(vArray) ) + { + Max = Vec_IntEntryLast(vArray); + iBest = iMono; + } + } + //Vec_IntPrint( Hsh_VecReadEntry(p->pHashM, iBest) ); + return iBest; +} +int Gia_PolyFindNext( Pln_Man_t * p ) +{ + int iBest = Vec_QueSize(p->vQue) ? Vec_QuePop(p->vQue) : 0; + //Vec_IntPrint( Hsh_VecReadEntry(p->pHashM, iBest) ); + return iBest; +} +void Gia_PolynBuildTest( Gia_Man_t * pGia ) +{ + abctime clk = Abc_Clock();//, clk2 = 0; + Gia_Obj_t * pObj; + int i, iMono, iDriver; + Pln_Man_t * p = Pln_ManAlloc( pGia ); + Gia_ManForEachCoReverse( pGia, pObj, i ) + { + Vec_IntFill( p->vTempC[0], 1, i+1 ); // 2^i + Vec_IntFill( p->vTempC[1], 1, -i-1 ); // -2^i + + iDriver = Gia_ObjFaninId0p( pGia, pObj ); + Vec_IntFill( p->vTempM[0], 1, iDriver ); // Driver + + if ( Gia_ObjFaninC0(pObj) ) + { + Gia_PolynBuildAdd( p, p->vTempC[0], NULL ); // C + Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[0] ); // -C * Driver + } + else + Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[0] ); // C * Driver + } + while ( 1 ) + { + //abctime temp = Abc_Clock(); + iMono = Gia_PolyFindNext(p); + if ( !iMono ) + break; + Gia_PolynBuildOne( p, iMono ); + //clk2 += Abc_Clock() - temp; + } + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + //Abc_PrintTime( 1, "Time2", clk2 ); + Pln_ManPrintFinal( p ); + Pln_ManStop( p ); +} + + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/aig/gia/module.make b/src/aig/gia/module.make index adc21d74..7da2858e 100644 --- a/src/aig/gia/module.make +++ b/src/aig/gia/module.make @@ -52,6 +52,7 @@ SRC += src/aig/gia/giaAig.c \ src/aig/gia/giaPack.c \ src/aig/gia/giaPat.c \ src/aig/gia/giaPf.c \ + src/aig/gia/giaPolyn.c \ src/aig/gia/giaQbf.c \ src/aig/gia/giaResub.c \ src/aig/gia/giaRetime.c \ diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index ab220ab3..c0052a74 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -1583,10 +1583,10 @@ int Abc_CommandPrintFanio( Abc_Frame_t * pAbc, int argc, char ** argv ) usage: Abc_Print( -2, "usage: print_fanio [-fiscmvh]\n" ); Abc_Print( -2, "\t prints the statistics about different objects in the network\n" ); - Abc_Print( -2, "\t-f : toggles considering fanins/outputs of all nodes [default = %s]\n", fUseFanio? "yes": "no" ); - Abc_Print( -2, "\t-i : toggles considering fanins/outputs of CI/CO [default = %s]\n", fUsePio? "yes": "no" ); - Abc_Print( -2, "\t-s : toggles considering input/output supports of CI/CO [default = %s]\n", fUseSupp? "yes": "no" ); - Abc_Print( -2, "\t-c : toggles considering input/output cones of CI/CO [default = %s]\n", fUseCone? "yes": "no" ); + Abc_Print( -2, "\t-f : toggles considering fanins/fanouts of all nodes [default = %s]\n", fUseFanio? "yes": "no" ); + Abc_Print( -2, "\t-i : toggles considering fanins/fanouts of CI/CO [default = %s]\n", fUsePio? "yes": "no" ); + Abc_Print( -2, "\t-s : toggles considering TFO/TFI support sizes of CI/CO [default = %s]\n", fUseSupp? "yes": "no" ); + Abc_Print( -2, "\t-c : toggles considering TFO/TFI cone sizes of CI/CO [default = %s]\n", fUseCone? "yes": "no" ); Abc_Print( -2, "\t-m : toggles printing MFFC sizes instead of fanouts [default = %s]\n", fMffc? "yes": "no" ); Abc_Print( -2, "\t-v : toggles verbose way of printing the stats [default = %s]\n", fVerbose? "yes": "no" ); Abc_Print( -2, "\t-h : print the command usage\n"); diff --git a/src/misc/vec/vecInt.h b/src/misc/vec/vecInt.h index 3d7c33fc..e0e2ba7f 100644 --- a/src/misc/vec/vecInt.h +++ b/src/misc/vec/vecInt.h @@ -1991,6 +1991,13 @@ static inline void Vec_IntAppendSkip( Vec_Int_t * vVec1, Vec_Int_t * vVec2, int if ( i != iVar ) Vec_IntPush( vVec1, Entry ); } +static inline void Vec_IntAppendMinus( Vec_Int_t * vVec1, Vec_Int_t * vVec2, int fMinus ) +{ + int Entry, i; + Vec_IntClear( vVec1 ); + Vec_IntForEachEntry( vVec2, Entry, i ) + Vec_IntPush( vVec1, fMinus ? -Entry : Entry ); +} /**Function************************************************************* |