src/map/fpga/fpgaCut.c File Reference

#include "fpgaInt.h"
Include dependency graph for fpgaCut.c:

Go to the source code of this file.

Data Structures

struct  Fpga_CutTableStrutct_t

Defines

#define FPGA_CUTS_MAX_COMPUTE   2000
#define FPGA_CUTS_MAX_USE   1000
#define FPGA_COUNT_ONES(u)   (bit_count[(u)&255]+bit_count[((u)>>8)&255]+bit_count[((u)>>16)&255]+bit_count[(u)>>24])
#define Fpga_ListForEachCut(pList, pCut)
#define Fpga_ListForEachCutSafe(pList, pCut, pCut2)

Typedefs

typedef struct
Fpga_CutTableStrutct_t 		Fpga_CutTable_t

Functions

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)
Fpga_Cut_t * Fpga_CutAlloc (Fpga_Man_t *p)
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)
void Fpga_MappingCuts (Fpga_Man_t *p)
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)

Variables

static int s_HashPrimes [10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 }
static int bit_count [256]

Define Documentation

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

Definition at line 58 of file fpgaCut.c.

#define FPGA_CUTS_MAX_COMPUTE   2000

Definition at line 39 of file fpgaCut.c.

#define FPGA_CUTS_MAX_USE   1000

Definition at line 42 of file fpgaCut.c.

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

Definition at line 87 of file fpgaCut.c.

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

Typedef Documentation

typedef struct Fpga_CutTableStrutct_t Fpga_CutTable_t

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

] DECLARATIONS ///

Definition at line 25 of file fpgaCut.c.

Function Documentation

Fpga_Cut_t* Fpga_CutAlloc ( Fpga_Man_t *  p  ) 

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

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

