From b28c4b5c17e0e3d390edab32c9346be8267e0627 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 15 Nov 2020 21:06:58 -0800 Subject: Experiments with MFFC computation. --- src/aig/gia/gia.h | 2 + src/aig/gia/giaFanout.c | 83 ++++++++++++++++++++++++++++++++++++++++++ src/aig/gia/giaMf.c | 97 ++++++++++++++++++++++++++++++++++++++++++++++++- src/aig/gia/giaUtil.c | 47 ++++++++++++++++++++++++ 4 files changed, 228 insertions(+), 1 deletion(-) diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index 4203329e..3616e10c 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -1403,6 +1403,7 @@ extern void Gia_ManFanoutStart( Gia_Man_t * p ); extern void Gia_ManFanoutStop( Gia_Man_t * p ); extern void Gia_ManStaticFanoutStart( Gia_Man_t * p ); extern void Gia_ManStaticFanoutStop( Gia_Man_t * p ); +extern void Gia_ManStaticMappingFanoutStart( Gia_Man_t * p ); /*=== giaForce.c =========================================================*/ extern void For_ManExperiment( Gia_Man_t * pGia, int nIters, int fClustered, int fVerbose ); /*=== giaFrames.c =========================================================*/ @@ -1693,6 +1694,7 @@ extern int Gia_ObjRecognizeMuxLits( Gia_Man_t * p, Gia_Obj_t * p extern int Gia_NodeMffcSize( Gia_Man_t * p, Gia_Obj_t * pNode ); extern int Gia_NodeMffcSizeMark( Gia_Man_t * p, Gia_Obj_t * pNode ); extern int Gia_NodeMffcSizeSupp( Gia_Man_t * p, Gia_Obj_t * pNode, Vec_Int_t * vSupp ); +extern int Gia_NodeMffcMapping( Gia_Man_t * p ); extern int Gia_ManHasDangling( Gia_Man_t * p ); extern int Gia_ManMarkDangling( Gia_Man_t * p ); extern Vec_Int_t * Gia_ManGetDangling( Gia_Man_t * p ); diff --git a/src/aig/gia/giaFanout.c b/src/aig/gia/giaFanout.c index 44e79ba2..8b104e9b 100644 --- a/src/aig/gia/giaFanout.c +++ b/src/aig/gia/giaFanout.c @@ -283,6 +283,89 @@ void Gia_ManStaticFanoutStart( Gia_Man_t * p ) Vec_IntFree( vCounts ); } + +/**Function************************************************************* + + Synopsis [Compute the map of all edges.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Gia_ManStartMappingFanoutMap( Gia_Man_t * p, Vec_Int_t * vFanoutNums ) +{ + Gia_Obj_t * pObj; + int i, iOffset = Gia_ManObjNum(p); + Vec_Int_t * vEdgeMap = Vec_IntAlloc( 2 * iOffset ); + Vec_IntFill( vEdgeMap, iOffset, 0 ); + Gia_ManForEachObj( p, pObj, i ) + { + if ( Vec_IntEntry(vFanoutNums, i) == 0 ) + continue; + Vec_IntWriteEntry( vEdgeMap, i, iOffset ); + iOffset += Vec_IntEntry( vFanoutNums, i ); + Vec_IntFillExtra( vEdgeMap, iOffset, 0 ); + } + //printf( "Fanout map is %.2fx larger than AIG manager.\n", 1.0*Vec_IntSize(vEdgeMap)/Gia_ManObjNum(p) ); + return vEdgeMap; +} + +/**Function************************************************************* + + Synopsis [Allocates static fanout.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManStaticMappingFanoutStart( Gia_Man_t * p ) +{ + Vec_Int_t * vCounts; + int * pRefsOld; + Gia_Obj_t * pObj, * pFanin; + int i, k, iFan, iFanout; + assert( p->vFanoutNums == NULL ); + assert( p->vFanout == NULL ); + // recompute reference counters + pRefsOld = p->pLutRefs; p->pLutRefs = NULL; + Gia_ManSetLutRefs(p); + p->vFanoutNums = Vec_IntAllocArray( p->pLutRefs, Gia_ManObjNum(p) ); + p->pLutRefs = pRefsOld; + // start the fanout maps + p->vFanout = Gia_ManStartMappingFanoutMap( p, p->vFanoutNums ); + // incrementally add fanouts + vCounts = Vec_IntStart( Gia_ManObjNum(p) ); + Gia_ManForEachLut( p, i ) + { + pObj = Gia_ManObj( p, i ); + Gia_LutForEachFanin( p, i, iFan, k ) + { + pFanin = Gia_ManObj( p, iFan ); + iFanout = Vec_IntEntry( vCounts, iFan ); + Gia_ObjSetFanout( p, pFanin, iFanout, pObj ); + Vec_IntAddToEntry( vCounts, iFan, 1 ); + } + } + Gia_ManForEachCo( p, pObj, i ) + { + iFan = Gia_ObjFaninId0p(p, pObj); + pFanin = Gia_ManObj( p, iFan ); + iFanout = Vec_IntEntry( vCounts, iFan ); + Gia_ObjSetFanout( p, pFanin, iFanout, pObj ); + Vec_IntAddToEntry( vCounts, iFan, 1 ); + } + // double-check the current number of fanouts added + Gia_ManForEachObj( p, pObj, i ) + assert( Vec_IntEntry(vCounts, i) == Gia_ObjFanoutNum(p, pObj) ); + Vec_IntFree( vCounts ); +} + /**Function************************************************************* Synopsis [Deallocates static fanout.] diff --git a/src/aig/gia/giaMf.c b/src/aig/gia/giaMf.c index 4bd08dcf..7c67fb88 100644 --- a/src/aig/gia/giaMf.c +++ b/src/aig/gia/giaMf.c @@ -1569,6 +1569,16 @@ static inline int Mf_CutAreaDerefed2( Mf_Man_t * p, int * pCut ) Mf_ObjMapRefDec( p, iObj ); return Ela1; } +static inline int Mf_CutAreaDerefed2Multi( Mf_Man_t * p, int ** ppCuts, int nCuts ) +{ + int Ela1 = 0, iObj, i; + Vec_IntClear( &p->vTemp ); + for ( i = 0; i < nCuts; i++ ) + Ela1 += Mf_CutRef2_rec( p, ppCuts[i], &p->vTemp, ABC_INFINITY ); + Vec_IntForEachEntry( &p->vTemp, iObj, i ) + Mf_ObjMapRefDec( p, iObj ); + return Ela1; +} int Mf_CutRef_rec( Mf_Man_t * p, int * pCut ) { @@ -1586,11 +1596,18 @@ int Mf_CutDeref_rec( Mf_Man_t * p, int * pCut ) Count += Mf_CutDeref_rec( p, Mf_ObjCutBest(p, pCut[i]) ); return Count; } +static inline int Mf_CutAreaRefed( Mf_Man_t * p, int * pCut ) +{ + int Ela1 = Mf_CutDeref_rec( p, pCut ); + int Ela2 = Mf_CutRef_rec( p, pCut ); + //assert( Ela1 == Ela2 ); + return Ela1; +} static inline int Mf_CutAreaDerefed( Mf_Man_t * p, int * pCut ) { int Ela1 = Mf_CutRef_rec( p, pCut ); int Ela2 = Mf_CutDeref_rec( p, pCut ); - assert( Ela1 == Ela2 ); + //assert( Ela1 == Ela2 ); return Ela1; } static inline float Mf_CutFlow( Mf_Man_t * p, int * pCut, int * pTime ) @@ -1640,6 +1657,83 @@ static inline void Mf_ObjComputeBestCut( Mf_Man_t * p, int iObj ) } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Mf_ManPrintFanoutProfile( Mf_Man_t * p, Vec_Int_t * vFanCounts ) +{ + Gia_Man_t * pGia = p->pGia0; + int i, Count, nMax = Vec_IntFindMax( vFanCounts ); + Vec_Int_t * vCounts = Vec_IntStart( nMax + 1 ); + Vec_IntForEachEntry( vFanCounts, Count, i ) + if ( Count && Gia_ObjIsAnd(Gia_ManObj(pGia, i)) ) + Vec_IntAddToEntry( vCounts, Count, 1 ); + printf( "\nFanout distribution for internal nodes:\n" ); + Vec_IntForEachEntry( vCounts, Count, i ) + if ( Count ) printf( "Fanout = %5d : Nodes = %5d.\n", i, Count ); + printf( "Total nodes with fanout = %d. Max fanout = %d.\n\n", Vec_IntCountPositive(vCounts), nMax ); + Vec_IntFree( vCounts ); +} +int Mf_ManPrintMfccStats( Mf_Man_t * p, int iObj ) +{ + Gia_Man_t * pGia = p->pGia0; + int Area = Mf_ObjMapRefNum(p, iObj) > 0 ? + Mf_CutAreaRefed (p, Mf_ObjCutBest(p, iObj)) : + Mf_CutAreaDerefed(p, Mf_ObjCutBest(p, iObj)); + printf( "%5d : Level = %5d Refs = %5d Mffc = %5d\n", + iObj, Gia_ObjLevelId(pGia, iObj), Mf_ObjMapRefNum(p, iObj), Area ); + return Area; +} +void Mf_ManOptimizationOne( Mf_Man_t * p, int iObj ) +{ + Gia_Man_t * pGia = p->pGia0; + int * ppCuts[32], nCuts = 0; + int iFanout, i, nAreaSum = 0, nAreaBest = 0; + // skip pivots whose MFFC fanouts are not used in the mapping or pointed to by COs + Gia_ObjForEachFanoutStaticId( pGia, iObj, iFanout, i ) + if ( Mf_ObjMapRefNum(p, iFanout) == 0 || Gia_ObjIsCo(Gia_ManObj(pGia, iFanout)) ) + return; + // print this pivot and its fanouts + printf( "\nPivot node = %d\n", iObj ); + printf( "Pivot " ), Mf_ManPrintMfccStats( p, iObj ); + Gia_ObjForEachFanoutStaticId( pGia, iObj, iFanout, i ) + printf( "Node " ), nAreaSum += Mf_ManPrintMfccStats( p, iFanout ); + // calculate the shared MFFC + Gia_ObjForEachFanoutStaticId( pGia, iObj, iFanout, i ) + Mf_ObjMapRefInc( p, iFanout ); + Gia_ObjForEachFanoutStaticId( pGia, iObj, iFanout, i ) + ppCuts[nCuts++] = Mf_ObjCutBest( p, iFanout ); + nAreaBest = Mf_CutAreaDerefed2Multi( p, ppCuts, nCuts ); + Gia_ObjForEachFanoutStaticId( pGia, iObj, iFanout, i ) + Mf_ObjMapRefDec( p, iFanout ); + printf( "Sum of MFFC size = %d\n", nAreaSum ); + printf( "Shared MFFC size = %d\n", nAreaBest ); +} +void Mf_ManOptimization( Mf_Man_t * p ) +{ + int nOutMax = 3; + Gia_Man_t * pGia = p->pGia0; + int i, Count, nNodes = Gia_NodeMffcMapping( pGia ); + Gia_ManLevelNum( pGia ); + Gia_ManStaticMappingFanoutStart( pGia ); + Mf_ManPrintFanoutProfile( p, pGia->vFanoutNums ); + printf( "\nIndividual logic cones:\n" ); + Vec_IntForEachEntry( pGia->vFanoutNums, Count, i ) + if ( Count >= 2 && Count <= nOutMax && Gia_ObjIsAnd(Gia_ManObj(pGia, i)) ) + Mf_ManOptimizationOne( p, i ); + printf( "\nFinished printing individual logic cones.\n" ); + Gia_ManStaticFanoutStop( pGia ); + Vec_IntFreeP( &pGia->vMapping ); +} + /**Function************************************************************* Synopsis [Technology mappping.] @@ -1682,6 +1776,7 @@ Gia_Man_t * Mf_ManPerformMapping( Gia_Man_t * pGia, Jf_Par_t * pPars ) p->fUseEla = 1; for ( ; p->Iter < p->pPars->nRounds + pPars->nRoundsEla; p->Iter++ ) Mf_ManComputeMapping( p ); + //Mf_ManOptimization( p ); if ( pPars->fVeryVerbose && pPars->fCutMin ) Vec_MemDumpTruthTables( p->vTtMem, Gia_ManName(p->pGia), pPars->nLutSize ); if ( pPars->fCutMin ) diff --git a/src/aig/gia/giaUtil.c b/src/aig/gia/giaUtil.c index 2e1830c5..b8f33b69 100644 --- a/src/aig/gia/giaUtil.c +++ b/src/aig/gia/giaUtil.c @@ -1234,6 +1234,53 @@ int Gia_NodeMffcSizeSupp( Gia_Man_t * p, Gia_Obj_t * pNode, Vec_Int_t * vSupp ) return ConeSize1; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Gia_NodeMffcMapping_rec( Gia_Man_t * p, int iObj, Vec_Int_t * vMapping, Vec_Int_t * vSupp ) +{ + Gia_Obj_t * pObj; int i, iNode, Count = 1; + if ( !iObj || Vec_IntEntry(vMapping, iObj) ) + return 0; + pObj = Gia_ManObj( p, iObj ); + if ( Gia_ObjIsCi(pObj) ) + return 0; + Gia_NodeMffcSizeSupp( p, pObj, vSupp ); + Vec_IntSort( vSupp, 0 ); + Vec_IntWriteEntry( vMapping, iObj, Vec_IntSize(vMapping) ); + Vec_IntPush( vMapping, Vec_IntSize(vSupp) ); + Vec_IntAppend( vMapping, vSupp ); + Vec_IntPush( vMapping, iObj ); + Vec_IntForEachEntry( vSupp, iNode, i ) + Count += Gia_NodeMffcMapping_rec( p, iNode, vMapping, vSupp ); + return Count; +} +int Gia_NodeMffcMapping( Gia_Man_t * p ) +{ + int i, Id, Count = 0; + int * pRefsOld; + Vec_Int_t * vMapping, * vSupp = Vec_IntAlloc( 100 ); + vMapping = Vec_IntAlloc( 2 * Gia_ManObjNum(p) ); + Vec_IntFill( vMapping, Gia_ManObjNum(p), 0 ); + pRefsOld = p->pRefs; p->pRefs = NULL; + Gia_ManCreateRefs( p ); + p->pRefs = pRefsOld; + Gia_ManForEachCoDriverId( p, Id, i ) + Count += Gia_NodeMffcMapping_rec( p, Id, vMapping, vSupp ); + Vec_IntFree( vSupp ); + p->vMapping = vMapping; + //printf( "Mapping is %.2fx larger than AIG manager.\n", 1.0*Vec_IntSize(vMapping)/Gia_ManObjNum(p) ); + return Count; +} + /**Function************************************************************* Synopsis [Returns 1 if AIG has dangling nodes.] -- cgit v1.2.3