mapperCut.c File Reference

#include "mapperInt.h"

Include dependency graph for mapperCut.c:

Go to the source code of this file.

Classes
struct	Map_CutTableStrutct_t

Macros
#define	MAP_CUTS_MAX_COMPUTE   1000
	DECLARATIONS ///.
#define	MAP_CUTS_MAX_USE   250
#define	Map_ListForEachCut(pList, pCut)
#define	Map_ListForEachCutSafe(pList, pCut, pCut2)

Typedefs
typedef struct Map_CutTableStrutct_t	Map_CutTable_t

Functions
int	Map_MappingCountAllCuts (Map_Man_t *pMan)
	FUNCTION DEFINITIONS ///.
void	Map_MappingCutsInput (Map_Man_t *p, Map_Node_t *pNode)
void	Map_MappingCuts (Map_Man_t *p)
	GLOBAL VARIABLES ///.
Map_Cut_t *	Map_CutMergeLists2 (Map_Man_t *p, Map_CutTable_t *pTable, Map_Cut_t *pList1, Map_Cut_t *pList2, int fComp1, int fComp2)
int	Map_CutSortCutsCompare (Map_Cut_t **pC1, Map_Cut_t **pC2)

Macro Definition Documentation

MAP_CUTS_MAX_COMPUTE

#define MAP_CUTS_MAX_COMPUTE   1000

DECLARATIONS ///.

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

FileName [mapperCut.c]

PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]

Synopsis [Generic technology mapping engine.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 2.0. Started - June 1, 2004.]

Revision [

Id

mapperCut.c,v 1.12 2005/02/28 05:34:27 alanmi Exp

]

Definition at line 29 of file mapperCut.c.

MAP_CUTS_MAX_USE

#define MAP_CUTS_MAX_USE   250

Definition at line 31 of file mapperCut.c.

Map_ListForEachCut

#define Map_ListForEachCut	(		pList,
			pCut )

Value:

    for ( pCut = pList;                                   \
          pCut;                                           \
          pCut = pCut->pNext )

Definition at line 74 of file mapperCut.c.

#define Map_ListForEachCut( pList, pCut )                 \
    for ( pCut = pList;                                   \
          pCut;                                           \
          pCut = pCut->pNext )

Map_ListForEachCutSafe

#define Map_ListForEachCutSafe	(		pList,
			pCut,
			pCut2 )

Value:

    for ( pCut = pList,                                   \
          pCut2 = pCut? pCut->pNext: NULL;                \
          pCut;                                           \
          pCut = pCut2,                                   \
          pCut2 = pCut? pCut->pNext: NULL )

Definition at line 78 of file mapperCut.c.

#define Map_ListForEachCutSafe( pList, pCut, pCut2 )      \
    for ( pCut = pList,                                   \
          pCut2 = pCut? pCut->pNext: NULL;                \
          pCut;                                           \
          pCut = pCut2,                                   \
          pCut2 = pCut? pCut->pNext: NULL )

Typedef Documentation

Map_CutTable_t

typedef struct Map_CutTableStrutct_t Map_CutTable_t

Definition at line 34 of file mapperCut.c.

Function Documentation

Map_CutMergeLists2()

Map_Cut_t * Map_CutMergeLists2	(	Map_Man_t *	p,
		Map_CutTable_t *	pTable,
		Map_Cut_t *	pList1,
		Map_Cut_t *	pList2,
		int	fComp1,
		int	fComp2 )

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

