diff options
| -rw-r--r-- | src/aig/gia/giaMuxes.c | 219 | ||||
| -rw-r--r-- | src/base/abci/abc.c | 43 |
2 files changed, 197 insertions, 65 deletions
diff --git a/src/aig/gia/giaMuxes.c b/src/aig/gia/giaMuxes.c index b215bac7..7834fdea 100644 --- a/src/aig/gia/giaMuxes.c +++ b/src/aig/gia/giaMuxes.c @@ -19,6 +19,8 @@ ***********************************************************************/ #include "gia.h" +#include "misc/util/utilNam.h" +#include "misc/vec/vecWec.h" ABC_NAMESPACE_IMPL_START @@ -299,27 +301,34 @@ void Gia_MuxStructPrint_rec( Gia_Man_t * p, int iObj, int fFirst ) Gia_Obj_t * pObj = Gia_ManObj( p, iObj ); int iCtrl; if ( !fFirst && (!Gia_ObjIsMuxId(p, iObj) || Gia_ObjRefNumId(p, iObj) > 0) ) + { +// printf( "%d", iObj ); + printf( "<%02d>", Gia_ObjLevelId(p, iObj) ); return; + } iCtrl = Gia_ObjFaninId2p(p, pObj); printf( " [(" ); if ( Gia_ObjIsMuxId(p, iCtrl) && Gia_ObjRefNumId(p, iCtrl) == 0 ) Gia_MuxStructPrint_rec( p, iCtrl, 0 ); else + { printf( "%d", iCtrl ); + printf( "<%d>", Gia_ObjLevelId(p, iCtrl) ); + } printf( ")" ); if ( Gia_ObjFaninC2(p, pObj) ) { Gia_MuxStructPrint_rec( p, Gia_ObjFaninId0p(p, pObj), 0 ); printf( "|" ); Gia_MuxStructPrint_rec( p, Gia_ObjFaninId1p(p, pObj), 0 ); - printf( "] " ); + printf( "]" ); } else { Gia_MuxStructPrint_rec( p, Gia_ObjFaninId1p(p, pObj), 0 ); printf( "|" ); Gia_MuxStructPrint_rec( p, Gia_ObjFaninId0p(p, pObj), 0 ); - printf( "] " ); + printf( "]" ); } } void Gia_MuxStructPrint( Gia_Man_t * p, int iObj ) @@ -373,13 +382,13 @@ void Gia_MuxStructDump_rec( Gia_Man_t * p, int iObj, int fFirst, Vec_Str_t * vSt Vec_StrPush( vStr, ']' ); } } -void Gia_MuxStructDump( Gia_Man_t * p, int iObj, Vec_Str_t * vStr, int Num, int nDigitsNum, int nDigitsId ) +void Gia_MuxStructDump( Gia_Man_t * p, int iObj, Vec_Str_t * vStr, int nDigitsNum, int nDigitsId ) { int Count1, Count2; assert( Gia_ObjIsMuxId(p, iObj) ); Count1 = Gia_MuxDeref( p, iObj ); Vec_StrClear( vStr ); - Vec_StrPrintNumStar( vStr, Num, nDigitsNum ); + Vec_StrPrintNumStar( vStr, Count1, nDigitsNum ); Gia_MuxStructDump_rec( p, iObj, 1, vStr, nDigitsId ); Vec_StrPush( vStr, '\0' ); Count2 = Gia_MuxRef( p, iObj ); @@ -413,92 +422,172 @@ int Gia_ManMuxCountOne( char * p ) Count += (*p == '['); return Count; } -void Gia_ManMuxProfile( Vec_Ptr_t * p, Vec_Int_t * vCounts ) + +typedef struct Mux_Man_t_ Mux_Man_t; +struct Mux_Man_t_ +{ + Gia_Man_t * pGia; // manager + Abc_Nam_t * pNames; // hashing name into ID + Vec_Wec_t * vTops; // top nodes for each struct +}; + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Mux_Man_t * Mux_ManAlloc( Gia_Man_t * pGia ) +{ + Mux_Man_t * p; + p = ABC_CALLOC( Mux_Man_t, 1 ); + p->pGia = pGia; + p->pNames = Abc_NamStart( 10000, 50 ); + p->vTops = Vec_WecAlloc( 1000 ); + Vec_WecPushLevel( p->vTops ); + return p; +} +void Mux_ManFree( Mux_Man_t * p ) { - int i; char * pTemp; - Vec_IntFill( vCounts, 1000, 0 ); - Vec_PtrForEachEntry( char *, p, pTemp, i ) - Vec_IntAddToEntry( vCounts, Abc_MinInt(Gia_ManMuxCountOne(pTemp), 999), 1 ); + Abc_NamStop( p->pNames ); + Vec_WecFree( p->vTops ); + ABC_FREE( p ); } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManMuxProfile( Mux_Man_t * p, int fWidth ) +{ + int i, Entry, Counter; + Vec_Int_t * vVec, * vCounts; + vCounts = Vec_IntStart( 1000 ); + if ( fWidth ) + { + Vec_WecForEachLevelStart( p->vTops, vVec, i, 1 ) + Vec_IntAddToEntry( vCounts, Abc_MinInt(Vec_IntSize(vVec), 999), 1 ); + printf( "The distribution of MUX tree widths:\n" ); + } + else + { + for ( i = 1; i < Vec_WecSize(p->vTops); i++ ) + Vec_IntAddToEntry( vCounts, Abc_MinInt(atoi(Abc_NamStr(p->pNames, i)), 999), 1 ); + printf( "The distribution of MUX tree sizes:\n" ); + } + Counter = 0; + Vec_IntForEachEntry( vCounts, Entry, i ) + { + if ( !Entry ) continue; + if ( ++Counter == 12 ) + printf( "\n" ), Counter = 0; + printf( " %d=%d", i, Entry ); + } + printf( "\nSummary: " ); + printf( "Max = %d ", Vec_IntFindMax(vCounts) ); + printf( "Ave = %.2f", 1.0*Vec_IntSum(vCounts)/Vec_IntCountPositive(vCounts) ); + printf( "\n" ); + Vec_IntFree( vCounts ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ void Gia_ManMuxProfiling( Gia_Man_t * p ) { + Mux_Man_t * pMan; Gia_Man_t * pNew; Gia_Obj_t * pObj; - Vec_Int_t * vFans; - Vec_Int_t * vCounts = Vec_IntAlloc( 100 ); - Vec_Ptr_t * vTrees = Vec_PtrAlloc( 1000 ); - Vec_Str_t * vStr = Vec_StrAlloc( 1000 ); - Vec_Int_t * vDegree = Vec_IntAlloc( 1000 ); - int i, nRefs, Size, Count, Total = 0, Roots = 0; - int nDigitsId, nMemory = 0; - char * pTemp; + Vec_Str_t * vStr; + Vec_Int_t * vFans, * vVec; + int i, Counter, fFound, iStructId, nDigitsId; abctime clk = Abc_Clock(); pNew = Gia_ManDupMuxes( p, 2 ); nDigitsId = Abc_Base10Log( Gia_ManObjNum(pNew) ); + pMan = Mux_ManAlloc( pNew ); + + Gia_ManLevelNum( pNew ); Gia_ManCreateRefs( pNew ); Gia_ManForEachCo( pNew, pObj, i ) Gia_ObjRefFanin0Inc( pNew, pObj ); - Vec_IntFill( vCounts, 1000, 0 ); + vStr = Vec_StrAlloc( 1000 ); vFans = Gia_ManFirstFanouts( pNew ); Gia_ManForEachMux( pNew, pObj, i ) { - Total++; - nRefs = Gia_ObjRefNumId(pNew, i); - assert( nRefs > 0 ); - if ( nRefs > 1 || !Gia_ObjIsMuxId(pNew, Vec_IntEntry(vFans, i)) ) - { - Roots++; - Size = Gia_MuxMffcSize(pNew, i); - Vec_IntAddToEntry( vCounts, Abc_MinInt(Size, 999), 1 ); - if ( Size >= 2 ) - { - Gia_MuxStructDump( pNew, i, vStr, Size, 3, nDigitsId ); - Vec_PtrPush( vTrees, Abc_UtilStrsav(Vec_StrArray(vStr)) ); - nMemory += Vec_StrSize(vStr); - } - } + // skip MUXes in the middle of the tree (which have only one MUX fanout) + if ( Gia_ObjRefNumId(pNew, i) == 1 && Gia_ObjIsMuxId(pNew, Vec_IntEntry(vFans, i)) ) + continue; + // this node is the root of the MUX structure - create hash key + Gia_MuxStructDump( pNew, i, vStr, 3, nDigitsId ); + iStructId = Abc_NamStrFindOrAdd( pMan->pNames, Vec_StrArray(vStr), &fFound ); + if ( !fFound ) + Vec_WecPushLevel( pMan->vTops ); + assert( Abc_NamObjNumMax(pMan->pNames) == Vec_WecSize(pMan->vTops) ); + Vec_IntPush( Vec_WecEntry(pMan->vTops, iStructId), i ); } - printf( "MUXes: Total = %d. Roots = %d. Trees = %d. Memory = %.2f MB\n", Total, Roots, Vec_PtrSize(vTrees), 1.0*nMemory/(1<<20) ); - Vec_IntForEachEntry( vCounts, Count, i ) - if ( Count ) - printf( "%d=%d ", i, Count ); - printf( "\n" ); - -// Vec_PtrForEachEntryStop( char *, vTrees, pTemp, i, Abc_MinInt(Vec_PtrSize(vTrees), 40) ) -// printf( "%6d : %3d %3d %s\n", i, -1, Gia_ManMuxCountOne(pTemp), pTemp ); - - // uniqify - Vec_PtrUniqify2( vTrees, (int (*)(void))Gia_ManMuxCompare, (void (*)(void))free, vDegree ); - Gia_ManMuxProfile( vTrees, vCounts ); - - nMemory = 0; - Vec_PtrForEachEntry( char *, vTrees, pTemp, i ) - nMemory += strlen(pTemp); + Vec_StrFree( vStr ); + Vec_IntFree( vFans ); - printf( "MUXes: Trees = %d. Memory = %.2f MB\n", Vec_PtrSize(vTrees), 1.0*nMemory/(1<<20) ); - Vec_IntForEachEntry( vCounts, Count, i ) - if ( Count ) - printf( "%d=%d ", i, Count ); - printf( "\n" ); + printf( "MUX structure profile for AIG \"%s\":\n", p->pName ); + printf( "Total MUXes = %d. Total trees = %d. Unique trees = %d. Memory = %.2f MB ", + Gia_ManMuxNum(pNew), Vec_WecSizeSize(pMan->vTops), Vec_WecSize(pMan->vTops), + 1.0*Abc_NamMemUsed(pMan->pNames)/(1<<20) ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); -// Vec_PtrForEachEntryStop( char *, vTrees, pTemp, i, Abc_MinInt(Vec_PtrSize(vTrees), 40) ) -// printf( "%6d : %3d %3d %s\n", i, Vec_IntEntry(vDegree, i), Gia_ManMuxCountOne(pTemp), pTemp ); + Gia_ManMuxProfile( pMan, 0 ); + Gia_ManMuxProfile( pMan, 1 ); - Vec_PtrForEachEntryStop( char *, vTrees, pTemp, i, Abc_MinInt(Vec_PtrSize(vTrees), 5000) ) - if ( Vec_IntEntry(vDegree, i) > 10 ) - printf( "%6d : %3d %3d %s\n", i, Vec_IntEntry(vDegree, i), Gia_ManMuxCountOne(pTemp), pTemp ); + // short the first ones + printf( "The first %d structures: \n", 10 ); + Vec_WecForEachLevelStartStop( pMan->vTops, vVec, i, 1, 10 ) + { + char * pTemp = Abc_NamStr(pMan->pNames, i); + printf( "%5d : ", i ); + printf( "Occur = %4d ", Vec_IntSize(vVec) ); + printf( "Size = %4d ", atoi(pTemp) ); + printf( "%s\n", pTemp ); + } - Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + // print trees for the first one + Counter = 0; + Vec_WecForEachLevelStart( pMan->vTops, vVec, i, 1 ) + { + char * pTemp = Abc_NamStr(pMan->pNames, i); + if ( Vec_IntSize(vVec) > 5 && atoi(pTemp) > 5 ) + { + int k, Entry; + printf( "For example, structure %d has %d MUXes and bit-width %d:\n", i, atoi(pTemp), Vec_IntSize(vVec) ); + Vec_IntForEachEntry( vVec, Entry, k ) + Gia_MuxStructPrint( pNew, Entry ); + if ( ++Counter == 5 ) + break; + } + } - Vec_PtrFreeFree( vTrees ); - Vec_StrFree( vStr ); - Vec_IntFree( vDegree ); - Vec_IntFree( vCounts ); - Vec_IntFree( vFans ); + Mux_ManFree( pMan ); Gia_ManStop( pNew ); } diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index a7e8c384..0fb1e406 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -326,6 +326,7 @@ static int Abc_CommandAbc9Ps ( Abc_Frame_t * pAbc, int argc, cha static int Abc_CommandAbc9PFan ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9PSig ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Status ( Abc_Frame_t * pAbc, int argc, char ** argv ); +static int Abc_CommandAbc9MuxProfile ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Show ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Strash ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Topand ( Abc_Frame_t * pAbc, int argc, char ** argv ); @@ -905,6 +906,7 @@ void Abc_Init( Abc_Frame_t * pAbc ) Cmd_CommandAdd( pAbc, "ABC9", "&pfan", Abc_CommandAbc9PFan, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&psig", Abc_CommandAbc9PSig, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&status", Abc_CommandAbc9Status, 0 ); + Cmd_CommandAdd( pAbc, "ABC9", "&mux_profile", Abc_CommandAbc9MuxProfile, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&show", Abc_CommandAbc9Show, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&st", Abc_CommandAbc9Strash, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&topand", Abc_CommandAbc9Topand, 0 ); @@ -25631,6 +25633,47 @@ usage: SeeAlso [] ***********************************************************************/ +int Abc_CommandAbc9MuxProfile( Abc_Frame_t * pAbc, int argc, char ** argv ) +{ + extern void Gia_ManMuxProfiling( Gia_Man_t * p ); + int c; + Extra_UtilGetoptReset(); + while ( ( c = Extra_UtilGetopt( argc, argv, "h" ) ) != EOF ) + { + switch ( c ) + { + case 'h': + goto usage; + default: + goto usage; + } + } + if ( pAbc->pGia == NULL ) + { + Abc_Print( -1, "Abc_CommandAbc9MuxProfile(): There is no AIG.\n" ); + return 1; + } + Gia_ManMuxProfiling( pAbc->pGia ); + return 0; + +usage: + Abc_Print( -2, "usage: &mux_profile [-h]\n" ); + Abc_Print( -2, "\t profile MUXes appearing in the design\n" ); + Abc_Print( -2, "\t-h : print the command usage\n"); + return 1; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ int Abc_CommandAbc9Show( Abc_Frame_t * pAbc, int argc, char ** argv ) { Aig_Man_t * pMan; |