diff options
Diffstat (limited to 'src/map')
-rw-r--r-- | src/map/fpga/fpga.c | 4 | ||||
-rw-r--r-- | src/map/fpga/fpgaCore.c | 19 | ||||
-rw-r--r-- | src/map/fpga/fpgaCut.c | 4 | ||||
-rw-r--r-- | src/map/fpga/fpgaMatch.c | 12 | ||||
-rw-r--r-- | src/map/if/if.h | 17 | ||||
-rw-r--r-- | src/map/if/ifCore.c | 68 | ||||
-rw-r--r-- | src/map/if/ifMan.c | 8 | ||||
-rw-r--r-- | src/map/if/ifMap.c | 334 | ||||
-rw-r--r-- | src/map/mapper/mapperCut.c | 3 |
9 files changed, 384 insertions, 85 deletions
diff --git a/src/map/fpga/fpga.c b/src/map/fpga/fpga.c index d04c9910..d7a128b0 100644 --- a/src/map/fpga/fpga.c +++ b/src/map/fpga/fpga.c @@ -57,8 +57,8 @@ void Fpga_Init( Abc_Frame_t * pAbc ) { // set the default library //Fpga_LutLib_t s_LutLib = { "lutlib", 6, {0,1,2,4,8,16,32}, {0,1,2,3,4,5,6} }; -// Fpga_LutLib_t s_LutLib = { "lutlib", 5, {0,1,1,1,1,1}, {0,1,1,1,1,1} }; - Fpga_LutLib_t s_LutLib = { "lutlib", 4, {0,1,1,1,1}, {0,1,1,1,1} }; + Fpga_LutLib_t s_LutLib = { "lutlib", 5, {0,1,1,1,1,1}, {0,1,1,1,1,1} }; +// Fpga_LutLib_t s_LutLib = { "lutlib", 4, {0,1,1,1,1}, {0,1,1,1,1} }; //Fpga_LutLib_t s_LutLib = { "lutlib", 3, {0,1,1,1}, {0,1,1,1} }; Abc_FrameSetLibLut( Fpga_LutLibDup(&s_LutLib) ); diff --git a/src/map/fpga/fpgaCore.c b/src/map/fpga/fpgaCore.c index 56facf20..634a8eb1 100644 --- a/src/map/fpga/fpgaCore.c +++ b/src/map/fpga/fpgaCore.c @@ -79,8 +79,12 @@ int Fpga_Mapping( Fpga_Man_t * p ) // print the AI-graph used for mapping //Fpga_ManShow( p, "test" ); +// if ( p->fVerbose ) +// Fpga_MappingPrintOutputArrivals( p ); if ( p->fVerbose ) - Fpga_MappingPrintOutputArrivals( p ); + { + PRT( "Total time", clock() - clkTotal ); + } return 1; } @@ -101,14 +105,14 @@ int Fpga_Mapping( Fpga_Man_t * p ) ***********************************************************************/ int Fpga_MappingPostProcess( Fpga_Man_t * p ) { - int fShowSwitching = 1; + int fShowSwitching = 0; int fRecoverAreaFlow = 1; int fRecoverArea = 1; float aAreaTotalCur, aAreaTotalCur2; int Iter, clk; -if ( p->fVerbose ) - printf( "Best clock period = %5.2f\n", Fpga_TimeComputeArrivalMax(p) ); +//if ( p->fVerbose ) +// printf( "Best clock period = %5.2f\n", Fpga_TimeComputeArrivalMax(p) ); // compute area, set references, and collect nodes used in the mapping Iter = 1; @@ -118,6 +122,9 @@ if ( p->fVerbose ) printf( "Iteration %dD : Area = %8.1f ", Iter++, aAreaTotalCur ); if ( fShowSwitching ) printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) ); +else +printf( "Delay = %5.2f ", Fpga_TimeComputeArrivalMax(p) ); + PRT( "Time", p->timeMatch ); } @@ -141,6 +148,8 @@ if ( p->fVerbose ) printf( "Iteration %dF : Area = %8.1f ", Iter++, aAreaTotalCur ); if ( fShowSwitching ) printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) ); +else +printf( "Delay = %5.2f ", Fpga_TimeComputeArrivalMax(p) ); PRT( "Time", clock() - clk ); } } @@ -166,6 +175,8 @@ if ( p->fVerbose ) printf( "Iteration %d%s : Area = %8.1f ", Iter++, (p->fSwitching?"S":"A"), aAreaTotalCur ); if ( fShowSwitching ) printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) ); +else +printf( "Delay = %5.2f ", Fpga_TimeComputeArrivalMax(p) ); PRT( "Time", clock() - clk ); } } diff --git a/src/map/fpga/fpgaCut.c b/src/map/fpga/fpgaCut.c index c2aba4a3..a5505e72 100644 --- a/src/map/fpga/fpgaCut.c +++ b/src/map/fpga/fpgaCut.c @@ -130,6 +130,7 @@ void Fpga_MappingCuts( Fpga_Man_t * p ) Fpga_CutTable_t * pTable; Fpga_Node_t * pNode; int nCuts, nNodes, i; + int clk = clock(); // set the elementary cuts for the PI variables assert( p->nVarsMax > 1 && p->nVarsMax < 11 ); @@ -154,8 +155,9 @@ void Fpga_MappingCuts( Fpga_Man_t * p ) if ( p->fVerbose ) { nCuts = Fpga_CutCountAll(p); - printf( "Nodes = %6d. Total %d-feasible cuts = %d. Cuts per node = %.1f.\n", + printf( "Nodes = %6d. Total %d-cuts = %d. Cuts per node = %.1f. ", p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes ); + PRT( "Time", clock() - clk ); } // print the cuts for the first primary output diff --git a/src/map/fpga/fpgaMatch.c b/src/map/fpga/fpgaMatch.c index 736d38b2..d413a067 100644 --- a/src/map/fpga/fpgaMatch.c +++ b/src/map/fpga/fpgaMatch.c @@ -87,6 +87,18 @@ int Fpga_MappingMatches( Fpga_Man_t * p, int fDelayOriented ) Extra_ProgressBarUpdate( pProgress, i, "Matches ..." ); } Extra_ProgressBarStop( pProgress ); +/* + if ( !fDelayOriented ) + { + float Area = 0.0; + for ( i = 0; i < p->nOutputs; i++ ) + { + printf( "%5.2f ", Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow ); + Area += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow; + } + printf( "\nTotal = %5.2f\n", Area ); + } +*/ return 1; } diff --git a/src/map/if/if.h b/src/map/if/if.h index 04e1541e..a1d2d41b 100644 --- a/src/map/if/if.h +++ b/src/map/if/if.h @@ -75,8 +75,10 @@ struct If_Par_t_ If_Lib_t * pLutLib; // the LUT library int nCutsMax; // the max number of cuts int fVerbose; // the verbosity flag - int fSeq; // sequential mapping + int fArea; // area-oriented mapping + int fFancy; // a fancy feature int fLatchPaths; // reset timing on latch paths + int fSeq; // sequential mapping int nLatches; // the number of latches float DelayTarget; // delay target float * pTimesArr; // arrival times @@ -110,6 +112,9 @@ struct If_Man_t_ float fEpsilon; // epsilon used for comparison float RequiredGlo; // global required times float AreaGlo; // global area + int nCutsUsed; // the number of cuts currently used + int nCutsMerged; // the total number of cuts merged + int nCutsMax; // the maximum number of cuts at a node // memory management Mem_Fixed_t * pMem; // memory manager int nEntrySize; // the size of the entry @@ -123,7 +128,6 @@ struct If_Man_t_ struct If_Cut_t_ { float Delay; // the delay of the cut - float Flow; // the area flow of the cut float Area; // the area of the cut If_Cut_t * pOne; // the parent cut If_Cut_t * pTwo; // the parent cut @@ -162,6 +166,10 @@ static inline If_Obj_t * If_ManPo( If_Man_t * p, int i ) { r static inline If_Obj_t * If_ManObj( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vObjs, i ); } static inline If_Cut_t * If_ManCut( If_Man_t * p, int i ) { return p->ppCuts[i]; } +static inline int If_ManPiNum( If_Man_t * p ) { return p->nObjs[IF_PI]; } +static inline int If_ManPoNum( If_Man_t * p ) { return p->nObjs[IF_PO]; } +static inline int If_ManAndNum( If_Man_t * p ) { return p->nObjs[IF_AND]; } + static inline int If_ObjIsConst1( If_Obj_t * pObj ) { return pObj->Type == IF_CONST1; } static inline int If_ObjIsPi( If_Obj_t * pObj ) { return pObj->Type == IF_PI; } static inline int If_ObjIsPo( If_Obj_t * pObj ) { return pObj->Type == IF_PO; } @@ -229,6 +237,8 @@ static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { r /// FUNCTION DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +/*=== ifCore.c ==========================================================*/ +extern int If_ManPerformMapping( If_Man_t * p ); /*=== ifMan.c ==========================================================*/ extern If_Man_t * If_ManStart( If_Par_t * pPars ); extern void If_ManStop( If_Man_t * p ); @@ -236,11 +246,12 @@ extern If_Obj_t * If_ManCreatePi( If_Man_t * p ); extern If_Obj_t * If_ManCreatePo( If_Man_t * p, If_Obj_t * pDriver, int fCompl0 ); extern If_Obj_t * If_ManCreateAnd( If_Man_t * p, If_Obj_t * pFan0, int fCompl0, If_Obj_t * pFan1, int fCompl1 ); /*=== ifMap.c ==========================================================*/ -extern int If_ManPerformMapping( If_Man_t * p ); +extern void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode ); /*=== ifUtil.c ==========================================================*/ extern float If_ManDelayMax( If_Man_t * p ); extern void If_ManCleanNodeCopy( If_Man_t * p ); extern void If_ManCleanCutData( If_Man_t * p ); +extern void If_ManComputeRequired( If_Man_t * p, int fFirstTime ); extern float If_ManScanMapping( If_Man_t * p ); #ifdef __cplusplus diff --git a/src/map/if/ifCore.c b/src/map/if/ifCore.c index 4d7e92d0..37a22d8b 100644 --- a/src/map/if/ifCore.c +++ b/src/map/if/ifCore.c @@ -24,6 +24,8 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +static int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode ); + //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// @@ -39,6 +41,72 @@ SeeAlso [] ***********************************************************************/ +int If_ManPerformMapping( If_Man_t * p ) +{ + If_Obj_t * pObj; + int nItersFlow = 2; + int nItersArea = 1; + int clkTotal = clock(); + int i; + // set arrival times and trivial cuts at const 1 and PIs + If_ManConst1(p)->Cuts[0].Delay = 0.0; + If_ManForEachPi( p, pObj, i ) + pObj->Cuts[0].Delay = p->pPars->pTimesArr[i]; + // set the fanout estimates of the PIs + If_ManForEachPi( p, pObj, i ) + pObj->EstRefs = (float)1.0; + // delay oriented mapping + If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0 ); + // area flow oriented mapping + for ( i = 0; i < nItersFlow; i++ ) + If_ManPerformMappingRound( p, p->pPars->nCutsMax, 1 ); + // area oriented mapping + for ( i = 0; i < nItersArea; i++ ) + If_ManPerformMappingRound( p, p->pPars->nCutsMax, 2 ); + if ( p->pPars->fVerbose ) + { + PRT( "Total time", clock() - clkTotal ); + } + return 1; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode ) +{ + If_Obj_t * pObj; + int i, clk = clock(); + assert( Mode >= 0 && Mode <= 2 ); + // set the cut number + p->nCutsUsed = nCutsUsed; + p->nCutsMerged = 0; + p->nCutsMax = 0; + // map the internal nodes + If_ManForEachNode( p, pObj, i ) + If_ObjPerformMapping( p, pObj, Mode ); + // compute required times and stats + If_ManComputeRequired( p, Mode==0 ); + if ( p->pPars->fVerbose ) + { + char Symb = (Mode == 0)? 'D' : ((Mode == 1)? 'F' : 'A'); + printf( "%c: Del = %6.2f. Area = %8.2f. Cuts = %6d. Lim = %2d. Ave = %5.2f. ", + Symb, p->RequiredGlo, p->AreaGlo, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) ); + PRT( "T", clock() - clk ); +// printf( "Max number of cuts = %d. Average number of cuts = %5.2f.\n", +// p->nCutsMax, 1.0 * p->nCutsMerged / If_ManAndNum(p) ); + } + return 1; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c index 616c5cf6..bc13c6f0 100644 --- a/src/map/if/ifMan.c +++ b/src/map/if/ifMan.c @@ -97,7 +97,7 @@ void If_ManStop( If_Man_t * p ) FREE( p->pPars->pTimesReq ); // free temporary cut memory pTemp = p->ppCuts[0]; - for ( i = 1; i < p->pPars->nCutsMax * p->pPars->nCutsMax; i++ ) + for ( i = 1; i < 1 + p->pPars->nCutsMax * p->pPars->nCutsMax; i++ ) if ( pTemp > p->ppCuts[i] ) pTemp = p->ppCuts[i]; free( pTemp ); @@ -228,14 +228,18 @@ If_Cut_t ** If_ManSetupCuts( If_Man_t * p ) { If_Cut_t ** pCutStore; int * pArrays, nCutSize, nCutsTotal, i; - nCutsTotal = p->pPars->nCutsMax * p->pPars->nCutsMax; + // decide how many cuts to alloc + nCutsTotal = 1 + p->pPars->nCutsMax * p->pPars->nCutsMax; + // figure out the cut size nCutSize = sizeof(If_Cut_t) + sizeof(int) * p->pPars->nLutSize; + // allocate and clean space for cuts pCutStore = (If_Cut_t **)ALLOC( If_Cut_t *, (nCutsTotal + 1) ); memset( pCutStore, 0, sizeof(If_Cut_t *) * (nCutsTotal + 1) ); pCutStore[0] = (If_Cut_t *)ALLOC( char, nCutSize * nCutsTotal ); memset( pCutStore[0], 0, nCutSize * nCutsTotal ); for ( i = 1; i < nCutsTotal; i++ ) pCutStore[i] = (If_Cut_t *)((char *)pCutStore[0] + sizeof(If_Cut_t) * i); + // assign room for cut leaves pArrays = (int *)((char *)pCutStore[0] + sizeof(If_Cut_t) * nCutsTotal); for ( i = 0; i < nCutsTotal; i++ ) pCutStore[i]->pLeaves = pArrays + i * p->pPars->nLutSize; diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c index 5f2c4133..0b505062 100644 --- a/src/map/if/ifMap.c +++ b/src/map/if/ifMap.c @@ -24,13 +24,69 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +/* + Ideas to try: + - reverse order of area recovery + - ordering of the outputs by size + - merging Delay, Delay2, and Area + - expand/reduce area recovery + +*/ + //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* - Synopsis [Prepares the object for FPGA mapping.] + Synopsis [Returns 1 if pDom is contained in pCut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_CutCheckDominance( If_Cut_t * pDom, If_Cut_t * pCut ) +{ + int i, k; + for ( i = 0; i < (int)pDom->nLeaves; i++ ) + { + for ( k = 0; k < (int)pCut->nLeaves; k++ ) + if ( pDom->pLeaves[i] == pCut->pLeaves[k] ) + break; + if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut + return 0; + } + // every node in pDom is contained in pCut + return 1; +} + +/**Function************************************************************* + + Synopsis [Returns 1 if pDom is equal to pCut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_CutCheckEquality( If_Cut_t * pDom, If_Cut_t * pCut ) +{ + int i; + if ( (int)pDom->nLeaves != (int)pCut->nLeaves ) + return 0; + for ( i = 0; i < (int)pDom->nLeaves; i++ ) + if ( pDom->pLeaves[i] != pCut->pLeaves[i] ) + return 0; + return 1; +} +/**Function************************************************************* + + Synopsis [Returns 1 if the cut is contained.] Description [] @@ -39,8 +95,39 @@ SeeAlso [] ***********************************************************************/ -int If_CutMerge( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC, int nLimit ) +int If_CutFilter( If_Man_t * p, If_Cut_t * pCut ) { + If_Cut_t * pTemp; + int i; + for ( i = 0; i < p->nCuts; i++ ) + { + pTemp = p->ppCuts[i]; + if ( pTemp->nLeaves > pCut->nLeaves ) + continue; + // skip the non-contained cuts +// if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign ) +// continue; + // check containment seriously + if ( If_CutCheckDominance( pTemp, pCut ) ) +// if ( If_CutCheckEquality( pTemp, pCut ) ) + return 1; + } + return 0; +} + +/**Function************************************************************* + + Synopsis [Prepares the object for FPGA mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC, int nLimit ) +{ int i, k, c; assert( pC0->nLeaves >= pC1->nLeaves ); // the case of the largest cut sizes @@ -125,6 +212,33 @@ int If_CutMerge( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC, int nLimit ) SeeAlso [] ***********************************************************************/ +static inline int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut, int nLimit ) +{ + // merge the nodes + if ( pCut0->nLeaves < pCut1->nLeaves ) + { + if ( !If_CutMergeOrdered( pCut1, pCut0, pCut, nLimit ) ) + return 0; + } + else + { + if ( !If_CutMergeOrdered( pCut0, pCut1, pCut, nLimit ) ) + return 0; + } + return 1; +} + +/**Function************************************************************* + + Synopsis [Prepares the object for FPGA mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ int If_CutCompareDelay( If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) { If_Cut_t * pC0 = *ppC0; @@ -137,9 +251,39 @@ int If_CutCompareDelay( If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) return -1; if ( pC0->nLeaves > pC1->nLeaves ) return 1; - if ( pC0->Flow < pC1->Flow ) + if ( pC0->Area < pC1->Area ) return -1; - if ( pC0->Flow > pC1->Flow ) + if ( pC0->Area > pC1->Area ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Prepares the object for FPGA mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutCompareDelayOld( If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) +{ + If_Cut_t * pC0 = *ppC0; + If_Cut_t * pC1 = *ppC1; + if ( pC0->Delay < pC1->Delay ) + return -1; + if ( pC0->Delay > pC1->Delay ) + return 1; + if ( pC0->Area < pC1->Area ) + return -1; + if ( pC0->Area > pC1->Area ) + return 1; + if ( pC0->nLeaves < pC1->nLeaves ) + return -1; + if ( pC0->nLeaves > pC1->nLeaves ) return 1; return 0; } @@ -159,9 +303,9 @@ int If_CutCompareArea( If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) { If_Cut_t * pC0 = *ppC0; If_Cut_t * pC1 = *ppC1; - if ( pC0->Flow < pC1->Flow ) + if ( pC0->Area < pC1->Area ) return -1; - if ( pC0->Flow > pC1->Flow ) + if ( pC0->Area > pC1->Area ) return 1; if ( pC0->nLeaves < pC1->nLeaves ) return -1; @@ -176,6 +320,28 @@ int If_CutCompareArea( If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) /**Function************************************************************* + Synopsis [Sorts the cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void If_ManSortCuts( If_Man_t * p, int Mode ) +{ + // sort the cuts + if ( Mode || p->pPars->fArea ) // area + qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareArea ); + else if ( p->pPars->fFancy ) + qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelayOld ); + else + qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelay ); +} + +/**Function************************************************************* + Synopsis [Computes delay.] Description [] @@ -190,6 +356,7 @@ float If_CutDelay( If_Man_t * p, If_Cut_t * pCut ) If_Obj_t * pLeaf; float Delay; int i; + assert( pCut->nLeaves > 1 ); Delay = -IF_FLOAT_LARGE; If_CutForEachLeaf( p, pCut, pLeaf, i ) Delay = IF_MAX( Delay, If_ObjCutBest(pLeaf)->Delay ); @@ -212,9 +379,18 @@ float If_CutFlow( If_Man_t * p, If_Cut_t * pCut ) If_Obj_t * pLeaf; float Flow; int i; + assert( pCut->nLeaves > 1 ); Flow = If_CutLutArea(p, pCut); If_CutForEachLeaf( p, pCut, pLeaf, i ) - Flow += If_ObjCutBest(pLeaf)->Flow / pLeaf->EstRefs; + { + if ( pLeaf->nRefs == 0 ) + Flow += If_ObjCutBest(pLeaf)->Area; + else + { + assert( pLeaf->EstRefs > p->fEpsilon ); + Flow += If_ObjCutBest(pLeaf)->Area / pLeaf->EstRefs; + } + } return Flow; } @@ -229,15 +405,19 @@ float If_CutFlow( If_Man_t * p, If_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -float If_CutArea1( If_Man_t * p, If_Cut_t * pCut ) +float If_CutRef( If_Man_t * p, If_Cut_t * pCut, int nLevels ) { If_Obj_t * pLeaf; float Area; int i; Area = If_CutLutArea(p, pCut); If_CutForEachLeaf( p, pCut, pLeaf, i ) - if ( pLeaf->nRefs == 0 ) - Area += If_CutLutArea(p, If_ObjCutBest(pLeaf)); + { + assert( pLeaf->nRefs >= 0 ); + if ( pLeaf->nRefs++ > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 ) + continue; + Area += If_CutRef( p, If_ObjCutBest(pLeaf), nLevels - 1 ); + } return Area; } @@ -252,12 +432,20 @@ float If_CutArea1( If_Man_t * p, If_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -void If_CutRef1( If_Man_t * p, If_Cut_t * pCut ) +float If_CutDeref( If_Man_t * p, If_Cut_t * pCut, int nLevels ) { If_Obj_t * pLeaf; + float Area; int i; + Area = If_CutLutArea(p, pCut); If_CutForEachLeaf( p, pCut, pLeaf, i ) - pLeaf->nRefs++; + { + assert( pLeaf->nRefs > 0 ); + if ( --pLeaf->nRefs > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 ) + continue; + Area += If_CutDeref( p, If_ObjCutBest(pLeaf), nLevels - 1 ); + } + return Area; } /**Function************************************************************* @@ -271,12 +459,14 @@ void If_CutRef1( If_Man_t * p, If_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -void If_CutDeref1( If_Man_t * p, If_Cut_t * pCut ) +float If_CutArea( If_Man_t * p, If_Cut_t * pCut, int nLevels ) { - If_Obj_t * pLeaf; - int i; - If_CutForEachLeaf( p, pCut, pLeaf, i ) - pLeaf->nRefs--; + float aResult, aResult2; + assert( pCut->nLeaves > 1 ); + aResult2 = If_CutRef( p, pCut, nLevels ); + aResult = If_CutDeref( p, pCut, nLevels ); + assert( aResult == aResult2 ); + return aResult; } /**Function************************************************************* @@ -303,85 +493,85 @@ void If_CutCopy( If_Cut_t * pCutDest, If_Cut_t * pCutSrc ) Synopsis [Finds the best cut.] - Description [] + Description [Mapping modes: delay (0), area flow (1), area (2).] SideEffects [] SeeAlso [] ***********************************************************************/ -void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj ) +void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode ) { If_Cut_t * pCut0, * pCut1, * pCut; int i, k; - // create cross-product of the cuts + + // prepare + if ( Mode == 0 ) + pObj->EstRefs = (float)pObj->nRefs; + else if ( Mode == 1 ) + pObj->EstRefs = (float)((2.0 * pObj->EstRefs + pObj->nRefs) / 3.0); + else if ( Mode == 2 && pObj->nRefs > 0 ) + If_CutDeref( p, If_ObjCutBest(pObj), 100 ); + + // recompute the parameters of the best cut p->nCuts = 0; - pCut = p->ppCuts[0]; + p->nCutsMerged++; + if ( Mode ) + { + pCut = If_ObjCutBest(pObj); + pCut->Delay = If_CutDelay( p, pCut ); + assert( pCut->Delay <= pObj->Required + p->fEpsilon ); + pCut->Area = (Mode == 2)? If_CutArea( p, pCut, 100 ) : If_CutFlow( p, pCut ); + // save the best cut from the previous iteration + If_CutCopy( p->ppCuts[p->nCuts++], pCut ); + p->nCutsMerged++; + } + + // generate cuts + pCut = p->ppCuts[p->nCuts]; If_ObjForEachCut( pObj->pFanin0, pCut0, i ) If_ObjForEachCut( pObj->pFanin1, pCut1, k ) { - if ( pCut0->nLeaves < pCut1->nLeaves ) - { - if ( !If_CutMerge( pCut1, pCut0, pCut, p->pPars->nLutSize ) ) - continue; - } - else - { - if ( !If_CutMerge( pCut0, pCut1, pCut, p->pPars->nLutSize ) ) - continue; - } + // prefilter using arrival times + if ( Mode && (pCut0->Delay > pObj->Required + p->fEpsilon || pCut1->Delay > pObj->Required + p->fEpsilon) ) + continue; + // merge the nodes + if ( !If_CutMerge( pCut0, pCut1, pCut, p->pPars->nLutSize ) ) + continue; + // check if this cut is contained in any of the available cuts + if ( If_CutFilter( p, pCut ) ) + continue; + // check if the cut satisfies the required times + pCut->Delay = If_CutDelay( p, pCut ); + if ( Mode && pCut->Delay > pObj->Required + p->fEpsilon ) + continue; // the cuts have been successfully merged pCut->pOne = pCut0; pCut->fCompl0 = pObj->fCompl0; pCut->pTwo = pCut1; pCut->fCompl1 = pObj->fCompl1; // pCut->Phase = ... - pCut->Delay = If_CutDelay( p, pCut ); - pCut->Flow = If_CutFlow( p, pCut ); + pCut->Area = (Mode == 2)? If_CutArea( p, pCut, 100 ) : If_CutFlow( p, pCut ); + p->nCutsMerged++; // prepare room for the next cut pCut = p->ppCuts[++p->nCuts]; } - // sort the cuts - if ( p->pPars->Mode == 1 ) // delay - qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelay ); - else - qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareArea ); + assert( p->nCuts > 0 ); + If_ManSortCuts( p, Mode ); // take the first - pObj->nCuts = IF_MIN( p->nCuts + 1, p->pPars->nCutsMax ); + pObj->nCuts = IF_MIN( p->nCuts + 1, p->nCutsUsed ); If_ObjForEachCutStart( pObj, pCut, i, 1 ) If_CutCopy( pCut, p->ppCuts[i-1] ); pObj->iCut = 1; -} - -/**Function************************************************************* - - Synopsis [Maps the nodes for delay.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManPerformMapping( If_Man_t * p ) -{ - If_Obj_t * pObj; - float DelayBest; - int i, clk = clock(); - // set arrival times and trivial cuts at const 1 and PIs - If_ManConst1(p)->Cuts[0].Delay = 0.0; - If_ManForEachPi( p, pObj, i ) - pObj->Cuts[0].Delay = p->pPars->pTimesArr[i]; - // set the initial fanout estimates - If_ManForEachObj( p, pObj, i ) - pObj->EstRefs = (float)pObj->nRefs; - // map the internal nodes - If_ManForEachNode( p, pObj, i ) - If_ObjPerformMapping( p, pObj ); - // get the best arrival time of the POs - DelayBest = If_ManDelayMax(p); - printf( "Best delay = %d. ", (int)DelayBest ); - PRT( "Time", clock() - clk ); - return 1; + assert( If_ObjCutBest(pObj)->nLeaves > 1 ); + // assign delay of the trivial cut + If_ObjCutTriv(pObj)->Delay = If_ObjCutBest(pObj)->Delay; +//printf( "%d %d ", pObj->Id, (int)If_ObjCutBest(pObj)->Delay ); +//printf( "%d %d ", pObj->Id, pObj->nCuts ); + // ref the selected cut + if ( Mode == 2 && pObj->nRefs > 0 ) + If_CutRef( p, If_ObjCutBest(pObj), 100 ); + // find the largest cut + if ( p->nCutsMax < pObj->nCuts ) + p->nCutsMax = pObj->nCuts; } //////////////////////////////////////////////////////////////////////// diff --git a/src/map/mapper/mapperCut.c b/src/map/mapper/mapperCut.c index 9dad07d0..91ef6562 100644 --- a/src/map/mapper/mapperCut.c +++ b/src/map/mapper/mapperCut.c @@ -612,7 +612,8 @@ int Map_CutMergeTwo( Map_Cut_t * pCut1, Map_Cut_t * pCut2, Map_Node_t * ppNodes[ { min = i; for ( k = i+1; k < nTotal; k++ ) - if ( ppNodes[k] < ppNodes[min] ) +// if ( ppNodes[k] < ppNodes[min] ) // reported bug fix (non-determinism!) + if ( ppNodes[k]->Num < ppNodes[min]->Num ) min = k; pNodeTemp = ppNodes[i]; ppNodes[i] = ppNodes[min]; |