src/map/fpga/fpgaUtils.c File Reference

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

Go to the source code of this file.

Defines

#define FPGA_CO_LIST_SIZE   5

Functions

static void Fpga_MappingDfs_rec (Fpga_Node_t *pNode, Fpga_NodeVec_t *vNodes, int fCollectEquiv)
static void Fpga_MappingDfsCuts_rec (Fpga_Node_t *pNode, Fpga_NodeVec_t *vNodes)
static int Fpga_MappingCompareOutputDelay (Fpga_Node_t **ppNode1, Fpga_Node_t **ppNode2)
static void Fpga_MappingFindLatest (Fpga_Man_t *p, int *pNodes, int nNodesMax)
static void Fpga_DfsLim_rec (Fpga_Node_t *pNode, int Level, Fpga_NodeVec_t *vNodes)
static int Fpga_CollectNodeTfo_rec (Fpga_Node_t *pNode, Fpga_Node_t *pPivot, Fpga_NodeVec_t *vVisited, Fpga_NodeVec_t *vTfo)
static Fpga_NodeVec_t * Fpga_MappingOrderCosByLevel (Fpga_Man_t *pMan)
Fpga_NodeVec_t * Fpga_MappingDfs (Fpga_Man_t *pMan, int fCollectEquiv)
Fpga_NodeVec_t * Fpga_MappingDfsNodes (Fpga_Man_t *pMan, Fpga_Node_t **ppNodes, int nNodes, int fEquiv)
float Fpga_MappingGetAreaFlow (Fpga_Man_t *p)
float Fpga_MappingArea (Fpga_Man_t *pMan)
float Fpga_MappingArea_rec (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_NodeVec_t *vNodes)
float Fpga_MappingAreaTrav (Fpga_Man_t *pMan)
float Fpga_MappingSetRefsAndArea_rec (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Node_t **ppStore)
float Fpga_MappingSetRefsAndArea (Fpga_Man_t *pMan)
void Fpga_MappingPrintOutputArrivals (Fpga_Man_t *p)
void Fpga_MappingSetupTruthTables (unsigned uTruths[][2])
void Fpga_MappingSetupMask (unsigned uMask[], int nVarsMax)
int Fpga_ManCheckConsistency (Fpga_Man_t *p)
int Fpga_CompareNodesByLevelDecreasing (Fpga_Node_t **ppS1, Fpga_Node_t **ppS2)
int Fpga_CompareNodesByLevelIncreasing (Fpga_Node_t **ppS1, Fpga_Node_t **ppS2)
void Fpga_MappingSortByLevel (Fpga_Man_t *pMan, Fpga_NodeVec_t *vNodes, int fIncreasing)
Fpga_NodeVec_t * Fpga_DfsLim (Fpga_Man_t *pMan, Fpga_Node_t *pNode, int nLevels)
void Fpga_ManCleanData0 (Fpga_Man_t *pMan)
Fpga_NodeVec_t * Fpga_CollectNodeTfo (Fpga_Man_t *pMan, Fpga_Node_t *pNode)
Fpga_NodeVec_t * Fpga_MappingLevelize (Fpga_Man_t *pMan, Fpga_NodeVec_t *vNodes)
int Fpga_MappingMaxLevel (Fpga_Man_t *pMan)
int Fpga_MappingUpdateLevel_rec (Fpga_Man_t *pMan, Fpga_Node_t *pNode, int fMaximum)
void Fpga_MappingSetChoiceLevels (Fpga_Man_t *pMan)
void Fpga_ManReportChoices (Fpga_Man_t *pMan)

Variables

static Fpga_Man_t * s_pMan = NULL

Define Documentation

#define FPGA_CO_LIST_SIZE   5

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

FileName [fpgaUtils.c]

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

Synopsis [Technology mapping for variable-size-LUT FPGAs.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 2.0. Started - August 18, 2004.]

Revision [

Id
fpgaUtils.c,v 1.3 2004/07/06 04:55:58 alanmi Exp

] DECLARATIONS ///

Definition at line 25 of file fpgaUtils.c.

Function Documentation

Fpga_NodeVec_t* Fpga_CollectNodeTfo ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pNode 
)

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

Synopsis [Collects the TFO of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 673 of file fpgaUtils.c.

00674 {
00675     Fpga_NodeVec_t * vVisited, * vTfo;
00676     int i;
00677     // perform the traversal
00678     vVisited = Fpga_NodeVecAlloc( 100 );
00679     vTfo     = Fpga_NodeVecAlloc( 100 );
00680     for ( i = 0; i < pMan->nOutputs; i++ )
00681         Fpga_CollectNodeTfo_rec( Fpga_Regular(pMan->pOutputs[i]), pNode, vVisited, vTfo );
00682     for ( i = 0; i < vVisited->nSize; i++ )
00683         vVisited->pArray[i]->fMark0 = vVisited->pArray[i]->fMark1 = 0;
00684     Fpga_NodeVecFree( vVisited );
00685     return vTfo;
00686 }

int Fpga_CollectNodeTfo_rec ( Fpga_Node_t *  pNode,
Fpga_Node_t *  pPivot,
Fpga_NodeVec_t *  vVisited,
Fpga_NodeVec_t *  vTfo 
) [static]

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

Synopsis [Collects the TFO of the node.]

Description [Returns 1 if the node should be collected.]

SideEffects []

SeeAlso []

Definition at line 699 of file fpgaUtils.c.

00700 {
00701     int Ret1, Ret2;
00702     assert( !Fpga_IsComplement(pNode) );
00703     // skip visited nodes
00704     if ( pNode->fMark0 )
00705         return pNode->fMark1;
00706     pNode->fMark0 = 1;
00707     Fpga_NodeVecPush( vVisited, pNode );
00708 
00709     // return the pivot node
00710     if ( pNode == pPivot )
00711     {
00712         pNode->fMark1 = 1;
00713         return 1;
00714     }
00715     if ( pNode->Level < pPivot->Level )
00716     {
00717         pNode->fMark1 = 0;
00718         return 0;
00719     }
00720     // visit the transitive fanin
00721     assert( Fpga_NodeIsAnd(pNode) );
00722     Ret1 = Fpga_CollectNodeTfo_rec( Fpga_Regular(pNode->p1), pPivot, vVisited, vTfo );
00723     Ret2 = Fpga_CollectNodeTfo_rec( Fpga_Regular(pNode->p2), pPivot, vVisited, vTfo );
00724     if ( Ret1 || Ret2 )
00725     {
00726         pNode->fMark1 = 1;
00727         Fpga_NodeVecPush( vTfo, pNode );
00728     }
00729     else
00730         pNode->fMark1 = 0;
00731     return pNode->fMark1;
00732 }

int Fpga_CompareNodesByLevelDecreasing ( Fpga_Node_t **  ppS1,
Fpga_Node_t **  ppS2 
)

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

Synopsis [Compares the supergates by their level.]

Description []

SideEffects []

SeeAlso []

Definition at line 542 of file fpgaUtils.c.

00543 {
00544     if ( Fpga_Regular(*ppS1)->Level > Fpga_Regular(*ppS2)->Level )
00545         return -1;
00546     if ( Fpga_Regular(*ppS1)->Level < Fpga_Regular(*ppS2)->Level )
00547         return 1;
00548     return 0;
00549 }

int Fpga_CompareNodesByLevelIncreasing ( Fpga_Node_t **  ppS1,
Fpga_Node_t **  ppS2 
)

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

Synopsis [Compares the supergates by their level.]

Description []

SideEffects []

SeeAlso []

Definition at line 562 of file fpgaUtils.c.

00563 {
00564     if ( Fpga_Regular(*ppS1)->Level < Fpga_Regular(*ppS2)->Level )
00565         return -1;
00566     if ( Fpga_Regular(*ppS1)->Level > Fpga_Regular(*ppS2)->Level )
00567         return 1;
00568     return 0;
00569 }

Fpga_NodeVec_t* Fpga_DfsLim ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pNode,
int  nLevels 
)

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

Synopsis [Computes the limited DFS ordering for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 604 of file fpgaUtils.c.

00605 {
00606     Fpga_NodeVec_t * vNodes;
00607     int i;
00608     // perform the traversal
00609     vNodes = Fpga_NodeVecAlloc( 100 );
00610     Fpga_DfsLim_rec( pNode, nLevels, vNodes );
00611     for ( i = 0; i < vNodes->nSize; i++ )
00612         vNodes->pArray[i]->fMark0 = 0;
00613     return vNodes;
00614 }

void Fpga_DfsLim_rec ( Fpga_Node_t *  pNode,
int  Level,
Fpga_NodeVec_t *  vNodes 
) [static]

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

Synopsis [Recursively computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 627 of file fpgaUtils.c.

00628 {
00629     assert( !Fpga_IsComplement(pNode) );
00630     if ( pNode->fMark0 )
00631         return;
00632     pNode->fMark0 = 1;
00633     // visit the transitive fanin
00634     Level--;
00635     if ( Level > 0 && Fpga_NodeIsAnd(pNode) )
00636     {
00637         Fpga_DfsLim_rec( Fpga_Regular(pNode->p1), Level, vNodes );
00638         Fpga_DfsLim_rec( Fpga_Regular(pNode->p2), Level, vNodes );
00639     }
00640     // add the node to the list
00641     Fpga_NodeVecPush( vNodes, pNode );
00642 }

int Fpga_ManCheckConsistency ( Fpga_Man_t *  p  ) 

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

Synopsis [Verify one useful property.]

Description [This procedure verifies one useful property. After the FRAIG construction with choice nodes is over, each primary node should have fanins that are primary nodes. The primary nodes is the one that does not have pNode->pRepr set to point to another node.]

SideEffects []

SeeAlso []

Definition at line 498 of file fpgaUtils.c.

00499 {
00500     Fpga_Node_t * pNode;
00501     Fpga_NodeVec_t * pVec;
00502     int i;
00503     pVec = Fpga_MappingDfs( p, 0 );
00504     for ( i = 0; i < pVec->nSize; i++ )
00505     {
00506         pNode = pVec->pArray[i];
00507         if ( Fpga_NodeIsVar(pNode) )
00508         {
00509             if ( pNode->pRepr )
00510                 printf( "Primary input %d is a secondary node.\n", pNode->Num );
00511         }
00512         else if ( Fpga_NodeIsConst(pNode) )
00513         {
00514             if ( pNode->pRepr )
00515                 printf( "Constant 1 %d is a secondary node.\n", pNode->Num );
00516         }
00517         else
00518         {
00519             if ( pNode->pRepr )
00520                 printf( "Internal node %d is a secondary node.\n", pNode->Num );
00521             if ( Fpga_Regular(pNode->p1)->pRepr )
00522                 printf( "Internal node %d has first fanin that is a secondary node.\n", pNode->Num );
00523             if ( Fpga_Regular(pNode->p2)->pRepr )
00524                 printf( "Internal node %d has second fanin that is a secondary node.\n", pNode->Num );
00525         }
00526     }
00527     Fpga_NodeVecFree( pVec );
00528     return 1;
00529 }

void Fpga_ManCleanData0 ( Fpga_Man_t *  pMan  ) 

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

Synopsis [Computes the limited DFS ordering for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 655 of file fpgaUtils.c.

00656 {
00657     int i;
00658     for ( i = 0; i < pMan->vNodesAll->nSize; i++ )
00659         pMan->vNodesAll->pArray[i]->pData0 = 0;
00660 }

void Fpga_ManReportChoices ( Fpga_Man_t *  pMan  ) 

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

Synopsis [Reports statistics on choice nodes.]

Description [The number of choice nodes is the number of primary nodes, which has pNextE set to a pointer. The number of choices is the number of entries in the equivalent-node lists of the primary nodes.]

SideEffects []

SeeAlso []

Definition at line 895 of file fpgaUtils.c.

00896 {
00897     Fpga_Node_t * pNode, * pTemp;
00898     int nChoiceNodes, nChoices;
00899     int i, LevelMax1, LevelMax2;
00900 
00901     // report the number of levels
00902     LevelMax1 = Fpga_MappingMaxLevel( pMan );
00903     pMan->nTravIds++;
00904     for ( i = 0; i < pMan->nOutputs; i++ )
00905         Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 0 );
00906     LevelMax2 = Fpga_MappingMaxLevel( pMan );
00907 
00908     // report statistics about choices
00909     nChoiceNodes = nChoices = 0;
00910     for ( i = 0; i < pMan->vAnds->nSize; i++ )
00911     {
00912         pNode = pMan->vAnds->pArray[i];
00913         if ( pNode->pRepr == NULL && pNode->pNextE != NULL )
00914         { // this is a choice node = the primary node that has equivalent nodes
00915             nChoiceNodes++;
00916             for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE )
00917                 nChoices++;
00918         }
00919     }
00920     if ( pMan->fVerbose )
00921     {
00922     printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 );
00923     printf( "Choice stats:  Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices );
00924     }
00925 /*
00926     {
00927         FILE * pTable;
00928         pTable = fopen( "stats_choice.txt", "a+" );
00929         fprintf( pTable, "%s ", pMan->pFileName );
00930         fprintf( pTable, "%4d ", LevelMax1 );
00931         fprintf( pTable, "%4d ", pMan->vAnds->nSize - pMan->nInputs );
00932         fprintf( pTable, "%4d ", LevelMax2 );
00933         fprintf( pTable, "%7d ", nChoiceNodes );
00934         fprintf( pTable, "%7d ", nChoices + nChoiceNodes );
00935         fprintf( pTable, "\n" );
00936         fclose( pTable );
00937     }
00938 */
00939 }

float Fpga_MappingArea ( Fpga_Man_t *  pMan  ) 

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

Synopsis [Computes the area of the current mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 175 of file fpgaUtils.c.

00176 {
00177     Fpga_Node_t * pNode;
00178     float aTotal;
00179     int i;
00180     // perform the traversal
00181     aTotal = 0;
00182     for ( i = 0; i < pMan->vMapping->nSize; i++ )
00183     {
00184         pNode = pMan->vMapping->pArray[i];
00185         aTotal += pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves];
00186     }
00187     return aTotal;
00188 }

float Fpga_MappingArea_rec ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pNode,
Fpga_NodeVec_t *  vNodes 
)

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

