/**CFile**************************************************************** FileName [acecPool.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [CEC for arithmetic circuits.] Synopsis [Core procedures.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - June 20, 2005.] Revision [$Id: acecPool.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] ***********************************************************************/ #include "acecInt.h" #include "misc/vec/vecWec.h" #include "misc/extra/extra.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Int_t * Acec_ManCreateCarryMap( Gia_Man_t * p, Vec_Int_t * vAdds ) { // map carries into their boxes Vec_Int_t * vCarryMap = Vec_IntStartFull( Gia_ManObjNum(p) ); int i; for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ ) Vec_IntWriteEntry( vCarryMap, Vec_IntEntry(vAdds, 6*i+4), i ); return vCarryMap; } int Acec_ManCheckCarryMap( Gia_Man_t * p, int Carry, Vec_Int_t * vAdds, Vec_Int_t * vCarryMap ) { int iBox = Vec_IntEntry( vCarryMap, Carry ); assert( iBox >= 0 ); return Vec_IntEntry( vCarryMap, Vec_IntEntry(vAdds, 6*iBox+0) ) >= 0 || Vec_IntEntry( vCarryMap, Vec_IntEntry(vAdds, 6*iBox+1) ) >= 0 || Vec_IntEntry( vCarryMap, Vec_IntEntry(vAdds, 6*iBox+2) ) >= 0; } Vec_Int_t * Acec_ManCollectCarryRoots( Gia_Man_t * p, Vec_Int_t * vAdds ) { Vec_Int_t * vCarryRoots = Vec_IntAlloc( 100 ); Vec_Bit_t * vIns = Vec_BitStart( Gia_ManObjNum(p) ); int i; // marks box inputs for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ ) { Vec_BitWriteEntry( vIns, Vec_IntEntry(vAdds, 6*i+0), 1 ); Vec_BitWriteEntry( vIns, Vec_IntEntry(vAdds, 6*i+1), 1 ); Vec_BitWriteEntry( vIns, Vec_IntEntry(vAdds, 6*i+2), 1 ); } // collect roots for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ ) if ( !Vec_BitEntry(vIns, Vec_IntEntry(vAdds, 6*i+4)) ) Vec_IntPush( vCarryRoots, Vec_IntEntry(vAdds, 6*i+4) ); Vec_BitFree( vIns ); return vCarryRoots; } Vec_Int_t * Acec_ManCollectXorRoots( Gia_Man_t * p, Vec_Int_t * vXors ) { Vec_Int_t * vXorRoots = Vec_IntAlloc( 100 ); Vec_Bit_t * vIns = Vec_BitStart( Gia_ManObjNum(p) ); int i; // marks box inputs for ( i = 0; 4*i < Vec_IntSize(vXors); i++ ) { Vec_BitWriteEntry( vIns, Vec_IntEntry(vXors, 4*i+1), 1 ); Vec_BitWriteEntry( vIns, Vec_IntEntry(vXors, 4*i+2), 1 ); Vec_BitWriteEntry( vIns, Vec_IntEntry(vXors, 4*i+3), 1 ); } // collect roots for ( i = 0; 4*i < Vec_IntSize(vXors); i++ ) if ( !Vec_BitEntry(vIns, Vec_IntEntry(vXors, 4*i)) ) Vec_IntPush( vXorRoots, Vec_IntEntry(vXors, 4*i) ); Vec_BitFree( vIns ); return vXorRoots; } void Acec_ManCountXorTreeInputs_rec( Gia_Man_t * p, int Node, Vec_Int_t * vXors, Vec_Int_t * vXorMap, Vec_Bit_t * vIsCarryRoot, Vec_Int_t * vCarryRootSet, Vec_Int_t * vXorSet ) { int k, iXorBox; if ( Node == 0 || Gia_ObjIsTravIdCurrentId(p, Node) ) return; Gia_ObjSetTravIdCurrentId(p, Node); iXorBox = Vec_IntEntry( vXorMap, Node ); if ( iXorBox == -1 ) { if ( Vec_BitEntry(vIsCarryRoot, Node) ) Vec_IntPush( vCarryRootSet, Node ); return; } for ( k = 1; k < 4; k++ ) Acec_ManCountXorTreeInputs_rec( p, Vec_IntEntry(vXors, 4*iXorBox+k), vXors, vXorMap, vIsCarryRoot, vCarryRootSet, vXorSet ); Vec_IntPush( vXorSet, Vec_IntEntry(vXors, 4*iXorBox) ); } Vec_Wec_t * Acec_ManCollectCarryRootSets( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vCarryMap, Vec_Int_t * vXors, Vec_Int_t * vXorRoots, Vec_Int_t * vCarryRoots ) { Vec_Wec_t * vCarryRootSets = Vec_WecAlloc( 100 ); // XorBoxes, CarryRoots, AdderBoxes, Ins/Ranks, Outs/Ranks Vec_Int_t * vCarryRootSet = Vec_IntAlloc( 100 ); Vec_Bit_t * vIsCarryRoot = Vec_BitStart( Gia_ManObjNum(p) ); Vec_Int_t * vXorSet = Vec_IntAlloc( 100 ), * vLevel; int i, k, XorRoot, CarryRoot; // map XORs into their cuts Vec_Int_t * vXorMap = Vec_IntStartFull( Gia_ManObjNum(p) ); for ( i = 0; 4*i < Vec_IntSize(vXors); i++ ) Vec_IntWriteEntry( vXorMap, Vec_IntEntry(vXors, 4*i), i ); // create carry root marks Vec_IntForEachEntry( vCarryRoots, CarryRoot, i ) Vec_BitWriteEntry( vIsCarryRoot, CarryRoot, 1 ); // collect carry roots attached to each XOR root Vec_IntForEachEntry( vXorRoots, XorRoot, i ) { Vec_IntClear( vXorSet ); Vec_IntClear( vCarryRootSet ); Gia_ManIncrementTravId( p ); Acec_ManCountXorTreeInputs_rec( p, XorRoot, vXors, vXorMap, vIsCarryRoot, vCarryRootSet, vXorSet ); // skip trivial Vec_IntForEachEntry( vCarryRootSet, CarryRoot, k ) if ( Acec_ManCheckCarryMap(p, CarryRoot, vAdds, vCarryMap) ) break; if ( k == Vec_IntSize(vCarryRootSet) ) continue; Vec_IntSort( vCarryRootSet, 0 ); vLevel = Vec_WecPushLevel( vCarryRootSets ); Vec_IntAppend( vLevel, vXorSet ); vLevel = Vec_WecPushLevel( vCarryRootSets ); Vec_IntAppend( vLevel, vCarryRootSet ); vLevel = Vec_WecPushLevel( vCarryRootSets ); vLevel = Vec_WecPushLevel( vCarryRootSets ); vLevel = Vec_WecPushLevel( vCarryRootSets ); // unmark carry root set Vec_IntForEachEntry( vCarryRootSet, CarryRoot, k ) { assert( Vec_BitEntry(vIsCarryRoot, CarryRoot) ); Vec_BitWriteEntry( vIsCarryRoot, CarryRoot, 0 ); } } Vec_IntFree( vCarryRootSet ); Vec_IntFree( vXorSet ); Vec_IntFree( vXorMap ); // collect unmarked carry roots Vec_IntForEachEntry( vCarryRoots, CarryRoot, k ) { if ( !Vec_BitEntry(vIsCarryRoot, CarryRoot) ) continue; if ( !Acec_ManCheckCarryMap(p, CarryRoot, vAdds, vCarryMap) ) continue; vLevel = Vec_WecPushLevel( vCarryRootSets ); vLevel = Vec_WecPushLevel( vCarryRootSets ); Vec_IntFill( vLevel, 1, CarryRoot ); vLevel = Vec_WecPushLevel( vCarryRootSets ); vLevel = Vec_WecPushLevel( vCarryRootSets ); vLevel = Vec_WecPushLevel( vCarryRootSets ); } Vec_BitFree( vIsCarryRoot ); return vCarryRootSets; } int Acec_ManCompareTwo( int * pPair0, int * pPair1 ) { if ( pPair0[1] < pPair1[1] ) return -1; if ( pPair0[1] > pPair1[1] ) return 1; return 0; } void Acec_ManCollectInsOuts( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vBoxes, Vec_Int_t * vBoxRanks, Vec_Bit_t * vBoxIns, Vec_Bit_t * vBoxOuts, Vec_Int_t * vResIns, Vec_Int_t * vResOuts ) { int i, k, iBox, iObj, Rank, RankMax = 0; // mark box inputs/outputs Vec_IntForEachEntry( vBoxes, iBox, i ) { Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+0), 1 ); Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+1), 1 ); Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+2), 1 ); Vec_BitWriteEntry( vBoxOuts, Vec_IntEntry(vAdds, 6*iBox+3), 1 ); Vec_BitWriteEntry( vBoxOuts, Vec_IntEntry(vAdds, 6*iBox+4), 1 ); } // collect unmarked inputs/output and their ranks Vec_IntForEachEntry( vBoxes, iBox, i ) { for ( k = 0; k < 3; k++ ) if ( !Vec_BitEntry(vBoxOuts, Vec_IntEntry(vAdds, 6*iBox+k)) ) Vec_IntPushTwo( vResIns, Vec_IntEntry(vAdds, 6*iBox+k), Vec_IntEntry(vBoxRanks, iBox) ); for ( k = 3; k < 5; k++ ) if ( Vec_IntEntry(vAdds, 6*iBox+k) && !Vec_BitEntry(vBoxIns, Vec_IntEntry(vAdds, 6*iBox+k)) ) Vec_IntPushTwo( vResOuts, Vec_IntEntry(vAdds, 6*iBox+k), Vec_IntEntry(vBoxRanks, iBox)-(int)(k==4) ); } // unmark box inputs/outputs Vec_IntForEachEntry( vBoxes, iBox, i ) { Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+0), 0 ); Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+1), 0 ); Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+2), 0 ); Vec_BitWriteEntry( vBoxOuts, Vec_IntEntry(vAdds, 6*iBox+3), 0 ); Vec_BitWriteEntry( vBoxOuts, Vec_IntEntry(vAdds, 6*iBox+4), 0 ); } // normalize ranks Vec_IntForEachEntryDouble( vResIns, iObj, Rank, k ) RankMax = Abc_MaxInt( RankMax, Rank ); Vec_IntForEachEntryDouble( vResOuts, iObj, Rank, k ) RankMax = Abc_MaxInt( RankMax, Rank ); Vec_IntForEachEntryDouble( vResIns, iObj, Rank, k ) Vec_IntWriteEntry( vResIns, k+1, 1 + RankMax - Rank ); Vec_IntForEachEntryDouble( vResOuts, iObj, Rank, k ) Vec_IntWriteEntry( vResOuts, k+1, 1 + RankMax - Rank ); // sort by rank qsort( Vec_IntArray(vResIns), (size_t)(Vec_IntSize(vResIns)/2), 8, (int (*)(const void *, const void *))Acec_ManCompareTwo ); qsort( Vec_IntArray(vResOuts), (size_t)(Vec_IntSize(vResOuts)/2), 8, (int (*)(const void *, const void *))Acec_ManCompareTwo ); } void Acec_ManCollectBoxSets_rec( Gia_Man_t * p, int Carry, int iRank, Vec_Int_t * vAdds, Vec_Int_t * vCarryMap, Vec_Int_t * vBoxes, Vec_Int_t * vBoxRanks ) { int iBox = Vec_IntEntry( vCarryMap, Carry ); if ( iBox == -1 ) return; Acec_ManCollectBoxSets_rec( p, Vec_IntEntry(vAdds, 6*iBox+0), iRank+1, vAdds, vCarryMap, vBoxes, vBoxRanks ); Acec_ManCollectBoxSets_rec( p, Vec_IntEntry(vAdds, 6*iBox+1), iRank+1, vAdds, vCarryMap, vBoxes, vBoxRanks ); if ( Vec_IntEntry(vAdds, 6*iBox+2) ) Acec_ManCollectBoxSets_rec( p, Vec_IntEntry(vAdds, 6*iBox+2), iRank+1, vAdds, vCarryMap, vBoxes, vBoxRanks ); Vec_IntPush( vBoxes, iBox ); Vec_IntWriteEntry( vBoxRanks, iBox, iRank ); } Vec_Wec_t * Acec_ManCollectBoxSets( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vXors ) { Vec_Int_t * vCarryMap = Acec_ManCreateCarryMap( p, vAdds ); Vec_Int_t * vCarryRoots = Acec_ManCollectCarryRoots( p, vAdds ); Vec_Int_t * vXorRoots = Acec_ManCollectXorRoots( p, vXors ); Vec_Wec_t * vBoxSets = Acec_ManCollectCarryRootSets( p, vAdds, vCarryMap, vXors, vXorRoots, vCarryRoots ); Vec_Int_t * vBoxRanks = Vec_IntStart( Vec_IntSize(vAdds)/6 ); Vec_Bit_t * vBoxIns = Vec_BitStart( Gia_ManObjNum(p) ); Vec_Bit_t * vBoxOuts = Vec_BitStart( Gia_ManObjNum(p) ); int i, k, Root; Vec_IntFree( vCarryRoots ); Vec_IntFree( vXorRoots ); // collect boxes for each carry set assert( Vec_WecSize(vBoxSets) % 5 == 0 ); for ( i = 0; 5*i < Vec_WecSize(vBoxSets); i++ ) { Vec_Int_t * vRoots = Vec_WecEntry( vBoxSets, 5*i+1 ); Vec_Int_t * vBoxes = Vec_WecEntry( vBoxSets, 5*i+2 ); Vec_Int_t * vIns = Vec_WecEntry( vBoxSets, 5*i+3 ); Vec_Int_t * vOuts = Vec_WecEntry( vBoxSets, 5*i+4 ); Vec_IntForEachEntry( vRoots, Root, k ) Acec_ManCollectBoxSets_rec( p, Root, 1, vAdds, vCarryMap, vBoxes, vBoxRanks ); Acec_ManCollectInsOuts( p, vAdds, vBoxes, vBoxRanks, vBoxIns, vBoxOuts, vIns, vOuts ); } Vec_IntFree( vBoxRanks ); Vec_BitFree( vBoxIns ); Vec_BitFree( vBoxOuts ); Vec_IntFree( vCarryMap ); return vBoxSets; } void Acec_ManPrintRanks2( Vec_Int_t * vPairs ) { int k, iObj, Rank; Vec_IntForEachEntryDouble( vPairs, iObj, Rank, k ) printf( "%d ", Rank ); printf( "\n" ); } void Acec_ManPrintRanks( Vec_Int_t * vPairs ) { int k, iObj, Count, Rank, RankMax = 0; Vec_Int_t * vCounts = Vec_IntStart( 100 ); Vec_IntForEachEntryDouble( vPairs, iObj, Rank, k ) { Vec_IntFillExtra( vCounts, Rank+1, 0 ); Vec_IntAddToEntry( vCounts, Rank, 1 ); RankMax = Abc_MaxInt( RankMax, Rank ); } Vec_IntForEachEntryStartStop( vCounts, Count, Rank, 1, RankMax+1 ) printf( "%2d=%2d ", Rank, Count ); printf( "\n" ); Vec_IntFree( vCounts ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Acec_ManProfile( Gia_Man_t * p, int fVerbose ) { abctime clk = Abc_Clock(); Vec_Wec_t * vBoxes; int i; Vec_Int_t * vXors, * vAdds = Ree_ManComputeCuts( p, &vXors, fVerbose ); //Ree_ManPrintAdders( vAdds, 1 ); printf( "Detected %d full-adders and %d half-adders. Found %d XOR-cuts. ", Ree_ManCountFadds(vAdds), Vec_IntSize(vAdds)/6-Ree_ManCountFadds(vAdds), Vec_IntSize(vXors)/4 ); Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); clk = Abc_Clock(); vBoxes = Acec_ManCollectBoxSets( p, vAdds, vXors ); printf( "Detected %d adder-tree%s. ", Vec_WecSize(vBoxes)/5, Vec_WecSize(vBoxes)/5 > 1 ? "s":"" ); Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); if ( fVerbose ) for ( i = 0; 5*i < Vec_WecSize(vBoxes); i++ ) { printf( "Tree %3d : ", i ); printf( "Xor = %4d ", Vec_IntSize(Vec_WecEntry(vBoxes,5*i+0)) ); printf( "Root = %4d ", Vec_IntSize(Vec_WecEntry(vBoxes,5*i+1)) ); //printf( "(Top = %5d) ", Vec_IntEntryLast(Vec_WecEntry(vBoxes,5*i+1)) ); printf( "Adder = %4d ", Vec_IntSize(Vec_WecEntry(vBoxes,5*i+2)) ); printf( "In = %4d ", Vec_IntSize(Vec_WecEntry(vBoxes,5*i+3))/2 ); printf( "Out = %4d ", Vec_IntSize(Vec_WecEntry(vBoxes,5*i+4))/2 ); printf( "\n" ); printf( " Ins: " ); Acec_ManPrintRanks( Vec_WecEntry(vBoxes,5*i+3) ); printf( " Outs: " ); Acec_ManPrintRanks( Vec_WecEntry(vBoxes,5*i+4) ); } Vec_IntFree( vXors ); Vec_IntFree( vAdds ); Vec_WecFree( vBoxes ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Bit_t * Acec_ManPoolGetPointed( Gia_Man_t * p, Vec_Int_t * vAdds ) { Vec_Bit_t * vMarks = Vec_BitStart( Gia_ManObjNum(p) ); int i, k; for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ ) for ( k = 0; k < 3; k++ ) Vec_BitWriteEntry( vMarks, Vec_IntEntry(vAdds, 6*i+k), 1 ); return vMarks; } Vec_Int_t * Acec_ManPoolTopMost( Gia_Man_t * p, Vec_Int_t * vAdds ) { int i, k, iTop, fVerbose = 0; Vec_Int_t * vTops = Vec_IntAlloc( 1000 ); Vec_Bit_t * vMarks = Acec_ManPoolGetPointed( p, vAdds ); for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ ) if ( !Vec_BitEntry(vMarks, Vec_IntEntry(vAdds, 6*i+3)) && !Vec_BitEntry(vMarks, Vec_IntEntry(vAdds, 6*i+4)) ) Vec_IntPush( vTops, i ); if ( fVerbose ) Vec_IntForEachEntry( vTops, iTop, i ) { printf( "%4d : ", iTop ); for ( k = 0; k < 3; k++ ) printf( "%4d ", Vec_IntEntry(vAdds, 6*iTop+k) ); printf( " -> " ); for ( k = 3; k < 5; k++ ) printf( "%4d ", Vec_IntEntry(vAdds, 6*iTop+k) ); printf( "\n" ); } Vec_BitFree( vMarks ); return vTops; } void Acec_ManPool( Gia_Man_t * p ) { Vec_Int_t * vTops, * vTree; Vec_Wec_t * vTrees; abctime clk = Abc_Clock(); Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, 1 ); int i, nFadds = Ree_ManCountFadds( vAdds ); printf( "Detected %d FAs and %d HAs. ", nFadds, Vec_IntSize(vAdds)/6-nFadds ); Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); clk = Abc_Clock(); nFadds = Ree_ManCountFadds( vAdds ); printf( "Detected %d FAs and %d HAs. ", nFadds, Vec_IntSize(vAdds)/6-nFadds ); Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); //Ree_ManPrintAdders( vAdds, 1 ); // detect topmost nodes vTops = Acec_ManPoolTopMost( p, vAdds ); printf( "Detected %d topmost adder%s.\n", Vec_IntSize(vTops), Vec_IntSize(vTops) > 1 ? "s":"" ); // collect adder trees vTrees = Gia_PolynCoreOrderArray( p, vAdds, vTops ); Vec_WecForEachLevel( vTrees, vTree, i ) printf( "Adder %5d : Tree with %5d nodes.\n", Vec_IntEntry(vTops, i), Vec_IntSize(vTree) ); Vec_WecFree( vTrees ); Vec_IntFree( vAdds ); Vec_IntFree( vTops ); } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END