Synopsis [Allocates the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 40 of file fpgaCutUtils.c.

00041 {
00042     Fpga_Cut_t * pCut;
00043     pCut = (Fpga_Cut_t *)Extra_MmFixedEntryFetch( p->mmCuts );
00044     memset( pCut, 0, sizeof(Fpga_Cut_t) );
00045     return pCut;
00046 }

Fpga_Cut_t * Fpga_CutArray2List ( Fpga_Cut_t **  pArray,
int  nCuts 
) [static]

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

Synopsis [Moves the nodes from the array into the list.]

Description []

SideEffects []

SeeAlso []

Definition at line 1136 of file fpgaCut.c.

01137 {
01138     Fpga_Cut_t * pListNew, ** ppListNew;
01139     int i;
01140     pListNew  = NULL;
01141     ppListNew = &pListNew;
01142     for ( i = 0; i < nCuts; i++ )
01143     {
01144         // connect these lists
01145         *ppListNew = pArray[i];
01146         ppListNew  = &pArray[i]->pNext;
01147 //printf( " %d(%.2f)", pArray[i]->nLeaves, pArray[i]->fLevel );
01148     }
01149 //printf( "\n" );
01150 
01151     *ppListNew = NULL;
01152     return pListNew;
01153 }

int Fpga_CutBelongsToList ( Fpga_Cut_t *  pList,
Fpga_Node_t *  ppNodes[],
int  nNodes 
) [static]

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 []

Definition at line 738 of file fpgaCut.c.

00739 {
00740     Fpga_Cut_t * pTemp;
00741     int i;
00742     for ( pTemp = pList; pTemp; pTemp = pTemp->pNext )
00743     {
00744         for ( i = 0; i < nNodes; i++ )
00745             if ( pTemp->ppLeaves[i] != ppNodes[i] )
00746                 break;
00747         if ( i == nNodes )
00748             return 1;
00749     }
00750     return 0;
00751 }

Fpga_Cut_t * Fpga_CutCompute ( Fpga_Man_t *  p,
Fpga_CutTable_t *  pTable,
Fpga_Node_t *  pNode 
) [static]

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

Synopsis [Computes the cuts for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 208 of file fpgaCut.c.

00209 {
00210     Fpga_Node_t * pTemp;
00211     Fpga_Cut_t * pList, * pList1, * pList2;
00212     Fpga_Cut_t * pCut;
00213     int fTree = 0;
00214     int fPivot1 = fTree && (Fpga_NodeReadRef(pNode->p1)>2);
00215     int fPivot2 = fTree && (Fpga_NodeReadRef(pNode->p2)>2);
00216 
00217     // if the cuts are computed return them
00218     if ( pNode->pCuts )
00219         return pNode->pCuts;
00220 
00221     // compute the cuts for the children
00222     pList1 = Fpga_Regular(pNode->p1)->pCuts;
00223     pList2 = Fpga_Regular(pNode->p2)->pCuts;
00224     // merge the lists
00225     pList = Fpga_CutMergeLists( p, pTable, pList1, pList2, 
00226         Fpga_IsComplement(pNode->p1), Fpga_IsComplement(pNode->p2),
00227         fPivot1, fPivot2 );
00228     // if there are functionally equivalent nodes, union them with this list
00229     assert( pList );
00230     // only add to the list of cuts if the node is a representative one
00231     if ( pNode->pRepr == NULL )
00232     {
00233         for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE )
00234         {
00235             assert( pTemp->pCuts );
00236             pList = Fpga_CutUnionLists( pList, pTemp->pCuts );
00237             assert( pTemp->pCuts );
00238             pList = Fpga_CutSortCuts( p, pTable, pList );
00239         }
00240     }
00241     // add the new cut
00242     pCut = Fpga_CutAlloc( p );
00243     pCut->nLeaves = 1;
00244     pCut->ppLeaves[0] = pNode;
00245     pCut->uSign = (1 << (pNode->Num%31));
00246     pCut->fLevel = (float)pCut->ppLeaves[0]->Level;
00247     // append (it is important that the elementary cut is appended first)
00248     pCut->pNext = pList;
00249     // set at the node
00250     pNode->pCuts = pCut;
00251     // remove the dominated cuts
00252 //    Fpga_CutFilter( p, pNode );
00253     // set the phase correctly
00254     if ( pNode->pRepr && Fpga_NodeComparePhase(pNode, pNode->pRepr) )
00255     {
00256         Fpga_ListForEachCut( pNode->pCuts, pCut )
00257             pCut->Phase = 1;
00258     }
00259 
00260 
00261 /*
00262     { 
00263         Fpga_Cut_t * pPrev;
00264         int i, Counter = 0;
00265         for ( pCut = pNode->pCuts->pNext, pPrev = pNode->pCuts; pCut; pCut = pCut->pNext )
00266         {
00267             for ( i = 0; i < pCut->nLeaves; i++ )
00268                 if ( pCut->ppLeaves[i]->Level >= pNode->Level )
00269                     break;
00270             if ( i != pCut->nLeaves )
00271                 pPrev->pNext = pCut->pNext;
00272             else 
00273                 pPrev = pCut; 
00274         }
00275     }
00276     { 
00277         int i, Counter = 0;;
00278         for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
00279             for ( i = 0; i < pCut->nLeaves; i++ )
00280                 Counter += (pCut->ppLeaves[i]->Level >= pNode->Level);
00281         if ( Counter )
00282             printf( " %d", Counter );
00283     }
00284 */
00285 
00286     return pCut;
00287 }

int Fpga_CutCountAll ( Fpga_Man_t *  pMan  ) 

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

Synopsis [Counts all the cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 764 of file fpgaCut.c.

00765 {
00766     Fpga_Node_t * pNode;
00767     Fpga_Cut_t * pCut;
00768     int i, nCuts;
00769     // go through all the nodes in the unique table of the manager
00770     nCuts = 0;
00771     for ( i = 0; i < pMan->nBins; i++ )
00772         for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
00773             for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
00774                 if ( pCut->nLeaves > 1 ) // skip the elementary cuts
00775                 {
00776 //                    Fpga_CutVolume( pCut );
00777                     nCuts++;
00778                 }
00779     return nCuts;
00780 }

void Fpga_CutFilter ( Fpga_Man_t *  p,
Fpga_Node_t *  pNode 
) [static]

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

Synopsis [Filter the cuts using dominance.]

Description []

SideEffects []

SeeAlso []

Definition at line 300 of file fpgaCut.c.

00301 { 
00302     Fpga_Cut_t * pTemp, * pPrev, * pCut, * pCut2;
00303     int i, k, Counter;
00304 
00305     Counter = 0;
00306     pPrev = pNode->pCuts;
00307     Fpga_ListForEachCutSafe( pNode->pCuts->pNext, pCut, pCut2 )
00308     {
00309         // go through all the previous cuts up to pCut
00310         for ( pTemp = pNode->pCuts->pNext; pTemp != pCut; pTemp = pTemp->pNext )
00311         {
00312             // check if every node in pTemp is contained in pCut
00313             for ( i = 0; i < pTemp->nLeaves; i++ )
00314             {
00315                 for ( k = 0; k < pCut->nLeaves; k++ )
00316                     if ( pTemp->ppLeaves[i] == pCut->ppLeaves[k] )
00317                         break;
00318                 if ( k == pCut->nLeaves ) // node i in pTemp is not contained in pCut
00319                     break;
00320             }
00321             if ( i == pTemp->nLeaves ) // every node in pTemp is contained in pCut
00322             {
00323                 Counter++;
00324                 break;
00325             }
00326         }
00327         if ( pTemp != pCut ) // pTemp contain pCut
00328         {
00329             pPrev->pNext = pCut->pNext;  // skip pCut
00330             // recycle pCut
00331             Fpga_CutFree( p, pCut );
00332         }
00333         else 
00334             pPrev = pCut; 
00335     }
00336 //  printf( "Dominated = %3d. \n", Counter );
00337 }

int Fpga_CutList2Array ( Fpga_Cut_t **  pArray,
Fpga_Cut_t *  pList 
) [static]

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

Synopsis [Moves the nodes from the list into the array.]

Description []

SideEffects []

SeeAlso []

Definition at line 1117 of file fpgaCut.c.

01118 {
01119     int i;
01120     for ( i = 0; pList; pList = pList->pNext, i++ )
01121         pArray[i] = pList;
01122     return i;
01123 }

void Fpga_CutListPrint ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pRoot 
) [static]

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

Synopsis [Prints the cuts in the list.]

Description []

SideEffects []

SeeAlso []

Definition at line 818 of file fpgaCut.c.

00819 {
00820     Fpga_Cut_t * pTemp;
00821     int Counter;
00822     for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ )
00823     {
00824         printf( "%2d : ", Counter + 1 );
00825         Fpga_CutPrint_( pMan, pTemp, pRoot );
00826     }
00827 }

void Fpga_CutListPrint2 ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pRoot 
) [static]

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

Synopsis [Prints the cuts in the list.]

Description []

SideEffects []

SeeAlso []

Definition at line 840 of file fpgaCut.c.

00841 {
00842     Fpga_Cut_t * pTemp;
00843     int Counter;
00844     for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ )
00845     {
00846         printf( "%2d : ", Counter + 1 );
00847         Fpga_CutPrint_( pMan, pTemp, pRoot );
00848     }
00849 }

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]

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

Synopsis [Merges two lists of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 351 of file fpgaCut.c.

00353 {
00354     Fpga_Node_t * ppNodes[FPGA_MAX_LEAVES];
00355     Fpga_Cut_t * pListNew, ** ppListNew, * pLists[FPGA_MAX_LEAVES+1] = { NULL };
00356     Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2;
00357     int nNodes, Counter, i;
00358     Fpga_Cut_t ** ppArray1, ** ppArray2, ** ppArray3;
00359     int nCuts1, nCuts2, nCuts3, k, fComp3;
00360 
00361     ppArray1 = pTable->pCuts1;
00362     ppArray2 = pTable->pCuts2;
00363     nCuts1 = Fpga_CutList2Array( ppArray1, pList1 );
00364     nCuts2 = Fpga_CutList2Array( ppArray2, pList2 );
00365     if ( fPivot1 )
00366         nCuts1 = 1;
00367     if ( fPivot2 )
00368         nCuts2 = 1;
00369     // swap the lists based on their length
00370     if ( nCuts1 > nCuts2 )
00371     {
00372          ppArray3 = ppArray1;
00373          ppArray1 = ppArray2;
00374          ppArray2 = ppArray3;
00375 
00376          nCuts3 = nCuts1;
00377          nCuts1 = nCuts2;
00378          nCuts2 = nCuts3;
00379 
00380          fComp3 = fComp1;
00381          fComp1 = fComp2;
00382          fComp2 = fComp3;
00383     }
00384     // pList1 is shorter or equal length compared to pList2
00385  
00386     // prepare the manager for the cut computation
00387     Fpga_CutTableRestart( pTable );
00388     // go through the cut pairs
00389     Counter = 0;
00390 //    for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext )
00391 //        for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext )
00392     for ( i = 0; i < nCuts1; i++ )
00393     {
00394         for ( k = 0; k <= i; k++ )
00395         {
00396             pTemp1 = ppArray1[i];
00397             pTemp2 = ppArray2[k];
00398 
00399             if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax )
00400             {
00401                 if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] )
00402                     continue;
00403                 if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] )
00404                     continue;
00405             }
00406 
00407             // check if k-feasible cut exists
00408             nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
00409             if ( nNodes == 0 )
00410                 continue;
00411             // consider the cut for possible addition to the set of new cuts
00412             pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
00413             if ( pCut == NULL )
00414                 continue;
00415             // add data to the cut
00416             pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
00417             pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
00418             // create the signature
00419             pCut->uSign = pTemp1->uSign | pTemp2->uSign;
00420             // add it to the corresponding list
00421             pCut->pNext = pLists[pCut->nLeaves];
00422             pLists[pCut->nLeaves] = pCut;
00423             // count this cut and quit if limit is reached
00424             Counter++;
00425             if ( Counter == FPGA_CUTS_MAX_COMPUTE )
00426                 goto QUITS;
00427         }
00428         for ( k = 0; k < i; k++ )
00429         {
00430             pTemp1 = ppArray1[k];
00431             pTemp2 = ppArray2[i];
00432 
00433             if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax )
00434             {
00435                 if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] )
00436                     continue;
00437                 if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] )
00438                     continue;
00439             }
00440 
00441 
00442             // check if k-feasible cut exists
00443             nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
00444             if ( nNodes == 0 )
00445                 continue;
00446             // consider the cut for possible addition to the set of new cuts
00447             pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
00448             if ( pCut == NULL )
00449                 continue;
00450             // add data to the cut
00451             pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
00452             pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
00453             // create the signature
00454             pCut->uSign = pTemp1->uSign | pTemp2->uSign;
00455             // add it to the corresponding list
00456             pCut->pNext = pLists[pCut->nLeaves];
00457             pLists[pCut->nLeaves] = pCut;
00458             // count this cut and quit if limit is reached
00459             Counter++;
00460             if ( Counter == FPGA_CUTS_MAX_COMPUTE )
00461                 goto QUITS;
00462         }
00463     }
00464     // consider the rest of them
00465     for ( i = nCuts1; i < nCuts2; i++ )
00466         for ( k = 0; k < nCuts1; k++ )
00467         {
00468             pTemp1 = ppArray1[k];
00469             pTemp2 = ppArray2[i];
00470 
00471             if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax )
00472             {
00473                 if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] )
00474                     continue;
00475                 if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] )
00476                     continue;
00477                 if ( pTemp1->ppLeaves[2] != pTemp2->ppLeaves[2] )
00478                     continue;
00479             }
00480 
00481 
00482             // check if k-feasible cut exists
00483             nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
00484             if ( nNodes == 0 )
00485                 continue;
00486             // consider the cut for possible addition to the set of new cuts
00487             pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
00488             if ( pCut == NULL )
00489                 continue;
00490             // add data to the cut
00491             pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
00492             pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
00493             // create the signature
00494             pCut->uSign = pTemp1->uSign | pTemp2->uSign;
00495             // add it to the corresponding list
00496             pCut->pNext = pLists[pCut->nLeaves];
00497             pLists[pCut->nLeaves] = pCut;
00498             // count this cut and quit if limit is reached
00499             Counter++;
00500             if ( Counter == FPGA_CUTS_MAX_COMPUTE )
00501                 goto QUITS;
00502         }
00503 QUITS :
00504     // combine all the lists into one
00505     pListNew  = NULL;
00506     ppListNew = &pListNew;
00507     for ( i = 1; i <= p->nVarsMax; i++ )
00508     {
00509         if ( pLists[i] == NULL )
00510             continue;
00511         // find the last entry
00512         for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut; 
00513             pPrev = pCut, pCut = pCut->pNext );
00514         // connect these lists
00515         *ppListNew = pLists[i];
00516         ppListNew  = &pPrev->pNext;
00517     }
00518     *ppListNew = NULL;
00519     // sort the cuts by arrival times and use only the first FPGA_CUTS_MAX_USE
00520     pListNew = Fpga_CutSortCuts( p, pTable, pListNew );
00521     return pListNew;
00522 }

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

00538 {
00539     Fpga_Node_t * ppNodes[FPGA_MAX_LEAVES];
00540     Fpga_Cut_t * pListNew, ** ppListNew, * pLists[FPGA_MAX_LEAVES+1] = { NULL };
00541     Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2;
00542     int nNodes, Counter, i;
00543 
00544     // prepare the manager for the cut computation
00545     Fpga_CutTableRestart( pTable );
00546     // go through the cut pairs
00547     Counter = 0;
00548     for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext )
00549         for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext )
00550         {
00551             // check if k-feasible cut exists
00552             nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
00553             if ( nNodes == 0 )
00554                 continue;
00555             // consider the cut for possible addition to the set of new cuts
00556             pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
00557             if ( pCut == NULL )
00558                 continue;
00559             // add data to the cut
00560             pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
00561             pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
00562             // add it to the corresponding list
00563             pCut->pNext = pLists[pCut->nLeaves];
00564             pLists[pCut->nLeaves] = pCut;
00565             // count this cut and quit if limit is reached
00566             Counter++;
00567             if ( Counter == FPGA_CUTS_MAX_COMPUTE )
00568                 goto QUITS;
00569         }
00570 QUITS :
00571     // combine all the lists into one
00572     pListNew  = NULL;
00573     ppListNew = &pListNew;
00574     for ( i = 1; i <= p->nVarsMax; i++ )
00575     {
00576         if ( pLists[i] == NULL )
00577             continue;
00578         // find the last entry
00579         for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut; 
00580             pPrev = pCut, pCut = pCut->pNext );
00581         // connect these lists
00582         *ppListNew = pLists[i];
00583         ppListNew  = &pPrev->pNext;
00584     }
00585     *ppListNew = NULL;
00586     // sort the cuts by arrival times and use only the first FPGA_CUTS_MAX_USE
00587     pListNew = Fpga_CutSortCuts( p, pTable, pListNew );
00588     return pListNew;
00589 }

