nwkMerge.h File Reference

Go to the source code of this file.

Data Structures
struct	Nwk_LMPars_t_
struct	Nwk_Edg_t_
struct	Nwk_Vrt_t_
struct	Nwk_Grf_t_

Macros
#define	NWK_MAX_LIST   16
	INCLUDES ///. More...
#define	Nwk_GraphForEachEdge(p, pEdge, k)
	MACRO DEFINITIONS ///. More...
#define	Nwk_ListForEachVertex(p, List, pVrt)
#define	Nwk_VertexForEachAdjacent(p, pVrt, pNext, k)   for ( k = 0; (k < pVrt->nEdges) && (((pNext) = p->pVerts[pVrt->pEdges[k]]), 1); k++ )

Typedefs
typedef struct Nwk_LMPars_t_	Nwk_LMPars_t
	BASIC TYPES ///. More...
typedef struct Nwk_Edg_t_	Nwk_Edg_t
typedef struct Nwk_Vrt_t_	Nwk_Vrt_t
typedef struct Nwk_Grf_t_	Nwk_Grf_t

Functions
ABC_DLL Nwk_Grf_t *	Nwk_ManGraphAlloc (int nVertsMax)
	INLINED FUNCTIONS ///. More...
ABC_DLL void	Nwk_ManGraphFree (Nwk_Grf_t *p)
ABC_DLL void	Nwk_ManGraphReportMemoryUsage (Nwk_Grf_t *p)
ABC_DLL void	Nwk_ManGraphHashEdge (Nwk_Grf_t *p, int iLut1, int iLut2)
ABC_DLL void	Nwk_ManGraphSolve (Nwk_Grf_t *p)
ABC_DLL int	Nwk_ManLutMergeGraphTest (char *pFileName)

Macro Definition Documentation

#define Nwk_GraphForEachEdge	(		p,
			pEdge,
			k
	)

Value:

for ( k = 0; k < p->nEdgeHash; k++ )                \
        for ( pEdge = p->pEdgeHash[k]; pEdge; pEdge = pEdge->pNext )

MACRO DEFINITIONS ///.

Definition at line 111 of file nwkMerge.h.

#define Nwk_ListForEachVertex	(		p,
			List,
			pVrt
	)

Value:

for ( pVrt = List? p->pVerts[List] : NULL;  pVrt;   \
          pVrt = pVrt->iNext? p->pVerts[pVrt->iNext] : NULL )

Definition at line 115 of file nwkMerge.h.

#define NWK_MAX_LIST   16

INCLUDES ///.

CFile****************************************************************

FileName [nwkMerge.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Logic network representation.]

Synopsis [External declarations.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

nwkMerge.h,v 1.1 2008/05/14 22:13:09 wudenni Exp

]PARAMETERS ///

Definition at line 38 of file nwkMerge.h.

#define Nwk_VertexForEachAdjacent	(		p,
			pVrt,
			pNext,
			k
	)		for ( k = 0; (k < pVrt->nEdges) && (((pNext) = p->pVerts[pVrt->pEdges[k]]), 1); k++ )

Definition at line 119 of file nwkMerge.h.

Typedef Documentation

typedef struct Nwk_Edg_t_ Nwk_Edg_t

Definition at line 60 of file nwkMerge.h.

typedef struct Nwk_Grf_t_ Nwk_Grf_t

Definition at line 80 of file nwkMerge.h.

typedef struct Nwk_LMPars_t_ Nwk_LMPars_t

BASIC TYPES ///.

Definition at line 45 of file nwkMerge.h.

typedef struct Nwk_Vrt_t_ Nwk_Vrt_t

Definition at line 69 of file nwkMerge.h.

Function Documentation

ABC_DLL Nwk_Grf_t* Nwk_ManGraphAlloc

(

int

nVertsMax

)

INLINED FUNCTIONS ///.

ITERATORS ///FUNCTION DECLARATIONS ///

INLINED FUNCTIONS ///.

CFile****************************************************************

FileName [nwkMerge.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Netlist representation.]

