/**CFile****************************************************************
FileName [gia.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Scalable AIG package.]
Synopsis []
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: gia.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "gia.h"
ABC_NAMESPACE_IMPL_START
/*
The code is based on the paper by F. A. Aloul, I. L. Markov, and K. A. Sakallah.
"FORCE: A Fast and Easy-To-Implement Variable-Ordering Heuristic", Proc. GLSVLSI�03.
http://www.eecs.umich.edu/~imarkov/pubs/conf/glsvlsi03-force.pdf
*/
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
typedef struct Frc_Obj_t_ Frc_Obj_t;
struct Frc_Obj_t_
{
unsigned fCi : 1; // terminal node CI
unsigned fCo : 1; // terminal node CO
unsigned fMark0 : 1; // first user-controlled mark
unsigned fMark1 : 1; // second user-controlled mark
unsigned nFanins : 28; // the number of fanins
unsigned nFanouts; // the number of fanouts
unsigned iFanout; // the current number of fanouts
int hHandle; // the handle of the node
int pPlace; // the placement of each node
union {
float fEdgeCenter; // center-of-gravity of the edge
unsigned iFanin;
};
int Fanios[0]; // the array of fanins/fanouts
};
typedef struct Frc_Man_t_ Frc_Man_t;
struct Frc_Man_t_
{
Gia_Man_t * pGia; // the original AIG manager
Vec_Int_t * vCis; // the vector of CIs (PIs + LOs)
Vec_Int_t * vCos; // the vector of COs (POs + LIs)
int nObjs; // the number of objects
int nRegs; // the number of registers
int * pObjData; // the array containing data for objects
int nObjData; // the size of array to store the logic network
int fVerbose; // verbose output flag
int nCutCur; // current cut
int nCutMax; // max cut seen
};
static inline int Frc_ManRegNum( Frc_Man_t * p ) { return p->nRegs; }
static inline int Frc_ManCiNum( Frc_Man_t * p ) { return Vec_IntSize(p->vCis); }
static inline int Frc_ManCoNum( Frc_Man_t * p ) { return Vec_IntSize(p->vCos); }
static inline int Frc_ManPiNum( Frc_Man_t * p ) { return Vec_IntSize(p->vCis) - p->nRegs; }
static inline int Frc_ManPoNum( Frc_Man_t * p ) { return Vec_IntSize(p->vCos) - p->nRegs; }
static inline int Frc_ManObjNum( Frc_Man_t * p ) { return p->nObjs; }
static inline int Frc_ManNodeNum( Frc_Man_t * p ) { return p->nObjs - Vec_IntSize(p->vCis) - Vec_IntSize(p->vCos); }
static inline Frc_Obj_t * Frc_ManObj( Frc_Man_t * p, int hHandle ) { return (Frc_Obj_t *)(p->pObjData + hHandle); }
static inline Frc_Obj_t * Frc_ManCi( Frc_Man_t * p, int i ) { return Frc_ManObj( p, Vec_IntEntry(p->vCis,i) ); }
static inline Frc_Obj_t * Frc_ManCo( Frc_Man_t * p, int i ) { return Frc_ManObj( p, Vec_IntEntry(p->vCos,i) ); }
static inline int Frc_ObjIsTerm( Frc_Obj_t * pObj ) { return pObj->fCi || pObj->fCo; }
static inline int Frc_ObjIsCi( Frc_Obj_t * pObj ) { return pObj->fCi; }
static inline int Frc_ObjIsCo( Frc_Obj_t * pObj ) { return pObj->fCo; }
static inline int Frc_ObjIsPi( Frc_Obj_t * pObj ) { return pObj->fCi && pObj->nFanins == 0; }
static inline int Frc_ObjIsPo( Frc_Obj_t * pObj ) { return pObj->fCo && pObj->nFanouts == 0; }
static inline int Frc_ObjIsNode( Frc_Obj_t * pObj ) { return!Frc_ObjIsTerm(pObj) && pObj->nFanins > 0; }
static inline int Frc_ObjIsConst0( Frc_Obj_t * pObj ) { return!Frc_ObjIsTerm(pObj) && pObj->nFanins == 0; }
static inline int Frc_ObjSize( Frc_Obj_t * pObj ) { return sizeof(Frc_Obj_t) / 4 + pObj->nFanins + pObj->nFanouts; }
static inline int Frc_ObjFaninNum( Frc_Obj_t * pObj ) { return pObj->nFanins; }
static inline int Frc_ObjFanoutNum( Frc_Obj_t * pObj ) { return pObj->nFanouts; }
static inline Frc_Obj_t * Frc_ObjFanin( Frc_Obj_t * pObj, int i ) { return (Frc_Obj_t *)(((int *)pObj) - pObj->Fanios[i]); }
static inline Frc_Obj_t * Frc_ObjFanout( Frc_Obj_t * pObj, int i ) { return (Frc_Obj_t *)(((int *)pObj) + pObj->Fanios[pObj->nFanins+i]); }
#define Frc_ManForEachObj( p, pObj, i ) \
for ( i = 0; (i < p->nObjData) && (pObj = Frc_ManObj(p,i)); i += Frc_ObjSize(pObj) )
#define Frc_ManForEachObjVec( vVec, p, pObj, i ) \
for ( i = 0; (i < Vec_IntSize(vVec)) && ((pObj) = Frc_ManObj(p, Vec_IntEntry(vVec,i))); i++ )
#define Frc_ManForEachNode( p, pObj, i ) \
for ( i = 0; (i < p->nObjData) && (pObj = Frc_ManObj(p,i)); i += Frc_ObjSize(pObj) ) if ( Frc_ObjIsTerm(pObj) ) {} else
#define Frc_ManForEachCi( p, pObj, i ) \
for ( i = 0; (i < Vec_IntSize(p->vCis)) && (pObj = Frc_ManObj(p,Vec_IntEntry(p->vCis,i))); i++ )
#define Frc_ManForEachCo( p, pObj, i ) \
for ( i = 0; (i < Vec_IntSize(p->vCos)) && (pObj = Frc_ManObj(p,Vec_IntEntry(p->vCos,i))); i++ )
#define Frc_ObjForEachFanin( pObj, pNext, i ) \
for ( i = 0; (i < (int)pObj->nFanins) && (pNext = Frc_ObjFanin(pObj,i)); i++ )
#define Frc_ObjForEachFaninReverse( pObj, pNext, i ) \
for ( i = (int)pObj->nFanins - 1; (i >= 0) && (pNext = Frc_ObjFanin(pObj,i)); i-- )
#define Frc_ObjForEachFanout( pObj, pNext, i ) \
for ( i = 0; (i < (int)pObj->nFanouts) && (pNext = Frc_ObjFanout(pObj,i)); i++ )
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Creates fanin/fanout pair.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ObjAddFanin( Frc_Obj_t * pObj, Frc_Obj_t * pFanin )
{
assert( pObj->iFanin < pObj->nFanins );
assert( pFanin->iFanout < pFanin->nFanouts );
pFanin->Fanios[pFanin->nFanins + pFanin->iFanout++] =
pObj->Fanios[pObj->iFanin++] = pObj->hHandle - pFanin->hHandle;
}
/**Function*************************************************************
Synopsis [Creates logic network isomorphic to the given AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Frc_Man_t * Frc_ManStartSimple( Gia_Man_t * pGia )
{
Frc_Man_t * p;
Frc_Obj_t * pObjLog, * pFanLog;
Gia_Obj_t * pObj;//, * pObjRi, * pObjRo;
int i, nNodes, hHandle = 0;
// prepare the AIG
Gia_ManCreateRefs( pGia );
// create logic network
p = ABC_CALLOC( Frc_Man_t, 1 );
p->pGia = pGia;
p->nRegs = Gia_ManRegNum(pGia);
p->vCis = Vec_IntAlloc( Gia_ManCiNum(pGia) );
p->vCos = Vec_IntAlloc( Gia_ManCoNum(pGia) );
p->nObjData = (sizeof(Frc_Obj_t) / 4) * Gia_ManObjNum(pGia) + 2 * (2 * Gia_ManAndNum(pGia) + Gia_ManCoNum(pGia));
p->pObjData = ABC_CALLOC( int, p->nObjData );
// create constant node
Gia_ManConst0(pGia)->Value = hHandle;
pObjLog = Frc_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = 0;
pObjLog->nFanouts = Gia_ObjRefNum( pGia, Gia_ManConst0(pGia) );
// count objects
hHandle += Frc_ObjSize( pObjLog );
nNodes = 1;
p->nObjs++;
// create the PIs
Gia_ManForEachCi( pGia, pObj, i )
{
// create PI object
pObj->Value = hHandle;
Vec_IntPush( p->vCis, hHandle );
pObjLog = Frc_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = 0;
pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
pObjLog->fCi = 0;
// count objects
hHandle += Frc_ObjSize( pObjLog );
p->nObjs++;
}
// create internal nodes
Gia_ManForEachAnd( pGia, pObj, i )
{
assert( Gia_ObjRefNum( pGia, pObj ) > 0 );
// create node object
pObj->Value = hHandle;
pObjLog = Frc_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = 2;
pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
// add fanins
pFanLog = Frc_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
Frc_ObjAddFanin( pObjLog, pFanLog );
pFanLog = Frc_ManObj( p, Gia_ObjValue(Gia_ObjFanin1(pObj)) );
Frc_ObjAddFanin( pObjLog, pFanLog );
// count objects
hHandle += Frc_ObjSize( pObjLog );
nNodes++;
p->nObjs++;
}
// create the POs
Gia_ManForEachCo( pGia, pObj, i )
{
// create PO object
pObj->Value = hHandle;
Vec_IntPush( p->vCos, hHandle );
pObjLog = Frc_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = 1;
pObjLog->nFanouts = 0;
pObjLog->fCo = 1;
// add fanins
pFanLog = Frc_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
Frc_ObjAddFanin( pObjLog, pFanLog );
// count objects
hHandle += Frc_ObjSize( pObjLog );
p->nObjs++;
}
// connect registers
// Gia_ManForEachRiRo( pGia, pObjRi, pObjRo, i )
// Frc_ObjAddFanin( Frc_ManObj(p,Gia_ObjValue(pObjRo)), Frc_ManObj(p,Gia_ObjValue(pObjRi)) );
assert( nNodes == Frc_ManNodeNum(p) );
assert( hHandle == p->nObjData );
if ( hHandle != p->nObjData )
printf( "Frc_ManStartSimple(): Fatal error in internal representation.\n" );
// make sure the fanin/fanout counters are correct
Gia_ManForEachObj( pGia, pObj, i )
{
if ( !~Gia_ObjValue(pObj) )
continue;
pObjLog = Frc_ManObj( p, Gia_ObjValue(pObj) );
assert( pObjLog->nFanins == pObjLog->iFanin );
assert( pObjLog->nFanouts == pObjLog->iFanout );
pObjLog->iFanin = pObjLog->iFanout = 0;
}
ABC_FREE( pGia->pRefs );
return p;
}
/**Function*************************************************************
Synopsis [Collect the fanin IDs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManCollectSuper_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSuper, Vec_Int_t * vVisit )
{
if ( pObj->fMark1 )
return;
pObj->fMark1 = 1;
Vec_IntPush( vVisit, Gia_ObjId(p, pObj) );
if ( pObj->fMark0 )
{
Vec_IntPush( vSuper, Gia_ObjId(p, pObj) );
return;
}
assert( Gia_ObjIsAnd(pObj) );
Frc_ManCollectSuper_rec( p, Gia_ObjFanin0(pObj), vSuper, vVisit );
Frc_ManCollectSuper_rec( p, Gia_ObjFanin1(pObj), vSuper, vVisit );
}
/**Function*************************************************************
Synopsis [Collect the fanin IDs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManCollectSuper( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSuper, Vec_Int_t * vVisit )
{
int Entry, i;
Vec_IntClear( vSuper );
Vec_IntClear( vVisit );
assert( pObj->fMark0 == 1 );
pObj->fMark0 = 0;
Frc_ManCollectSuper_rec( p, pObj, vSuper, vVisit );
pObj->fMark0 = 1;
Vec_IntForEachEntry( vVisit, Entry, i )
Gia_ManObj(p, Entry)->fMark1 = 0;
}
/**Function*************************************************************
Synopsis [Assigns references while removing the MUX/XOR ones.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManCreateRefsSpecial( Gia_Man_t * p )
{
Gia_Obj_t * pObj, * pFan0, * pFan1;
Gia_Obj_t * pObjC, * pObjD0, * pObjD1;
int i;
assert( p->pRefs == NULL );
Gia_ManCleanMark0( p );
Gia_ManCreateRefs( p );
Gia_ManForEachAnd( p, pObj, i )
{
assert( pObj->fMark0 == 0 );
pFan0 = Gia_ObjFanin0(pObj);
pFan1 = Gia_ObjFanin1(pObj);
// skip nodes whose fanins are PIs or are already marked
if ( Gia_ObjIsCi(pFan0) || pFan0->fMark0 ||
Gia_ObjIsCi(pFan1) || pFan1->fMark0 )
continue;
// skip nodes that are not MUX type
if ( !Gia_ObjIsMuxType(pObj) )
continue;
// the node is MUX type, mark it and its fanins
pObj->fMark0 = 1;
pFan0->fMark0 = 1;
pFan1->fMark0 = 1;
// deref the control
pObjC = Gia_ObjRecognizeMux( pObj, &pObjD1, &pObjD0 );
Gia_ObjRefDec( p, Gia_Regular(pObjC) );
if ( Gia_Regular(pObjD0) == Gia_Regular(pObjD1) )
Gia_ObjRefDec( p, Gia_Regular(pObjD0) );
}
Gia_ManForEachAnd( p, pObj, i )
assert( Gia_ObjRefNum(p, pObj) > 0 );
Gia_ManCleanMark0( p );
}
/**Function*************************************************************
Synopsis [Assigns references while removing the MUX/XOR ones.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManTransformRefs( Gia_Man_t * p, int * pnObjs, int * pnFanios )
{
Vec_Int_t * vSuper, * vVisit;
Gia_Obj_t * pObj, * pFanin;
int i, k, Counter;
assert( p->pRefs != NULL );
// mark nodes to be used in the logic network
Gia_ManCleanMark0( p );
Gia_ManConst0(p)->fMark0 = 1;
// mark the inputs
Gia_ManForEachCi( p, pObj, i )
pObj->fMark0 = 1;
// mark those nodes that have ref count more than 1
Gia_ManForEachAnd( p, pObj, i )
pObj->fMark0 = (Gia_ObjRefNum(p, pObj) > 1);
// mark the output drivers
Gia_ManForEachCoDriver( p, pObj, i )
pObj->fMark0 = 1;
// count the number of nodes
Counter = 0;
Gia_ManForEachObj( p, pObj, i )
Counter += pObj->fMark0;
*pnObjs = Counter + Gia_ManCoNum(p);
// reset the references
ABC_FREE( p->pRefs );
p->pRefs = ABC_CALLOC( int, Gia_ManObjNum(p) );
// reference from internal nodes
Counter = 0;
vSuper = Vec_IntAlloc( 100 );
vVisit = Vec_IntAlloc( 100 );
Gia_ManCleanMark1( p );
Gia_ManForEachAnd( p, pObj, i )
{
if ( pObj->fMark0 == 0 )
continue;
Frc_ManCollectSuper( p, pObj, vSuper, vVisit );
Gia_ManForEachObjVec( vSuper, p, pFanin, k )
{
assert( pFanin->fMark0 );
Gia_ObjRefInc( p, pFanin );
}
Counter += Vec_IntSize( vSuper );
}
Gia_ManCheckMark1( p );
Vec_IntFree( vSuper );
Vec_IntFree( vVisit );
// reference from outputs
Gia_ManForEachCoDriver( p, pObj, i )
{
assert( pObj->fMark0 );
Gia_ObjRefInc( p, pObj );
}
*pnFanios = Counter + Gia_ManCoNum(p);
}
/**Function*************************************************************
Synopsis [Creates logic network isomorphic to the given AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Frc_Man_t * Frc_ManStart( Gia_Man_t * pGia )
{
Frc_Man_t * p;
Frc_Obj_t * pObjLog, * pFanLog;
Gia_Obj_t * pObj, * pFanin;//, * pObjRi, * pObjRo;
Vec_Int_t * vSuper, * vVisit;
int nObjs, nFanios, nNodes = 0;
int i, k, hHandle = 0;
// prepare the AIG
// Gia_ManCreateRefs( pGia );
Frc_ManCreateRefsSpecial( pGia );
Frc_ManTransformRefs( pGia, &nObjs, &nFanios );
Gia_ManFillValue( pGia );
// create logic network
p = ABC_CALLOC( Frc_Man_t, 1 );
p->pGia = pGia;
p->nRegs = Gia_ManRegNum(pGia);
p->vCis = Vec_IntAlloc( Gia_ManCiNum(pGia) );
p->vCos = Vec_IntAlloc( Gia_ManCoNum(pGia) );
p->nObjData = (sizeof(Frc_Obj_t) / 4) * nObjs + 2 * nFanios;
p->pObjData = ABC_CALLOC( int, p->nObjData );
// create constant node
Gia_ManConst0(pGia)->Value = hHandle;
pObjLog = Frc_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = 0;
pObjLog->nFanouts = Gia_ObjRefNum( pGia, Gia_ManConst0(pGia) );
// count objects
hHandle += Frc_ObjSize( pObjLog );
nNodes++;
p->nObjs++;
// create the PIs
Gia_ManForEachCi( pGia, pObj, i )
{
// create PI object
pObj->Value = hHandle;
Vec_IntPush( p->vCis, hHandle );
pObjLog = Frc_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = 0;
pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
pObjLog->fCi = 1;
// count objects
hHandle += Frc_ObjSize( pObjLog );
p->nObjs++;
}
// create internal nodes
vSuper = Vec_IntAlloc( 100 );
vVisit = Vec_IntAlloc( 100 );
Gia_ManForEachAnd( pGia, pObj, i )
{
if ( pObj->fMark0 == 0 )
{
assert( Gia_ObjRefNum( pGia, pObj ) == 0 );
continue;
}
assert( Gia_ObjRefNum( pGia, pObj ) > 0 );
Frc_ManCollectSuper( pGia, pObj, vSuper, vVisit );
// create node object
pObj->Value = hHandle;
pObjLog = Frc_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = Vec_IntSize( vSuper );
pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
// add fanins
Gia_ManForEachObjVec( vSuper, pGia, pFanin, k )
{
pFanLog = Frc_ManObj( p, Gia_ObjValue(pFanin) );
Frc_ObjAddFanin( pObjLog, pFanLog );
}
// count objects
hHandle += Frc_ObjSize( pObjLog );
nNodes++;
p->nObjs++;
}
Vec_IntFree( vSuper );
Vec_IntFree( vVisit );
// create the POs
Gia_ManForEachCo( pGia, pObj, i )
{
// create PO object
pObj->Value = hHandle;
Vec_IntPush( p->vCos, hHandle );
pObjLog = Frc_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = 1;
pObjLog->nFanouts = 0;
pObjLog->fCo = 1;
// add fanins
pFanLog = Frc_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
Frc_ObjAddFanin( pObjLog, pFanLog );
// count objects
hHandle += Frc_ObjSize( pObjLog );
p->nObjs++;
}
// connect registers
// Gia_ManForEachRiRo( pGia, pObjRi, pObjRo, i )
// Frc_ObjAddFanin( Frc_ManObj(p,Gia_ObjValue(pObjRo)), Frc_ManObj(p,Gia_ObjValue(pObjRi)) );
Gia_ManCleanMark0( pGia );
assert( nNodes == Frc_ManNodeNum(p) );
assert( nObjs == p->nObjs );
assert( hHandle == p->nObjData );
if ( hHandle != p->nObjData )
printf( "Frc_ManStart(): Fatal error in internal representation.\n" );
// make sure the fanin/fanout counters are correct
Gia_ManForEachObj( pGia, pObj, i )
{
if ( !~Gia_ObjValue(pObj) )
continue;
pObjLog = Frc_ManObj( p, Gia_ObjValue(pObj) );
assert( pObjLog->nFanins == pObjLog->iFanin );
assert( pObjLog->nFanouts == pObjLog->iFanout );
pObjLog->iFanin = pObjLog->iFanout = 0;
}
ABC_FREE( pGia->pRefs );
return p;
}
/**Function*************************************************************
Synopsis [Creates logic network isomorphic to the given AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManPrintStats( Frc_Man_t * p )
{
// if ( p->pName )
// printf( "%8s : ", p->pName );
printf( "i/o =%7d/%7d ", Frc_ManPiNum(p), Frc_ManPoNum(p) );
if ( Frc_ManRegNum(p) )
printf( "ff =%7d ", Frc_ManRegNum(p) );
printf( "node =%8d ", Frc_ManNodeNum(p) );
printf( "obj =%8d ", Frc_ManObjNum(p) );
// printf( "lev =%5d ", Frc_ManLevelNum(p) );
// printf( "cut =%5d ", Frc_ManCrossCut(p) );
printf( "mem =%5.2f MB", 4.0*p->nObjData/(1<<20) );
// printf( "obj =%5d ", Frc_ManObjNum(p) );
printf( "\n" );
}
/**Function*************************************************************
Synopsis [Creates logic network isomorphic to the given AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManStop( Frc_Man_t * p )
{
Vec_IntFree( p->vCis );
Vec_IntFree( p->vCos );
ABC_FREE( p->pObjData );
ABC_FREE( p );
}
/**Function*************************************************************
Synopsis [Computes cross cut size for the given order of POs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Frc_ManCrossCut_rec( Frc_Man_t * p, Frc_Obj_t * pObj )
{
assert( pObj->iFanout > 0 );
if ( pObj->iFanout-- == pObj->nFanouts )
{
Frc_Obj_t * pFanin;
int i;
p->nCutCur++;
p->nCutMax = Abc_MaxInt( p->nCutMax, p->nCutCur );
if ( !Frc_ObjIsCi(pObj) )
Frc_ObjForEachFanin( pObj, pFanin, i )
p->nCutCur -= Frc_ManCrossCut_rec( p, pFanin );
}
return pObj->iFanout == 0;
}
/**Function*************************************************************
Synopsis [Computes cross cut size for the given order of POs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Frc_ManCrossCut2_rec( Frc_Man_t * p, Frc_Obj_t * pObj )
{
assert( pObj->iFanout > 0 );
if ( pObj->iFanout-- == pObj->nFanouts )
{
Frc_Obj_t * pFanin;
int i;
p->nCutCur++;
p->nCutMax = Abc_MaxInt( p->nCutMax, p->nCutCur );
if ( !Frc_ObjIsCi(pObj) )
Frc_ObjForEachFaninReverse( pObj, pFanin, i )
p->nCutCur -= Frc_ManCrossCut2_rec( p, pFanin );
}
return pObj->iFanout == 0;
}
/**Function*************************************************************
Synopsis [Computes cross cut size for the given order of POs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Frc_ManCrossCut( Frc_Man_t * p, Vec_Int_t * vOrder, int fReverse )
{
Frc_Obj_t * pObj;
int i;
assert( Vec_IntSize(vOrder) == Frc_ManCoNum(p) );
p->nCutCur = 0;
p->nCutMax = 0;
Frc_ManForEachObj( p, pObj, i )
pObj->iFanout = pObj->nFanouts;
Frc_ManForEachObjVec( vOrder, p, pObj, i )
{
assert( Frc_ObjIsCo(pObj) );
if ( fReverse )
p->nCutCur -= Frc_ManCrossCut2_rec( p, Frc_ObjFanin(pObj,0) );
else
p->nCutCur -= Frc_ManCrossCut_rec( p, Frc_ObjFanin(pObj,0) );
}
assert( p->nCutCur == 0 );
// Frc_ManForEachObj( p, pObj, i )
// assert( pObj->iFanout == 0 );
return p->nCutMax;
}
/**Function*************************************************************
Synopsis [Collects CO handles.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Int_t * Frc_ManCollectCos( Frc_Man_t * p )
{
Vec_Int_t * vCoOrder;
Frc_Obj_t * pObj;
int i;
vCoOrder = Vec_IntAlloc( Frc_ManCoNum(p) );
Frc_ManForEachCo( p, pObj, i )
Vec_IntPush( vCoOrder, pObj->hHandle );
return vCoOrder;
}
/**Function*************************************************************
Synopsis [Computes cross cut size for the given order of POs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManCrossCutTest( Frc_Man_t * p, Vec_Int_t * vOrderInit )
{
Vec_Int_t * vOrder;
// clock_t clk = clock();
vOrder = vOrderInit? vOrderInit : Frc_ManCollectCos( p );
printf( "CrossCut = %6d\n", Frc_ManCrossCut( p, vOrder, 0 ) );
printf( "CrossCut = %6d\n", Frc_ManCrossCut( p, vOrder, 1 ) );
Vec_IntReverseOrder( vOrder );
printf( "CrossCut = %6d\n", Frc_ManCrossCut( p, vOrder, 0 ) );
printf( "CrossCut = %6d\n", Frc_ManCrossCut( p, vOrder, 1 ) );
Vec_IntReverseOrder( vOrder );
if ( vOrder != vOrderInit )
Vec_IntFree( vOrder );
// ABC_PRT( "Time", clock() - clk );
}
/**Function*************************************************************
Synopsis [Generates random placement.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManPlaceRandom( Frc_Man_t * p )
{
Frc_Obj_t * pThis;
int * pPlacement;
int i, h, Temp, iNext, Counter;
pPlacement = ABC_ALLOC( int, p->nObjs );
for ( i = 0; i < p->nObjs; i++ )
pPlacement[i] = i;
for ( i = 0; i < p->nObjs; i++ )
{
iNext = Gia_ManRandom( 0 ) % p->nObjs;
Temp = pPlacement[i];
pPlacement[i] = pPlacement[iNext];
pPlacement[iNext] = Temp;
}
Counter = 0;
Frc_ManForEachObj( p, pThis, h )
pThis->pPlace = pPlacement[Counter++];
ABC_FREE( pPlacement );
}
/**Function*************************************************************
Synopsis [Shuffles array of random integers.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManArrayShuffle( Vec_Int_t * vArray )
{
int i, iNext, Temp;
for ( i = 0; i < vArray->nSize; i++ )
{
iNext = Gia_ManRandom( 0 ) % vArray->nSize;
Temp = vArray->pArray[i];
vArray->pArray[i] = vArray->pArray[iNext];
vArray->pArray[iNext] = Temp;
}
}
/**Function*************************************************************
Synopsis [Computes cross cut size for the given order of POs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManPlaceDfs_rec( Frc_Man_t * p, Frc_Obj_t * pObj, int * piPlace )
{
assert( pObj->iFanout > 0 );
if ( pObj->iFanout-- == pObj->nFanouts )
{
Frc_Obj_t * pFanin;
int i;
if ( !Frc_ObjIsCi(pObj) )
Frc_ObjForEachFanin( pObj, pFanin, i )
Frc_ManPlaceDfs_rec( p, pFanin, piPlace );
pObj->pPlace = (*piPlace)++;
}
}
/**Function*************************************************************
Synopsis [Generates DFS placement.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManPlaceDfs( Frc_Man_t * p, Vec_Int_t * vCoOrder )
{
Frc_Obj_t * pObj;
int i, nPlaces = 0;
Frc_ManForEachObj( p, pObj, i )
{
pObj->iFanout = pObj->nFanouts;
if ( pObj->nFanouts == 0 && !Frc_ObjIsCo(pObj) )
pObj->pPlace = nPlaces++;
}
Frc_ManForEachObjVec( vCoOrder, p, pObj, i )
{
assert( Frc_ObjIsCo(pObj) );
Frc_ManPlaceDfs_rec( p, Frc_ObjFanin(pObj,0), &nPlaces );
pObj->pPlace = nPlaces++;
}
assert( nPlaces == p->nObjs );
}
/**Function*************************************************************
Synopsis [Generates DFS placement by trying both orders.]
Description [Returns the cross cut size of the best order. ]
SideEffects []
SeeAlso []
***********************************************************************/
int Frc_ManPlaceDfsBoth( Frc_Man_t * p, Vec_Int_t * vCoOrder, int * piCutSize2 )
{
int nCutStart1, nCutStart2;
nCutStart1 = Frc_ManCrossCut( p, vCoOrder, 0 );
Vec_IntReverseOrder( vCoOrder );
nCutStart2 = Frc_ManCrossCut( p, vCoOrder, 0 );
if ( nCutStart1 <= nCutStart2 )
{
Vec_IntReverseOrder( vCoOrder ); // undo
Frc_ManPlaceDfs( p, vCoOrder );
*piCutSize2 = nCutStart2;
return nCutStart1;
}
else
{
Frc_ManPlaceDfs( p, vCoOrder );
Vec_IntReverseOrder( vCoOrder ); // undo
*piCutSize2 = nCutStart1;
return nCutStart2;
}
}
/**Function*************************************************************
Synopsis [Performs iterative refinement of the given placement.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_ManPlacementRefine( Frc_Man_t * p, int nIters, int fVerbose )
{
int fRandomize = 0;
Vec_Int_t * vCoOrder;
Frc_Obj_t * pThis, * pNext;
double CostThis, CostPrev;
float * pVertX, VertX;
int * pPermX, * pHandles;
int k, h, Iter, iMinX, iMaxX, Counter, nCutStart, nCutCur, nCutCur2, nCutPrev;
clock_t clk = clock(), clk2, clk2Total = 0;
// create starting one-dimensional placement
vCoOrder = Frc_ManCollectCos( p );
if ( fRandomize )
Frc_ManArrayShuffle( vCoOrder );
nCutStart = Frc_ManPlaceDfsBoth( p, vCoOrder, &nCutCur2 );
// refine placement
CostPrev = 0.0;
nCutPrev = nCutStart;
pHandles = ABC_ALLOC( int, p->nObjs );
pVertX = ABC_ALLOC( float, p->nObjs );
for ( Iter = 0; Iter < nIters; Iter++ )
{
// compute centers of hyperedges
CostThis = 0.0;
Frc_ManForEachObj( p, pThis, h )
{
iMinX = iMaxX = pThis->pPlace;
Frc_ObjForEachFanout( pThis, pNext, k )
{
iMinX = Abc_MinInt( iMinX, pNext->pPlace );
iMaxX = Abc_MaxInt( iMaxX, pNext->pPlace );
}
pThis->fEdgeCenter = 0.5 * (iMaxX + iMinX);
CostThis += (iMaxX - iMinX);
}
// compute new centers of objects
Counter = 0;
Frc_ManForEachObj( p, pThis, h )
{
VertX = pThis->fEdgeCenter;
Frc_ObjForEachFanin( pThis, pNext, k )
VertX += pNext->fEdgeCenter;
pVertX[Counter] = VertX / (Frc_ObjFaninNum(pThis) + 1);
pHandles[Counter++] = h;
}
assert( Counter == Frc_ManObjNum(p) );
// sort these numbers
clk2 = clock();
pPermX = Gia_SortFloats( pVertX, pHandles, p->nObjs );
clk2Total += clock() - clk2;
assert( pPermX == pHandles );
Vec_IntClear( vCoOrder );
for ( k = 0; k < p->nObjs; k++ )
{
pThis = Frc_ManObj( p, pPermX[k] );
pThis->pPlace = k;
if ( Frc_ObjIsCo(pThis) )
Vec_IntPush( vCoOrder, pThis->hHandle );
}
/*
printf( "Ordering of PIs:\n" );
Frc_ManForEachCi( p, pThis, k )
printf( "PI number = %7d. Object handle = %7d, Coordinate = %7d.\n",
k, pThis->hHandle, pThis->pPlace );
*/
nCutCur = Frc_ManPlaceDfsBoth( p, vCoOrder, &nCutCur2 );
// evaluate cost
if ( fVerbose )
{
printf( "%2d : Span = %e ", Iter+1, CostThis );
printf( "Cut = %6d (%5.2f %%) CutR = %6d ", nCutCur, 100.0*(nCutStart-nCutCur)/nCutStart, nCutCur2 );
ABC_PRTn( "Total", clock() - clk );
ABC_PRT( "Sort", clk2Total );
// Frc_ManCrossCutTest( p, vCoOrder );
}
// if ( 1.0 * nCutPrev / nCutCur < 1.001 )
// break;
nCutPrev = nCutCur;
}
ABC_FREE( pHandles );
ABC_FREE( pVertX );
Vec_IntFree( vCoOrder );
}
/**Function*************************************************************
Synopsis [Returns 1 if all fanouts are COsw.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Frc_ObjFanoutsAreCos( Frc_Obj_t * pThis )
{
Frc_Obj_t * pNext;
int i;
Frc_ObjForEachFanout( pThis, pNext, i )
if ( !Frc_ObjIsCo(pNext) )
return 0;
return 1;
}
/**Function*************************************************************
Synopsis [Computes the distances from the given set of objects.]
Description [Returns one of the most distant objects.]
SideEffects []
SeeAlso []
***********************************************************************/
void Frc_DumpGraphIntoFile( Frc_Man_t * p )
{
FILE * pFile;
Frc_Obj_t * pThis, * pNext;
int i, k, Counter = 0;
// assign numbers to CIs and internal nodes
Frc_ManForEachObj( p, pThis, i )
{
if ( i && ((Frc_ObjIsCi(pThis) && !Frc_ObjFanoutsAreCos(pThis)) || Frc_ObjIsNode(pThis)) )
pThis->iFanin = Counter++;
else
pThis->iFanin = ~0;
}
// assign numbers to all other nodes
pFile = fopen( "x\\large\\aig\\dg1.g", "w" );
Frc_ManForEachObj( p, pThis, i )
{
Frc_ObjForEachFanout( pThis, pNext, k )
{
if ( ~pThis->iFanin && ~pNext->iFanin )
fprintf( pFile, "%d %d\n", pThis->iFanin, pNext->iFanin );
}
}
fclose( pFile );
}
/**Function*************************************************************
Synopsis [Experiment with the FORCE algorithm.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void For_ManExperiment( Gia_Man_t * pGia, int nIters, int fClustered, int fVerbose )
{
Frc_Man_t * p;
Gia_ManRandom( 1 );
if ( fClustered )
p = Frc_ManStart( pGia );
else
p = Frc_ManStartSimple( pGia );
// Frc_DumpGraphIntoFile( p );
if ( fVerbose )
Frc_ManPrintStats( p );
// Frc_ManCrossCutTest( p, NULL );
Frc_ManPlacementRefine( p, nIters, fVerbose );
Frc_ManStop( p );
}
/**Function*************************************************************
Synopsis [Experiment with the FORCE algorithm.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void For_ManFileExperiment()
{
FILE * pFile;
int * pBuffer;
int i, Size, Exp = 25;
clock_t clk = clock();
int RetValue;
Size = (1 << Exp);
printf( "2^%d machine words (%d bytes).\n", Exp, (int)sizeof(int) * Size );
pBuffer = ABC_ALLOC( int, Size );
for ( i = 0; i < Size; i++ )
pBuffer[i] = i;
ABC_PRT( "Fillup", clock() - clk );
clk = clock();
pFile = fopen( "test.txt", "rb" );
RetValue = fread( pBuffer, 1, sizeof(int) * Size, pFile );
fclose( pFile );
ABC_PRT( "Read ", clock() - clk );
clk = clock();
pFile = fopen( "test.txt", "wb" );
fwrite( pBuffer, 1, sizeof(int) * Size, pFile );
fclose( pFile );
ABC_PRT( "Write ", clock() - clk );
/*
2^25 machine words (134217728 bytes).
Fillup = 0.06 sec
Read = 0.08 sec
Write = 1.81 sec
*/
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END