| /**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 $] |
| |
| ***********************************************************************/ |
| |
| #ifndef ABC__map__fpga__fpgaInt_h |
| #define ABC__map__fpga__fpgaInt_h |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// INCLUDES /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <string.h> |
| #include "misc/extra/extra.h" |
| #include "fpga.h" |
| |
| ABC_NAMESPACE_HEADER_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// PARAMETERS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| // uncomment to have fanouts represented in the mapping graph |
| //#define FPGA_ALLOCATE_FANOUT 1 |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// MACRO DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| #ifdef _WIN32 |
| #define inline __inline // compatible with MS VS 6.0 |
| #endif |
| |
| // the maximum number of cut leaves (currently does not work for 7) |
| #define FPGA_MAX_LEAVES 6 |
| |
| // the bit masks |
| #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) |
| |
| // maximum/minimum operators |
| #define FPGA_MIN(a,b) (((a) < (b))? (a) : (b)) |
| #define FPGA_MAX(a,b) (((a) > (b))? (a) : (b)) |
| |
| // the small and large numbers (min/max float are 1.17e-38/3.40e+38) |
| #define FPGA_FLOAT_LARGE ((float)1.0e+20) |
| #define FPGA_FLOAT_SMALL ((float)1.0e-20) |
| #define FPGA_INT_LARGE (10000000) |
| |
| // the macro to compute the signature |
| #define FPGA_SEQ_SIGN(p) (1 << (((ABC_PTRUINT_T)p)%31)); |
| |
| // internal macros to work with cuts |
| #define Fpga_CutIsComplement(p) (((int)((ABC_PTRUINT_T)(p) & 01))) |
| #define Fpga_CutRegular(p) ((Fpga_Cut_t *)((ABC_PTRUINT_T)(p) & ~01)) |
| #define Fpga_CutNot(p) ((Fpga_Cut_t *)((ABC_PTRUINT_T)(p) ^ 01)) |
| #define Fpga_CutNotCond(p,c) ((Fpga_Cut_t *)((ABC_PTRUINT_T)(p) ^ (c))) |
| |
| // the cut nodes |
| #define Fpga_SeqIsComplement( p ) (((int)((ABC_PTRUINT_T) (p) & 01))) |
| #define Fpga_SeqRegular( p ) ((Fpga_Node_t *)((ABC_PTRUINT_T)(p) & ~015)) |
| #define Fpga_SeqIndex( p ) ((((ABC_PTRUINT_T)(p)) >> 1) & 07) |
| #define Fpga_SeqIndexCreate( p, Ind ) (((ABC_PTRUINT_T)(p)) | (1 << (((ABC_PTRUINT_T)(Ind)) & 07))) |
| |
| // internal macros for referencing of nodes |
| #define Fpga_NodeReadRef(p) ((Fpga_Regular(p))->nRefs) |
| #define Fpga_NodeRef(p) ((Fpga_Regular(p))->nRefs++) |
| |
| // returns the complemented attribute of the node |
| #define Fpga_NodeIsSimComplement(p) (Fpga_IsComplement(p)? !(Fpga_Regular(p)->fInv) : (p)->fInv) |
| |
| // generating random unsigned (#define RAND_MAX 0x7fff) |
| #define FPGA_RANDOM_UNSIGNED ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand())) |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// STRUCTURE DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| // the mapping manager |
| struct Fpga_ManStruct_t_ |
| { |
| // the mapping graph |
| Fpga_Node_t ** pBins; // the table of nodes hashed by their children |
| int nBins; // the size of the table |
| Fpga_Node_t ** pInputs; // the array of inputs |
| int nInputs; // the number of inputs |
| Fpga_Node_t ** pOutputs; // the array of outputs |
| int nOutputs; // the number of outputs |
| int nNodes; // the total number of nodes |
| int nLatches; // the number of latches in the circuit |
| Fpga_Node_t * pConst1; // the constant 1 node |
| Fpga_NodeVec_t * vNodesAll; // the nodes by number |
| Fpga_NodeVec_t * vAnds; // the nodes reachable from COs |
| Fpga_NodeVec_t * vMapping; // the nodes used in the current mapping |
| |
| // info about the original circuit |
| char * pFileName; // the file name |
| char ** ppOutputNames; // the primary output names |
| float * pInputArrivals;// the PI arrival times |
| |
| // mapping parameters |
| int nVarsMax; // the max number of variables |
| int fAreaRecovery; // the flag to use area flow as the first parameter |
| int fVerbose; // the verbosiness flag |
| int fSwitching; // minimize the switching activity (instead of area) |
| int fLatchPaths; // optimize latch paths for delay, other paths for area |
| int nTravIds; // the counter of traversal IDs |
| float DelayTarget; // the target required times |
| |
| // support of choice nodes |
| int nChoiceNodes; // the number of choice nodes |
| int nChoices; // the number of all choices |
| |
| int nCanons; |
| int nMatches; |
| |
| // the supergate library |
| Fpga_LutLib_t * pLutLib; // the current LUT library |
| |
| // the memory managers |
| Extra_MmFixed_t * mmNodes; // the memory manager for nodes |
| Extra_MmFixed_t * mmCuts; // the memory manager for cuts |
| |
| // resynthesis parameters |
| int fResynthesis; // the resynthesis flag |
| float fRequiredGlo; // the global required times |
| float fRequiredShift;// the shift of the required times |
| float fRequiredStart;// the starting global required times |
| float fRequiredGain; // the reduction in delay |
| float fAreaGlo; // the total area |
| float fAreaGain; // the reduction in area |
| float fEpsilon; // the epsilon used to compare floats |
| float fDelayWindow; // the delay window for delay-oriented resynthesis |
| float DelayLimit; // for resynthesis |
| float AreaLimit; // for resynthesis |
| float TimeLimit; // for resynthesis |
| |
| // runtime statistics |
| clock_t timeToMap; // time to transfer to the mapping structure |
| clock_t timeCuts; // time to compute k-feasible cuts |
| clock_t timeTruth; // time to compute the truth table for each cut |
| clock_t timeMatch; // time to perform matching for each node |
| clock_t timeRecover; // time to perform area recovery |
| clock_t timeToNet; // time to transfer back to the network |
| clock_t timeTotal; // the total mapping time |
| clock_t time1; // time to transfer to the mapping structure |
| clock_t time2; // time to transfer to the mapping structure |
| }; |
| |
| // the LUT library |
| struct Fpga_LutLibStruct_t_ |
| { |
| char * pName; // the name of the LUT library |
| int LutMax; // the maximum LUT size |
| int fVarPinDelays; // set to 1 if variable pin delays are specified |
| float pLutAreas[FPGA_MAX_LUTSIZE+1]; // the areas of LUTs |
| float pLutDelays[FPGA_MAX_LUTSIZE+1][FPGA_MAX_LUTSIZE+1];// the delays of LUTs |
| }; |
| |
| // the mapping node |
| struct Fpga_NodeStruct_t_ |
| { |
| // general information about the node |
| Fpga_Node_t * pNext; // the next node in the hash table |
| Fpga_Node_t * pLevel; // the next node in the linked list by level |
| int Num; // the unique number of this node |
| int NumA; // the unique number of this node |
| int Num2; // the temporary number of this node |
| int nRefs; // the number of references (fanouts) of the given node |
| unsigned fMark0 : 1; // the mark used for traversals |
| unsigned fMark1 : 1; // the mark used for traversals |
| unsigned fInv : 1; // the complemented attribute for the equivalent nodes |
| unsigned Value : 2; // the value of the nodes |
| unsigned fUsed : 1; // the flag indicating that the node is used in the mapping |
| unsigned fTemp : 1; // unused |
| unsigned Level :11; // the level of the given node |
| unsigned uData :14; // used to mark the fanins, for which resynthesis was tried |
| int TravId; |
| |
| // the successors of this node |
| Fpga_Node_t * p1; // the first child |
| Fpga_Node_t * p2; // the second child |
| Fpga_Node_t * pNextE; // the next functionally equivalent node |
| Fpga_Node_t * pRepr; // the representative of the functionally equivalent class |
| |
| #ifdef FPGA_ALLOCATE_FANOUT |
| // representation of node's fanouts |
| Fpga_Node_t * pFanPivot; // the first fanout of this node |
| Fpga_Node_t * pFanFanin1; // the next fanout of p1 |
| Fpga_Node_t * pFanFanin2; // the next fanout of p2 |
| // Fpga_NodeVec_t * vFanouts; // the array of fanouts of the gate |
| #endif |
| |
| // the delay information |
| float tRequired; // the best area flow |
| float aEstFanouts; // the fanout estimation |
| float Switching; // the probability of switching |
| int LValue; // the l-value of the node |
| short nLatches1; // the number of latches on the first edge |
| short nLatches2; // the number of latches on the second edge |
| |
| // cut information |
| Fpga_Cut_t * pCutBest; // the best mapping |
| Fpga_Cut_t * pCutOld; // the old mapping |
| Fpga_Cut_t * pCuts; // mapping choices for the node (elementary comes first) |
| Fpga_Cut_t * pCutsN; // mapping choices for the node (elementary comes first) |
| |
| // misc information |
| char * pData0; // temporary storage for the corresponding network node |
| }; |
| |
| // the cuts used for matching |
| struct Fpga_CutStruct_t_ |
| { |
| Fpga_Cut_t * pOne; // the father of this cut |
| Fpga_Cut_t * pTwo; // the mother of this cut |
| Fpga_Node_t * pRoot; // the root of the cut |
| Fpga_Node_t * ppLeaves[FPGA_MAX_LEAVES+1]; // the leaves of this cut |
| float fLevel; // the average level of the fanins |
| unsigned uSign; // signature for quick comparison |
| char fMark; // the mark to denote visited cut |
| char Phase; // the mark to denote complemented cut |
| char nLeaves; // the number of leaves of this cut |
| char nVolume; // the volume of this cut |
| float tArrival; // the arrival time |
| float aFlow; // the area flow of the cut |
| Fpga_Cut_t * pNext; // the pointer to the next cut in the list |
| }; |
| |
| // the vector of nodes |
| struct Fpga_NodeVecStruct_t_ |
| { |
| Fpga_Node_t ** pArray; // the array of nodes |
| int nSize; // the number of entries in the array |
| int nCap; // the number of allocated entries |
| }; |
| |
| // getting hold of the next fanout of the node |
| #define Fpga_NodeReadNextFanout( pNode, pFanout ) \ |
| ( ( pFanout == NULL )? NULL : \ |
| ((Fpga_Regular((pFanout)->p1) == (pNode))? \ |
| (pFanout)->pFanFanin1 : (pFanout)->pFanFanin2) ) |
| |
| // getting hold of the place where the next fanout will be attached |
| #define Fpga_NodeReadNextFanoutPlace( pNode, pFanout ) \ |
| ( (Fpga_Regular((pFanout)->p1) == (pNode))? \ |
| &(pFanout)->pFanFanin1 : &(pFanout)->pFanFanin2 ) |
| |
| // iterator through the fanouts of the node |
| #define Fpga_NodeForEachFanout( pNode, pFanout ) \ |
| for ( pFanout = (pNode)->pFanPivot; pFanout; \ |
| pFanout = Fpga_NodeReadNextFanout(pNode, pFanout) ) |
| |
| // safe iterator through the fanouts of the node |
| #define Fpga_NodeForEachFanoutSafe( pNode, pFanout, pFanout2 ) \ |
| for ( pFanout = (pNode)->pFanPivot, \ |
| pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout); \ |
| pFanout; \ |
| pFanout = pFanout2, \ |
| pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout) ) |
| |
| static inline int Fpga_FloatMoreThan( Fpga_Man_t * p, float Arg1, float Arg2 ) { return Arg1 > Arg2 + p->fEpsilon; } |
| static inline int Fpga_FloatLessThan( Fpga_Man_t * p, float Arg1, float Arg2 ) { return Arg1 < Arg2 - p->fEpsilon; } |
| static inline int Fpga_FloatEqual( Fpga_Man_t * p, float Arg1, float Arg2 ) { return Arg1 > Arg2 - p->fEpsilon && Arg1 < Arg2 + p->fEpsilon; } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// GLOBAL VARIABLES /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /*=== fpgaCut.c ===============================================================*/ |
| extern void Fpga_MappingCuts( Fpga_Man_t * p ); |
| extern void Fpga_MappingCreatePiCuts( Fpga_Man_t * p ); |
| extern int Fpga_CutCountAll( Fpga_Man_t * pMan ); |
| /*=== fpgaCutUtils.c ===============================================================*/ |
| extern Fpga_Cut_t * Fpga_CutAlloc( Fpga_Man_t * p ); |
| extern Fpga_Cut_t * Fpga_CutDup( Fpga_Man_t * p, Fpga_Cut_t * pCutOld ); |
| extern void Fpga_CutFree( Fpga_Man_t * p, Fpga_Cut_t * pCut ); |
| extern void Fpga_CutPrint( Fpga_Man_t * p, Fpga_Node_t * pRoot, Fpga_Cut_t * pCut ); |
| extern Fpga_Cut_t * Fpga_CutCreateSimple( Fpga_Man_t * p, Fpga_Node_t * pNode ); |
| extern float Fpga_CutGetRootArea( Fpga_Man_t * p, Fpga_Cut_t * pCut ); |
| extern Fpga_Cut_t * Fpga_CutListAppend( Fpga_Cut_t * pSetAll, Fpga_Cut_t * pSets ); |
| extern void Fpga_CutListRecycle( Fpga_Man_t * p, Fpga_Cut_t * pSetList, Fpga_Cut_t * pSave ); |
| extern int Fpga_CutListCount( Fpga_Cut_t * pSets ); |
| extern void Fpga_CutRemoveFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ); |
| extern void Fpga_CutInsertFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ); |
| extern float Fpga_CutGetAreaRefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); |
| extern float Fpga_CutGetAreaDerefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); |
| extern float Fpga_CutRef( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); |
| extern float Fpga_CutDeref( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); |
| extern float Fpga_CutGetAreaFlow( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); |
| extern void Fpga_CutGetParameters( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); |
| /*=== fraigFanout.c =============================================================*/ |
| extern void Fpga_NodeAddFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanout ); |
| extern void Fpga_NodeRemoveFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanoutToRemove ); |
| extern int Fpga_NodeGetFanoutNum( Fpga_Node_t * pNode ); |
| /*=== fpgaLib.c ============================================================*/ |
| extern Fpga_LutLib_t * Fpga_LutLibRead( char * FileName, int fVerbose ); |
| extern void Fpga_LutLibFree( Fpga_LutLib_t * p ); |
| extern void Fpga_LutLibPrint( Fpga_LutLib_t * pLutLib ); |
| extern int Fpga_LutLibDelaysAreDiscrete( Fpga_LutLib_t * pLutLib ); |
| /*=== fpgaMatch.c ===============================================================*/ |
| extern int Fpga_MappingMatches( Fpga_Man_t * p, int fDelayOriented ); |
| extern int Fpga_MappingMatchesArea( Fpga_Man_t * p ); |
| extern int Fpga_MappingMatchesSwitch( Fpga_Man_t * p ); |
| /*=== fpgaShow.c =============================================================*/ |
| extern void Fpga_MappingShow( Fpga_Man_t * pMan, char * pFileName ); |
| extern void Fpga_MappingShowNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppRoots, int nRoots, char * pFileName ); |
| /*=== fpgaSwitch.c =============================================================*/ |
| extern float Fpga_CutGetSwitchDerefed( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ); |
| extern float Fpga_CutRefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); |
| extern float Fpga_CutDerefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); |
| extern float Fpga_MappingGetSwitching( Fpga_Man_t * pMan, Fpga_NodeVec_t * vMapping ); |
| /*=== fpgaTime.c ===============================================================*/ |
| extern float Fpga_TimeCutComputeArrival( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); |
| extern float Fpga_TimeCutComputeArrival_rec( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); |
| extern float Fpga_TimeComputeArrivalMax( Fpga_Man_t * p ); |
| extern void Fpga_TimeComputeRequiredGlobal( Fpga_Man_t * p, int fFirstTime ); |
| extern void Fpga_TimeComputeRequired( Fpga_Man_t * p, float fRequired ); |
| extern void Fpga_TimePropagateRequired( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ); |
| extern void Fpga_TimePropagateArrival( Fpga_Man_t * p ); |
| /*=== fpgaVec.c =============================================================*/ |
| extern Fpga_NodeVec_t * Fpga_NodeVecAlloc( int nCap ); |
| extern void Fpga_NodeVecFree( Fpga_NodeVec_t * p ); |
| extern Fpga_Node_t ** Fpga_NodeVecReadArray( Fpga_NodeVec_t * p ); |
| extern int Fpga_NodeVecReadSize( Fpga_NodeVec_t * p ); |
| extern void Fpga_NodeVecGrow( Fpga_NodeVec_t * p, int nCapMin ); |
| extern void Fpga_NodeVecShrink( Fpga_NodeVec_t * p, int nSizeNew ); |
| extern void Fpga_NodeVecClear( Fpga_NodeVec_t * p ); |
| extern void Fpga_NodeVecPush( Fpga_NodeVec_t * p, Fpga_Node_t * Entry ); |
| extern int Fpga_NodeVecPushUnique( Fpga_NodeVec_t * p, Fpga_Node_t * Entry ); |
| extern Fpga_Node_t * Fpga_NodeVecPop( Fpga_NodeVec_t * p ); |
| extern void Fpga_NodeVecWriteEntry( Fpga_NodeVec_t * p, int i, Fpga_Node_t * Entry ); |
| extern Fpga_Node_t * Fpga_NodeVecReadEntry( Fpga_NodeVec_t * p, int i ); |
| extern void Fpga_NodeVecSortByLevel( Fpga_NodeVec_t * p ); |
| extern void Fpga_SortNodesByArrivalTimes( Fpga_NodeVec_t * p ); |
| extern void Fpga_NodeVecUnion( Fpga_NodeVec_t * p, Fpga_NodeVec_t * p1, Fpga_NodeVec_t * p2 ); |
| extern void Fpga_NodeVecPushOrder( Fpga_NodeVec_t * vNodes, Fpga_Node_t * pNode, int fIncreasing ); |
| extern void Fpga_NodeVecReverse( Fpga_NodeVec_t * vNodes ); |
| |
| /*=== fpgaUtils.c ===============================================================*/ |
| extern Fpga_NodeVec_t * Fpga_MappingDfs( Fpga_Man_t * pMan, int fCollectEquiv ); |
| extern Fpga_NodeVec_t * Fpga_MappingDfsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes, int fEquiv ); |
| extern int Fpga_CountLevels( Fpga_Man_t * pMan ); |
| extern float Fpga_MappingGetAreaFlow( Fpga_Man_t * p ); |
| extern float Fpga_MappingArea( Fpga_Man_t * pMan ); |
| extern float Fpga_MappingAreaTrav( Fpga_Man_t * pMan ); |
| extern float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ); |
| extern void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p ); |
| extern void Fpga_MappingSetupTruthTables( unsigned uTruths[][2] ); |
| extern void Fpga_MappingSetupMask( unsigned uMask[], int nVarsMax ); |
| extern void Fpga_MappingSortByLevel( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes, int fIncreasing ); |
| extern Fpga_NodeVec_t * Fpga_DfsLim( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int nLevels ); |
| extern Fpga_NodeVec_t * Fpga_MappingLevelize( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes ); |
| extern int Fpga_MappingMaxLevel( Fpga_Man_t * pMan ); |
| extern void Fpga_ManReportChoices( Fpga_Man_t * pMan ); |
| extern void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan ); |
| |
| |
| |
| ABC_NAMESPACE_HEADER_END |
| |
| #endif |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
