From 267f61164aac2a22409fd89364f38e7b7082e7d8 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 20 Jul 2011 18:40:09 +0700 Subject: Changes to enable smarter simulation. --- src/aig/ssw/module.make | 1 + src/aig/ssw/ssw.h | 3 + src/aig/ssw/sswRarity.c | 360 ++++++++++++++++++++++++++++++++++++++++++++++++ src/aig/ssw/sswSim.c | 70 ++++++++++ 4 files changed, 434 insertions(+) create mode 100644 src/aig/ssw/sswRarity.c (limited to 'src/aig/ssw') diff --git a/src/aig/ssw/module.make b/src/aig/ssw/module.make index 9d93fb93..b6b813b1 100644 --- a/src/aig/ssw/module.make +++ b/src/aig/ssw/module.make @@ -11,6 +11,7 @@ SRC += src/aig/ssw/sswAig.c \ src/aig/ssw/sswMan.c \ src/aig/ssw/sswPart.c \ src/aig/ssw/sswPairs.c \ + src/aig/ssw/sswRarity.c \ src/aig/ssw/sswSat.c \ src/aig/ssw/sswSemi.c \ src/aig/ssw/sswSim.c \ diff --git a/src/aig/ssw/ssw.h b/src/aig/ssw/ssw.h index e4a2619e..07c31a74 100644 --- a/src/aig/ssw/ssw.h +++ b/src/aig/ssw/ssw.h @@ -124,6 +124,9 @@ extern int Ssw_SmlNumFrames( Ssw_Sml_t * p ); extern int Ssw_SmlNumWordsTotal( Ssw_Sml_t * p ); extern unsigned * Ssw_SmlSimInfo( Ssw_Sml_t * p, Aig_Obj_t * pObj ); extern int Ssw_SmlObjsAreEqualWord( Ssw_Sml_t * p, Aig_Obj_t * pObj0, Aig_Obj_t * pObj1 ); +extern void Ssw_SmlInitializeSpecial( Ssw_Sml_t * p, Vec_Int_t * vInit ); +extern Vec_Ptr_t * Ssw_SmlSimDataPointers( Ssw_Sml_t * p ); + ABC_NAMESPACE_HEADER_END diff --git a/src/aig/ssw/sswRarity.c b/src/aig/ssw/sswRarity.c new file mode 100644 index 00000000..f07b0f2a --- /dev/null +++ b/src/aig/ssw/sswRarity.c @@ -0,0 +1,360 @@ +/**CFile**************************************************************** + + FileName [sswRarity.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Inductive prover with constraints.] + + Synopsis [Rarity-driven refinement of equivalence classes.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - September 1, 2008.] + + Revision [$Id: sswRarity.c,v 1.00 2008/09/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "sswInt.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Ssw_RarMan_t_ Ssw_RarMan_t; +struct Ssw_RarMan_t_ +{ + // parameters + int nWords; // the number of words to simulate + int nFrames; // the number of frames to simulate + int nBinSize; // the number of flops in one group + int fVerbose; // the verbosiness flag + int nGroups; // the number of flop groups + // internal data + Aig_Man_t * pAig; // AIG with equivalence classes + Ssw_Cla_t * ppClasses; // equivalence classes + Ssw_Sml_t * pSml; // simulation manager + Vec_Ptr_t * vSimInfo; // simulation info from pSml manager + Vec_Int_t * vInits; // initial state + // rarity data + int * pRarity; // occur counts for patterns in groups + int * pGroupValues; // occur counts in each group + double * pPatCosts; // pattern costs + +}; + +static inline int Ssw_RarGetBinPat( Ssw_RarMan_t * p, int iBin, int iPat ) +{ + assert( iBin >= 0 && iBin < Aig_ManRegNum(p->pAig) / p->nBinSize ); + assert( iPat >= 0 && iPat < (1 << p->nBinSize) ); + return p->pRarity[iBin * (1 << p->nBinSize) + iPat]; +} +static inline void Ssw_RarSetBinPat( Ssw_RarMan_t * p, int iBin, int iPat, int Value ) +{ + assert( iBin >= 0 && iBin < Aig_ManRegNum(p->pAig) / p->nBinSize ); + assert( iPat >= 0 && iPat < (1 << p->nBinSize) ); + p->pRarity[iBin * (1 << p->nBinSize) + iPat] = Value; +} +static inline void Ssw_RarAddToBinPat( Ssw_RarMan_t * p, int iBin, int iPat ) +{ + assert( iBin >= 0 && iBin < Aig_ManRegNum(p->pAig) / p->nBinSize ); + assert( iPat >= 0 && iPat < (1 << p->nBinSize) ); + p->pRarity[iBin * (1 << p->nBinSize) + iPat]++; +} + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Ssw_RarMan_t * Ssw_RarManStart( Aig_Man_t * pAig, int nWords, int nFrames, int nBinSize, int fVerbose ) +{ + Ssw_RarMan_t * p; + if ( Aig_ManRegNum(pAig) < nBinSize || nBinSize <= 0 ) + return NULL; + p = ABC_CALLOC( Ssw_RarMan_t, 1 ); + p->pAig = pAig; + p->nWords = nWords; + p->nFrames = nFrames; + p->nBinSize = nBinSize; + p->fVerbose = fVerbose; + p->nGroups = Aig_ManRegNum(pAig) / nBinSize; + p->pRarity = ABC_CALLOC( int, (1 << nBinSize) * p->nGroups ); + p->pGroupValues = ABC_CALLOC( int, (Aig_ManRegNum(pAig) / nBinSize) ); + p->pPatCosts = ABC_CALLOC( double, p->nWords * 32 ); + p->pSml = Ssw_SmlStart( pAig, 0, nFrames, nWords ); + return p; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Ssw_RarManStop( Ssw_RarMan_t * p ) +{ + Ssw_SmlStop( p->pSml ); + Ssw_ClassesStop( p->ppClasses ); + Vec_PtrFreeP( &p->vSimInfo ); + Vec_IntFreeP( &p->vInits ); + ABC_FREE( p->pGroupValues ); + ABC_FREE( p->pPatCosts ); + ABC_FREE( p->pRarity ); + ABC_FREE( p ); +} + + +/**Function************************************************************* + + Synopsis [Updates rarity counters.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Ssw_RarUpdateCounters( Ssw_RarMan_t * p ) +{ + Aig_Obj_t * pObj; + unsigned * pData; + int i, k; + for ( k = 0; k < p->nWords * 32; k++ ) + { + for ( i = 0; i < p->nGroups; i++ ) + p->pGroupValues[i] = 0; + Saig_ManForEachLi( p->pAig, pObj, i ) + { + pData = Vec_PtrEntry( p->vSimInfo, Aig_ObjId(pObj) ); + if ( Aig_InfoHasBit(pData, k) ) + p->pGroupValues[i / p->nBinSize] |= (1 << (i % p->nBinSize)); + } + for ( i = 0; i < p->nGroups; i++ ) + Ssw_RarAddToBinPat( p, i, p->pGroupValues[i] ); + } +} + +/**Function************************************************************* + + Synopsis [Select best patterns.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Ssw_RarTransferPatterns( Ssw_RarMan_t * p, Vec_Int_t * vInits ) +{ + Aig_Obj_t * pObj; + unsigned * pData; + int i, k, Value; + for ( i = 0; i < p->nWords * 32; i++ ) + p->pPatCosts[i] = 0.0; + for ( i = 0; i < p->nGroups; i++ ) + { + for ( k = 0; k < p->nWords * 32; k++ ) + { + Value = Ssw_RarGetBinPat( p, i, k ); + if ( Value == 0 ) + continue; + p->pPatCosts[k] += 1.0/(Value*Value); + } + } + // choose as many as there are words + Vec_IntClear( vInits ); + for ( i = 0; i < p->nFrames; i++ ) + { + // select the best + int iPatBest = -1; + double iCostBest = -ABC_INFINITY; + for ( k = 0; k < p->nWords * 32; k++ ) + if ( iCostBest < p->pPatCosts[k] ) + { + iCostBest = p->pPatCosts[k]; + iPatBest = k; + } + // remove from costs + assert( iPatBest >= 0 ); + p->pPatCosts[iPatBest] = -ABC_INFINITY; + // set the flops + Saig_ManForEachLo( p->pAig, pObj, k ) + { + pData = Vec_PtrEntry( p->vSimInfo, Aig_ObjId(pObj) ); + Vec_IntPush( vInits, Aig_InfoHasBit(pData, iPatBest) ); + } + } + assert( Vec_IntSize(vInits) == Aig_ManRegNum(p->pAig) * p->nFrames ); +} + + +/**Function************************************************************* + + Synopsis [Performs fraiging for one node.] + + Description [Returns the fraiged node.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Ssw_RarFindStartingState( Aig_Man_t * pAig, Abc_Cex_t * pCex ) +{ + Vec_Int_t * vInit; + Aig_Obj_t * pObj, * pObjLi; + int f, i, iBit; + // assign register outputs + Saig_ManForEachLi( pAig, pObj, i ) + pObj->fMarkB = 0; + // simulate the timeframes + iBit = pCex->nRegs; + for ( f = 0; f <= pCex->iFrame; f++ ) + { + // set the PI simulation information + Aig_ManConst1(pAig)->fMarkB = 1; + Saig_ManForEachPi( pAig, pObj, i ) + pObj->fMarkB = Aig_InfoHasBit( pCex->pData, iBit++ ); + Saig_ManForEachLiLo( pAig, pObjLi, pObj, i ) + pObj->fMarkB = pObjLi->fMarkB; + // simulate internal nodes + Aig_ManForEachNode( pAig, pObj, i ) + pObj->fMarkB = ( Aig_ObjFanin0(pObj)->fMarkB ^ Aig_ObjFaninC0(pObj) ) + & ( Aig_ObjFanin1(pObj)->fMarkB ^ Aig_ObjFaninC1(pObj) ); + // assign the COs + Aig_ManForEachPo( pAig, pObj, i ) + pObj->fMarkB = ( Aig_ObjFanin0(pObj)->fMarkB ^ Aig_ObjFaninC0(pObj) ); + } + assert( iBit == pCex->nBits ); + // check that the output failed as expected -- cannot check because it is not an SRM! +// pObj = Aig_ManPo( pAig, pCex->iPo ); +// if ( pObj->fMarkB != 1 ) +// printf( "The counter-example does not refine the output.\n" ); + // record the new pattern + vInit = Vec_IntAlloc( Saig_ManRegNum(pAig) ); + Saig_ManForEachLo( pAig, pObj, i ) + Vec_IntPush( vInit, pObj->fMarkB ); + return vInit; +} + +/**Function************************************************************* + + Synopsis [Filter equivalence classes of nodes.] + + Description [Unrolls at most nFramesMax frames. Works with nConfMax + conflicts until the first undefined SAT call. Verbose prints the message.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Ssw_RarSignalFilter( Aig_Man_t * pAig, int nWords, int nFrames, int nBinSize, int nRounds, Abc_Cex_t * pCex, int fLatchOnly, int fVerbose ) +{ + Ssw_RarMan_t * p; + int r, i, k, clkTotal = clock(); + assert( Aig_ManRegNum(pAig) > 0 ); + assert( Aig_ManConstrNum(pAig) == 0 ); + // consider the case of empty AIG + if ( Aig_ManNodeNum(pAig) == 0 ) + return; + // reset random numbers + Aig_ManRandom( 1 ); + // create manager + p = Ssw_RarManStart( pAig, nWords, nFrames, nBinSize, fVerbose ); + // create trivial equivalence classes with all nodes being candidates for constant 1 + if ( pAig->pReprs == NULL ) + p->ppClasses = Ssw_ClassesPrepareSimple( pAig, fLatchOnly, 0 ); + else + p->ppClasses = Ssw_ClassesPrepareFromReprs( pAig ); + Ssw_ClassesSetData( p->ppClasses, NULL, NULL, Ssw_SmlObjIsConstWord, Ssw_SmlObjsAreEqualWord ); + // compute starting state if needed + assert( p->vInits == NULL ); + if ( pCex ) + p->vInits = Ssw_RarFindStartingState( pAig, pCex ); + else + p->vInits = Vec_IntStart( Aig_ManRegNum(pAig) ); + // duplicate the array + for ( i = 1; i < nFrames; i++ ) + for ( k = 0; k < Aig_ManRegNum(pAig); k++ ) + Vec_IntPush( p->vInits, Vec_IntEntry(p->vInits, k) ); + assert( Vec_IntSize(p->vInits) == Aig_ManRegNum(pAig) * nFrames ); + // initialize simulation manager + p->pSml = Ssw_SmlStart( pAig, 0, nFrames, nWords ); + p->vSimInfo = Ssw_SmlSimDataPointers( p->pSml ); + Ssw_SmlInitializeSpecial( p->pSml, p->vInits ); + // print the stats + if ( fVerbose ) + { + printf( "Initial : " ); + Ssw_ClassesPrint( p->ppClasses, 0 ); + } + // refine classes using BMC + for ( r = 0; r < nRounds; r++ ) + { + // start filtering equivalence classes + if ( Ssw_ClassesCand1Num(p->ppClasses) == 0 && Ssw_ClassesClassNum(p->ppClasses) == 0 ) + { + printf( "All equivalences are refined away.\n" ); + break; + } + // simulate + Ssw_SmlSimulateOne( p->pSml ); + // check equivalence classes + Ssw_ClassesRefineConst1( p->ppClasses, 1 ); + Ssw_ClassesRefine( p->ppClasses, 1 ); + // printout + if ( fVerbose ) + { + printf( "Round %3d: ", r ); + Ssw_ClassesPrint( p->ppClasses, 0 ); + } + // get initialization patterns + Ssw_RarUpdateCounters( p ); + Ssw_RarTransferPatterns( p, p->vInits ); + Ssw_SmlInitializeSpecial( p->pSml, p->vInits ); + +/* + // check timeout + if ( TimeLimit && ((float)TimeLimit <= (float)(clock()-clkTotal)/(float)(CLOCKS_PER_SEC)) ) + { + printf( "Reached timeout (%d seconds).\n", TimeLimit ); + break; + } +*/ + } + // cleanup + Ssw_RarManStop( p ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/aig/ssw/sswSim.c b/src/aig/ssw/sswSim.c index 83457d53..37fc16af 100644 --- a/src/aig/ssw/sswSim.c +++ b/src/aig/ssw/sswSim.c @@ -568,6 +568,27 @@ void Ssw_SmlObjAssignConst( Ssw_Sml_t * p, Aig_Obj_t * pObj, int fConst1, int iF pSims[i] = fConst1? ~(unsigned)0 : 0; } +/**Function************************************************************* + + Synopsis [Assigns constant patterns to the PI node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Ssw_SmlObjAssignConstWord( Ssw_Sml_t * p, Aig_Obj_t * pObj, int fConst1, int iFrame, int iWord ) +{ + unsigned * pSims; + assert( iFrame < p->nFrames ); + assert( iWord < p->nWordsFrame ); + assert( Aig_ObjIsPi(pObj) ); + pSims = Ssw_ObjSim( p, pObj->Id ) + p->nWordsFrame * iFrame; + pSims[iWord] = fConst1? ~(unsigned)0 : 0; +} + /**Function************************************************************* Synopsis [Assigns constant patterns to the PI node.] @@ -893,6 +914,33 @@ void Ssw_SmlInitialize( Ssw_Sml_t * p, int fInit ) } } +/**Function************************************************************* + + Synopsis [Assings random simulation info for the PIs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Ssw_SmlInitializeSpecial( Ssw_Sml_t * p, Vec_Int_t * vInit ) +{ + Aig_Obj_t * pObj; + int Entry, i, k, nRegs; + nRegs = Aig_ManRegNum(p->pAig); + assert( nRegs > 0 ); + assert( nRegs <= Aig_ManPiNum(p->pAig) ); + assert( Vec_IntSize(vInit) == nRegs * p->nFrames ); + // assign random info for primary inputs + Saig_ManForEachPi( p->pAig, pObj, i ) + Ssw_SmlAssignRandom( p, pObj ); + // assign the initial state for the latches + Vec_IntForEachEntry( vInit, Entry, i ) + Ssw_SmlObjAssignConstWord( p, Saig_ManLo(p->pAig, i % nRegs), Entry, 0, i / nRegs ); +} + /**Function************************************************************* Synopsis [Assings random simulation info for the PIs.] @@ -1121,6 +1169,28 @@ void Ssw_SmlClean( Ssw_Sml_t * p ) memset( p->pData, 0, sizeof(unsigned) * Aig_ManObjNumMax(p->pAig) * p->nWordsTotal ); } +/**Function************************************************************* + + Synopsis [Get simulation data.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * Ssw_SmlSimDataPointers( Ssw_Sml_t * p ) +{ + Vec_Ptr_t * vSimInfo; + Aig_Obj_t * pObj; + int i; + vSimInfo = Vec_PtrStart( Aig_ManObjNumMax(p->pAig) ); + Aig_ManForEachObj( p->pAig, pObj, i ) + Vec_PtrWriteEntry( vSimInfo, i, Ssw_ObjSim(p, i) ); + return vSimInfo; +} + /**Function************************************************************* Synopsis [Deallocates simulation manager.] -- cgit v1.2.3