From 9206e6ff80e56c810814a9b9f61e45be8c4c4987 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 8 Oct 2012 21:20:13 -0700 Subject: Improvements to gate sizing. --- abclib.dsp | 8 ++ src/map/scl/module.make | 1 + src/map/scl/scl.c | 53 +++++-- src/map/scl/sclGsize.c | 54 ++++++++ src/map/scl/sclInt.h | 50 +++---- src/map/scl/sclLoad.c | 94 ++++++++----- src/map/scl/sclMan.h | 99 ++++++++++--- src/map/scl/sclSize.c | 13 +- src/map/scl/sclTime.c | 51 ++++--- src/map/scl/sclUpsize.c | 329 +++++++++++++++++++++++++++++++------------ src/map/scl/sclUtil.c | 1 + src/misc/vec/vecQue.h | 360 ++++++++++++++++++++++++++++++++++++++++++++++++ 12 files changed, 910 insertions(+), 203 deletions(-) create mode 100644 src/map/scl/sclGsize.c create mode 100644 src/misc/vec/vecQue.h diff --git a/abclib.dsp b/abclib.dsp index b500a687..c729baa9 100644 --- a/abclib.dsp +++ b/abclib.dsp @@ -2391,6 +2391,10 @@ SOURCE=.\src\map\scl\sclFile.c # End Source File # Begin Source File +SOURCE=.\src\map\scl\sclGsize.c +# End Source File +# Begin Source File + SOURCE=.\src\map\scl\sclInt.h # End Source File # Begin Source File @@ -2627,6 +2631,10 @@ SOURCE=.\src\misc\vec\vecPtr.h # End Source File # Begin Source File +SOURCE=.\src\misc\vec\vecQue.h +# End Source File +# Begin Source File + SOURCE=.\src\misc\vec\vecSet.h # End Source File # Begin Source File diff --git a/src/map/scl/module.make b/src/map/scl/module.make index 7ba331de..dbf63a99 100644 --- a/src/map/scl/module.make +++ b/src/map/scl/module.make @@ -1,6 +1,7 @@ SRC += src/map/scl/scl.c \ src/map/scl/sclBuff.c \ src/map/scl/sclFile.c \ + src/map/scl/sclGsize.c \ src/map/scl/sclLoad.c \ src/map/scl/sclSize.c \ src/map/scl/sclTime.c \ diff --git a/src/map/scl/scl.c b/src/map/scl/scl.c index f5c9d914..dfdc000d 100644 --- a/src/map/scl/scl.c +++ b/src/map/scl/scl.c @@ -644,15 +644,29 @@ usage: int Scl_CommandUpsize( Abc_Frame_t * pAbc, int argc, char **argv ) { Abc_Ntk_t * pNtk = Abc_FrameReadNtk(pAbc); - int Window = 2; - int Ratio = 10; - int nIters = 100; + int nIters = 300; + int Window = 2; + int Ratio = 10; + int Notches = 10; + int TimeOut = 0; int c, fVerbose = 0; + int fVeryVerbose = 0; Extra_UtilGetoptReset(); - while ( ( c = Extra_UtilGetopt( argc, argv, "WRIvh" ) ) != EOF ) + while ( ( c = Extra_UtilGetopt( argc, argv, "IWRNTvwh" ) ) != EOF ) { switch ( c ) { + case 'I': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-I\" should be followed by a positive integer.\n" ); + goto usage; + } + nIters = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nIters < 0 ) + goto usage; + break; case 'W': if ( globalUtilOptind >= argc ) { @@ -675,20 +689,34 @@ int Scl_CommandUpsize( Abc_Frame_t * pAbc, int argc, char **argv ) if ( Ratio < 0 ) goto usage; break; - case 'I': + case 'N': if ( globalUtilOptind >= argc ) { - Abc_Print( -1, "Command line switch \"-I\" should be followed by a positive integer.\n" ); + Abc_Print( -1, "Command line switch \"-N\" should be followed by a positive integer.\n" ); goto usage; } - nIters = atoi(argv[globalUtilOptind]); + Notches = atoi(argv[globalUtilOptind]); globalUtilOptind++; - if ( nIters < 0 ) + if ( Notches < 0 ) + goto usage; + break; + case 'T': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-T\" should be followed by a positive integer.\n" ); + goto usage; + } + TimeOut = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( TimeOut < 0 ) goto usage; break; case 'v': fVerbose ^= 1; break; + case 'w': + fVeryVerbose ^= 1; + break; case 'h': goto usage; default: @@ -717,16 +745,19 @@ int Scl_CommandUpsize( Abc_Frame_t * pAbc, int argc, char **argv ) return 1; } - Abc_SclUpsizePerform( (SC_Lib *)pAbc->pLibScl, pNtk, Window, Ratio, nIters, fVerbose ); + Abc_SclUpsizePerform( (SC_Lib *)pAbc->pLibScl, pNtk, nIters, Window, Ratio, Notches, TimeOut, fVerbose, fVeryVerbose ); return 0; usage: - fprintf( pAbc->Err, "usage: upsize [-WRI num] [-vh]\n" ); + fprintf( pAbc->Err, "usage: upsize [-IWRNT num] [-vwh]\n" ); fprintf( pAbc->Err, "\t selectively increases gate sizes in timing-critical regions\n" ); + fprintf( pAbc->Err, "\t-I : the number of upsizing iterations to perform [default = %d]\n", nIters ); fprintf( pAbc->Err, "\t-W : delay window (in percents) of near-critical COs [default = %d]\n", Window ); fprintf( pAbc->Err, "\t-R : ratio of critical nodes (in percents) to update [default = %d]\n", Ratio ); - fprintf( pAbc->Err, "\t-I : the number of upsizing iterations to perform [default = %d]\n", nIters ); + fprintf( pAbc->Err, "\t-N : limit on discrete upsizing steps at a node [default = %d]\n", Notches ); + fprintf( pAbc->Err, "\t-T : approximate timeout in seconds [default = %d]\n", TimeOut ); fprintf( pAbc->Err, "\t-v : toggle printing verbose information [default = %s]\n", fVerbose? "yes": "no" ); + fprintf( pAbc->Err, "\t-w : toggle printing more verbose information [default = %s]\n", fVeryVerbose? "yes": "no" ); fprintf( pAbc->Err, "\t-h : print the command usage\n"); return 1; } diff --git a/src/map/scl/sclGsize.c b/src/map/scl/sclGsize.c new file mode 100644 index 00000000..0e840f8b --- /dev/null +++ b/src/map/scl/sclGsize.c @@ -0,0 +1,54 @@ +/**CFile**************************************************************** + + FileName [sclGsize.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Standard-cell library representation.] + + Synopsis [Selective increase of gate sizes.] + + Author [Alan Mishchenko, Niklas Een] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - August 24, 2012.] + + Revision [$Id: sclGsize.c,v 1.0 2012/08/24 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "sclInt.h" +#include "sclMan.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/map/scl/sclInt.h b/src/map/scl/sclInt.h index 9474e24d..e65d1702 100644 --- a/src/map/scl/sclInt.h +++ b/src/map/scl/sclInt.h @@ -423,30 +423,32 @@ static inline void Abc_SclLibFree( SC_Lib * p ) } -/*=== sclBuff.c =============================================================*/ -extern int Abc_SclCheckNtk( Abc_Ntk_t * p, int fVerbose ); -extern Abc_Ntk_t * Abc_SclPerformBuffering( Abc_Ntk_t * p, int Degree, int fVerbose ); -/*=== sclFile.c =============================================================*/ -extern SC_Lib * Abc_SclRead( char * pFileName ); -extern void Abc_SclWrite( char * pFileName, SC_Lib * p ); -extern void Abc_SclWriteText( char * pFileName, SC_Lib * p ); -extern void Abc_SclLoad( char * pFileName, SC_Lib ** ppScl ); -extern void Abc_SclSave( char * pFileName, SC_Lib * pScl ); -/*=== sclTime.c =============================================================*/ -extern void Abc_SclTimePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int fUseWireLoads, int fShowAll, int fShort ); -/*=== sclSize.c =============================================================*/ -extern void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * p ); -/*=== sclUpsize.c =============================================================*/ -extern void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int Window, int Ratio, int nIters, int fVerbose ); -/*=== sclUtil.c =============================================================*/ -extern void Abc_SclHashCells( SC_Lib * p ); -extern int Abc_SclCellFind( SC_Lib * p, char * pName ); -extern void Abc_SclLinkCells( SC_Lib * p ); -extern void Abc_SclPrintCells( SC_Lib * p ); -extern Vec_Int_t * Abc_SclManFindGates( SC_Lib * pLib, Abc_Ntk_t * p ); -extern void Abc_SclManSetGates( SC_Lib * pLib, Abc_Ntk_t * p, Vec_Int_t * vGates ); -extern void Abc_SclPrintGateSizes( SC_Lib * pLib, Abc_Ntk_t * p ); -extern void Abc_SclMinsizePerform( SC_Lib * pLib, Abc_Ntk_t * p, int fVerbose ); +/*=== sclBuff.c ===============================================================*/ +extern int Abc_SclCheckNtk( Abc_Ntk_t * p, int fVerbose ); +extern Abc_Ntk_t * Abc_SclPerformBuffering( Abc_Ntk_t * p, int Degree, int fVerbose ); +/*=== sclFile.c ===============================================================*/ +extern SC_Lib * Abc_SclRead( char * pFileName ); +extern void Abc_SclWrite( char * pFileName, SC_Lib * p ); +extern void Abc_SclWriteText( char * pFileName, SC_Lib * p ); +extern void Abc_SclLoad( char * pFileName, SC_Lib ** ppScl ); +extern void Abc_SclSave( char * pFileName, SC_Lib * pScl ); +/*=== sclLoad.c ===============================================================*/ +extern SC_WireLoad * Abc_SclFindWireLoadModel( SC_Lib * p, float Area ); +/*=== sclTime.c ===============================================================*/ +extern void Abc_SclTimePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int fUseWireLoads, int fShowAll, int fShort ); +/*=== sclSize.c ===============================================================*/ +extern void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * p ); +/*=== sclUpsize.c ===============================================================*/ +extern void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nIters, int Window, int Ratio, int Notches, int TimeOut, int fVerbose, int fVeryVerbose ); +/*=== sclUtil.c ===============================================================*/ +extern void Abc_SclHashCells( SC_Lib * p ); +extern int Abc_SclCellFind( SC_Lib * p, char * pName ); +extern void Abc_SclLinkCells( SC_Lib * p ); +extern void Abc_SclPrintCells( SC_Lib * p ); +extern Vec_Int_t * Abc_SclManFindGates( SC_Lib * pLib, Abc_Ntk_t * p ); +extern void Abc_SclManSetGates( SC_Lib * pLib, Abc_Ntk_t * p, Vec_Int_t * vGates ); +extern void Abc_SclPrintGateSizes( SC_Lib * pLib, Abc_Ntk_t * p ); +extern void Abc_SclMinsizePerform( SC_Lib * pLib, Abc_Ntk_t * p, int fVerbose ); ABC_NAMESPACE_HEADER_END diff --git a/src/map/scl/sclLoad.c b/src/map/scl/sclLoad.c index 0ad3a405..fc48aa82 100644 --- a/src/map/scl/sclLoad.c +++ b/src/map/scl/sclLoad.c @@ -34,7 +34,7 @@ ABC_NAMESPACE_IMPL_START /**Function************************************************************* - Synopsis [Returns estimated wire capacitances for each fanout count.] + Synopsis [Returns the wireload model for the given area.] Description [] @@ -43,52 +43,69 @@ ABC_NAMESPACE_IMPL_START SeeAlso [] ***********************************************************************/ -Vec_Flt_t * Abc_SclFindWireCaps( SC_Man * p ) +SC_WireLoad * Abc_SclFindWireLoadModel( SC_Lib * p, float Area ) { - Vec_Flt_t * vCaps = NULL; SC_WireLoad * pWL = NULL; - int i, Entry, EntryMax; - float EntryPrev, EntryCur; - p->pWLoadUsed = NULL; - if ( p->pLib->default_wire_load_sel && strlen(p->pLib->default_wire_load_sel) ) + char * pWLoadUsed = NULL; + int i; + if ( p->default_wire_load_sel && strlen(p->default_wire_load_sel) ) { - float Area; SC_WireLoadSel * pWLS = NULL; - SC_LibForEachWireLoadSel( p->pLib, pWLS, i ) - if ( !strcmp(pWLS->pName, p->pLib->default_wire_load_sel) ) + SC_LibForEachWireLoadSel( p, pWLS, i ) + if ( !strcmp(pWLS->pName, p->default_wire_load_sel) ) break; - if ( i == Vec_PtrSize(p->pLib->vWireLoadSels) ) + if ( i == Vec_PtrSize(p->vWireLoadSels) ) { - Abc_Print( -1, "Cannot find wire load selection model \"%s\".\n", p->pLib->default_wire_load_sel ); + Abc_Print( -1, "Cannot find wire load selection model \"%s\".\n", p->default_wire_load_sel ); exit(1); } - Area = (float)Abc_SclGetTotalArea( p ); for ( i = 0; i < Vec_FltSize(pWLS->vAreaFrom); i++) if ( Area >= Vec_FltEntry(pWLS->vAreaFrom, i) && Area < Vec_FltEntry(pWLS->vAreaTo, i) ) { - p->pWLoadUsed = (char *)Vec_PtrEntry(pWLS->vWireLoadModel, i); + pWLoadUsed = (char *)Vec_PtrEntry(pWLS->vWireLoadModel, i); break; } if ( i == Vec_FltSize(pWLS->vAreaFrom) ) - p->pWLoadUsed = (char *)Vec_PtrEntryLast(pWLS->vWireLoadModel); + pWLoadUsed = (char *)Vec_PtrEntryLast(pWLS->vWireLoadModel); } - else if ( p->pLib->default_wire_load && strlen(p->pLib->default_wire_load) ) - p->pWLoadUsed = p->pLib->default_wire_load; + else if ( p->default_wire_load && strlen(p->default_wire_load) ) + pWLoadUsed = p->default_wire_load; else { Abc_Print( 0, "No wire model given.\n" ); return NULL; } // Get the actual table and reformat it for 'wire_cap' output: - assert( p->pWLoadUsed != NULL ); - SC_LibForEachWireLoad( p->pLib, pWL, i ) - if ( !strcmp(pWL->pName, p->pWLoadUsed) ) + assert( pWLoadUsed != NULL ); + SC_LibForEachWireLoad( p, pWL, i ) + if ( !strcmp(pWL->pName, pWLoadUsed) ) break; - if ( i == Vec_PtrSize(p->pLib->vWireLoads) ) + if ( i == Vec_PtrSize(p->vWireLoads) ) { - Abc_Print( -1, "Cannot find wire load model \"%s\".\n", p->pWLoadUsed ); + Abc_Print( -1, "Cannot find wire load model \"%s\".\n", pWLoadUsed ); exit(1); } +// printf( "Using wireload model \"%s\".\n", pWL->pName ); + return pWL; +} + +/**Function************************************************************* + + Synopsis [Returns estimated wire capacitances for each fanout count.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Flt_t * Abc_SclFindWireCaps( SC_Man * p, SC_WireLoad * pWL ) +{ + Vec_Flt_t * vCaps = NULL; + float EntryPrev, EntryCur; + int i, Entry, EntryMax; + assert( pWL != NULL ); // find the biggest fanout EntryMax = 0; Vec_IntForEachEntry( pWL->vFanout, Entry, i ) @@ -111,7 +128,7 @@ Vec_Flt_t * Abc_SclFindWireCaps( SC_Man * p ) /**Function************************************************************* - Synopsis [Computes/updates load for all nodes in the network.] + Synopsis [Computes load for all nodes in the network.] Description [] @@ -143,22 +160,31 @@ void Abc_SclComputeLoad( SC_Man * p ) pLoad->fall += pPin->fall_cap; } } - if ( !p->fUseWireLoads ) + if ( p->pWLoadUsed == NULL ) return; // add wire load - vWireCaps = Abc_SclFindWireCaps( p ); - if ( vWireCaps ) + vWireCaps = Abc_SclFindWireCaps( p, p->pWLoadUsed ); + Abc_NtkForEachNode1( p->pNtk, pObj, i ) { - Abc_NtkForEachNode1( p->pNtk, pObj, i ) - { - SC_Pair * pLoad = Abc_SclObjLoad( p, pObj ); - k = Abc_MinInt( Vec_FltSize(vWireCaps)-1, Abc_ObjFanoutNum(pObj) ); - pLoad->rise += Vec_FltEntry(vWireCaps, k); - pLoad->fall += Vec_FltEntry(vWireCaps, k); - } - Vec_FltFree( vWireCaps ); + SC_Pair * pLoad = Abc_SclObjLoad( p, pObj ); + k = Abc_MinInt( Vec_FltSize(vWireCaps)-1, Abc_ObjFanoutNum(pObj) ); + pLoad->rise += Vec_FltEntry(vWireCaps, k); + pLoad->fall += Vec_FltEntry(vWireCaps, k); } + Vec_FltFree( vWireCaps ); } + +/**Function************************************************************* + + Synopsis [Updates load of the node's fanins.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ void Abc_SclUpdateLoad( SC_Man * p, Abc_Obj_t * pObj, SC_Cell * pOld, SC_Cell * pNew ) { Abc_Obj_t * pFanin; diff --git a/src/map/scl/sclMan.h b/src/map/scl/sclMan.h index 700dc2bc..f1566ad0 100644 --- a/src/map/scl/sclMan.h +++ b/src/map/scl/sclMan.h @@ -26,6 +26,8 @@ /// INCLUDES /// //////////////////////////////////////////////////////////////////////// +#include "misc/vec/vecQue.h" + ABC_NAMESPACE_HEADER_START //////////////////////////////////////////////////////////////////////// @@ -49,21 +51,33 @@ struct SC_Man_ { SC_Lib * pLib; // library Abc_Ntk_t * pNtk; // network - int fUseWireLoads; // set to 1 if wireloads are used int nObjs; // allocated size + // get assignment Vec_Int_t * vGates; // mapping of objId into gateId + Vec_Int_t * vGatesBest; // best gate sizes found so far + Vec_Int_t * vUpdates; // sizing updates in this round + // timing information SC_Pair * pLoads; // loads for each gate + SC_Pair * pLoads2; // loads for each gate SC_Pair * pDepts; // departures for each gate SC_Pair * pTimes; // arrivals for each gate SC_Pair * pSlews; // slews for each gate SC_Pair * pTimes2; // arrivals for each gate SC_Pair * pSlews2; // slews for each gate - char * pWLoadUsed; // name of the used WireLoad model - clock_t clkStart; // starting time + Vec_Flt_t * vTimesOut; // output arrival times + Vec_Que_t * vQue; // outputs by their time + SC_WireLoad * pWLoadUsed; // name of the used WireLoad model float SumArea; // total area float MaxDelay; // max delay float SumArea0; // total area at the begining float MaxDelay0; // max delay at the begining + float BestDelay; // best delay in the middle + // runtime statistics + clock_t timeTotal; // starting/total time + clock_t timeCone; // critical path selection + clock_t timeSize; // incremental sizing + clock_t timeTime; // timing update + clock_t timeOther; // everything else }; //////////////////////////////////////////////////////////////////////// @@ -78,6 +92,7 @@ static inline SC_Cell * Abc_SclObjCell( SC_Man * p, Abc_Obj_t * pObj ) static inline void Abc_SclObjSetCell( SC_Man * p, Abc_Obj_t * pObj, SC_Cell * pCell ) { Vec_IntWriteEntry( p->vGates, Abc_ObjId(pObj), pCell->Id ); } static inline SC_Pair * Abc_SclObjLoad( SC_Man * p, Abc_Obj_t * pObj ) { return p->pLoads + Abc_ObjId(pObj); } +static inline SC_Pair * Abc_SclObjLoad2( SC_Man * p, Abc_Obj_t * pObj ) { return p->pLoads2 + Abc_ObjId(pObj); } static inline SC_Pair * Abc_SclObjDept( SC_Man * p, Abc_Obj_t * pObj ) { return p->pDepts + Abc_ObjId(pObj); } static inline SC_Pair * Abc_SclObjTime( SC_Man * p, Abc_Obj_t * pObj ) { return p->pTimes + Abc_ObjId(pObj); } static inline SC_Pair * Abc_SclObjSlew( SC_Man * p, Abc_Obj_t * pObj ) { return p->pSlews + Abc_ObjId(pObj); } @@ -113,24 +128,38 @@ static inline double Abc_SclObjSlewPs( SC_Man * p, Abc_Obj_t * pObj, int fRis static inline SC_Man * Abc_SclManAlloc( SC_Lib * pLib, Abc_Ntk_t * pNtk ) { SC_Man * p; + int i; assert( Abc_NtkHasMapping(pNtk) ); p = ABC_CALLOC( SC_Man, 1 ); - p->pLib = pLib; - p->pNtk = pNtk; - p->nObjs = Abc_NtkObjNumMax(pNtk); - p->pLoads = ABC_CALLOC( SC_Pair, p->nObjs ); - p->pDepts = ABC_CALLOC( SC_Pair, p->nObjs ); - p->pTimes = ABC_CALLOC( SC_Pair, p->nObjs ); - p->pSlews = ABC_CALLOC( SC_Pair, p->nObjs ); - p->pTimes2 = ABC_CALLOC( SC_Pair, p->nObjs ); - p->pSlews2 = ABC_CALLOC( SC_Pair, p->nObjs ); - p->clkStart = clock(); + p->pLib = pLib; + p->pNtk = pNtk; + p->nObjs = Abc_NtkObjNumMax(pNtk); + p->pLoads = ABC_CALLOC( SC_Pair, p->nObjs ); + p->pLoads2 = ABC_CALLOC( SC_Pair, p->nObjs ); + p->pDepts = ABC_CALLOC( SC_Pair, p->nObjs ); + p->pTimes = ABC_CALLOC( SC_Pair, p->nObjs ); + p->pSlews = ABC_CALLOC( SC_Pair, p->nObjs ); + p->pTimes2 = ABC_CALLOC( SC_Pair, p->nObjs ); + p->pSlews2 = ABC_CALLOC( SC_Pair, p->nObjs ); + p->vTimesOut = Vec_FltStart( Abc_NtkCoNum(pNtk) ); + p->vQue = Vec_QueAlloc( Abc_NtkCoNum(pNtk) ); + Vec_QueSetCosts( p->vQue, Vec_FltArray(p->vTimesOut) ); + for ( i = 0; i < Abc_NtkCoNum(pNtk); i++ ) + Vec_QuePush( p->vQue, i ); + p->vUpdates = Vec_IntAlloc( 1000 ); return p; } static inline void Abc_SclManFree( SC_Man * p ) { + Vec_IntFreeP( &p->vUpdates ); + Vec_IntFreeP( &p->vGatesBest ); +// Vec_QuePrint( p->vQue ); + Vec_QueCheck( p->vQue ); + Vec_QueFreeP( &p->vQue ); + Vec_FltFreeP( &p->vTimesOut ); Vec_IntFreeP( &p->vGates ); ABC_FREE( p->pLoads ); + ABC_FREE( p->pLoads2 ); ABC_FREE( p->pDepts ); ABC_FREE( p->pTimes ); ABC_FREE( p->pSlews ); @@ -159,13 +188,12 @@ static inline void Abc_SclManCleanTime( SC_Man * p ) ***********************************************************************/ static inline void Abc_SclConeStore( SC_Man * p, Vec_Int_t * vCone ) { - SC_Pair Zero = { 0.0, 0.0 }; Abc_Obj_t * pObj; int i; Abc_NtkForEachObjVec( vCone, p->pNtk, pObj, i ) { - *Abc_SclObjTime2(p, pObj) = *Abc_SclObjTime(p, pObj); *Abc_SclObjTime(p, pObj) = Zero; - *Abc_SclObjSlew2(p, pObj) = *Abc_SclObjSlew(p, pObj); *Abc_SclObjSlew(p, pObj) = Zero; + *Abc_SclObjTime2(p, pObj) = *Abc_SclObjTime(p, pObj); + *Abc_SclObjSlew2(p, pObj) = *Abc_SclObjSlew(p, pObj); } } static inline void Abc_SclConeRestore( SC_Man * p, Vec_Int_t * vCone ) @@ -178,6 +206,43 @@ static inline void Abc_SclConeRestore( SC_Man * p, Vec_Int_t * vCone ) *Abc_SclObjSlew(p, pObj) = *Abc_SclObjSlew2(p, pObj); } } +static inline void Abc_SclConeClear( SC_Man * p, Vec_Int_t * vCone ) +{ + SC_Pair Zero = { 0.0, 0.0 }; + Abc_Obj_t * pObj; + int i; + Abc_NtkForEachObjVec( vCone, p->pNtk, pObj, i ) + { + *Abc_SclObjTime(p, pObj) = Zero; + *Abc_SclObjSlew(p, pObj) = Zero; + } +} + +/**Function************************************************************* + + Synopsis [Stores/retrivies load information.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Abc_SclLoadStore( SC_Man * p, Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanin; + int i; + Abc_ObjForEachFanin( pObj, pFanin, i ) + *Abc_SclObjLoad2(p, pFanin) = *Abc_SclObjLoad(p, pFanin); +} +static inline void Abc_SclLoadRestore( SC_Man * p, Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanin; + int i; + Abc_ObjForEachFanin( pObj, pFanin, i ) + *Abc_SclObjLoad(p, pFanin) = *Abc_SclObjLoad2(p, pFanin); +} /**Function************************************************************* @@ -246,7 +311,7 @@ extern Abc_Obj_t * Abc_SclFindMostCriticalFanin( SC_Man * p, int * pfRise, Abc_O extern void Abc_SclTimeNtkPrint( SC_Man * p, int fShowAll, int fShort ); extern SC_Man * Abc_SclManStart( SC_Lib * pLib, Abc_Ntk_t * pNtk, int fUseWireLoads ); extern void Abc_SclTimeCone( SC_Man * p, Vec_Int_t * vCone ); -extern void Abc_SclTimeNtkRecompute( SC_Man * p, float * pArea, float * pDelay ); +extern void Abc_SclTimeNtkRecompute( SC_Man * p, float * pArea, float * pDelay, int fReverse ); /*=== sclTime.c =============================================================*/ extern void Abc_SclComputeLoad( SC_Man * p ); extern void Abc_SclUpdateLoad( SC_Man * p, Abc_Obj_t * pObj, SC_Cell * pOld, SC_Cell * pNew ); diff --git a/src/map/scl/sclSize.c b/src/map/scl/sclSize.c index d2e5fd3a..45b0bcd2 100644 --- a/src/map/scl/sclSize.c +++ b/src/map/scl/sclSize.c @@ -336,12 +336,12 @@ void Abc_SclUpdateNetwork( SC_Man * p, Abc_Obj_t * pObj, int nCone, int fUpsize, printf( "d =%8.2f ps ", SC_LibTimePs(p->pLib, Abc_SclGetMaxDelay(p)) ); printf( "a =%10.2f ", p->SumArea ); printf( "n =%5d ", nCone ); -// Abc_PrintTime( 1, "Time", clock() - p->clkStart ); -// ABC_PRTr( "Time", clock() - p->clkStart ); +// Abc_PrintTime( 1, "Time", clock() - p->timeTotal ); +// ABC_PRTr( "Time", clock() - p->timeTotal ); if ( fVeryVerbose ) - ABC_PRT( "Time", clock() - p->clkStart ); + ABC_PRT( "Time", clock() - p->timeTotal ); else - ABC_PRTr( "Time", clock() - p->clkStart ); + ABC_PRTr( "Time", clock() - p->timeTotal ); } } @@ -366,6 +366,7 @@ void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars clock_t nRuntimeLimit = pPars->nTimeOut ? pPars->nTimeOut * CLOCKS_PER_SEC + clock() : 0; int r, i, nNodes, nCones = 0, nDownSize = 0; p = Abc_SclManStart( pLib, pNtk, pPars->fUseWireLoads ); + p->timeTotal = clock(); if ( pPars->fPrintCP ) Abc_SclTimeNtkPrint( p, 0, 0 ); if ( pPars->fVerbose ) @@ -377,7 +378,7 @@ void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars printf( "d =%8.2f ps ", SC_LibTimePs(p->pLib, Abc_SclGetMaxDelay(p)) ); printf( "a =%10.2f ", p->SumArea ); printf( " " ); - Abc_PrintTime( 1, "Time", clock() - p->clkStart ); + Abc_PrintTime( 1, "Time", clock() - p->timeTotal ); } for ( r = i = 0; r < nIters; r++ ) { @@ -471,7 +472,7 @@ void Abc_SclSizingPerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, SC_SizePars * pPars printf( "Area: " ); printf( "%.2f -> %.2f ", p->SumArea0, p->SumArea ); printf( "(%+.1f %%). ", 100.0 * (p->SumArea - p->SumArea0)/ p->SumArea0 ); - Abc_PrintTime( 1, "Time", clock() - p->clkStart ); + Abc_PrintTime( 1, "Time", clock() - p->timeTotal ); // save the result and quit Abc_SclManSetGates( pLib, pNtk, p->vGates ); // updates gate pointers Abc_SclManFree( p ); diff --git a/src/map/scl/sclTime.c b/src/map/scl/sclTime.c index d714c20d..261e8c75 100644 --- a/src/map/scl/sclTime.c +++ b/src/map/scl/sclTime.c @@ -82,7 +82,7 @@ Abc_Obj_t * Abc_SclFindMostCriticalFanin( SC_Man * p, int * pfRise, Abc_Obj_t * SeeAlso [] ***********************************************************************/ -static inline void Abc_SclTimeGatePrint( SC_Man * p, Abc_Obj_t * pObj, int fRise, int Length, float maxDelay ) +static inline void Abc_SclTimeNodePrint( SC_Man * p, Abc_Obj_t * pObj, int fRise, int Length, float maxDelay ) { printf( "%7d : ", Abc_ObjId(pObj) ); printf( "%d ", Abc_ObjFaninNum(pObj) ); @@ -90,8 +90,8 @@ static inline void Abc_SclTimeGatePrint( SC_Man * p, Abc_Obj_t * pObj, int fRise if ( fRise >= 0 ) printf( "(%s) ", fRise ? "rise" : "fall" ); printf( "delay = (" ); - printf( "%7.1f ps ", Abc_SclObjTimePs(p, pObj, 1) ); - printf( "%7.1f ps ) ", Abc_SclObjTimePs(p, pObj, 0) ); + printf( "%8.2f ps ", Abc_SclObjTimePs(p, pObj, 1) ); + printf( "%8.2f ps ) ", Abc_SclObjTimePs(p, pObj, 0) ); printf( "load =%6.2f ff ", Abc_SclObjLoadFf(p, pObj, fRise >= 0 ? fRise : 0 ) ); printf( "slew =%6.1f ps ", Abc_SclObjSlewPs(p, pObj, fRise >= 0 ? fRise : 0 ) ); printf( "slack =%6.1f ps", Abc_SclObjSlack(p, pObj, maxDelay) ); @@ -103,10 +103,10 @@ void Abc_SclTimeNtkPrint( SC_Man * p, int fShowAll, int fShort ) Abc_Obj_t * pObj, * pPivot = Abc_SclFindCriticalCo( p, &fRise ); float maxDelay = Abc_SclObjTimePs(p, pPivot, fRise); - printf( "WireLoad model = \"%s\". ", p->pWLoadUsed ? p->pWLoadUsed : "none" ); + printf( "WireLoad model = \"%s\". ", p->pWLoadUsed ? p->pWLoadUsed->pName : "none" ); printf( "Gates = %d. ", Abc_NtkNodeNum(p->pNtk) ); printf( "Area = %.2f. ", Abc_SclGetTotalArea( p ) ); - printf( "Critical delay = %.1f ps\n", maxDelay ); + printf( "Critical delay = %.2f ps\n", maxDelay ); if ( fShort ) return; @@ -120,7 +120,7 @@ void Abc_SclTimeNtkPrint( SC_Man * p, int fShowAll, int fShort ) // print timing Abc_NtkForEachNodeReverse( p->pNtk, pObj, i ) if ( Abc_ObjFaninNum(pObj) > 0 ) - Abc_SclTimeGatePrint( p, pObj, -1, nLength, maxDelay ); + Abc_SclTimeNodePrint( p, pObj, -1, nLength, maxDelay ); } else { @@ -137,7 +137,7 @@ void Abc_SclTimeNtkPrint( SC_Man * p, int fShowAll, int fShort ) while ( pObj && Abc_ObjIsNode(pObj) ) { printf( "Critical path -- " ); - Abc_SclTimeGatePrint( p, pObj, fRise, nLength, maxDelay ); + Abc_SclTimeNodePrint( p, pObj, fRise, nLength, maxDelay ); pObj = Abc_SclFindMostCriticalFanin( p, &fRise, pObj ); } } @@ -185,7 +185,7 @@ static inline float Abc_SclLookup( SC_Surface * p, float slew, float load ) return p0 + sfrac * (p1 - p0); // <<== multiply result with K factor here } -void Abc_SclTimePin( SC_Man * p, SC_Timing * pTime, Abc_Obj_t * pObj, Abc_Obj_t * pFanin ) +void Abc_SclTimeFanin( SC_Man * p, SC_Timing * pTime, Abc_Obj_t * pObj, Abc_Obj_t * pFanin ) { SC_Pair * pArrIn = Abc_SclObjTime( p, pFanin ); SC_Pair * pSlewIn = Abc_SclObjSlew( p, pFanin ); @@ -208,7 +208,7 @@ void Abc_SclTimePin( SC_Man * p, SC_Timing * pTime, Abc_Obj_t * pObj, Abc_Obj_t pSlewOut->fall = Abc_MaxFloat( pSlewOut->fall, Abc_SclLookup(pTime->pFallTrans, pSlewIn->rise, pLoad->fall) ); } } -void Abc_SclDeptPin( SC_Man * p, SC_Timing * pTime, Abc_Obj_t * pObj, Abc_Obj_t * pFanin ) +void Abc_SclDeptFanin( SC_Man * p, SC_Timing * pTime, Abc_Obj_t * pObj, Abc_Obj_t * pFanin ) { SC_Pair * pDepIn = Abc_SclObjDept( p, pFanin ); // modified SC_Pair * pSlewIn = Abc_SclObjSlew( p, pFanin ); @@ -226,7 +226,7 @@ void Abc_SclDeptPin( SC_Man * p, SC_Timing * pTime, Abc_Obj_t * pObj, Abc_Obj_t pDepIn->rise = Abc_MaxFloat( pDepIn->rise, pDepOut->fall + Abc_SclLookup(pTime->pCellFall, pSlewIn->rise, pLoad->fall) ); } } -void Abc_SclTimeGate( SC_Man * p, Abc_Obj_t * pObj, int fDept ) +void Abc_SclTimeNode( SC_Man * p, Abc_Obj_t * pObj, int fDept ) { SC_Timings * pRTime; SC_Timing * pTime; @@ -252,9 +252,9 @@ void Abc_SclTimeGate( SC_Man * p, Abc_Obj_t * pObj, int fDept ) assert( Vec_PtrSize(pRTime->vTimings) == 1 ); pTime = (SC_Timing *)Vec_PtrEntry( pRTime->vTimings, 0 ); if ( fDept ) - Abc_SclDeptPin( p, pTime, pObj, Abc_ObjFanin(pObj, k) ); + Abc_SclDeptFanin( p, pTime, pObj, Abc_ObjFanin(pObj, k) ); else - Abc_SclTimePin( p, pTime, pObj, Abc_ObjFanin(pObj, k) ); + Abc_SclTimeFanin( p, pTime, pObj, Abc_ObjFanin(pObj, k) ); } } void Abc_SclTimeCone( SC_Man * p, Vec_Int_t * vCone ) @@ -262,32 +262,38 @@ void Abc_SclTimeCone( SC_Man * p, Vec_Int_t * vCone ) int fVerbose = 0; Abc_Obj_t * pObj; int i; + Abc_SclConeClear( p, vCone ); Abc_NtkForEachObjVec( vCone, p->pNtk, pObj, i ) { if ( fVerbose && Abc_ObjIsNode(pObj) ) printf( " Updating node %d with gate %s\n", Abc_ObjId(pObj), Abc_SclObjCell(p, pObj)->pName ); - if ( fVerbose && Abc_ObjIsNode(pObj) ) printf( " before (%6.1f ps %6.1f ps) ", Abc_SclObjTimePs(p, pObj, 1), Abc_SclObjTimePs(p, pObj, 0) ); - - Abc_SclTimeGate( p, pObj, 0 ); - + Abc_SclTimeNode( p, pObj, 0 ); if ( fVerbose && Abc_ObjIsNode(pObj) ) printf( "after (%6.1f ps %6.1f ps)\n", Abc_SclObjTimePs(p, pObj, 1), Abc_SclObjTimePs(p, pObj, 0) ); } } -void Abc_SclTimeNtkRecompute( SC_Man * p, float * pArea, float * pDelay ) +void Abc_SclTimeNtkRecompute( SC_Man * p, float * pArea, float * pDelay, int fReverse ) { Abc_Obj_t * pObj; int i; Abc_SclComputeLoad( p ); Abc_SclManCleanTime( p ); Abc_NtkForEachNode1( p->pNtk, pObj, i ) - Abc_SclTimeGate( p, pObj, 0 ); - Abc_NtkForEachNodeReverse1( p->pNtk, pObj, i ) - Abc_SclTimeGate( p, pObj, 1 ); + Abc_SclTimeNode( p, pObj, 0 ); + if ( fReverse ) + Abc_NtkForEachNodeReverse1( p->pNtk, pObj, i ) + Abc_SclTimeNode( p, pObj, 1 ); Abc_NtkForEachCo( p->pNtk, pObj, i ) + { Abc_SclObjDupFanin( p, pObj ); + Vec_FltWriteEntry( p->vTimesOut, i, Abc_SclObjTimeMax(p, pObj) ); + Vec_QueUpdate( p->vQue, i ); + } +// Vec_FltClear( p->vTimesOut ); +// Abc_NtkForEachCo( p->pNtk, pObj, i ) +// Vec_FltPush( p->vTimesOut, Abc_SclObjTimeMax(p, pObj) ); if ( pArea ) *pArea = Abc_SclGetTotalArea( p ); if ( pDelay ) @@ -308,10 +314,11 @@ void Abc_SclTimeNtkRecompute( SC_Man * p, float * pArea, float * pDelay ) SC_Man * Abc_SclManStart( SC_Lib * pLib, Abc_Ntk_t * pNtk, int fUseWireLoads ) { SC_Man * p = Abc_SclManAlloc( pLib, pNtk ); - p->fUseWireLoads = fUseWireLoads; assert( p->vGates == NULL ); p->vGates = Abc_SclManFindGates( pLib, pNtk ); - Abc_SclTimeNtkRecompute( p, &p->SumArea0, &p->MaxDelay0 ); + if ( fUseWireLoads ) + p->pWLoadUsed = Abc_SclFindWireLoadModel( pLib, Abc_SclGetTotalArea(p) ); + Abc_SclTimeNtkRecompute( p, &p->SumArea0, &p->MaxDelay0, 0 ); p->SumArea = p->SumArea0; return p; } diff --git a/src/map/scl/sclUpsize.c b/src/map/scl/sclUpsize.c index 8f4d2ca0..b648f720 100644 --- a/src/map/scl/sclUpsize.c +++ b/src/map/scl/sclUpsize.c @@ -45,35 +45,45 @@ extern Vec_Int_t * Abc_SclFindCriticalCoWindow( SC_Man * p, int Window ); SeeAlso [] ***********************************************************************/ -void Abc_SclFindTFO_rec( Abc_Obj_t * pObj, Vec_Int_t * vVisited ) +void Abc_SclFindTFO_rec( Abc_Obj_t * pObj, Vec_Int_t * vNodes, Vec_Int_t * vCos ) { Abc_Obj_t * pNext; int i; -// if ( Abc_ObjIsCo(pObj) ) -// return; if ( Abc_NodeIsTravIdCurrent( pObj ) ) return; Abc_NodeSetTravIdCurrent( pObj ); + if ( Abc_ObjIsCo(pObj) ) + { + Vec_IntPush( vCos, Abc_ObjId(pObj) ); + return; + } + assert( Abc_ObjIsNode(pObj) ); Abc_ObjForEachFanout( pObj, pNext, i ) - Abc_SclFindTFO_rec( pNext, vVisited ); - Vec_IntPush( vVisited, Abc_ObjId(pObj) ); + Abc_SclFindTFO_rec( pNext, vNodes, vCos ); + Vec_IntPush( vNodes, Abc_ObjId(pObj) ); } Vec_Int_t * Abc_SclFindTFO( Abc_Ntk_t * p, Vec_Int_t * vPath ) { - Vec_Int_t * vVisited; + Vec_Int_t * vNodes, * vCos; Abc_Obj_t * pObj, * pFanin; int i, k; assert( Vec_IntSize(vPath) > 0 ); - vVisited = Vec_IntAlloc( 100 ); + vCos = Vec_IntAlloc( 100 ); + vNodes = Vec_IntAlloc( 100 ); // collect nodes in the TFO Abc_NtkIncrementTravId( p ); Abc_NtkForEachObjVec( vPath, p, pObj, i ) Abc_ObjForEachFanin( pObj, pFanin, k ) if ( Abc_ObjIsNode(pFanin) ) - Abc_SclFindTFO_rec( pFanin, vVisited ); + Abc_SclFindTFO_rec( pFanin, vNodes, vCos ); // reverse order - Vec_IntReverseOrder( vVisited ); - return vVisited; + Vec_IntReverseOrder( vNodes ); +// Vec_IntSort( vNodes, 0 ); +//Vec_IntPrint( vNodes ); +//Vec_IntPrint( vCos ); + Vec_IntAppend( vNodes, vCos ); + Vec_IntFree( vCos ); + return vNodes; } /**Function************************************************************* @@ -143,7 +153,11 @@ Vec_Int_t * Abc_SclFindCriticalNodeWindow( SC_Man * p, Vec_Int_t * vPathCos, int int i; Abc_NtkIncrementTravId( p->pNtk ); Abc_NtkForEachObjVec( vPathCos, p->pNtk, pObj, i ) - Abc_SclFindCriticalNodeWindow_rec( p, Abc_ObjFanin0(pObj), vPath, fSlack - (fMaxArr - Abc_SclObjTimeMax(p, pObj)) ); + { + float fSlackThis = fSlack - (fMaxArr - Abc_SclObjTimeMax(p, pObj)); + assert( fSlackThis >= 0 ); + Abc_SclFindCriticalNodeWindow_rec( p, Abc_ObjFanin0(pObj), vPath, fSlackThis ); + } // label critical nodes Abc_NtkForEachObjVec( vPathCos, p->pNtk, pObj, i ) pObj->fMarkA = 1; @@ -199,12 +213,13 @@ Vec_Int_t * Abc_SclFindNodesToUpdate( Abc_Obj_t * pPivot, Vec_Int_t ** pvEvals ) assert( pObj->fMarkB == 0 ); pObj->fMarkB = 1; } - // collect nodes pointed to by non-labeled nodes + // collect nodes visible from the critical paths *pvEvals = Vec_IntAlloc( 10 ); Abc_NtkForEachObjVec( vNodes, p, pObj, i ) Abc_ObjForEachFanout( pObj, pNext, k ) if ( pNext->fMarkA && !pNext->fMarkB ) { + assert( pObj->fMarkB ); Vec_IntPush( *pvEvals, Abc_ObjId(pObj) ); break; } @@ -218,32 +233,7 @@ Vec_Int_t * Abc_SclFindNodesToUpdate( Abc_Obj_t * pPivot, Vec_Int_t ** pvEvals ) /**Function************************************************************* - Synopsis [Compute gain in changing the gate size.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Abc_SclFindGain( SC_Man * p, Vec_Int_t * vCone, Vec_Int_t * vEvals ) -{ - double dGain = 0; - Abc_Obj_t * pObj; - int i; - Abc_SclConeStore( p, vCone ); - Abc_SclTimeCone( p, vCone ); - Abc_NtkForEachObjVec( vEvals, p->pNtk, pObj, i ) - dGain += Abc_SclObjGain( p, pObj ); - Abc_SclConeRestore( p, vCone ); - dGain /= Vec_IntSize(vEvals); - return (float)dGain; -} - -/**Function************************************************************* - - Synopsis [Begin by upsizing gates will many fanouts.] + Synopsis [Computes the set of gates to upsize.] Description [] @@ -252,51 +242,75 @@ float Abc_SclFindGain( SC_Man * p, Vec_Int_t * vCone, Vec_Int_t * vEvals ) SeeAlso [] ***********************************************************************/ -int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio ) +int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio, int Notches ) { SC_Cell * pCellOld, * pCellNew; + Vec_Int_t * vChamps; // best gate for each node Vec_Flt_t * vSavings; // best gain for each node - Vec_Int_t * vBests; // best gate for each node - Vec_Int_t * vCone, * vEvals, * vUpdates; - Abc_Obj_t * pObj; - float dGain, dGainBest = 0; - int i, k, Entry, gateBest = -1; + Vec_Int_t * vRecalcs, * vEvals, * vUpdate; + Abc_Obj_t * pObj, * pTemp; + float dGain, dGainBest; + int i, k, n, Entry, gateBest; int nUpsizes = 0; - // return nUpsizes; + // compute savings due to upsizing each node + vChamps = Vec_IntAlloc( Vec_IntSize(vPathNodes) ); vSavings = Vec_FltAlloc( Vec_IntSize(vPathNodes) ); - vBests = Vec_IntAlloc( Vec_IntSize(vPathNodes) ); Abc_NtkForEachObjVec( vPathNodes, p->pNtk, pObj, i ) { - dGainBest = 0; - pCellOld = Abc_SclObjCell( p, pObj ); + // compute nodes to recalculate timing and nodes to evaluate afterwards + vRecalcs = Abc_SclFindNodesToUpdate( pObj, &vEvals ); + // save old gate, timing, fanin load + pCellOld = Abc_SclObjCell( p, pObj ); + Abc_SclConeStore( p, vRecalcs ); + Abc_SclLoadStore( p, pObj ); // try different gate sizes for this node - vCone = Abc_SclFindNodesToUpdate( pObj, &vEvals ); + dGainBest = 0.0; + gateBest = -1; SC_RingForEachCell( pCellOld, pCellNew, k ) { if ( pCellNew == pCellOld ) continue; + if ( k > Notches ) + break; +//printf( "Tring %s\n", pCellNew->pName ); + // set new cell Abc_SclObjSetCell( p, pObj, pCellNew ); - //printf( "changing %s for %s at node %d ", pCellOld->pName, pCellNew->pName, Abc_ObjId(pObj) ); Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew ); - dGain = Abc_SclFindGain( p, vCone, vEvals ); - Abc_SclUpdateLoad( p, pObj, pCellNew, pCellOld ); - //printf( "gain is %f\n", dGain ); + // recompute timing + Abc_SclTimeCone( p, vRecalcs ); + // set old cell + Abc_SclObjSetCell( p, pObj, pCellOld ); + Abc_SclLoadRestore( p, pObj ); + // evaluate gain + dGain = 0.0; + Abc_NtkForEachObjVec( vEvals, p->pNtk, pTemp, n ) + dGain += Abc_SclObjGain( p, pTemp ); + dGain /= Vec_IntSize(vEvals); + if ( dGain <= 0.0 ) + continue; + // put back timing and load +//printf( "gain is %f\n", dGain ); if ( dGainBest < dGain ) { dGainBest = dGain; gateBest = pCellNew->Id; } } +//printf( "gain is %f\n", dGainBest ); + // remember savings assert( dGainBest >= 0.0 ); - Vec_IntFree( vCone ); - Vec_IntFree( vEvals ); - Abc_SclObjSetCell( p, pObj, pCellOld ); + Vec_IntPush( vChamps, gateBest ); Vec_FltPush( vSavings, dGainBest ); - Vec_IntPush( vBests, gateBest ); + // put back old cell and timing + Abc_SclObjSetCell( p, pObj, pCellOld ); + Abc_SclConeRestore( p, vRecalcs ); + // cleanup + Vec_IntFree( vRecalcs ); + Vec_IntFree( vEvals ); } - assert( Vec_IntSize(vBests) == Vec_IntSize(vPathNodes) ); + assert( Vec_IntSize(vChamps) == Vec_IntSize(vPathNodes) ); // we have computed the gains - find the best ones { @@ -314,38 +328,116 @@ int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio ) pPerm = Abc_QuickSortCost( Vec_IntArray(vCosts), Vec_IntSize(vCosts), 1 ); assert( Vec_FltEntry(vSavings, pPerm[0]) >= Vec_FltEntry(vSavings, pPerm[Vec_FltSize(vSavings)-1]) ); // find those that are good to update - Limit = Abc_MaxInt( 1, (int)(0.01 * Ratio * Vec_IntSize(vBests)) ); - vUpdates = Vec_IntAlloc( Limit ); + Limit = Abc_MaxInt( 1, (int)(0.01 * Ratio * Vec_IntSize(vChamps)) ); + vUpdate = Vec_IntAlloc( Limit ); for ( i = 0; i < Limit; i++ ) if ( Vec_FltEntry(vSavings, pPerm[i]) > 0 ) - Vec_IntPush( vUpdates, pPerm[i] ); + { + assert( Vec_IntEntry(vChamps, pPerm[i]) >= 0 ); + Vec_IntPush( vUpdate, pPerm[i] ); + } Vec_IntFree( vCosts ); ABC_FREE( pPerm ); } // update the network - Vec_IntForEachEntry( vUpdates, Entry, i ) + Vec_IntForEachEntry( vUpdate, Entry, i ) { // get the object pObj = Abc_NtkObj( p->pNtk, Vec_IntEntry(vPathNodes, Entry) ); - // find new gate + assert( pObj->fMarkA ); + // find old and new gates pCellOld = Abc_SclObjCell( p, pObj ); - pCellNew = SC_LibCell( p->pLib, Vec_IntEntry(vBests, Entry) ); + pCellNew = SC_LibCell( p->pLib, Vec_IntEntry(vChamps, Entry) ); assert( pCellNew != NULL ); +// printf( "%6d %s -> %s \n", Abc_ObjId(pObj), pCellOld->pName, pCellNew->pName ); // update gate Abc_SclUpdateLoad( p, pObj, pCellOld, pCellNew ); p->SumArea += pCellNew->area - pCellOld->area; Abc_SclObjSetCell( p, pObj, pCellNew ); - nUpsizes++; + // record the update + Vec_IntPush( p->vUpdates, Abc_ObjId(pObj) ); + Vec_IntPush( p->vUpdates, pCellNew->Id ); } - Vec_IntFree( vUpdates ); - Vec_IntFree( vBests ); + // cleanup + nUpsizes = Vec_IntSize(vUpdate); + Vec_IntFree( vUpdate ); + Vec_IntFree( vChamps ); Vec_FltFree( vSavings ); return nUpsizes; } +void Abc_SclApplyUpdateToBest( Vec_Int_t * vGates, Vec_Int_t * vGatesBest, Vec_Int_t * vUpdate ) +{ + int i, ObjId, GateId, GateId2; + Vec_IntForEachEntryDouble( vUpdate, ObjId, GateId, i ) + Vec_IntWriteEntry( vGatesBest, ObjId, GateId ); + Vec_IntClear( vUpdate ); + Vec_IntForEachEntryTwo( vGates, vGatesBest, GateId, GateId2, i ) + assert( GateId == GateId2 ); +//printf( "Updating gates.\n" ); +} +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SclUpsizePrintDiffs( SC_Man * p, SC_Lib * pLib, Abc_Ntk_t * pNtk ) +{ + float fDiff = (float)0.001; + int k; + Abc_Obj_t * pObj; + + SC_Pair * pTimes = ABC_ALLOC( SC_Pair, p->nObjs ); + SC_Pair * pSlews = ABC_ALLOC( SC_Pair, p->nObjs ); + SC_Pair * pLoads = ABC_ALLOC( SC_Pair, p->nObjs ); + + memcpy( pTimes, p->pTimes, sizeof(SC_Pair) * p->nObjs ); + memcpy( pSlews, p->pSlews, sizeof(SC_Pair) * p->nObjs ); + memcpy( pLoads, p->pLoads, sizeof(SC_Pair) * p->nObjs ); + + Abc_SclTimeNtkRecompute( p, NULL, NULL, 0 ); + + Abc_NtkForEachNode( pNtk, pObj, k ) + { + if ( Abc_AbsFloat(p->pLoads[k].rise - pLoads[k].rise) > fDiff ) + printf( "%6d : load rise differs %12.6f %f %f\n", k, SC_LibCapFf(pLib, p->pLoads[k].rise)-SC_LibCapFf(pLib, pLoads[k].rise), SC_LibCapFf(pLib, p->pLoads[k].rise), SC_LibCapFf(pLib, pLoads[k].rise) ); + if ( Abc_AbsFloat(p->pLoads[k].fall - pLoads[k].fall) > fDiff ) + printf( "%6d : load fall differs %12.6f %f %f\n", k, SC_LibCapFf(pLib, p->pLoads[k].fall)-SC_LibCapFf(pLib, pLoads[k].fall), SC_LibCapFf(pLib, p->pLoads[k].fall), SC_LibCapFf(pLib, pLoads[k].fall) ); + + if ( Abc_AbsFloat(p->pSlews[k].rise - pSlews[k].rise) > fDiff ) + printf( "%6d : slew rise differs %12.6f %f %f\n", k, SC_LibTimePs(pLib, p->pSlews[k].rise)-SC_LibTimePs(pLib, pSlews[k].rise), SC_LibTimePs(pLib, p->pSlews[k].rise), SC_LibTimePs(pLib, pSlews[k].rise) ); + if ( Abc_AbsFloat(p->pSlews[k].fall - pSlews[k].fall) > fDiff ) + printf( "%6d : slew fall differs %12.6f %f %f\n", k, SC_LibTimePs(pLib, p->pSlews[k].fall)-SC_LibTimePs(pLib, pSlews[k].fall), SC_LibTimePs(pLib, p->pSlews[k].fall), SC_LibTimePs(pLib, pSlews[k].fall) ); + + if ( Abc_AbsFloat(p->pTimes[k].rise - pTimes[k].rise) > fDiff ) + printf( "%6d : time rise differs %12.6f %f %f\n", k, SC_LibTimePs(pLib, p->pTimes[k].rise)-SC_LibTimePs(pLib, pTimes[k].rise), SC_LibTimePs(pLib, p->pTimes[k].rise), SC_LibTimePs(pLib, pTimes[k].rise) ); + if ( Abc_AbsFloat(p->pTimes[k].fall - pTimes[k].fall) > fDiff ) + printf( "%6d : time fall differs %12.6f %f %f\n", k, SC_LibTimePs(pLib, p->pTimes[k].fall)-SC_LibTimePs(pLib, pTimes[k].fall), SC_LibTimePs(pLib, p->pTimes[k].fall), SC_LibTimePs(pLib, pTimes[k].fall) ); + } + +/* +if ( memcmp( pTimes, p->pTimes, sizeof(SC_Pair) * p->nObjs ) ) + printf( "Times differ!\n" ); +if ( memcmp( pSlews, p->pSlews, sizeof(SC_Pair) * p->nObjs ) ) + printf( "Slews differ!\n" ); +if ( memcmp( pLoads, p->pLoads, sizeof(SC_Pair) * p->nObjs ) ) + printf( "Loads differ!\n" ); +*/ + + ABC_FREE( pTimes ); + ABC_FREE( pSlews ); + ABC_FREE( pLoads ); +} + /**Function************************************************************* Synopsis [Print cumulative statistics.] @@ -357,20 +449,26 @@ int Abc_SclFindUpsizes( SC_Man * p, Vec_Int_t * vPathNodes, int Ratio ) SeeAlso [] ***********************************************************************/ -void Abc_SclUpsizePrint( SC_Man * p, int Iter, Vec_Int_t * vPathPos, Vec_Int_t * vPathNodes, Vec_Int_t * vTFO, int nUpsizes ) +void Abc_SclUpsizePrint( SC_Man * p, int Iter, int nPathPos, int nPathNodes, int nUpsizes, int nTFOs, int fVerbose ) { - printf( "Iter %3d ", Iter ); - printf( "PO:%5d. ", Vec_IntSize(vPathPos) ); - printf( "Node:%6d. ", Vec_IntSize(vPathNodes) ); - printf( "TFO:%6d. ", Vec_IntSize(vTFO) ); - printf( "Size:%5d. ", nUpsizes ); + printf( "%4d ", Iter ); + printf( "PO:%5d. ", nPathPos ); + printf( "Path:%6d. ", nPathNodes ); + printf( "Gate:%5d. ", nUpsizes ); + printf( "TFO:%6d. ", nTFOs ); + printf( "B: " ); + printf( "%.2f ps ", SC_LibTimePs(p->pLib, p->BestDelay) ); + printf( "(%+5.1f %%) ", 100.0 * (p->BestDelay - p->MaxDelay0)/ p->MaxDelay0 ); printf( "D: " ); - printf( "%.2f ps ", SC_LibTimePs(p->pLib, p->MaxDelay) ); - printf( "(%+5.1f %%) ", 100.0 * (p->MaxDelay - p->MaxDelay0)/ p->MaxDelay0 ); + printf( "%.2f ps ", SC_LibTimePs(p->pLib, p->MaxDelay) ); + printf( "(%+5.1f %%) ", 100.0 * (p->MaxDelay - p->MaxDelay0)/ p->MaxDelay0 ); printf( "A: " ); - printf( "%.2f ", p->SumArea ); - printf( "(%+5.1f %%) ", 100.0 * (p->SumArea - p->SumArea0)/ p->SumArea0 ); - Abc_PrintTime( 1, "Time", clock() - p->clkStart ); + printf( "%.2f ", p->SumArea ); + printf( "(%+5.1f %%) ", 100.0 * (p->SumArea - p->SumArea0)/ p->SumArea0 ); + if ( fVerbose ) + ABC_PRT( "T", clock() - p->timeTotal ); + else + ABC_PRTr( "T", clock() - p->timeTotal ); } /**Function************************************************************* @@ -384,49 +482,102 @@ void Abc_SclUpsizePrint( SC_Man * p, int Iter, Vec_Int_t * vPathPos, Vec_Int_t * SeeAlso [] ***********************************************************************/ -void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int Window, int Ratio, int nIters, int fVerbose ) +void Abc_SclUpsizePerform( SC_Lib * pLib, Abc_Ntk_t * pNtk, int nIters, int Window, int Ratio, int Notches, int TimeOut, int fVerbose, int fVeryVerbose ) { SC_Man * p; Vec_Int_t * vPathPos; // critical POs Vec_Int_t * vPathNodes; // critical nodes and PIs Vec_Int_t * vTFO; int i, nUpsizes = -1; + int nAllPos, nAllNodes, nAllTfos, nAllUpsizes; + clock_t clk; + + if ( fVerbose ) + { + printf( "Sizing parameters: " ); + printf( "Iters =%4d. ", nIters ); + printf( "Time window =%3d %%. ", Window ); + printf( "Update ratio =%3d %%. ", Ratio ); + printf( "Max upsize steps =%2d. ", Notches ); + printf( "Timeout =%3d sec", TimeOut ); + printf( "\n" ); + } // prepare the manager; collect init stats p = Abc_SclManStart( pLib, pNtk, 1 ); + p->timeTotal = clock(); + assert( p->vGatesBest == NULL ); + p->vGatesBest = Vec_IntDup( p->vGates ); + p->BestDelay = p->MaxDelay0; // perform upsizing + nAllPos = nAllNodes = nAllTfos = nAllUpsizes = 0; for ( i = 0; nUpsizes && i < nIters; i++ ) { + // detect critical path + clk = clock(); vPathPos = Abc_SclFindCriticalCoWindow( p, Window ); vPathNodes = Abc_SclFindCriticalNodeWindow( p, vPathPos, Window ); - nUpsizes = Abc_SclFindUpsizes( p, vPathNodes, Ratio ); + p->timeCone += clock() - clk; + + // selectively upsize the nodes + clk = clock(); + nUpsizes = Abc_SclFindUpsizes( p, vPathNodes, Ratio, Notches ); + p->timeSize += clock() - clk; + + // unmark critical path + clk = clock(); Abc_SclUnmarkCriticalNodeWindow( p, vPathNodes ); Abc_SclUnmarkCriticalNodeWindow( p, vPathPos ); + p->timeCone += clock() - clk; - // update info + // update timing information + clk = clock(); vTFO = Abc_SclFindTFO( p->pNtk, vPathNodes ); -// Abc_SclTimeNtkRecompute( p, &p->SumArea, &p->MaxDelay ); - Abc_SclConeStore( p, vTFO ); Abc_SclTimeCone( p, vTFO ); + p->timeTime += clock() - clk; +// Abc_SclUpsizePrintDiffs( p, pLib, pNtk ); + + // save the best network p->MaxDelay = Abc_SclGetMaxDelay( p ); + if ( p->BestDelay > p->MaxDelay ) + { + p->BestDelay = p->MaxDelay; + Abc_SclApplyUpdateToBest( p->vGates, p->vGatesBest, p->vUpdates ); + } - Abc_SclUpsizePrint( p, i, vPathPos, vPathNodes, vTFO, nUpsizes ); + // report and cleanup + Abc_SclUpsizePrint( p, i, Vec_IntSize(vPathPos), Vec_IntSize(vPathNodes), nUpsizes, Vec_IntSize(vTFO), fVeryVerbose ); //|| (i == nIters-1) ); + nAllPos += Vec_IntSize(vPathPos); + nAllNodes += Vec_IntSize(vPathNodes); + nAllTfos += Vec_IntSize(vTFO); + nAllUpsizes += nUpsizes; Vec_IntFree( vPathPos ); Vec_IntFree( vPathNodes ); Vec_IntFree( vTFO ); - - if ( i && i % 50 == 0 ) - Abc_SclComputeLoad( p ); } -// Abc_NtkCleanMarkAB( pNtk ); + // update for best gates and recompute timing + ABC_SWAP( Vec_Int_t *, p->vGatesBest, p->vGates ); + if ( fVerbose ) + { + Abc_SclTimeNtkRecompute( p, &p->SumArea, &p->MaxDelay, 0 ); + Abc_SclUpsizePrint( p, i, nAllPos/i, nAllNodes/i, nAllUpsizes/i, nAllTfos/i, 1 ); + // report runtime + p->timeTotal = clock() - p->timeTotal; + p->timeOther = p->timeTotal - p->timeCone - p->timeSize - p->timeTime; + ABC_PRTP( "Runtime: Critical path", p->timeCone, p->timeTotal ); + ABC_PRTP( "Runtime: Sizing eval ", p->timeSize, p->timeTotal ); + ABC_PRTP( "Runtime: Timing update", p->timeTime, p->timeTotal ); + ABC_PRTP( "Runtime: Other ", p->timeOther, p->timeTotal ); + ABC_PRTP( "Runtime: TOTAL ", p->timeTotal, p->timeTotal ); + } // save the result and quit Abc_SclManSetGates( pLib, pNtk, p->vGates ); // updates gate pointers Abc_SclManFree( p ); +// Abc_NtkCleanMarkAB( pNtk ); } - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/map/scl/sclUtil.c b/src/map/scl/sclUtil.c index 6a1f6a36..37efbd44 100644 --- a/src/map/scl/sclUtil.c +++ b/src/map/scl/sclUtil.c @@ -233,6 +233,7 @@ void Abc_SclManSetGates( SC_Lib * pLib, Abc_Ntk_t * p, Vec_Int_t * vGates ) SC_Cell * pCell = SC_LibCell( pLib, Vec_IntEntry(vGates, Abc_ObjId(pObj)) ); assert( pCell->n_inputs == Abc_ObjFaninNum(pObj) ); pObj->pData = Mio_LibraryReadGateByName( (Mio_Library_t *)p->pManFunc, pCell->pName, NULL ); + assert( pObj->fMarkA == 0 && pObj->fMarkB == 0 ); //printf( "Found gate %s\n", pCell->name ); } } diff --git a/src/misc/vec/vecQue.h b/src/misc/vec/vecQue.h new file mode 100644 index 00000000..d31abb27 --- /dev/null +++ b/src/misc/vec/vecQue.h @@ -0,0 +1,360 @@ +/**CFile**************************************************************** + + FileName [vecQue.h] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Resizable arrays.] + + Synopsis [Priority queue.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: vecQue.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#ifndef ABC__misc__vec__Queue_h +#define ABC__misc__vec__Queue_h + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#include + +ABC_NAMESPACE_HEADER_START + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// BASIC TYPES /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Vec_Que_t_ Vec_Que_t; +struct Vec_Que_t_ +{ + int nCap; + int nSize; + int * pHeap; + int * pOrder; + float * pCostsFlt; // owned by the caller +}; + +static inline float Vec_QueCost( Vec_Que_t * p, int v ) { return p->pCostsFlt ? p->pCostsFlt[v] : v; } + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Que_t * Vec_QueAlloc( int nCap ) +{ + Vec_Que_t * p; + p = ABC_CALLOC( Vec_Que_t, 1 ); + if ( nCap < 16 ) + nCap = 16; + p->nSize = 1; + p->nCap = nCap + 1; + p->pHeap = ABC_FALLOC( int, p->nCap ); + p->pOrder = ABC_FALLOC( int, p->nCap ); + return p; +} +static inline void Vec_QueFree( Vec_Que_t * p ) +{ + ABC_FREE( p->pOrder ); + ABC_FREE( p->pHeap ); + ABC_FREE( p ); +} +static inline void Vec_QueFreeP( Vec_Que_t ** p ) +{ + if ( *p ) + Vec_QueFree( *p ); + *p = NULL; +} +static inline void Vec_QueSetCosts( Vec_Que_t * p, float * pCosts ) +{ + assert( p->pCostsFlt == NULL ); + p->pCostsFlt = pCosts; +} +static inline void Vec_QueGrow( Vec_Que_t * p, int nCapMin ) +{ + if ( p->nCap >= nCapMin ) + return; + p->pHeap = ABC_REALLOC( int, p->pHeap, nCapMin ); + p->pOrder = ABC_REALLOC( int, p->pOrder, nCapMin ); + memset( p->pHeap + p->nCap, 0xff, (nCapMin - p->nCap) * sizeof(int) ); + memset( p->pOrder + p->nCap, 0xff, (nCapMin - p->nCap) * sizeof(int) ); + p->nCap = nCapMin; +} +static inline void Vec_QueClear( Vec_Que_t * p ) +{ + int i; + assert( p->pHeap[0] == -1 ); + for ( i = 1; i < p->nSize; i++ ) + { + assert( p->pHeap[i] >= 0 && p->pOrder[p->pHeap[i]] == i ); + p->pOrder[p->pHeap[i]] = -1; + p->pHeap[i] = -1; + } + p->nSize = 1; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_QueSize( Vec_Que_t * p ) +{ + assert( p->nSize > 0 ); + return p->nSize - 1; +} +static inline int Vec_QueTop( Vec_Que_t * p ) +{ + return Vec_QueSize(p) > 0 ? p->pHeap[1] : -1; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_QueMoveUp( Vec_Que_t * p, int v ) +{ + float Cost = Vec_QueCost(p, v); + int i = p->pOrder[v]; + int parent = i >> 1; + int fMoved = 0; + assert( p->pOrder[v] != -1 ); + assert( p->pHeap[i] == v ); + while ( i > 1 && Cost > Vec_QueCost(p, p->pHeap[parent]) ) + { + p->pHeap[i] = p->pHeap[parent]; + p->pOrder[p->pHeap[i]] = i; + i = parent; + parent = i >> 1; + fMoved = 1; + } + p->pHeap[i] = v; + p->pOrder[v] = i; + return fMoved; +} +static inline void Vec_QueMoveDown( Vec_Que_t * p, int v ) +{ + float Cost = Vec_QueCost(p, v); + int i = p->pOrder[v]; + int child = i << 1; + while ( child < p->nSize ) + { + if ( child + 1 < p->nSize && Vec_QueCost(p, p->pHeap[child]) < Vec_QueCost(p, p->pHeap[child+1]) ) + child++; + assert( child < p->nSize ); + if ( Cost >= Vec_QueCost(p, p->pHeap[child])) + break; + p->pHeap[i] = p->pHeap[child]; + p->pOrder[p->pHeap[i]] = i; + i = child; + child = child << 1; + } + p->pHeap[i] = v; + p->pOrder[v] = i; +} +static inline void Vec_QueUpdate( Vec_Que_t * p, int v ) +{ + if ( !Vec_QueMoveUp( p, v ) ) + Vec_QueMoveDown( p, v ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_QuePush( Vec_Que_t * p, int v ) +{ + if ( p->nSize == p->nCap ) + Vec_QueGrow( p, 2 * p->nCap ); + assert( p->nSize < p->nCap ); + assert( p->pOrder[v] == -1 ); + assert( p->pHeap[p->nSize] == -1 ); + p->pOrder[v] = p->nSize; + p->pHeap[p->nSize++] = v; + Vec_QueMoveUp( p, v ); +} +static inline int Vec_QuePop( Vec_Que_t * p ) +{ + int v, Res; + assert( p->nSize > 1 ); + Res = p->pHeap[1]; p->pOrder[Res] = -1; + if ( --p->nSize == 1 ) + return Res; + v = p->pHeap[p->nSize]; p->pHeap[p->nSize] = -1; + p->pHeap[1] = v; p->pOrder[v] = 1; + Vec_QueMoveDown( p, v ); + return Res; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_QuePrint( Vec_Que_t * p ) +{ + int i, k, m; + for ( i = k = 1; i < p->nSize; i += k, k *= 2 ) + { + for ( m = 0; m < k; m++ ) + if ( i+m < p->nSize ) + printf( "%-5d", p->pHeap[i+m] ); + printf( "\n" ); + for ( m = 0; m < k; m++ ) + if ( i+m < p->nSize ) + printf( "%-5.0f", Vec_QueCost(p, p->pHeap[i+m]) ); + printf( "\n" ); + printf( "\n" ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_QueCheck( Vec_Que_t * p ) +{ + int i, child; + assert( p->nSize > 0 ); + assert( p->nSize <= p->nCap ); + // check mapping + for ( i = 0; i < p->nSize-1; i++ ) + assert( p->pOrder[i] > 0 ); + for ( ; i < p->nCap; i++ ) + assert( p->pOrder[i] == -1 ); + // check heap + assert( p->pHeap[0] == -1 ); + for ( i = 0; i < p->nSize-1; i++ ) + assert( p->pHeap[p->pOrder[i]] == i ); + for ( i++; i < p->nCap; i++ ) + assert( p->pHeap[i] == -1 ); + // check heap property + for ( i = 1; i < p->nSize; i++ ) + { + child = i << 1; + if ( child < p->nSize ) + assert( Vec_QueCost(p, p->pHeap[i]) >= Vec_QueCost(p, p->pHeap[child]) ); + child++; + if ( child < p->nSize ) + assert( Vec_QueCost(p, p->pHeap[i]) >= Vec_QueCost(p, p->pHeap[child]) ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_QueTest( Vec_Flt_t * vCosts ) +{ + Vec_Int_t * vTop; + Vec_Que_t * p; + int i, Entry; + + // start the queue + p = Vec_QueAlloc( Vec_FltSize(vCosts) ); + Vec_QueSetCosts( p, Vec_FltArray(vCosts) ); + for ( i = 0; i < Vec_FltSize(vCosts); i++ ) + Vec_QuePush( p, i ); +// Vec_QuePrint( p ); + Vec_QueCheck( p ); + + // find the topmost 10% + vTop = Vec_IntAlloc( Vec_FltSize(vCosts) / 10 ); + while ( Vec_IntSize(vTop) < Vec_FltSize(vCosts) / 10 ) + Vec_IntPush( vTop, Vec_QuePop(p) ); +// Vec_IntPrint( vTop ); +// Vec_QueCheck( p ); // queque is not ready at this point!!! + + // put them back + Vec_IntForEachEntry( vTop, Entry, i ) + Vec_QuePush( p, Entry ); + Vec_IntFree( vTop ); + Vec_QueCheck( p ); + + Vec_QueFree( p ); +} + +/* + { + extern void Vec_QueTest( Vec_Flt_t * p ); + Vec_QueTest( p->vTimesOut ); + } +*/ + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + + +ABC_NAMESPACE_HEADER_END + +#endif + -- cgit v1.2.3