From 59f3389c9bce4c20c6476d46513883f0cf15e454 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 28 Apr 2016 20:54:38 -0700 Subject: Experiments with arithmetic circuits. --- src/aig/gia/giaPolyn.c | 289 ++++++++++++++++++++++++++++++++++++++++++++++++ src/aig/gia/module.make | 1 + 2 files changed, 290 insertions(+) (limited to 'src/aig') 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 \ -- cgit v1.2.3