src/map/fpga/fpgaInt.h File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "extra.h"
#include "fpga.h"
Include dependency graph for fpgaInt.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  Fpga_ManStruct_t_
struct  Fpga_LutLibStruct_t_
struct  Fpga_NodeStruct_t_
struct  Fpga_CutStruct_t_
struct  Fpga_NodeVecStruct_t_

Defines

#define FPGA_MAX_LEAVES   6
#define FPGA_MASK(n)   ((~((unsigned)0)) >> (32-(n)))
#define FPGA_FULL   (~((unsigned)0))
#define FPGA_NO_VAR   (-9999.0)
#define FPGA_NUM_BYTES(n)   (((n)/16 + (((n)%16) > 0))*16)
#define FPGA_MIN(a, b)   (((a) < (b))? (a) : (b))
#define FPGA_MAX(a, b)   (((a) > (b))? (a) : (b))
#define FPGA_FLOAT_LARGE   ((float)1.0e+20)
#define FPGA_FLOAT_SMALL   ((float)1.0e-20)
#define FPGA_INT_LARGE   (10000000)
#define FPGA_SEQ_SIGN(p)   (1 << (((unsigned)p)%31));
#define Fpga_CutIsComplement(p)   (((int)((unsigned long) (p) & 01)))
#define Fpga_CutRegular(p)   ((Fpga_Cut_t *)((unsigned long)(p) & ~01))
#define Fpga_CutNot(p)   ((Fpga_Cut_t *)((unsigned long)(p) ^ 01))
#define Fpga_CutNotCond(p, c)   ((Fpga_Cut_t *)((unsigned long)(p) ^ (c)))
#define Fpga_SeqIsComplement(p)   (((int)((unsigned long) (p) & 01)))
#define Fpga_SeqRegular(p)   ((Fpga_Node_t *)((unsigned long)(p) & ~015))
#define Fpga_SeqIndex(p)   ((((unsigned long)(p)) >> 1) & 07)
#define Fpga_SeqIndexCreate(p, Ind)   (((unsigned long)(p)) | (1 << (((unsigned)(Ind)) & 07)))
#define Fpga_NodeReadRef(p)   ((Fpga_Regular(p))->nRefs)
#define Fpga_NodeRef(p)   ((Fpga_Regular(p))->nRefs++)
#define Fpga_NodeIsSimComplement(p)   (Fpga_IsComplement(p)? !(Fpga_Regular(p)->fInv) : (p)->fInv)
#define FPGA_RANDOM_UNSIGNED   ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand()))
#define PRT(a, t)   printf("%s = ", (a)); printf("%6.2f sec\n", (float)(t)/(float)(CLOCKS_PER_SEC))
#define Fpga_NodeReadNextFanout(pNode, pFanout)
#define Fpga_NodeReadNextFanoutPlace(pNode, pFanout)
#define Fpga_NodeForEachFanout(pNode, pFanout)
#define Fpga_NodeForEachFanoutSafe(pNode, pFanout, pFanout2)

Functions

