| /**CFile**************************************************************** |
| |
| FileName [abcMffc.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [Network and node package.] |
| |
| Synopsis [Computing multi-output maximum fanout-free cones.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: abcMffc.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "base/abc/abc.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Dereferences and collects the nodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_MffcDeref_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes ) |
| { |
| Abc_Obj_t * pFanin; |
| int i; |
| if ( Abc_ObjIsCi(pNode) ) |
| return; |
| Abc_ObjForEachFanin( pNode, pFanin, i ) |
| { |
| assert( pFanin->vFanouts.nSize > 0 ); |
| if ( --pFanin->vFanouts.nSize == 0 ) |
| Abc_MffcDeref_rec( pFanin, vNodes ); |
| } |
| if ( vNodes ) |
| Vec_PtrPush( vNodes, pNode ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [References the nodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_MffcRef_rec( Abc_Obj_t * pNode ) |
| { |
| Abc_Obj_t * pFanin; |
| int i; |
| if ( Abc_ObjIsCi(pNode) ) |
| return; |
| Abc_ObjForEachFanin( pNode, pFanin, i ) |
| { |
| if ( pFanin->vFanouts.nSize++ == 0 ) |
| Abc_MffcRef_rec( pFanin ); |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collects nodes belonging to the MFFC.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_MffcCollectNodes( Abc_Obj_t ** pNodes, int nNodes, Vec_Ptr_t * vNodes ) |
| { |
| int i; |
| Vec_PtrClear( vNodes ); |
| for ( i = 0; i < nNodes; i++ ) |
| Abc_MffcDeref_rec( pNodes[i], vNodes ); |
| for ( i = 0; i < nNodes; i++ ) |
| Abc_MffcRef_rec( pNodes[i] ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collects leaves of the MFFC.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_MffcCollectLeaves( Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves ) |
| { |
| Abc_Obj_t * pNode, * pFanin; |
| int i, k; |
| assert( Vec_PtrSize(vNodes) > 0 ); |
| pNode = (Abc_Obj_t *)Vec_PtrEntry( vNodes, 0 ); |
| // label them |
| Abc_NtkIncrementTravId( pNode->pNtk ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i ) |
| Abc_NodeSetTravIdCurrent( pNode ); |
| // collect non-labeled fanins |
| Vec_PtrClear( vLeaves ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i ) |
| Abc_ObjForEachFanin( pNode, pFanin, k ) |
| { |
| if ( Abc_NodeIsTravIdCurrent(pFanin) ) |
| continue; |
| Abc_NodeSetTravIdCurrent( pFanin ); |
| Vec_PtrPush( vLeaves, pFanin ); |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collects internal nodes that are roots of MFFCs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Abc_NktMffcMarkRoots( Abc_Ntk_t * pNtk, int fSkipPis ) |
| { |
| Vec_Ptr_t * vRoots, * vNodes, * vLeaves; |
| Abc_Obj_t * pObj, * pLeaf; |
| int i, k; |
| Abc_NtkCleanMarkA( pNtk ); |
| // mark the drivers of combinational outputs |
| vRoots = Vec_PtrAlloc( 1000 ); |
| Abc_NtkForEachCo( pNtk, pObj, i ) |
| { |
| pObj = Abc_ObjFanin0( pObj ); |
| // if ( Abc_ObjIsCi(pObj) || Abc_ObjFaninNum(pObj) == 0 || pObj->fMarkA ) |
| if ( Abc_ObjIsCi(pObj) || pObj->fMarkA ) |
| continue; |
| pObj->fMarkA = 1; |
| Vec_PtrPush( vRoots, pObj ); |
| } |
| // explore starting from the drivers |
| vNodes = Vec_PtrAlloc( 100 ); |
| vLeaves = Vec_PtrAlloc( 100 ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| if ( Abc_ObjIsCi(pObj) ) |
| continue; |
| // collect internal nodes |
| Abc_MffcCollectNodes( &pObj, 1, vNodes ); |
| // collect leaves |
| Abc_MffcCollectLeaves( vNodes, vLeaves ); |
| // add non-PI leaves |
| Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pLeaf, k ) |
| { |
| if ( (fSkipPis && Abc_ObjIsCi(pLeaf)) || pLeaf->fMarkA ) |
| continue; |
| pLeaf->fMarkA = 1; |
| Vec_PtrPush( vRoots, pLeaf ); |
| } |
| } |
| Vec_PtrFree( vLeaves ); |
| Vec_PtrFree( vNodes ); |
| Abc_NtkCleanMarkA( pNtk ); |
| return vRoots; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collect fanout reachable root nodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffcCollectFanout_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vFanouts ) |
| { |
| Abc_Obj_t * pFanout; |
| int i; |
| if ( Abc_ObjIsCo(pObj) ) |
| return; |
| if ( Abc_ObjFanoutNum(pObj) > 64 ) |
| return; |
| if ( Abc_NodeIsTravIdCurrent(pObj) ) |
| return; |
| Abc_NodeSetTravIdCurrent(pObj); |
| if ( pObj->fMarkA ) |
| { |
| if ( pObj->vFanouts.nSize > 0 ) |
| Vec_PtrPush( vFanouts, pObj ); |
| return; |
| } |
| Abc_ObjForEachFanout( pObj, pFanout, i ) |
| Abc_NktMffcCollectFanout_rec( pFanout, vFanouts ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collect fanout reachable root nodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffcCollectFanout( Abc_Obj_t ** pNodes, int nNodes, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vFanouts ) |
| { |
| Abc_Obj_t * pFanin, * pFanout; |
| int i, k; |
| // dereference nodes |
| for ( i = 0; i < nNodes; i++ ) |
| Abc_MffcDeref_rec( pNodes[i], NULL ); |
| // collect fanouts |
| Vec_PtrClear( vFanouts ); |
| pFanin = (Abc_Obj_t *)Vec_PtrEntry( vLeaves, 0 ); |
| Abc_NtkIncrementTravId( pFanin->pNtk ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, i ) |
| Abc_ObjForEachFanout( pFanin, pFanout, k ) |
| Abc_NktMffcCollectFanout_rec( pFanout, vFanouts ); |
| // reference nodes |
| for ( i = 0; i < nNodes; i++ ) |
| Abc_MffcRef_rec( pNodes[i] ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Grow one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Abc_Obj_t * Abc_NktMffcGrowOne( Abc_Ntk_t * pNtk, Abc_Obj_t ** ppObjs, int nObjs, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vFanouts ) |
| { |
| Abc_Obj_t * pFanout, * pFanoutBest = NULL; |
| double CostBest = 0.0; |
| int i, k; |
| Abc_MffcCollectNodes( ppObjs, nObjs, vNodes ); |
| Abc_MffcCollectLeaves( vNodes, vLeaves ); |
| // collect fanouts of all fanins |
| Abc_NktMffcCollectFanout( ppObjs, nObjs, vLeaves, vFanouts ); |
| // try different fanouts |
| Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, i ) |
| { |
| for ( k = 0; k < nObjs; k++ ) |
| if ( pFanout == ppObjs[k] ) |
| break; |
| if ( k < nObjs ) |
| continue; |
| ppObjs[nObjs] = pFanout; |
| Abc_MffcCollectNodes( ppObjs, nObjs+1, vNodes ); |
| Abc_MffcCollectLeaves( vNodes, vLeaves ); |
| if ( pFanoutBest == NULL || CostBest < 1.0 * Vec_PtrSize(vNodes)/Vec_PtrSize(vLeaves) ) |
| { |
| CostBest = 1.0 * Vec_PtrSize(vNodes)/Vec_PtrSize(vLeaves); |
| pFanoutBest = pFanout; |
| } |
| } |
| return pFanoutBest; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Procedure to increase MFF size by pairing nodes.] |
| |
| Description [For each node in the array vRoots, find a matching node, |
| so that the ratio of nodes inside to the leaf nodes is maximized.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Abc_NktMffcGrowRoots( Abc_Ntk_t * pNtk, Vec_Ptr_t * vRoots ) |
| { |
| Vec_Ptr_t * vRoots1, * vNodes, * vLeaves, * vFanouts; |
| Abc_Obj_t * pObj, * pRoot2, * pNodes[2]; |
| int i; |
| Abc_NtkCleanMarkA( pNtk ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| pObj->fMarkA = 1; |
| vRoots1 = Vec_PtrAlloc( 100 ); |
| vNodes = Vec_PtrAlloc( 100 ); |
| vLeaves = Vec_PtrAlloc( 100 ); |
| vFanouts = Vec_PtrAlloc( 100 ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| pNodes[0] = pObj; |
| pRoot2 = Abc_NktMffcGrowOne( pNtk, pNodes, 1, vNodes, vLeaves, vFanouts ); |
| Vec_PtrPush( vRoots1, pRoot2 ); |
| } |
| Vec_PtrFree( vNodes ); |
| Vec_PtrFree( vLeaves ); |
| Vec_PtrFree( vFanouts ); |
| Abc_NtkCleanMarkA( pNtk ); |
| return vRoots1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Procedure to increase MFF size by pairing nodes.] |
| |
| Description [For each node in the array vRoots, find a matching node, |
| so that the ratio of nodes inside to the leaf nodes is maximized.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Abc_NktMffcGrowRootsAgain( Abc_Ntk_t * pNtk, Vec_Ptr_t * vRoots, Vec_Ptr_t * vRoots1 ) |
| { |
| Vec_Ptr_t * vRoots2, * vNodes, * vLeaves, * vFanouts; |
| Abc_Obj_t * pObj, * pRoot2, * ppObjs[3]; |
| int i; |
| Abc_NtkCleanMarkA( pNtk ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| pObj->fMarkA = 1; |
| vRoots2 = Vec_PtrAlloc( 100 ); |
| vNodes = Vec_PtrAlloc( 100 ); |
| vLeaves = Vec_PtrAlloc( 100 ); |
| vFanouts = Vec_PtrAlloc( 100 ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| ppObjs[0] = pObj; |
| ppObjs[1] = (Abc_Obj_t *)Vec_PtrEntry( vRoots1, i ); |
| if ( ppObjs[1] == NULL ) |
| { |
| Vec_PtrPush( vRoots2, NULL ); |
| continue; |
| } |
| pRoot2 = Abc_NktMffcGrowOne( pNtk, ppObjs, 2, vNodes, vLeaves, vFanouts ); |
| Vec_PtrPush( vRoots2, pRoot2 ); |
| } |
| Vec_PtrFree( vNodes ); |
| Vec_PtrFree( vLeaves ); |
| Vec_PtrFree( vFanouts ); |
| Abc_NtkCleanMarkA( pNtk ); |
| assert( Vec_PtrSize(vRoots) == Vec_PtrSize(vRoots2) ); |
| return vRoots2; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Testbench.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffcPrint( char * pFileName, Abc_Obj_t ** pNodes, int nNodes, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves ) |
| { |
| FILE * pFile; |
| Abc_Obj_t * pObj, * pFanin; |
| int i, k; |
| // convert the network |
| Abc_NtkToSop( pNodes[0]->pNtk, -1, ABC_INFINITY ); |
| // write the file |
| pFile = fopen( pFileName, "wb" ); |
| fprintf( pFile, ".model %s_part\n", pNodes[0]->pNtk->pName ); |
| fprintf( pFile, ".inputs" ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i ) |
| fprintf( pFile, " %s", Abc_ObjName(pObj) ); |
| fprintf( pFile, "\n" ); |
| fprintf( pFile, ".outputs" ); |
| for ( i = 0; i < nNodes; i++ ) |
| fprintf( pFile, " %s", Abc_ObjName(pNodes[i]) ); |
| fprintf( pFile, "\n" ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) |
| { |
| fprintf( pFile, ".names" ); |
| Abc_ObjForEachFanin( pObj, pFanin, k ) |
| fprintf( pFile, " %s", Abc_ObjName(pFanin) ); |
| fprintf( pFile, " %s", Abc_ObjName(pObj) ); |
| fprintf( pFile, "\n%s", (char *)pObj->pData ); |
| } |
| fprintf( pFile, ".end\n" ); |
| fclose( pFile ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Testbench.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffcPrintInt( char * pFileName, Abc_Ntk_t * pNtk, Vec_Int_t * vRoots, Vec_Int_t * vNodes, Vec_Int_t * vLeaves ) |
| { |
| FILE * pFile; |
| Abc_Obj_t * pObj, * pFanin; |
| int i, k; |
| // convert the network |
| Abc_NtkToSop( pNtk, -1, ABC_INFINITY ); |
| // write the file |
| pFile = fopen( pFileName, "wb" ); |
| fprintf( pFile, ".model %s_part\n", pNtk->pName ); |
| fprintf( pFile, ".inputs" ); |
| Abc_NtkForEachObjVec( vLeaves, pNtk, pObj, i ) |
| fprintf( pFile, " %s", Abc_ObjName(pObj) ); |
| fprintf( pFile, "\n" ); |
| fprintf( pFile, ".outputs" ); |
| Abc_NtkForEachObjVec( vRoots, pNtk, pObj, i ) |
| fprintf( pFile, " %s", Abc_ObjName(pObj) ); |
| fprintf( pFile, "\n" ); |
| Abc_NtkForEachObjVec( vNodes, pNtk, pObj, i ) |
| { |
| fprintf( pFile, ".names" ); |
| Abc_ObjForEachFanin( pObj, pFanin, k ) |
| fprintf( pFile, " %s", Abc_ObjName(pFanin) ); |
| fprintf( pFile, " %s", Abc_ObjName(pObj) ); |
| fprintf( pFile, "\n%s", (char *)pObj->pData ); |
| } |
| fprintf( pFile, ".end\n" ); |
| fclose( pFile ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Testbench.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffcTest( Abc_Ntk_t * pNtk ) |
| { |
| char pFileName[1000]; |
| Vec_Ptr_t * vRoots, * vRoots1, * vRoots2, * vNodes, * vLeaves; |
| Abc_Obj_t * pNodes[3], * pObj; |
| int i, nNodes = 0, nNodes2 = 0; |
| vRoots = Abc_NktMffcMarkRoots( pNtk, 1 ); |
| vRoots1 = Abc_NktMffcGrowRoots( pNtk, vRoots ); |
| vRoots2 = Abc_NktMffcGrowRootsAgain( pNtk, vRoots, vRoots1 ); |
| vNodes = Vec_PtrAlloc( 100 ); |
| vLeaves = Vec_PtrAlloc( 100 ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| printf( "%6d : ", i ); |
| |
| Abc_MffcCollectNodes( &pObj, 1, vNodes ); |
| Abc_MffcCollectLeaves( vNodes, vLeaves ); |
| nNodes += Vec_PtrSize(vNodes); |
| printf( "%6d ", Abc_ObjId(pObj) ); |
| printf( "Vol =%3d ", Vec_PtrSize(vNodes) ); |
| printf( "Cut =%3d ", Vec_PtrSize(vLeaves) ); |
| if ( Vec_PtrSize(vLeaves) < 2 ) |
| { |
| printf( "\n" ); |
| continue; |
| } |
| |
| pNodes[0] = pObj; |
| pNodes[1] = (Abc_Obj_t *)Vec_PtrEntry( vRoots1, i ); |
| pNodes[2] = (Abc_Obj_t *)Vec_PtrEntry( vRoots2, i ); |
| if ( pNodes[1] == NULL || pNodes[2] == NULL ) |
| { |
| printf( "\n" ); |
| continue; |
| } |
| Abc_MffcCollectNodes( pNodes, 3, vNodes ); |
| Abc_MffcCollectLeaves( vNodes, vLeaves ); |
| nNodes2 += Vec_PtrSize(vNodes); |
| printf( "%6d ", Abc_ObjId(pNodes[1]) ); |
| printf( "%6d ", Abc_ObjId(pNodes[2]) ); |
| printf( "Vol =%3d ", Vec_PtrSize(vNodes) ); |
| printf( "Cut =%3d ", Vec_PtrSize(vLeaves) ); |
| |
| printf( "%4.2f ", 1.0 * Vec_PtrSize(vNodes)/Vec_PtrSize(vLeaves) ); |
| printf( "\n" ); |
| |
| // generate file |
| if ( Vec_PtrSize(vNodes) < 10 ) |
| continue; |
| sprintf( pFileName, "%s_mffc%04d_%02d.blif", Abc_NtkName(pNtk), Abc_ObjId(pObj), Vec_PtrSize(vNodes) ); |
| Abc_NktMffcPrint( pFileName, pNodes, 3, vNodes, vLeaves ); |
| } |
| printf( "Total nodes = %d. Root nodes = %d. Mffc nodes = %d. Mffc nodes2 = %d.\n", |
| Abc_NtkNodeNum(pNtk), Vec_PtrSize(vRoots), nNodes, nNodes2 ); |
| Vec_PtrFree( vNodes ); |
| Vec_PtrFree( vLeaves ); |
| Vec_PtrFree( vRoots ); |
| Vec_PtrFree( vRoots1 ); |
| Vec_PtrFree( vRoots2 ); |
| } |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Create the network of supernodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffcTestSuper( Abc_Ntk_t * pNtk ) |
| { |
| Vec_Ptr_t * vRoots, * vFanins, * vFanouts, * vNodes, * vLeaves; |
| Abc_Obj_t * pObj, * pFanin; |
| Vec_Int_t * vCounts, * vNumbers, * vSizes, * vMarks; |
| Vec_Int_t * vNode1, * vNode2; |
| int i, k, Entry, nSizes; |
| abctime clk = Abc_Clock(); |
| vRoots = Abc_NktMffcMarkRoots( pNtk, 1 ); |
| vFanins = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) ); |
| vFanouts = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) ); |
| vCounts = Vec_IntStart( Abc_NtkObjNumMax(pNtk) ); |
| vNode1 = Vec_IntStart( Abc_NtkObjNumMax(pNtk) ); |
| vNode2 = Vec_IntStart( Abc_NtkObjNumMax(pNtk) ); |
| vSizes = Vec_IntStart( Abc_NtkObjNumMax(pNtk) ); |
| vMarks = Vec_IntStart( Abc_NtkObjNumMax(pNtk) ); |
| |
| // create fanins/fanouts |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| Vec_PtrWriteEntry( vFanins, Abc_ObjId(pObj), Vec_IntAlloc(8) ); |
| Vec_PtrWriteEntry( vFanouts, Abc_ObjId(pObj), Vec_IntAlloc(8) ); |
| } |
| // add fanins/fanouts |
| vNodes = Vec_PtrAlloc( 100 ); |
| vLeaves = Vec_PtrAlloc( 100 ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| Abc_MffcCollectNodes( &pObj, 1, vNodes ); |
| Abc_MffcCollectLeaves( vNodes, vLeaves ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, k ) |
| { |
| if ( !Abc_ObjIsNode(pFanin) ) |
| continue; |
| Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanins, Abc_ObjId(pObj)), Abc_ObjId(pFanin) ); |
| Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pFanin)), Abc_ObjId(pObj) ); |
| // count how many times each object is a fanin |
| Vec_IntAddToEntry( vCounts, Abc_ObjId(pFanin), 1 ); |
| } |
| Vec_IntWriteEntry( vSizes, Abc_ObjId(pObj), Vec_PtrSize(vNodes) ); |
| } |
| |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| Abc_MffcCollectNodes( &pObj, 1, vNodes ); |
| Abc_MffcCollectLeaves( vNodes, vLeaves ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, k ) |
| { |
| if ( !Abc_ObjIsNode(pFanin) ) |
| continue; |
| if ( Vec_IntEntry(vCounts, Abc_ObjId(pFanin)) != 2 ) |
| continue; |
| if ( Vec_IntEntry(vNode1, Abc_ObjId(pFanin)) == 0 ) |
| Vec_IntWriteEntry( vNode1, Abc_ObjId(pFanin), Abc_ObjId(pObj) ); |
| else //if ( Vec_IntEntry(vNode2, Abc_ObjId(pFanin)) == 0 ) |
| Vec_IntWriteEntry( vNode2, Abc_ObjId(pFanin), Abc_ObjId(pObj) ); |
| |
| Vec_IntWriteEntry( vMarks, Abc_ObjId(pFanin), 1 ); |
| Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj), 1 ); |
| } |
| } |
| |
| // count sizes |
| nSizes = 0; |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| if ( Vec_IntEntry( vMarks, Abc_ObjId(pObj) ) ) |
| nSizes += Vec_IntEntry( vSizes, Abc_ObjId(pObj) ); |
| } |
| printf( "Included = %6d. Total = %6d. (%6.2f %%)\n", |
| nSizes, Abc_NtkNodeNum(pNtk), 100.0 * nSizes / Abc_NtkNodeNum(pNtk) ); |
| |
| |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| if ( Vec_IntEntry(vCounts, Abc_ObjId(pObj)) != 2 ) |
| continue; |
| printf( "%d ", Vec_IntEntry( vSizes, Abc_ObjId(pObj) ) + |
| Vec_IntEntry( vSizes, Vec_IntEntry(vNode1, Abc_ObjId(pObj)) ) + |
| Vec_IntEntry( vSizes, Vec_IntEntry(vNode2, Abc_ObjId(pObj)) ) ); |
| } |
| printf( "\n" ); |
| |
| // print how many times they appear |
| vNumbers = Vec_IntStart( 32 ); |
| Vec_IntForEachEntry( vCounts, Entry, i ) |
| { |
| /* |
| if ( Entry == 2 ) |
| { |
| pObj = Abc_NtkObj( pNtk, i ); |
| Abc_MffcCollectNodes( &pObj, 1, vNodes ); |
| Abc_MffcCollectLeaves( vNodes, vLeaves ); |
| printf( "%d(%d) ", Vec_PtrSize(vNodes), Vec_PtrSize(vLeaves) ); |
| } |
| */ |
| if ( Entry == 0 ) |
| continue; |
| if ( Entry <= 10 ) |
| Vec_IntAddToEntry( vNumbers, Entry, 1 ); |
| else if ( Entry <= 100 ) |
| Vec_IntAddToEntry( vNumbers, 10 + Entry/10, 1 ); |
| else if ( Entry < 1000 ) |
| Vec_IntAddToEntry( vNumbers, 20 + Entry/100, 1 ); |
| else |
| Vec_IntAddToEntry( vNumbers, 30, 1 ); |
| } |
| for ( i = 1; i <= 10; i++ ) |
| if ( Vec_IntEntry(vNumbers,i) ) |
| printf( " n = %4d %6d\n", i, Vec_IntEntry(vNumbers,i) ); |
| for ( i = 11; i <= 20; i++ ) |
| if ( Vec_IntEntry(vNumbers,i) ) |
| printf( "%4d < n <= %4d %6d\n", 10*(i-10), 10*(i-9), Vec_IntEntry(vNumbers,i) ); |
| for ( i = 21; i < 30; i++ ) |
| if ( Vec_IntEntry(vNumbers,i) ) |
| printf( "%4d < n <= %4d %6d\n", 100*(i-20), 100*(i-19), Vec_IntEntry(vNumbers,i) ); |
| if ( Vec_IntEntry(vNumbers,31) ) |
| printf( " n > 1000 %6d\n", Vec_IntEntry(vNumbers,30) ); |
| printf( "Total MFFCs = %d. ", Vec_PtrSize(vRoots) ); |
| Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); |
| Vec_IntFree( vNumbers ); |
| Vec_PtrFree( vNodes ); |
| Vec_PtrFree( vLeaves ); |
| |
| // delete fanins/fanouts |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanins, Abc_ObjId(pObj)) ); |
| Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pObj)) ); |
| } |
| |
| Vec_IntFree( vCounts ); |
| Vec_PtrFree( vFanouts ); |
| Vec_PtrFree( vFanins ); |
| Vec_PtrFree( vRoots ); |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collects the leaves and the roots of the window.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffCollectLeafRoot( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots ) |
| { |
| Abc_Obj_t * pObj, * pNext; |
| int i, k; |
| // mark |
| Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) |
| pObj->fMarkA = 1; |
| // collect leaves |
| Vec_PtrClear( vLeaves ); |
| Abc_NtkIncrementTravId( pNtk ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) |
| Abc_ObjForEachFanin( pObj, pNext, k ) |
| { |
| if ( pNext->fMarkA || Abc_NodeIsTravIdCurrent(pNext) ) |
| continue; |
| Abc_NodeSetTravIdCurrent(pNext); |
| Vec_PtrPush( vLeaves, pNext ); |
| } |
| // collect roots |
| Vec_PtrClear( vRoots ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) |
| { |
| Abc_ObjForEachFanout( pObj, pNext, k ) |
| if ( !pNext->fMarkA ) |
| { |
| Vec_PtrPush( vRoots, pObj ); |
| break; |
| } |
| } |
| // unmark |
| Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i ) |
| pObj->fMarkA = 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collects the leaves and the roots of the window.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffCollectLeafRootInt( Abc_Ntk_t * pNtk, Vec_Int_t * vNodes, Vec_Int_t * vLeaves, Vec_Int_t * vRoots ) |
| { |
| Abc_Obj_t * pObj, * pNext; |
| int i, k; |
| // mark |
| Abc_NtkForEachObjVec( vNodes, pNtk, pObj, i ) |
| pObj->fMarkA = 1; |
| // collect leaves |
| Vec_IntClear( vLeaves ); |
| Abc_NtkIncrementTravId( pNtk ); |
| Abc_NtkForEachObjVec( vNodes, pNtk, pObj, i ) |
| Abc_ObjForEachFanin( pObj, pNext, k ) |
| { |
| if ( pNext->fMarkA || Abc_NodeIsTravIdCurrent(pNext) ) |
| continue; |
| Abc_NodeSetTravIdCurrent(pNext); |
| Vec_IntPush( vLeaves, Abc_ObjId(pNext) ); |
| } |
| // collect roots |
| if ( vRoots ) |
| { |
| Vec_IntClear( vRoots ); |
| Abc_NtkForEachObjVec( vNodes, pNtk, pObj, i ) |
| { |
| Abc_ObjForEachFanout( pObj, pNext, k ) |
| if ( !pNext->fMarkA ) |
| { |
| Vec_IntPush( vRoots, Abc_ObjId(pObj) ); |
| break; |
| } |
| } |
| } |
| // unmark |
| Abc_NtkForEachObjVec( vNodes, pNtk, pObj, i ) |
| pObj->fMarkA = 0; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Create the network of supernodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffcTestIdeaOne( Abc_Ntk_t * pNtk, Abc_Obj_t * pObj ) |
| { |
| Vec_Ptr_t * vNodes, * vLeaves, * vRoots, * vVolume; |
| Vec_Ptr_t * vLeaves2, * vRoots2, * vVolume2; |
| Abc_Obj_t * pNode, * pNodeBest = pObj; |
| double Cost, CostBest = 0.0; |
| int i, k; |
| vNodes = Vec_PtrAlloc( 100 ); |
| vLeaves = Vec_PtrAlloc( 100 ); |
| vRoots = Vec_PtrAlloc( 100 ); |
| vVolume = Vec_PtrAlloc( 100 ); |
| vLeaves2 = Vec_PtrAlloc( 100 ); |
| vRoots2 = Vec_PtrAlloc( 100 ); |
| vVolume2 = Vec_PtrAlloc( 100 ); |
| printf( "\n" ); |
| for ( i = 1; i <= 16; i++ ) |
| { |
| Vec_PtrPush( vNodes, pNodeBest ); |
| Abc_NktMffCollectLeafRoot( pNtk, vNodes, vLeaves, vRoots ); |
| Abc_MffcCollectNodes( (Abc_Obj_t **)Vec_PtrArray(vRoots), Vec_PtrSize(vRoots), vVolume ); |
| |
| printf( "%2d : Node =%6d (%2d%3d) Cost =%6.2f ", i, Abc_ObjId(pNodeBest), |
| Abc_ObjFaninNum(pNodeBest), Abc_ObjFanoutNum(pNodeBest), CostBest ); |
| printf( "Leaf =%2d Root =%2d Vol =%2d\n", Vec_PtrSize(vLeaves), Vec_PtrSize(vRoots), Vec_PtrSize(vVolume) ); |
| |
| // try including different nodes |
| pNodeBest = NULL; |
| Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, k ) |
| { |
| if ( !Abc_ObjIsNode(pNode) ) |
| continue; |
| Vec_PtrPush( vNodes, pNode ); |
| Abc_NktMffCollectLeafRoot( pNtk, vNodes, vLeaves2, vRoots2 ); |
| Abc_MffcCollectNodes( (Abc_Obj_t **)Vec_PtrArray(vRoots2), Vec_PtrSize(vRoots2), vVolume2 ); |
| Cost = 1.0 * Vec_PtrSize(vVolume2) / (Vec_PtrSize(vLeaves2) + 3 * Vec_PtrSize(vRoots2)); |
| if ( pNodeBest == NULL || CostBest < Cost ) |
| { |
| pNodeBest = pNode; |
| CostBest = Cost; |
| } |
| Vec_PtrPop( vNodes ); |
| } |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pNode, k ) |
| { |
| if ( Vec_PtrFind(vNodes, pNode) >= 0 ) |
| continue; |
| if ( !Abc_ObjIsNode(pNode) ) |
| continue; |
| Vec_PtrPush( vNodes, pNode ); |
| Abc_NktMffCollectLeafRoot( pNtk, vNodes, vLeaves2, vRoots2 ); |
| Abc_MffcCollectNodes( (Abc_Obj_t **)Vec_PtrArray(vRoots2), Vec_PtrSize(vRoots2), vVolume2 ); |
| Cost = 1.0 * Vec_PtrSize(vVolume2) / (Vec_PtrSize(vLeaves2) + 3 * Vec_PtrSize(vRoots2)); |
| if ( pNodeBest == NULL || CostBest < Cost ) |
| { |
| pNodeBest = pNode; |
| CostBest = Cost; |
| } |
| Vec_PtrPop( vNodes ); |
| } |
| if ( pNodeBest == NULL ) |
| break; |
| } |
| |
| Vec_PtrFree( vNodes ); |
| Vec_PtrFree( vLeaves ); |
| Vec_PtrFree( vRoots ); |
| Vec_PtrFree( vVolume ); |
| Vec_PtrFree( vLeaves2 ); |
| Vec_PtrFree( vRoots2 ); |
| Vec_PtrFree( vVolume2 ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Create the network of supernodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffcTestIdea( Abc_Ntk_t * pNtk ) |
| { |
| Abc_Obj_t * pObj; |
| int i; |
| Abc_NtkForEachNode( pNtk, pObj, i ) |
| if ( Abc_ObjIsNode(pObj) && Abc_ObjId(pObj) % 100 == 0 ) |
| Abc_NktMffcTestIdeaOne( pNtk, pObj ); |
| } |
| |
| |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Creates MFFCs and their fanins/fanouts/volumes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Abc_NktMffcDerive( Abc_Ntk_t * pNtk, Vec_Ptr_t ** pvFanins, Vec_Ptr_t ** pvFanouts, Vec_Ptr_t ** pvVolumes ) |
| { |
| Vec_Ptr_t * vRoots, * vFanins, * vFanouts, * vVolumes, * vNodes, * vLeaves; |
| Abc_Obj_t * pObj, * pFanin; |
| int i, k; |
| abctime clk = Abc_Clock(); |
| // create roots |
| vRoots = Abc_NktMffcMarkRoots( pNtk, 0 ); |
| // create fanins/fanouts/volumes |
| vFanins = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) ); |
| vFanouts = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) ); |
| vVolumes = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| Vec_PtrWriteEntry( vFanins, Abc_ObjId(pObj), Vec_IntAlloc(8) ); |
| Vec_PtrWriteEntry( vFanouts, Abc_ObjId(pObj), Vec_IntAlloc(8) ); |
| Vec_PtrWriteEntry( vVolumes, Abc_ObjId(pObj), Vec_IntAlloc(8) ); |
| } |
| // add fanins/fanouts |
| vNodes = Vec_PtrAlloc( 100 ); |
| vLeaves = Vec_PtrAlloc( 100 ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| if ( Abc_ObjIsCi(pObj) ) |
| continue; |
| Abc_MffcCollectNodes( &pObj, 1, vNodes ); |
| Abc_MffcCollectLeaves( vNodes, vLeaves ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, k ) |
| { |
| Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanins, Abc_ObjId(pObj)), Abc_ObjId(pFanin) ); |
| Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pFanin)), Abc_ObjId(pObj) ); |
| } |
| Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pFanin, k ) |
| Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj)), Abc_ObjId(pFanin) ); |
| } |
| |
| Vec_PtrFree( vNodes ); |
| Vec_PtrFree( vLeaves ); |
| // sort |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| Vec_IntSort( (Vec_Int_t *)Vec_PtrEntry(vFanins, Abc_ObjId(pObj)), 0 ); |
| Vec_IntSort( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pObj)), 0 ); |
| } |
| // return |
| *pvFanins = vFanins; |
| *pvFanouts = vFanouts; |
| *pvVolumes = vVolumes; |
| return vRoots; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Frees MFFCs and their fanins/fanouts.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffcFree( Vec_Ptr_t * vRoots, Vec_Ptr_t * vFanins, Vec_Ptr_t * vFanouts, Vec_Ptr_t * vVolumes ) |
| { |
| Abc_Obj_t * pObj; |
| int i; |
| Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i ) |
| { |
| Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanins, Abc_ObjId(pObj)) ); |
| Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pObj)) ); |
| Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj)) ); |
| } |
| Vec_PtrFree( vVolumes ); |
| Vec_PtrFree( vFanouts ); |
| Vec_PtrFree( vFanins ); |
| Vec_PtrFree( vRoots ); |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns the cost of two supports.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| double Abc_NktMffcCostTwo( Vec_Int_t * vSupp1, Vec_Int_t * vSupp2, int Volume, int Limit ) |
| { |
| int nCommon = Vec_IntTwoCountCommon( vSupp1, vSupp2 ); |
| //printf( "s1=%2d s2=%2d c=%2d v=%2d ", Vec_IntSize(vSupp1), Vec_IntSize(vSupp2), nCommon, Volume ); |
| if ( Vec_IntSize(vSupp1) + Vec_IntSize(vSupp2) - nCommon > Limit ) |
| return (double)-ABC_INFINITY; |
| return 0.6 * nCommon - 1.2 * Vec_IntSize(vSupp2) + 0.8 * Volume; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns support of the group.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Abc_NktMffcSupport( Vec_Ptr_t * vThis, Vec_Ptr_t * vFanins ) |
| { |
| Vec_Int_t * vIns, * vIns2, * vTemp; |
| Abc_Obj_t * pObj; |
| int i; |
| vIns = Vec_IntAlloc( 100 ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vThis, pObj, i ) |
| { |
| vIns2 = (Vec_Int_t *)Vec_PtrEntry( vFanins, Abc_ObjId(pObj) ); |
| vIns = Vec_IntTwoMerge( vTemp = vIns, vIns2 ); |
| Vec_IntFree( vTemp ); |
| } |
| return vIns; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns the best merger for the cluster of given node (pPivot).] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Abc_Obj_t * Abc_NktMffcFindBest( Abc_Ntk_t * pNtk, Vec_Int_t * vMarks, Vec_Int_t * vIns, Vec_Ptr_t * vFanins, Vec_Ptr_t * vFanouts, Vec_Ptr_t * vVolumes, int Limit ) |
| { |
| Vec_Int_t * vIns2, * vOuts, * vOuts2, * vTemp; |
| Abc_Obj_t * pPivot2, * pObj, * pObjBest = NULL; |
| double Cost, CostBest = (double)-ABC_INFINITY; |
| int i, Volume; |
| // collect the fanouts of the fanins |
| vOuts = Vec_IntAlloc( 100 ); |
| Abc_NtkForEachObjVec( vIns, pNtk, pObj, i ) |
| { |
| vOuts2 = (Vec_Int_t *)Vec_PtrEntry( vFanouts, Abc_ObjId(pObj) ); |
| if ( Vec_IntSize(vOuts2) > 16 ) |
| continue; |
| vOuts = Vec_IntTwoMerge( vTemp = vOuts, vOuts2 ); |
| Vec_IntFree( vTemp ); |
| } |
| // check the pairs |
| Abc_NtkForEachObjVec( vOuts, pNtk, pPivot2, i ) |
| { |
| if ( Vec_IntEntry(vMarks, Abc_ObjId(pPivot2)) == 0 ) |
| continue; |
| vIns2 = (Vec_Int_t *)Vec_PtrEntry( vFanins, Abc_ObjId(pPivot2) ); |
| Volume = Vec_IntSize((Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pPivot2))); |
| Cost = Abc_NktMffcCostTwo( vIns, vIns2, Volume, Limit ); |
| //printf( "%5d %2d\n", Abc_ObjId(pPivot2), Cost ); |
| if ( Cost == (double)-ABC_INFINITY ) |
| continue; |
| if ( pObjBest == NULL || CostBest < Cost ) |
| { |
| pObjBest = pPivot2; |
| CostBest = Cost; |
| } |
| } |
| //printf( "Choosing %d\n", pObjBest->Id ); |
| Vec_IntFree( vOuts ); |
| return pObjBest; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Processes one cluster.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Abc_NktMffcSaveOne( Vec_Ptr_t * vThis, Vec_Ptr_t * vVolumes ) |
| { |
| Vec_Int_t * vVolume, * vResult; |
| Abc_Obj_t * pObj; |
| int i, k, Entry; |
| vResult = Vec_IntAlloc( 100 ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vThis, pObj, i ) |
| { |
| vVolume = (Vec_Int_t *)Vec_PtrEntry( vVolumes, Abc_ObjId(pObj) ); |
| Vec_IntForEachEntry( vVolume, Entry, k ) |
| Vec_IntPush( vResult, Entry ); |
| } |
| return vResult; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Procedure used for sorting the nodes in decreasing order of levels.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Abc_NodeCompareVolumeDecrease( Abc_Obj_t ** pp1, Abc_Obj_t ** pp2 ) |
| { |
| int Diff = Abc_ObjRegular(*pp1)->iTemp - Abc_ObjRegular(*pp2)->iTemp; |
| if ( Diff > 0 ) |
| return -1; |
| if ( Diff < 0 ) |
| return 1; |
| Diff = Abc_ObjRegular(*pp1)->Id - Abc_ObjRegular(*pp2)->Id; |
| if ( Diff > 0 ) |
| return -1; |
| if ( Diff < 0 ) |
| return 1; |
| return 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Create the network of supernodes.] |
| |
| Description [Returns array of interger arrays of IDs of nodes |
| included in a disjoint structural decomposition of the network.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Abc_NktMffcServer( Abc_Ntk_t * pNtk, int nInMax, int nOutMax ) |
| { |
| Vec_Ptr_t * vResult, * vThis; |
| Vec_Ptr_t * vPivots, * vFanins, * vFanouts, * vVolumes; |
| Vec_Int_t * vLeaves, * vMarks; |
| Abc_Obj_t * pObj, * pObj2; |
| int i, k; |
| assert( nOutMax >= 1 && nOutMax <= 32 ); |
| vResult = Vec_PtrAlloc( 100 ); |
| // create fanins/fanouts |
| vPivots = Abc_NktMffcDerive( pNtk, &vFanins, &vFanouts, &vVolumes ); |
| // sort by their MFFC size |
| Vec_PtrForEachEntry( Abc_Obj_t *, vPivots, pObj, i ) |
| pObj->iTemp = Vec_IntSize((Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj))); |
| Vec_PtrSort( vPivots, (int (*)(void))Abc_NodeCompareVolumeDecrease ); |
| // create marks |
| vMarks = Vec_IntStart( Abc_NtkObjNumMax(pNtk) ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, vPivots, pObj, i ) |
| if ( Abc_ObjIsNode(pObj) && Vec_IntSize((Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj))) > 1 ) |
| Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj), 1 ); |
| // consider nodes in the order of the marks |
| vThis = Vec_PtrAlloc( 10 ); |
| // while ( 1 ) |
| Vec_PtrForEachEntry( Abc_Obj_t *, vPivots, pObj, i ) |
| { |
| // pObj = Abc_NtkObj( pNtk, 589 ); |
| if ( Vec_IntEntry(vMarks, Abc_ObjId(pObj)) == 0 ) |
| continue; |
| // start the set |
| Vec_PtrClear( vThis ); |
| Vec_PtrPush( vThis, pObj ); |
| Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj), 0 ); |
| // quit if exceeded the limit |
| vLeaves = (Vec_Int_t *)Vec_PtrEntry( vFanins, Abc_ObjId(pObj) ); |
| if ( Vec_IntSize(vLeaves) > nInMax ) |
| { |
| Vec_PtrPush( vResult, Abc_NktMffcSaveOne(vThis, vVolumes) ); |
| continue; |
| } |
| // try adding one node at a time |
| for ( k = 1; k < nOutMax; k++ ) |
| { |
| // quit if exceeded the limit |
| vLeaves = Abc_NktMffcSupport( vThis, vFanins ); |
| assert( Vec_IntSize(vLeaves) <= nInMax ); |
| pObj2 = Abc_NktMffcFindBest( pNtk, vMarks, vLeaves, vFanins, vFanouts, vVolumes, nInMax ); |
| Vec_IntFree( vLeaves ); |
| // quit if there is no extension |
| if ( pObj2 == NULL ) |
| break; |
| Vec_PtrPush( vThis, pObj2 ); |
| Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj2), 0 ); |
| } |
| Vec_PtrPush( vResult, Abc_NktMffcSaveOne(vThis, vVolumes) ); |
| // break; |
| } |
| Vec_PtrFree( vThis ); |
| Vec_IntFree( vMarks ); |
| // delele fanins/outputs |
| Abc_NktMffcFree( vPivots, vFanins, vFanouts, vVolumes ); |
| return vResult; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Testbench.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Abc_NktMffcServerTest( Abc_Ntk_t * pNtk ) |
| { |
| char pFileName[1000]; |
| Vec_Ptr_t * vGlobs; |
| Vec_Int_t * vGlob, * vLeaves, * vRoots; |
| double Cost, CostAll = 0.0; |
| int i, k, Entry, nNodes = 0; |
| abctime clk = Abc_Clock(); |
| vGlobs = Abc_NktMffcServer( pNtk, 18, 3 ); |
| vLeaves = Vec_IntAlloc( 100 ); |
| vRoots = Vec_IntAlloc( 100 ); |
| Vec_PtrForEachEntry( Vec_Int_t *, vGlobs, vGlob, i ) |
| { |
| nNodes += Vec_IntSize(vGlob); |
| Abc_NktMffCollectLeafRootInt( pNtk, vGlob, vLeaves, vRoots ); |
| if ( Vec_IntSize(vGlob) <= Vec_IntSize(vRoots) ) |
| continue; |
| Cost = 1.0 * Vec_IntSize(vGlob)/(Vec_IntSize(vLeaves) + Vec_IntSize(vRoots)); |
| CostAll += Cost; |
| if ( Cost < 0.5 ) |
| continue; |
| |
| printf( "%6d : Root =%3d. Leaf =%3d. Node =%4d. ", |
| i, Vec_IntSize(vRoots), Vec_IntSize(vLeaves), Vec_IntSize(vGlob) ); |
| printf( "Cost =%6.2f ", Cost ); |
| Vec_IntForEachEntry( vRoots, Entry, k ) |
| printf( "%d ", Entry ); |
| printf( "\n" ); |
| |
| sprintf( pFileName, "%sc%04di%02dn%02d.blif", Abc_NtkName(pNtk), i, Vec_IntSize(vLeaves), Vec_IntSize(vGlob) ); |
| Abc_NktMffcPrintInt( pFileName, pNtk, vRoots, vGlob, vLeaves ); |
| } |
| Vec_IntFree( vLeaves ); |
| Vec_IntFree( vRoots ); |
| Vec_PtrForEachEntry( Vec_Int_t *, vGlobs, vGlob, i ) |
| Vec_IntFree( vGlob ); |
| Vec_PtrFree( vGlobs ); |
| printf( "Total = %6d. Nodes = %6d. ", Abc_NtkNodeNum(pNtk), nNodes ); |
| printf( "Cost = %6.2f ", CostAll ); |
| Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); |
| } |
| |
| ABC_NAMESPACE_IMPL_END |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