int Fpga_CutMergeTwo ( Fpga_Cut_t *  pCut1,
Fpga_Cut_t *  pCut2,
Fpga_Node_t *  ppNodes[],
int  nNodesMax 
) [static]

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 []

Definition at line 603 of file fpgaCut.c.

00604 {
00605     Fpga_Node_t * pNodeTemp;
00606     int nTotal, i, k, min, Counter;
00607     unsigned uSign;
00608 
00609     // use quick prefiltering
00610     uSign = pCut1->uSign | pCut2->uSign;
00611     Counter = FPGA_COUNT_ONES(uSign);
00612     if ( Counter > nNodesMax )
00613         return 0;
00614 /*
00615     // check the special case when at least of the cuts is the largest
00616     if ( pCut1->nLeaves == nNodesMax )
00617     {
00618         if ( pCut2->nLeaves == nNodesMax )
00619         {
00620             // return 0 if the cuts are different
00621             for ( i = 0; i < nNodesMax; i++ )
00622                 if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i] )
00623                     return 0;
00624             // return nNodesMax if they are the same
00625             for ( i = 0; i < nNodesMax; i++ )
00626                 ppNodes[i] = pCut1->ppLeaves[i];
00627             return nNodesMax;
00628         }
00629         else if ( pCut2->nLeaves == nNodesMax - 1 ) 
00630         {
00631             // return 0 if the cuts are different
00632             fMismatch = 0;
00633             for ( i = 0; i < nNodesMax; i++ )
00634                 if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i - fMismatch] )
00635                 {
00636                     if ( fMismatch == 1 )
00637                         return 0;
00638                     fMismatch = 1;
00639                 }
00640             // return nNodesMax if they are the same
00641             for ( i = 0; i < nNodesMax; i++ )
00642                 ppNodes[i] = pCut1->ppLeaves[i];
00643             return nNodesMax;
00644         }
00645     }
00646     else if ( pCut1->nLeaves == nNodesMax - 1 && pCut2->nLeaves == nNodesMax )
00647     {
00648         // return 0 if the cuts are different
00649         fMismatch = 0;
00650         for ( i = 0; i < nNodesMax; i++ )
00651             if ( pCut1->ppLeaves[i - fMismatch] != pCut2->ppLeaves[i] )
00652             {
00653                 if ( fMismatch == 1 )
00654                     return 0;
00655                 fMismatch = 1;
00656             }
00657         // return nNodesMax if they are the same
00658         for ( i = 0; i < nNodesMax; i++ )
00659             ppNodes[i] = pCut2->ppLeaves[i];
00660         return nNodesMax;
00661     }
00662 */
00663     // count the number of unique entries in pCut2
00664     nTotal = pCut1->nLeaves;
00665     for ( i = 0; i < pCut2->nLeaves; i++ )
00666     {
00667         // try to find this entry among the leaves of pCut1
00668         for ( k = 0; k < pCut1->nLeaves; k++ )
00669             if ( pCut2->ppLeaves[i] == pCut1->ppLeaves[k] )
00670                 break;
00671         if ( k < pCut1->nLeaves ) // found
00672             continue;
00673         // we found a new entry to add
00674         if ( nTotal == nNodesMax )
00675             return 0;
00676         ppNodes[nTotal++] = pCut2->ppLeaves[i];
00677     }
00678     // we know that the feasible cut exists
00679 
00680     // add the starting entries
00681     for ( k = 0; k < pCut1->nLeaves; k++ )
00682         ppNodes[k] = pCut1->ppLeaves[k];
00683 
00684     // selection-sort the entries
00685     for ( i = 0; i < nTotal - 1; i++ )
00686     {
00687         min = i;
00688         for ( k = i+1; k < nTotal; k++ )
00689 //            if ( ppNodes[k] < ppNodes[min] ) // reported bug fix (non-determinism!)
00690             if ( ppNodes[k]->Num < ppNodes[min]->Num )
00691                 min = k;
00692         pNodeTemp    = ppNodes[i];
00693         ppNodes[i]   = ppNodes[min];
00694         ppNodes[min] = pNodeTemp;
00695     }
00696 
00697     return nTotal;
00698 }

