1 /**CFile****************************************************************
2
3 FileName [abcSpeedup.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Network and node package.]
8
9 Synopsis [Delay trace and speedup.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: abcSpeedup.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "base/abc/abc.h"
22 #include "base/main/main.h"
23 #include "map/if/if.h"
24 #include "aig/aig/aig.h"
25
26 ABC_NAMESPACE_IMPL_START
27
28
29 ////////////////////////////////////////////////////////////////////////
30 /// DECLARATIONS ///
31 ////////////////////////////////////////////////////////////////////////
32
Abc_ObjArrival(Abc_Obj_t * pNode)33 static inline float Abc_ObjArrival( Abc_Obj_t * pNode ) { return pNode->pNtk->pLutTimes[3*pNode->Id+0]; }
Abc_ObjRequired(Abc_Obj_t * pNode)34 static inline float Abc_ObjRequired( Abc_Obj_t * pNode ) { return pNode->pNtk->pLutTimes[3*pNode->Id+1]; }
Abc_ObjSlack(Abc_Obj_t * pNode)35 static inline float Abc_ObjSlack( Abc_Obj_t * pNode ) { return pNode->pNtk->pLutTimes[3*pNode->Id+2]; }
36
Abc_ObjSetArrival(Abc_Obj_t * pNode,float Time)37 static inline void Abc_ObjSetArrival( Abc_Obj_t * pNode, float Time ) { pNode->pNtk->pLutTimes[3*pNode->Id+0] = Time; }
Abc_ObjSetRequired(Abc_Obj_t * pNode,float Time)38 static inline void Abc_ObjSetRequired( Abc_Obj_t * pNode, float Time ) { pNode->pNtk->pLutTimes[3*pNode->Id+1] = Time; }
Abc_ObjSetSlack(Abc_Obj_t * pNode,float Time)39 static inline void Abc_ObjSetSlack( Abc_Obj_t * pNode, float Time ) { pNode->pNtk->pLutTimes[3*pNode->Id+2] = Time; }
40
41 ////////////////////////////////////////////////////////////////////////
42 /// FUNCTION DEFINITIONS ///
43 ////////////////////////////////////////////////////////////////////////
44
45 /**Function*************************************************************
46
47 Synopsis [Sorts the pins in the decreasing order of delays.]
48
49 Description []
50
51 SideEffects []
52
53 SeeAlso []
54
55 ***********************************************************************/
Abc_NtkDelayTraceSortPins(Abc_Obj_t * pNode,int * pPinPerm,float * pPinDelays)56 void Abc_NtkDelayTraceSortPins( Abc_Obj_t * pNode, int * pPinPerm, float * pPinDelays )
57 {
58 Abc_Obj_t * pFanin;
59 int i, j, best_i, temp;
60 // start the trivial permutation and collect pin delays
61 Abc_ObjForEachFanin( pNode, pFanin, i )
62 {
63 pPinPerm[i] = i;
64 pPinDelays[i] = Abc_ObjArrival(pFanin);
65 }
66 // selection sort the pins in the decreasible order of delays
67 // this order will match the increasing order of LUT input pins
68 for ( i = 0; i < Abc_ObjFaninNum(pNode)-1; i++ )
69 {
70 best_i = i;
71 for ( j = i+1; j < Abc_ObjFaninNum(pNode); j++ )
72 if ( pPinDelays[pPinPerm[j]] > pPinDelays[pPinPerm[best_i]] )
73 best_i = j;
74 if ( best_i == i )
75 continue;
76 temp = pPinPerm[i];
77 pPinPerm[i] = pPinPerm[best_i];
78 pPinPerm[best_i] = temp;
79 }
80 // verify
81 assert( Abc_ObjFaninNum(pNode) == 0 || pPinPerm[0] < Abc_ObjFaninNum(pNode) );
82 for ( i = 1; i < Abc_ObjFaninNum(pNode); i++ )
83 {
84 assert( pPinPerm[i] < Abc_ObjFaninNum(pNode) );
85 assert( pPinDelays[pPinPerm[i-1]] >= pPinDelays[pPinPerm[i]] );
86 }
87 }
88
89 /**Function*************************************************************
90
91 Synopsis []
92
93 Description []
94
95 SideEffects []
96
97 SeeAlso []
98
99 ***********************************************************************/
Abc_NtkDelayTraceLut(Abc_Ntk_t * pNtk,int fUseLutLib)100 float Abc_NtkDelayTraceLut( Abc_Ntk_t * pNtk, int fUseLutLib )
101 {
102 int fUseSorting = 1;
103 int pPinPerm[32];
104 float pPinDelays[32];
105 If_LibLut_t * pLutLib;
106 Abc_Obj_t * pNode, * pFanin;
107 Vec_Ptr_t * vNodes;
108 float tArrival, tRequired, tSlack, * pDelays;
109 int i, k;
110
111 assert( Abc_NtkIsLogic(pNtk) );
112 // get the library
113 pLutLib = fUseLutLib? (If_LibLut_t *)Abc_FrameReadLibLut() : NULL;
114 if ( pLutLib && pLutLib->LutMax < Abc_NtkGetFaninMax(pNtk) )
115 {
116 printf( "The max LUT size (%d) is less than the max fanin count (%d).\n",
117 pLutLib->LutMax, Abc_NtkGetFaninMax(pNtk) );
118 return -ABC_INFINITY;
119 }
120
121 // initialize the arrival times
122 ABC_FREE( pNtk->pLutTimes );
123 pNtk->pLutTimes = ABC_ALLOC( float, 3 * Abc_NtkObjNumMax(pNtk) );
124 for ( i = 0; i < Abc_NtkObjNumMax(pNtk); i++ )
125 {
126 pNtk->pLutTimes[3*i+0] = pNtk->pLutTimes[3*i+2] = 0;
127 pNtk->pLutTimes[3*i+1] = ABC_INFINITY;
128 }
129
130 // propagate arrival times
131 vNodes = Abc_NtkDfs( pNtk, 1 );
132 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
133 {
134 tArrival = -ABC_INFINITY;
135 if ( pLutLib == NULL )
136 {
137 Abc_ObjForEachFanin( pNode, pFanin, k )
138 if ( tArrival < Abc_ObjArrival(pFanin) + 1.0 )
139 tArrival = Abc_ObjArrival(pFanin) + 1.0;
140 }
141 else if ( !pLutLib->fVarPinDelays )
142 {
143 pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
144 Abc_ObjForEachFanin( pNode, pFanin, k )
145 if ( tArrival < Abc_ObjArrival(pFanin) + pDelays[0] )
146 tArrival = Abc_ObjArrival(pFanin) + pDelays[0];
147 }
148 else
149 {
150 pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
151 if ( fUseSorting )
152 {
153 Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
154 Abc_ObjForEachFanin( pNode, pFanin, k )
155 if ( tArrival < Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] )
156 tArrival = Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k];
157 }
158 else
159 {
160 Abc_ObjForEachFanin( pNode, pFanin, k )
161 if ( tArrival < Abc_ObjArrival(pFanin) + pDelays[k] )
162 tArrival = Abc_ObjArrival(pFanin) + pDelays[k];
163 }
164 }
165 if ( Abc_ObjFaninNum(pNode) == 0 )
166 tArrival = 0.0;
167 Abc_ObjSetArrival( pNode, tArrival );
168 }
169 Vec_PtrFree( vNodes );
170
171 // get the latest arrival times
172 tArrival = -ABC_INFINITY;
173 Abc_NtkForEachCo( pNtk, pNode, i )
174 if ( tArrival < Abc_ObjArrival(Abc_ObjFanin0(pNode)) )
175 tArrival = Abc_ObjArrival(Abc_ObjFanin0(pNode));
176
177 // initialize the required times
178 Abc_NtkForEachCo( pNtk, pNode, i )
179 if ( Abc_ObjRequired(Abc_ObjFanin0(pNode)) > tArrival )
180 Abc_ObjSetRequired( Abc_ObjFanin0(pNode), tArrival );
181
182 // propagate the required times
183 vNodes = Abc_NtkDfsReverse( pNtk );
184 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
185 {
186 if ( pLutLib == NULL )
187 {
188 tRequired = Abc_ObjRequired(pNode) - (float)1.0;
189 Abc_ObjForEachFanin( pNode, pFanin, k )
190 if ( Abc_ObjRequired(pFanin) > tRequired )
191 Abc_ObjSetRequired( pFanin, tRequired );
192 }
193 else if ( !pLutLib->fVarPinDelays )
194 {
195 pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
196 tRequired = Abc_ObjRequired(pNode) - pDelays[0];
197 Abc_ObjForEachFanin( pNode, pFanin, k )
198 if ( Abc_ObjRequired(pFanin) > tRequired )
199 Abc_ObjSetRequired( pFanin, tRequired );
200 }
201 else
202 {
203 pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
204 if ( fUseSorting )
205 {
206 Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
207 Abc_ObjForEachFanin( pNode, pFanin, k )
208 {
209 tRequired = Abc_ObjRequired(pNode) - pDelays[k];
210 if ( Abc_ObjRequired(Abc_ObjFanin(pNode,pPinPerm[k])) > tRequired )
211 Abc_ObjSetRequired( Abc_ObjFanin(pNode,pPinPerm[k]), tRequired );
212 }
213 }
214 else
215 {
216 Abc_ObjForEachFanin( pNode, pFanin, k )
217 {
218 tRequired = Abc_ObjRequired(pNode) - pDelays[k];
219 if ( Abc_ObjRequired(pFanin) > tRequired )
220 Abc_ObjSetRequired( pFanin, tRequired );
221 }
222 }
223 }
224 // set slack for this object
225 tSlack = Abc_ObjRequired(pNode) - Abc_ObjArrival(pNode);
226 assert( tSlack + 0.001 > 0.0 );
227 Abc_ObjSetSlack( pNode, tSlack < 0.0 ? 0.0 : tSlack );
228 }
229 Vec_PtrFree( vNodes );
230 return tArrival;
231 }
232
233 /**Function*************************************************************
234
235 Synopsis [Delay tracing of the LUT mapped network.]
236
237 Description []
238
239 SideEffects []
240
241 SeeAlso []
242
243 ***********************************************************************/
Abc_NtkDelayTracePrint(Abc_Ntk_t * pNtk,int fUseLutLib,int fVerbose)244 void Abc_NtkDelayTracePrint( Abc_Ntk_t * pNtk, int fUseLutLib, int fVerbose )
245 {
246 Abc_Obj_t * pNode;
247 If_LibLut_t * pLutLib;
248 int i, Nodes, * pCounters;
249 float tArrival, tDelta, nSteps, Num;
250 // get the library
251 pLutLib = fUseLutLib? (If_LibLut_t *)Abc_FrameReadLibLut() : NULL;
252 if ( pLutLib && pLutLib->LutMax < Abc_NtkGetFaninMax(pNtk) )
253 {
254 printf( "The max LUT size (%d) is less than the max fanin count (%d).\n",
255 pLutLib->LutMax, Abc_NtkGetFaninMax(pNtk) );
256 return;
257 }
258 // decide how many steps
259 nSteps = fUseLutLib ? 20 : Abc_NtkLevel(pNtk);
260 pCounters = ABC_ALLOC( int, nSteps + 1 );
261 memset( pCounters, 0, sizeof(int)*(nSteps + 1) );
262 // perform delay trace
263 tArrival = Abc_NtkDelayTraceLut( pNtk, fUseLutLib );
264 tDelta = tArrival / nSteps;
265 // count how many nodes have slack in the corresponding intervals
266 Abc_NtkForEachNode( pNtk, pNode, i )
267 {
268 if ( Abc_ObjFaninNum(pNode) == 0 )
269 continue;
270 Num = Abc_ObjSlack(pNode) / tDelta;
271 assert( Num >=0 && Num <= nSteps );
272 pCounters[(int)Num]++;
273 }
274 // print the results
275 printf( "Max delay = %6.2f. Delay trace using %s model:\n", tArrival, fUseLutLib? "LUT library" : "unit-delay" );
276 Nodes = 0;
277 for ( i = 0; i < nSteps; i++ )
278 {
279 Nodes += pCounters[i];
280 printf( "%3d %s : %5d (%6.2f %%)\n", fUseLutLib? 5*(i+1) : i+1,
281 fUseLutLib? "%":"lev", Nodes, 100.0*Nodes/Abc_NtkNodeNum(pNtk) );
282 }
283 ABC_FREE( pCounters );
284 }
285
286 /**Function*************************************************************
287
288 Synopsis [Returns 1 if pOld is in the TFI of pNew.]
289
290 Description []
291
292 SideEffects []
293
294 SeeAlso []
295
296 ***********************************************************************/
Abc_AigCheckTfi_rec(Abc_Obj_t * pNode,Abc_Obj_t * pOld)297 int Abc_AigCheckTfi_rec( Abc_Obj_t * pNode, Abc_Obj_t * pOld )
298 {
299 // check the trivial cases
300 if ( pNode == NULL )
301 return 0;
302 if ( Abc_ObjIsCi(pNode) )
303 return 0;
304 if ( pNode == pOld )
305 return 1;
306 // skip the visited node
307 if ( Abc_NodeIsTravIdCurrent( pNode ) )
308 return 0;
309 Abc_NodeSetTravIdCurrent( pNode );
310 // check the children
311 if ( Abc_AigCheckTfi_rec( Abc_ObjFanin0(pNode), pOld ) )
312 return 1;
313 if ( Abc_AigCheckTfi_rec( Abc_ObjFanin1(pNode), pOld ) )
314 return 1;
315 // check equivalent nodes
316 return Abc_AigCheckTfi_rec( (Abc_Obj_t *)pNode->pData, pOld );
317 }
318
319 /**Function*************************************************************
320
321 Synopsis [Returns 1 if pOld is in the TFI of pNew.]
322
323 Description []
324
325 SideEffects []
326
327 SeeAlso []
328
329 ***********************************************************************/
Abc_AigCheckTfi(Abc_Obj_t * pNew,Abc_Obj_t * pOld)330 int Abc_AigCheckTfi( Abc_Obj_t * pNew, Abc_Obj_t * pOld )
331 {
332 assert( !Abc_ObjIsComplement(pNew) );
333 assert( !Abc_ObjIsComplement(pOld) );
334 Abc_NtkIncrementTravId( pNew->pNtk );
335 return Abc_AigCheckTfi_rec( pNew, pOld );
336 }
337
338 /**Function*************************************************************
339
340 Synopsis [Adds strashed nodes for one node.]
341
342 Description []
343
344 SideEffects []
345
346 SeeAlso []
347
348 ***********************************************************************/
Abc_NtkSpeedupNode_rec(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)349 int Abc_NtkSpeedupNode_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
350 {
351 if ( Abc_NodeIsTravIdCurrent(pNode) )
352 return 1;
353 if ( Abc_ObjIsCi(pNode) )
354 return 0;
355 assert( Abc_ObjIsNode(pNode) );
356 Abc_NodeSetTravIdCurrent( pNode );
357 if ( !Abc_NtkSpeedupNode_rec( Abc_ObjFanin0(pNode), vNodes ) )
358 return 0;
359 if ( !Abc_NtkSpeedupNode_rec( Abc_ObjFanin1(pNode), vNodes ) )
360 return 0;
361 Vec_PtrPush( vNodes, pNode );
362 return 1;
363 }
364
365 /**Function*************************************************************
366
367 Synopsis [Adds strashed nodes for one node.]
368
369 Description []
370
371 SideEffects []
372
373 SeeAlso []
374
375 ***********************************************************************/
Abc_NtkSpeedupNode(Abc_Ntk_t * pNtk,Abc_Ntk_t * pAig,Abc_Obj_t * pNode,Vec_Ptr_t * vLeaves,Vec_Ptr_t * vTimes)376 void Abc_NtkSpeedupNode( Abc_Ntk_t * pNtk, Abc_Ntk_t * pAig, Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vTimes )
377 {
378 Vec_Ptr_t * vNodes;
379 Abc_Obj_t * pObj, * pObj2, * pAnd;
380 Abc_Obj_t * ppCofs[32];
381 int nCofs, i, k, nSkip;
382
383 // quit of regulars are the same
384 Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
385 Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj2, k )
386 if ( i != k && Abc_ObjRegular(pObj->pCopy) == Abc_ObjRegular(pObj2->pCopy) )
387 {
388 // printf( "Identical after structural hashing!!!\n" );
389 return;
390 }
391
392 // collect the AIG nodes
393 vNodes = Vec_PtrAlloc( 100 );
394 Abc_NtkIncrementTravId( pAig );
395 Abc_NodeSetTravIdCurrent( Abc_AigConst1(pAig) );
396 Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
397 {
398 pAnd = pObj->pCopy;
399 Abc_NodeSetTravIdCurrent( Abc_ObjRegular(pAnd) );
400 }
401 // traverse from the root node
402 pAnd = pNode->pCopy;
403 if ( !Abc_NtkSpeedupNode_rec( Abc_ObjRegular(pAnd), vNodes ) )
404 {
405 // printf( "Bad node!!!\n" );
406 Vec_PtrFree( vNodes );
407 return;
408 }
409
410 // derive cofactors
411 nCofs = (1 << Vec_PtrSize(vTimes));
412 for ( i = 0; i < nCofs; i++ )
413 {
414 Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, k )
415 {
416 pAnd = pObj->pCopy;
417 Abc_ObjRegular(pAnd)->pCopy = Abc_ObjRegular(pAnd);
418 }
419 Vec_PtrForEachEntry( Abc_Obj_t *, vTimes, pObj, k )
420 {
421 pAnd = pObj->pCopy;
422 Abc_ObjRegular(pAnd)->pCopy = Abc_ObjNotCond( Abc_AigConst1(pAig), ((i & (1<<k)) == 0) );
423 }
424 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, k )
425 pObj->pCopy = Abc_AigAnd( (Abc_Aig_t *)pAig->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) );
426 // save the result
427 pAnd = pNode->pCopy;
428 ppCofs[i] = Abc_ObjNotCond( Abc_ObjRegular(pAnd)->pCopy, Abc_ObjIsComplement(pAnd) );
429 }
430 Vec_PtrFree( vNodes );
431
432 //Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[0] );
433 //Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[1] );
434
435 // collect the resulting tree
436 Vec_PtrForEachEntry( Abc_Obj_t *, vTimes, pObj, k )
437 for ( nSkip = (1<<k), i = 0; i < nCofs; i += 2*nSkip )
438 {
439 pAnd = pObj->pCopy;
440 ppCofs[i] = Abc_AigMux( (Abc_Aig_t *)pAig->pManFunc, Abc_ObjRegular(pAnd), ppCofs[i+nSkip], ppCofs[i] );
441 }
442 //Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[0] );
443
444 // create choice node
445 pAnd = Abc_ObjRegular(pNode->pCopy); // repr
446 pObj = Abc_ObjRegular(ppCofs[0]); // new
447 if ( pAnd->pData == NULL && pObj->pData == NULL && !Abc_AigNodeIsConst(pObj) && !Abc_AigCheckTfi(pObj, pAnd) )
448 {
449 pObj->pData = pAnd->pData;
450 pAnd->pData = pObj;
451 }
452
453 }
454
455 /**Function*************************************************************
456
457 Synopsis [Determines timing-critical edges of the node.]
458
459 Description []
460
461 SideEffects []
462
463 SeeAlso []
464
465 ***********************************************************************/
Abc_NtkDelayTraceTCEdges(Abc_Ntk_t * pNtk,Abc_Obj_t * pNode,float tDelta,int fUseLutLib)466 unsigned Abc_NtkDelayTraceTCEdges( Abc_Ntk_t * pNtk, Abc_Obj_t * pNode, float tDelta, int fUseLutLib )
467 {
468 int pPinPerm[32];
469 float pPinDelays[32];
470 If_LibLut_t * pLutLib;
471 Abc_Obj_t * pFanin;
472 unsigned uResult = 0;
473 float tRequired, * pDelays;
474 int k;
475 pLutLib = fUseLutLib? (If_LibLut_t *)Abc_FrameReadLibLut() : NULL;
476 tRequired = Abc_ObjRequired(pNode);
477 if ( pLutLib == NULL )
478 {
479 Abc_ObjForEachFanin( pNode, pFanin, k )
480 if ( tRequired < Abc_ObjArrival(pFanin) + 1.0 + tDelta )
481 uResult |= (1 << k);
482 }
483 else if ( !pLutLib->fVarPinDelays )
484 {
485 pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
486 Abc_ObjForEachFanin( pNode, pFanin, k )
487 if ( tRequired < Abc_ObjArrival(pFanin) + pDelays[0] + tDelta )
488 uResult |= (1 << k);
489 }
490 else
491 {
492 pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
493 Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
494 Abc_ObjForEachFanin( pNode, pFanin, k )
495 if ( tRequired < Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] + tDelta )
496 uResult |= (1 << pPinPerm[k]);
497 }
498 return uResult;
499 }
500
501 /**Function*************************************************************
502
503 Synopsis [Adds choices to speed up the network by the given percentage.]
504
505 Description []
506
507 SideEffects []
508
509 SeeAlso []
510
511 ***********************************************************************/
Abc_NtkSpeedup(Abc_Ntk_t * pNtk,int fUseLutLib,int Percentage,int Degree,int fVerbose,int fVeryVerbose)512 Abc_Ntk_t * Abc_NtkSpeedup( Abc_Ntk_t * pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose )
513 {
514 Abc_Ntk_t * pNtkNew;
515 Vec_Ptr_t * vTimeCries, * vTimeFanins;
516 Abc_Obj_t * pNode, * pFanin, * pFanin2;
517 float tDelta, tArrival;
518 int i, k, k2, Counter, CounterRes, nTimeCris;
519 unsigned * puTCEdges;
520 // perform delay trace
521 tArrival = Abc_NtkDelayTraceLut( pNtk, fUseLutLib );
522 tDelta = fUseLutLib ? tArrival*Percentage/100.0 : 1.0;
523 if ( fVerbose )
524 {
525 printf( "Max delay = %.2f. Delta = %.2f. ", tArrival, tDelta );
526 printf( "Using %s model. ", fUseLutLib? "LUT library" : "unit-delay" );
527 if ( fUseLutLib )
528 printf( "Percentage = %d. ", Percentage );
529 printf( "\n" );
530 }
531 // mark the timing critical nodes and edges
532 puTCEdges = ABC_ALLOC( unsigned, Abc_NtkObjNumMax(pNtk) );
533 memset( puTCEdges, 0, sizeof(unsigned) * Abc_NtkObjNumMax(pNtk) );
534 Abc_NtkForEachNode( pNtk, pNode, i )
535 {
536 if ( Abc_ObjSlack(pNode) >= tDelta )
537 continue;
538 puTCEdges[pNode->Id] = Abc_NtkDelayTraceTCEdges( pNtk, pNode, tDelta, fUseLutLib );
539 }
540 if ( fVerbose )
541 {
542 Counter = CounterRes = 0;
543 Abc_NtkForEachNode( pNtk, pNode, i )
544 {
545 Abc_ObjForEachFanin( pNode, pFanin, k )
546 if ( !Abc_ObjIsCi(pFanin) && Abc_ObjSlack(pFanin) < tDelta )
547 Counter++;
548 CounterRes += Extra_WordCountOnes( puTCEdges[pNode->Id] );
549 }
550 printf( "Edges: Total = %7d. 0-slack = %7d. Critical = %7d. Ratio = %4.2f\n",
551 Abc_NtkGetTotalFanins(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter );
552 }
553 // start the resulting network
554 pNtkNew = Abc_NtkStrash( pNtk, 0, 1, 0 );
555
556 // collect nodes to be used for resynthesis
557 Counter = CounterRes = 0;
558 vTimeCries = Vec_PtrAlloc( 16 );
559 vTimeFanins = Vec_PtrAlloc( 16 );
560 Abc_NtkForEachNode( pNtk, pNode, i )
561 {
562 if ( Abc_ObjSlack(pNode) >= tDelta )
563 continue;
564 // count the number of non-PI timing-critical nodes
565 nTimeCris = 0;
566 Abc_ObjForEachFanin( pNode, pFanin, k )
567 if ( !Abc_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) )
568 nTimeCris++;
569 if ( !fVeryVerbose && nTimeCris == 0 )
570 continue;
571 Counter++;
572 // count the total number of timing critical second-generation nodes
573 Vec_PtrClear( vTimeCries );
574 if ( nTimeCris )
575 {
576 Abc_ObjForEachFanin( pNode, pFanin, k )
577 if ( !Abc_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) )
578 Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
579 if ( puTCEdges[pFanin->Id] & (1<<k2) )
580 Vec_PtrPushUnique( vTimeCries, pFanin2 );
581 }
582 // if ( !fVeryVerbose && (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
583 if ( (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
584 continue;
585 CounterRes++;
586 // collect second generation nodes
587 Vec_PtrClear( vTimeFanins );
588 Abc_ObjForEachFanin( pNode, pFanin, k )
589 {
590 if ( Abc_ObjIsCi(pFanin) )
591 Vec_PtrPushUnique( vTimeFanins, pFanin );
592 else
593 Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
594 Vec_PtrPushUnique( vTimeFanins, pFanin2 );
595 }
596 // print the results
597 if ( fVeryVerbose )
598 {
599 printf( "%5d Node %5d : %d %2d %2d ", Counter, pNode->Id,
600 nTimeCris, Vec_PtrSize(vTimeCries), Vec_PtrSize(vTimeFanins) );
601 Abc_ObjForEachFanin( pNode, pFanin, k )
602 printf( "%d(%.2f)%s ", pFanin->Id, Abc_ObjSlack(pFanin), (puTCEdges[pNode->Id] & (1<<k))? "*":"" );
603 printf( "\n" );
604 }
605 // add the node to choices
606 if ( Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree )
607 continue;
608 // order the fanins in the increasing order of criticalily
609 if ( Vec_PtrSize(vTimeCries) > 1 )
610 {
611 pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
612 pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
613 if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
614 {
615 Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
616 Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
617 }
618 }
619 if ( Vec_PtrSize(vTimeCries) > 2 )
620 {
621 pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
622 pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 2 );
623 if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
624 {
625 Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 );
626 Vec_PtrWriteEntry( vTimeCries, 2, pFanin );
627 }
628 pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
629 pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
630 if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
631 {
632 Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
633 Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
634 }
635 }
636 // add choice
637 Abc_NtkSpeedupNode( pNtk, pNtkNew, pNode, vTimeFanins, vTimeCries );
638 }
639 Vec_PtrFree( vTimeCries );
640 Vec_PtrFree( vTimeFanins );
641 ABC_FREE( puTCEdges );
642 if ( fVerbose )
643 printf( "Nodes: Total = %7d. 0-slack = %7d. Workable = %7d. Ratio = %4.2f\n",
644 Abc_NtkNodeNum(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter );
645
646 // remove invalid choice nodes
647 Abc_AigForEachAnd( pNtkNew, pNode, i )
648 if ( pNode->pData )
649 {
650 if ( Abc_ObjFanoutNum((Abc_Obj_t *)pNode->pData) > 0 )
651 pNode->pData = NULL;
652 }
653
654 // return the result
655 return pNtkNew;
656 }
657
658 /**Function*************************************************************
659
660 Synopsis [Marks nodes for power-optimization.]
661
662 Description []
663
664 SideEffects []
665
666 SeeAlso []
667
668 ***********************************************************************/
Abc_NtkPowerEstimate(Abc_Ntk_t * pNtk,int fProbOne)669 Vec_Int_t * Abc_NtkPowerEstimate( Abc_Ntk_t * pNtk, int fProbOne )
670 {
671 extern Aig_Man_t * Abc_NtkToDar( Abc_Ntk_t * pNtk, int fExors, int fRegisters );
672 extern Vec_Int_t * Saig_ManComputeSwitchProbs( Aig_Man_t * p, int nFrames, int nPref, int fProbOne );
673 Vec_Int_t * vProbs;
674 Vec_Int_t * vSwitching;
675 float * pProbability;
676 float * pSwitching;
677 Abc_Ntk_t * pNtkStr;
678 Aig_Man_t * pAig;
679 Aig_Obj_t * pObjAig;
680 Abc_Obj_t * pObjAbc, * pObjAbc2;
681 int i;
682 // start the resulting array
683 vProbs = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
684 pProbability = (float *)vProbs->pArray;
685 // strash the network
686 pNtkStr = Abc_NtkStrash( pNtk, 0, 1, 0 );
687 Abc_NtkForEachObj( pNtk, pObjAbc, i )
688 if ( Abc_ObjRegular((Abc_Obj_t *)pObjAbc->pTemp)->Type == ABC_FUNC_NONE )
689 pObjAbc->pTemp = NULL;
690 // map network into an AIG
691 pAig = Abc_NtkToDar( pNtkStr, 0, (int)(Abc_NtkLatchNum(pNtk) > 0) );
692 vSwitching = Saig_ManComputeSwitchProbs( pAig, 48, 16, fProbOne );
693 pSwitching = (float *)vSwitching->pArray;
694 Abc_NtkForEachObj( pNtk, pObjAbc, i )
695 {
696 if ( (pObjAbc2 = Abc_ObjRegular((Abc_Obj_t *)pObjAbc->pTemp)) && (pObjAig = Aig_Regular((Aig_Obj_t *)pObjAbc2->pTemp)) )
697 pProbability[pObjAbc->Id] = pSwitching[pObjAig->Id];
698 }
699 Vec_IntFree( vSwitching );
700 Aig_ManStop( pAig );
701 Abc_NtkDelete( pNtkStr );
702 return vProbs;
703 }
704
705 /**Function*************************************************************
706
707 Synopsis [Marks nodes for power-optimization.]
708
709 Description []
710
711 SideEffects []
712
713 SeeAlso []
714
715 ***********************************************************************/
Abc_NtkPowerPrint(Abc_Ntk_t * pNtk,Vec_Int_t * vProbs)716 void Abc_NtkPowerPrint( Abc_Ntk_t * pNtk, Vec_Int_t * vProbs )
717 {
718 Abc_Obj_t * pObj;
719 float * pProb, TotalProb = 0.0, ProbThis, Probs[6] = {0.0};
720 int i, nNodes = 0, nEdges = 0, Counter[6] = {0};
721 pProb = (float *)vProbs->pArray;
722 assert( Vec_IntSize(vProbs) >= Abc_NtkObjNumMax(pNtk) );
723 Abc_NtkForEachObj( pNtk, pObj, i )
724 {
725 if ( !Abc_ObjIsNode(pObj) && !Abc_ObjIsPi(pObj) )
726 continue;
727 nNodes++;
728 nEdges += Abc_ObjFanoutNum(pObj);
729 ProbThis = pProb[i] * Abc_ObjFanoutNum(pObj);
730 TotalProb += ProbThis;
731 assert( pProb[i] >= 0.0 && pProb[i] <= 1.0 );
732 if ( pProb[i] >= 0.5 )
733 {
734 Counter[5]++;
735 Probs[5] += ProbThis;
736 }
737 else if ( pProb[i] >= 0.4 )
738 {
739 Counter[4]++;
740 Probs[4] += ProbThis;
741 }
742 else if ( pProb[i] >= 0.3 )
743 {
744 Counter[3]++;
745 Probs[3] += ProbThis;
746 }
747 else if ( pProb[i] >= 0.2 )
748 {
749 Counter[2]++;
750 Probs[2] += ProbThis;
751 }
752 else if ( pProb[i] >= 0.1 )
753 {
754 Counter[1]++;
755 Probs[1] += ProbThis;
756 }
757 else
758 {
759 Counter[0]++;
760 Probs[0] += ProbThis;
761 }
762 }
763 printf( "Node distribution: " );
764 for ( i = 0; i < 6; i++ )
765 printf( "n%d%d = %6.2f%% ", i, i+1, 100.0 * Counter[i]/nNodes );
766 printf( "\n" );
767 printf( "Power distribution: " );
768 for ( i = 0; i < 6; i++ )
769 printf( "p%d%d = %6.2f%% ", i, i+1, 100.0 * Probs[i]/TotalProb );
770 printf( "\n" );
771 printf( "Total probs = %7.2f. ", TotalProb );
772 printf( "Total edges = %d. ", nEdges );
773 printf( "Average = %7.2f. ", TotalProb / nEdges );
774 printf( "\n" );
775 }
776
777 /**Function*************************************************************
778
779 Synopsis [Determines timing-critical edges of the node.]
780
781 Description []
782
783 SideEffects []
784
785 SeeAlso []
786
787 ***********************************************************************/
Abc_NtkPowerCriticalEdges(Abc_Ntk_t * pNtk,Abc_Obj_t * pNode,float Limit,Vec_Int_t * vProbs)788 unsigned Abc_NtkPowerCriticalEdges( Abc_Ntk_t * pNtk, Abc_Obj_t * pNode, float Limit, Vec_Int_t * vProbs )
789 {
790 Abc_Obj_t * pFanin;
791 float * pProb = (float *)vProbs->pArray;
792 unsigned uResult = 0;
793 int k;
794 Abc_ObjForEachFanin( pNode, pFanin, k )
795 if ( pProb[pFanin->Id] >= Limit )
796 uResult |= (1 << k);
797 return uResult;
798 }
799
800 /**Function*************************************************************
801
802 Synopsis [Adds choices to speed up the network by the given percentage.]
803
804 Description []
805
806 SideEffects []
807
808 SeeAlso []
809
810 ***********************************************************************/
Abc_NtkPowerdown(Abc_Ntk_t * pNtk,int fUseLutLib,int Percentage,int Degree,int fVerbose,int fVeryVerbose)811 Abc_Ntk_t * Abc_NtkPowerdown( Abc_Ntk_t * pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose )
812 {
813 Abc_Ntk_t * pNtkNew;
814 Vec_Int_t * vProbs;
815 Vec_Ptr_t * vTimeCries, * vTimeFanins;
816 Abc_Obj_t * pNode, * pFanin, * pFanin2;
817 float * pProb, Limit;
818 int i, k, k2, Counter, CounterRes, nTimeCris;
819 unsigned * puPCEdges;
820 // compute the limit
821 Limit = 0.5 - (1.0 * Percentage / 100);
822 // perform computation of switching probability
823 vProbs = Abc_NtkPowerEstimate( pNtk, 0 );
824 pProb = (float *)vProbs->pArray;
825 // compute percentage of wires of each type
826 if ( fVerbose )
827 Abc_NtkPowerPrint( pNtk, vProbs );
828 // mark the power critical nodes and edges
829 puPCEdges = ABC_ALLOC( unsigned, Abc_NtkObjNumMax(pNtk) );
830 memset( puPCEdges, 0, sizeof(unsigned) * Abc_NtkObjNumMax(pNtk) );
831 Abc_NtkForEachNode( pNtk, pNode, i )
832 {
833 if ( pProb[pNode->Id] < Limit )
834 continue;
835 puPCEdges[pNode->Id] = Abc_NtkPowerCriticalEdges( pNtk, pNode, Limit, vProbs );
836 }
837 /*
838 if ( fVerbose )
839 {
840 Counter = CounterRes = 0;
841 Abc_NtkForEachNode( pNtk, pNode, i )
842 {
843 Counter += Abc_ObjFaninNum(pNode);
844 CounterRes += Extra_WordCountOnes( puPCEdges[pNode->Id] );
845 }
846 printf( "Edges: Total = %7d. Critical = %7d. Ratio = %4.2f\n",
847 Counter, CounterRes, 1.0*CounterRes/Counter );
848 }
849 */
850 // start the resulting network
851 pNtkNew = Abc_NtkStrash( pNtk, 0, 1, 0 );
852
853 // collect nodes to be used for resynthesis
854 Counter = CounterRes = 0;
855 vTimeCries = Vec_PtrAlloc( 16 );
856 vTimeFanins = Vec_PtrAlloc( 16 );
857 Abc_NtkForEachNode( pNtk, pNode, i )
858 {
859 // if ( pProb[pNode->Id] < Limit )
860 // continue;
861 // count the number of non-PI power-critical nodes
862 nTimeCris = 0;
863 Abc_ObjForEachFanin( pNode, pFanin, k )
864 if ( !Abc_ObjIsCi(pFanin) && (puPCEdges[pNode->Id] & (1<<k)) )
865 nTimeCris++;
866 if ( !fVeryVerbose && nTimeCris == 0 )
867 continue;
868 Counter++;
869 // count the total number of power-critical second-generation nodes
870 Vec_PtrClear( vTimeCries );
871 if ( nTimeCris )
872 {
873 Abc_ObjForEachFanin( pNode, pFanin, k )
874 if ( !Abc_ObjIsCi(pFanin) && (puPCEdges[pNode->Id] & (1<<k)) )
875 Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
876 if ( puPCEdges[pFanin->Id] & (1<<k2) )
877 Vec_PtrPushUnique( vTimeCries, pFanin2 );
878 }
879 // if ( !fVeryVerbose && (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
880 if ( (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
881 continue;
882 CounterRes++;
883 // collect second generation nodes
884 Vec_PtrClear( vTimeFanins );
885 Abc_ObjForEachFanin( pNode, pFanin, k )
886 {
887 if ( Abc_ObjIsCi(pFanin) )
888 Vec_PtrPushUnique( vTimeFanins, pFanin );
889 else
890 Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
891 Vec_PtrPushUnique( vTimeFanins, pFanin2 );
892 }
893 // print the results
894 if ( fVeryVerbose )
895 {
896 printf( "%5d Node %5d : %d %2d %2d ", Counter, pNode->Id,
897 nTimeCris, Vec_PtrSize(vTimeCries), Vec_PtrSize(vTimeFanins) );
898 Abc_ObjForEachFanin( pNode, pFanin, k )
899 printf( "%d(%.2f)%s ", pFanin->Id, pProb[pFanin->Id], (puPCEdges[pNode->Id] & (1<<k))? "*":"" );
900 printf( "\n" );
901 }
902 // add the node to choices
903 if ( Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree )
904 continue;
905 // order the fanins in the increasing order of criticalily
906 if ( Vec_PtrSize(vTimeCries) > 1 )
907 {
908 pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
909 pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
910 // if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
911 if ( pProb[pFanin->Id] > pProb[pFanin2->Id] )
912 {
913 Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
914 Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
915 }
916 }
917 if ( Vec_PtrSize(vTimeCries) > 2 )
918 {
919 pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
920 pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 2 );
921 // if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
922 if ( pProb[pFanin->Id] > pProb[pFanin2->Id] )
923 {
924 Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 );
925 Vec_PtrWriteEntry( vTimeCries, 2, pFanin );
926 }
927 pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
928 pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
929 // if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
930 if ( pProb[pFanin->Id] > pProb[pFanin2->Id] )
931 {
932 Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
933 Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
934 }
935 }
936 // add choice
937 Abc_NtkSpeedupNode( pNtk, pNtkNew, pNode, vTimeFanins, vTimeCries );
938 }
939 Vec_PtrFree( vTimeCries );
940 Vec_PtrFree( vTimeFanins );
941 ABC_FREE( puPCEdges );
942 if ( fVerbose )
943 printf( "Nodes: Total = %7d. Power-critical = %7d. Workable = %7d. Ratio = %4.2f\n",
944 Abc_NtkNodeNum(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter );
945
946 // remove invalid choice nodes
947 Abc_AigForEachAnd( pNtkNew, pNode, i )
948 if ( pNode->pData )
949 {
950 if ( Abc_ObjFanoutNum((Abc_Obj_t *)pNode->pData) > 0 )
951 pNode->pData = NULL;
952 }
953
954 // return the result
955 Vec_IntFree( vProbs );
956 return pNtkNew;
957 }
958
959 ////////////////////////////////////////////////////////////////////////
960 /// END OF FILE ///
961 ////////////////////////////////////////////////////////////////////////
962
963
964 ABC_NAMESPACE_IMPL_END
965
966