Synopsis [Merges two lists of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 522 of file mapperCut.c.

{
    Map_Node_t * ppNodes[6];
    Map_Cut_t * pListNew, ** ppListNew, * pLists[7] = { NULL };
    Map_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2;
    int nNodes, Counter, i;
 
    // prepare the manager for the cut computation
    Map_CutTableRestart( pTable );
    // go through the cut pairs
    Counter = 0;
    for ( pTemp1 = pList1; pTemp1; pTemp1 = pTemp1->pNext )
        for ( pTemp2 = pList2; pTemp2; pTemp2 = pTemp2->pNext )
        {
            // check if k-feasible cut exists
            nNodes = Map_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
            if ( nNodes == 0 )
                continue;
            // consider the cut for possible addition to the set of new cuts
            pCut = Map_CutTableConsider( p, pTable, ppNodes, nNodes );
            if ( pCut == NULL )
                continue;
            // add data to the cut
            pCut->pOne = Map_CutNotCond( pTemp1, fComp1 );
            pCut->pTwo = Map_CutNotCond( pTemp2, fComp2 );
            // add it to the corresponding list
            pCut->pNext = pLists[(int)pCut->nLeaves];
            pLists[(int)pCut->nLeaves] = pCut;
            // count this cut and quit if limit is reached
            Counter++;
            if ( Counter == MAP_CUTS_MAX_COMPUTE )
                goto QUITS;
        }
QUITS :
    // combine all the lists into one
    pListNew  = NULL;
    ppListNew = &pListNew;
    for ( i = 1; i <= p->nVarsMax; i++ )
    {
        if ( pLists[i] == NULL )
            continue;
        // find the last entry
        for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut; 
            pPrev = pCut, pCut = pCut->pNext );
        // connect these lists
        *ppListNew = pLists[i];
        ppListNew  = &pPrev->pNext;
    }
    *ppListNew = NULL;
    // soft the cuts by arrival times and use only the first MAP_CUTS_MAX_USE
    pListNew = Map_CutSortCuts( p, pTable, pListNew );
    return pListNew;
}

Map_CutSortCutsCompare()

int Map_CutSortCutsCompare	(	Map_Cut_t **	pC1,
		Map_Cut_t **	pC2 )

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

Synopsis [Compares the cuts by the number of leaves and then by delay.]

Description []

SideEffects []

SeeAlso []

Definition at line 980 of file mapperCut.c.

{
    if ( (*pC1)->nLeaves < (*pC2)->nLeaves )
        return -1;
    if ( (*pC1)->nLeaves > (*pC2)->nLeaves )
        return 1;
    return 0;
}

Map_MappingCountAllCuts()

int Map_MappingCountAllCuts

(

Map_Man_t *

pMan

)

FUNCTION DEFINITIONS ///.

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

