diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2005-07-29 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2005-07-29 08:01:00 -0700 |
commit | 888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc (patch) | |
tree | 11d48c9e9069f54dc300c3571ae63c744c802c50 /src/map/fpga/fpgaCut.c | |
parent | 7f94414388cce67bd3cc1a6d6269f0ed31ed0d06 (diff) | |
download | abc-888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc.tar.gz abc-888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc.tar.bz2 abc-888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc.zip |
Version abc50729
Diffstat (limited to 'src/map/fpga/fpgaCut.c')
-rw-r--r-- | src/map/fpga/fpgaCut.c | 1150 |
1 files changed, 1150 insertions, 0 deletions
diff --git a/src/map/fpga/fpgaCut.c b/src/map/fpga/fpgaCut.c new file mode 100644 index 00000000..27079953 --- /dev/null +++ b/src/map/fpga/fpgaCut.c @@ -0,0 +1,1150 @@ +/**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 $] + +***********************************************************************/ + +#include "fpgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Fpga_CutTableStrutct_t Fpga_CutTable_t; +struct Fpga_CutTableStrutct_t +{ + Fpga_Cut_t ** pBins; // the table used for linear probing + int nBins; // the size of the table + int * pCuts; // the array of cuts currently stored + int nCuts; // the number of cuts currently stored + Fpga_Cut_t ** pArray; // the temporary array of cuts + Fpga_Cut_t ** pCuts1; // the temporary array of cuts + Fpga_Cut_t ** pCuts2; // the temporary array of cuts +}; + +// the largest number of cuts considered +#define FPGA_CUTS_MAX_COMPUTE 500 +// the largest number of cuts used +#define FPGA_CUTS_MAX_USE 200 + +// primes used to compute the hash key +static int s_HashPrimes[10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 }; + +static int bit_count[256] = { + 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, + 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, + 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, + 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, + 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, + 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, + 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, + 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8 +}; + +#define FPGA_COUNT_ONES(u) (bit_count[(u)&255]+bit_count[((u)>>8)&255]+bit_count[((u)>>16)&255]+bit_count[(u)>>24]) + +static Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Node_t * pNode ); +static void Fpga_CutFilter( Fpga_Man_t * p, Fpga_Node_t * pNode ); +static Fpga_Cut_t * Fpga_CutMergeLists( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 ); +static int Fpga_CutMergeTwo( Fpga_Cut_t * pCut1, Fpga_Cut_t * pCut2, Fpga_Node_t * ppNodes[], int nNodesMax ); +static Fpga_Cut_t * Fpga_CutUnionLists( Fpga_Cut_t * pList1, Fpga_Cut_t * pList2 ); +static int Fpga_CutBelongsToList( Fpga_Cut_t * pList, Fpga_Node_t * ppNodes[], int nNodes ); +extern Fpga_Cut_t * Fpga_CutAlloc( Fpga_Man_t * p ); +extern int Fpga_CutCountAll( Fpga_Man_t * pMan ); + +static void Fpga_CutListPrint( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ); +static void Fpga_CutListPrint2( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ); +static void Fpga_CutPrint_( Fpga_Man_t * pMan, Fpga_Cut_t * pCut, Fpga_Node_t * pRoot ); + +static Fpga_CutTable_t * Fpga_CutTableStart( Fpga_Man_t * pMan ); +static void Fpga_CutTableStop( Fpga_CutTable_t * p ); +static unsigned Fpga_CutTableHash( Fpga_Node_t * ppNodes[], int nNodes ); +static int Fpga_CutTableLookup( Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ); +static Fpga_Cut_t * Fpga_CutTableConsider( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ); +static void Fpga_CutTableRestart( Fpga_CutTable_t * p ); + +static int Fpga_CutSortCutsCompare( Fpga_Cut_t ** pC1, Fpga_Cut_t ** pC2 ); +static Fpga_Cut_t * Fpga_CutSortCuts( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Cut_t * pList ); +static int Fpga_CutList2Array( Fpga_Cut_t ** pArray, Fpga_Cut_t * pList ); +static Fpga_Cut_t * Fpga_CutArray2List( Fpga_Cut_t ** pArray, int nCuts ); + + +// iterator through all the cuts of the list +#define Fpga_ListForEachCut( pList, pCut ) \ + for ( pCut = pList; \ + pCut; \ + pCut = pCut->pNext ) +#define Fpga_ListForEachCutSafe( pList, pCut, pCut2 ) \ + for ( pCut = pList, \ + pCut2 = pCut? pCut->pNext: NULL; \ + pCut; \ + pCut = pCut2, \ + pCut2 = pCut? pCut->pNext: NULL ) + + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**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 [] + +***********************************************************************/ +void Fpga_MappingCuts( Fpga_Man_t * p ) +{ + ProgressBar * pProgress; + Fpga_CutTable_t * pTable; + Fpga_Node_t * pNode; + int nCuts, nNodes, i; + + // set the elementary cuts for the PI variables + assert( p->nVarsMax > 1 && p->nVarsMax < 7 ); + 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-feasible cuts = %d. Cuts per node = %.1f.\n", + p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes ); + } + + // print the cuts for the first primary output +// Fpga_CutListPrint( p, Fpga_Regular(p->pOutputs[0]) ); +} + +/**Function************************************************************* + + Synopsis [Performs technology mapping for variable-size-LUTs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingCreatePiCuts( Fpga_Man_t * p ) +{ + 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]; + } +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Node_t * pNode ) +{ + Fpga_Node_t * pTemp; + Fpga_Cut_t * pList, * pList1, * pList2; + Fpga_Cut_t * pCut; + int fPivot1 = p->fTree && (Fpga_NodeReadRef(pNode->p1)>2); + int fPivot2 = p->fTree && (Fpga_NodeReadRef(pNode->p2)>2); + + // if the cuts are computed return them + if ( pNode->pCuts ) + return pNode->pCuts; + + // compute the cuts for the children + pList1 = Fpga_Regular(pNode->p1)->pCuts; + pList2 = Fpga_Regular(pNode->p2)->pCuts; + // merge the lists + pList = Fpga_CutMergeLists( p, pTable, pList1, pList2, + Fpga_IsComplement(pNode->p1), Fpga_IsComplement(pNode->p2), + fPivot1, fPivot2 ); + // if there are functionally equivalent nodes, union them with this list + assert( pList ); + // only add to the list of cuts if the node is a representative one + if ( pNode->pRepr == NULL ) + { + for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE ) + { + assert( pTemp->pCuts ); + pList = Fpga_CutUnionLists( pList, pTemp->pCuts ); + assert( pTemp->pCuts ); + pList = Fpga_CutSortCuts( p, pTable, pList ); + } + } + // add the new cut + pCut = Fpga_CutAlloc( p ); + pCut->nLeaves = 1; + pCut->ppLeaves[0] = pNode; + pCut->uSign = (1 << (pNode->Num%31)); + pCut->fLevel = (float)pCut->ppLeaves[0]->Level; + // append (it is important that the elementary cut is appended first) + pCut->pNext = pList; + // set at the node + pNode->pCuts = pCut; + // remove the dominated cuts + Fpga_CutFilter( p, pNode ); + // set the phase correctly + if ( pNode->pRepr && Fpga_NodeComparePhase(pNode, pNode->pRepr) ) + { + Fpga_ListForEachCut( pNode->pCuts, pCut ) + pCut->Phase = 1; + } + + +/* + { + Fpga_Cut_t * pPrev; + int i, Counter = 0; + for ( pCut = pNode->pCuts->pNext, pPrev = pNode->pCuts; pCut; pCut = pCut->pNext ) + { + for ( i = 0; i < pCut->nLeaves; i++ ) + if ( pCut->ppLeaves[i]->Level >= pNode->Level ) + break; + if ( i != pCut->nLeaves ) + pPrev->pNext = pCut->pNext; + else + pPrev = pCut; + } + } + { + int i, Counter = 0;; + for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) + for ( i = 0; i < pCut->nLeaves; i++ ) + Counter += (pCut->ppLeaves[i]->Level >= pNode->Level); + if ( Counter ) + printf( " %d", Counter ); + } +*/ + + return pCut; +} + +/**Function************************************************************* + + Synopsis [Filter the cuts using dominance.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutFilter( Fpga_Man_t * p, Fpga_Node_t * pNode ) +{ + Fpga_Cut_t * pTemp, * pPrev, * pCut, * pCut2; + int i, k, Counter; + + Counter = 0; + pPrev = pNode->pCuts; + Fpga_ListForEachCutSafe( pNode->pCuts->pNext, pCut, pCut2 ) + { + // go through all the previous cuts up to pCut + for ( pTemp = pNode->pCuts->pNext; pTemp != pCut; pTemp = pTemp->pNext ) + { + // check if every node in pTemp is contained in pCut + for ( i = 0; i < pTemp->nLeaves; i++ ) + { + for ( k = 0; k < pCut->nLeaves; k++ ) + if ( pTemp->ppLeaves[i] == pCut->ppLeaves[k] ) + break; + if ( k == pCut->nLeaves ) // node i in pTemp is not contained in pCut + break; + } + if ( i == pTemp->nLeaves ) // every node in pTemp is contained in pCut + { + Counter++; + break; + } + } + if ( pTemp != pCut ) // pTemp contain pCut + { + pPrev->pNext = pCut->pNext; // skip pCut + // recycle pCut + Fpga_CutFree( p, pCut ); + } + else + pPrev = pCut; + } +// printf( "Dominated = %3d. \n", Counter ); +} + + +/**Function************************************************************* + + Synopsis [Merges two lists of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutMergeLists( Fpga_Man_t * p, Fpga_CutTable_t * pTable, + Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 ) +{ + Fpga_Node_t * ppNodes[6]; + Fpga_Cut_t * pListNew, ** ppListNew, * pLists[7] = { NULL }; + Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2; + int nNodes, Counter, i; + Fpga_Cut_t ** ppArray1, ** ppArray2, ** ppArray3; + int nCuts1, nCuts2, nCuts3, k, fComp3; + + ppArray1 = pTable->pCuts1; + ppArray2 = pTable->pCuts2; + nCuts1 = Fpga_CutList2Array( ppArray1, pList1 ); + nCuts2 = Fpga_CutList2Array( ppArray2, pList2 ); + if ( fPivot1 ) + nCuts1 = 1; + if ( fPivot2 ) + nCuts2 = 1; + // swap the lists based on their length + if ( nCuts1 > nCuts2 ) + { + ppArray3 = ppArray1; + ppArray1 = ppArray2; + ppArray2 = ppArray3; + + nCuts3 = nCuts1; + nCuts1 = nCuts2; + nCuts2 = nCuts3; + + fComp3 = fComp1; + fComp1 = fComp2; + fComp2 = fComp3; + } + // pList1 is shorter or equal length compared to pList2 + + // 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 ) + for ( i = 0; i < nCuts1; i++ ) + { + for ( k = 0; k <= i; k++ ) + { + pTemp1 = ppArray1[i]; + pTemp2 = ppArray2[k]; + + if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax ) + { + if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] ) + continue; + if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] ) + continue; + } + + // 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 ); + // create the signature + pCut->uSign = pTemp1->uSign | pTemp2->uSign; + // add it to the corresponding list + pCut->pNext = pLists[pCut->nLeaves]; + pLists[pCut->nLeaves] = pCut; + // count this cut and quit if limit is reached + Counter++; + if ( Counter == FPGA_CUTS_MAX_COMPUTE ) + goto QUITS; + } + for ( k = 0; k < i; k++ ) + { + pTemp1 = ppArray1[k]; + pTemp2 = ppArray2[i]; + + if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax ) + { + if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] ) + continue; + if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] ) + continue; + } + + + // 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 ); + // create the signature + pCut->uSign = pTemp1->uSign | pTemp2->uSign; + // add it to the corresponding list + pCut->pNext = pLists[pCut->nLeaves]; + pLists[pCut->nLeaves] = pCut; + // count this cut and quit if limit is reached + Counter++; + if ( Counter == FPGA_CUTS_MAX_COMPUTE ) + goto QUITS; + } + } + // consider the rest of them + for ( i = nCuts1; i < nCuts2; i++ ) + for ( k = 0; k < nCuts1; k++ ) + { + pTemp1 = ppArray1[k]; + pTemp2 = ppArray2[i]; + + if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax ) + { + if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] ) + continue; + if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] ) + continue; + if ( pTemp1->ppLeaves[2] != pTemp2->ppLeaves[2] ) + continue; + } + + + // 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 ); + // create the signature + pCut->uSign = pTemp1->uSign | pTemp2->uSign; + // add it to the corresponding list + pCut->pNext = pLists[pCut->nLeaves]; + pLists[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; +} + + +/**Function************************************************************* + + Synopsis [Merges two lists of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +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 ) +{ + Fpga_Node_t * ppNodes[6]; + Fpga_Cut_t * pListNew, ** ppListNew, * pLists[7] = { 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[pCut->nLeaves]; + pLists[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; +} + +/**Function************************************************************* + + Synopsis [Merges two cuts.] + + Description [Returns the number of nodes in the resulting cut, or 0 if the + cut is infeasible. Returns the resulting nodes in the array ppNodes[].] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutMergeTwo( Fpga_Cut_t * pCut1, Fpga_Cut_t * pCut2, Fpga_Node_t * ppNodes[], int nNodesMax ) +{ + Fpga_Node_t * pNodeTemp; + int nTotal, i, k, min, Counter; + unsigned uSign; + + // use quick prefiltering + uSign = pCut1->uSign | pCut2->uSign; + Counter = FPGA_COUNT_ONES(uSign); + if ( Counter > nNodesMax ) + return 0; +/* + // check the special case when at least of the cuts is the largest + if ( pCut1->nLeaves == nNodesMax ) + { + if ( pCut2->nLeaves == nNodesMax ) + { + // return 0 if the cuts are different + for ( i = 0; i < nNodesMax; i++ ) + if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i] ) + return 0; + // return nNodesMax if they are the same + for ( i = 0; i < nNodesMax; i++ ) + ppNodes[i] = pCut1->ppLeaves[i]; + return nNodesMax; + } + else if ( pCut2->nLeaves == nNodesMax - 1 ) + { + // return 0 if the cuts are different + fMismatch = 0; + for ( i = 0; i < nNodesMax; i++ ) + if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i - fMismatch] ) + { + if ( fMismatch == 1 ) + return 0; + fMismatch = 1; + } + // return nNodesMax if they are the same + for ( i = 0; i < nNodesMax; i++ ) + ppNodes[i] = pCut1->ppLeaves[i]; + return nNodesMax; + } + } + else if ( pCut1->nLeaves == nNodesMax - 1 && pCut2->nLeaves == nNodesMax ) + { + // return 0 if the cuts are different + fMismatch = 0; + for ( i = 0; i < nNodesMax; i++ ) + if ( pCut1->ppLeaves[i - fMismatch] != pCut2->ppLeaves[i] ) + { + if ( fMismatch == 1 ) + return 0; + fMismatch = 1; + } + // return nNodesMax if they are the same + for ( i = 0; i < nNodesMax; i++ ) + ppNodes[i] = pCut2->ppLeaves[i]; + return nNodesMax; + } +*/ + // count the number of unique entries in pCut2 + nTotal = pCut1->nLeaves; + for ( i = 0; i < pCut2->nLeaves; i++ ) + { + // try to find this entry among the leaves of pCut1 + for ( k = 0; k < pCut1->nLeaves; k++ ) + if ( pCut2->ppLeaves[i] == pCut1->ppLeaves[k] ) + break; + if ( k < pCut1->nLeaves ) // found + continue; + // we found a new entry to add + if ( nTotal == nNodesMax ) + return 0; + ppNodes[nTotal++] = pCut2->ppLeaves[i]; + } + // we know that the feasible cut exists + + // add the starting entries + for ( k = 0; k < pCut1->nLeaves; k++ ) + ppNodes[k] = pCut1->ppLeaves[k]; + + // selection-sort the entries + for ( i = 0; i < nTotal - 1; i++ ) + { + min = i; + for ( k = i+1; k < nTotal; k++ ) + if ( ppNodes[k] < ppNodes[min] ) + min = k; + pNodeTemp = ppNodes[i]; + ppNodes[i] = ppNodes[min]; + ppNodes[min] = pNodeTemp; + } + + return nTotal; +} + +/**Function************************************************************* + + Synopsis [Computes the union of the two lists of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutUnionLists( Fpga_Cut_t * pList1, Fpga_Cut_t * pList2 ) +{ + Fpga_Cut_t * pTemp, * pRoot; + // find the last cut in the first list + pRoot = pList1; + Fpga_ListForEachCut( pList1, pTemp ) + pRoot = pTemp; + // attach the non-trival part of the second cut to the end of the first + assert( pRoot->pNext == NULL ); + pRoot->pNext = pList2->pNext; + pList2->pNext = NULL; + return pList1; +} + + +/**Function************************************************************* + + Synopsis [Checks whether the given cut belongs to the list.] + + Description [This procedure takes most of the runtime in the cut + computation.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutBelongsToList( Fpga_Cut_t * pList, Fpga_Node_t * ppNodes[], int nNodes ) +{ + Fpga_Cut_t * pTemp; + int i; + for ( pTemp = pList; pTemp; pTemp = pTemp->pNext ) + { + for ( i = 0; i < nNodes; i++ ) + if ( pTemp->ppLeaves[i] != ppNodes[i] ) + break; + if ( i == nNodes ) + return 1; + } + return 0; +} + +/**Function************************************************************* + + Synopsis [Counts all the cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutCountAll( Fpga_Man_t * pMan ) +{ + 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 + nCuts++; + return nCuts; +} + + +/**Function************************************************************* + + Synopsis [Clean the signatures.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutsCleanSign( Fpga_Man_t * pMan ) +{ + 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; +} + + + +/**Function************************************************************* + + Synopsis [Prints the cuts in the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutListPrint( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ) +{ + Fpga_Cut_t * pTemp; + int Counter; + for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ ) + { + printf( "%2d : ", Counter + 1 ); + Fpga_CutPrint_( pMan, pTemp, pRoot ); + } +} + +/**Function************************************************************* + + Synopsis [Prints the cuts in the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutListPrint2( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ) +{ + Fpga_Cut_t * pTemp; + int Counter; + for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ ) + { + printf( "%2d : ", Counter + 1 ); + Fpga_CutPrint_( pMan, pTemp, pRoot ); + } +} + +/**Function************************************************************* + + Synopsis [Prints the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutPrint_( Fpga_Man_t * pMan, Fpga_Cut_t * pCut, Fpga_Node_t * pRoot ) +{ + int i; + printf( "(%3d) {", pRoot->Num ); + for ( i = 0; i < pMan->nVarsMax; i++ ) + if ( pCut->ppLeaves[i] ) + printf( " %3d", pCut->ppLeaves[i]->Num ); + printf( " }\n" ); +} + + + + + + + + +/**Function************************************************************* + + Synopsis [Starts the hash table to canonicize cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_CutTable_t * Fpga_CutTableStart( Fpga_Man_t * pMan ) +{ + Fpga_CutTable_t * p; + // allocate the table + p = ALLOC( Fpga_CutTable_t, 1 ); + memset( p, 0, sizeof(Fpga_CutTable_t) ); + p->nBins = Cudd_Prime( 10 * FPGA_CUTS_MAX_COMPUTE ); + p->pBins = ALLOC( Fpga_Cut_t *, p->nBins ); + memset( p->pBins, 0, sizeof(Fpga_Cut_t *) * p->nBins ); + p->pCuts = ALLOC( int, 2 * FPGA_CUTS_MAX_COMPUTE ); + p->pArray = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE ); + p->pCuts1 = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE ); + p->pCuts2 = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE ); + return p; +} + +/**Function************************************************************* + + Synopsis [Stops the hash table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutTableStop( Fpga_CutTable_t * p ) +{ + free( p->pCuts1 ); + free( p->pCuts2 ); + free( p->pArray ); + free( p->pBins ); + free( p->pCuts ); + free( p ); +} + +/**Function************************************************************* + + Synopsis [Computes the hash value of the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Fpga_CutTableHash( Fpga_Node_t * ppNodes[], int nNodes ) +{ + unsigned uRes; + int i; + uRes = 0; + for ( i = 0; i < nNodes; i++ ) + uRes += s_HashPrimes[i] * ppNodes[i]->Num; + return uRes; +} + +/**Function************************************************************* + + Synopsis [Looks up the table for the available cut.] + + Description [Returns -1 if the same cut is found. Returns the index + of the cell where the cut should be added, if it does not exist.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutTableLookup( Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ) +{ + Fpga_Cut_t * pCut; + unsigned Key; + int b, i; + + Key = Fpga_CutTableHash(ppNodes, nNodes) % p->nBins; + for ( b = Key; p->pBins[b]; b = (b+1) % p->nBins ) + { + pCut = p->pBins[b]; + if ( pCut->nLeaves != nNodes ) + continue; + for ( i = 0; i < nNodes; i++ ) + if ( pCut->ppLeaves[i] != ppNodes[i] ) + break; + if ( i == nNodes ) + return -1; + } + return b; +} + + +/**Function************************************************************* + + Synopsis [Starts the hash table to canonicize cuts.] + + Description [Considers addition of the cut to the hash table.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutTableConsider( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ) +{ + Fpga_Cut_t * pCut; + int Place, i; + // check the cut + Place = Fpga_CutTableLookup( p, ppNodes, nNodes ); + if ( Place == -1 ) + return NULL; + assert( nNodes > 0 ); + // create the new cut + pCut = Fpga_CutAlloc( pMan ); + pCut->nLeaves = nNodes; + pCut->fLevel = 0.0; + for ( i = 0; i < nNodes; i++ ) + { + pCut->ppLeaves[i] = ppNodes[i]; + pCut->fLevel += ppNodes[i]->Level; + } + pCut->fLevel /= nNodes; + // add the cut to the table + assert( p->pBins[Place] == NULL ); + p->pBins[Place] = pCut; + // add the cut to the new list + p->pCuts[ p->nCuts++ ] = Place; + return pCut; +} + +/**Function************************************************************* + + Synopsis [Prepares the table to be used with other cuts.] + + Description [Restarts the table by cleaning the info about cuts stored + when the previous node was considered.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutTableRestart( Fpga_CutTable_t * p ) +{ + int i; + for ( i = 0; i < p->nCuts; i++ ) + { + assert( p->pBins[ p->pCuts[i] ] ); + p->pBins[ p->pCuts[i] ] = NULL; + } + p->nCuts = 0; +} + + + +/**Function************************************************************* + + Synopsis [Compares the cuts by the number of leaves and then by delay.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutSortCutsCompare( Fpga_Cut_t ** pC1, Fpga_Cut_t ** pC2 ) +{ + if ( (*pC1)->nLeaves < (*pC2)->nLeaves ) + return -1; + if ( (*pC1)->nLeaves > (*pC2)->nLeaves ) + return 1; +/* + if ( (*pC1)->fLevel > (*pC2)->fLevel ) + return -1; + if ( (*pC1)->fLevel < (*pC2)->fLevel ) + return 1; +*/ + return 0; +} + +/**Function************************************************************* + + Synopsis [Sorts the cuts by average arrival time.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutSortCuts( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Cut_t * pList ) +{ + Fpga_Cut_t * pListNew; + int nCuts, i; + // move the cuts from the list into the array + nCuts = Fpga_CutList2Array( p->pCuts1, pList ); + assert( nCuts <= FPGA_CUTS_MAX_COMPUTE ); + // sort the cuts + qsort( (void *)p->pCuts1, nCuts, sizeof(Fpga_Cut_t *), + (int (*)(const void *, const void *)) Fpga_CutSortCutsCompare ); + // move them back into the list + if ( nCuts > FPGA_CUTS_MAX_USE - 1 ) + { +// printf( "*" ); + // free the remaining cuts + for ( i = FPGA_CUTS_MAX_USE - 1; i < nCuts; i++ ) + Extra_MmFixedEntryRecycle( pMan->mmCuts, (char *)p->pCuts1[i] ); + // update the number of cuts + nCuts = FPGA_CUTS_MAX_USE - 1; + } + pListNew = Fpga_CutArray2List( p->pCuts1, nCuts ); + return pListNew; +} + +/**Function************************************************************* + + Synopsis [Moves the nodes from the list into the array.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutList2Array( Fpga_Cut_t ** pArray, Fpga_Cut_t * pList ) +{ + int i; + for ( i = 0; pList; pList = pList->pNext, i++ ) + pArray[i] = pList; + return i; +} + +/**Function************************************************************* + + Synopsis [Moves the nodes from the array into the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutArray2List( Fpga_Cut_t ** pArray, int nCuts ) +{ + Fpga_Cut_t * pListNew, ** ppListNew; + int i; + pListNew = NULL; + ppListNew = &pListNew; + for ( i = 0; i < nCuts; i++ ) + { + // connect these lists + *ppListNew = pArray[i]; + ppListNew = &pArray[i]->pNext; +//printf( " %d(%.2f)", pArray[i]->nLeaves, pArray[i]->fLevel ); + } +//printf( "\n" ); + + *ppListNew = NULL; + return pListNew; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + |