ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
Functions
nwkSpeedup.c File Reference
#include "nwk.h"
Include dependency graph for nwkSpeedup.c:

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START int Aig_ManSpeedupNode_rec (Aig_Man_t *pAig, Aig_Obj_t *pNode, Vec_Ptr_t *vNodes)
 DECLARATIONS ///.
 
void Aig_ManSpeedupNode (Nwk_Man_t *pNtk, Aig_Man_t *pAig, Nwk_Obj_t *pNode, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vTimes)
 
unsigned Nwk_ManDelayTraceTCEdges (Nwk_Man_t *pNtk, Nwk_Obj_t *pNode, float tDelta, int fUseLutLib)
 
Aig_Man_t * Nwk_ManSpeedup (Nwk_Man_t *pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose)
 

Function Documentation

◆ Aig_ManSpeedupNode()

void Aig_ManSpeedupNode ( Nwk_Man_t * pNtk,
Aig_Man_t * pAig,
Nwk_Obj_t * pNode,
Vec_Ptr_t * vLeaves,
Vec_Ptr_t * vTimes )

Function*************************************************************

Synopsis [Adds strashed nodes for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 72 of file nwkSpeedup.c.

73{
74 Vec_Ptr_t * vNodes;
75 Nwk_Obj_t * pObj, * pObj2;
76 Aig_Obj_t * ppCofs[32], * pAnd, * pTemp;
77 int nCofs, i, k, nSkip;
78
79 // quit of regulars are the same
80 Vec_PtrForEachEntry( Nwk_Obj_t *, vLeaves, pObj, i )
81 Vec_PtrForEachEntry( Nwk_Obj_t *, vLeaves, pObj2, k )
82 if ( i != k && Aig_Regular((Aig_Obj_t *)pObj->pCopy) == Aig_Regular((Aig_Obj_t *)pObj2->pCopy) )
83 {
84// printf( "Identical after structural hashing!!!\n" );
85 return;
86 }
87
88 // collect the AIG nodes
89 vNodes = Vec_PtrAlloc( 100 );
90 Aig_ManIncrementTravId( pAig );
91 Aig_ObjSetTravIdCurrent( pAig, Aig_ManConst1(pAig) );
92 Vec_PtrForEachEntry( Nwk_Obj_t *, vLeaves, pObj, i )
93 {
94 pAnd = (Aig_Obj_t *)pObj->pCopy;
95 Aig_ObjSetTravIdCurrent( pAig, Aig_Regular(pAnd) );
96 }
97 // traverse from the root node
98 pAnd = (Aig_Obj_t *)pNode->pCopy;
99 if ( !Aig_ManSpeedupNode_rec( pAig, Aig_Regular(pAnd), vNodes ) )
100 {
101// printf( "Bad node!!!\n" );
102 Vec_PtrFree( vNodes );
103 return;
104 }
105
106 // derive cofactors
107 nCofs = (1 << Vec_PtrSize(vTimes));
108 for ( i = 0; i < nCofs; i++ )
109 {
110 Vec_PtrForEachEntry( Nwk_Obj_t *, vLeaves, pObj, k )
111 {
112 pAnd = (Aig_Obj_t *)pObj->pCopy;
113 Aig_Regular(pAnd)->pData = Aig_Regular(pAnd);
114 }
115 Vec_PtrForEachEntry( Nwk_Obj_t *, vTimes, pObj, k )
116 {
117 pAnd = (Aig_Obj_t *)pObj->pCopy;
118 Aig_Regular(pAnd)->pData = Aig_NotCond( Aig_ManConst1(pAig), ((i & (1<<k)) == 0) );
119 }
120 Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pTemp, k )
121 pTemp->pData = Aig_And( pAig, Aig_ObjChild0Copy(pTemp), Aig_ObjChild1Copy(pTemp) );
122 // save the result
123 pAnd = (Aig_Obj_t *)pNode->pCopy;
124 ppCofs[i] = Aig_NotCond( (Aig_Obj_t *)Aig_Regular(pAnd)->pData, Aig_IsComplement(pAnd) );
125 }
126 Vec_PtrFree( vNodes );
127
128//Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[0] );
129//Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[1] );
130
131 // collect the resulting tree
132 Vec_PtrForEachEntry( Nwk_Obj_t *, vTimes, pObj, k )
133 for ( nSkip = (1<<k), i = 0; i < nCofs; i += 2*nSkip )
134 {
135 pAnd = (Aig_Obj_t *)pObj->pCopy;
136 ppCofs[i] = Aig_Mux( pAig, Aig_Regular(pAnd), ppCofs[i+nSkip], ppCofs[i] );
137 }
138//Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[0] );
139
140 // create choice node
141 pAnd = Aig_Regular((Aig_Obj_t *)pNode->pCopy); // repr
142 pTemp = Aig_Regular(ppCofs[0]); // new
143 if ( Aig_ObjEquiv(pAig, pAnd) == NULL && Aig_ObjEquiv(pAig, pTemp) == NULL && !Aig_ObjCheckTfi(pAig, pTemp, pAnd) )
144 pAig->pEquivs[pAnd->Id] = pTemp;
145}
Aig_ObjCheckTfi
int Aig_ObjCheckTfi(Aig_Man_t *p, Aig_Obj_t *pNew, Aig_Obj_t *pOld)
Definition aigRepr.c:435
Aig_ManIncrementTravId
void Aig_ManIncrementTravId(Aig_Man_t *p)
DECLARATIONS ///.
Definition aigUtil.c:44
Aig_And
Aig_Obj_t * Aig_And(Aig_Man_t *p, Aig_Obj_t *p0, Aig_Obj_t *p1)
Definition aigOper.c:104
Aig_Mux
Aig_Obj_t * Aig_Mux(Aig_Man_t *p, Aig_Obj_t *pC, Aig_Obj_t *p1, Aig_Obj_t *p0)
Definition aigOper.c:317
Aig_Obj_t
struct Aig_Obj_t_ Aig_Obj_t
Definition aig.h:51
Aig_ManSpeedupNode_rec
ABC_NAMESPACE_IMPL_START int Aig_ManSpeedupNode_rec(Aig_Man_t *pAig, Aig_Obj_t *pNode, Vec_Ptr_t *vNodes)
DECLARATIONS ///.
Definition nwkSpeedup.c:45
Nwk_Obj_t
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition nwk.h:49
Aig_Obj_t_::Id
int Id
Definition aig.h:85
Aig_Obj_t_::pData
void * pData
Definition aig.h:87
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
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Aig_ManSpeedupNode_rec()

ABC_NAMESPACE_IMPL_START int Aig_ManSpeedupNode_rec ( Aig_Man_t * pAig,
Aig_Obj_t * pNode,
Vec_Ptr_t * vNodes )

DECLARATIONS ///.

CFile****************************************************************

FileName [nwkSpeedup.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Netlist representation.]

Synopsis [Global delay optimization using structural choices.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id
nwkSpeedup.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

] FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Adds strashed nodes for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file nwkSpeedup.c.

46{
47 if ( Aig_ObjIsTravIdCurrent(pAig, pNode) )
48 return 1;
49 if ( Aig_ObjIsCi(pNode) )
50 return 0;
51 assert( Aig_ObjIsNode(pNode) );
52 Aig_ObjSetTravIdCurrent( pAig, pNode );
53 if ( !Aig_ManSpeedupNode_rec( pAig, Aig_ObjFanin0(pNode), vNodes ) )
54 return 0;
55 if ( !Aig_ManSpeedupNode_rec( pAig, Aig_ObjFanin1(pNode), vNodes ) )
56 return 0;
57 Vec_PtrPush( vNodes, pNode );
58 return 1;
59}
assert
#define assert(ex)
Definition util_old.h:213
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Nwk_ManDelayTraceTCEdges()

unsigned Nwk_ManDelayTraceTCEdges ( Nwk_Man_t * pNtk,
Nwk_Obj_t * pNode,
float tDelta,
int fUseLutLib )

Function*************************************************************

Synopsis [Determines timing-critical edges of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 158 of file nwkSpeedup.c.

159{
160 int pPinPerm[32];
161 float pPinDelays[32];
162 If_LibLut_t * pLutLib = fUseLutLib? pNtk->pLutLib : NULL;
163 Nwk_Obj_t * pFanin;
164 unsigned uResult = 0;
165 float tRequired, * pDelays;
166 int k;
167 tRequired = Nwk_ObjRequired(pNode);
168 if ( pLutLib == NULL )
169 {
170 Nwk_ObjForEachFanin( pNode, pFanin, k )
171 if ( tRequired < Nwk_ObjArrival(pFanin) + 1.0 + tDelta )
172 uResult |= (1 << k);
173 }
174 else if ( !pLutLib->fVarPinDelays )
175 {
176 pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pNode)];
177 Nwk_ObjForEachFanin( pNode, pFanin, k )
178 if ( tRequired < Nwk_ObjArrival(pFanin) + pDelays[0] + tDelta )
179 uResult |= (1 << k);
180 }
181 else
182 {
183 pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pNode)];
184 Nwk_ManDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
185 Nwk_ObjForEachFanin( pNode, pFanin, k )
186 if ( tRequired < Nwk_ObjArrival(Nwk_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] + tDelta )
187 uResult |= (1 << pPinPerm[k]);
188 }
189 return uResult;
190}
If_LibLut_t
struct If_LibLut_t_ If_LibLut_t
Definition if.h:82
Nwk_ManDelayTraceSortPins
ABC_DLL void Nwk_ManDelayTraceSortPins(Nwk_Obj_t *pNode, int *pPinPerm, float *pPinDelays)
Definition nwkTiming.c:67
Nwk_ObjForEachFanin
#define Nwk_ObjForEachFanin(pObj, pFanin, i)
Definition nwk.h:199
If_LibLut_t_::fVarPinDelays
int fVarPinDelays
Definition if.h:191
If_LibLut_t_::pLutDelays
float pLutDelays[IF_MAX_LUTSIZE+1][IF_MAX_LUTSIZE+1]
Definition if.h:193
Nwk_Man_t_::pLutLib
If_LibLut_t * pLutLib
Definition nwk.h:75
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Nwk_ManSpeedup()

Aig_Man_t * Nwk_ManSpeedup ( Nwk_Man_t * pNtk,
int fUseLutLib,
int Percentage,
int Degree,
int fVerbose,
int fVeryVerbose )

Function*************************************************************

Synopsis [Adds choices to speed up the network by the given percentage.]

Description []

SideEffects []

SeeAlso []

Definition at line 203 of file nwkSpeedup.c.

204{
205 Aig_Man_t * pAig, * pTemp;
206 Vec_Ptr_t * vTimeCries, * vTimeFanins;
207 Nwk_Obj_t * pNode, * pFanin, * pFanin2;
208 Aig_Obj_t * pAnd;
209 If_LibLut_t * pTempLib = pNtk->pLutLib;
210 Tim_Man_t * pTempTim = NULL;
211 float tDelta, tArrival;
212 int i, k, k2, Counter, CounterRes, nTimeCris;
213 unsigned * puTCEdges;
214 // perform delay trace
215 if ( !fUseLutLib )
216 {
217 pNtk->pLutLib = NULL;
218 if ( pNtk->pManTime )
219 {
220 pTempTim = pNtk->pManTime;
221 pNtk->pManTime = Tim_ManDup( pTempTim, 1 );
222 }
223 }
224 tArrival = Nwk_ManDelayTraceLut( pNtk );
225 tDelta = fUseLutLib ? tArrival*Percentage/100.0 : 1.0;
226 if ( fVerbose )
227 {
228 printf( "Max delay = %.2f. Delta = %.2f. ", tArrival, tDelta );
229 printf( "Using %s model. ", fUseLutLib? "LUT library" : "unit-delay" );
230 if ( fUseLutLib )
231 printf( "Percentage = %d. ", Percentage );
232 printf( "\n" );
233 }
234 // mark the timing critical nodes and edges
235 puTCEdges = ABC_ALLOC( unsigned, Nwk_ManObjNumMax(pNtk) );
236 memset( puTCEdges, 0, sizeof(unsigned) * Nwk_ManObjNumMax(pNtk) );
237 Nwk_ManForEachNode( pNtk, pNode, i )
238 {
239 if ( Nwk_ObjSlack(pNode) >= tDelta )
240 continue;
241 puTCEdges[pNode->Id] = Nwk_ManDelayTraceTCEdges( pNtk, pNode, tDelta, fUseLutLib );
242 }
243 if ( fVerbose )
244 {
245 Counter = CounterRes = 0;
246 Nwk_ManForEachNode( pNtk, pNode, i )
247 {
248 Nwk_ObjForEachFanin( pNode, pFanin, k )
249 if ( !Nwk_ObjIsCi(pFanin) && Nwk_ObjSlack(pFanin) < tDelta )
250 Counter++;
251 CounterRes += Aig_WordCountOnes( puTCEdges[pNode->Id] );
252 }
253 printf( "Edges: Total = %7d. 0-slack = %7d. Critical = %7d. Ratio = %4.2f\n",
254 Nwk_ManGetTotalFanins(pNtk), Counter, CounterRes, Counter? 1.0*CounterRes/Counter : 0.0 );
255 }
256 // start the resulting network
257 pAig = Nwk_ManStrash( pNtk );
258 pAig->pEquivs = ABC_ALLOC( Aig_Obj_t *, 3 * Aig_ManObjNumMax(pAig) );
259 memset( pAig->pEquivs, 0, sizeof(Aig_Obj_t *) * 3 * Aig_ManObjNumMax(pAig) );
260
261 // collect nodes to be used for resynthesis
262 Counter = CounterRes = 0;
263 vTimeCries = Vec_PtrAlloc( 16 );
264 vTimeFanins = Vec_PtrAlloc( 16 );
265 Nwk_ManForEachNode( pNtk, pNode, i )
266 {
267 if ( Nwk_ObjSlack(pNode) >= tDelta )
268 continue;
269 // count the number of non-PI timing-critical nodes
270 nTimeCris = 0;
271 Nwk_ObjForEachFanin( pNode, pFanin, k )
272 if ( !Nwk_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) )
273 nTimeCris++;
274 if ( !fVeryVerbose && nTimeCris == 0 )
275 continue;
276 Counter++;
277 // count the total number of timing critical second-generation nodes
278 Vec_PtrClear( vTimeCries );
279 if ( nTimeCris )
280 {
281 Nwk_ObjForEachFanin( pNode, pFanin, k )
282 if ( !Nwk_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) )
283 Nwk_ObjForEachFanin( pFanin, pFanin2, k2 )
284 if ( puTCEdges[pFanin->Id] & (1<<k2) )
285 Vec_PtrPushUnique( vTimeCries, pFanin2 );
286 }
287// if ( !fVeryVerbose && (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
288 if ( (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
289 continue;
290 CounterRes++;
291 // collect second generation nodes
292 Vec_PtrClear( vTimeFanins );
293 Nwk_ObjForEachFanin( pNode, pFanin, k )
294 {
295 if ( Nwk_ObjIsCi(pFanin) )
296 Vec_PtrPushUnique( vTimeFanins, pFanin );
297 else
298 Nwk_ObjForEachFanin( pFanin, pFanin2, k2 )
299 Vec_PtrPushUnique( vTimeFanins, pFanin2 );
300 }
301 // print the results
302 if ( fVeryVerbose )
303 {
304 printf( "%5d Node %5d : %d %2d %2d ", Counter, pNode->Id,
305 nTimeCris, Vec_PtrSize(vTimeCries), Vec_PtrSize(vTimeFanins) );
306 Nwk_ObjForEachFanin( pNode, pFanin, k )
307 printf( "%d(%.2f)%s ", pFanin->Id, Nwk_ObjSlack(pFanin), (puTCEdges[pNode->Id] & (1<<k))? "*":"" );
308 printf( "\n" );
309 }
310 // add the node to choices
311 if ( Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree )
312 continue;
313 // order the fanins in the increasing order of criticalily
314 if ( Vec_PtrSize(vTimeCries) > 1 )
315 {
316 pFanin = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
317 pFanin2 = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
318 if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) )
319 {
320 Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
321 Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
322 }
323 }
324 if ( Vec_PtrSize(vTimeCries) > 2 )
325 {
326 pFanin = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
327 pFanin2 = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 2 );
328 if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) )
329 {
330 Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 );
331 Vec_PtrWriteEntry( vTimeCries, 2, pFanin );
332 }
333 pFanin = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
334 pFanin2 = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
335 if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) )
336 {
337 Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
338 Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
339 }
340 }
341 // add choice
342 Aig_ManSpeedupNode( pNtk, pAig, pNode, vTimeFanins, vTimeCries );
343 }
344 Vec_PtrFree( vTimeCries );
345 Vec_PtrFree( vTimeFanins );
346 ABC_FREE( puTCEdges );
347 if ( fVerbose )
348 printf( "Nodes: Total = %7d. 0-slack = %7d. Workable = %7d. Ratio = %4.2f\n",
349 Nwk_ManNodeNum(pNtk), Counter, CounterRes, Counter? 1.0*CounterRes/Counter : 0.0 );
350
351 // remove invalid choice nodes
352 Aig_ManForEachNode( pAig, pAnd, i )
353 if ( Aig_ObjEquiv(pAig, pAnd) )
354 {
355 if ( Aig_ObjRefs(Aig_ObjEquiv(pAig, pAnd)) > 0 )
356 pAig->pEquivs[pAnd->Id] = NULL;
357 }
358
359 // put back the library
360 if ( !fUseLutLib )
361 pNtk->pLutLib = pTempLib;
362 if ( pTempTim )
363 {
364 Tim_ManStop( pNtk->pManTime );
365 pNtk->pManTime = pTempTim;
366 }
367
368 // reconstruct the network
369 pAig = Aig_ManDupDfs( pTemp = pAig );
370 Aig_ManStop( pTemp );
371 // reset levels
372 Aig_ManChoiceLevel( pAig );
373 return pAig;
374}
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition abc_global.h:264
ABC_FREE
#define ABC_FREE(obj)
Definition abc_global.h:267
Aig_ManDupDfs
Aig_Man_t * Aig_ManDupDfs(Aig_Man_t *p)
Definition aigDup.c:563
Aig_ManStop
void Aig_ManStop(Aig_Man_t *p)
Definition aigMan.c:187
Aig_ManForEachNode
#define Aig_ManForEachNode(p, pObj, i)
Definition aig.h:413
Aig_Man_t
typedefABC_NAMESPACE_HEADER_START struct Aig_Man_t_ Aig_Man_t
INCLUDES ///.
Definition aig.h:50
Aig_ManChoiceLevel
int Aig_ManChoiceLevel(Aig_Man_t *p)
Definition aigDfs.c:595
Nwk_ManStrash
ABC_DLL Aig_Man_t * Nwk_ManStrash(Nwk_Man_t *p)
Definition nwkStrash.c:99
Nwk_ManDelayTraceTCEdges
unsigned Nwk_ManDelayTraceTCEdges(Nwk_Man_t *pNtk, Nwk_Obj_t *pNode, float tDelta, int fUseLutLib)
Definition nwkSpeedup.c:158
Aig_ManSpeedupNode
void Aig_ManSpeedupNode(Nwk_Man_t *pNtk, Aig_Man_t *pAig, Nwk_Obj_t *pNode, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vTimes)
Definition nwkSpeedup.c:72
Nwk_ManForEachNode
#define Nwk_ManForEachNode(p, pObj, i)
Definition nwk.h:192
Nwk_ManDelayTraceLut
ABC_DLL float Nwk_ManDelayTraceLut(Nwk_Man_t *pNtk)
Definition nwkTiming.c:326
Nwk_ManGetTotalFanins
ABC_DLL int Nwk_ManGetTotalFanins(Nwk_Man_t *pNtk)
Definition nwkUtil.c:94
Nwk_Man_t_::pManTime
Tim_Man_t * pManTime
Definition nwk.h:74
Tim_Man_t
typedefABC_NAMESPACE_HEADER_START struct Tim_Man_t_ Tim_Man_t
INCLUDES ///.
Definition tim.h:92
Tim_ManStop
void Tim_ManStop(Tim_Man_t *p)
Definition timMan.c:378
Tim_ManDup
Tim_Man_t * Tim_ManDup(Tim_Man_t *p, int fUnitDelay)
Definition timMan.c:86
memset
char * memset()
Here is the call graph for this function: