/**CFile****************************************************************
FileName [giaEmbed.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Scalable AIG package.]
Synopsis [Logic network derived from AIG.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: giaEmbed.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include <math.h>
#include "gia.h"
#include "aig/ioa/ioa.h"
ABC_NAMESPACE_IMPL_START
/*
The code is based on the paper by D. Harel and Y. Koren,
"Graph drawing by high-dimensional embedding",
J. Graph Algs & Apps, Vol 8(2), pp. 195-217 (2004).
http://www.emis.de/journals/JGAA/accepted/2004/HarelKoren2004.8.2.pdf
Iterative refinement is described in the paper: 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 ///
////////////////////////////////////////////////////////////////////////
#define GIA_PLACE_SIZE 0x7fff
// objects will be placed in box [0, GIA_PLACE_SIZE] x [0, GIA_PLACE_SIZE]
typedef float Emb_Dat_t;
typedef struct Emb_Obj_t_ Emb_Obj_t;
struct Emb_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
int hHandle; // the handle of the node
union {
unsigned TravId; // user-specified value
unsigned iFanin;
};
union {
unsigned Value; // user-specified value
unsigned iFanout;
};
int Fanios[0]; // the array of fanins/fanouts
};
typedef struct Emb_Man_t_ Emb_Man_t;
struct Emb_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 nTravIds; // traversal ID of the network
int * pObjData; // the array containing data for objects
int nObjData; // the size of array to store the logic network
int fVerbose; // verbose output flag
Emb_Dat_t * pVecs; // array of vectors of size nObjs * nDims
int nReached; // the number of nodes reachable from the pivot
int nDistMax; // the maximum distance from the node
float ** pMatr; // covariance matrix nDims * nDims
float ** pEigen; // the first several eigen values of the matrix
float * pSols; // solutions to the problem nObjs * nSols;
unsigned short*pPlacement; // (x,y) coordinates for each cell
};
static inline int Emb_ManRegNum( Emb_Man_t * p ) { return p->nRegs; }
static inline int Emb_ManCiNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCis); }
static inline int Emb_ManCoNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCos); }
static inline int Emb_ManPiNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCis) - p->nRegs; }
static inline int Emb_ManPoNum( Emb_Man_t * p ) { return Vec_IntSize(p->vCos) - p->nRegs; }
static inline int Emb_ManObjNum( Emb_Man_t * p ) { return p->nObjs; }
static inline int Emb_ManNodeNum( Emb_Man_t * p ) { return p->nObjs - Vec_IntSize(p->vCis) - Vec_IntSize(p->vCos); }
static inline Emb_Obj_t * Emb_ManObj( Emb_Man_t * p, unsigned hHandle ) { return (Emb_Obj_t *)(p->pObjData + hHandle); }
static inline Emb_Obj_t * Emb_ManCi( Emb_Man_t * p, int i ) { return Emb_ManObj( p, Vec_IntEntry(p->vCis,i) ); }
static inline Emb_Obj_t * Emb_ManCo( Emb_Man_t * p, int i ) { return Emb_ManObj( p, Vec_IntEntry(p->vCos,i) ); }
static inline int Emb_ObjIsTerm( Emb_Obj_t * pObj ) { return pObj->fCi || pObj->fCo; }
static inline int Emb_ObjIsCi( Emb_Obj_t * pObj ) { return pObj->fCi; }
static inline int Emb_ObjIsCo( Emb_Obj_t * pObj ) { return pObj->fCo; }
//static inline int Emb_ObjIsPi( Emb_Obj_t * pObj ) { return pObj->fCi && pObj->nFanins == 0; }
//static inline int Emb_ObjIsPo( Emb_Obj_t * pObj ) { return pObj->fCo && pObj->nFanouts == 0; }
static inline int Emb_ObjIsNode( Emb_Obj_t * pObj ) { return!Emb_ObjIsTerm(pObj) && pObj->nFanins > 0; }
//static inline int Emb_ObjIsConst0( Emb_Obj_t * pObj ) { return!Emb_ObjIsTerm(pObj) && pObj->nFanins == 0; }
static inline int Emb_ObjSize( Emb_Obj_t * pObj ) { return sizeof(Emb_Obj_t) / 4 + pObj->nFanins + pObj->nFanouts; }
static inline int Emb_ObjFaninNum( Emb_Obj_t * pObj ) { return pObj->nFanins; }
static inline int Emb_ObjFanoutNum( Emb_Obj_t * pObj ) { return pObj->nFanouts; }
static inline Emb_Obj_t * Emb_ObjFanin( Emb_Obj_t * pObj, int i ) { return (Emb_Obj_t *)(((int *)pObj) - pObj->Fanios[i]); }
static inline Emb_Obj_t * Emb_ObjFanout( Emb_Obj_t * pObj, int i ) { return (Emb_Obj_t *)(((int *)pObj) + pObj->Fanios[pObj->nFanins+i]); }
static inline void Emb_ManResetTravId( Emb_Man_t * p ) { extern void Emb_ManCleanTravId( Emb_Man_t * p ); Emb_ManCleanTravId( p ); p->nTravIds = 1; }
static inline void Emb_ManIncrementTravId( Emb_Man_t * p ) { p->nTravIds++; }
static inline void Emb_ObjSetTravId( Emb_Obj_t * pObj, int TravId ) { pObj->TravId = TravId; }
static inline void Emb_ObjSetTravIdCurrent( Emb_Man_t * p, Emb_Obj_t * pObj ) { pObj->TravId = p->nTravIds; }
static inline void Emb_ObjSetTravIdPrevious( Emb_Man_t * p, Emb_Obj_t * pObj ) { pObj->TravId = p->nTravIds - 1; }
static inline int Emb_ObjIsTravIdCurrent( Emb_Man_t * p, Emb_Obj_t * pObj ) { return ((int)pObj->TravId == p->nTravIds); }
static inline int Emb_ObjIsTravIdPrevious( Emb_Man_t * p, Emb_Obj_t * pObj ) { return ((int)pObj->TravId == p->nTravIds - 1); }
static inline Emb_Dat_t * Emb_ManVec( Emb_Man_t * p, int v ) { return p->pVecs + v * p->nObjs; }
static inline float * Emb_ManSol( Emb_Man_t * p, int v ) { return p->pSols + v * p->nObjs; }
#define Emb_ManForEachObj( p, pObj, i ) \
for ( i = 0; (i < p->nObjData) && (pObj = Emb_ManObj(p,i)); i += Emb_ObjSize(pObj) )
#define Emb_ManForEachNode( p, pObj, i ) \
for ( i = 0; (i < p->nObjData) && (pObj = Emb_ManObj(p,i)); i += Emb_ObjSize(pObj) ) if ( Emb_ObjIsTerm(pObj) ) {} else
#define Emb_ManForEachObjVec( vVec, p, pObj, i ) \
for ( i = 0; (i < Vec_IntSize(vVec)) && ((pObj) = Emb_ManObj(p, Vec_IntEntry(vVec,i))); i++ )
#define Emb_ObjForEachFanin( pObj, pNext, i ) \
for ( i = 0; (i < (int)pObj->nFanins) && (pNext = Emb_ObjFanin(pObj,i)); i++ )
#define Emb_ObjForEachFanout( pObj, pNext, i ) \
for ( i = 0; (i < (int)pObj->nFanouts) && (pNext = Emb_ObjFanout(pObj,i)); i++ )
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Creates fanin/fanout pair.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ObjAddFanin( Emb_Obj_t * pObj, Emb_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 []
***********************************************************************/
Emb_Man_t * Emb_ManStartSimple( Gia_Man_t * pGia )
{
Emb_Man_t * p;
Emb_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( Emb_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(Emb_Obj_t) / 4) * Gia_ManObjNum(pGia) + 2 * (2 * Gia_ManAndNum(pGia) + Gia_ManCoNum(pGia) + Gia_ManRegNum(pGia) + Gia_ManCoNum(pGia));
p->pObjData = ABC_CALLOC( int, p->nObjData );
// create constant node
Gia_ManConst0(pGia)->Value = hHandle;
pObjLog = Emb_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = Gia_ManCoNum(pGia); //0;
pObjLog->nFanouts = Gia_ObjRefNum( pGia, Gia_ManConst0(pGia) );
// count objects
hHandle += Emb_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 = Emb_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = Gia_ObjIsRo( pGia, pObj );
pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
pObjLog->fCi = 1;
// count objects
hHandle += Emb_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 = Emb_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = 2;
pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
// add fanins
pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
Emb_ObjAddFanin( pObjLog, pFanLog );
pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin1(pObj)) );
Emb_ObjAddFanin( pObjLog, pFanLog );
// count objects
hHandle += Emb_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 = Emb_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = 1;
pObjLog->nFanouts = 1 + Gia_ObjIsRi( pGia, pObj );
pObjLog->fCo = 1;
// add fanins
pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
Emb_ObjAddFanin( pObjLog, pFanLog );
// count objects
hHandle += Emb_ObjSize( pObjLog );
p->nObjs++;
}
// connect registers
Gia_ManForEachRiRo( pGia, pObjRi, pObjRo, i )
Emb_ObjAddFanin( Emb_ManObj(p,Gia_ObjValue(pObjRo)), Emb_ManObj(p,Gia_ObjValue(pObjRi)) );
assert( nNodes == Emb_ManNodeNum(p) );
assert( hHandle == p->nObjData );
assert( p->nObjs == Gia_ManObjNum(pGia) );
if ( hHandle != p->nObjData )
printf( "Emb_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 = Emb_ManObj( p, Gia_ObjValue(pObj) );
assert( pObjLog->nFanins == pObjLog->iFanin || Gia_ObjIsConst0(pObj) );
assert( pObjLog->nFanouts == pObjLog->iFanout || Gia_ObjIsCo(pObj) );
pObjLog->iFanin = pObjLog->iFanout = 0;
}
ABC_FREE( pGia->pRefs );
return p;
}
/**Function*************************************************************
Synopsis [Collect the fanin IDs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_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) );
Emb_ManCollectSuper_rec( p, Gia_ObjFanin0(pObj), vSuper, vVisit );
Emb_ManCollectSuper_rec( p, Gia_ObjFanin1(pObj), vSuper, vVisit );
}
/**Function*************************************************************
Synopsis [Collect the fanin IDs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_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;
Emb_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 Emb_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 Emb_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;
Emb_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 [Cleans the value.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManCleanTravId( Emb_Man_t * p )
{
Emb_Obj_t * pObj;
int i;
Emb_ManForEachObj( p, pObj, i )
pObj->TravId = 0;
}
/**Function*************************************************************
Synopsis [Cleans the value.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManSetValue( Emb_Man_t * p )
{
Emb_Obj_t * pObj;
int i, Counter = 0;
Emb_ManForEachObj( p, pObj, i )
{
pObj->Value = Counter++;
// if ( pObj->fCi && pObj->nFanins == 0 )
// printf( "CI: Handle = %8d. Value = %6d. Fanins = %d.\n", pObj->hHandle, pObj->Value, pObj->nFanins );
}
}
/**Function*************************************************************
Synopsis [Creates logic network isomorphic to the given AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Emb_Man_t * Emb_ManStart( Gia_Man_t * pGia )
{
Emb_Man_t * p;
Emb_Obj_t * pObjLog, * pFanLog;
Gia_Obj_t * pObj, * pObjRi, * pObjRo, * pFanin;
Vec_Int_t * vSuper, * vVisit;
int nObjs, nFanios, nNodes = 0;
int i, k, hHandle = 0;
// prepare the AIG
// Gia_ManCreateRefs( pGia );
Emb_ManCreateRefsSpecial( pGia );
Emb_ManTransformRefs( pGia, &nObjs, &nFanios );
Gia_ManFillValue( pGia );
// create logic network
p = ABC_CALLOC( Emb_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(Emb_Obj_t) / 4) * nObjs + 2 * (nFanios + Gia_ManRegNum(pGia) + Gia_ManCoNum(pGia));
p->pObjData = ABC_CALLOC( int, p->nObjData );
// create constant node
Gia_ManConst0(pGia)->Value = hHandle;
pObjLog = Emb_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = Gia_ManCoNum(pGia); //0;
pObjLog->nFanouts = Gia_ObjRefNum( pGia, Gia_ManConst0(pGia) );
// count objects
hHandle += Emb_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 = Emb_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = Gia_ObjIsRo( pGia, pObj );
pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
pObjLog->fCi = 1;
// count objects
hHandle += Emb_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 );
Emb_ManCollectSuper( pGia, pObj, vSuper, vVisit );
// create node object
pObj->Value = hHandle;
pObjLog = Emb_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 = Emb_ManObj( p, Gia_ObjValue(pFanin) );
Emb_ObjAddFanin( pObjLog, pFanLog );
}
// count objects
hHandle += Emb_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 = Emb_ManObj( p, hHandle );
pObjLog->hHandle = hHandle;
pObjLog->nFanins = 1;
pObjLog->nFanouts = 1 + Gia_ObjIsRi( pGia, pObj );
pObjLog->fCo = 1;
// add fanins
pFanLog = Emb_ManObj( p, Gia_ObjValue(Gia_ObjFanin0(pObj)) );
Emb_ObjAddFanin( pObjLog, pFanLog );
// count objects
hHandle += Emb_ObjSize( pObjLog );
p->nObjs++;
}
// connect registers
Gia_ManForEachRiRo( pGia, pObjRi, pObjRo, i )
Emb_ObjAddFanin( Emb_ManObj(p,Gia_ObjValue(pObjRo)), Emb_ManObj(p,Gia_ObjValue(pObjRi)) );
Gia_ManCleanMark0( pGia );
assert( nNodes == Emb_ManNodeNum(p) );
assert( nObjs == p->nObjs );
assert( hHandle == p->nObjData );
if ( hHandle != p->nObjData )
printf( "Emb_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 = Emb_ManObj( p, Gia_ObjValue(pObj) );
assert( pObjLog->nFanins == pObjLog->iFanin || Gia_ObjIsConst0(pObj) );
assert( pObjLog->nFanouts == pObjLog->iFanout || Gia_ObjIsCo(pObj) );
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 Emb_ManPrintStats( Emb_Man_t * p )
{
// if ( p->pName )
// printf( "%8s : ", p->pName );
printf( "i/o =%7d/%7d ", Emb_ManPiNum(p), Emb_ManPoNum(p) );
if ( Emb_ManRegNum(p) )
printf( "ff =%7d ", Emb_ManRegNum(p) );
printf( "node =%8d ", Emb_ManNodeNum(p) );
printf( "obj =%8d ", Emb_ManObjNum(p) );
// printf( "lev =%5d ", Emb_ManLevelNum(p) );
// printf( "cut =%5d ", Emb_ManCrossCut(p) );
printf( "mem =%5.2f MB", 4.0*p->nObjData/(1<<20) );
// printf( "obj =%5d ", Emb_ManObjNum(p) );
printf( "\n" );
// Emb_ManSatExperiment( p );
}
/**Function*************************************************************
Synopsis [Creates logic network isomorphic to the given AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManStop( Emb_Man_t * p )
{
Vec_IntFree( p->vCis );
Vec_IntFree( p->vCos );
ABC_FREE( p->pPlacement );
ABC_FREE( p->pVecs );
ABC_FREE( p->pSols );
ABC_FREE( p->pMatr );
ABC_FREE( p->pEigen );
ABC_FREE( p->pObjData );
ABC_FREE( p );
}
/**Function*************************************************************
Synopsis [Prints the distribution of fanins/fanouts in the network.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManPrintFanio( Emb_Man_t * p )
{
char Buffer[100];
Emb_Obj_t * pNode;
Vec_Int_t * vFanins, * vFanouts;
int nFanins, nFanouts, nFaninsMax, nFanoutsMax, nFaninsAll, nFanoutsAll;
int i, k, nSizeMax;
// determine the largest fanin and fanout
nFaninsMax = nFanoutsMax = 0;
nFaninsAll = nFanoutsAll = 0;
Emb_ManForEachNode( p, pNode, i )
{
if ( i == 0 ) continue; // skip const 0 obj
nFanins = Emb_ObjFaninNum(pNode);
nFanouts = Emb_ObjFanoutNum(pNode);
nFaninsAll += nFanins;
nFanoutsAll += nFanouts;
nFaninsMax = Abc_MaxInt( nFaninsMax, nFanins );
nFanoutsMax = Abc_MaxInt( nFanoutsMax, nFanouts );
}
// allocate storage for fanin/fanout numbers
nSizeMax = Abc_MaxInt( 10 * (Abc_Base10Log(nFaninsMax) + 1), 10 * (Abc_Base10Log(nFanoutsMax) + 1) );
vFanins = Vec_IntStart( nSizeMax );
vFanouts = Vec_IntStart( nSizeMax );
// count the number of fanins and fanouts
Emb_ManForEachNode( p, pNode, i )
{
if ( i == 0 ) continue; // skip const 0 obj
nFanins = Emb_ObjFaninNum(pNode);
nFanouts = Emb_ObjFanoutNum(pNode);
if ( nFanins < 10 )
Vec_IntAddToEntry( vFanins, nFanins, 1 );
else if ( nFanins < 100 )
Vec_IntAddToEntry( vFanins, 10 + nFanins/10, 1 );
else if ( nFanins < 1000 )
Vec_IntAddToEntry( vFanins, 20 + nFanins/100, 1 );
else if ( nFanins < 10000 )
Vec_IntAddToEntry( vFanins, 30 + nFanins/1000, 1 );
else if ( nFanins < 100000 )
Vec_IntAddToEntry( vFanins, 40 + nFanins/10000, 1 );
else if ( nFanins < 1000000 )
Vec_IntAddToEntry( vFanins, 50 + nFanins/100000, 1 );
else if ( nFanins < 10000000 )
Vec_IntAddToEntry( vFanins, 60 + nFanins/1000000, 1 );
if ( nFanouts < 10 )
Vec_IntAddToEntry( vFanouts, nFanouts, 1 );
else if ( nFanouts < 100 )
Vec_IntAddToEntry( vFanouts, 10 + nFanouts/10, 1 );
else if ( nFanouts < 1000 )
Vec_IntAddToEntry( vFanouts, 20 + nFanouts/100, 1 );
else if ( nFanouts < 10000 )
Vec_IntAddToEntry( vFanouts, 30 + nFanouts/1000, 1 );
else if ( nFanouts < 100000 )
Vec_IntAddToEntry( vFanouts, 40 + nFanouts/10000, 1 );
else if ( nFanouts < 1000000 )
Vec_IntAddToEntry( vFanouts, 50 + nFanouts/100000, 1 );
else if ( nFanouts < 10000000 )
Vec_IntAddToEntry( vFanouts, 60 + nFanouts/1000000, 1 );
}
printf( "The distribution of fanins and fanouts in the network:\n" );
printf( " Number Nodes with fanin Nodes with fanout\n" );
for ( k = 0; k < nSizeMax; k++ )
{
if ( vFanins->pArray[k] == 0 && vFanouts->pArray[k] == 0 )
continue;
if ( k < 10 )
printf( "%15d : ", k );
else
{
sprintf( Buffer, "%d - %d", (int)pow((double)10, k/10) * (k%10), (int)pow((double)10, k/10) * (k%10+1) - 1 );
printf( "%15s : ", Buffer );
}
if ( vFanins->pArray[k] == 0 )
printf( " " );
else
printf( "%12d ", vFanins->pArray[k] );
printf( " " );
if ( vFanouts->pArray[k] == 0 )
printf( " " );
else
printf( "%12d ", vFanouts->pArray[k] );
printf( "\n" );
}
Vec_IntFree( vFanins );
Vec_IntFree( vFanouts );
printf( "Fanins: Max = %d. Ave = %.2f. Fanouts: Max = %d. Ave = %.2f.\n",
nFaninsMax, 1.0*nFaninsAll/Emb_ManNodeNum(p),
nFanoutsMax, 1.0*nFanoutsAll/Emb_ManNodeNum(p) );
}
/**Function*************************************************************
Synopsis [Computes the distance from the given object]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Emb_ManComputeDistance_old( Emb_Man_t * p, Emb_Obj_t * pPivot )
{
Vec_Int_t * vThis, * vNext, * vTemp;
Emb_Obj_t * pThis, * pNext;
int i, k, d, nVisited = 0;
// assert( Emb_ObjIsTerm(pPivot) );
vThis = Vec_IntAlloc( 1000 );
vNext = Vec_IntAlloc( 1000 );
Emb_ManIncrementTravId( p );
Emb_ObjSetTravIdCurrent( p, pPivot );
Vec_IntPush( vThis, pPivot->hHandle );
for ( d = 0; Vec_IntSize(vThis) > 0; d++ )
{
nVisited += Vec_IntSize(vThis);
Vec_IntClear( vNext );
Emb_ManForEachObjVec( vThis, p, pThis, i )
{
Emb_ObjForEachFanin( pThis, pNext, k )
{
if ( Emb_ObjIsTravIdCurrent(p, pNext) )
continue;
Emb_ObjSetTravIdCurrent(p, pNext);
Vec_IntPush( vNext, pNext->hHandle );
nVisited += !Emb_ObjIsTerm(pNext);
}
Emb_ObjForEachFanout( pThis, pNext, k )
{
if ( Emb_ObjIsTravIdCurrent(p, pNext) )
continue;
Emb_ObjSetTravIdCurrent(p, pNext);
Vec_IntPush( vNext, pNext->hHandle );
nVisited += !Emb_ObjIsTerm(pNext);
}
}
vTemp = vThis; vThis = vNext; vNext = vTemp;
}
Vec_IntFree( vThis );
Vec_IntFree( vNext );
// check if there are several strongly connected components
// if ( nVisited < Emb_ManNodeNum(p) )
// printf( "Visited less nodes (%d) than present (%d).\n", nVisited, Emb_ManNodeNum(p) );
return d;
}
/**Function*************************************************************
Synopsis [Traverses from the given node.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Gia_ManTestDistanceInternal( Emb_Man_t * p )
{
int nAttempts = 20;
int i, iNode, Dist;
abctime clk;
Emb_Obj_t * pPivot, * pNext;
Gia_ManRandom( 1 );
Emb_ManResetTravId( p );
// compute distances from several randomly selected PIs
clk = Abc_Clock();
printf( "From inputs: " );
for ( i = 0; i < nAttempts; i++ )
{
iNode = Gia_ManRandom( 0 ) % Emb_ManCiNum(p);
pPivot = Emb_ManCi( p, iNode );
if ( Emb_ObjFanoutNum(pPivot) == 0 )
{ i--; continue; }
pNext = Emb_ObjFanout( pPivot, 0 );
if ( !Emb_ObjIsNode(pNext) )
{ i--; continue; }
Dist = Emb_ManComputeDistance_old( p, pPivot );
printf( "%d ", Dist );
}
ABC_PRT( "Time", Abc_Clock() - clk );
// compute distances from several randomly selected POs
clk = Abc_Clock();
printf( "From outputs: " );
for ( i = 0; i < nAttempts; i++ )
{
iNode = Gia_ManRandom( 0 ) % Emb_ManCoNum(p);
pPivot = Emb_ManCo( p, iNode );
pNext = Emb_ObjFanin( pPivot, 0 );
if ( !Emb_ObjIsNode(pNext) )
{ i--; continue; }
Dist = Emb_ManComputeDistance_old( p, pPivot );
printf( "%d ", Dist );
}
ABC_PRT( "Time", Abc_Clock() - clk );
// compute distances from several randomly selected nodes
clk = Abc_Clock();
printf( "From nodes: " );
for ( i = 0; i < nAttempts; i++ )
{
iNode = Gia_ManRandom( 0 ) % Gia_ManObjNum(p->pGia);
if ( !~Gia_ManObj(p->pGia, iNode)->Value )
{ i--; continue; }
pPivot = Emb_ManObj( p, Gia_ManObj(p->pGia, iNode)->Value );
if ( !Emb_ObjIsNode(pPivot) )
{ i--; continue; }
Dist = Emb_ManComputeDistance_old( p, pPivot );
printf( "%d ", Dist );
}
ABC_PRT( "Time", Abc_Clock() - clk );
}
/**Function*************************************************************
Synopsis [Returns sorted array of node handles with largest fanout.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Gia_ManTestDistance( Gia_Man_t * pGia )
{
Emb_Man_t * p;
abctime clk = Abc_Clock();
p = Emb_ManStart( pGia );
// Emb_ManPrintFanio( p );
Emb_ManPrintStats( p );
ABC_PRT( "Time", Abc_Clock() - clk );
Gia_ManTestDistanceInternal( p );
Emb_ManStop( p );
}
/**Function*************************************************************
Synopsis [Perform BFS from the set of nodes.]
Description [Returns one of the most distant objects.]
SideEffects []
SeeAlso []
***********************************************************************/
Emb_Obj_t * Emb_ManPerformBfs( Emb_Man_t * p, Vec_Int_t * vThis, Vec_Int_t * vNext, Emb_Dat_t * pDist )
{
Vec_Int_t * vTemp;
Emb_Obj_t * pThis, * pNext, * pResult;
int i, k;
assert( Vec_IntSize(vThis) > 0 );
for ( p->nDistMax = 0; Vec_IntSize(vThis) > 0; p->nDistMax++ )
{
p->nReached += Vec_IntSize(vThis);
Vec_IntClear( vNext );
Emb_ManForEachObjVec( vThis, p, pThis, i )
{
if ( pDist ) pDist[pThis->Value] = p->nDistMax;
Emb_ObjForEachFanin( pThis, pNext, k )
{
if ( Emb_ObjIsTravIdCurrent(p, pNext) )
continue;
Emb_ObjSetTravIdCurrent(p, pNext);
Vec_IntPush( vNext, pNext->hHandle );
}
Emb_ObjForEachFanout( pThis, pNext, k )
{
if ( Emb_ObjIsTravIdCurrent(p, pNext) )
continue;
Emb_ObjSetTravIdCurrent(p, pNext);
Vec_IntPush( vNext, pNext->hHandle );
}
}
vTemp = vThis; vThis = vNext; vNext = vTemp;
}
assert( Vec_IntSize(vNext) > 0 );
pResult = Emb_ManObj( p, Vec_IntEntry(vNext, 0) );
assert( pDist == NULL || pDist[pResult->Value] == p->nDistMax - 1 );
return pResult;
}
/**Function*************************************************************
Synopsis [Computes the distances from the given set of objects.]
Description [Returns one of the most distant objects.]
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Int_t * Emb_ManConnectedComponents( Emb_Man_t * p )
{
Gia_Obj_t * pObj;
Vec_Int_t * vThis, * vNext, * vResult;
Emb_Obj_t * pThis;
int i;
vResult = Vec_IntAlloc( 1000 );
vThis = Vec_IntAlloc( 1000 );
vNext = Vec_IntAlloc( 1000 );
p->nReached = 0;
Emb_ManIncrementTravId( p );
Gia_ManForEachCo( p->pGia, pObj, i )
{
pThis = Emb_ManObj( p, Gia_ObjValue(pObj) );
if ( Emb_ObjIsTravIdCurrent(p, pThis) )
continue;
Emb_ObjSetTravIdCurrent( p, pThis );
Vec_IntPush( vResult, pThis->hHandle );
// perform BFS from this node
Vec_IntClear( vThis );
Vec_IntPush( vThis, pThis->hHandle );
Emb_ManPerformBfs( p, vThis, vNext, NULL );
}
Vec_IntFree( vThis );
Vec_IntFree( vNext );
return vResult;
}
/**Function*************************************************************
Synopsis [Computes the distances from the given set of objects.]
Description [Returns one of the most distant objects.]
SideEffects []
SeeAlso []
***********************************************************************/
Emb_Obj_t * Emb_ManFindDistances( Emb_Man_t * p, Vec_Int_t * vStart, Emb_Dat_t * pDist )
{
Vec_Int_t * vThis, * vNext;
Emb_Obj_t * pThis, * pResult;
int i;
p->nReached = p->nDistMax = 0;
vThis = Vec_IntAlloc( 1000 );
vNext = Vec_IntAlloc( 1000 );
Emb_ManIncrementTravId( p );
Emb_ManForEachObjVec( vStart, p, pThis, i )
{
Emb_ObjSetTravIdCurrent( p, pThis );
Vec_IntPush( vThis, pThis->hHandle );
}
pResult = Emb_ManPerformBfs( p, vThis, vNext, pDist );
Vec_IntFree( vThis );
Vec_IntFree( vNext );
return pResult;
}
/**Function*************************************************************
Synopsis [Traverses from the given node.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Emb_Obj_t * Emb_ManRandomVertex( Emb_Man_t * p )
{
Emb_Obj_t * pPivot;
do {
int iNode = (911 * Gia_ManRandom(0)) % Gia_ManObjNum(p->pGia);
if ( ~Gia_ManObj(p->pGia, iNode)->Value )
pPivot = Emb_ManObj( p, Gia_ManObj(p->pGia, iNode)->Value );
else
pPivot = NULL;
}
while ( pPivot == NULL || !Emb_ObjIsNode(pPivot) );
return pPivot;
}
/**Function*************************************************************
Synopsis [Computes the distances from the given set of objects.]
Description [Returns one of the most distant objects.]
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_DumpGraphIntoFile( Emb_Man_t * p )
{
FILE * pFile;
Emb_Obj_t * pThis, * pNext;
int i, k;
pFile = fopen( "1.g", "w" );
Emb_ManForEachObj( p, pThis, i )
{
if ( !Emb_ObjIsTravIdCurrent(p, pThis) )
continue;
Emb_ObjForEachFanout( pThis, pNext, k )
{
assert( Emb_ObjIsTravIdCurrent(p, pNext) );
fprintf( pFile, "%d %d\n", pThis->Value, pNext->Value );
}
}
fclose( pFile );
}
/**Function*************************************************************
Synopsis [Computes dimentions of the graph.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManComputeDimensions( Emb_Man_t * p, int nDims )
{
Emb_Obj_t * pRandom, * pPivot;
Vec_Int_t * vStart, * vComps;
int d, nReached;
int i;//, Counter;
// connect unconnected components
vComps = Emb_ManConnectedComponents( p );
// printf( "Components = %d. Considered %d objects (out of %d).\n", Vec_IntSize(vComps), p->nReached, Emb_ManObjNum(p) );
if ( Vec_IntSize(vComps) > 1 )
{
Emb_Obj_t * pFanin, * pObj = Emb_ManObj( p, 0 );
Emb_ManForEachObjVec( vComps, p, pFanin, i )
{
assert( Emb_ObjIsCo(pFanin) );
pFanin->Fanios[pFanin->nFanins + pFanin->nFanouts-1] =
pObj->Fanios[i] = pObj->hHandle - pFanin->hHandle;
}
}
Vec_IntFree( vComps );
// allocate memory for vectors
assert( p->pVecs == NULL );
p->pVecs = ABC_CALLOC( Emb_Dat_t, p->nObjs * nDims );
// for ( i = 0; i < p->nObjs * nDims; i++ )
// p->pVecs[i] = ABC_INFINITY;
vStart = Vec_IntAlloc( nDims );
// get the pivot vertex
pRandom = Emb_ManRandomVertex( p );
Vec_IntPush( vStart, pRandom->hHandle );
// get the most distant vertex from the pivot
pPivot = Emb_ManFindDistances( p, vStart, NULL );
// Emb_DumpGraphIntoFile( p );
nReached = p->nReached;
if ( nReached < Emb_ManObjNum(p) )
{
// printf( "Considering a connected component with %d objects (out of %d).\n", p->nReached, Emb_ManObjNum(p) );
}
// start dimensions with this vertex
Vec_IntClear( vStart );
for ( d = 0; d < nDims; d++ )
{
// printf( "%3d : Adding vertex %7d with distance %3d.\n", d+1, pPivot->Value, p->nDistMax );
Vec_IntPush( vStart, pPivot->hHandle );
if ( d+1 == nReached )
break;
pPivot = Emb_ManFindDistances( p, vStart, Emb_ManVec(p, d) );
assert( nReached == p->nReached );
}
Vec_IntFree( vStart );
// make sure the number of reached objects is correct
// Counter = 0;
// for ( i = 0; i < p->nObjs; i++ )
// if ( p->pVecs[i] < ABC_INFINITY )
// Counter++;
// assert( Counter == nReached );
}
/**Function*************************************************************
Synopsis [Allocated square matrix of floats.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
float ** Emb_ManMatrAlloc( int nDims )
{
int i;
float ** pMatr = (float **)ABC_ALLOC( char, sizeof(float *) * nDims + sizeof(float) * nDims * nDims );
pMatr[0] = (float *)(pMatr + nDims);
for ( i = 1; i < nDims; i++ )
pMatr[i] = pMatr[i-1] + nDims;
return pMatr;
}
/**Function*************************************************************
Synopsis [Computes covariance matrix.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManComputeCovariance( Emb_Man_t * p, int nDims )
{
Emb_Dat_t * pOne, * pTwo;
double Ave;
float * pRow;
int d, i, k, v;
// average vectors
for ( d = 0; d < nDims; d++ )
{
// compute average
Ave = 0.0;
pOne = Emb_ManVec( p, d );
for ( v = 0; v < p->nObjs; v++ )
if ( pOne[v] < ABC_INFINITY )
Ave += pOne[v];
Ave /= p->nReached;
// update the vector
for ( v = 0; v < p->nObjs; v++ )
if ( pOne[v] < ABC_INFINITY )
pOne[v] -= Ave;
else
pOne[v] = 0.0;
}
// compute the matrix
assert( p->pMatr == NULL );
assert( p->pEigen == NULL );
p->pMatr = Emb_ManMatrAlloc( nDims );
p->pEigen = Emb_ManMatrAlloc( nDims );
for ( i = 0; i < nDims; i++ )
{
pOne = Emb_ManVec( p, i );
pRow = p->pMatr[i];
for ( k = 0; k < nDims; k++ )
{
pTwo = Emb_ManVec( p, k );
pRow[k] = 0.0;
for ( v = 0; v < p->nObjs; v++ )
pRow[k] += pOne[v]*pTwo[v];
}
}
}
/**Function*************************************************************
Synopsis [Returns random vector.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManVecRandom( float * pVec, int nDims )
{
int i;
for ( i = 0; i < nDims; i++ )
pVec[i] = Gia_ManRandom( 0 );
}
/**Function*************************************************************
Synopsis [Returns normalized vector.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManVecNormal( float * pVec, int nDims )
{
int i;
double Norm = 0.0;
for ( i = 0; i < nDims; i++ )
Norm += pVec[i] * pVec[i];
Norm = pow( Norm, 0.5 );
for ( i = 0; i < nDims; i++ )
pVec[i] /= Norm;
}
/**Function*************************************************************
Synopsis [Multiplies vector by vector.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
float Emb_ManVecMultiplyOne( float * pVec0, float * pVec1, int nDims )
{
float Res = 0.0;
int i;
for ( i = 0; i < nDims; i++ )
Res += pVec0[i] * pVec1[i];
return Res;
}
/**Function*************************************************************
Synopsis [Copies the vector.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManVecCopyOne( float * pVecDest, float * pVecSour, int nDims )
{
int i;
for ( i = 0; i < nDims; i++ )
pVecDest[i] = pVecSour[i];
}
/**Function*************************************************************
Synopsis [Multiplies matrix by vector.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManVecMultiply( float ** pMatr, float * pVec, int nDims, float * pRes )
{
int k;
for ( k = 0; k < nDims; k++ )
pRes[k] = Emb_ManVecMultiplyOne( pMatr[k], pVec, nDims );
}
/**Function*************************************************************
Synopsis [Multiplies vector by matrix.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManVecOrthogonolizeOne( float * pEigen, float * pVecI, int nDims, float * pVecRes )
{
int k;
for ( k = 0; k < nDims; k++ )
pVecRes[k] = pVecI[k] - pEigen[k] * Emb_ManVecMultiplyOne( pVecI, pEigen, nDims );
}
/**Function*************************************************************
Synopsis [Computes the first nSols eigen-vectors.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManComputeEigenvectors( Emb_Man_t * p, int nDims, int nSols )
{
float * pVecUiHat, * pVecUi;
int i, j, k;
assert( nSols < nDims );
pVecUiHat = p->pEigen[nSols];
for ( i = 0; i < nSols; i++ )
{
pVecUi = p->pEigen[i];
Emb_ManVecRandom( pVecUiHat, nDims );
Emb_ManVecNormal( pVecUiHat, nDims );
k = 0;
do {
k++;
Emb_ManVecCopyOne( pVecUi, pVecUiHat, nDims );
for ( j = 0; j < i; j++ )
{
Emb_ManVecOrthogonolizeOne( p->pEigen[j], pVecUi, nDims, pVecUiHat );
Emb_ManVecCopyOne( pVecUi, pVecUiHat, nDims );
}
Emb_ManVecMultiply( p->pMatr, pVecUi, nDims, pVecUiHat );
Emb_ManVecNormal( pVecUiHat, nDims );
} while ( Emb_ManVecMultiplyOne( pVecUiHat, pVecUi, nDims ) < 0.999 && k < 100 );
Emb_ManVecCopyOne( pVecUi, pVecUiHat, nDims );
// printf( "Converged after %d iterations.\n", k );
}
}
/**Function*************************************************************
Synopsis [Derives solutions from original vectors and eigenvectors.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManComputeSolutions( Emb_Man_t * p, int nDims, int nSols )
{
Emb_Dat_t * pX;
float * pY;
int i, j, k;
assert( p->pSols == NULL );
p->pSols = ABC_CALLOC( float, p->nObjs * nSols );
for ( i = 0; i < nDims; i++ )
{
pX = Emb_ManVec( p, i );
for ( j = 0; j < nSols; j++ )
{
pY = Emb_ManSol( p, j );
for ( k = 0; k < p->nObjs; k++ )
pY[k] += pX[k] * p->pEigen[j][i];
}
}
}
/**Function*************************************************************
Synopsis [Projects into square of size [0;GIA_PLACE_SIZE] x [0;GIA_PLACE_SIZE].]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManDerivePlacement( Emb_Man_t * p, int nSols )
{
float * pY0, * pY1, Max0, Max1, Min0, Min1, Str0, Str1;
int * pPerm0, * pPerm1;
int k;
if ( nSols != 2 )
return;
// compute intervals
Min0 = ABC_INFINITY;
Max0 = -ABC_INFINITY;
pY0 = Emb_ManSol( p, 0 );
for ( k = 0; k < p->nObjs; k++ )
{
Min0 = Abc_MinInt( Min0, pY0[k] );
Max0 = Abc_MaxInt( Max0, pY0[k] );
}
Str0 = 1.0*GIA_PLACE_SIZE/(Max0 - Min0);
// update the coordinates
for ( k = 0; k < p->nObjs; k++ )
pY0[k] = (pY0[k] != 0.0) ? ((pY0[k] - Min0) * Str0) : 0.0;
// compute intervals
Min1 = ABC_INFINITY;
Max1 = -ABC_INFINITY;
pY1 = Emb_ManSol( p, 1 );
for ( k = 0; k < p->nObjs; k++ )
{
Min1 = Abc_MinInt( Min1, pY1[k] );
Max1 = Abc_MaxInt( Max1, pY1[k] );
}
Str1 = 1.0*GIA_PLACE_SIZE/(Max1 - Min1);
// update the coordinates
for ( k = 0; k < p->nObjs; k++ )
pY1[k] = (pY1[k] != 0.0) ? ((pY1[k] - Min1) * Str1) : 0.0;
// derive the order of these numbers
pPerm0 = Gia_SortFloats( pY0, NULL, p->nObjs );
pPerm1 = Gia_SortFloats( pY1, NULL, p->nObjs );
// average solutions and project them into square [0;GIA_PLACE_SIZE] x [0;GIA_PLACE_SIZE]
p->pPlacement = ABC_ALLOC( unsigned short, 2 * p->nObjs );
for ( k = 0; k < p->nObjs; k++ )
{
p->pPlacement[2*pPerm0[k]+0] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
p->pPlacement[2*pPerm1[k]+1] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
}
ABC_FREE( pPerm0 );
ABC_FREE( pPerm1 );
}
/**Function*************************************************************
Synopsis [Computes wire-length.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
double Emb_ManComputeHPWL( Emb_Man_t * p )
{
double Result = 0.0;
Emb_Obj_t * pThis, * pNext;
int i, k, iMinX, iMaxX, iMinY, iMaxY;
if ( p->pPlacement == NULL )
return 0.0;
Emb_ManForEachObj( p, pThis, i )
{
iMinX = iMaxX = p->pPlacement[2*pThis->Value+0];
iMinY = iMaxY = p->pPlacement[2*pThis->Value+1];
Emb_ObjForEachFanout( pThis, pNext, k )
{
iMinX = Abc_MinInt( iMinX, p->pPlacement[2*pNext->Value+0] );
iMaxX = Abc_MaxInt( iMaxX, p->pPlacement[2*pNext->Value+0] );
iMinY = Abc_MinInt( iMinY, p->pPlacement[2*pNext->Value+1] );
iMaxY = Abc_MaxInt( iMaxY, p->pPlacement[2*pNext->Value+1] );
}
Result += (iMaxX - iMinX) + (iMaxY - iMinY);
}
return Result;
}
/**Function*************************************************************
Synopsis [Performs iterative refinement of the given placement.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManPlacementRefine( Emb_Man_t * p, int nIters, int fVerbose )
{
Emb_Obj_t * pThis, * pNext;
double CostThis, CostPrev;
float * pEdgeX, * pEdgeY;
float * pVertX, * pVertY;
float VertX, VertY;
int * pPermX, * pPermY;
int i, k, Iter, iMinX, iMaxX, iMinY, iMaxY;
abctime clk = Abc_Clock();
if ( p->pPlacement == NULL )
return;
pEdgeX = ABC_ALLOC( float, p->nObjs );
pEdgeY = ABC_ALLOC( float, p->nObjs );
pVertX = ABC_ALLOC( float, p->nObjs );
pVertY = ABC_ALLOC( float, p->nObjs );
// refine placement
CostPrev = 0.0;
for ( Iter = 0; Iter < nIters; Iter++ )
{
// compute centers of hyperedges
CostThis = 0.0;
Emb_ManForEachObj( p, pThis, i )
{
iMinX = iMaxX = p->pPlacement[2*pThis->Value+0];
iMinY = iMaxY = p->pPlacement[2*pThis->Value+1];
Emb_ObjForEachFanout( pThis, pNext, k )
{
iMinX = Abc_MinInt( iMinX, p->pPlacement[2*pNext->Value+0] );
iMaxX = Abc_MaxInt( iMaxX, p->pPlacement[2*pNext->Value+0] );
iMinY = Abc_MinInt( iMinY, p->pPlacement[2*pNext->Value+1] );
iMaxY = Abc_MaxInt( iMaxY, p->pPlacement[2*pNext->Value+1] );
}
pEdgeX[pThis->Value] = 0.5 * (iMaxX + iMinX);
pEdgeY[pThis->Value] = 0.5 * (iMaxY + iMinY);
CostThis += (iMaxX - iMinX) + (iMaxY - iMinY);
}
// compute new centers of objects
Emb_ManForEachObj( p, pThis, i )
{
VertX = pEdgeX[pThis->Value];
VertY = pEdgeY[pThis->Value];
Emb_ObjForEachFanin( pThis, pNext, k )
{
VertX += pEdgeX[pNext->Value];
VertY += pEdgeY[pNext->Value];
}
pVertX[pThis->Value] = VertX / (Emb_ObjFaninNum(pThis) + 1);
pVertY[pThis->Value] = VertY / (Emb_ObjFaninNum(pThis) + 1);
}
// sort these numbers
pPermX = Gia_SortFloats( pVertX, NULL, p->nObjs );
pPermY = Gia_SortFloats( pVertY, NULL, p->nObjs );
for ( k = 0; k < p->nObjs; k++ )
{
p->pPlacement[2*pPermX[k]+0] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
p->pPlacement[2*pPermY[k]+1] = (unsigned short)(int)(1.0 * k * GIA_PLACE_SIZE / p->nObjs);
}
ABC_FREE( pPermX );
ABC_FREE( pPermY );
// evaluate cost
if ( fVerbose )
{
printf( "%2d : HPWL = %e ", Iter+1, CostThis );
ABC_PRT( "Time", Abc_Clock() - clk );
}
}
ABC_FREE( pEdgeX );
ABC_FREE( pEdgeY );
ABC_FREE( pVertX );
ABC_FREE( pVertY );
}
/**Function*************************************************************
Synopsis [Derives solutions from original vectors and eigenvectors.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManPrintSolutions( Emb_Man_t * p, int nSols )
{
float * pSol;
int i, k;
for ( i = 0; i < nSols; i++ )
{
pSol = Emb_ManSol( p, i );
for ( k = 0; k < p->nObjs; k++ )
printf( "%4d ", (int)(100 * pSol[k]) );
printf( "\n" );
}
}
/**Function*************************************************************
Synopsis [Prepares image for dumping.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Int_t * Emb_ManDumpGnuplotPrepare( Emb_Man_t * p )
{
// int nRows = 496;
// int nCols = 710;
int nRows = 500;
int nCols = 700;
Vec_Int_t * vLines;
Emb_Obj_t * pThis;
char * pBuffer, ** ppRows;
int i, k, placeX, placeY;
int fStart;
// alloc memory
pBuffer = ABC_CALLOC( char, nRows * (nCols+1) );
ppRows = ABC_ALLOC( char *, nRows );
for ( i = 0; i < nRows; i++ )
ppRows[i] = pBuffer + i*(nCols+1);
// put data into them
Emb_ManForEachObj( p, pThis, i )
{
placeX = p->pPlacement[2*pThis->Value+0] * nCols / (1<<16);
placeY = p->pPlacement[2*pThis->Value+1] * nRows / (1<<16);
assert( placeX < nCols && placeY < nRows );
ppRows[placeY][placeX] = 1;
}
// select lines
vLines = Vec_IntAlloc( 1000 );
for ( i = 0; i < nRows; i++ )
{
fStart = 0;
for ( k = 0; k <= nCols; k++ )
{
if ( ppRows[i][k] && !fStart )
{
Vec_IntPush( vLines, k );
Vec_IntPush( vLines, i );
fStart = 1;
}
if ( !ppRows[i][k] && fStart )
{
Vec_IntPush( vLines, k-1 );
Vec_IntPush( vLines, i );
fStart = 0;
}
}
assert( fStart == 0 );
}
ABC_FREE( pBuffer );
ABC_FREE( ppRows );
return vLines;
}
/**Function*************************************************************
Synopsis [Derives solutions from original vectors and eigenvectors.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Emb_ManDumpGnuplot( Emb_Man_t * p, char * pName, int fDumpLarge, int fShowImage )
{
extern void Gia_ManGnuplotShow( char * pPlotFileName );
// char * pDirectory = "place\\";
char * pDirectory = "";
// extern char * Ioa_TimeStamp();
FILE * pFile;
char Buffer[1000];
Emb_Obj_t * pThis, * pNext;
int i, k;
if ( p->pPlacement == NULL )
{
printf( "Emb_ManDumpGnuplot(): Placement is not available.\n" );
return;
}
sprintf( Buffer, "%s%s", pDirectory, Gia_FileNameGenericAppend(pName, ".plt") );
pFile = fopen( Buffer, "w" );
fprintf( pFile, "# This Gnuplot file was produced by ABC on %s\n", Ioa_TimeStamp() );
fprintf( pFile, "\n" );
fprintf( pFile, "set nokey\n" );
fprintf( pFile, "\n" );
if ( !fShowImage )
{
// fprintf( pFile, "set terminal postscript\n" );
fprintf( pFile, "set terminal gif font \'arial\' 10 size 800,600 xffffff x000000 x000000 x000000\n" );
fprintf( pFile, "set output \'%s\'\n", Gia_FileNameGenericAppend(pName, ".gif") );
fprintf( pFile, "\n" );
}
fprintf( pFile, "set title \"%s : PI = %d PO = %d FF = %d Node = %d Obj = %d HPWL = %.2e\\n",
pName, Emb_ManPiNum(p), Emb_ManPoNum(p), Emb_ManRegNum(p), Emb_ManNodeNum(p), Emb_ManObjNum(p), Emb_ManComputeHPWL(p) );
fprintf( pFile, "(image generated by ABC and Gnuplot on %s)\"", Ioa_TimeStamp() );
fprintf( pFile, "font \"Times, 12\"\n" );
fprintf( pFile, "\n" );
fprintf( pFile, "plot [:] '-' w l\n" );
fprintf( pFile, "\n" );
if ( fDumpLarge )
{
int begX, begY, endX, endY;
Vec_Int_t * vLines = Emb_ManDumpGnuplotPrepare( p );
Vec_IntForEachEntry( vLines, begX, i )
{
begY = Vec_IntEntry( vLines, i+1 );
endX = Vec_IntEntry( vLines, i+2 );
endY = Vec_IntEntry( vLines, i+3 );
i += 3;
fprintf( pFile, "%5d %5d\n", begX, begY );
fprintf( pFile, "%5d %5d\n", endX, endY );
fprintf( pFile, "\n" );
}
Vec_IntFree( vLines );
}
else
{
Emb_ManForEachObj( p, pThis, i )
{
if ( !Emb_ObjIsTravIdCurrent(p, pThis) )
continue;
Emb_ObjForEachFanout( pThis, pNext, k )
{
assert( Emb_ObjIsTravIdCurrent(p, pNext) );
fprintf( pFile, "%5d %5d\n", p->pPlacement[2*pThis->Value+0], p->pPlacement[2*pThis->Value+1] );
fprintf( pFile, "%5d %5d\n", p->pPlacement[2*pNext->Value+0], p->pPlacement[2*pNext->Value+1] );
fprintf( pFile, "\n" );
}
}
}
fprintf( pFile, "EOF\n" );
fprintf( pFile, "\n" );
if ( fShowImage )
{
fprintf( pFile, "pause -1 \"Close window\"\n" ); // Hit return to continue
fprintf( pFile, "reset\n" );
fprintf( pFile, "\n" );
}
else
{
fprintf( pFile, "# pause -1 \"Close window\"\n" ); // Hit return to continue
fprintf( pFile, "# reset\n" );
fprintf( pFile, "\n" );
}
fclose( pFile );
if ( fShowImage )
Gia_ManGnuplotShow( Buffer );
}
/**Function*************************************************************
Synopsis [Computes dimentions of the graph.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Gia_ManSolveProblem( Gia_Man_t * pGia, Emb_Par_t * pPars )
{
Emb_Man_t * p;
int i;
abctime clkSetup;
abctime clk;
// Gia_ManTestDistance( pGia );
// transform AIG into internal data-structure
clk = Abc_Clock();
if ( pPars->fCluster )
{
p = Emb_ManStart( pGia );
if ( pPars->fVerbose )
{
printf( "Clustered: " );
Emb_ManPrintStats( p );
}
}
else
p = Emb_ManStartSimple( pGia );
p->fVerbose = pPars->fVerbose;
// Emb_ManPrintFanio( p );
// prepare data-structure
Gia_ManRandom( 1 ); // reset random numbers for deterministic behavior
Emb_ManResetTravId( p );
Emb_ManSetValue( p );
clkSetup = Abc_Clock() - clk;
clk = Abc_Clock();
Emb_ManComputeDimensions( p, pPars->nDims );
if ( pPars->fVerbose )
ABC_PRT( "Setup ", clkSetup );
if ( pPars->fVerbose )
ABC_PRT( "Dimensions", Abc_Clock() - clk );
clk = Abc_Clock();
Emb_ManComputeCovariance( p, pPars->nDims );
if ( pPars->fVerbose )
ABC_PRT( "Matrix ", Abc_Clock() - clk );
clk = Abc_Clock();
Emb_ManComputeEigenvectors( p, pPars->nDims, pPars->nSols );
Emb_ManComputeSolutions( p, pPars->nDims, pPars->nSols );
Emb_ManDerivePlacement( p, pPars->nSols );
if ( pPars->fVerbose )
ABC_PRT( "Eigenvecs ", Abc_Clock() - clk );
if ( pPars->fRefine )
{
clk = Abc_Clock();
Emb_ManPlacementRefine( p, pPars->nIters, pPars->fVerbose );
if ( pPars->fVerbose )
ABC_PRT( "Refinement", Abc_Clock() - clk );
}
if ( (pPars->fDump || pPars->fDumpLarge) && pPars->nSols == 2 )
{
clk = Abc_Clock();
Emb_ManDumpGnuplot( p, pGia->pName, pPars->fDumpLarge, pPars->fShowImage );
if ( pPars->fVerbose )
ABC_PRT( "Image dump", Abc_Clock() - clk );
}
// transfer placement
if ( Gia_ManObjNum(pGia) == p->nObjs )
{
// assuming normalized ordering of the AIG
pGia->pPlacement = ABC_CALLOC( Gia_Plc_t, p->nObjs );
for ( i = 0; i < p->nObjs; i++ )
{
pGia->pPlacement[i].xCoord = p->pPlacement[2*i+0];
pGia->pPlacement[i].yCoord = p->pPlacement[2*i+1];
}
}
Emb_ManStop( p );
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END