Synopsis [LUT merging algorithm.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

nwkMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Allocates the graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 46 of file nwkMerge.c.

{
    Nwk_Grf_t * p;
    p = ABC_ALLOC( Nwk_Grf_t, 1 );
    memset( p, 0, sizeof(Nwk_Grf_t) );
    p->nVertsMax = nVertsMax;
    p->nEdgeHash = Abc_PrimeCudd( 3 * nVertsMax );
    p->pEdgeHash = ABC_CALLOC( Nwk_Edg_t *, p->nEdgeHash );
    p->pMemEdges = Aig_MmFixedStart( sizeof(Nwk_Edg_t), p->nEdgeHash );
    p->vPairs    = Vec_IntAlloc( 1000 );
    return p;
}

ABC_DLL void Nwk_ManGraphFree

(

Nwk_Grf_t *

p

)

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

Synopsis [Deallocates the graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 70 of file nwkMerge.c.

{
    if ( p->vPairs )    Vec_IntFree( p->vPairs );
    if ( p->pMemEdges ) Aig_MmFixedStop( p->pMemEdges, 0 );
    if ( p->pMemVerts ) Aig_MmFlexStop( p->pMemVerts, 0 );
    ABC_FREE( p->pVerts );
    ABC_FREE( p->pEdgeHash );
    ABC_FREE( p->pMapLut2Id );
    ABC_FREE( p->pMapId2Lut );
    ABC_FREE( p );
}

ABC_DLL void Nwk_ManGraphHashEdge	(	Nwk_Grf_t *	p,
		int	iLut1,
		int	iLut2
	)

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

Synopsis [Finds or adds the edge to the graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 119 of file nwkMerge.c.

{
    Nwk_Edg_t * pEntry;
    unsigned Key;
    if ( iLut1 == iLut2 )
        return;
    if ( iLut1 > iLut2 )
    {
        Key = iLut1;
        iLut1 = iLut2;
        iLut2 = Key;
    }
    assert( iLut1 < iLut2 );
    if ( p->nObjs < iLut2 )
        p->nObjs = iLut2;
    Key = (unsigned)(741457 * iLut1 + 4256249 * iLut2) % p->nEdgeHash;
    for ( pEntry = p->pEdgeHash[Key]; pEntry; pEntry = pEntry->pNext )
        if ( pEntry->iNode1 == iLut1 && pEntry->iNode2 == iLut2 )
            return;
    pEntry = (Nwk_Edg_t *)Aig_MmFixedEntryFetch( p->pMemEdges );
    pEntry->iNode1 = iLut1;
    pEntry->iNode2 = iLut2;
    pEntry->pNext = p->pEdgeHash[Key];
    p->pEdgeHash[Key] = pEntry;
    p->nEdges++;
}

ABC_DLL void Nwk_ManGraphReportMemoryUsage

(

Nwk_Grf_t *

p

)

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

Synopsis [Prepares the graph for solving the problem.]

Description []

SideEffects []

SeeAlso []

Definition at line 93 of file nwkMerge.c.

{
    p->nMemBytes1 = 
        sizeof(Nwk_Grf_t) +
        sizeof(void *) * p->nEdgeHash + 
        sizeof(int) * (p->nObjs + p->nVertsMax) +
        sizeof(Nwk_Edg_t) * p->nEdges;
    p->nMemBytes2 = 
        sizeof(Nwk_Vrt_t) * p->nVerts + 
        sizeof(int) * 2 * p->nEdges;
    printf( "Memory usage stats:  Preprocessing = %.2f MB.  Solving = %.2f MB.\n",
        1.0 * p->nMemBytes1 / (1<<20), 1.0 * p->nMemBytes2 / (1<<20) );
}

ABC_DLL void Nwk_ManGraphSolve

(

Nwk_Grf_t *

p

)

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

Synopsis [Solves the problem by extracting one edge at a time.]

Description []

SideEffects []

SeeAlso []

Definition at line 621 of file nwkMerge.c.

{
    Nwk_Vrt_t * pVertex, * pNext;
    int i, j;
    Nwk_ManGraphPrepare( p );
    while ( 1 )
    {
        // find the next vertex to extract
        assert( p->pLists1[0] == 0 );
        for ( i = 1; i <= NWK_MAX_LIST; i++ )
            if ( p->pLists1[i] )
            {
//                printf( "%d ", i );
//                printf( "ListA = %2d. Length = %5d.\n", i, Nwk_ManGraphListLength(p,p->pLists1[i]) );
                pVertex = p->pVerts[ p->pLists1[i] ];
                assert( pVertex->nEdges == 1 );
                pNext = p->pVerts[ pVertex->pEdges[0] ];
                Nwk_ManGraphUpdate( p, pVertex, pNext );
                break;
            }
        if ( i < NWK_MAX_LIST + 1 )
            continue;
        // find the next vertex to extract
        assert( p->pLists2[0] == 0 );
        assert( p->pLists2[1] == 0 );
        for ( j = 2; j <= NWK_MAX_LIST; j++ )
            if ( p->pLists2[j] )
            {
//                printf( "***%d ", j );
//                printf( "ListB = %2d. Length = %5d.\n", j, Nwk_ManGraphListLength(p,p->pLists2[j]) );
                pVertex = Nwk_ManGraphListFindMin( p, p->pLists2[j] ); 
                assert( pVertex->nEdges == j || j == NWK_MAX_LIST );
                pNext = Nwk_ManGraphListFindMinEdge( p, pVertex );
                Nwk_ManGraphUpdate( p, pVertex, pNext );
                break;
            }
        if ( j == NWK_MAX_LIST + 1 )
            break;
    }
    Nwk_ManGraphSortPairs( p );
}

ABC_DLL int Nwk_ManLutMergeGraphTest

(

char *

pFileName

)

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

Synopsis [Solves the graph coming from file.]

Description []

SideEffects []

SeeAlso []

Definition at line 703 of file nwkMerge.c.

{
    int nPairs;
    Nwk_Grf_t * p;
    abctime clk = Abc_Clock();
    p = Nwk_ManLutMergeReadGraph( pFileName );
    ABC_PRT( "Reading", Abc_Clock() - clk );
    clk = Abc_Clock();
    Nwk_ManGraphSolve( p );
    printf( "GRAPH: Nodes = %6d. Edges = %6d.  Pairs = %6d.  ", 
        p->nVerts, p->nEdges, Vec_IntSize(p->vPairs)/2 );
    ABC_PRT( "Solving", Abc_Clock() - clk );
    nPairs = Vec_IntSize(p->vPairs)/2;
    Nwk_ManGraphReportMemoryUsage( p );
    Nwk_ManGraphFree( p );
    return nPairs;
}