ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
abcSpeedup.c
Go to the documentation of this file.
1
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
26ABC_NAMESPACE_IMPL_START
27
28
32
33static inline float Abc_ObjArrival( Abc_Obj_t * pNode ) { return pNode->pNtk->pLutTimes[3*pNode->Id+0]; }
34static inline float Abc_ObjRequired( Abc_Obj_t * pNode ) { return pNode->pNtk->pLutTimes[3*pNode->Id+1]; }
35static inline float Abc_ObjSlack( Abc_Obj_t * pNode ) { return pNode->pNtk->pLutTimes[3*pNode->Id+2]; }
36
37static inline void Abc_ObjSetArrival( Abc_Obj_t * pNode, float Time ) { pNode->pNtk->pLutTimes[3*pNode->Id+0] = Time; }
38static inline void Abc_ObjSetRequired( Abc_Obj_t * pNode, float Time ) { pNode->pNtk->pLutTimes[3*pNode->Id+1] = Time; }
39static inline void Abc_ObjSetSlack( Abc_Obj_t * pNode, float Time ) { pNode->pNtk->pLutTimes[3*pNode->Id+2] = Time; }
40
44
56void 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
100float 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
244void 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
297int 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
330int 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
349int 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
376void 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
466unsigned 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
512Abc_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
669Vec_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
716void 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
788unsigned 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
811Abc_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
962
963
964ABC_NAMESPACE_IMPL_END
965
Abc_NtkPowerdown
Abc_Ntk_t * Abc_NtkPowerdown(Abc_Ntk_t *pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose)
Definition abcSpeedup.c:811
Abc_NtkPowerEstimate
Vec_Int_t * Abc_NtkPowerEstimate(Abc_Ntk_t *pNtk, int fProbOne)
Definition abcSpeedup.c:669
Abc_NtkPowerPrint
void Abc_NtkPowerPrint(Abc_Ntk_t *pNtk, Vec_Int_t *vProbs)
Definition abcSpeedup.c:716
Abc_NtkPowerCriticalEdges
unsigned Abc_NtkPowerCriticalEdges(Abc_Ntk_t *pNtk, Abc_Obj_t *pNode, float Limit, Vec_Int_t *vProbs)
Definition abcSpeedup.c:788
Abc_NtkSpeedup
Abc_Ntk_t * Abc_NtkSpeedup(Abc_Ntk_t *pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose)
Definition abcSpeedup.c:512
Abc_NtkDelayTraceTCEdges
unsigned Abc_NtkDelayTraceTCEdges(Abc_Ntk_t *pNtk, Abc_Obj_t *pNode, float tDelta, int fUseLutLib)
Definition abcSpeedup.c:466
Abc_AigCheckTfi
int Abc_AigCheckTfi(Abc_Obj_t *pNew, Abc_Obj_t *pOld)
Definition abcSpeedup.c:330
Abc_NtkDelayTraceSortPins
void Abc_NtkDelayTraceSortPins(Abc_Obj_t *pNode, int *pPinPerm, float *pPinDelays)
FUNCTION DEFINITIONS ///.
Definition abcSpeedup.c:56
Abc_NtkSpeedupNode_rec
int Abc_NtkSpeedupNode_rec(Abc_Obj_t *pNode, Vec_Ptr_t *vNodes)
Definition abcSpeedup.c:349
Abc_AigCheckTfi_rec
int Abc_AigCheckTfi_rec(Abc_Obj_t *pNode, Abc_Obj_t *pOld)
Definition abcSpeedup.c:297
Abc_NtkDelayTraceLut
float Abc_NtkDelayTraceLut(Abc_Ntk_t *pNtk, int fUseLutLib)
Definition abcSpeedup.c:100
Abc_NtkDelayTracePrint
void Abc_NtkDelayTracePrint(Abc_Ntk_t *pNtk, int fUseLutLib, int fVerbose)
Definition abcSpeedup.c:244
Abc_NtkSpeedupNode
void Abc_NtkSpeedupNode(Abc_Ntk_t *pNtk, Abc_Ntk_t *pAig, Abc_Obj_t *pNode, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vTimes)
Definition abcSpeedup.c:376
Abc_Obj_t
struct Abc_Obj_t_ Abc_Obj_t
Definition abc.h:116
Abc_NtkForEachCo
#define Abc_NtkForEachCo(pNtk, pCo, i)
Definition abc.h:522
Abc_NtkGetFaninMax
ABC_DLL int Abc_NtkGetFaninMax(Abc_Ntk_t *pNtk)
Definition abcUtil.c:486
Abc_AigForEachAnd
#define Abc_AigForEachAnd(pNtk, pNode, i)
Definition abc.h:488
Abc_NtkDfs
ABC_DLL Vec_Ptr_t * Abc_NtkDfs(Abc_Ntk_t *pNtk, int fCollectAll)
Definition abcDfs.c:82
Abc_NtkForEachObj
#define Abc_NtkForEachObj(pNtk, pObj, i)
ITERATORS ///.
Definition abc.h:449
Abc_AigMux
ABC_DLL Abc_Obj_t * Abc_AigMux(Abc_Aig_t *pMan, Abc_Obj_t *pC, Abc_Obj_t *p1, Abc_Obj_t *p0)
Definition abcAig.c:752
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition abc.h:527
Abc_Aig_t
struct Abc_Aig_t_ Abc_Aig_t
Definition abc.h:117
Abc_Ntk_t
struct Abc_Ntk_t_ Abc_Ntk_t
Definition abc.h:115
Abc_NtkLevel
ABC_DLL int Abc_NtkLevel(Abc_Ntk_t *pNtk)
Definition abcDfs.c:1449
Abc_AigAnd
ABC_DLL Abc_Obj_t * Abc_AigAnd(Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1)
Definition abcAig.c:700
Abc_NtkStrash
ABC_DLL Abc_Ntk_t * Abc_NtkStrash(Abc_Ntk_t *pNtk, int fAllNodes, int fCleanup, int fRecord)
Definition abcStrash.c:265
Abc_NtkDelete
ABC_DLL void Abc_NtkDelete(Abc_Ntk_t *pNtk)
Definition abcNtk.c:1421
ABC_FUNC_NONE
@ ABC_FUNC_NONE
Definition abc.h:64
Abc_AigConst1
ABC_DLL Abc_Obj_t * Abc_AigConst1(Abc_Ntk_t *pNtk)
Definition abcAig.c:683
Abc_NtkDfsReverse
ABC_DLL Vec_Ptr_t * Abc_NtkDfsReverse(Abc_Ntk_t *pNtk)
Definition abcDfs.c:221
Abc_NtkGetTotalFanins
ABC_DLL int Abc_NtkGetTotalFanins(Abc_Ntk_t *pNtk)
Definition abcUtil.c:520
Abc_NtkForEachNode
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition abc.h:464
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition abc_global.h:264
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition abc_global.h:250
ABC_FREE
#define ABC_FREE(obj)
Definition abc_global.h:267
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition abc_namespaces.h:54
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition abc_namespaces.h:55
Aig_ManStop
void Aig_ManStop(Aig_Man_t *p)
Definition aigMan.c:187
Aig_Obj_t
struct Aig_Obj_t_ Aig_Obj_t
Definition aig.h:51
Aig_Man_t
typedefABC_NAMESPACE_HEADER_START struct Aig_Man_t_ Aig_Man_t
INCLUDES ///.
Definition aig.h:50
Abc_FrameReadLibLut
ABC_DLL void * Abc_FrameReadLibLut()
Definition mainFrame.c:57
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition bblif.c:37
p
Cube * p
Definition exorList.c:222
Saig_ManComputeSwitchProbs
Vec_Int_t * Saig_ManComputeSwitchProbs(Aig_Man_t *pAig, int nFrames, int nPref, int fProbOne)
Definition giaSwitch.c:711
Abc_NtkToDar
Aig_Man_t * Abc_NtkToDar(Abc_Ntk_t *pNtk, int fExors, int fRegisters)
Definition abcDar.c:237
If_LibLut_t
struct If_LibLut_t_ If_LibLut_t
Definition if.h:82
Abc_Ntk_t_::pLutTimes
float * pLutTimes
Definition abc.h:210
Abc_Ntk_t_::pManFunc
void * pManFunc
Definition abc.h:191
Abc_Obj_t_::pData
void * pData
Definition abc.h:145
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition abc.h:130
Abc_Obj_t_::Id
int Id
Definition abc.h:132
Abc_Obj_t_::pCopy
Abc_Obj_t * pCopy
Definition abc.h:148
Abc_Obj_t_::pTemp
void * pTemp
Definition abc.h:147
Aig_Obj_t_::Id
int Id
Definition aig.h:85
If_LibLut_t_::fVarPinDelays
int fVarPinDelays
Definition if.h:191
If_LibLut_t_::LutMax
int LutMax
Definition if.h:190
If_LibLut_t_::pLutDelays
float pLutDelays[IF_MAX_LUTSIZE+1][IF_MAX_LUTSIZE+1]
Definition if.h:193
assert
#define assert(ex)
Definition util_old.h:213
memset
char * memset()
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition vecPtr.h:42
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition vecPtr.h:55