static Fpga_FloatMoreThan (Fpga_Man_t *p, float Arg1, float Arg2)
static Fpga_FloatLessThan (Fpga_Man_t *p, float Arg1, float Arg2)
static Fpga_FloatEqual (Fpga_Man_t *p, float Arg1, float Arg2)
void Fpga_MappingCuts (Fpga_Man_t *p)
void Fpga_MappingCreatePiCuts (Fpga_Man_t *p)
int Fpga_CutCountAll (Fpga_Man_t *pMan)
Fpga_Cut_t * Fpga_CutAlloc (Fpga_Man_t *p)
Fpga_Cut_t * Fpga_CutDup (Fpga_Man_t *p, Fpga_Cut_t *pCutOld)
void Fpga_CutFree (Fpga_Man_t *p, Fpga_Cut_t *pCut)
void Fpga_CutPrint (Fpga_Man_t *p, Fpga_Node_t *pRoot, Fpga_Cut_t *pCut)
Fpga_Cut_t * Fpga_CutCreateSimple (Fpga_Man_t *p, Fpga_Node_t *pNode)
float Fpga_CutGetRootArea (Fpga_Man_t *p, Fpga_Cut_t *pCut)
Fpga_Cut_t * Fpga_CutListAppend (Fpga_Cut_t *pSetAll, Fpga_Cut_t *pSets)
void Fpga_CutListRecycle (Fpga_Man_t *p, Fpga_Cut_t *pSetList, Fpga_Cut_t *pSave)
int Fpga_CutListCount (Fpga_Cut_t *pSets)
void Fpga_CutRemoveFanouts (Fpga_Man_t *p, Fpga_Node_t *pNode, Fpga_Cut_t *pCut)
void Fpga_CutInsertFanouts (Fpga_Man_t *p, Fpga_Node_t *pNode, Fpga_Cut_t *pCut)
float Fpga_CutGetAreaRefed (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
float Fpga_CutGetAreaDerefed (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
float Fpga_CutRef (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
float Fpga_CutDeref (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
float Fpga_CutGetAreaFlow (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
void Fpga_CutGetParameters (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
void Fpga_NodeAddFaninFanout (Fpga_Node_t *pFanin, Fpga_Node_t *pFanout)
void Fpga_NodeRemoveFaninFanout (Fpga_Node_t *pFanin, Fpga_Node_t *pFanoutToRemove)
int Fpga_NodeGetFanoutNum (Fpga_Node_t *pNode)
Fpga_LutLib_t * Fpga_LutLibCreate (char *FileName, int fVerbose)
void Fpga_LutLibFree (Fpga_LutLib_t *p)
void Fpga_LutLibPrint (Fpga_LutLib_t *pLutLib)
int Fpga_LutLibDelaysAreDiscrete (Fpga_LutLib_t *pLutLib)
int Fpga_MappingMatches (Fpga_Man_t *p, int fDelayOriented)
int Fpga_MappingMatchesArea (Fpga_Man_t *p)
int Fpga_MappingMatchesSwitch (Fpga_Man_t *p)
void Fpga_MappingShow (Fpga_Man_t *pMan, char *pFileName)
void Fpga_MappingShowNodes (Fpga_Man_t *pMan, Fpga_Node_t **ppRoots, int nRoots, char *pFileName)
float Fpga_CutGetSwitchDerefed (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut)
float Fpga_CutRefSwitch (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
float Fpga_CutDerefSwitch (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
float Fpga_MappingGetSwitching (Fpga_Man_t *pMan, Fpga_NodeVec_t *vMapping)
float Fpga_TimeCutComputeArrival (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
float Fpga_TimeCutComputeArrival_rec (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
float Fpga_TimeComputeArrivalMax (Fpga_Man_t *p)
void Fpga_TimeComputeRequiredGlobal (Fpga_Man_t *p, int fFirstTime)
void Fpga_TimeComputeRequired (Fpga_Man_t *p, float fRequired)
void Fpga_TimePropagateRequired (Fpga_Man_t *p, Fpga_NodeVec_t *vNodes)
void Fpga_TimePropagateArrival (Fpga_Man_t *p)
Fpga_NodeVec_t * Fpga_NodeVecAlloc (int nCap)
void Fpga_NodeVecFree (Fpga_NodeVec_t *p)
Fpga_Node_t ** Fpga_NodeVecReadArray (Fpga_NodeVec_t *p)
int Fpga_NodeVecReadSize (Fpga_NodeVec_t *p)
void Fpga_NodeVecGrow (Fpga_NodeVec_t *p, int nCapMin)
void Fpga_NodeVecShrink (Fpga_NodeVec_t *p, int nSizeNew)
void Fpga_NodeVecClear (Fpga_NodeVec_t *p)
void Fpga_NodeVecPush (Fpga_NodeVec_t *p, Fpga_Node_t *Entry)
int Fpga_NodeVecPushUnique (Fpga_NodeVec_t *p, Fpga_Node_t *Entry)
Fpga_Node_t * Fpga_NodeVecPop (Fpga_NodeVec_t *p)
void Fpga_NodeVecWriteEntry (Fpga_NodeVec_t *p, int i, Fpga_Node_t *Entry)
Fpga_Node_t * Fpga_NodeVecReadEntry (Fpga_NodeVec_t *p, int i)
void Fpga_NodeVecSortByLevel (Fpga_NodeVec_t *p)
void Fpga_SortNodesByArrivalTimes (Fpga_NodeVec_t *p)
void Fpga_NodeVecUnion (Fpga_NodeVec_t *p, Fpga_NodeVec_t *p1, Fpga_NodeVec_t *p2)
void Fpga_NodeVecPushOrder (Fpga_NodeVec_t *vNodes, Fpga_Node_t *pNode, int fIncreasing)
void Fpga_NodeVecReverse (Fpga_NodeVec_t *vNodes)
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)
int Fpga_CountLevels (Fpga_Man_t *pMan)
float Fpga_MappingGetAreaFlow (Fpga_Man_t *p)
float Fpga_MappingArea (Fpga_Man_t *pMan)
float Fpga_MappingAreaTrav (Fpga_Man_t *pMan)
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)
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)
Fpga_NodeVec_t * Fpga_MappingLevelize (Fpga_Man_t *pMan, Fpga_NodeVec_t *vNodes)
int Fpga_MappingMaxLevel (Fpga_Man_t *pMan)
void Fpga_ManReportChoices (Fpga_Man_t *pMan)
void Fpga_MappingSetChoiceLevels (Fpga_Man_t *pMan)
unsigned int Cudd_Prime (unsigned int p)

Define Documentation

#define Fpga_CutIsComplement ( p   )     (((int)((unsigned long) (p) & 01)))

Definition at line 70 of file fpgaInt.h.

#define Fpga_CutNot ( p   )     ((Fpga_Cut_t *)((unsigned long)(p) ^ 01))

Definition at line 72 of file fpgaInt.h.

#define Fpga_CutNotCond ( p,
c   )     ((Fpga_Cut_t *)((unsigned long)(p) ^ (c)))

Definition at line 73 of file fpgaInt.h.

#define Fpga_CutRegular ( p   )     ((Fpga_Cut_t *)((unsigned long)(p) & ~01))

Definition at line 71 of file fpgaInt.h.

#define FPGA_FLOAT_LARGE   ((float)1.0e+20)

Definition at line 62 of file fpgaInt.h.

#define FPGA_FLOAT_SMALL   ((float)1.0e-20)

Definition at line 63 of file fpgaInt.h.

#define FPGA_FULL   (~((unsigned)0))

Definition at line 53 of file fpgaInt.h.

#define FPGA_INT_LARGE   (10000000)

Definition at line 64 of file fpgaInt.h.

#define FPGA_MASK ( n   )     ((~((unsigned)0)) >> (32-(n)))

Definition at line 52 of file fpgaInt.h.

#define FPGA_MAX ( a,
b   )     (((a) > (b))? (a) : (b))

Definition at line 59 of file fpgaInt.h.

#define FPGA_MAX_LEAVES   6

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

FileName [fpgaInt.h]

PackageName [MVSIS 2.0: 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
fpgaInt.h,v 1.8 2004/09/30 21:18:10 satrajit Exp

] INCLUDES /// PARAMETERS /// MACRO DEFINITIONS ///

Definition at line 49 of file fpgaInt.h.

#define FPGA_MIN ( a,
b   )     (((a) < (b))? (a) : (b))

Definition at line 58 of file fpgaInt.h.

#define FPGA_NO_VAR   (-9999.0)

Definition at line 54 of file fpgaInt.h.

#define Fpga_NodeForEachFanout ( pNode,
pFanout   ) 
Value:
for ( pFanout = (pNode)->pFanPivot; pFanout;                 \
          pFanout = Fpga_NodeReadNextFanout(pNode, pFanout) )

Definition at line 269 of file fpgaInt.h.

#define Fpga_NodeForEachFanoutSafe ( pNode,
pFanout,
pFanout2   ) 
Value:
for ( pFanout  = (pNode)->pFanPivot,                         \
          pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout);    \
          pFanout;                                               \
          pFanout  = pFanout2,                                   \
          pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout) )

Definition at line 274 of file fpgaInt.h.

#define Fpga_NodeIsSimComplement ( p   )     (Fpga_IsComplement(p)? !(Fpga_Regular(p)->fInv) : (p)->fInv)

Definition at line 86 of file fpgaInt.h.

#define Fpga_NodeReadNextFanout ( pNode,
pFanout   ) 
Value:
( ( pFanout == NULL )? NULL :                                \
        ((Fpga_Regular((pFanout)->p1) == (pNode))?               \
             (pFanout)->pFanFanin1 : (pFanout)->pFanFanin2) )

Definition at line 258 of file fpgaInt.h.

#define Fpga_NodeReadNextFanoutPlace ( pNode,
pFanout   ) 
Value:
( (Fpga_Regular((pFanout)->p1) == (pNode))?                  \
         &(pFanout)->pFanFanin1 : &(pFanout)->pFanFanin2 )

Definition at line 264 of file fpgaInt.h.

#define Fpga_NodeReadRef ( p   )     ((Fpga_Regular(p))->nRefs)

Definition at line 82 of file fpgaInt.h.

#define Fpga_NodeRef ( p   )     ((Fpga_Regular(p))->nRefs++)

Definition at line 83 of file fpgaInt.h.

#define FPGA_NUM_BYTES ( n   )     (((n)/16 + (((n)%16) > 0))*16)

Definition at line 55 of file fpgaInt.h.

#define FPGA_RANDOM_UNSIGNED   ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand()))

Definition at line 89 of file fpgaInt.h.

#define FPGA_SEQ_SIGN ( p   )     (1 << (((unsigned)p)%31));

Definition at line 67 of file fpgaInt.h.

#define Fpga_SeqIndex ( p   )     ((((unsigned long)(p)) >> 1) & 07)

Definition at line 78 of file fpgaInt.h.

#define Fpga_SeqIndexCreate ( p,
Ind   )     (((unsigned long)(p)) | (1 << (((unsigned)(Ind)) & 07)))

Definition at line 79 of file fpgaInt.h.

#define Fpga_SeqIsComplement ( p   )     (((int)((unsigned long) (p) & 01)))

Definition at line 76 of file fpgaInt.h.

#define Fpga_SeqRegular ( p   )     ((Fpga_Node_t *)((unsigned long)(p) & ~015))

Definition at line 77 of file fpgaInt.h.

#define PRT ( a,
t   )     printf("%s = ", (a)); printf("%6.2f sec\n", (float)(t)/(float)(CLOCKS_PER_SEC))

Definition at line 92 of file fpgaInt.h.

Function Documentation

unsigned int Cudd_Prime ( unsigned int  p  ) 

AutomaticEnd Function********************************************************************

Synopsis [Returns the next prime >= p.]

Description []

SideEffects [None]

Definition at line 152 of file cuddTable.c.

00154 {
00155     int i,pn;
00156 
00157     p--;
00158     do {
00159         p++;
00160         if (p&1) {
00161             pn = 1;
00162             i = 3;
00163             while ((unsigned) (i * i) <= p) {
00164                 if (p % i == 0) {
00165                     pn = 0;
00166                     break;
00167                 }
00168                 i += 2;
00169             }
00170         } else {
00171             pn = 0;
00172         }
00173     } while (!pn);
00174     return(p);
00175 
00176 } /* end of Cudd_Prime */

int Fpga_CountLevels ( Fpga_Man_t *  pMan  ) 
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 }

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 }

Fpga_Cut_t* Fpga_CutCreateSimple ( Fpga_Man_t *  p,
Fpga_Node_t *  pNode 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 120 of file fpgaCutUtils.c.

00121 {
00122     Fpga_Cut_t * pCut;
00123     pCut = Fpga_CutAlloc( p );
00124     pCut->pRoot       = pNode;
00125     pCut->nLeaves     = 1;
00126     pCut->ppLeaves[0] = pNode;
00127     pCut->uSign = FPGA_SEQ_SIGN(pCut->ppLeaves[0]);
00128     return pCut;
00129 }

float Fpga_CutDeref ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pNode,
Fpga_Cut_t *  pCut,
int  fFanouts 
)

function*************************************************************

synopsis [Dereferences the cut.]

description [This procedure is similar to the procedure NodeRecusiveDeref.]

sideeffects []

seealso []

Definition at line 417 of file fpgaCutUtils.c.

00418 {
00419     Fpga_Node_t * pNodeChild;
00420     float aArea;
00421     int i;
00422 
00423     // deref the fanouts
00424 //    if ( fFanouts ) 
00425 //        Fpga_CutRemoveFanouts( pMan, pNode, pCut );
00426 
00427     // start the area of this cut
00428     aArea = pMan->pLutLib->pLutAreas[pCut->nLeaves];
00429     // go through the children
00430     for ( i = 0; i < pCut->nLeaves; i++ )
00431     {
00432         pNodeChild = pCut->ppLeaves[i];
00433         assert( pNodeChild->nRefs > 0 );
00434         if ( --pNodeChild->nRefs > 0 )  
00435             continue;
00436         if ( !Fpga_NodeIsAnd(pNodeChild) ) 
00437             continue;
00438         aArea += Fpga_CutDeref( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts );
00439     }
00440     return aArea;
00441 }

float Fpga_CutDerefSwitch ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pNode,
Fpga_Cut_t *  pCut,
int  fFanouts 
)

function*************************************************************

synopsis [Dereferences the cut.]

description [This procedure is similar to the procedure NodeRecusiveDeref.]

sideeffects []

seealso []

Definition at line 92 of file fpgaSwitch.c.

00093 {
00094     Fpga_Node_t * pNodeChild;
00095     float aArea;
00096     int i;
00097     // start the area of this cut
00098     aArea = pNode->Switching;
00099     if ( pCut->nLeaves == 1 )
00100         return aArea;
00101     // go through the children
00102     for ( i = 0; i < pCut->nLeaves; i++ )
00103     {
00104         pNodeChild = pCut->ppLeaves[i];
00105         assert( pNodeChild->nRefs > 0 );
00106         if ( --pNodeChild->nRefs > 0 )  
00107             continue;
00108         aArea += Fpga_CutDerefSwitch( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts );
00109     }
00110     return aArea;
00111 }

Fpga_Cut_t* Fpga_CutDup ( Fpga_Man_t *  p,
Fpga_Cut_t *  pCutOld 
)

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

Synopsis [Duplicates the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 59 of file fpgaCutUtils.c.

00060 {
00061     Fpga_Cut_t * pCutNew;
00062     int i;
00063     pCutNew = Fpga_CutAlloc( p );
00064     pCutNew->pRoot   = pCutOld->pRoot;
00065     pCutNew->nLeaves = pCutOld->nLeaves;
00066     for ( i = 0; i < pCutOld->nLeaves; i++ )
00067         pCutNew->ppLeaves[i] = pCutOld->ppLeaves[i];
00068     return pCutNew;
00069 }

void Fpga_CutFree ( Fpga_Man_t *  p,
Fpga_Cut_t *  pCut 
)

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

Synopsis [Deallocates the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 82 of file fpgaCutUtils.c.

00083 {
00084     if ( pCut )
00085     Extra_MmFixedEntryRecycle( p->mmCuts, (char *)pCut );
00086 }

float Fpga_CutGetAreaDerefed ( Fpga_Man_t *  pMan,
Fpga_Cut_t *  pCut 
)

function*************************************************************

synopsis [Computes the exact area associated with the cut.]

description []

sideeffects []

seealso []

Definition at line 358 of file fpgaCutUtils.c.

00359 {
00360     float aResult, aResult2;
00361     if ( pCut->nLeaves == 1 )
00362         return 0;
00363     aResult2 = Fpga_CutRef( pMan, NULL, pCut, 0 );
00364     aResult  = Fpga_CutDeref( pMan, NULL, pCut, 0 );
00365     assert( Fpga_FloatEqual( pMan, aResult, aResult2 ) );
00366     return aResult;
00367 }

float Fpga_CutGetAreaFlow ( Fpga_Man_t *  pMan,
Fpga_Cut_t *  pCut 
)

function*************************************************************

synopsis [Computes the area flow of the cut.]

description []

sideeffects []

seealso []

Definition at line 310 of file fpgaCutUtils.c.

00311 {
00312     Fpga_Cut_t * pCutFanin;
00313     int i;
00314     pCut->aFlow = pMan->pLutLib->pLutAreas[pCut->nLeaves];
00315     for ( i = 0; i < pCut->nLeaves; i++ )
00316     {
00317         // get the cut implementing this phase of the fanin
00318         pCutFanin  = pCut->ppLeaves[i]->pCutBest;   
00319         assert( pCutFanin );
00320         pCut->aFlow  += pCutFanin->aFlow / pCut->ppLeaves[i]->nRefs;
00321     }
00322     return pCut->aFlow;
00323 }

float Fpga_CutGetAreaRefed ( Fpga_Man_t *  pMan,
Fpga_Cut_t *  pCut 
)

function*************************************************************

synopsis [Computes the exact area associated with the cut.]

description []

sideeffects []

seealso []

Definition at line 336 of file fpgaCutUtils.c.

00337 {
00338     float aResult, aResult2;
00339     if ( pCut->nLeaves == 1 )
00340         return 0;
00341     aResult  = Fpga_CutDeref( pMan, NULL, pCut, 0 );
00342     aResult2 = Fpga_CutRef( pMan, NULL, pCut, 0 );
00343     assert( Fpga_FloatEqual( pMan, aResult, aResult2 ) );
00344     return aResult;
00345 }

void Fpga_CutGetParameters ( Fpga_Man_t *  pMan,
Fpga_Cut_t *  pCut 
)

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

Synopsis [Computes the arrival time and the area flow of the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 275 of file fpgaCutUtils.c.

00276 {
00277     Fpga_Cut_t * pFaninCut;
00278     int i;
00279     pCut->tArrival = -FPGA_FLOAT_LARGE;
00280     pCut->aFlow    = pMan->pLutLib->pLutAreas[pCut->nLeaves];
00281     for ( i = 0; i < pCut->nLeaves; i++ )
00282     {
00283         pFaninCut = pCut->ppLeaves[i]->pCutBest;
00284         if ( pCut->tArrival < pFaninCut->tArrival )
00285              pCut->tArrival = pFaninCut->tArrival;
00286         // if the fanout count is not set, assume it to be 1
00287         if ( pCut->ppLeaves[i]->nRefs == 0 )
00288             pCut->aFlow += pFaninCut->aFlow;
00289         else
00290 //            pCut->aFlow += pFaninCut->aFlow / pCut->ppLeaves[i]->nRefs;
00291             pCut->aFlow += pFaninCut->aFlow / pCut->ppLeaves[i]->aEstFanouts;
00292     }
00293     // use the first pin to compute the delay of the LUT 
00294     // (this mapper does not support the variable pin delay model)
00295     pCut->tArrival += pMan->pLutLib->pLutDelays[pCut->nLeaves][0];
00296 }

float Fpga_CutGetRootArea ( Fpga_Man_t *  p,
Fpga_Cut_t *  pCut 
)

function*************************************************************

synopsis [Computes the exact area associated with the cut.]

description []

sideeffects []

seealso []

Definition at line 143 of file fpgaCutUtils.c.

00144 {
00145     return p->pLutLib->pLutAreas[pCut->nLeaves];
00146 }

float Fpga_CutGetSwitchDerefed ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pNode,
Fpga_Cut_t *  pCut 
)

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

FileName [fpgaSwitch.c]

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

Synopsis [Generic technology mapping engine.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - September 8, 2003.]

Revision [

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

] DECLARATIONS /// FUNCTION DEFINITIONS ///function*************************************************************

synopsis [Computes the exact area associated with the cut.]

description []

sideeffects []

seealso []

Definition at line 40 of file fpgaSwitch.c.

00041 {
00042     float aResult, aResult2;
00043     aResult2 = Fpga_CutRefSwitch( pMan, pNode, pCut, 0 );
00044     aResult  = Fpga_CutDerefSwitch( pMan, pNode, pCut, 0 );
00045 //    assert( aResult == aResult2 );
00046     return aResult;
00047 }

void Fpga_CutInsertFanouts ( Fpga_Man_t *  p,
Fpga_Node_t *  pNode,
Fpga_Cut_t *  pCut 
)
Fpga_Cut_t* Fpga_CutListAppend ( Fpga_Cut_t *  pSetAll,
Fpga_Cut_t *  pSets 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 159 of file fpgaCutUtils.c.

00160 {
00161     Fpga_Cut_t * pPrev, * pTemp;
00162     if ( pSetAll == NULL )
00163         return pSets;
00164     if ( pSets == NULL )
00165         return pSetAll;
00166     // find the last one
00167     for ( pTemp = pSets; pTemp; pTemp = pTemp->pNext )
00168         pPrev = pTemp;
00169     // append all the end of the current set
00170     assert( pPrev->pNext == NULL );
00171     pPrev->pNext = pSetAll;
00172     return pSets;
00173 }

int Fpga_CutListCount ( Fpga_Cut_t *  pSets  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 207 of file fpgaCutUtils.c.

00208 {
00209     Fpga_Cut_t * pTemp;
00210     int i;
00211     for ( i = 0, pTemp = pSets; pTemp; pTemp = pTemp->pNext, i++ );
00212     return i;
00213 }

void Fpga_CutListRecycle ( Fpga_Man_t *  p,
Fpga_Cut_t *  pSetList,
Fpga_Cut_t *  pSave 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 186 of file fpgaCutUtils.c.

00187 {
00188     Fpga_Cut_t * pNext, * pTemp;
00189     for ( pTemp = pSetList, pNext = pTemp? pTemp->pNext : NULL; 
00190           pTemp; 
00191           pTemp = pNext, pNext = pNext? pNext->pNext : NULL )
00192         if ( pTemp != pSave )
00193             Extra_MmFixedEntryRecycle( p->mmCuts, (char *)pTemp );
00194 }

void Fpga_CutPrint ( Fpga_Man_t *  p,
Fpga_Node_t *  pRoot,
Fpga_Cut_t *  pCut 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 99 of file fpgaCutUtils.c.

00100 {
00101     int i;
00102     printf( "CUT:  Delay = %4.2f. Area = %4.2f. Nodes = %d -> {", 
00103         pCut->tArrival, pCut->aFlow, pRoot->Num );
00104     for ( i = 0; i < pCut->nLeaves; i++ )
00105         printf( " %d", pCut->ppLeaves[i]->Num );
00106     printf( " } \n" );
00107 }

float Fpga_CutRef ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pNode,
Fpga_Cut_t *  pCut,
int  fFanouts 
)

function*************************************************************

synopsis [References the cut.]

description [This procedure is similar to the procedure NodeReclaim.]

sideeffects []

seealso []

Definition at line 380 of file fpgaCutUtils.c.

00381 {
00382     Fpga_Node_t * pNodeChild;
00383     float aArea;
00384     int i;
00385 
00386     // deref the fanouts
00387 //    if ( fFanouts ) 
00388 //        Fpga_CutInsertFanouts( pMan, pNode, pCut );
00389 
00390     // start the area of this cut
00391     aArea = pMan->pLutLib->pLutAreas[pCut->nLeaves];
00392     // go through the children
00393     for ( i = 0; i < pCut->nLeaves; i++ )
00394     {
00395         pNodeChild = pCut->ppLeaves[i];
00396         assert( pNodeChild->nRefs >= 0 );
00397         if ( pNodeChild->nRefs++ > 0 )  
00398             continue;
00399         if ( !Fpga_NodeIsAnd(pNodeChild) ) 
00400             continue;
00401         aArea += Fpga_CutRef( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts );
00402     }
00403     return aArea;
00404 }

float Fpga_CutRefSwitch ( Fpga_Man_t *  pMan,
Fpga_Node_t *  pNode,
Fpga_Cut_t *  pCut,
int  fFanouts 
)

function*************************************************************

synopsis [References the cut.]

description [This procedure is similar to the procedure NodeReclaim.]

sideeffects []

seealso []

Definition at line 60 of file fpgaSwitch.c.

00061 {
00062     Fpga_Node_t * pNodeChild;
00063     float aArea;
00064     int i;
00065     // start the area of this cut
00066     aArea = pNode->Switching;
00067     if ( pCut->nLeaves == 1 )
00068         return aArea;
00069     // go through the children
00070     for ( i = 0; i < pCut->nLeaves; i++ )
00071     {
00072         pNodeChild = pCut->ppLeaves[i];
00073         assert( pNodeChild->nRefs >= 0 );
00074         if ( pNodeChild->nRefs++ > 0 )  
00075             continue;
00076         aArea += Fpga_CutRefSwitch( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts );
00077     }
00078     return aArea;
00079 }

void Fpga_CutRemoveFanouts ( Fpga_Man_t *  p,
Fpga_Node_t *  pNode,
Fpga_Cut_t *  pCut 
)
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 }

static Fpga_FloatEqual ( Fpga_Man_t *  p,
float  Arg1,
float  Arg2 
) [inline, static]

Definition at line 283 of file fpgaInt.h.

00283 { return Arg1 > Arg2 - p->fEpsilon && Arg1 < Arg2 + p->fEpsilon; }

static Fpga_FloatLessThan ( Fpga_Man_t *  p,
float  Arg1,
float  Arg2 
) [inline, static]

Definition at line 282 of file fpgaInt.h.

00282 { return Arg1 < Arg2 - p->fEpsilon; }

static Fpga_FloatMoreThan ( Fpga_Man_t *  p,
float  Arg1,
float  Arg2 
) [inline, static]

Definition at line 281 of file fpgaInt.h.

00281 { return Arg1 > Arg2 + p->fEpsilon; }

Fpga_LutLib_t* Fpga_LutLibCreate ( char *  FileName,
int  fVerbose 
)

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

Synopsis [Reads the description of LUTs from the LUT library file.]

Description []

SideEffects []

SeeAlso []

Definition at line 55 of file fpgaLib.c.

00056 {
00057     char pBuffer[1000], * pToken;
00058     Fpga_LutLib_t * p;
00059     FILE * pFile;
00060     int i, k;
00061 
00062     pFile = fopen( FileName, "r" );
00063     if ( pFile == NULL )
00064     {
00065         printf( "Cannot open LUT library file \"%s\".\n", FileName );
00066         return NULL;
00067     }
00068 
00069     p = ALLOC( Fpga_LutLib_t, 1 );
00070     memset( p, 0, sizeof(Fpga_LutLib_t) );
00071     p->pName = Extra_UtilStrsav( FileName );
00072 
00073     i = 1;
00074     while ( fgets( pBuffer, 1000, pFile ) != NULL )
00075     {
00076         pToken = strtok( pBuffer, " \t\n" );
00077         if ( pToken == NULL )
00078             continue;
00079         if ( pToken[0] == '#' )
00080             continue;
00081         if ( i != atoi(pToken) )
00082         {
00083             printf( "Error in the LUT library file \"%s\".\n", FileName );
00084             free( p );
00085             return NULL;
00086         }
00087 
00088         // read area
00089         pToken = strtok( NULL, " \t\n" );
00090         p->pLutAreas[i] = (float)atof(pToken);
00091 
00092         // read delays
00093         k = 0;
00094         while ( pToken = strtok( NULL, " \t\n" ) )
00095             p->pLutDelays[i][k++] = (float)atof(pToken);
00096 
00097         // check for out-of-bound
00098         if ( k > i )
00099         {
00100             printf( "LUT %d has too many pins (%d). Max allowed is %d.\n", i, k, i );
00101             return NULL;
00102         }
00103 
00104         // check if var delays are specifies
00105         if ( k > 1 )
00106             p->fVarPinDelays = 1;
00107 
00108         if ( i == FPGA_MAX_LUTSIZE )
00109         {
00110             printf( "Skipping LUTs of size more than %d.\n", i );
00111             return NULL;
00112         }
00113         i++;
00114     }
00115     p->LutMax = i-1;
00116     if ( p->LutMax > FPGA_MAX_LEAVES )
00117     {
00118         p->LutMax = FPGA_MAX_LEAVES;
00119         printf( "Warning: LUTs with more than %d input will not be used.\n", FPGA_MAX_LEAVES );
00120     }
00121 
00122     // check the library
00123     if ( p->fVarPinDelays )
00124     {
00125         for ( i = 1; i <= p->LutMax; i++ )
00126             for ( k = 0; k < i; k++ )
00127             {
00128                 if ( p->pLutDelays[i][k] <= 0.0 )
00129                     printf( "Warning: Pin %d of LUT %d has delay %f. Pin delays should be non-negative numbers. Technology mapping may not work correctly.\n", 
00130                         k, i, p->pLutDelays[i][k] );
00131                 if ( k && p->pLutDelays[i][k-1] > p->pLutDelays[i][k] )
00132                     printf( "Warning: Pin %d of LUT %d has delay %f. Pin %d of LUT %d has delay %f. Pin delays should be in non-decreasing order. Technology mapping may not work correctly.\n", 
00133                         k-1, i, p->pLutDelays[i][k-1], 
00134                         k, i, p->pLutDelays[i][k] );
00135             }
00136     }
00137     else
00138     {
00139         for ( i = 1; i <= p->LutMax; i++ )
00140         {
00141             if ( p->pLutDelays[i][0] <= 0.0 )
00142                 printf( "Warning: LUT %d has delay %f. Pin delays should be non-negative numbers. Technology mapping may not work correctly.\n", 
00143                     k, i, p->pLutDelays[i][0] );
00144         }
00145     }
00146 
00147     return p;
00148 }

int Fpga_LutLibDelaysAreDiscrete ( Fpga_LutLib_t *  pLutLib  ) 

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

Synopsis [Returns 1 if the delays are discrete.]

Description []

SideEffects []

SeeAlso []

Definition at line 232 of file fpgaLib.c.

00233 {
00234     float Delay;
00235     int i;
00236     for ( i = 1; i <= pLutLib->LutMax; i++ )
00237     {
00238         Delay = pLutLib->pLutDelays[i][0];
00239         if ( ((float)((int)Delay)) != Delay )
00240             return 0;
00241     }
00242     return 1;
00243 }

void Fpga_LutLibFree ( Fpga_LutLib_t *  pLutLib  ) 

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

Synopsis [Frees the LUT library.]

Description []

SideEffects []

SeeAlso []

Definition at line 181 of file fpgaLib.c.

00182 {
00183     if ( pLutLib == NULL )
00184         return;
00185     FREE( pLutLib->pName );
00186     FREE( pLutLib );
00187 }

void Fpga_LutLibPrint ( Fpga_LutLib_t *  pLutLib  ) 

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

Synopsis [Prints the LUT library.]

Description []

SideEffects []

SeeAlso []

Definition at line 201 of file fpgaLib.c.

00202 {
00203     int i, k;
00204     printf( "# The area/delay of k-variable LUTs:\n" );
00205     printf( "# k    area     delay\n" );
00206     if ( pLutLib->fVarPinDelays )
00207     {
00208         for ( i = 1; i <= pLutLib->LutMax; i++ )
00209         {
00210             printf( "%d   %7.2f  ", i, pLutLib->pLutAreas[i] );
00211             for ( k = 0; k < i; k++ )
00212                 printf( " %7.2f", pLutLib->pLutDelays[i][k] );
00213             printf( "\n" );
00214         }
00215     }
00216     else
00217         for ( i = 1; i <= pLutLib->LutMax; i++ )
00218             printf( "%d   %7.2f   %7.2f\n", i, pLutLib->pLutAreas[i], pLutLib->pLutDelays[i][0] );
00219 }

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_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 }

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  ) 

GLOBAL VARIABLES /// FUNCTION DEFINITIONS ///

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 }

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 }

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 }

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 }

float Fpga_MappingGetSwitching ( Fpga_Man_t *  pMan,
Fpga_NodeVec_t *  vMapping 
)

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

Synopsis [Computes the array of mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 124 of file fpgaSwitch.c.

00125 {
00126     Fpga_Node_t * pNode;
00127     float Switch;
00128     int i;
00129     Switch = 0.0;
00130     for ( i = 0; i < vMapping->nSize; i++ )
00131     {
00132         pNode = vMapping->pArray[i];
00133         // at least one phase has the best cut assigned
00134         assert( !Fpga_NodeIsAnd(pNode) || pNode->pCutBest != NULL );
00135         // at least one phase is used in the mapping
00136         assert( pNode->nRefs > 0 );
00137         // compute the array due to the supergate
00138         Switch += pNode->Switching;
00139     }
00140     // add buffer for each CO driven by a CI
00141     for ( i = 0; i < pMan->nOutputs; i++ )
00142         if ( Fpga_NodeIsVar(pMan->pOutputs[i]) && !Fpga_IsComplement(pMan->pOutputs[i]) )
00143             Switch += pMan->pOutputs[i]->Switching;
00144     return Switch;
00145 }

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_MappingMatches ( Fpga_Man_t *  p,
int  fDelayOriented 
)

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

Synopsis [Finds the best delay assignment of LUTs.]

Description [This procedure iterates through all the nodes of the object graph reachable from the POs and assigns the best match to each of them. If the flag fDelayOriented is set to 1, it tries to minimize the arrival time and uses the area flow as a tie-breaker. If the flag is set to 0, it considers all the cuts, whose arrival times matches the required time at the node, and minimizes the area flow using the arrival time as a tie-breaker.

Before this procedure is called, the required times should be set and the fanout counts should be computed. In the first iteration, the required times are set to very large number (by NodeCreate) and the fanout counts are set to the number of fanouts in the AIG. In the following iterations, the required times are set by the backward traversal, while the fanouts are estimated approximately.

If the arrival times of the PI nodes are given, they should be assigned to the PIs after the cuts are computed and before this procedure is called for the first time.]

SideEffects []

SeeAlso []

Definition at line 64 of file fpgaMatch.c.

00065 {
00066     ProgressBar * pProgress;
00067     Fpga_Node_t * pNode;
00068     int i, nNodes;
00069     
00070     // assign the arrival times of the PIs
00071     for ( i = 0; i < p->nInputs; i++ )
00072         p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];
00073 
00074     // match LUTs with nodes in the topological order
00075     nNodes = p->vAnds->nSize;
00076     pProgress = Extra_ProgressBarStart( stdout, nNodes );
00077     for ( i = 0; i < nNodes; i++ )
00078     {
00079         pNode = p->vAnds->pArray[i];
00080         if ( !Fpga_NodeIsAnd( pNode ) )
00081             continue;
00082         // skip a secondary node
00083         if ( pNode->pRepr )
00084             continue;
00085         // match the node
00086         Fpga_MatchNode( p, pNode, fDelayOriented );
00087         Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
00088     }
00089     Extra_ProgressBarStop( pProgress );
00090 /*
00091     if ( !fDelayOriented )
00092     {
00093         float Area = 0.0;
00094         for ( i = 0; i < p->nOutputs; i++ )
00095         {
00096             printf( "%5.2f ", Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow );
00097             Area += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow;
00098         }
00099         printf( "\nTotal = %5.2f\n", Area );
00100     }
00101 */
00102     return 1;
00103 }

