| /**CFile**************************************************************** |
| |
| FileName [cnfMap.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [AIG-to-CNF conversion.] |
| |
| Synopsis [] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - April 28, 2007.] |
| |
| Revision [$Id: cnfMap.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "cnf.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes area flow of the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Cnf_CutAssignAreaFlow( Cnf_Man_t * p, Dar_Cut_t * pCut, int * pAreaFlows ) |
| { |
| Aig_Obj_t * pLeaf; |
| int i; |
| pCut->Value = 0; |
| // pCut->uSign = 100 * Cnf_CutSopCost( p, pCut ); |
| pCut->uSign = 10 * Cnf_CutSopCost( p, pCut ); |
| Dar_CutForEachLeaf( p->pManAig, pCut, pLeaf, i ) |
| { |
| pCut->Value += pLeaf->nRefs; |
| if ( !Aig_ObjIsNode(pLeaf) ) |
| continue; |
| assert( pLeaf->nRefs > 0 ); |
| pCut->uSign += pAreaFlows[pLeaf->Id] / (pLeaf->nRefs? pLeaf->nRefs : 1); |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes area flow of the supergate.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Cnf_CutSuperAreaFlow( Vec_Ptr_t * vSuper, int * pAreaFlows ) |
| { |
| Aig_Obj_t * pLeaf; |
| int i, nAreaFlow; |
| nAreaFlow = 100 * (Vec_PtrSize(vSuper) + 1); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vSuper, pLeaf, i ) |
| { |
| pLeaf = Aig_Regular(pLeaf); |
| if ( !Aig_ObjIsNode(pLeaf) ) |
| continue; |
| assert( pLeaf->nRefs > 0 ); |
| nAreaFlow += pAreaFlows[pLeaf->Id] / (pLeaf->nRefs? pLeaf->nRefs : 1); |
| } |
| return nAreaFlow; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Cnf_DeriveMapping( Cnf_Man_t * p ) |
| { |
| Vec_Ptr_t * vSuper; |
| Aig_Obj_t * pObj; |
| Dar_Cut_t * pCut, * pCutBest; |
| int i, k, AreaFlow, * pAreaFlows; |
| // allocate area flows |
| pAreaFlows = ABC_ALLOC( int, Aig_ManObjNumMax(p->pManAig) ); |
| memset( pAreaFlows, 0, sizeof(int) * Aig_ManObjNumMax(p->pManAig) ); |
| // visit the nodes in the topological order and update their best cuts |
| vSuper = Vec_PtrAlloc( 100 ); |
| Aig_ManForEachNode( p->pManAig, pObj, i ) |
| { |
| // go through the cuts |
| pCutBest = NULL; |
| Dar_ObjForEachCut( pObj, pCut, k ) |
| { |
| pCut->fBest = 0; |
| if ( k == 0 ) |
| continue; |
| Cnf_CutAssignAreaFlow( p, pCut, pAreaFlows ); |
| if ( pCutBest == NULL || pCutBest->uSign > pCut->uSign || |
| (pCutBest->uSign == pCut->uSign && pCutBest->Value < pCut->Value) ) |
| pCutBest = pCut; |
| } |
| // check the big cut |
| // Aig_ObjCollectSuper( pObj, vSuper ); |
| // get the area flow of this cut |
| // AreaFlow = Cnf_CutSuperAreaFlow( vSuper, pAreaFlows ); |
| AreaFlow = ABC_INFINITY; |
| if ( AreaFlow >= (int)pCutBest->uSign ) |
| { |
| pAreaFlows[pObj->Id] = pCutBest->uSign; |
| pCutBest->fBest = 1; |
| } |
| else |
| { |
| pAreaFlows[pObj->Id] = AreaFlow; |
| pObj->fMarkB = 1; // mark the special node |
| } |
| } |
| Vec_PtrFree( vSuper ); |
| ABC_FREE( pAreaFlows ); |
| |
| /* |
| // compute the area of mapping |
| AreaFlow = 0; |
| Aig_ManForEachCo( p->pManAig, pObj, i ) |
| AreaFlow += Dar_ObjBestCut(Aig_ObjFanin0(pObj))->uSign / 100 / Aig_ObjFanin0(pObj)->nRefs; |
| printf( "Area of the network = %d.\n", AreaFlow ); |
| */ |
| } |
| |
| |
| |
| #if 0 |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes area of the first level.] |
| |
| Description [The cut need to be derefed.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Aig_CutDeref( Aig_Man_t * p, Dar_Cut_t * pCut ) |
| { |
| Aig_Obj_t * pLeaf; |
| int i; |
| Dar_CutForEachLeaf( p, pCut, pLeaf, i ) |
| { |
| assert( pLeaf->nRefs > 0 ); |
| if ( --pLeaf->nRefs > 0 || !Aig_ObjIsAnd(pLeaf) ) |
| continue; |
| Aig_CutDeref( p, Aig_ObjBestCut(pLeaf) ); |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes area of the first level.] |
| |
| Description [The cut need to be derefed.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Aig_CutRef( Aig_Man_t * p, Dar_Cut_t * pCut ) |
| { |
| Aig_Obj_t * pLeaf; |
| int i, Area = pCut->Value; |
| Dar_CutForEachLeaf( p, pCut, pLeaf, i ) |
| { |
| assert( pLeaf->nRefs >= 0 ); |
| if ( pLeaf->nRefs++ > 0 || !Aig_ObjIsAnd(pLeaf) ) |
| continue; |
| Area += Aig_CutRef( p, Aig_ObjBestCut(pLeaf) ); |
| } |
| return Area; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes exact area of the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Cnf_CutArea( Aig_Man_t * p, Dar_Cut_t * pCut ) |
| { |
| int Area; |
| Area = Aig_CutRef( p, pCut ); |
| Aig_CutDeref( p, pCut ); |
| return Area; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns 1 if the second cut is better.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline int Cnf_CutCompare( Dar_Cut_t * pC0, Dar_Cut_t * pC1 ) |
| { |
| if ( pC0->Area < pC1->Area - 0.0001 ) |
| return -1; |
| if ( pC0->Area > pC1->Area + 0.0001 ) // smaller area flow is better |
| return 1; |
| // if ( pC0->NoRefs < pC1->NoRefs ) |
| // return -1; |
| // if ( pC0->NoRefs > pC1->NoRefs ) // fewer non-referenced fanins is better |
| // return 1; |
| // if ( pC0->FanRefs / pC0->nLeaves > pC1->FanRefs / pC1->nLeaves ) |
| // return -1; |
| // if ( pC0->FanRefs / pC0->nLeaves < pC1->FanRefs / pC1->nLeaves ) |
| // return 1; // larger average fanin ref-counter is better |
| // return 0; |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns the cut with the smallest area flow.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Dar_Cut_t * Cnf_ObjFindBestCut( Aig_Obj_t * pObj ) |
| { |
| Dar_Cut_t * pCut, * pCutBest; |
| int i; |
| pCutBest = NULL; |
| Dar_ObjForEachCut( pObj, pCut, i ) |
| if ( pCutBest == NULL || Cnf_CutCompare(pCutBest, pCut) == 1 ) |
| pCutBest = pCut; |
| return pCutBest; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes area flow of the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Cnf_CutAssignArea( Cnf_Man_t * p, Dar_Cut_t * pCut ) |
| { |
| Aig_Obj_t * pLeaf; |
| int i; |
| pCut->Area = (float)pCut->Cost; |
| pCut->NoRefs = 0; |
| pCut->FanRefs = 0; |
| Dar_CutForEachLeaf( p->pManAig, pCut, pLeaf, i ) |
| { |
| if ( !Aig_ObjIsNode(pLeaf) ) |
| continue; |
| if ( pLeaf->nRefs == 0 ) |
| { |
| pCut->Area += Aig_ObjBestCut(pLeaf)->Cost; |
| pCut->NoRefs++; |
| } |
| else |
| { |
| if ( pCut->FanRefs + pLeaf->nRefs > 15 ) |
| pCut->FanRefs = 15; |
| else |
| pCut->FanRefs += pLeaf->nRefs; |
| } |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs one round of "area recovery" using exact local area.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Cnf_ManMapForCnf( Cnf_Man_t * p ) |
| { |
| Aig_Obj_t * pObj; |
| Dar_Cut_t * pCut, * pCutBest; |
| int i, k; |
| // visit the nodes in the topological order and update their best cuts |
| Aig_ManForEachNode( p->pManAig, pObj, i ) |
| { |
| // find the old best cut |
| pCutBest = Aig_ObjBestCut(pObj); |
| Dar_ObjClearBestCut(pCutBest); |
| // if the node is used, dereference its cut |
| if ( pObj->nRefs ) |
| Aig_CutDeref( p->pManAig, pCutBest ); |
| |
| // evaluate the cuts of this node |
| Dar_ObjForEachCut( pObj, pCut, k ) |
| // Cnf_CutAssignAreaFlow( p, pCut ); |
| pCut->Area = (float)Cnf_CutArea( p->pManAig, pCut ); |
| |
| // find the new best cut |
| pCutBest = Cnf_ObjFindBestCut(pObj); |
| Dar_ObjSetBestCut( pCutBest ); |
| // if the node is used, reference its cut |
| if ( pObj->nRefs ) |
| Aig_CutRef( p->pManAig, pCutBest ); |
| } |
| return 1; |
| } |
| |
| #endif |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
