#include "fpgaInt.h"

Include dependency graph for fpgaCut.c:

Classes
struct	Fpga_CutTableStrutct_t

Macros
#define	FPGA_CUTS_MAX_COMPUTE 2000

#define	FPGA_CUTS_MAX_USE 1000

#define	FPGA_COUNT_ONES(u)

#define	Fpga_ListForEachCut(pList, pCut)

#define	Fpga_ListForEachCutSafe(pList, pCut, pCut2)

Typedefs
typedef typedefABC_NAMESPACE_IMPL_START struct Fpga_CutTableStrutct_t	Fpga_CutTable_t
	DECLARATIONS ///.

Functions
Fpga_Cut_t *	Fpga_CutAlloc (Fpga_Man_t *p)
	DECLARATIONS ///.

int	Fpga_CutCountAll (Fpga_Man_t *pMan)

void	Fpga_MappingCuts (Fpga_Man_t *p)
	FUNCTION DEFINITIONS ///.

void	Fpga_MappingCreatePiCuts (Fpga_Man_t *p)

Fpga_Cut_t *	Fpga_CutMergeLists2 (Fpga_Man_t p, Fpga_CutTable_t pTable, Fpga_Cut_t pList1, Fpga_Cut_t pList2, int fComp1, int fComp2, int fPivot1, int fPivot2)

void	Fpga_CutsCleanSign (Fpga_Man_t *pMan)

void	Fpga_CutsCleanRoot (Fpga_Man_t *pMan)

Macro Definition Documentation

◆ FPGA_COUNT_ONES

#define FPGA_COUNT_ONES ( u )

Value:

(bit_count[(u)&255]+bit_count[((u)>>8)&255]+bit_count[((u)>>16)&255]+bit_count[(u)>>24])

Definition at line 61 of file fpgaCut.c.

◆ FPGA_CUTS_MAX_COMPUTE

#define FPGA_CUTS_MAX_COMPUTE 2000

Definition at line 42 of file fpgaCut.c.

◆ FPGA_CUTS_MAX_USE

#define FPGA_CUTS_MAX_USE 1000

Definition at line 45 of file fpgaCut.c.

◆ Fpga_ListForEachCut

#define Fpga_ListForEachCut	(		pList,
			pCut )

Value:

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

Definition at line 90 of file fpgaCut.c.

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

◆ Fpga_ListForEachCutSafe

#define Fpga_ListForEachCutSafe	(	pList,
		pCut,
		pCut2 )

Value:

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

Definition at line 94 of file fpgaCut.c.

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

Typedef Documentation

◆ Fpga_CutTable_t

typedef typedefABC_NAMESPACE_IMPL_START struct Fpga_CutTableStrutct_t Fpga_CutTable_t

DECLARATIONS ///.

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

FileName [fpgaCut.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 - August 18, 2004.]

Revision [

Id: fpgaCut.c,v 1.3 2004/07/06 04:55:57 alanmi Exp

]

Definition at line 28 of file fpgaCut.c.

Function Documentation

◆ Fpga_CutAlloc()

Fpga_Cut_t * Fpga_CutAlloc ( Fpga_Man_t * p )

extern

DECLARATIONS ///.

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

FileName [fpgaCutUtils.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 - August 18, 2004.]

Revision [

Id: fpgaCutUtils.h,v 1.0 2003/09/08 00:00:00 alanmi Exp

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

Synopsis [Allocates the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 43 of file fpgaCutUtils.c.

{
    Fpga_Cut_t * pCut;
    pCut = (Fpga_Cut_t *)Extra_MmFixedEntryFetch( p->mmCuts );
    memset( pCut, 0, sizeof(Fpga_Cut_t) );
    return pCut;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Fpga_CutCountAll()

int Fpga_CutCountAll ( Fpga_Man_t * pMan )

extern

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

Synopsis [Counts all the cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 767 of file fpgaCut.c.

{
    Fpga_Node_t * pNode;
    Fpga_Cut_t * pCut;
    int i, nCuts;
    // go through all the nodes in the unique table of the manager
    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
                {
//                    Fpga_CutVolume( pCut );
                    nCuts++;
                }
    return nCuts;
}

Here is the caller graph for this function:

◆ Fpga_CutMergeLists2()

Fpga_Cut_t * Fpga_CutMergeLists2	(	Fpga_Man_t *	p,
		Fpga_CutTable_t *	pTable,
		Fpga_Cut_t *	pList1,
		Fpga_Cut_t *	pList2,
		int	fComp1,
		int	fComp2,
		int	fPivot1,
		int	fPivot2 )

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

Synopsis [Merges two lists of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 539 of file fpgaCut.c.

{
    Fpga_Node_t * ppNodes[FPGA_MAX_LEAVES];
    Fpga_Cut_t * pListNew, ** ppListNew, * pLists[FPGA_MAX_LEAVES+1] = { NULL };
    Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2;
    int nNodes, Counter, i;
 
    // prepare the manager for the cut computation
    Fpga_CutTableRestart( pTable );
    // go through the cut pairs
    Counter = 0;
    for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext )
        for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext )
        {
            // check if k-feasible cut exists
            nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
            if ( nNodes == 0 )
                continue;
            // consider the cut for possible addition to the set of new cuts
            pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
            if ( pCut == NULL )
                continue;
            // add data to the cut
            pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
            pCut->pTwo = Fpga_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 == FPGA_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;
    // sort the cuts by arrival times and use only the first FPGA_CUTS_MAX_USE
    pListNew = Fpga_CutSortCuts( p, pTable, pListNew );
    return pListNew;
}

◆ Fpga_CutsCleanRoot()

void Fpga_CutsCleanRoot ( Fpga_Man_t * pMan )

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

Synopsis [Clean the signatures.]

Description []

SideEffects []

SeeAlso []

Definition at line 819 of file fpgaCut.c.

{
    Fpga_Node_t * pNode;
    Fpga_Cut_t * pCut;
    int i;
    for ( i = 0; i < pMan->nBins; i++ )
        for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
            for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
                pCut->pRoot = NULL;
}

◆ Fpga_CutsCleanSign()

void Fpga_CutsCleanSign ( Fpga_Man_t * pMan )

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

Synopsis [Clean the signatures.]

Description []

SideEffects []

SeeAlso []

Definition at line 797 of file fpgaCut.c.

{
    Fpga_Node_t * pNode;
    Fpga_Cut_t * pCut;
    int i;
    for ( i = 0; i < pMan->nBins; i++ )
        for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
            for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
                pCut->uSign = 0;
}

◆ Fpga_MappingCreatePiCuts()

void Fpga_MappingCreatePiCuts ( Fpga_Man_t * p )

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

Synopsis [Performs technology mapping for variable-size-LUTs.]

Description []

SideEffects []

SeeAlso []

Definition at line 181 of file fpgaCut.c.

{
    Fpga_Cut_t * pCut;
    int i;
 
    // set the elementary cuts for the PI variables
    for ( i = 0; i < p->nInputs; i++ )
    {
        pCut = Fpga_CutAlloc( p );
        pCut->nLeaves = 1;
        pCut->ppLeaves[0] = p->pInputs[i];
        pCut->uSign = (1 << (i%31));
        p->pInputs[i]->pCuts   = pCut;
        p->pInputs[i]->pCutBest = pCut;
        // set the input arrival times
//        p->pInputs[i]->pCut[1]->tArrival = p->pInputArrivals[i];
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Fpga_MappingCuts()

void Fpga_MappingCuts ( Fpga_Man_t * p )

FUNCTION DEFINITIONS ///.

GLOBAL VARIABLES ///.

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 130 of file fpgaCut.c.

{
    ProgressBar * pProgress;
    Fpga_CutTable_t * pTable;
    Fpga_Node_t * pNode;
    int nCuts, nNodes, i;
    clock_t clk = clock();
 
    // set the elementary cuts for the PI variables
    assert( p->nVarsMax > 1 && p->nVarsMax < 11 );
    Fpga_MappingCreatePiCuts( p );
 
    // compute the cuts for the internal nodes
    nNodes = p->vAnds->nSize;
    pProgress = Extra_ProgressBarStart( stdout, nNodes );
    pTable = Fpga_CutTableStart( p );
    for ( i = 0; i < nNodes; i++ )
    {
        Extra_ProgressBarUpdate( pProgress, i, "Cuts ..." );
        pNode = p->vAnds->pArray[i];
        if ( !Fpga_NodeIsAnd( pNode ) )
            continue;
        Fpga_CutCompute( p, pTable, pNode );
    }
    Extra_ProgressBarStop( pProgress );
    Fpga_CutTableStop( pTable );
 
    // report the stats
    if ( p->fVerbose )
    {
        nCuts = Fpga_CutCountAll(p);
        printf( "Nodes = %6d. Total %d-cuts = %d. Cuts per node = %.1f. ", 
               p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes );
        ABC_PRT( "Time", clock() - clk );
    }
 
    // print the cuts for the first primary output
//    Fpga_CutListPrint( p, Fpga_Regular(p->pOutputs[0]) );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Classes

Macros

Typedefs

Functions

Macro Definition Documentation

◆ FPGA_COUNT_ONES

◆ FPGA_CUTS_MAX_COMPUTE

◆ FPGA_CUTS_MAX_USE

◆ Fpga_ListForEachCut

◆ Fpga_ListForEachCutSafe

Typedef Documentation

◆ Fpga_CutTable_t

Function Documentation

◆ Fpga_CutAlloc()

◆ Fpga_CutCountAll()

◆ Fpga_CutMergeLists2()

◆ Fpga_CutsCleanRoot()

◆ Fpga_CutsCleanSign()

◆ Fpga_MappingCreatePiCuts()

◆ Fpga_MappingCuts()