Synopsis [Recursively computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 201 of file fpgaUtils.c.

00202 {
00203     float aArea;
00204     int i;
00205     assert( !Fpga_IsComplement(pNode) );
00206     if ( !Fpga_NodeIsAnd(pNode) )
00207         return 0;
00208     if ( pNode->fMark0 )
00209         return 0;
00210     assert( pNode->pCutBest != NULL );
00211     // visit the transitive fanin of the selected cut
00212     aArea = 0;
00213     for ( i = 0; i < pNode->pCutBest->nLeaves; i++ )
00214         aArea += Fpga_MappingArea_rec( pMan, pNode->pCutBest->ppLeaves[i], vNodes );
00215     // make sure the node is not visited through the fanin nodes
00216     assert( pNode->fMark0 == 0 );
00217     // mark the node as visited
00218     pNode->fMark0 = 1;
00219     // add the node to the list
00220     aArea += pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves];
00221     // add the node to the list
00222     Fpga_NodeVecPush( vNodes, pNode );
00223     return aArea;
00224 }

float Fpga_MappingAreaTrav ( Fpga_Man_t *  pMan  ) 

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

Synopsis [Computes the area of the current mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 237 of file fpgaUtils.c.

00238 {
00239     Fpga_NodeVec_t * vNodes;
00240     float aTotal;
00241     int i;
00242     // perform the traversal
00243     aTotal = 0;
00244     vNodes = Fpga_NodeVecAlloc( 100 );
00245     for ( i = 0; i < pMan->nOutputs; i++ )
00246         aTotal += Fpga_MappingArea_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), vNodes );
00247     for ( i = 0; i < vNodes->nSize; i++ )
00248         vNodes->pArray[i]->fMark0 = 0;
00249     Fpga_NodeVecFree( vNodes );
00250     return aTotal;
00251 }

int Fpga_MappingCompareOutputDelay ( Fpga_Node_t **  ppNode1,
Fpga_Node_t **  ppNode2 
) [static]

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

Synopsis [Compares the outputs by their arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 344 of file fpgaUtils.c.

00345 {
00346     Fpga_Node_t * pNode1 = Fpga_Regular(*ppNode1);
00347     Fpga_Node_t * pNode2 = Fpga_Regular(*ppNode2);
00348     float Arrival1 = pNode1->pCutBest? pNode1->pCutBest->tArrival : 0;
00349     float Arrival2 = pNode2->pCutBest? pNode2->pCutBest->tArrival : 0;
00350     if ( Arrival1 < Arrival2 )
00351         return -1;
00352     if ( Arrival1 > Arrival2 )
00353         return 1;
00354     return 0;
00355 }

Fpga_NodeVec_t* Fpga_MappingDfs ( Fpga_Man_t *  pMan,
int  fCollectEquiv 
)

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

Synopsis [Computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 52 of file fpgaUtils.c.

00053 {
00054     Fpga_NodeVec_t * vNodes;//, * vNodesCo;
00055     Fpga_Node_t * pNode;
00056     int i;
00057     // collect the CO nodes by level
00058 //    vNodesCo = Fpga_MappingOrderCosByLevel( pMan );
00059     // start the array
00060     vNodes = Fpga_NodeVecAlloc( 100 );
00061     // collect the PIs
00062     for ( i = 0; i < pMan->nInputs; i++ )
00063     {
00064         pNode = pMan->pInputs[i];
00065         Fpga_NodeVecPush( vNodes, pNode );
00066         pNode->fMark0 = 1;
00067     }
00068     // perform the traversal
00069     for ( i = 0; i < pMan->nOutputs; i++ )
00070         Fpga_MappingDfs_rec( Fpga_Regular(pMan->pOutputs[i]), vNodes, fCollectEquiv );
00071 //    for ( i = vNodesCo->nSize - 1; i >= 0 ; i-- )
00072 //        for ( pNode = vNodesCo->pArray[i]; pNode; pNode = (Fpga_Node_t *)pNode->pData0 )
00073 //            Fpga_MappingDfs_rec( pNode, vNodes, fCollectEquiv );
00074     // clean the node marks
00075     for ( i = 0; i < vNodes->nSize; i++ )
00076         vNodes->pArray[i]->fMark0 = 0;
00077 //    for ( i = 0; i < pMan->nOutputs; i++ )
00078 //        Fpga_MappingUnmark_rec( Fpga_Regular(pMan->pOutputs[i]) );
00079 //    Fpga_NodeVecFree( vNodesCo );
00080     return vNodes;
00081 }

void Fpga_MappingDfs_rec ( Fpga_Node_t *  pNode,
Fpga_NodeVec_t *  vNodes,
int  fCollectEquiv 
) [static]

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

Synopsis [Recursively computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 94 of file fpgaUtils.c.

00095 {
00096     assert( !Fpga_IsComplement(pNode) );
00097     if ( pNode->fMark0 )
00098         return;
00099     // visit the transitive fanin
00100     if ( Fpga_NodeIsAnd(pNode) )
00101     {
00102         Fpga_MappingDfs_rec( Fpga_Regular(pNode->p1), vNodes, fCollectEquiv );
00103         Fpga_MappingDfs_rec( Fpga_Regular(pNode->p2), vNodes, fCollectEquiv );
00104     }
00105     // visit the equivalent nodes
00106     if ( fCollectEquiv && pNode->pNextE )
00107         Fpga_MappingDfs_rec( pNode->pNextE, vNodes, fCollectEquiv );
00108     // make sure the node is not visited through the equivalent nodes
00109     assert( pNode->fMark0 == 0 );
00110     // mark the node as visited
00111     pNode->fMark0 = 1;
00112     // add the node to the list
00113     Fpga_NodeVecPush( vNodes, pNode );
00114 }

static void Fpga_MappingDfsCuts_rec ( Fpga_Node_t *  pNode,
Fpga_NodeVec_t *  vNodes 
) [static]
Fpga_NodeVec_t* Fpga_MappingDfsNodes ( Fpga_Man_t *  pMan,
Fpga_Node_t **  ppNodes,
int  nNodes,
int  fEquiv 
)

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

Synopsis [Computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 127 of file fpgaUtils.c.

00128 {
00129     Fpga_NodeVec_t * vNodes;
00130     int i;
00131     // perform the traversal
00132     vNodes = Fpga_NodeVecAlloc( 200 );
00133     for ( i = 0; i < nNodes; i++ )
00134         Fpga_MappingDfs_rec( ppNodes[i], vNodes, fEquiv );
00135     for ( i = 0; i < vNodes->nSize; i++ )
00136         vNodes->pArray[i]->fMark0 = 0;
00137     return vNodes;
00138 }

void Fpga_MappingFindLatest ( Fpga_Man_t *  p,
int *  pNodes,
int  nNodesMax 
) [static]

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

Synopsis [Finds given number of latest arriving COs.]

Description []

SideEffects []

SeeAlso []

Definition at line 368 of file fpgaUtils.c.

00369 {
00370     int nNodes, i, k, v;
00371     assert( p->nOutputs >= nNodesMax );
00372     pNodes[0] = 0;
00373     nNodes = 1;
00374     for ( i = 1; i < p->nOutputs; i++ )
00375     {
00376         for ( k = nNodes - 1; k >= 0; k-- )
00377             if ( Fpga_MappingCompareOutputDelay( &p->pOutputs[pNodes[k]], &p->pOutputs[i] ) >= 0 )
00378                 break;
00379         if ( k == nNodesMax - 1 )
00380             continue;
00381         if ( nNodes < nNodesMax )
00382             nNodes++;
00383         for ( v = nNodes - 1; v > k+1; v-- )
00384             pNodes[v] = pNodes[v-1];
00385         pNodes[k+1] = i;
00386     }
00387 }

float Fpga_MappingGetAreaFlow ( Fpga_Man_t *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 151 of file fpgaUtils.c.

00152 {
00153     float aFlowFlowTotal = 0;
00154     int i;
00155     for ( i = 0; i < p->nOutputs; i++ )
00156     {
00157         if ( Fpga_NodeIsConst(p->pOutputs[i]) )
00158             continue;
00159         aFlowFlowTotal += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow;
00160     }
00161     return aFlowFlowTotal;
00162 }

Fpga_NodeVec_t* Fpga_MappingLevelize ( Fpga_Man_t *  pMan,
Fpga_NodeVec_t *  vNodes 
)

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

Synopsis [Levelizes the nodes accessible from the POs.]

Description []

SideEffects []

SeeAlso []

Definition at line 745 of file fpgaUtils.c.

00746 {
00747     Fpga_NodeVec_t * vLevels;
00748     Fpga_Node_t ** ppNodes;
00749     Fpga_Node_t * pNode;
00750     int nNodes, nLevelsMax, i;
00751 
00752     // reassign the levels (this may be necessary for networks which choices)
00753     ppNodes = vNodes->pArray;
00754     nNodes  = vNodes->nSize;
00755     for ( i = 0; i < nNodes; i++ )
00756     {
00757         pNode = ppNodes[i];
00758         if ( !Fpga_NodeIsAnd(pNode) )
00759         {
00760             pNode->Level = 0;
00761             continue;
00762         }
00763         pNode->Level = 1 + FPGA_MAX( Fpga_Regular(pNode->p1)->Level, Fpga_Regular(pNode->p2)->Level );
00764     }
00765 
00766     // get the max levels
00767     nLevelsMax = 0;
00768     for ( i = 0; i < pMan->nOutputs; i++ )
00769         nLevelsMax = FPGA_MAX( nLevelsMax, (int)Fpga_Regular(pMan->pOutputs[i])->Level );
00770     nLevelsMax++;
00771 
00772     // allocate storage for levels
00773     vLevels = Fpga_NodeVecAlloc( nLevelsMax );
00774     for ( i = 0; i < nLevelsMax; i++ )
00775         Fpga_NodeVecPush( vLevels, NULL );
00776 
00777     // go through the nodes and add them to the levels
00778     for ( i = 0; i < nNodes; i++ )
00779     {
00780         pNode = ppNodes[i];
00781         pNode->pLevel = NULL;
00782         if ( !Fpga_NodeIsAnd(pNode) )
00783             continue;
00784         // attach the node to this level
00785         pNode->pLevel = Fpga_NodeVecReadEntry( vLevels, pNode->Level );
00786         Fpga_NodeVecWriteEntry( vLevels, pNode->Level, pNode );
00787     }
00788     return vLevels;
00789 }

int Fpga_MappingMaxLevel ( Fpga_Man_t *  pMan  ) 

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

Synopsis [Sets up the mask.]

Description []

SideEffects []

SeeAlso []

Definition at line 802 of file fpgaUtils.c.

00803 {
00804     int nLevelMax, i;
00805     nLevelMax = 0;
00806     for ( i = 0; i < pMan->nOutputs; i++ )
00807         nLevelMax = nLevelMax > (int)Fpga_Regular(pMan->pOutputs[i])->Level? 
00808                 nLevelMax : (int)Fpga_Regular(pMan->pOutputs[i])->Level;
00809     return nLevelMax;
00810 }

Fpga_NodeVec_t * Fpga_MappingOrderCosByLevel ( Fpga_Man_t *  pMan  )  [static]

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

Synopsis [Returns the array of CO nodes sorted by level.]

Description []

SideEffects []

SeeAlso []

Definition at line 952 of file fpgaUtils.c.

00953 {
00954     Fpga_Node_t * pNode;
00955     Fpga_NodeVec_t * vNodes;
00956     int i, nLevels;
00957     // get the largest level of a CO
00958     nLevels = Fpga_MappingMaxLevel( pMan );
00959     // allocate the array of nodes
00960     vNodes = Fpga_NodeVecAlloc( nLevels + 1 );
00961     for ( i = 0; i <= nLevels; i++ )
00962         Fpga_NodeVecPush( vNodes, NULL );
00963     // clean the marks
00964     for ( i = 0; i < pMan->nOutputs; i++ )
00965         Fpga_Regular(pMan->pOutputs[i])->fMark0 = 0;
00966     // put the nodes into the structure
00967     for ( i = 0; i < pMan->nOutputs; i++ )
00968     {
00969         pNode = Fpga_Regular(pMan->pOutputs[i]);
00970         if ( pNode->fMark0 )
00971             continue;
00972         pNode->fMark0 = 1;
00973         pNode->pData0 = (char *)Fpga_NodeVecReadEntry( vNodes, pNode->Level );
00974         Fpga_NodeVecWriteEntry( vNodes, pNode->Level, pNode );
00975     }
00976     for ( i = 0; i < pMan->nOutputs; i++ )
00977         Fpga_Regular(pMan->pOutputs[i])->fMark0 = 0;
00978     return vNodes;
00979 
00980 }

void Fpga_MappingPrintOutputArrivals ( Fpga_Man_t *  p  ) 

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

Synopsis [Prints a bunch of latest arriving outputs.]

Description []

SideEffects []

SeeAlso []

Definition at line 400 of file fpgaUtils.c.

00401 {
00402     Fpga_Node_t * pNode;
00403     int pSorted[FPGA_CO_LIST_SIZE];
00404     int fCompl, Limit, MaxNameSize, i;
00405 
00406     // determine the number of nodes to print
00407     Limit = (p->nOutputs > FPGA_CO_LIST_SIZE)? FPGA_CO_LIST_SIZE : p->nOutputs;
00408 
00409     // determine the order
00410     Fpga_MappingFindLatest( p, pSorted, Limit );
00411 
00412     // determine max size of the node's name
00413     MaxNameSize = 0;
00414     for ( i = 0; i < Limit; i++ )
00415         if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) )
00416             MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]);
00417 
00418     // print the latest outputs
00419     for ( i = 0; i < Limit; i++ )
00420     {
00421         // get the i-th latest output
00422         pNode  = Fpga_Regular(p->pOutputs[pSorted[i]]);
00423         fCompl = Fpga_IsComplement(p->pOutputs[pSorted[i]]);
00424         // print out the best arrival time
00425         printf( "Output  %-*s : ", MaxNameSize + 3, p->ppOutputNames[pSorted[i]] );
00426         printf( "Delay = %8.2f  ",     (double)pNode->pCutBest->tArrival );
00427         if ( fCompl )
00428             printf( "NEG" );
00429         else
00430             printf( "POS" );
00431         printf( "\n" );
00432     }
00433 }

void Fpga_MappingSetChoiceLevels ( Fpga_Man_t *  pMan  ) 

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

Synopsis [Resets the levels of the nodes in the choice graph.]

Description [Makes the level of the choice nodes to be equal to the maximum of the level of the nodes in the equivalence class. This way sorting by level leads to the reverse topological order, which is needed for the required time computation.]

SideEffects []

SeeAlso []

Definition at line 874 of file fpgaUtils.c.

00875 {
00876     int i;
00877     pMan->nTravIds++;
00878     for ( i = 0; i < pMan->nOutputs; i++ )
00879         Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 1 );
00880 }

