1 /**CFile****************************************************************
2
3 FileName [abcIfif.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Network and node package.]
8
9 Synopsis [Experiment with technology mapping.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: abcIfif.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "base/abc/abc.h"
22 #include "map/if/if.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 #define IFIF_MAX_LEAVES 6
31
32
33 typedef struct Abc_IffObj_t_ Abc_IffObj_t;
34 struct Abc_IffObj_t_
35 {
36 float Delay[IFIF_MAX_LEAVES+1]; // separate delay
37 // int nLeaves;
38 // int pLeaves[IFIF_MAX_LEAVES];
39 };
40
41 typedef struct Abc_IffMan_t_ Abc_IffMan_t;
42 struct Abc_IffMan_t_
43 {
44 Abc_Ntk_t * pNtk;
45 Ifif_Par_t * pPars;
46 // internal data
47 int nObjs;
48 Abc_IffObj_t * pObjs;
49 };
50
Abc_IffObj(Abc_IffMan_t * p,int i)51 static inline Abc_IffObj_t * Abc_IffObj( Abc_IffMan_t * p, int i ) { assert( i >= 0 && i < p->nObjs ); return p->pObjs + i; }
Abc_IffDelay(Abc_IffMan_t * p,Abc_Obj_t * pObj,int fDelay1)52 static inline float Abc_IffDelay( Abc_IffMan_t * p, Abc_Obj_t * pObj, int fDelay1 ) { return Abc_IffObj(p, Abc_ObjId(pObj))->Delay[fDelay1]; }
53
54 ////////////////////////////////////////////////////////////////////////
55 /// FUNCTION DEFINITIONS ///
56 ////////////////////////////////////////////////////////////////////////
57
58 /**Function*************************************************************
59
60 Synopsis []
61
62 Description []
63
64 SideEffects []
65
66 SeeAlso []
67
68 ***********************************************************************/
Abc_NtkIfifStart(Abc_Ntk_t * pNtk,Ifif_Par_t * pPars)69 Abc_IffMan_t * Abc_NtkIfifStart( Abc_Ntk_t * pNtk, Ifif_Par_t * pPars )
70 {
71 Abc_IffMan_t * p;
72 p = ABC_CALLOC( Abc_IffMan_t, 1 );
73 p->pNtk = pNtk;
74 p->pPars = pPars;
75 // internal data
76 p->nObjs = Abc_NtkObjNumMax( pNtk );
77 p->pObjs = ABC_CALLOC( Abc_IffObj_t, p->nObjs );
78 return p;
79 }
Abc_NtkIfifStop(Abc_IffMan_t * p)80 void Abc_NtkIfifStop( Abc_IffMan_t * p )
81 {
82 // internal data
83 ABC_FREE( p->pObjs );
84 ABC_FREE( p );
85 }
86
87 /**Function*************************************************************
88
89 Synopsis [Collects fanins into ppNodes in decreasing order.]
90
91 Description []
92
93 SideEffects []
94
95 SeeAlso []
96
97 ***********************************************************************/
Abc_ObjSortByDelay(Abc_IffMan_t * p,Abc_Obj_t * pObj,int fDelay1,Abc_Obj_t ** ppNodes)98 void Abc_ObjSortByDelay( Abc_IffMan_t * p, Abc_Obj_t * pObj, int fDelay1, Abc_Obj_t ** ppNodes )
99 {
100 Abc_Obj_t * pFanin;
101 int i, a, k = 0;
102 Abc_ObjForEachFanin( pObj, pFanin, i )
103 {
104 ppNodes[k++] = pFanin;
105 if ( Abc_ObjIsCi(pFanin) )
106 continue;
107 for ( a = k-1; a > 0; a-- )
108 if ( Abc_IffDelay(p, ppNodes[a-1], fDelay1) + p->pPars->pLutDelays[a-1] < Abc_IffDelay(p, ppNodes[a], fDelay1) + p->pPars->pLutDelays[a] )
109 ABC_SWAP( Abc_Obj_t *, ppNodes[a-1], ppNodes[a] );
110 }
111 /*
112 for ( a = 1; a < k; a++ )
113 {
114 float D1 = Abc_IffDelay(p, ppNodes[a-1], fDelay1);
115 float D2 = Abc_IffDelay(p, ppNodes[a], fDelay1);
116 if ( Abc_ObjIsCi(ppNodes[a-1]) || Abc_ObjIsCi(ppNodes[a]) )
117 continue;
118 assert( Abc_IffDelay(p, ppNodes[a-1], fDelay1) + p->pPars->pLutDelays[a-1] >= Abc_IffDelay(p, ppNodes[a], fDelay1) + p->pPars->pLutDelays[a] - 0.01 );
119 }
120 */
121 }
122
123 /**Function*************************************************************
124
125 Synopsis [This is the delay which object has all by itself.]
126
127 Description [This delay is stored in Delay0.]
128
129 SideEffects []
130
131 SeeAlso []
132
133 ***********************************************************************/
Abc_ObjDelay0(Abc_IffMan_t * p,Abc_Obj_t * pObj)134 float Abc_ObjDelay0( Abc_IffMan_t * p, Abc_Obj_t * pObj )
135 {
136 int i;
137 float Delay0 = 0;
138 Abc_Obj_t * ppNodes[6];
139 Abc_ObjSortByDelay( p, pObj, 1, ppNodes );
140 for ( i = 0; i < Abc_ObjFaninNum(pObj); i++ )
141 Delay0 = Abc_MaxFloat( Delay0, Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i] );
142 return Delay0;
143 }
144
145 /**Function*************************************************************
146
147 Synopsis [This is the delay object has in the structure.]
148
149 Description [This delay is stored in Delay1.]
150
151 SideEffects []
152
153 SeeAlso []
154
155 ***********************************************************************/
Abc_ObjDelay1(Abc_IffMan_t * p,Abc_Obj_t * pObj)156 float Abc_ObjDelay1( Abc_IffMan_t * p, Abc_Obj_t * pObj )
157 {
158 int i, fVeryVerbose = 0;
159 // Abc_IffObj_t * pIfif = Abc_IffObj( p, Abc_ObjId(pObj) );
160 Abc_Obj_t * ppNodes[6];
161 float Delay1, DelayNew;
162
163 if ( Abc_ObjFaninNum(pObj) == 0 )
164 return 0;
165
166 // sort fanins by delay1+LutDelay
167 Abc_ObjSortByDelay( p, pObj, 1, ppNodes );
168
169 // print verbose results
170 if ( fVeryVerbose )
171 {
172 printf( "Object %d Level %d\n", Abc_ObjId(pObj), Abc_ObjLevel(pObj) );
173 for ( i = 0; i < Abc_ObjFaninNum(pObj); i++ )
174 {
175 printf( "Fanin %d : ", i );
176 printf( "D0 %3.2f ", Abc_IffDelay(p, ppNodes[i], 0) );
177 printf( "D0* %3.2f ", Abc_IffDelay(p, ppNodes[i], 0) + p->pPars->pLutDelays[i] - p->pPars->DelayWire );
178 printf( "D1 %3.2f", Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i] );
179 printf( "\n" );
180 }
181 printf( "\n" );
182 }
183 /*
184 // for the first nDegree delays, sort them by the minimum Delay1+LutDelay and Delay0-Wire+LutDelay
185 Delay1 = 0;
186 pIfif->nLeaves = 0;
187 for ( i = 0; i < Abc_ObjFaninNum(pObj); i++ )
188 {
189 if ( Abc_ObjIsNode(ppNodes[i]) && pIfif->nLeaves < p->pPars->nDegree )
190 {
191 DelayNew = Abc_MinFloat( Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i],
192 Abc_IffDelay(p, ppNodes[i], 0) + p->pPars->pLutDelays[i] - p->pPars->DelayWire );
193 pIfif->pLeaves[pIfif->nLeaves++] = Abc_ObjId(ppNodes[i]);
194 }
195 else
196 DelayNew = Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i];
197 Delay1 = Abc_MaxFloat( Delay1, DelayNew );
198 }
199 */
200 // for the first nDegree delays, sort them by the minimum Delay1+LutDelay and Delay0-Wire+LutDelay
201 Delay1 = 0;
202 for ( i = 0; i < Abc_ObjFaninNum(pObj); i++ )
203 {
204 if ( i < p->pPars->nDegree )
205 DelayNew = Abc_MinFloat( Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i],
206 Abc_IffDelay(p, ppNodes[i], 0) + p->pPars->pLutDelays[i] - p->pPars->DelayWire );
207 else
208 DelayNew = Abc_IffDelay(p, ppNodes[i], 1) + p->pPars->pLutDelays[i];
209 Delay1 = Abc_MaxFloat( Delay1, DelayNew );
210 }
211 assert( Delay1 > 0 );
212 return Delay1;
213 }
214
215
216 /**Function*************************************************************
217
218 Synopsis [This is the delay which object has all by itself.]
219
220 Description [This delay is stored in Delay0.]
221
222 SideEffects []
223
224 SeeAlso []
225
226 ***********************************************************************/
Abc_ObjDelayDegree(Abc_IffMan_t * p,Abc_Obj_t * pObj,int d)227 float Abc_ObjDelayDegree( Abc_IffMan_t * p, Abc_Obj_t * pObj, int d )
228 {
229 int i;
230 float Delay0 = 0, DelayNew;
231 Abc_Obj_t * ppNodes[6];
232 assert( d >= 0 && d <= p->pPars->nDegree );
233 Abc_ObjSortByDelay( p, pObj, p->pPars->nDegree, ppNodes );
234 for ( i = 0; i < Abc_ObjFaninNum(pObj); i++ )
235 {
236 DelayNew = Abc_IffDelay(p, ppNodes[i], p->pPars->nDegree) + p->pPars->pLutDelays[i];
237 if ( i == 0 && d > 0 )
238 DelayNew = Abc_MinFloat(DelayNew, Abc_IffDelay(p, ppNodes[i], d-1) + p->pPars->pLutDelays[i] - p->pPars->DelayWire );
239 Delay0 = Abc_MaxFloat( Delay0, DelayNew );
240 }
241 return Delay0;
242 }
243
244 /**Function*************************************************************
245
246 Synopsis []
247
248 Description []
249
250 SideEffects []
251
252 SeeAlso []
253
254 ***********************************************************************/
Abc_NtkPerformIfif(Abc_Ntk_t * pNtk,Ifif_Par_t * pPars)255 void Abc_NtkPerformIfif( Abc_Ntk_t * pNtk, Ifif_Par_t * pPars )
256 {
257 Abc_IffMan_t * p;
258 Abc_IffObj_t * pIffObj;
259 Vec_Ptr_t * vNodes;
260 Abc_Obj_t * pObj;
261 float Delay, Delay10, DegreeFinal;
262 int i, d, Count10;
263 assert( pPars->pLutLib->LutMax >= 0 && pPars->pLutLib->LutMax <= IFIF_MAX_LEAVES );
264 assert( pPars->nLutSize >= 0 && pPars->nLutSize <= IFIF_MAX_LEAVES );
265 assert( pPars->nDegree >= 0 && pPars->nDegree <= IFIF_MAX_LEAVES );
266 // convert to AIGs
267 Abc_NtkToAig( pNtk );
268 Abc_NtkLevel( pNtk );
269
270 // print parameters
271 if ( pPars->fVerbose )
272 {
273 printf( "Running mapper into LUT structures with the following parameters:\n" );
274 printf( "Pin+Wire: {" );
275 for ( i = 0; i < pPars->pLutLib->LutMax; i++ )
276 printf( " %3.2f", pPars->pLutDelays[i] );
277 printf( " } " );
278 printf( "Wire %3.2f Degree %d Type: %s\n",
279 pPars->DelayWire, pPars->nDegree, pPars->fCascade? "Cascade" : "Cluster" );
280 }
281
282 // start manager
283 p = Abc_NtkIfifStart( pNtk, pPars );
284 // printf( "Running experiment with LUT delay %d and degree %d (LUT size is %d).\n", DelayWire, nDegree, nLutSize );
285
286 // compute the delay
287 vNodes = Abc_NtkDfs( pNtk, 0 );
288 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
289 {
290 assert( Abc_ObjIsNode(pObj) );
291 pIffObj = Abc_IffObj( p, Abc_ObjId(pObj) );
292
293 if ( pPars->fCascade )
294 {
295 for ( d = 0; d <= pPars->nDegree; d++ )
296 pIffObj->Delay[d] = Abc_ObjDelayDegree( p, pObj, d );
297 }
298 else
299 {
300 pIffObj->Delay[0] = Abc_ObjDelay0( p, pObj );
301 pIffObj->Delay[1] = Abc_ObjDelay1( p, pObj );
302 }
303 }
304
305 // get final degree number
306 if ( pPars->fCascade )
307 DegreeFinal = pPars->nDegree;
308 else
309 DegreeFinal = 1;
310
311 if ( p->pPars->fVeryVerbose )
312 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
313 {
314 printf( "Node %3d : Lev =%3d ", Abc_ObjId(pObj), Abc_ObjLevel(pObj) );
315 for ( d = 0; d <= DegreeFinal; d++ )
316 printf( "Del%d =%4.2f ", d, Abc_IffDelay(p, pObj, d) );
317 printf( "\n" );
318 }
319 Vec_PtrFree( vNodes );
320
321
322 // consider delay at the outputs
323 Delay = 0;
324 Abc_NtkForEachCo( pNtk, pObj, i )
325 Delay = Abc_MaxFloat( Delay, Abc_IffDelay(p, Abc_ObjFanin0(pObj), DegreeFinal) );
326 Delay10 = 0.9 * Delay;
327
328 // consider delay at the outputs
329 Count10 = 0;
330 Abc_NtkForEachCo( pNtk, pObj, i )
331 if ( Abc_IffDelay(p, Abc_ObjFanin0(pObj), DegreeFinal) >= Delay10 )
332 Count10++;
333
334 printf( "Critical delay %5.2f. Critical outputs %5.2f %%\n", Delay, 100.0 * Count10 / Abc_NtkCoNum(pNtk) );
335 // printf( "%.2f %.2f\n", Delay, 100.0 * Count10 / Abc_NtkCoNum(pNtk) );
336
337 // derive a new network
338
339 // stop manager
340 Abc_NtkIfifStop( p );
341 }
342
343 ////////////////////////////////////////////////////////////////////////
344 /// END OF FILE ///
345 ////////////////////////////////////////////////////////////////////////
346
347
348 ABC_NAMESPACE_IMPL_END
349
350