From ae037e45038cca6f0b86abea50692399a03b01be Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 10 Dec 2006 08:01:00 -0800 Subject: Version abc61210 --- src/map/if/ifSeq.c | 357 ++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 300 insertions(+), 57 deletions(-) (limited to 'src/map/if/ifSeq.c') diff --git a/src/map/if/ifSeq.c b/src/map/if/ifSeq.c index ac2754c0..ddc74a49 100644 --- a/src/map/if/ifSeq.c +++ b/src/map/if/ifSeq.c @@ -24,9 +24,11 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static void If_ObjPerformMappingLI( If_Man_t * p, If_Obj_t * pLatch ); -static void If_ObjPerformMappingLO( If_Man_t * p, If_Obj_t * pLatch, If_Obj_t * pObj ); -static int If_ManMappingSeqConverged( If_Man_t * p ); +static int If_ManBinarySearchPeriod( If_Man_t * p, int Mode ); +static int If_ManBinarySearch_rec( If_Man_t * p, int Mode, int FiMin, int FiMax ); +static int If_ManPerformMappingRoundSeq( If_Man_t * p, int Mode, int nIter, char * pLabel ); +static int If_ManPrepareMappingSeq( If_Man_t * p ); +static int If_ObjPerformMappingLatch( If_Man_t * p, If_Obj_t * pObj ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// @@ -45,46 +47,100 @@ static int If_ManMappingSeqConverged( If_Man_t * p ); ***********************************************************************/ int If_ManPerformMappingSeq( If_Man_t * p ) { - If_Obj_t * pObj, * pLatch; - int i, clkTotal = clock(); - // set the number of cuts used + int PeriodBest, Mode = 0; + + // collect nodes in the sequential order + If_ManPrepareMappingSeq( p ); + + // perform combinational mapping to get the upper bound on the clock period + If_ManPerformMappingRound( p, 2, 0, 0, NULL ); + p->RequiredGlo = If_ManDelayMax( p, 0 ); + + // set parameters p->nCutsUsed = p->pPars->nCutsMax; - // 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 - p->pPars->fFancy = 1; - If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 0, NULL ); - p->pPars->fFancy = 0; - - // perform iterations over the circuit - while ( !If_ManMappingSeqConverged( p ) ) + p->nAttempts = 0; + p->nMaxIters = 50; + p->Period = (int)p->RequiredGlo; + + // make sure the clock period words + if ( !If_ManBinarySearchPeriod( p, Mode ) ) { - // assign cuts to latches - If_ManForEachLatch( p, pLatch, i ) - If_ObjPerformMappingLI( p, pLatch ); - // assign cuts to primary inputs - If_ManForEachLatch( p, pLatch, i ) - If_ObjPerformMappingLO( p, pLatch, If_ManPi(p, If_ManPiNum(p) - If_ManPoNum(p) + i) ); - // map the nodes - If_ManForEachNode( p, pObj, i ) - If_ObjPerformMapping( p, pObj, 0 ); + printf( "If_ManPerformMappingSeq(): The upper bound on the clock period cannot be computed.\n" ); + return 0; } - if ( p->pPars->fVerbose ) + // perform binary search + PeriodBest = If_ManBinarySearch_rec( p, Mode, 0, p->Period ); + + // recompute the best l-values + if ( p->Period != PeriodBest ) { - PRT( "Total time", clock() - clkTotal ); + p->Period = PeriodBest; + if ( !If_ManBinarySearchPeriod( p, Mode ) ) + { + printf( "If_ManPerformMappingSeq(): The final clock period cannot be confirmed.\n" ); + return 0; + } } +/* + // fix the problem with non-converged delays + If_ManForEachNode( p, pObj, i ) + if ( pObj->LValue < -ABC_INFINITY/2 ) + pObj->LValue = (float)0.0; + // write the retiming lags + p->vLags = Vec_IntStart( If_ManObjNum(p) + 1 ); + If_ManForEachNode( p, pObj, i ) + Vec_IntWriteEntry( vLags, i, Abc_NodeComputeLag(pObj->LValue, p->Period) ); +*/ +/* + // print the statistic into a file + { + FILE * pTable; + pTable = fopen( "a/seqmap__stats.txt", "a+" ); + fprintf( pTable, "%d ", p->Period ); + fprintf( pTable, "\n" ); + fclose( pTable ); + } +*/ + // print the result + if ( p->pPars->fLiftLeaves ) + { +// if ( p->pPars->fVerbose ) + printf( "The best clock period is %3d. (Currently, network is not modified, so mapping will fail.)\n", p->Period ); + return 0; + } +// if ( p->pPars->fVerbose ) + printf( "The best clock period is %3d.\n", p->Period ); return 1; } /**Function************************************************************* - Synopsis [Performs sequential mapping.] + Synopsis [Performs binary search for the optimal clock period.] + + Description [Assumes that FiMin is infeasible while FiMax is feasible.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_ManBinarySearch_rec( If_Man_t * p, int Mode, int FiMin, int FiMax ) +{ + assert( FiMin < FiMax ); + if ( FiMin + 1 == FiMax ) + return FiMax; + // compute the median + p->Period = FiMin + (FiMax - FiMin)/2; + if ( If_ManBinarySearchPeriod( p, Mode ) ) + return If_ManBinarySearch_rec( p, Mode, FiMin, p->Period ); // Median is feasible + else + return If_ManBinarySearch_rec( p, Mode, p->Period, FiMax ); // Median is infeasible +} + +/**Function************************************************************* + + Synopsis [Returns 1 if retiming with this clock period is feasible.] Description [] @@ -93,16 +149,153 @@ int If_ManPerformMappingSeq( If_Man_t * p ) SeeAlso [] ***********************************************************************/ -void If_CutLift( If_Cut_t * pCut ) +int If_ManBinarySearchPeriod( If_Man_t * p, int Mode ) { - unsigned i; - for ( i = 0; i < pCut->nLeaves; i++ ) - pCut->pLeaves[i] = ((pCut->pLeaves[i] >> 8) << 8) | ((pCut->pLeaves[i] & 255) + 1); + If_Obj_t * pObj; + int i, c, fConverged; + int fResetRefs = 0; + + p->nAttempts++; + + // set l-values of all nodes to be minus infinity, except PIs and constants + If_ManForEachObj( p, pObj, i ) + { + pObj->nCuts = 1; + If_ObjSetLValue( pObj, -IF_FLOAT_LARGE ); + if ( fResetRefs ) + pObj->nRefs = 0; + } + If_ObjSetLValue( If_ManConst1(p), (float)0.0 ); + If_ManForEachPi( p, pObj, i ) + If_ObjSetLValue( pObj, (float)0.0 ); + + // reset references to their original state + if ( fResetRefs ) + { + If_ManForEachObj( p, pObj, i ) + { + if ( If_ObjIsCo(pObj) ) + continue; + if ( pObj->pFanin0 ) pObj->pFanin0->nRefs++; + if ( pObj->pFanin1 ) pObj->pFanin1->nRefs++; + } + } + + // update all values iteratively + fConverged = 0; + for ( c = 1; c <= p->nMaxIters; c++ ) + { + if ( !If_ManPerformMappingRoundSeq( p, Mode, c, NULL ) ) + { + fConverged = 1; + break; + } + p->RequiredGlo = If_ManDelayMax( p, 1 ); + if ( p->RequiredGlo > p->Period + p->fEpsilon ) + break; + } + + // report the results + if ( p->pPars->fVerbose ) + { + p->AreaGlo = p->pPars->fLiftLeaves? If_ManScanMappingSeq(p) : If_ManScanMapping(p); + printf( "Attempt = %2d. Iters = %3d. Area = %10.2f. Fi = %6.2f. ", p->nAttempts, c, p->AreaGlo, (float)p->Period ); + if ( fConverged ) + printf( " Feasible" ); + else if ( c > p->nMaxIters ) + printf( "Infeasible (timeout)" ); + else + printf( "Infeasible" ); + printf( "\n" ); + } + return fConverged; } /**Function************************************************************* - Synopsis [Performs sequential mapping.] + Synopsis [Performs one pass of l-value computation over all nodes.] + + Description [Experimentally it was found that checking POs changes + is not enough to detect the convergence of l-values in the network.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_ManPerformMappingRoundSeq( If_Man_t * p, int Mode, int nIter, char * pLabel ) +{ + ProgressBar * pProgress; + If_Obj_t * pObj; + int i, clk = clock(); + int fVeryVerbose = 0; + int fChange = 0; + assert( Mode >= 0 && Mode <= 2 ); + if ( !p->pPars->fVerbose ) + pProgress = Extra_ProgressBarStart( stdout, If_ManObjNum(p) ); + // map the internal nodes + p->nCutsMerged = 0; + If_ManForEachNode( p, pObj, i ) + { + if ( !p->pPars->fVerbose ) + Extra_ProgressBarUpdate( pProgress, i, pLabel ); + // consider the camse of an AND gate + assert( If_ObjIsAnd(pObj) ); + If_ObjPerformMappingAnd( p, pObj, Mode ); + if ( pObj->fRepr ) + If_ObjPerformMappingChoice( p, pObj, Mode ); + // check if updating happens + if ( If_ObjLValue(pObj) < If_ObjCutBest(pObj)->Delay - p->fEpsilon ) + { + If_ObjSetLValue( pObj, If_ObjCutBest(pObj)->Delay ); + fChange = 1; + } +//if ( If_ObjLValue(pObj) > -1000.0 ) +//printf( "Node %d %.2f ", pObj->Id, If_ObjLValue(pObj) ); + } + if ( !p->pPars->fVerbose ) + Extra_ProgressBarStop( pProgress ); + // propagate arrival times from the registers + Vec_PtrForEachEntry( p->vLatchOrder, pObj, i ) + fChange |= If_ObjPerformMappingLatch( p, pObj ); +//printf( "\n\n" ); + // compute area and delay + if ( fVeryVerbose ) + { + p->RequiredGlo = If_ManDelayMax( p, 1 ); + p->AreaGlo = p->pPars->fLiftLeaves? If_ManScanMappingSeq(p) : If_ManScanMapping(p); + printf( "S%d: Fi = %6.2f. Del = %6.2f. Area = %8.2f. Cuts = %8d. Lim = %2d. Ave = %5.2f. ", + nIter, (float)p->Period, p->RequiredGlo, p->AreaGlo, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) ); + PRT( "T", clock() - clk ); + } + return fChange; +} + +/**Function************************************************************* + + Synopsis [Collects latches in the topological order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void If_ManCollectLatches_rec( If_Obj_t * pObj, Vec_Ptr_t * vLatches ) +{ + if ( !If_ObjIsLatch(pObj) ) + return; + if ( pObj->fMark ) + return; + pObj->fMark = 1; + If_ManCollectLatches_rec( pObj->pFanin0, vLatches ); + Vec_PtrPush( vLatches, pObj ); +} + +/**Function************************************************************* + + Synopsis [Collects latches in the topological order.] Description [] @@ -111,19 +304,25 @@ void If_CutLift( If_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -void If_ObjPerformMappingLI( If_Man_t * p, If_Obj_t * pLatch ) +Vec_Ptr_t * If_ManCollectLatches( If_Man_t * p ) { - If_Obj_t * pFanin; - int c; - assert( If_ObjIsPo(pLatch) ); - pFanin = If_ObjFanin0(pLatch); - for ( c = 0; c < pFanin->nCuts; c++ ) - If_CutCopy( pLatch->Cuts + c, pFanin->Cuts + c ); + Vec_Ptr_t * vLatches; + If_Obj_t * pObj; + int i; + // collect latches + vLatches = Vec_PtrAlloc( p->pPars->nLatches ); + Vec_PtrForEachEntryStart( p->vCis, pObj, i, If_ManCiNum(p) - p->pPars->nLatches ) + If_ManCollectLatches_rec( pObj, vLatches ); + // clean marks + Vec_PtrForEachEntry( vLatches, pObj, i ) + pObj->fMark = 0; + assert( Vec_PtrSize(vLatches) == p->pPars->nLatches ); + return vLatches; } /**Function************************************************************* - Synopsis [Performs sequential mapping.] + Synopsis [Prepares for sequential mapping by linking the latches.] Description [] @@ -132,23 +331,43 @@ void If_ObjPerformMappingLI( If_Man_t * p, If_Obj_t * pLatch ) SeeAlso [] ***********************************************************************/ -void If_ObjPerformMappingLO( If_Man_t * p, If_Obj_t * pLatch, If_Obj_t * pObj ) +int If_ManPrepareMappingSeq( If_Man_t * p ) { + If_Obj_t * pObj, * pObjLi, * pObjLo, * pTemp; If_Cut_t * pCut; - int c, Limit = IF_MIN( p->nCuts + 1, p->nCutsUsed ); - assert( If_ObjIsPo(pLatch) ); - for ( c = 1; c < Limit; c++ ) + int i; + // link the latch outputs (PIs) directly to the drivers of latch inputs (POs) + for ( i = 0; i < p->pPars->nLatches; i++ ) + { + pObjLo = If_ManCi( p, If_ManCiNum(p) - p->pPars->nLatches + i ); + pObjLi = If_ManCo( p, If_ManCoNum(p) - p->pPars->nLatches + i ); + pObjLo->pFanin0 = If_ObjFanin0( pObjLi ); + pObjLo->fCompl0 = If_ObjFaninC0( pObjLi ); +// pObjLo->pFanin0 = pObjLi; + } + // collect latches + p->vLatchOrder = If_ManCollectLatches( p ); + // propagate elementary cuts + if ( p->pPars->fLiftLeaves ) { - pCut = pObj->Cuts + c; - If_CutCopy( pCut, pLatch->Cuts + c - 1 ); - If_CutLift( pCut ); - pCut->Delay -= p->Fi; + Vec_PtrForEachEntry( p->vLatchOrder, pObj, i ) + { + pCut = If_ObjCutTriv(pObj); + If_CutCopy( pCut, If_ObjFanin0(pObj)->Cuts ); + If_CutLift( pCut ); + pCut->Delay -= p->Period; + pCut->fCompl ^= pObj->fCompl0; + + pTemp = If_ManObj(p, pCut->pLeaves[0] >> 8); + assert( !If_ObjIsLatch(pTemp) ); + } } + return 1; } /**Function************************************************************* - Synopsis [Performs sequential mapping.] + Synopsis [Performs mapping of the latches.] Description [] @@ -157,12 +376,36 @@ void If_ObjPerformMappingLO( If_Man_t * p, If_Obj_t * pLatch, If_Obj_t * pObj ) SeeAlso [] ***********************************************************************/ -int If_ManMappingSeqConverged( If_Man_t * p ) +int If_ObjPerformMappingLatch( If_Man_t * p, If_Obj_t * pObj ) { - return 0; + If_Obj_t * pFanin; + If_Cut_t * pCut; + float LValueOld; + int i; + assert( If_ObjIsLatch(pObj) ); + // save old l-value + LValueOld = If_ObjLValue(pObj); + pFanin = If_ObjFanin0(pObj); + assert( pFanin->nCuts > 0 ); + if ( !p->pPars->fLiftLeaves ) + { + pObj->nCuts = 1; + If_ObjSetLValue( pObj, If_ObjLValue(pFanin) - p->Period ); + } + else + { + pObj->nCuts = pFanin->nCuts; + If_ObjForEachCut( pObj, pCut, i ) + { + If_CutCopy( pCut, pFanin->Cuts + i ); + If_CutLift( pCut ); + pCut->Delay -= p->Period; + pCut->fCompl ^= pObj->fCompl0; + } + } + return LValueOld != If_ObjLValue(pObj); } - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -- cgit v1.2.3