giaForce.c File Reference

#include "gia.h"

Go to the source code of this file.

Data Structures
struct	Frc_Obj_t_
struct	Frc_Man_t_

Macros
#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++ )

Typedefs
typedef typedefABC_NAMESPACE_IMPL_START struct Frc_Obj_t_	Frc_Obj_t
	DECLARATIONS ///. More...
typedef struct Frc_Man_t_	Frc_Man_t

Functions
static int	Frc_ManRegNum (Frc_Man_t *p)
static int	Frc_ManCiNum (Frc_Man_t *p)
static int	Frc_ManCoNum (Frc_Man_t *p)
static int	Frc_ManPiNum (Frc_Man_t *p)
static int	Frc_ManPoNum (Frc_Man_t *p)
static int	Frc_ManObjNum (Frc_Man_t *p)
static int	Frc_ManNodeNum (Frc_Man_t *p)
static Frc_Obj_t *	Frc_ManObj (Frc_Man_t *p, int hHandle)
static Frc_Obj_t *	Frc_ManCi (Frc_Man_t *p, int i)
static Frc_Obj_t *	Frc_ManCo (Frc_Man_t *p, int i)
static int	Frc_ObjIsTerm (Frc_Obj_t *pObj)
static int	Frc_ObjIsCi (Frc_Obj_t *pObj)
static int	Frc_ObjIsCo (Frc_Obj_t *pObj)
static int	Frc_ObjIsPi (Frc_Obj_t *pObj)
static int	Frc_ObjIsPo (Frc_Obj_t *pObj)
static int	Frc_ObjIsNode (Frc_Obj_t *pObj)
static int	Frc_ObjIsConst0 (Frc_Obj_t *pObj)
static int	Frc_ObjSize (Frc_Obj_t *pObj)
static int	Frc_ObjFaninNum (Frc_Obj_t *pObj)
static int	Frc_ObjFanoutNum (Frc_Obj_t *pObj)
static Frc_Obj_t *	Frc_ObjFanin (Frc_Obj_t *pObj, int i)
static Frc_Obj_t *	Frc_ObjFanout (Frc_Obj_t *pObj, int i)
void	Frc_ObjAddFanin (Frc_Obj_t *pObj, Frc_Obj_t *pFanin)
	FUNCTION DEFINITIONS ///. More...
Frc_Man_t *	Frc_ManStartSimple (Gia_Man_t *pGia)
void	Frc_ManCollectSuper_rec (Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSuper, Vec_Int_t *vVisit)
void	Frc_ManCollectSuper (Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSuper, Vec_Int_t *vVisit)
void	Frc_ManCreateRefsSpecial (Gia_Man_t *p)
void	Frc_ManTransformRefs (Gia_Man_t *p, int *pnObjs, int *pnFanios)
Frc_Man_t *	Frc_ManStart (Gia_Man_t *pGia)
void	Frc_ManPrintStats (Frc_Man_t *p)
void	Frc_ManStop (Frc_Man_t *p)
int	Frc_ManCrossCut_rec (Frc_Man_t *p, Frc_Obj_t *pObj)
int	Frc_ManCrossCut2_rec (Frc_Man_t *p, Frc_Obj_t *pObj)
int	Frc_ManCrossCut (Frc_Man_t *p, Vec_Int_t *vOrder, int fReverse)
Vec_Int_t *	Frc_ManCollectCos (Frc_Man_t *p)
void	Frc_ManCrossCutTest (Frc_Man_t *p, Vec_Int_t *vOrderInit)
void	Frc_ManPlaceRandom (Frc_Man_t *p)
void	Frc_ManArrayShuffle (Vec_Int_t *vArray)
void	Frc_ManPlaceDfs_rec (Frc_Man_t *p, Frc_Obj_t *pObj, int *piPlace)
void	Frc_ManPlaceDfs (Frc_Man_t *p, Vec_Int_t *vCoOrder)
int	Frc_ManPlaceDfsBoth (Frc_Man_t *p, Vec_Int_t *vCoOrder, int *piCutSize2)
void	Frc_ManPlacementRefine (Frc_Man_t *p, int nIters, int fVerbose)
int	Frc_ObjFanoutsAreCos (Frc_Obj_t *pThis)
void	Frc_DumpGraphIntoFile (Frc_Man_t *p)
void	For_ManExperiment (Gia_Man_t *pGia, int nIters, int fClustered, int fVerbose)
void	For_ManFileExperiment ()

Macro Definition Documentation

#define Frc_ManForEachCi	(		p,
			pObj,
			i
	)		for ( i = 0; (i < Vec_IntSize(p->vCis)) && (pObj = Frc_ManObj(p,Vec_IntEntry(p->vCis,i))); i++ )

Definition at line 103 of file giaForce.c.

#define Frc_ManForEachCo	(		p,
			pObj,
			i
	)		for ( i = 0; (i < Vec_IntSize(p->vCos)) && (pObj = Frc_ManObj(p,Vec_IntEntry(p->vCos,i))); i++ )

Definition at line 105 of file giaForce.c.

#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

Definition at line 101 of file giaForce.c.

#define Frc_ManForEachObj	(		p,
			pObj,
			i
	)		for ( i = 0; (i < p->nObjData) && (pObj = Frc_ManObj(p,i)); i += Frc_ObjSize(pObj) )

Definition at line 96 of file giaForce.c.

#define Frc_ManForEachObjVec	(		vVec,
			p,
			pObj,
			i
	)		for ( i = 0; (i < Vec_IntSize(vVec)) && ((pObj) = Frc_ManObj(p, Vec_IntEntry(vVec,i))); i++ )

Definition at line 98 of file giaForce.c.

#define Frc_ObjForEachFanin	(		pObj,
			pNext,
			i
	)		for ( i = 0; (i < (int)pObj->nFanins) && (pNext = Frc_ObjFanin(pObj,i)); i++ )

Definition at line 108 of file giaForce.c.

#define Frc_ObjForEachFaninReverse	(		pObj,
			pNext,
			i
	)		for ( i = (int)pObj->nFanins - 1; (i >= 0) && (pNext = Frc_ObjFanin(pObj,i)); i-- )

Definition at line 110 of file giaForce.c.

#define Frc_ObjForEachFanout	(		pObj,
			pNext,
			i
	)		for ( i = 0; (i < (int)pObj->nFanouts) && (pNext = Frc_ObjFanout(pObj,i)); i++ )

Definition at line 112 of file giaForce.c.

Typedef Documentation

typedef struct Frc_Man_t_ Frc_Man_t

Definition at line 55 of file giaForce.c.

typedef typedefABC_NAMESPACE_IMPL_START struct Frc_Obj_t_ Frc_Obj_t

DECLARATIONS ///.

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

]

Definition at line 36 of file giaForce.c.

Function Documentation

void For_ManExperiment	(	Gia_Man_t *	pGia,
		int	nIters,
		int	fClustered,
		int	fVerbose
	)

Function*************************************************************

Synopsis [Experiment with the FORCE algorithm.]

Description []

SideEffects []

SeeAlso []

Definition at line 1039 of file giaForce.c.

{
    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 );
}

void For_ManFileExperiment

(

)

Function*************************************************************

Synopsis [Experiment with the FORCE algorithm.]

Description []

SideEffects []

SeeAlso []

Definition at line 1066 of file giaForce.c.

{
    FILE * pFile;
    int * pBuffer;
    int i, Size, Exp = 25;
    abctime clk = Abc_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", Abc_Clock() - clk );

clk = Abc_Clock();
    pFile = fopen( "test.txt", "rb" );
    RetValue = fread( pBuffer, 1, sizeof(int) * Size, pFile );
    fclose( pFile );
ABC_PRT( "Read  ", Abc_Clock() - clk );

clk = Abc_Clock();
    pFile = fopen( "test.txt", "wb" );
    fwrite( pBuffer, 1, sizeof(int) * Size, pFile );
    fclose( pFile );
ABC_PRT( "Write ", Abc_Clock() - clk );
/*
2^25 machine words (134217728 bytes).
Fillup =    0.06 sec
Read   =    0.08 sec
Write  =    1.81 sec
*/
}

void Frc_DumpGraphIntoFile

(

Frc_Man_t *

p

)

Function*************************************************************

Synopsis [Computes the distances from the given set of objects.]

Description [Returns one of the most distant objects.]

SideEffects []

SeeAlso []

Definition at line 1002 of file giaForce.c.

{
    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 );
}

void Frc_ManArrayShuffle

(

Vec_Int_t *

vArray

)

Function*************************************************************

Synopsis [Shuffles array of random integers.]

Description []

SideEffects []

SeeAlso []

Definition at line 775 of file giaForce.c.

{
    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;
    }
}

static Frc_Obj_t* Frc_ManCi ( Frc_Man_t *  p, int  i  )

inlinestatic

Definition at line 79 of file giaForce.c.

{ return Frc_ManObj( p, Vec_IntEntry(p->vCis,i) );                     }

static int Frc_ManCiNum ( Frc_Man_t *  p )

inlinestatic

Definition at line 71 of file giaForce.c.

{ return Vec_IntSize(p->vCis);                                         }

static Frc_Obj_t* Frc_ManCo ( Frc_Man_t *  p, int  i  )

inlinestatic

Definition at line 80 of file giaForce.c.

{ return Frc_ManObj( p, Vec_IntEntry(p->vCos,i) );                     }

Vec_Int_t* Frc_ManCollectCos

(

Frc_Man_t *

p

)

Function*************************************************************

Synopsis [Collects CO handles.]

Description []

SideEffects []

SeeAlso []

Definition at line 692 of file giaForce.c.

{
    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;
}

void Frc_ManCollectSuper	(	Gia_Man_t *	p,
		Gia_Obj_t *	pObj,
		Vec_Int_t *	vSuper,
		Vec_Int_t *	vVisit
	)

Function*************************************************************

Synopsis [Collect the fanin IDs.]

Description []

SideEffects []

SeeAlso []

Definition at line 289 of file giaForce.c.

{
    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;
}

void Frc_ManCollectSuper_rec	(	Gia_Man_t *	p,
		Gia_Obj_t *	pObj,
		Vec_Int_t *	vSuper,
		Vec_Int_t *	vVisit
	)

Function*************************************************************

Synopsis [Collect the fanin IDs.]

Description []

SideEffects []

SeeAlso []

Definition at line 261 of file giaForce.c.

{
    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 );
    
}

static int Frc_ManCoNum ( Frc_Man_t *  p )

inlinestatic

Definition at line 72 of file giaForce.c.

{ return Vec_IntSize(p->vCos);                                         }

void Frc_ManCreateRefsSpecial

(

Gia_Man_t *

p

)

Function*************************************************************

Synopsis [Assigns references while removing the MUX/XOR ones.]

Description []

SideEffects []

SeeAlso []

Definition at line 313 of file giaForce.c.

{
    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 );
}

int Frc_ManCrossCut	(	Frc_Man_t *	p,
		Vec_Int_t *	vOrder,
		int	fReverse
	)

Function*************************************************************

Synopsis [Computes cross cut size for the given order of POs.]

Description []

SideEffects []

SeeAlso []

Definition at line 658 of file giaForce.c.

{
    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;
}

int Frc_ManCrossCut2_rec	(	Frc_Man_t *	p,
		Frc_Obj_t *	pObj
	)

Function*************************************************************

Synopsis [Computes cross cut size for the given order of POs.]

Description []

SideEffects []

SeeAlso []

Definition at line 631 of file giaForce.c.

{
    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;
}

int Frc_ManCrossCut_rec	(	Frc_Man_t *	p,
		Frc_Obj_t *	pObj
	)

Function*************************************************************

Synopsis [Computes cross cut size for the given order of POs.]

Description []

SideEffects []

SeeAlso []

Definition at line 604 of file giaForce.c.

{
    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;
}

void Frc_ManCrossCutTest	(	Frc_Man_t *	p,
		Vec_Int_t *	vOrderInit
	)

Function*************************************************************

Synopsis [Computes cross cut size for the given order of POs.]

Description []

SideEffects []

SeeAlso []

Definition at line 714 of file giaForce.c.

{
    Vec_Int_t * vOrder;
//    abctime clk = Abc_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", Abc_Clock() - clk );
}

