diff options
Diffstat (limited to 'src/map/fpga/fpgaInt.h')
| -rw-r--r-- | src/map/fpga/fpgaInt.h | 395 |
1 files changed, 395 insertions, 0 deletions
diff --git a/src/map/fpga/fpgaInt.h b/src/map/fpga/fpgaInt.h new file mode 100644 index 00000000..0fea9ec8 --- /dev/null +++ b/src/map/fpga/fpgaInt.h @@ -0,0 +1,395 @@ +/**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 <stdio.h> +#include <stdlib.h> +#include <string.h> +#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 |