void Fpga_CutPrint_ ( Fpga_Man_t *  pMan,
Fpga_Cut_t *  pCut,
Fpga_Node_t *  pRoot 
) [static]

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

Synopsis [Prints the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 862 of file fpgaCut.c.

00863 {
00864     int i;
00865     printf( "(%3d)  {", pRoot->Num );
00866     for ( i = 0; i < pMan->nVarsMax; i++ )
00867         if ( pCut->ppLeaves[i] )
00868             printf( " %3d", pCut->ppLeaves[i]->Num );
00869     printf( " }\n" );
00870 }

void Fpga_CutsCleanSign ( Fpga_Man_t *  pMan  ) 

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

Synopsis [Clean the signatures.]

Description []

SideEffects []

SeeAlso []

Definition at line 794 of file fpgaCut.c.

00795 {
00796     Fpga_Node_t * pNode;
00797     Fpga_Cut_t * pCut;
00798     int i;
00799     for ( i = 0; i < pMan->nBins; i++ )
00800         for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
00801             for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
00802                 pCut->uSign = 0;
00803 }

Fpga_Cut_t * Fpga_CutSortCuts ( Fpga_Man_t *  pMan,
Fpga_CutTable_t *  p,
Fpga_Cut_t *  pList 
) [static]

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

Synopsis [Sorts the cuts by average arrival time.]

Description []

SideEffects []

SeeAlso []

Definition at line 1082 of file fpgaCut.c.

01083 {
01084     Fpga_Cut_t * pListNew;
01085     int nCuts, i;
01086     // move the cuts from the list into the array
01087     nCuts = Fpga_CutList2Array( p->pCuts1, pList );
01088     assert( nCuts <= FPGA_CUTS_MAX_COMPUTE );
01089     // sort the cuts
01090     qsort( (void *)p->pCuts1, nCuts, sizeof(void *), 
01091             (int (*)(const void *, const void *)) Fpga_CutSortCutsCompare );
01092     // move them back into the list
01093     if ( nCuts > FPGA_CUTS_MAX_USE - 1 )
01094     {
01095 //        printf( "*" );
01096         // free the remaining cuts
01097         for ( i = FPGA_CUTS_MAX_USE - 1; i < nCuts; i++ )
01098             Extra_MmFixedEntryRecycle( pMan->mmCuts, (char *)p->pCuts1[i] );
01099         // update the number of cuts
01100         nCuts = FPGA_CUTS_MAX_USE - 1;
01101     }
01102     pListNew = Fpga_CutArray2List( p->pCuts1, nCuts );
01103     return pListNew;
01104 }

int Fpga_CutSortCutsCompare ( Fpga_Cut_t **  pC1,
Fpga_Cut_t **  pC2 
) [static]

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 1056 of file fpgaCut.c.

01057 {
01058     if ( (*pC1)->nLeaves < (*pC2)->nLeaves )
01059         return -1;
01060     if ( (*pC1)->nLeaves > (*pC2)->nLeaves )
01061         return 1;
01062 /*
01063     if ( (*pC1)->fLevel > (*pC2)->fLevel )
01064         return -1;
01065     if ( (*pC1)->fLevel < (*pC2)->fLevel )
01066         return 1;
01067 */
01068     return 0;
01069 }

Fpga_Cut_t * Fpga_CutTableConsider ( Fpga_Man_t *  pMan,
Fpga_CutTable_t *  p,
Fpga_Node_t *  ppNodes[],
int  nNodes 
) [static]

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

Synopsis [Starts the hash table to canonicize cuts.]

Description [Considers addition of the cut to the hash table.]

SideEffects []

SeeAlso []

Definition at line 993 of file fpgaCut.c.

00994 {
00995     Fpga_Cut_t * pCut;
00996     int Place, i;
00997     // check the cut
00998     Place = Fpga_CutTableLookup( p, ppNodes, nNodes );
00999     if ( Place == -1 )
01000         return NULL;
01001     assert( nNodes > 0 );
01002     // create the new cut
01003     pCut = Fpga_CutAlloc( pMan );
01004     pCut->nLeaves = nNodes;
01005     pCut->fLevel = 0.0;
01006     for ( i = 0; i < nNodes; i++ )
01007     {
01008         pCut->ppLeaves[i] = ppNodes[i];
01009         pCut->fLevel += ppNodes[i]->Level;
01010     }
01011     pCut->fLevel /= nNodes;
01012     // add the cut to the table
01013     assert( p->pBins[Place] == NULL );
01014     p->pBins[Place] = pCut;
01015     // add the cut to the new list
01016     p->pCuts[ p->nCuts++ ] = Place;
01017     return pCut;
01018 }

unsigned Fpga_CutTableHash ( Fpga_Node_t *  ppNodes[],
int  nNodes 
) [static]

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

Synopsis [Computes the hash value of the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 938 of file fpgaCut.c.

00939 {
00940     unsigned uRes;
00941     int i;
00942     uRes = 0;
00943     for ( i = 0; i < nNodes; i++ )
00944         uRes += s_HashPrimes[i] * ppNodes[i]->Num;
00945     return uRes;
00946 }

int Fpga_CutTableLookup ( Fpga_CutTable_t *  p,
Fpga_Node_t *  ppNodes[],
int  nNodes 
) [static]

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 []

Definition at line 960 of file fpgaCut.c.

00961 {
00962     Fpga_Cut_t * pCut;
00963     unsigned Key;
00964     int b, i;
00965 
00966     Key = Fpga_CutTableHash(ppNodes, nNodes) % p->nBins; 
00967     for ( b = Key; p->pBins[b]; b = (b+1) % p->nBins )
00968     {
00969         pCut = p->pBins[b];
00970         if ( pCut->nLeaves != nNodes )
00971             continue;
00972         for ( i = 0; i < nNodes; i++ )
00973             if ( pCut->ppLeaves[i] != ppNodes[i] )
00974                 break;
00975         if ( i == nNodes )
00976             return -1;
00977     }
00978     return b;
00979 }

void Fpga_CutTableRestart ( Fpga_CutTable_t *  p  )  [static]

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 []

Definition at line 1032 of file fpgaCut.c.

01033 {
01034     int i;
01035     for ( i = 0; i < p->nCuts; i++ )
01036     {
01037         assert( p->pBins[ p->pCuts[i] ] );
01038         p->pBins[ p->pCuts[i] ] = NULL;
01039     }
01040     p->nCuts = 0;
01041 }

Fpga_CutTable_t * Fpga_CutTableStart ( Fpga_Man_t *  pMan  )  [static]

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

Synopsis [Starts the hash table to canonicize cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 890 of file fpgaCut.c.

00891 {
00892     Fpga_CutTable_t * p;
00893     // allocate the table
00894     p = ALLOC( Fpga_CutTable_t, 1 );
00895     memset( p, 0, sizeof(Fpga_CutTable_t) );
00896     p->nBins = Cudd_Prime( 10 * FPGA_CUTS_MAX_COMPUTE );
00897     p->pBins = ALLOC( Fpga_Cut_t *, p->nBins );
00898     memset( p->pBins, 0, sizeof(Fpga_Cut_t *) * p->nBins );
00899     p->pCuts = ALLOC( int, 2 * FPGA_CUTS_MAX_COMPUTE );
00900     p->pArray = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE );
00901     p->pCuts1 = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE );
00902     p->pCuts2 = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE );
00903     return p;
00904 }

void Fpga_CutTableStop ( Fpga_CutTable_t *  p  )  [static]

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

Synopsis [Stops the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 917 of file fpgaCut.c.

00918 {
00919     free( p->pCuts1 );
00920     free( p->pCuts2 );
00921     free( p->pArray );
00922     free( p->pBins );
00923     free( p->pCuts );
00924     free( p );
00925 }

Fpga_Cut_t * Fpga_CutUnionLists ( Fpga_Cut_t *  pList1,
Fpga_Cut_t *  pList2 
) [static]

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

Synopsis [Computes the union of the two lists of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 711 of file fpgaCut.c.

00712 {
00713     Fpga_Cut_t * pTemp, * pRoot;
00714     // find the last cut in the first list
00715     pRoot = pList1;
00716     Fpga_ListForEachCut( pList1, pTemp )
00717         pRoot = pTemp;
00718     // attach the non-trival part of the second cut to the end of the first
00719     assert( pRoot->pNext == NULL );
00720     pRoot->pNext = pList2->pNext;   
00721     pList2->pNext = NULL;
00722     return pList1;
00723 }

void Fpga_MappingCreatePiCuts ( Fpga_Man_t *  p  ) 

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 178 of file fpgaCut.c.

00179 {
00180     Fpga_Cut_t * pCut;
00181     int i;
00182 
00183     // set the elementary cuts for the PI variables
00184     for ( i = 0; i < p->nInputs; i++ )
00185     {
00186         pCut = Fpga_CutAlloc( p );
00187         pCut->nLeaves = 1;
00188         pCut->ppLeaves[0] = p->pInputs[i];
00189         pCut->uSign = (1 << (i%31));
00190         p->pInputs[i]->pCuts   = pCut;
00191         p->pInputs[i]->pCutBest = pCut;
00192         // set the input arrival times
00193 //        p->pInputs[i]->pCut[1]->tArrival = p->pInputArrivals[i];
00194     }
00195 }

void Fpga_MappingCuts ( Fpga_Man_t *  p  ) 

FUNCTION DEFINITIONS ///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 127 of file fpgaCut.c.

00128 {
00129     ProgressBar * pProgress;
00130     Fpga_CutTable_t * pTable;
00131     Fpga_Node_t * pNode;
00132     int nCuts, nNodes, i;
00133     int clk = clock();
00134 
00135     // set the elementary cuts for the PI variables
00136     assert( p->nVarsMax > 1 && p->nVarsMax < 11 );
00137     Fpga_MappingCreatePiCuts( p );
00138 
00139     // compute the cuts for the internal nodes
00140     nNodes = p->vAnds->nSize;
00141     pProgress = Extra_ProgressBarStart( stdout, nNodes );
00142     pTable = Fpga_CutTableStart( p );
00143     for ( i = 0; i < nNodes; i++ )
00144     {
00145         Extra_ProgressBarUpdate( pProgress, i, "Cuts ..." );
00146         pNode = p->vAnds->pArray[i];
00147         if ( !Fpga_NodeIsAnd( pNode ) )
00148             continue;
00149         Fpga_CutCompute( p, pTable, pNode );
00150     }
00151     Extra_ProgressBarStop( pProgress );
00152     Fpga_CutTableStop( pTable );
00153 
00154     // report the stats
00155     if ( p->fVerbose )
00156     {
00157         nCuts = Fpga_CutCountAll(p);
00158         printf( "Nodes = %6d. Total %d-cuts = %d. Cuts per node = %.1f. ", 
00159                p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes );
00160         PRT( "Time", clock() - clk );
00161     }
00162 
00163     // print the cuts for the first primary output
00164 //    Fpga_CutListPrint( p, Fpga_Regular(p->pOutputs[0]) );
00165 }

Variable Documentation

int bit_count[256] [static]
Initial value:
 {
  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
}

Definition at line 47 of file fpgaCut.c.

int s_HashPrimes[10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 } [static]

Definition at line 45 of file fpgaCut.c.

Generated on Tue Jan 5 12:19:02 2010 for abc70930 by  doxygen 1.6.1