src/map/if/ifSeq.c File Reference

#include "if.h"
Include dependency graph for ifSeq.c:

Go to the source code of this file.

Functions

void If_ManPrepareMappingSeq (If_Man_t *p)
void If_ManCollectLatches_rec (If_Obj_t *pObj, Vec_Ptr_t *vLatches)
Vec_Ptr_t * If_ManCollectLatches (If_Man_t *p)
int If_ManPerformMappingRoundSeq (If_Man_t *p, int nIter)
int If_ManBinarySearchPeriod (If_Man_t *p)
int If_ManBinarySearch_rec (If_Man_t *p, int FiMin, int FiMax)
void If_ManPerformMappingSeqPost (If_Man_t *p)
int If_ManPerformMappingSeq (If_Man_t *p)

Variables

int s_MappingTime

Function Documentation

int If_ManBinarySearch_rec ( If_Man_t *  p,
int  FiMin,
int  FiMax 
)

Function*************************************************************

Synopsis [Performs binary search for the optimal clock period.]

Description [Assumes that FiMin is infeasible while FiMax is feasible.]

SideEffects []

SeeAlso []

Definition at line 253 of file ifSeq.c.

00254 {
00255     assert( FiMin < FiMax );
00256     if ( FiMin + 1 == FiMax )
00257         return FiMax;
00258     // compute the median
00259     p->Period = FiMin + (FiMax - FiMin)/2;
00260     if ( If_ManBinarySearchPeriod( p ) )
00261         return If_ManBinarySearch_rec( p, FiMin, p->Period ); // Median is feasible
00262     else 
00263         return If_ManBinarySearch_rec( p, p->Period, FiMax ); // Median is infeasible
00264 }

int If_ManBinarySearchPeriod ( If_Man_t *  p  ) 

Function*************************************************************

Synopsis [Returns 1 if retiming with this clock period is feasible.]

Description []

SideEffects []

SeeAlso []

Definition at line 183 of file ifSeq.c.

00184 {
00185     If_Obj_t * pObj;
00186     int i, c, fConverged;
00187     int fResetRefs = 0;
00188 
00189     p->nAttempts++;
00190 
00191     // reset initial LValues (PIs to 0; others to -inf)
00192     If_ManForEachObj( p, pObj, i )
00193     {
00194         if ( If_ObjIsPi(pObj) || If_ObjIsConst1(pObj) )
00195         {
00196             If_ObjSetLValue( pObj, (float)0.0 );
00197             If_ObjSetArrTime( pObj, (float)0.0 );
00198         }
00199         else
00200         {
00201             If_ObjSetLValue( pObj, (float)-IF_INFINITY );
00202             If_ObjSetArrTime( pObj, (float)-IF_INFINITY );
00203         }
00204         // undo any previous mapping, except for CIs
00205         if ( If_ObjIsAnd(pObj) )
00206             If_ObjCutBest(pObj)->nLeaves = 0;
00207     }
00208 
00209     // update all values iteratively
00210     fConverged = 0;
00211     for ( c = 1; c <= p->nMaxIters; c++ )
00212     {
00213         if ( !If_ManPerformMappingRoundSeq( p, c ) )
00214         {
00215             p->RequiredGlo = If_ManDelayMax( p, 1 );
00216             fConverged = 1;
00217             break;
00218         }
00219         p->RequiredGlo = If_ManDelayMax( p, 1 );
00220 //printf( "Global = %d \n", (int)p->RequiredGlo );
00221         if ( p->RequiredGlo > p->Period + p->fEpsilon )
00222             break; 
00223     }
00224 
00225     // report the results
00226     if ( p->pPars->fVerbose )
00227     {
00228         p->AreaGlo = If_ManScanMapping(p);
00229         printf( "Attempt = %2d.  Iters = %3d.  Area = %10.2f.  Fi = %6.2f.  ", p->nAttempts, c, p->AreaGlo, (float)p->Period );
00230         if ( fConverged )
00231             printf( "  Feasible" );
00232         else if ( c > p->nMaxIters )
00233             printf( "Infeasible (timeout)" );
00234         else
00235             printf( "Infeasible" );
00236         printf( "\n" );
00237     }
00238     return fConverged;
00239 }

Vec_Ptr_t* If_ManCollectLatches ( If_Man_t *  p  ) 

Function*************************************************************

Synopsis [Collects latches in the topological order.]

Description []

SideEffects []

SeeAlso []

Definition at line 92 of file ifSeq.c.

00093 {
00094     Vec_Ptr_t * vLatches;
00095     If_Obj_t * pObj;
00096     int i;
00097     // collect latches 
00098     vLatches = Vec_PtrAlloc( p->pPars->nLatches );
00099     If_ManForEachLatchOutput( p, pObj, i )
00100         If_ManCollectLatches_rec( pObj, vLatches );
00101     // clean marks
00102     Vec_PtrForEachEntry( vLatches, pObj, i )
00103         pObj->fMark = 0;
00104     assert( Vec_PtrSize(vLatches) == p->pPars->nLatches );
00105     return vLatches;
00106 }

