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
390
391
392
393
394
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
|