float Fpga_MappingSetRefsAndArea ( Fpga_Man_t *  pMan  ) 

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

Synopsis [Sets the correct reference counts for the mapping.]

Description [Collects the nodes in reverse topological order and places in them in array pMan->vMapping.]

SideEffects []

SeeAlso []

Definition at line 297 of file fpgaUtils.c.

00298 {
00299     Fpga_Node_t * pNode, ** ppStore;
00300     float aArea;
00301     int i, LevelMax;
00302 
00303     // clean all references
00304     for ( i = 0; i < pMan->vNodesAll->nSize; i++ )
00305         pMan->vNodesAll->pArray[i]->nRefs = 0;
00306 
00307     // allocate place to store the nodes
00308     LevelMax = Fpga_MappingMaxLevel( pMan );
00309     ppStore = ALLOC( Fpga_Node_t *, LevelMax + 1 );
00310     memset( ppStore, 0, sizeof(Fpga_Node_t *) * (LevelMax + 1) );
00311 
00312     // collect nodes reachable from POs in the DFS order through the best cuts
00313     aArea = 0;
00314     for ( i = 0; i < pMan->nOutputs; i++ )
00315     {
00316         pNode = Fpga_Regular(pMan->pOutputs[i]);
00317         if ( pNode == pMan->pConst1 )
00318             continue;
00319         aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode, ppStore );
00320         pNode->nRefs++;
00321     }
00322 
00323     // reconnect the nodes in reverse topological order
00324     pMan->vMapping->nSize = 0;
00325     for ( i = LevelMax; i >= 0; i-- )
00326         for ( pNode = ppStore[i]; pNode; pNode = (Fpga_Node_t *)pNode->pData0 )
00327             Fpga_NodeVecPush( pMan->vMapping, pNode );
00328     free( ppStore );
00329     return aArea;
00330 }

