/**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 __FPGA_INT_H__ #define __FPGA_INT_H__ //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// //#include "leaks.h" #include #include #include #include "extra.h" #include "fraig.h" #include "fpga.h" //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// /// MACRO DEFITIONS /// //////////////////////////////////////////////////////////////////////// #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 << (((unsigned)p)%31)); // internal macros to work with cuts #define Fpga_CutIsComplement(p) (((int)((long) (p) & 01))) #define Fpga_CutRegular(p) ((Fpga_Cut_t *)((unsigned)(p) & ~01)) #define Fpga_CutNot(p) ((Fpga_Cut_t *)((long)(p) ^ 01)) #define Fpga_CutNotCond(p,c) ((Fpga_Cut_t *)((long)(p) ^ (c))) // the cut nodes #define Fpga_SeqIsComplement( p ) (((int)((long) (p) & 01))) #define Fpga_SeqRegular( p ) ((Fpga_Node_t *)((unsigned)(p) & ~015)) #define Fpga_SeqIndex( p ) ((((unsigned)(p)) >> 1) & 07) #define Fpga_SeqIndexCreate( p, Ind ) (((unsigned)(p)) | (1 << (((unsigned)(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())) // outputs the runtime in seconds #define PRT(a,t) printf("%s = ", (a)); printf("%6.2f sec\n", (float)(t)/(float)(CLOCKS_PER_SEC)) //////////////////////////////////////////////////////////////////////// /// 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 Fpga_Node_t * pConst1; // the constant 1 node Fpga_NodeVec_t * vAnds; // the array of pointer to nodes by number Fpga_NodeVec_t * vNodesAll; // the array of pointer to nodes by number int nLatches; // the number of latches in the circuit // 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 fTree; // the flag to enable tree mapping int fPower; // the flag to enable power optimization int fAreaRecovery; // the flag to use area flow as the first parameter int fVerbose; // the verbosiness flag int fRefCount; // enables reference counting int fSequential; // use sequential mapping int nTravIds; // 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 unsigned uTruths[6][2]; // the elementary truth tables // the memory managers Extra_MmFixed_t * mmNodes; // the memory manager for nodes Extra_MmFixed_t * mmCuts; // the memory manager for cuts // simulation info from the FRAIG manager int nSimRounds; // the number of words in the simulation info unsigned ** pSimInfo; // the simulation info for each PI // 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 int timeToMap; // time to transfer to the mapping structure int timeCuts; // time to compute k-feasible cuts int timeTruth; // time to compute the truth table for each cut int timeMatch; // time to perform matching for each node int timeRecover; // time to perform area recovery int timeToNet; // time to transfer back to the network int timeTotal; // the total mapping time int time1; // time to transfer to the mapping structure int 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 float pLutAreas[FPGA_MAX_LUTSIZE+1]; // the areas of LUTs float pLutDelays[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 short Num2; // the temporary number of this node short 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 // Fpga_NodeVec_t * vFanouts; // the array of fanouts of the node // 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 // the delay information float tRequired; // the best area flow float aEstFanouts; // the fanout estimation float SwitchProb; // 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) ) //////////////////////////////////////////////////////////////////////// /// GLOBAL VARIABLES /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /*=== 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_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_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_LutLibCreate( 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 ); /*=== 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 ); extern void Fpga_TimeComputeRequired( Fpga_Man_t * p, float fRequired ); extern void Fpga_TimePropagateRequired( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ); /*=== fpgaTruth.c ===============================================================*/ extern void Fpga_MappingTruths( Fpga_Man_t * pMan ); /*=== 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 Fpga_NodeVec_t * Fpga_MappingDfsCutsNode( Fpga_Man_t * pMan, Fpga_Node_t * pNode ); //extern Sat_IntVec_t * Fpga_MappingDfsNodesSat( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes ); extern Fpga_NodeVec_t * Fpga_MappingDfsCuts( Fpga_Man_t * pMan ); extern int Fpga_CountLevels( Fpga_Man_t * pMan ); extern int Fpga_CountLevelsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppRoots, int nRoots ); extern void Fpga_MappingMarkUsed( Fpga_Man_t * pMan ); extern float Fpga_MappingGetAreaFlow( Fpga_Man_t * p ); extern float Fpga_MappingArea( Fpga_Man_t * pMan ); extern float Fpga_MappingComputeCutAreas( Fpga_Man_t * pMan ); extern float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ); extern int Fpga_MappingCountLevels( Fpga_Man_t * pMan ); extern void Fpga_MappingUnmark( Fpga_Man_t * pMan ); extern void Fpga_MappingUnmark_rec( Fpga_Node_t * pNode ); extern void Fpga_MappingMark_rec( Fpga_Node_t * pNode ); extern void Fpga_MappedMark_rec( Fpga_Node_t * pNode ); extern void Fpga_MappedUnmark_rec( Fpga_Node_t * pNode ); 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 float Fpga_MappingPrintSwitching( Fpga_Man_t * pMan ); extern int Fpga_GetMaxLevel( Fpga_Man_t * pMan ); extern void Fpga_ManReportChoices( Fpga_Man_t * pMan ); extern void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan ); /*=== CUDD package.c ===============================================================*/ extern unsigned int Cudd_Prime( unsigned int p ); //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// #endif