int Fpga_MappingMatchesArea ( Fpga_Man_t *  p  ) 

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

Synopsis [Finds the best area assignment of LUTs.]

Description []

SideEffects []

SeeAlso []

Definition at line 193 of file fpgaMatch.c.

00194 {
00195     ProgressBar * pProgress;
00196     Fpga_Node_t * pNode;
00197     int i, nNodes;
00198     
00199     // assign the arrival times of the PIs
00200     for ( i = 0; i < p->nInputs; i++ )
00201         p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];
00202 
00203     // match LUTs with nodes in the topological order
00204     nNodes = p->vAnds->nSize;
00205     pProgress = Extra_ProgressBarStart( stdout, nNodes );
00206     for ( i = 0; i < nNodes; i++ )
00207     {
00208         pNode = p->vAnds->pArray[i];
00209         if ( !Fpga_NodeIsAnd( pNode ) )
00210             continue;
00211         // skip a secondary node
00212         if ( pNode->pRepr )
00213             continue;
00214         // match the node
00215         Fpga_MatchNodeArea( p, pNode );
00216         Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
00217     }
00218     Extra_ProgressBarStop( pProgress );
00219     return 1;
00220 }

int Fpga_MappingMatchesSwitch ( Fpga_Man_t *  p  ) 

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

Synopsis [Finds the best area assignment of LUTs.]

Description []

SideEffects []

SeeAlso []

Definition at line 346 of file fpgaMatch.c.

00347 {
00348     ProgressBar * pProgress;
00349     Fpga_Node_t * pNode;
00350     int i, nNodes;
00351     
00352     // assign the arrival times of the PIs
00353     for ( i = 0; i < p->nInputs; i++ )
00354         p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];
00355 
00356     // match LUTs with nodes in the topological order
00357     nNodes = p->vAnds->nSize;
00358     pProgress = Extra_ProgressBarStart( stdout, nNodes );
00359     for ( i = 0; i < nNodes; i++ )
00360     {
00361         pNode = p->vAnds->pArray[i];
00362         if ( !Fpga_NodeIsAnd( pNode ) )
00363             continue;
00364         // skip a secondary node
00365         if ( pNode->pRepr )
00366             continue;
00367         // match the node
00368         Fpga_MatchNodeSwitch( p, pNode );
00369         Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
00370     }
00371     Extra_ProgressBarStop( pProgress );
00372     return 1;
00373 }

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 }

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 }

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_MappingShow ( Fpga_Man_t *  pMan,
char *  pFileName 
)
void Fpga_MappingShowNodes ( Fpga_Man_t *  pMan,
Fpga_Node_t **  ppRoots,
int  nRoots,
char *  pFileName 
)
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 }

void Fpga_NodeAddFaninFanout ( Fpga_Node_t *  pFanin,
Fpga_Node_t *  pFanout 
)
int Fpga_NodeGetFanoutNum ( Fpga_Node_t *  pNode  ) 
void Fpga_NodeRemoveFaninFanout ( Fpga_Node_t *  pFanin,
Fpga_Node_t *  pFanoutToRemove 
)
Fpga_NodeVec_t* Fpga_NodeVecAlloc ( int  nCap  ) 

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

Synopsis [Allocates a vector with the given capacity.]

Description []

SideEffects []

SeeAlso []

Definition at line 42 of file fpgaVec.c.

00043 {
00044     Fpga_NodeVec_t * p;
00045     p = ALLOC( Fpga_NodeVec_t, 1 );
00046     if ( nCap > 0 && nCap < 16 )
00047         nCap = 16;
00048     p->nSize  = 0;
00049     p->nCap   = nCap;
00050     p->pArray = p->nCap? ALLOC( Fpga_Node_t *, p->nCap ) : NULL;
00051     return p;
00052 }