float Fpga_MappingSetRefsAndArea_rec ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pNode,
Fpga_Node_t **  ppStore 
)

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

Synopsis [Recursively computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 265 of file fpgaUtils.c.

00266 {
00267     float aArea;
00268     int i;
00269     assert( !Fpga_IsComplement(pNode) );
00270     if ( pNode->nRefs++ )
00271         return 0;
00272     if ( !Fpga_NodeIsAnd(pNode) )
00273         return 0;
00274     assert( pNode->pCutBest != NULL );
00275     // store the node in the structure by level
00276     pNode->pData0 = (char *)ppStore[pNode->Level]; 
00277     ppStore[pNode->Level] = pNode;
00278     // visit the transitive fanin of the selected cut
00279     aArea = pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves];
00280     for ( i = 0; i < pNode->pCutBest->nLeaves; i++ )
00281         aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode->pCutBest->ppLeaves[i], ppStore );
00282     return aArea;
00283 }

void Fpga_MappingSetupMask ( unsigned  uMask[],
int  nVarsMax 
)

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

Synopsis [Sets up the mask.]

Description []

SideEffects []

SeeAlso []

Definition at line 473 of file fpgaUtils.c.

00474 {
00475     if ( nVarsMax == 6 )
00476         uMask[0] = uMask[1] = FPGA_FULL;
00477     else
00478     {
00479         uMask[0] = FPGA_MASK(1 << nVarsMax);
00480         uMask[1] = 0;
00481     }
00482 }

void Fpga_MappingSetupTruthTables ( unsigned  uTruths[][2]  ) 

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

Synopsis [Sets up the truth tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 447 of file fpgaUtils.c.

00448 {
00449     int m, v;
00450     // set up the truth tables
00451     for ( m = 0; m < 32; m++ )
00452         for ( v = 0; v < 5; v++ )
00453             if ( m & (1 << v) )
00454                 uTruths[v][0] |= (1 << m);
00455     // make adjustments for the case of 6 variables
00456     for ( v = 0; v < 5; v++ )
00457         uTruths[v][1] = uTruths[v][0];
00458     uTruths[5][0] = 0;
00459     uTruths[5][1] = FPGA_FULL;
00460 }

void Fpga_MappingSortByLevel ( Fpga_Man_t *  pMan,
Fpga_NodeVec_t *  vNodes,
int  fIncreasing 
)

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

Synopsis [Orders the nodes in the decreasing order of levels.]

Description []

SideEffects []

SeeAlso []

Definition at line 582 of file fpgaUtils.c.

00583 {
00584     if ( fIncreasing )
00585         qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *), 
00586                 (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelIncreasing );
00587     else
00588         qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *), 
00589                 (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelDecreasing );
00590 //    assert( Fpga_CompareNodesByLevel( vNodes->pArray, vNodes->pArray + vNodes->nSize - 1 ) <= 0 );
00591 }

int Fpga_MappingUpdateLevel_rec ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pNode,
int  fMaximum 
)

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

Synopsis [Analyses choice nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 824 of file fpgaUtils.c.

00825 {
00826     Fpga_Node_t * pTemp;
00827     int Level1, Level2, LevelE;
00828     assert( !Fpga_IsComplement(pNode) );
00829     if ( !Fpga_NodeIsAnd(pNode) )
00830         return pNode->Level;
00831     // skip the visited node
00832     if ( pNode->TravId == pMan->nTravIds )
00833         return pNode->Level;
00834     pNode->TravId = pMan->nTravIds;
00835     // compute levels of the children nodes
00836     Level1 = Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pNode->p1), fMaximum );
00837     Level2 = Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pNode->p2), fMaximum );
00838     pNode->Level = 1 + FPGA_MAX( Level1, Level2 );
00839     if ( pNode->pNextE )
00840     {
00841         LevelE = Fpga_MappingUpdateLevel_rec( pMan, pNode->pNextE, fMaximum );
00842         if ( fMaximum )
00843         {
00844             if ( pNode->Level < (unsigned)LevelE )
00845                 pNode->Level = LevelE;
00846         }
00847         else
00848         {
00849             if ( pNode->Level > (unsigned)LevelE )
00850                 pNode->Level = LevelE;
00851         }
00852         // set the level of all equivalent nodes to be the same minimum
00853         if ( pNode->pRepr == NULL ) // the primary node
00854             for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE )
00855                 pTemp->Level = pNode->Level;
00856     }
00857     return pNode->Level;
00858 }

Variable Documentation

Fpga_Man_t* s_pMan = NULL [static]

Definition at line 34 of file fpgaUtils.c.

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