void If_ManCollectLatches_rec ( If_Obj_t *  pObj,
Vec_Ptr_t *  vLatches 
)

Function*************************************************************

Synopsis [Collects latches in the topological order.]

Description []

SideEffects []

SeeAlso []

Definition at line 70 of file ifSeq.c.

00071 {
00072     if ( !If_ObjIsLatch(pObj) )
00073         return;
00074     if ( pObj->fMark )
00075         return;
00076     pObj->fMark = 1;
00077     If_ManCollectLatches_rec( pObj->pFanin0, vLatches );
00078     Vec_PtrPush( vLatches, pObj );
00079 }

int If_ManPerformMappingRoundSeq ( If_Man_t *  p,
int  nIter 
)

Function*************************************************************

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 []

Definition at line 120 of file ifSeq.c.

00121 {
00122     If_Obj_t * pObj;
00123     int i, clk = clock();
00124     int fVeryVerbose = 0;
00125     int fChange = 0;
00126 
00127     // map the internal nodes
00128     p->nCutsMerged = 0;
00129     If_ManForEachNode( p, pObj, i )
00130     {
00131         If_ObjPerformMappingAnd( p, pObj, 0, 0 );
00132         if ( pObj->fRepr )
00133             If_ObjPerformMappingChoice( p, pObj, 0, 0 );
00134     }
00135 
00136     // postprocess the mapping
00137 //printf( "Itereation %d: \n", nIter );
00138     If_ManForEachNode( p, pObj, i )
00139     {
00140         // update the LValues stored separately
00141         if ( If_ObjLValue(pObj) < If_ObjCutBest(pObj)->Delay - p->fEpsilon )
00142         {
00143             If_ObjSetLValue( pObj, If_ObjCutBest(pObj)->Delay );
00144             fChange = 1;
00145         }
00146 //printf( "%d ", (int)If_ObjLValue(pObj) );
00147         // reset the visit counters
00148         assert( pObj->nVisits == 0 );
00149         pObj->nVisits = pObj->nVisitsCopy;
00150     }
00151 //printf( "\n" );
00152 
00153     // propagate LValues over the registers
00154     Vec_PtrForEachEntry( p->vLatchOrder, pObj, i )
00155     {
00156         If_ObjSetLValue( pObj, If_ObjLValue(If_ObjFanin0(pObj)) - p->Period );
00157         If_ObjSetArrTime( pObj, If_ObjLValue(pObj) );
00158     }
00159 
00160     // compute area and delay
00161     if ( fVeryVerbose )
00162     {
00163         p->RequiredGlo = If_ManDelayMax( p, 1 );
00164         p->AreaGlo = If_ManScanMapping(p);
00165         printf( "S%d:  Fi = %6.2f. Del = %6.2f. Area = %8.2f. Cuts = %8d. ", 
00166              nIter, (float)p->Period, p->RequiredGlo, p->AreaGlo, p->nCutsMerged );
00167         PRT( "T", clock() - clk );
00168     }
00169     return fChange;
00170 }

int If_ManPerformMappingSeq ( If_Man_t *  p  ) 

Function*************************************************************