Synopsis [Counts all the cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 100 of file mapperCut.c.

{
    Map_Node_t * pNode;
    Map_Cut_t * pCut;
    int i, nCuts;
//    int nCuts55 = 0, nCuts5x = 0, nCuts4x = 0, nCuts3x = 0;
//    int pCounts[7] = {0};
    nCuts = 0;
    for ( i = 0; i < pMan->nBins; i++ )
        for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
            for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
                if ( pCut->nLeaves > 1 ) // skip the elementary cuts
                {
                    nCuts++;
/*
                    if ( Map_CutRegular(pCut->pOne)->nLeaves == 5 && Map_CutRegular(pCut->pTwo)->nLeaves == 5 )
                        nCuts55++;
                    if ( Map_CutRegular(pCut->pOne)->nLeaves == 5 || Map_CutRegular(pCut->pTwo)->nLeaves == 5 )
                        nCuts5x++;
                    else if ( Map_CutRegular(pCut->pOne)->nLeaves == 4 || Map_CutRegular(pCut->pTwo)->nLeaves == 4 )
                        nCuts4x++;
                    else if ( Map_CutRegular(pCut->pOne)->nLeaves == 3 || Map_CutRegular(pCut->pTwo)->nLeaves == 3 )
                        nCuts3x++;
*/                  
//                    pCounts[ Map_CutRegular(pCut->pOne)->nLeaves ]++;
//                    pCounts[ Map_CutRegular(pCut->pTwo)->nLeaves ]++;
                }
//    printf( "Total cuts = %6d. 55 = %6d. 5x = %6d. 4x = %6d. 3x = %6d.\n", nCuts, nCuts55, nCuts5x, nCuts4x, nCuts3x );
 
//    printf( "Total cuts = %6d. 6= %6d. 5= %6d. 4= %6d. 3= %6d. 2= %6d. 1= %6d.\n", 
//        nCuts, pCounts[6], pCounts[5], pCounts[4], pCounts[3], pCounts[2], pCounts[1] );
    return nCuts;
}

Here is the caller graph for this function:

Map_MappingCuts()

void Map_MappingCuts

(

Map_Man_t *

p

)

GLOBAL VARIABLES ///.

FUNCTION DEFINITIONS ///

Definition at line 172 of file mapperCut.c.

{
    ProgressBar * pProgress;
    Map_CutTable_t * pTable;
    Map_Node_t * pNode;
    int nCuts, nNodes, i;
    abctime clk = Abc_Clock();
    // set the elementary cuts for the PI variables
    assert( p->nVarsMax > 1 && p->nVarsMax < 7 );
    for ( i = 0; i < p->nInputs; i++ )
        Map_MappingCutsInput( p, p->pInputs[i] );
 
    // compute the cuts for the internal nodes
    nNodes = p->vMapObjs->nSize;
    pProgress = Extra_ProgressBarStart( stdout, nNodes );
    pTable = Map_CutTableStart( p );
    for ( i = 0; i < nNodes; i++ )
    {
        pNode = p->vMapObjs->pArray[i];
        if ( Map_NodeIsBuf(pNode) )
            Map_MappingCutsInput( p, pNode );
        else if ( Map_NodeIsAnd(pNode) )
            Map_CutCompute( p, pTable, pNode );
        else continue;
        Extra_ProgressBarUpdate( pProgress, i, "Cuts ..." );
    }
    Extra_ProgressBarStop( pProgress );
    Map_CutTableStop( pTable );
 
    // report the stats
    if ( p->fVerbose )
    {
        nCuts = Map_MappingCountAllCuts(p);
        printf( "Nodes = %6d.  Total %d-feasible cuts = %10d.  Per node = %.1f. ", 
               p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes );
        ABC_PRT( "Time", Abc_Clock() - clk );
    }
 
    // print the cuts for the first primary output
//    Map_CutListPrint( p, Map_Regular(p->pOutputs[0]) );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Map_MappingCutsInput()

void Map_MappingCutsInput	(	Map_Man_t *	p,
		Map_Node_t *	pNode )

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

Synopsis [Computes the cuts for each node in the object graph.]

Description [The cuts are computed in one sweep over the mapping graph. First, the elementary cuts, which include the node itself, are assigned to the PI nodes. The internal nodes are considered in the DFS order. Each node is two-input AND-gate. So to compute the cuts at a node, we need to merge the sets of cuts of its two predecessors. The merged set contains only unique cuts with the number of inputs equal to k or less. Finally, the elementary cut, composed of the node itself, is added to the set of cuts for the node.

This procedure is pretty fast for 5-feasible cuts, but it dramatically slows down on some "dense" networks when computing 6-feasible cuts. The problem is that there are too many cuts in this case. We should think how to heuristically trim the number of cuts in such cases, to have reasonable runtime.]

SideEffects []

SeeAlso []

Definition at line 158 of file mapperCut.c.

{
    Map_Cut_t * pCut;
    assert( Map_NodeIsVar(pNode) || Map_NodeIsBuf(pNode) );
    pCut = Map_CutAlloc( p );
    pCut->nLeaves = 1;
    pCut->ppLeaves[0] = pNode;
    pNode->pCuts   = pCut;
    pNode->pCutBest[0] = NULL; // negative polarity is not mapped
    pNode->pCutBest[1] = pCut; // positive polarity is a trivial cut
    pCut->uTruth = 0xAAAAAAAA; // the first variable "1010"
    pCut->M[0].AreaFlow = 0.0;
    pCut->M[1].AreaFlow = 0.0;
}

Here is the call graph for this function:

Here is the caller graph for this function: