From c0aa9b6a5dc680af2c9509924a869448ed841150 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 21 Jul 2014 13:49:25 -0700 Subject: Adding new command &sopb for resource-aware SOP balancing. --- src/aig/gia/gia.h | 7 +- src/aig/gia/giaIf.c | 26 ++++++ src/aig/gia/giaSopb.c | 230 ++++++++++++++++++++++++++++++++++++++++++++++++ src/aig/gia/module.make | 1 + 4 files changed, 263 insertions(+), 1 deletion(-) create mode 100644 src/aig/gia/giaSopb.c (limited to 'src/aig/gia') diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index 6fc30367..b641da7f 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -966,13 +966,15 @@ static inline int Gia_ObjLutIsMux( Gia_Man_t * p, int Id ) { re for ( i = Vec_IntSize(p->vCis) - 1; (i >= 0) && ((pObj) = Gia_ManCi(p, i)); i-- ) #define Gia_ManForEachCo( p, pObj, i ) \ for ( i = 0; (i < Vec_IntSize(p->vCos)) && ((pObj) = Gia_ManCo(p, i)); i++ ) +#define Gia_ManForEachCoVec( vVec, p, pObj, i ) \ + for ( i = 0; (i < Vec_IntSize(vVec)) && ((pObj) = Gia_ManCo(p, Vec_IntEntry(vVec,i))); i++ ) #define Gia_ManForEachCoId( p, Id, i ) \ for ( i = 0; (i < Vec_IntSize(p->vCos)) && ((Id) = Gia_ObjId(p, Gia_ManCo(p, i))); i++ ) #define Gia_ManForEachCoReverse( p, pObj, i ) \ for ( i = Vec_IntSize(p->vCos) - 1; (i >= 0) && ((pObj) = Gia_ManCo(p, i)); i-- ) #define Gia_ManForEachCoDriver( p, pObj, i ) \ for ( i = 0; (i < Vec_IntSize(p->vCos)) && ((pObj) = Gia_ObjFanin0(Gia_ManCo(p, i))); i++ ) -#define Gia_ManForEachCoDriverId( p, DriverId, i ) \ +#define Gia_ManForEachCoDriverId( p, DriverId, i ) \ for ( i = 0; (i < Vec_IntSize(p->vCos)) && (((DriverId) = Gia_ObjFaninId0p(p, Gia_ManCo(p, i))), 1); i++ ) #define Gia_ManForEachPi( p, pObj, i ) \ for ( i = 0; (i < Gia_ManPiNum(p)) && ((pObj) = Gia_ManCi(p, i)); i++ ) @@ -1165,6 +1167,7 @@ extern void Gia_ManSetIfParsDefault( void * pIfPars ); extern void Gia_ManMappingVerify( Gia_Man_t * p ); extern void Gia_ManTransferMapping( Gia_Man_t * pGia, Gia_Man_t * p ); extern Gia_Man_t * Gia_ManPerformMapping( Gia_Man_t * p, void * pIfPars, int fNormalized ); +extern Gia_Man_t * Gia_ManPerformSopBalance( Gia_Man_t * p, int nCutNum, int nRelaxRatio, int fVerbose ); /*=== giaJf.c ===========================================================*/ extern void Jf_ManSetDefaultPars( Jf_Par_t * pPars ); extern Gia_Man_t * Jf_ManPerformMapping( Gia_Man_t * pGia, Jf_Par_t * pPars ); @@ -1237,6 +1240,8 @@ extern Gia_Man_t * Gia_ManSeqStructSweep( Gia_Man_t * p, int fConst, int /*=== giaShrink.c ===========================================================*/ extern Gia_Man_t * Gia_ManMapShrink4( Gia_Man_t * p, int fKeepLevel, int fVerbose ); extern Gia_Man_t * Gia_ManMapShrink6( Gia_Man_t * p, int nFanoutMax, int fKeepLevel, int fVerbose ); +/*=== giaSopb.c ============================================================*/ +extern Gia_Man_t * Gia_ManPerformSopBalanceWin( Gia_Man_t * p, int LevelMax, int nLevelRatio, int nCutNum, int nRelaxRatio, int fVerbose ); /*=== giaSort.c ============================================================*/ extern int * Gia_SortFloats( float * pArray, int * pPerm, int nSize ); /*=== giaSim.c ============================================================*/ diff --git a/src/aig/gia/giaIf.c b/src/aig/gia/giaIf.c index 20204798..a3ebf305 100644 --- a/src/aig/gia/giaIf.c +++ b/src/aig/gia/giaIf.c @@ -1732,6 +1732,32 @@ Gia_Man_t * Gia_ManPerformMapping( Gia_Man_t * p, void * pp, int fNormalized ) Gia_ManStop( p ); return pNew; } +Gia_Man_t * Gia_ManPerformSopBalance( Gia_Man_t * p, int nCutNum, int nRelaxRatio, int fVerbose ) +{ + Gia_Man_t * pNew; + If_Man_t * pIfMan; + If_Par_t Pars, * pPars = &Pars; + If_ManSetDefaultPars( pPars ); + pPars->nCutsMax = nCutNum; + pPars->nRelaxRatio = nRelaxRatio; + pPars->fVerbose = fVerbose; + pPars->nLutSize = 6; + pPars->fDelayOpt = 1; + pPars->fCutMin = 1; + pPars->fTruth = 1; + pPars->fExpRed = 0; + // perform mapping + pIfMan = Gia_ManToIf( p, pPars ); + If_ManPerformMapping( pIfMan ); + pNew = Gia_ManFromIfAig( pIfMan ); + If_ManStop( pIfMan ); + // transfer name + assert( pNew->pName == NULL ); + pNew->pName = Abc_UtilStrsav( p->pName ); + pNew->pSpec = Abc_UtilStrsav( p->pSpec ); + Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) ); + return pNew; +} /**Function************************************************************* diff --git a/src/aig/gia/giaSopb.c b/src/aig/gia/giaSopb.c new file mode 100644 index 00000000..28e01c8c --- /dev/null +++ b/src/aig/gia/giaSopb.c @@ -0,0 +1,230 @@ +/**CFile**************************************************************** + + FileName [giaSopb.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Scalable AIG package.] + + Synopsis [SOP balancing for a window.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: giaSopb.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "gia.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManHighlight_rec( Gia_Man_t * p, int iObj ) +{ + Gia_Obj_t * pObj; + if ( Gia_ObjIsTravIdCurrentId(p, iObj) ) + return; + Gia_ObjSetTravIdCurrentId(p, iObj); + pObj = Gia_ManObj( p, iObj ); + if ( Gia_ObjIsAnd(pObj) ) + Gia_ManHighlight_rec( p, Gia_ObjFaninId0(pObj, iObj) ); + if ( Gia_ObjIsAnd(pObj) ) + Gia_ManHighlight_rec( p, Gia_ObjFaninId1(pObj, iObj) ); +} +void Gia_ManPrepareWin( Gia_Man_t * p, Vec_Int_t * vOuts, Vec_Int_t ** pvPis, Vec_Int_t ** pvPos, Vec_Int_t ** pvAnds ) +{ + Gia_Obj_t * pObj; + int i; + // mark the section + Gia_ManIncrementTravId( p ); + Gia_ManForEachCoVec( vOuts, p, pObj, i ) + Gia_ManHighlight_rec( p, Gia_ObjFaninId0p(p, pObj) ); + // mark fanins of the outside area + Gia_ManCleanMark0( p ); + Gia_ManForEachObj1( p, pObj, i ) + { + if ( Gia_ObjIsCi(pObj) ) + continue; + if ( Gia_ObjIsAnd(pObj) && !Gia_ObjIsTravIdCurrentId(p, i) ) + continue; + Gia_ObjFanin0(pObj)->fMark0 = 1; + if ( Gia_ObjIsAnd(pObj) ) + Gia_ObjFanin1(pObj)->fMark0 = 1; + } + // collect pointed nodes + *pvPis = Vec_IntAlloc( 1000 ); + *pvPos = Vec_IntAlloc( 1000 ); + *pvAnds = Vec_IntAlloc( 1000 ); + Gia_ManForEachObj1( p, pObj, i ) + { + if ( !Gia_ObjIsTravIdCurrentId(p, i) ) + continue; + if ( Gia_ObjIsCi(pObj) ) + Vec_IntPush( *pvPis, i ); + else if ( pObj->fMark0 ) + Vec_IntPush( *pvPos, i ); + if ( Gia_ObjIsAnd(pObj) ) + Vec_IntPush( *pvAnds, i ); + } + Gia_ManCleanMark0( p ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManExtractWin( Gia_Man_t * p, Vec_Int_t * vOuts ) +{ + Vec_Int_t * vPis, * vPos, * vAnds; + Gia_Man_t * pNew; + Gia_Obj_t * pObj; + int i; + Gia_ManPrepareWin( p, vOuts, &vPis, &vPos, &vAnds ); + // create AIG + pNew = Gia_ManStart( Vec_IntSize(vPis) + Vec_IntSize(vPos) + Vec_IntSize(vAnds) + 1 ); + pNew->pName = Abc_UtilStrsav( p->pName ); + Gia_ManConst0(p)->Value = 0; + Gia_ManForEachObjVec( vPis, p, pObj, i ) + pObj->Value = Gia_ManAppendCi( pNew ); + Gia_ManForEachObjVec( vAnds, p, pObj, i ) + pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + Gia_ManForEachObjVec( vPos, p, pObj, i ) + Gia_ManAppendCo( pNew, pObj->Value ); + Vec_IntFree( vPis ); + Vec_IntFree( vPos ); + Vec_IntFree( vAnds ); + return pNew; +} +Gia_Man_t * Gia_ManInsertWin( Gia_Man_t * p, Vec_Int_t * vOuts, Gia_Man_t * pWin ) +{ + Vec_Int_t * vPos, * vPis, * vAnds; + Gia_Man_t * pNew, * pTemp; + Gia_Obj_t * pObj; + int i; + Gia_ManPrepareWin( p, vOuts, &vPis, &vPos, &vAnds ); + // create AIG + pNew = Gia_ManStart( Gia_ManObjNum(p) - Vec_IntSize(vAnds) + Gia_ManAndNum(pWin) ); + pNew->pName = Abc_UtilStrsav( p->pName ); + pNew->pSpec = Abc_UtilStrsav( p->pSpec ); + // inputs + Gia_ManConst0(p)->Value = 0; + Gia_ManForEachCi( p, pObj, i ) + pObj->Value = Gia_ManAppendCi( pNew ); + Gia_ManConst0(pWin)->Value = 0; + Gia_ManForEachCi( pWin, pObj, i ) + pObj->Value = Gia_ManObj(p, Vec_IntEntry(vPis, i))->Value; + // internal nodes + Gia_ManHashAlloc( pNew ); + Gia_ManForEachAnd( pWin, pObj, i ) + pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + Gia_ManForEachCo( pWin, pObj, i ) + Gia_ManObj( p, Vec_IntEntry(vPos, i) )->Value = Gia_ObjFanin0Copy(pObj); + Gia_ManForEachAnd( p, pObj, i ) + if ( !Gia_ObjIsTravIdCurrentId(p, i) ) + pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ); + Gia_ManForEachCo( p, pObj, i ) + Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) ); + Gia_ManHashStop( pNew ); + // cleanup + Vec_IntFree( vPis ); + Vec_IntFree( vPos ); + Vec_IntFree( vAnds ); + pNew = Gia_ManCleanup( pTemp = pNew ); + Gia_ManStop( pTemp ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Gia_ManFindLatest( Gia_Man_t * p, int LevelMax ) +{ + Vec_Int_t * vOuts; + Gia_Obj_t * pObj; + int i; + vOuts = Vec_IntAlloc( 1000 ); + Gia_ManForEachCo( p, pObj, i ) + if ( Gia_ObjLevel(p, pObj) > LevelMax ) + Vec_IntPush( vOuts, i ); + return vOuts; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManPerformSopBalanceWin( Gia_Man_t * p, int LevelMax, int nLevelRatio, int nCutNum, int nRelaxRatio, int fVerbose ) +{ + Vec_Int_t * vOuts; + Gia_Man_t * pNew, * pWin, * pWinNew; + int nLevels = Gia_ManLevelNum( p ); + if ( nLevelRatio ) + LevelMax = (int)((1.0 - 0.01 * nLevelRatio) * nLevels); +//printf( "Using LevelMax = %d.\n", LevelMax ); + vOuts = Gia_ManFindLatest( p, LevelMax ); + if ( Vec_IntSize(vOuts) == 0 ) + { + Vec_IntFree( vOuts ); + return Gia_ManDup( p ); + } + pWin = Gia_ManExtractWin( p, vOuts ); + pWinNew = Gia_ManPerformSopBalance( pWin, nCutNum, nRelaxRatio, fVerbose ); + Gia_ManStop( pWin ); + pNew = Gia_ManInsertWin( p, vOuts, pWinNew ); + Gia_ManStop( pWinNew ); + Vec_IntFree( vOuts ); + return pNew; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/aig/gia/module.make b/src/aig/gia/module.make index 471b750a..a8ebc836 100644 --- a/src/aig/gia/module.make +++ b/src/aig/gia/module.make @@ -51,6 +51,7 @@ SRC += src/aig/gia/giaAig.c \ src/aig/gia/giaShrink7.c \ src/aig/gia/giaSim.c \ src/aig/gia/giaSim2.c \ + src/aig/gia/giaSopb.c \ src/aig/gia/giaSort.c \ src/aig/gia/giaSpeedup.c \ src/aig/gia/giaStg.c \ -- cgit v1.2.3