summaryrefslogtreecommitdiffstats
path: root/src/map/fpga/fpgaInt.h
blob: 0d18b7f4f5fa1330155fc4477ccbe95a44fce67a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
/**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                                ///
////////////////////////////////////////////////////////////////////////