static int Frc_ManNodeNum ( Frc_Man_t *  p )

inlinestatic

Definition at line 76 of file giaForce.c.

{ return p->nObjs - Vec_IntSize(p->vCis) - Vec_IntSize(p->vCos);       } 

static Frc_Obj_t* Frc_ManObj ( Frc_Man_t *  p, int  hHandle  )

inlinestatic

Definition at line 78 of file giaForce.c.

{ return (Frc_Obj_t *)(p->pObjData + hHandle);                         } 

static int Frc_ManObjNum ( Frc_Man_t *  p )

inlinestatic

Definition at line 75 of file giaForce.c.

{ return p->nObjs;                                                     } 

static int Frc_ManPiNum ( Frc_Man_t *  p )

inlinestatic

Definition at line 73 of file giaForce.c.

{ return Vec_IntSize(p->vCis) - p->nRegs;                              }

void Frc_ManPlaceDfs	(	Frc_Man_t *	p,
		Vec_Int_t *	vCoOrder
	)

Function*************************************************************

Synopsis [Generates DFS placement.]

Description []

SideEffects []

SeeAlso []

Definition at line 823 of file giaForce.c.

{
    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 );
}

void Frc_ManPlaceDfs_rec	(	Frc_Man_t *	p,
		Frc_Obj_t *	pObj,
		int *	piPlace
	)

Function*************************************************************

Synopsis [Computes cross cut size for the given order of POs.]

Description []

SideEffects []

SeeAlso []

Definition at line 798 of file giaForce.c.

{
    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)++;
    }
}

int Frc_ManPlaceDfsBoth	(	Frc_Man_t *	p,
		Vec_Int_t *	vCoOrder,
		int *	piCutSize2
	)

Function*************************************************************

Synopsis [Generates DFS placement by trying both orders.]

Description [Returns the cross cut size of the best order. ]

SideEffects []

SeeAlso []

Definition at line 853 of file giaForce.c.

{
    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;
    }
}

void Frc_ManPlacementRefine	(	Frc_Man_t *	p,
		int	nIters,
		int	fVerbose
	)

Function*************************************************************

Synopsis [Performs iterative refinement of the given placement.]

Description []

SideEffects []

SeeAlso []

Definition at line 886 of file giaForce.c.

{
    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;
    abctime clk = Abc_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 = Abc_Clock();
        pPermX = Gia_SortFloats( pVertX, pHandles, p->nObjs );
        clk2Total += Abc_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", Abc_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 );
}

void Frc_ManPlaceRandom

(

Frc_Man_t *

p

)

Function*************************************************************

Synopsis [Generates random placement.]

Description []

SideEffects []

SeeAlso []

Definition at line 743 of file giaForce.c.

{
    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 );
}

static int Frc_ManPoNum ( Frc_Man_t *  p )

inlinestatic

Definition at line 74 of file giaForce.c.

{ return Vec_IntSize(p->vCos) - p->nRegs;                              }

void Frc_ManPrintStats

(

Frc_Man_t *

p

)

Function*************************************************************