void Fpga_NodeVecClear ( Fpga_NodeVec_t *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 150 of file fpgaVec.c.

00151 {
00152     p->nSize = 0;
00153 }

void Fpga_NodeVecFree ( Fpga_NodeVec_t *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 65 of file fpgaVec.c.

00066 {
00067     FREE( p->pArray );
00068     FREE( p );
00069 }

void Fpga_NodeVecGrow ( Fpga_NodeVec_t *  p,
int  nCapMin 
)

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

Synopsis [Resizes the vector to the given capacity.]

Description []

SideEffects []

SeeAlso []

Definition at line 114 of file fpgaVec.c.

00115 {
00116     if ( p->nCap >= nCapMin )
00117         return;
00118     p->pArray = REALLOC( Fpga_Node_t *, p->pArray, nCapMin ); 
00119     p->nCap   = nCapMin;
00120 }

Fpga_Node_t* Fpga_NodeVecPop ( Fpga_NodeVec_t *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 210 of file fpgaVec.c.

00211 {
00212     return p->pArray[--p->nSize];
00213 }

void Fpga_NodeVecPush ( Fpga_NodeVec_t *  p,
Fpga_Node_t *  Entry 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 166 of file fpgaVec.c.

00167 {
00168     if ( p->nSize == p->nCap )
00169     {
00170         if ( p->nCap < 16 )
00171             Fpga_NodeVecGrow( p, 16 );
00172         else
00173             Fpga_NodeVecGrow( p, 2 * p->nCap );
00174     }
00175     p->pArray[p->nSize++] = Entry;
00176 }

void Fpga_NodeVecPushOrder ( Fpga_NodeVec_t *  vNodes,
Fpga_Node_t *  pNode,
int  fIncreasing 
)

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

Synopsis [Inserts a new node in the order by arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 363 of file fpgaVec.c.

00364 {
00365     Fpga_Node_t * pNode1, * pNode2;
00366     int i;
00367     Fpga_NodeVecPush( vNodes, pNode );
00368     // find the place of the node
00369     for ( i = vNodes->nSize-1; i > 0; i-- )
00370     {
00371         pNode1 = vNodes->pArray[i  ];
00372         pNode2 = vNodes->pArray[i-1];
00373         if ( fIncreasing && pNode1->pCutBest->tArrival >= pNode2->pCutBest->tArrival ||
00374             !fIncreasing && pNode1->pCutBest->tArrival <= pNode2->pCutBest->tArrival )
00375             break;
00376         vNodes->pArray[i  ] = pNode2;
00377         vNodes->pArray[i-1] = pNode1;
00378     }
00379 }

int Fpga_NodeVecPushUnique ( Fpga_NodeVec_t *  p,
Fpga_Node_t *  Entry 
)

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

Synopsis [Add the element while ensuring uniqueness.]

Description [Returns 1 if the element was found, and 0 if it was new. ]

SideEffects []

SeeAlso []

Definition at line 189 of file fpgaVec.c.

00190 {
00191     int i;
00192     for ( i = 0; i < p->nSize; i++ )
00193         if ( p->pArray[i] == Entry )
00194             return 1;
00195     Fpga_NodeVecPush( p, Entry );
00196     return 0;
00197 }

Fpga_Node_t** Fpga_NodeVecReadArray ( Fpga_NodeVec_t *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 82 of file fpgaVec.c.

00083 {
00084     return p->pArray;
00085 }

Fpga_Node_t* Fpga_NodeVecReadEntry ( Fpga_NodeVec_t *  p,
int  i 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 243 of file fpgaVec.c.

00244 {
00245     assert( i >= 0 && i < p->nSize );
00246     return p->pArray[i];
00247 }

int Fpga_NodeVecReadSize ( Fpga_NodeVec_t *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 98 of file fpgaVec.c.

00099 {
00100     return p->nSize;
00101 }

void Fpga_NodeVecReverse ( Fpga_NodeVec_t *  vNodes  ) 

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

Synopsis [Inserts a new node in the order by arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 392 of file fpgaVec.c.

00393 {
00394     Fpga_Node_t * pNode1, * pNode2;
00395     int i;
00396     for ( i = 0; i < vNodes->nSize/2; i++ )
00397     {
00398         pNode1 = vNodes->pArray[i];
00399         pNode2 = vNodes->pArray[vNodes->nSize-1-i];
00400         vNodes->pArray[i]                 = pNode2;
00401         vNodes->pArray[vNodes->nSize-1-i] = pNode1;
00402     }
00403 }

void Fpga_NodeVecShrink ( Fpga_NodeVec_t *  p,
int  nSizeNew 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 133 of file fpgaVec.c.

00134 {
00135     assert( p->nSize >= nSizeNew );
00136     p->nSize = nSizeNew;
00137 }

void Fpga_NodeVecSortByLevel ( Fpga_NodeVec_t *  p  ) 

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

Synopsis [Sorting the entries by their integer value.]

Description []

SideEffects []

SeeAlso []

Definition at line 286 of file fpgaVec.c.

00287 {
00288     qsort( (void *)p->pArray, p->nSize, sizeof(Fpga_Node_t *), 
00289             (int (*)(const void *, const void *)) Fpga_NodeVecCompareLevels );
00290 }

void Fpga_NodeVecUnion ( Fpga_NodeVec_t *  p,
Fpga_NodeVec_t *  p1,
Fpga_NodeVec_t *  p2 
)

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

Synopsis [Computes the union of nodes in two arrays.]

Description []

SideEffects []

SeeAlso []

Definition at line 342 of file fpgaVec.c.

00343 {
00344     int i;
00345     Fpga_NodeVecClear( p );
00346     for ( i = 0; i < p1->nSize; i++ )
00347         Fpga_NodeVecPush( p, p1->pArray[i] );
00348     for ( i = 0; i < p2->nSize; i++ )
00349         Fpga_NodeVecPush( p, p2->pArray[i] );
00350 }

void Fpga_NodeVecWriteEntry ( Fpga_NodeVec_t *  p,
int  i,
Fpga_Node_t *  Entry 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 226 of file fpgaVec.c.

00227 {
00228     assert( i >= 0 && i < p->nSize );
00229     p->pArray[i] = Entry;
00230 }

void Fpga_SortNodesByArrivalTimes ( Fpga_NodeVec_t *  p  ) 

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

Synopsis [Orders the nodes in the increasing order of the arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 323 of file fpgaVec.c.

00324 {
00325     qsort( (void *)p->pArray, p->nSize, sizeof(Fpga_Node_t *), 
00326             (int (*)(const void *, const void *)) Fpga_NodeVecCompareArrivals );
00327 //    assert( Fpga_CompareNodesByLevel( p->pArray, p->pArray + p->nSize - 1 ) <= 0 );
00328 }

float Fpga_TimeComputeArrivalMax ( Fpga_Man_t *  p  ) 

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

Synopsis [Computes the maximum arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 86 of file fpgaTime.c.

00087 {
00088     float fRequired;
00089     int i;
00090     if ( p->fLatchPaths && p->nLatches == 0 )
00091     {
00092         printf( "Delay optimization of latch path is not performed because there is no latches.\n" );
00093         p->fLatchPaths = 0;
00094     }
00095     // get the critical PO arrival time
00096     fRequired = -FPGA_FLOAT_LARGE;
00097     if ( p->fLatchPaths )
00098     {
00099         for ( i = p->nOutputs - p->nLatches; i < p->nOutputs; i++ )
00100         {
00101             if ( Fpga_NodeIsConst(p->pOutputs[i]) )
00102                 continue;
00103             fRequired = FPGA_MAX( fRequired, Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival );
00104 //            printf( " %5.1f", Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival );
00105         }
00106 //        printf( "Required latches = %5.1f\n", fRequired );
00107     }
00108     else
00109     {
00110         for ( i = 0; i < p->nOutputs; i++ )
00111         {
00112             if ( Fpga_NodeIsConst(p->pOutputs[i]) )
00113                 continue;
00114             fRequired = FPGA_MAX( fRequired, Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival );
00115 //            printf( " %5.1f", Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival );
00116         }
00117 //        printf( "Required outputs = %5.1f\n", fRequired );
00118     }
00119     return fRequired;
00120 }

void Fpga_TimeComputeRequired ( Fpga_Man_t *  p,
float  fRequired 
)

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

Synopsis [Computes the required times of all nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 165 of file fpgaTime.c.

00166 {
00167     int i;
00168     // clean the required times and the fanout counts for all nodes
00169     for ( i = 0; i < p->vAnds->nSize; i++ )
00170         p->vAnds->pArray[i]->tRequired = FPGA_FLOAT_LARGE;
00171     // set the required times for the POs
00172     if ( p->fLatchPaths )
00173         for ( i = p->nOutputs - p->nLatches; i < p->nOutputs; i++ )
00174             Fpga_Regular(p->pOutputs[i])->tRequired = fRequired;
00175     else
00176         for ( i = 0; i < p->nOutputs; i++ )
00177             Fpga_Regular(p->pOutputs[i])->tRequired = fRequired;
00178     // collect nodes reachable from POs in the DFS order through the best cuts
00179     Fpga_TimePropagateRequired( p, p->vMapping );
00180 /*
00181     {
00182         int Counter = 0;
00183         for ( i = 0; i < p->vAnds->nSize; i++ )
00184             if ( p->vAnds->pArray[i]->tRequired > FPGA_FLOAT_LARGE - 100 )
00185                 Counter++;
00186         printf( "The number of nodes with large required times = %d.\n", Counter );
00187     }
00188 */
00189 }

void Fpga_TimeComputeRequiredGlobal ( Fpga_Man_t *  p,
int  fFirstTime 
)

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

Synopsis [Computes the required times of all nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 133 of file fpgaTime.c.

00134 {
00135     p->fRequiredGlo = Fpga_TimeComputeArrivalMax( p );
00136     // update the required times according to the target
00137     if ( p->DelayTarget != -1 )
00138     {
00139         if ( p->fRequiredGlo > p->DelayTarget + p->fEpsilon )
00140         {
00141             if ( fFirstTime )
00142                 printf( "Cannot meet the target required times (%4.2f). Mapping continues anyway.\n", p->DelayTarget );
00143         }
00144         else if ( p->fRequiredGlo < p->DelayTarget - p->fEpsilon )
00145         {
00146             if ( fFirstTime )
00147                 printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->fRequiredGlo, p->DelayTarget );
00148             p->fRequiredGlo = p->DelayTarget;
00149         }
00150     }
00151     Fpga_TimeComputeRequired( p, p->fRequiredGlo );
00152 }

float Fpga_TimeCutComputeArrival ( Fpga_Man_t *  pMan,
Fpga_Cut_t *  pCut 
)

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

FileName [fpgaTime.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
fpgaTime.c,v 1.1 2005/01/23 06:59:42 alanmi Exp

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

Synopsis [Computes the arrival times of the cut.]

Description [Computes the maximum arrival time of the cut leaves and adds the delay of the LUT.]

SideEffects []

SeeAlso []

Definition at line 41 of file fpgaTime.c.

00042 {
00043     int i;
00044     float tArrival;
00045     tArrival = -FPGA_FLOAT_LARGE;
00046     for ( i = 0; i < pCut->nLeaves; i++ )
00047         if ( tArrival < pCut->ppLeaves[i]->pCutBest->tArrival )
00048             tArrival = pCut->ppLeaves[i]->pCutBest->tArrival;
00049     tArrival += pMan->pLutLib->pLutDelays[pCut->nLeaves][0];
00050     return tArrival;
00051 }

float Fpga_TimeCutComputeArrival_rec ( Fpga_Man_t *  pMan,
Fpga_Cut_t *  pCut 
)

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

Synopsis [Computes the arrival times of the cut recursively.]

Description [When computing the arrival time for the previously unused cuts, their arrival time may be incorrect because their fanins have incorrect arrival time. This procedure is called to fix this problem.]

SideEffects []

SeeAlso []

Definition at line 66 of file fpgaTime.c.

00067 {
00068     int i;
00069     for ( i = 0; i < pCut->nLeaves; i++ )
00070         if ( pCut->ppLeaves[i]->nRefs == 0 )
00071             Fpga_TimeCutComputeArrival_rec( pMan, pCut->ppLeaves[i]->pCutBest );
00072     return Fpga_TimeCutComputeArrival( pMan, pCut );
00073 }

void Fpga_TimePropagateArrival ( Fpga_Man_t *  p  ) 

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

Synopsis [Computes the required times of all nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 242 of file fpgaTime.c.

00243 {
00244     Fpga_Node_t * pNode;
00245     Fpga_Cut_t * pCut;
00246     int i;
00247 
00248     // clean the required times and the fanout counts for all nodes
00249     for ( i = 0; i < p->vAnds->nSize; i++ )
00250     {
00251         pNode = p->vAnds->pArray[i];
00252         for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
00253             pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut );
00254     }
00255 }

void Fpga_TimePropagateRequired ( Fpga_Man_t *  p,
Fpga_NodeVec_t *  vNodes 
)

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

Synopsis [Computes the required times of the given nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 202 of file fpgaTime.c.

00203 {
00204     Fpga_Node_t * pNode, * pChild;
00205     float fRequired;
00206     int i, k;
00207 
00208     // sorts the nodes in the decreasing order of levels
00209 //    Fpga_MappingSortByLevel( p, vNodes, 0 );
00210     // the nodes area already sorted in Fpga_MappingSetRefsAndArea()
00211 
00212     // go through the nodes in the reverse topological order
00213     for ( k = 0; k < vNodes->nSize; k++ )
00214     {
00215         pNode = vNodes->pArray[k];
00216         if ( !Fpga_NodeIsAnd(pNode) )
00217             continue;
00218         // get the required time for children
00219         fRequired = pNode->tRequired - p->pLutLib->pLutDelays[pNode->pCutBest->nLeaves][0];
00220         // update the required time of the children
00221         for ( i = 0; i < pNode->pCutBest->nLeaves; i++ )
00222         {
00223             pChild = pNode->pCutBest->ppLeaves[i];
00224             pChild->tRequired = FPGA_MIN( pChild->tRequired, fRequired );
00225         }
00226     }
00227 }

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