diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 20:01:00 -0800 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 20:01:00 -0800 |
commit | 0c6505a26a537dc911b6566f82d759521e527c08 (patch) | |
tree | f2687995efd4943fe3b1307fce7ef5942d0a57b3 /src/base/abci/abcCut.c | |
parent | 4d30a1e4f1edecff86d5066ce4653a370e59e5e1 (diff) | |
download | abc-0c6505a26a537dc911b6566f82d759521e527c08.tar.gz abc-0c6505a26a537dc911b6566f82d759521e527c08.tar.bz2 abc-0c6505a26a537dc911b6566f82d759521e527c08.zip |
Version abc80130_2
Diffstat (limited to 'src/base/abci/abcCut.c')
-rw-r--r-- | src/base/abci/abcCut.c | 494 |
1 files changed, 462 insertions, 32 deletions
diff --git a/src/base/abci/abcCut.c b/src/base/abci/abcCut.c index f487bd1b..d399ce5f 100644 --- a/src/base/abci/abcCut.c +++ b/src/base/abci/abcCut.c @@ -25,8 +25,16 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +static void Abc_NtkPrintCuts( void * p, Abc_Ntk_t * pNtk, int fSeq ); +static void Abc_NtkPrintCuts_( void * p, Abc_Ntk_t * pNtk, int fSeq ); + +extern int nTotal, nGood, nEqual; + +static Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk ); +static int Abc_NtkComputeArea( Abc_Ntk_t * pNtk, Cut_Man_t * p ); + //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -42,18 +50,30 @@ ***********************************************************************/ Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) { + ProgressBar * pProgress; Cut_Man_t * p; - Abc_Obj_t * pObj, * pDriver, * pNode; + Abc_Obj_t * pObj, * pNode; Vec_Ptr_t * vNodes; Vec_Int_t * vChoices; int i; int clk = clock(); - assert( Abc_NtkIsStrash(pNtk) ); + extern void Abc_NtkBalanceAttach( Abc_Ntk_t * pNtk ); + extern void Abc_NtkBalanceDetach( Abc_Ntk_t * pNtk ); + nTotal = nGood = nEqual = 0; + + assert( Abc_NtkIsStrash(pNtk) ); // start the manager pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); p = Cut_ManStart( pParams ); + // compute node attributes if local or global cuts are requested + if ( pParams->fGlobal || pParams->fLocal ) + { + extern Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk ); + Cut_ManSetNodeAttrs( p, Abc_NtkGetNodeAttributes(pNtk) ); + } + // prepare for cut dropping if ( pParams->fDrop ) Cut_ManSetFanoutCounts( p, Abc_NtkFanoutCounts(pNtk) ); // set cuts for PIs @@ -61,8 +81,9 @@ Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) if ( Abc_ObjFanoutNum(pObj) > 0 ) Cut_NodeSetTriv( p, pObj->Id ); // compute cuts for internal nodes - vNodes = Abc_AigDfs( pNtk, 0, 1 ); + vNodes = Abc_AigDfs( pNtk, 0, 1 ); // collects POs vChoices = Vec_IntAlloc( 100 ); + pProgress = Extra_ProgressBarStart( stdout, Vec_PtrSize(vNodes) ); Vec_PtrForEachEntry( vNodes, pObj, i ) { // when we reached a CO, it is time to deallocate the cuts @@ -73,12 +94,19 @@ Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) continue; } // skip constant node, it has no cuts - if ( Abc_NodeIsConst(pObj) ) - continue; +// if ( Abc_NodeIsConst(pObj) ) +// continue; + Extra_ProgressBarUpdate( pProgress, i, NULL ); // compute the cuts to the internal node - Abc_NodeGetCuts( p, pObj ); + Abc_NodeGetCuts( p, pObj, pParams->fDag, pParams->fTree ); + // consider dropping the fanins cuts + if ( pParams->fDrop ) + { + Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId0(pObj) ); + Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId1(pObj) ); + } // add cuts due to choices - if ( Abc_NodeIsAigChoice(pObj) ) + if ( Abc_AigNodeIsChoice(pObj) ) { Vec_IntClear( vChoices ); for ( pNode = pObj; pNode; pNode = pNode->pData ) @@ -86,31 +114,203 @@ Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) Cut_NodeUnionCuts( p, vChoices ); } } - if ( !pParams->fSeq ) + Extra_ProgressBarStop( pProgress ); + Vec_PtrFree( vNodes ); + Vec_IntFree( vChoices ); + Cut_ManPrintStats( p ); +PRT( "TOTAL ", clock() - clk ); + printf( "Area = %d.\n", Abc_NtkComputeArea( pNtk, p ) ); +//Abc_NtkPrintCuts( p, pNtk, 0 ); +// Cut_ManPrintStatsToFile( p, pNtk->pSpec, clock() - clk ); + + // temporary printout of stats + if ( nTotal ) + printf( "Total cuts = %d. Good cuts = %d. Ratio = %5.2f\n", nTotal, nGood, ((double)nGood)/nTotal ); + return p; +} + +/**Function************************************************************* + + Synopsis [Cut computation using the oracle.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkCutsOracle( Abc_Ntk_t * pNtk, Cut_Oracle_t * p ) +{ + Abc_Obj_t * pObj; + Vec_Ptr_t * vNodes; + int i, clk = clock(); + int fDrop = Cut_OracleReadDrop(p); + + assert( Abc_NtkIsStrash(pNtk) ); + + // prepare cut droppping + if ( fDrop ) + Cut_OracleSetFanoutCounts( p, Abc_NtkFanoutCounts(pNtk) ); + + // set cuts for PIs + Abc_NtkForEachCi( pNtk, pObj, i ) + if ( Abc_ObjFanoutNum(pObj) > 0 ) + Cut_OracleNodeSetTriv( p, pObj->Id ); + + // compute cuts for internal nodes + vNodes = Abc_AigDfs( pNtk, 0, 1 ); // collects POs + Vec_PtrForEachEntry( vNodes, pObj, i ) { - Vec_PtrFree( vNodes ); - Vec_IntFree( vChoices ); -PRT( "Total", clock() - clk ); - return p; + // when we reached a CO, it is time to deallocate the cuts + if ( Abc_ObjIsCo(pObj) ) + { + if ( fDrop ) + Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId0(pObj) ); + continue; + } + // skip constant node, it has no cuts +// if ( Abc_NodeIsConst(pObj) ) +// continue; + // compute the cuts to the internal node + Cut_OracleComputeCuts( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj), + Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj) ); + // consider dropping the fanins cuts + if ( fDrop ) + { + Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId0(pObj) ); + Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId1(pObj) ); + } } - assert( 0 ); + Vec_PtrFree( vNodes ); +//PRT( "Total", clock() - clk ); +//Abc_NtkPrintCuts_( p, pNtk, 0 ); +} + - // compute sequential cuts - Abc_NtkIncrementTravId( pNtk ); - Abc_NtkForEachLatch( pNtk, pObj, i ) +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Man_t * Abc_NtkSeqCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) +{ +/* + Cut_Man_t * p; + Abc_Obj_t * pObj, * pNode; + int i, nIters, fStatus; + Vec_Int_t * vChoices; + int clk = clock(); + + assert( Abc_NtkIsSeq(pNtk) ); + assert( pParams->fSeq ); +// assert( Abc_NtkIsDfsOrdered(pNtk) ); + + // start the manager + pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); + pParams->nCutSet = Abc_NtkCutSetNodeNum( pNtk ); + p = Cut_ManStart( pParams ); + + // set cuts for the constant node and the PIs + pObj = Abc_AigConst1(pNtk); + if ( Abc_ObjFanoutNum(pObj) > 0 ) + Cut_NodeSetTriv( p, pObj->Id ); + Abc_NtkForEachPi( pNtk, pObj, i ) { - pDriver = Abc_ObjFanin0(pObj); - if ( !Abc_ObjIsNode(pDriver) ) - continue; - if ( Abc_NodeIsTravIdCurrent(pDriver) ) - continue; - Abc_NodeSetTravIdCurrent(pDriver); - Cut_NodeSetComputedAsNew( p, pDriver->Id ); +//printf( "Setting trivial cut %d.\n", pObj->Id ); + Cut_NodeSetTriv( p, pObj->Id ); + } + // label the cutset nodes and set their number in the array + // assign the elementary cuts to the cutset nodes + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + { + assert( pObj->fMarkC == 0 ); + pObj->fMarkC = 1; + pObj->pCopy = (Abc_Obj_t *)i; + Cut_NodeSetTriv( p, pObj->Id ); +//printf( "Setting trivial cut %d.\n", pObj->Id ); } - // compute as long as new cuts appear + // process the nodes + vChoices = Vec_IntAlloc( 100 ); + for ( nIters = 0; nIters < 10; nIters++ ) + { +//printf( "ITERATION %d:\n", nIters ); + // compute the cuts for the internal nodes + Abc_AigForEachAnd( pNtk, pObj, i ) + { + Abc_NodeGetCutsSeq( p, pObj, nIters==0 ); + // add cuts due to choices + if ( Abc_AigNodeIsChoice(pObj) ) + { + Vec_IntClear( vChoices ); + for ( pNode = pObj; pNode; pNode = pNode->pData ) + Vec_IntPush( vChoices, pNode->Id ); + Cut_NodeUnionCutsSeq( p, vChoices, (pObj->fMarkC ? (int)pObj->pCopy : -1), nIters==0 ); + } + } + // merge the new cuts with the old cuts + Abc_NtkForEachPi( pNtk, pObj, i ) + Cut_NodeNewMergeWithOld( p, pObj->Id ); + Abc_AigForEachAnd( pNtk, pObj, i ) + Cut_NodeNewMergeWithOld( p, pObj->Id ); + // for the cutset, transfer temp cuts to new cuts + fStatus = 0; + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + fStatus |= Cut_NodeTempTransferToNew( p, pObj->Id, i ); + if ( fStatus == 0 ) + break; + } + Vec_IntFree( vChoices ); + + // if the status is not finished, transfer new to old for the cutset + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + Cut_NodeNewMergeWithOld( p, pObj->Id ); + // transfer the old cuts to the new positions + Abc_NtkForEachObj( pNtk, pObj, i ) + Cut_NodeOldTransferToNew( p, pObj->Id ); + + // unlabel the cutset nodes + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + pObj->fMarkC = 0; +if ( pParams->fVerbose ) +{ + Cut_ManPrintStats( p ); +PRT( "TOTAL ", clock() - clk ); +printf( "Converged after %d iterations.\n", nIters ); +} +//Abc_NtkPrintCuts( p, pNtk, 1 ); return p; +*/ + return NULL; +} + +/**Function************************************************************* + + Synopsis [Computes area.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkComputeArea( Abc_Ntk_t * pNtk, Cut_Man_t * p ) +{ + Abc_Obj_t * pObj; + int Counter, i; + Counter = 0; + Abc_NtkForEachCo( pNtk, pObj, i ) + Counter += Cut_ManMappingArea_rec( p, Abc_ObjFaninId0(pObj) ); + return Counter; } /**Function************************************************************* @@ -124,14 +324,14 @@ PRT( "Total", clock() - clk ); SeeAlso [] ***********************************************************************/ -void * Abc_NodeGetCutsRecursive( void * p, Abc_Obj_t * pObj ) +void * Abc_NodeGetCutsRecursive( void * p, Abc_Obj_t * pObj, int fDag, int fTree ) { void * pList; if ( pList = Abc_NodeReadCuts( p, pObj ) ) return pList; - Abc_NodeGetCutsRecursive( p, Abc_ObjFanin0(pObj) ); - Abc_NodeGetCutsRecursive( p, Abc_ObjFanin1(pObj) ); - return Abc_NodeGetCuts( p, pObj ); + Abc_NodeGetCutsRecursive( p, Abc_ObjFanin0(pObj), fDag, fTree ); + Abc_NodeGetCutsRecursive( p, Abc_ObjFanin1(pObj), fDag, fTree ); + return Abc_NodeGetCuts( p, pObj, fDag, fTree ); } /**Function************************************************************* @@ -145,10 +345,73 @@ void * Abc_NodeGetCutsRecursive( void * p, Abc_Obj_t * pObj ) SeeAlso [] ***********************************************************************/ -void * Abc_NodeGetCuts( void * p, Abc_Obj_t * pObj ) +void * Abc_NodeGetCuts( void * p, Abc_Obj_t * pObj, int fDag, int fTree ) { + Abc_Obj_t * pFanin; + int fDagNode, fTriv, TreeCode = 0; +// assert( Abc_NtkIsStrash(pObj->pNtk) ); + assert( Abc_ObjFaninNum(pObj) == 2 ); + + + // check if the node is a DAG node + fDagNode = (Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj)); + // increment the counter of DAG nodes + if ( fDagNode ) Cut_ManIncrementDagNodes( p ); + // add the trivial cut if the node is a DAG node, or if we compute all cuts + fTriv = fDagNode || !fDag; + // check if fanins are DAG nodes + if ( fTree ) + { + pFanin = Abc_ObjFanin0(pObj); + TreeCode |= (Abc_ObjFanoutNum(pFanin) > 1 && !Abc_NodeIsMuxControlType(pFanin)); + pFanin = Abc_ObjFanin1(pObj); + TreeCode |= ((Abc_ObjFanoutNum(pFanin) > 1 && !Abc_NodeIsMuxControlType(pFanin)) << 1); + } + + + // changes due to the global/local cut computation + { + Cut_Params_t * pParams = Cut_ManReadParams(p); + if ( pParams->fLocal ) + { + Vec_Int_t * vNodeAttrs = Cut_ManReadNodeAttrs(p); + fDagNode = Vec_IntEntry( vNodeAttrs, pObj->Id ); + if ( fDagNode ) Cut_ManIncrementDagNodes( p ); +// fTriv = fDagNode || !pParams->fGlobal; + fTriv = !Vec_IntEntry( vNodeAttrs, pObj->Id ); + TreeCode = 0; + pFanin = Abc_ObjFanin0(pObj); + TreeCode |= Vec_IntEntry( vNodeAttrs, pFanin->Id ); + pFanin = Abc_ObjFanin1(pObj); + TreeCode |= (Vec_IntEntry( vNodeAttrs, pFanin->Id ) << 1); + } + } return Cut_NodeComputeCuts( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj), - Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj) ); + Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj), fTriv, TreeCode ); +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NodeGetCutsSeq( void * p, Abc_Obj_t * pObj, int fTriv ) +{ +/* + int CutSetNum; + assert( Abc_NtkIsSeq(pObj->pNtk) ); + assert( Abc_ObjFaninNum(pObj) == 2 ); + fTriv = pObj->fMarkC ? 0 : fTriv; + CutSetNum = pObj->fMarkC ? (int)pObj->pCopy : -1; + Cut_NodeComputeCutsSeq( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj), + Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj), Seq_ObjFaninL0(pObj), Seq_ObjFaninL1(pObj), fTriv, CutSetNum ); +*/ } /**Function************************************************************* @@ -164,7 +427,7 @@ void * Abc_NodeGetCuts( void * p, Abc_Obj_t * pObj ) ***********************************************************************/ void * Abc_NodeReadCuts( void * p, Abc_Obj_t * pObj ) { - return Cut_NodeReadCuts( p, pObj->Id ); + return Cut_NodeReadCutsNew( p, pObj->Id ); } /**Function************************************************************* @@ -183,6 +446,173 @@ void Abc_NodeFreeCuts( void * p, Abc_Obj_t * pObj ) Cut_NodeFreeCuts( p, pObj->Id ); } +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkPrintCuts( void * p, Abc_Ntk_t * pNtk, int fSeq ) +{ + Cut_Man_t * pMan = p; + Cut_Cut_t * pList; + Abc_Obj_t * pObj; + int i; + printf( "Cuts of the network:\n" ); + Abc_NtkForEachObj( pNtk, pObj, i ) + { + pList = Abc_NodeReadCuts( p, pObj ); + printf( "Node %s:\n", Abc_ObjName(pObj) ); + Cut_CutPrintList( pList, fSeq ); + } +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkPrintCuts_( void * p, Abc_Ntk_t * pNtk, int fSeq ) +{ + Cut_Man_t * pMan = p; + Cut_Cut_t * pList; + Abc_Obj_t * pObj; + pObj = Abc_NtkObj( pNtk, 2 * Abc_NtkObjNum(pNtk) / 3 ); + pList = Abc_NodeReadCuts( p, pObj ); + printf( "Node %s:\n", Abc_ObjName(pObj) ); + Cut_CutPrintList( pList, fSeq ); +} + + + + +/**Function************************************************************* + + Synopsis [Assigns global attributes randomly.] + + Description [Old code.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk ) +{ + Vec_Int_t * vAttrs; +// Vec_Ptr_t * vNodes; + Abc_Obj_t * pObj;//, * pTemp; + int i;//, k; + int nNodesTotal = 0, nMffcsTotal = 0; + extern Vec_Ptr_t * Abc_NodeMffsInsideCollect( Abc_Obj_t * pNode ); + + vAttrs = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 ); +// Abc_NtkForEachCi( pNtk, pObj, i ) +// Vec_IntWriteEntry( vAttrs, pObj->Id, 1 ); + + Abc_NtkForEachObj( pNtk, pObj, i ) + { + if ( Abc_ObjIsNode(pObj) ) + nNodesTotal++; + if ( Abc_ObjIsCo(pObj) && Abc_ObjIsNode(Abc_ObjFanin0(pObj)) ) + nMffcsTotal += Abc_NodeMffcSize( Abc_ObjFanin0(pObj) ); +// if ( Abc_ObjIsNode(pObj) && (rand() % 4 == 0) ) +// if ( Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj) && (rand() % 3 == 0) ) + if ( Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj) ) + { + int nMffc = Abc_NodeMffcSize(pObj); + nMffcsTotal += Abc_NodeMffcSize(pObj); +// printf( "%d ", nMffc ); + + if ( nMffc > 2 || Abc_ObjFanoutNum(pObj) > 8 ) + Vec_IntWriteEntry( vAttrs, pObj->Id, 1 ); + } + } +/* + Abc_NtkForEachObj( pNtk, pObj, i ) + { + if ( Vec_IntEntry( vAttrs, pObj->Id ) ) + { + vNodes = Abc_NodeMffsInsideCollect( pObj ); + Vec_PtrForEachEntry( vNodes, pTemp, k ) + if ( pTemp != pObj ) + Vec_IntWriteEntry( vAttrs, pTemp->Id, 0 ); + Vec_PtrFree( vNodes ); + } + } +*/ + printf( "Total nodes = %d. Total MFFC nodes = %d.\n", nNodesTotal, nMffcsTotal ); + return vAttrs; +} + +/**Function************************************************************* + + Synopsis [Assigns global attributes randomly.] + + Description [Old code.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkSubDagSize_rec( Abc_Obj_t * pObj, Vec_Int_t * vAttrs ) +{ + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return 0; + Abc_NodeSetTravIdCurrent(pObj); + if ( Vec_IntEntry( vAttrs, pObj->Id ) ) + return 0; + if ( Abc_ObjIsCi(pObj) ) + return 1; + assert( Abc_ObjFaninNum(pObj) == 2 ); + return 1 + Abc_NtkSubDagSize_rec(Abc_ObjFanin0(pObj), vAttrs) + + Abc_NtkSubDagSize_rec(Abc_ObjFanin1(pObj), vAttrs); +} + +/**Function************************************************************* + + Synopsis [Assigns global attributes randomly.] + + Description [Old code.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Abc_NtkGetNodeAttributes2( Abc_Ntk_t * pNtk ) +{ + Vec_Int_t * vAttrs; + Abc_Obj_t * pObj; + int i, nSize; + assert( Abc_NtkIsDfsOrdered(pNtk) ); + vAttrs = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 ); + Abc_NtkForEachObj( pNtk, pObj, i ) + { + // skip no-nodes and nodes without fanouts + if ( pObj->Id == 0 || !(Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj)) ) + continue; + // the node has more than one fanout - count its sub-DAG size + Abc_NtkIncrementTravId( pNtk ); + nSize = Abc_NtkSubDagSize_rec( pObj, vAttrs ); + if ( nSize > 15 ) + Vec_IntWriteEntry( vAttrs, pObj->Id, 1 ); + } + return vAttrs; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// |