Synopsis [Creates logic network isomorphic to the given AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 557 of file giaForce.c.

{
//    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" );
}

static int Frc_ManRegNum ( Frc_Man_t *  p )

inlinestatic

Definition at line 70 of file giaForce.c.

{ return p->nRegs;                                                     }

Frc_Man_t* Frc_ManStart

(

Gia_Man_t *

pGia

)

Function*************************************************************

Synopsis [Creates logic network isomorphic to the given AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 428 of file giaForce.c.

{
    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;
}

Frc_Man_t* Frc_ManStartSimple

(

Gia_Man_t *

pGia

)

Function*************************************************************

Synopsis [Creates logic network isomorphic to the given AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 150 of file giaForce.c.

{
    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;
}

void Frc_ManStop

(

Frc_Man_t *

p

)

Function*************************************************************

Synopsis [Creates logic network isomorphic to the given AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 584 of file giaForce.c.

{
    Vec_IntFree( p->vCis );
    Vec_IntFree( p->vCos );
    ABC_FREE( p->pObjData );
    ABC_FREE( p );
}

void Frc_ManTransformRefs	(	Gia_Man_t *	p,
		int *	pnObjs,
		int *	pnFanios
	)

Function*************************************************************

Synopsis [Assigns references while removing the MUX/XOR ones.]

Description []

SideEffects []

SeeAlso []

Definition at line 359 of file giaForce.c.

{
    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);
}

void Frc_ObjAddFanin	(	Frc_Obj_t *	pObj,
		Frc_Obj_t *	pFanin
	)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Creates fanin/fanout pair.]

Description []

SideEffects []

SeeAlso []

Definition at line 131 of file giaForce.c.

{ 
    assert( pObj->iFanin < pObj->nFanins );
    assert( pFanin->iFanout < pFanin->nFanouts );
    pFanin->Fanios[pFanin->nFanins + pFanin->iFanout++] = 
        pObj->Fanios[pObj->iFanin++] = pObj->hHandle - pFanin->hHandle;
}

static Frc_Obj_t* Frc_ObjFanin ( Frc_Obj_t *  pObj, int  i  )

inlinestatic

Definition at line 93 of file giaForce.c.

{ return (Frc_Obj_t *)(((int *)pObj) - pObj->Fanios[i]);               } 

static int Frc_ObjFaninNum ( Frc_Obj_t *  pObj )

inlinestatic

Definition at line 91 of file giaForce.c.

{ return pObj->nFanins;                                                } 

static Frc_Obj_t* Frc_ObjFanout ( Frc_Obj_t *  pObj, int  i  )

inlinestatic

Definition at line 94 of file giaForce.c.

{ return (Frc_Obj_t *)(((int *)pObj) + pObj->Fanios[pObj->nFanins+i]); } 

static int Frc_ObjFanoutNum ( Frc_Obj_t *  pObj )

inlinestatic

Definition at line 92 of file giaForce.c.

{ return pObj->nFanouts;                                               } 

int Frc_ObjFanoutsAreCos

(

Frc_Obj_t *

pThis

)

Function*************************************************************

Synopsis [Returns 1 if all fanouts are COsw.]

Description []

SideEffects []

SeeAlso []

Definition at line 981 of file giaForce.c.

{
    Frc_Obj_t * pNext;
    int i;
    Frc_ObjForEachFanout( pThis, pNext, i )
        if ( !Frc_ObjIsCo(pNext) )
            return 0;
    return 1;
}

static int Frc_ObjIsCi ( Frc_Obj_t *  pObj )

inlinestatic

Definition at line 83 of file giaForce.c.

{ return pObj->fCi;                                                    } 

static int Frc_ObjIsCo ( Frc_Obj_t *  pObj )

inlinestatic

Definition at line 84 of file giaForce.c.

{ return pObj->fCo;                                                    } 

static int Frc_ObjIsConst0 ( Frc_Obj_t *  pObj )

inlinestatic

Definition at line 88 of file giaForce.c.

{ return!Frc_ObjIsTerm(pObj) && pObj->nFanins == 0;                    } 

static int Frc_ObjIsNode ( Frc_Obj_t *  pObj )

inlinestatic

Definition at line 87 of file giaForce.c.

{ return!Frc_ObjIsTerm(pObj) && pObj->nFanins > 0;                     } 

static int Frc_ObjIsPi ( Frc_Obj_t *  pObj )

inlinestatic

Definition at line 85 of file giaForce.c.

{ return pObj->fCi && pObj->nFanins == 0;                              } 

static int Frc_ObjIsPo ( Frc_Obj_t *  pObj )

inlinestatic

Definition at line 86 of file giaForce.c.

{ return pObj->fCo && pObj->nFanouts == 0;                             } 

static int Frc_ObjIsTerm ( Frc_Obj_t *  pObj )

inlinestatic

Definition at line 82 of file giaForce.c.

{ return pObj->fCi || pObj->fCo;                                       } 

static int Frc_ObjSize ( Frc_Obj_t *  pObj )

inlinestatic

Definition at line 90 of file giaForce.c.

{ return sizeof(Frc_Obj_t) / 4 + pObj->nFanins + pObj->nFanouts;       }