Synopsis [Performs sequential mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 332 of file ifSeq.c.

00333 {
00334     int clkTotal = clock();
00335     int PeriodBest;
00336 
00337     p->SortMode = 0;
00338 
00339     // perform combinational mapping to get the upper bound on the clock period
00340     If_ManPerformMappingRound( p, 1, 0, 0, NULL );
00341     p->RequiredGlo = If_ManDelayMax( p, 0 );
00342     p->RequiredGlo2 = p->RequiredGlo;
00343 
00344     // set direct linking of latches with their inputs
00345     If_ManPrepareMappingSeq( p );
00346 
00347     // collect latches
00348     p->vLatchOrder = If_ManCollectLatches( p );
00349 
00350     // set parameters
00351     p->nCutsUsed = p->pPars->nCutsMax;
00352     p->nAttempts = 0;
00353     p->nMaxIters = 50;
00354     p->Period    = (int)p->RequiredGlo;
00355 
00356     // make sure the clock period works
00357     if ( !If_ManBinarySearchPeriod( p ) )
00358     {
00359         printf( "If_ManPerformMappingSeq(): The upper bound on the clock period cannot be computed.\n" );
00360         return 0;
00361     }
00362 
00363     // perform binary search
00364     PeriodBest = If_ManBinarySearch_rec( p, 0, p->Period );
00365 
00366     // recompute the best l-values
00367     if ( p->Period != PeriodBest )
00368     {
00369         p->Period = PeriodBest;
00370         if ( !If_ManBinarySearchPeriod( p ) )
00371         {
00372             printf( "If_ManPerformMappingSeq(): The final clock period cannot be confirmed.\n" );
00373             return 0;
00374         }
00375     }
00376     if ( p->pPars->fVerbose )
00377     {
00378 /*
00379         {
00380             FILE * pTable;
00381             pTable = fopen( "iscas/stats_new.txt", "a+" );
00382 //            fprintf( pTable, "%s ",  pNtk->pName );
00383             fprintf( pTable, "%d ", p->Period );
00384     //        fprintf( pTable, "%.2f ", (float)(s_MappingMem)/(float)(1<<20) );
00385 //            fprintf( pTable, "%.2f", (float)(s_MappingTime)/(float)(CLOCKS_PER_SEC) );
00386 //            fprintf( pTable, "\n" );
00387             fclose( pTable );
00388         }
00389 */
00390         printf( "The best clock period is %3d.  ", p->Period );
00391         PRT( "Sequential time", clock() - clkTotal );
00392     }
00393     p->RequiredGlo = (float)PeriodBest;
00394 
00395     // postprocess it using combinational mapping
00396     If_ManPerformMappingSeqPost( p );
00397     s_MappingTime = clock() - clkTotal;
00398     return 1;
00399 }

void If_ManPerformMappingSeqPost ( If_Man_t *  p  ) 

Function*************************************************************

Synopsis [Performs sequential mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 277 of file ifSeq.c.

00278 {
00279     If_Obj_t * pObjLi, * pObjLo, * pObj;
00280     int i;
00281 
00282     // link the latch outputs (CIs) directly to the drivers of latch inputs (COs)
00283     for ( i = 0; i < p->pPars->nLatches; i++ )
00284     {
00285         pObjLi = If_ManLi( p, i );
00286         pObjLo = If_ManLo( p, i );
00287 //        printf( "%3d : %2d -> %2d   \n", i, 
00288 //            (int)If_ObjLValue(If_ObjFanin0(pObjLo)), (int)If_ObjLValue(pObjLo) );
00289     }
00290 
00291     // set arrival times
00292     assert( p->pPars->pTimesArr != NULL );
00293     If_ManForEachLatchOutput( p, pObjLo, i )
00294         p->pPars->pTimesArr[i] = If_ObjLValue(pObjLo);
00295 
00296     // set the required times
00297     assert( p->pPars->pTimesReq == NULL );
00298     p->pPars->pTimesReq = ALLOC( float, If_ManCoNum(p) );
00299     If_ManForEachPo( p, pObj, i )
00300     {
00301         p->pPars->pTimesReq[i] = p->RequiredGlo2;
00302 //        printf( "Out %3d : %2d   \n", i, (int)p->pPars->pTimesReq[i] );
00303     }
00304     If_ManForEachLatchInput( p, pObjLi, i )
00305     {
00306         p->pPars->pTimesReq[i] = If_ObjLValue(If_ObjFanin0(pObjLi));
00307 //        printf( "Out %3d : %2d   \n", i, (int)p->pPars->pTimesReq[i] );
00308     }
00309 
00310     // undo previous mapping
00311     If_ManForEachObj( p, pObj, i )
00312         if ( If_ObjIsAnd(pObj) )
00313             If_ObjCutBest(pObj)->nLeaves = 0;
00314 
00315     // map again combinationally
00316     p->pPars->fSeqMap = 0;
00317     If_ManPerformMappingComb( p );
00318     p->pPars->fSeqMap = 1;
00319 }

void If_ManPrepareMappingSeq ( If_Man_t *  p  ) 

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Prepares for sequential mapping by linking the latches.]

Description []

SideEffects []

SeeAlso []

Definition at line 44 of file ifSeq.c.

00045 {
00046     If_Obj_t * pObjLi, * pObjLo;
00047     int i;
00048 
00049     // link the latch outputs (CIs) directly to the drivers of latch inputs (COs)
00050     for ( i = 0; i < p->pPars->nLatches; i++ )
00051     {
00052         pObjLi = If_ManLi( p, i );
00053         pObjLo = If_ManLo( p, i );
00054         pObjLo->pFanin0 = If_ObjFanin0( pObjLi );
00055         pObjLo->fCompl0 = If_ObjFaninC0( pObjLi );
00056     }
00057 }

Variable Documentation

int s_MappingTime

CFile****************************************************************

FileName [ifSeq.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [FPGA mapping based on priority cuts.]

Synopsis [Sequential mapping.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - November 21, 2006.]

Revision [

Id
ifSeq.c,v 1.00 2006/11/21 00:00:00 alanmi Exp

] DECLARATIONS ///

CFile****************************************************************

FileName [abcPrint.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Printing statistics.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id
abcPrint.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

] DECLARATIONS ///

Definition at line 34 of file abcPrint.c.

Generated on Tue Jan 5 12:19:04 2010 for abc70930 by  doxygen 1.6.1