1 /**CFile****************************************************************
2
3 FileName [mapperTime.c]
4
5 PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
6
7 Synopsis [Generic technology mapping engine.]
8
9 Author [MVSIS Group]
10
11 Affiliation [UC Berkeley]
12
13 Date [Ver. 2.0. Started - June 1, 2004.]
14
15 Revision [$Id: mapperTime.c,v 1.3 2005/03/02 02:35:54 alanmi Exp $]
16
17 ***********************************************************************/
18
19 #include "mapperInt.h"
20
21 #include "misc/util/utilNam.h"
22 #include "map/scl/sclCon.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 ////////////////////////////////////////////////////////////////////////
31 /// FUNCTION DEFINITIONS ///
32 ////////////////////////////////////////////////////////////////////////
33
34 /**Function*************************************************************
35
36 Synopsis [Computes the maximum arrival times.]
37
38 Description []
39
40 SideEffects []
41
42 SeeAlso []
43
44 ***********************************************************************/
Map_TimeComputeArrivalMax(Map_Man_t * p)45 float Map_TimeComputeArrivalMax( Map_Man_t * p )
46 {
47 float tReqMax, tReq;
48 int i, fPhase;
49 // get the critical PO arrival time
50 tReqMax = -MAP_FLOAT_LARGE;
51 for ( i = 0; i < p->nOutputs; i++ )
52 {
53 if ( Map_NodeIsConst(p->pOutputs[i]) )
54 continue;
55 fPhase = !Map_IsComplement(p->pOutputs[i]);
56 tReq = Map_Regular(p->pOutputs[i])->tArrival[fPhase].Worst;
57 tReqMax = MAP_MAX( tReqMax, tReq );
58 }
59 return tReqMax;
60 }
61
62 /**Function*************************************************************
63
64 Synopsis [Computes the arrival times of the cut.]
65
66 Description [Computes the arrival times of the cut if it is implemented using
67 the given supergate with the given phase. Uses the constraint-type specification
68 of rise/fall arrival times.]
69
70 SideEffects []
71
72 SeeAlso []
73
74 ***********************************************************************/
Map_TimeCutComputeArrival(Map_Node_t * pNode,Map_Cut_t * pCut,int fPhase,float tWorstLimit)75 float Map_TimeCutComputeArrival( Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase, float tWorstLimit )
76 {
77 Map_Match_t * pM = pCut->M + fPhase;
78 Map_Super_t * pSuper = pM->pSuperBest;
79 unsigned uPhaseTot = pM->uPhaseBest;
80 Map_Time_t * ptArrRes = &pM->tArrive;
81 Map_Time_t * ptArrIn;
82 int fPinPhase;
83 float tDelay, tExtra;
84 int i;
85
86 tExtra = pNode->p->pNodeDelays ? pNode->p->pNodeDelays[pNode->Num] : 0;
87 ptArrRes->Rise = ptArrRes->Fall = 0.0;
88 ptArrRes->Worst = MAP_FLOAT_LARGE;
89 for ( i = pCut->nLeaves - 1; i >= 0; i-- )
90 {
91 // get the phase of the given pin
92 fPinPhase = ((uPhaseTot & (1 << i)) == 0);
93 ptArrIn = pCut->ppLeaves[i]->tArrival + fPinPhase;
94
95 // get the rise of the output due to rise of the inputs
96 if ( pSuper->tDelaysR[i].Rise > 0 )
97 {
98 tDelay = ptArrIn->Rise + pSuper->tDelaysR[i].Rise + tExtra;
99 if ( tDelay > tWorstLimit )
100 return MAP_FLOAT_LARGE;
101 if ( ptArrRes->Rise < tDelay )
102 ptArrRes->Rise = tDelay;
103 }
104
105 // get the rise of the output due to fall of the inputs
106 if ( pSuper->tDelaysR[i].Fall > 0 )
107 {
108 tDelay = ptArrIn->Fall + pSuper->tDelaysR[i].Fall + tExtra;
109 if ( tDelay > tWorstLimit )
110 return MAP_FLOAT_LARGE;
111 if ( ptArrRes->Rise < tDelay )
112 ptArrRes->Rise = tDelay;
113 }
114
115 // get the fall of the output due to rise of the inputs
116 if ( pSuper->tDelaysF[i].Rise > 0 )
117 {
118 tDelay = ptArrIn->Rise + pSuper->tDelaysF[i].Rise + tExtra;
119 if ( tDelay > tWorstLimit )
120 return MAP_FLOAT_LARGE;
121 if ( ptArrRes->Fall < tDelay )
122 ptArrRes->Fall = tDelay;
123 }
124
125 // get the fall of the output due to fall of the inputs
126 if ( pSuper->tDelaysF[i].Fall > 0 )
127 {
128 tDelay = ptArrIn->Fall + pSuper->tDelaysF[i].Fall + tExtra;
129 if ( tDelay > tWorstLimit )
130 return MAP_FLOAT_LARGE;
131 if ( ptArrRes->Fall < tDelay )
132 ptArrRes->Fall = tDelay;
133 }
134 }
135 // return the worst-case of rise/fall arrival times
136 ptArrRes->Worst = MAP_MAX(ptArrRes->Rise, ptArrRes->Fall);
137 return ptArrRes->Worst;
138 }
139
140
141 /**Function*************************************************************
142
143 Synopsis []
144
145 Description []
146
147 SideEffects []
148
149 SeeAlso []
150
151 ***********************************************************************/
Map_TimePropagateRequiredPhase(Map_Man_t * p,Map_Node_t * pNode,int fPhase)152 void Map_TimePropagateRequiredPhase( Map_Man_t * p, Map_Node_t * pNode, int fPhase )
153 {
154 Map_Time_t * ptReqIn, * ptReqOut;
155 Map_Cut_t * pCut;
156 Map_Super_t * pSuper;
157 float tNewReqTime, tExtra;
158 unsigned uPhase;
159 int fPinPhase, i;
160
161 tExtra = pNode->p->pNodeDelays ? pNode->p->pNodeDelays[pNode->Num] : 0;
162 // get the cut to be propagated
163 pCut = pNode->pCutBest[fPhase];
164 assert( pCut != NULL );
165 // get the supergate and its polarity
166 pSuper = pCut->M[fPhase].pSuperBest;
167 uPhase = pCut->M[fPhase].uPhaseBest;
168 // get the required time of the output of the supergate
169 ptReqOut = pNode->tRequired + fPhase;
170 // set the required time of the children
171 for ( i = 0; i < pCut->nLeaves; i++ )
172 {
173 // get the phase of the given pin of the supergate
174 fPinPhase = ((uPhase & (1 << i)) == 0);
175 ptReqIn = pCut->ppLeaves[i]->tRequired + fPinPhase;
176 assert( pCut->ppLeaves[i]->nRefAct[2] > 0 );
177
178 // get the rise of the output due to rise of the inputs
179 // if ( ptArrOut->Rise < ptArrIn->Rise + pSuper->tDelaysR[i].Rise )
180 // ptArrOut->Rise = ptArrIn->Rise + pSuper->tDelaysR[i].Rise;
181 if ( pSuper->tDelaysR[i].Rise > 0 )
182 {
183 tNewReqTime = ptReqOut->Rise - pSuper->tDelaysR[i].Rise - tExtra;
184 ptReqIn->Rise = MAP_MIN( ptReqIn->Rise, tNewReqTime );
185 }
186
187 // get the rise of the output due to fall of the inputs
188 // if ( ptArrOut->Rise < ptArrIn->Fall + pSuper->tDelaysR[i].Fall )
189 // ptArrOut->Rise = ptArrIn->Fall + pSuper->tDelaysR[i].Fall;
190 if ( pSuper->tDelaysR[i].Fall > 0 )
191 {
192 tNewReqTime = ptReqOut->Rise - pSuper->tDelaysR[i].Fall - tExtra;
193 ptReqIn->Fall = MAP_MIN( ptReqIn->Fall, tNewReqTime );
194 }
195
196 // get the fall of the output due to rise of the inputs
197 // if ( ptArrOut->Fall < ptArrIn->Rise + pSuper->tDelaysF[i].Rise )
198 // ptArrOut->Fall = ptArrIn->Rise + pSuper->tDelaysF[i].Rise;
199 if ( pSuper->tDelaysF[i].Rise > 0 )
200 {
201 tNewReqTime = ptReqOut->Fall - pSuper->tDelaysF[i].Rise - tExtra;
202 ptReqIn->Rise = MAP_MIN( ptReqIn->Rise, tNewReqTime );
203 }
204
205 // get the fall of the output due to fall of the inputs
206 // if ( ptArrOut->Fall < ptArrIn->Fall + pSuper->tDelaysF[i].Fall )
207 // ptArrOut->Fall = ptArrIn->Fall + pSuper->tDelaysF[i].Fall;
208 if ( pSuper->tDelaysF[i].Fall > 0 )
209 {
210 tNewReqTime = ptReqOut->Fall - pSuper->tDelaysF[i].Fall - tExtra;
211 ptReqIn->Fall = MAP_MIN( ptReqIn->Fall, tNewReqTime );
212 }
213 }
214
215 // compare the required times with the arrival times
216 // assert( pNode->tArrival[fPhase].Rise < ptReqOut->Rise + p->fEpsilon );
217 // assert( pNode->tArrival[fPhase].Fall < ptReqOut->Fall + p->fEpsilon );
218 }
Map_MatchComputeReqTimes(Map_Cut_t * pCut,int fPhase,Map_Time_t * ptArrRes)219 float Map_MatchComputeReqTimes( Map_Cut_t * pCut, int fPhase, Map_Time_t * ptArrRes )
220 {
221 Map_Time_t * ptArrIn;
222 Map_Super_t * pSuper;
223 unsigned uPhaseTot;
224 int fPinPhase, i;
225 float tDelay;
226
227 // get the supergate and the phase
228 pSuper = pCut->M[fPhase].pSuperBest;
229 uPhaseTot = pCut->M[fPhase].uPhaseBest;
230
231 // propagate the arrival times
232 ptArrRes->Rise = ptArrRes->Fall = -MAP_FLOAT_LARGE;
233 for ( i = 0; i < pCut->nLeaves; i++ )
234 {
235 // get the phase of the given pin
236 fPinPhase = ((uPhaseTot & (1 << i)) == 0);
237 ptArrIn = pCut->ppLeaves[i]->tRequired + fPinPhase;
238 // assert( ptArrIn->Worst < MAP_FLOAT_LARGE );
239
240 // get the rise of the output due to rise of the inputs
241 if ( pSuper->tDelaysR[i].Rise > 0 )
242 {
243 tDelay = ptArrIn->Rise + pSuper->tDelaysR[i].Rise;
244 if ( ptArrRes->Rise < tDelay )
245 ptArrRes->Rise = tDelay;
246 }
247
248 // get the rise of the output due to fall of the inputs
249 if ( pSuper->tDelaysR[i].Fall > 0 )
250 {
251 tDelay = ptArrIn->Fall + pSuper->tDelaysR[i].Fall;
252 if ( ptArrRes->Rise < tDelay )
253 ptArrRes->Rise = tDelay;
254 }
255
256 // get the fall of the output due to rise of the inputs
257 if ( pSuper->tDelaysF[i].Rise > 0 )
258 {
259 tDelay = ptArrIn->Rise + pSuper->tDelaysF[i].Rise;
260 if ( ptArrRes->Fall < tDelay )
261 ptArrRes->Fall = tDelay;
262 }
263
264 // get the fall of the output due to fall of the inputs
265 if ( pSuper->tDelaysF[i].Fall > 0 )
266 {
267 tDelay = ptArrIn->Fall + pSuper->tDelaysF[i].Fall;
268 if ( ptArrRes->Fall < tDelay )
269 ptArrRes->Fall = tDelay;
270 }
271 }
272 // return the worst-case of rise/fall arrival times
273 return MAP_MAX(ptArrRes->Rise, ptArrRes->Fall);
274 }
275
276
277 /**Function*************************************************************
278
279 Synopsis [Computes the required times of all nodes.]
280
281 Description []
282
283 SideEffects []
284
285 SeeAlso []
286
287 ***********************************************************************/
Map_TimePropagateRequired(Map_Man_t * p)288 void Map_TimePropagateRequired( Map_Man_t * p )
289 {
290 Map_Node_t * pNode;
291 //Map_Time_t tReqOutTest, * ptReqOutTest = &tReqOutTest;
292 Map_Time_t * ptReqIn, * ptReqOut;
293 int fPhase, k;
294
295 // go through the nodes in the reverse topological order
296 for ( k = p->vMapObjs->nSize - 1; k >= 0; k-- )
297 {
298 pNode = p->vMapObjs->pArray[k];
299 if ( pNode->nRefAct[2] == 0 )
300 continue;
301
302 // propagate required times through the buffer
303 if ( Map_NodeIsBuf(pNode) )
304 {
305 assert( pNode->p2 == NULL );
306 Map_Regular(pNode->p1)->tRequired[ Map_IsComplement(pNode->p1)] = pNode->tRequired[0];
307 Map_Regular(pNode->p1)->tRequired[!Map_IsComplement(pNode->p1)] = pNode->tRequired[1];
308 continue;
309 }
310
311 // this computation works for regular nodes only
312 assert( !Map_IsComplement(pNode) );
313 // at least one phase should be mapped
314 assert( pNode->pCutBest[0] != NULL || pNode->pCutBest[1] != NULL );
315 // the node should be used in the currently assigned mapping
316 assert( pNode->nRefAct[0] > 0 || pNode->nRefAct[1] > 0 );
317
318 // if one of the cuts is not given, project the required times from the other cut
319 if ( pNode->pCutBest[0] == NULL || pNode->pCutBest[1] == NULL )
320 {
321 // assert( 0 );
322 // get the missing phase
323 fPhase = (pNode->pCutBest[1] == NULL);
324 // check if the missing phase is needed in the mapping
325 if ( pNode->nRefAct[fPhase] > 0 )
326 {
327 // get the pointers to the required times of the missing phase
328 ptReqOut = pNode->tRequired + fPhase;
329 // assert( ptReqOut->Fall < MAP_FLOAT_LARGE );
330 // get the pointers to the required times of the present phase
331 ptReqIn = pNode->tRequired + !fPhase;
332 // propagate the required times from the missing phase to the present phase
333 // tArrInv.Fall = pMatch->tArrive.Rise + p->pSuperLib->tDelayInv.Fall;
334 // tArrInv.Rise = pMatch->tArrive.Fall + p->pSuperLib->tDelayInv.Rise;
335 ptReqIn->Fall = MAP_MIN( ptReqIn->Fall, ptReqOut->Rise - p->pSuperLib->tDelayInv.Rise );
336 ptReqIn->Rise = MAP_MIN( ptReqIn->Rise, ptReqOut->Fall - p->pSuperLib->tDelayInv.Fall );
337 }
338 }
339
340 // finalize the worst case computation
341 pNode->tRequired[0].Worst = MAP_MIN( pNode->tRequired[0].Fall, pNode->tRequired[0].Rise );
342 pNode->tRequired[1].Worst = MAP_MIN( pNode->tRequired[1].Fall, pNode->tRequired[1].Rise );
343
344 // skip the PIs
345 if ( !Map_NodeIsAnd(pNode) )
346 continue;
347
348 // propagate required times of different phases of the node
349 // the ordering of phases does not matter since they are mapped independently
350 if ( pNode->pCutBest[0] && pNode->tRequired[0].Worst < MAP_FLOAT_LARGE )
351 Map_TimePropagateRequiredPhase( p, pNode, 0 );
352 if ( pNode->pCutBest[1] && pNode->tRequired[1].Worst < MAP_FLOAT_LARGE )
353 Map_TimePropagateRequiredPhase( p, pNode, 1 );
354 }
355 /*
356 // in the end, we verify the required times
357 // for this, we compute the arrival times of the outputs of each phase
358 // of the supergates using the fanins' required times as the fanins' arrival times
359 // the resulting arrival time of the supergate should be less than the actual required time
360 for ( k = p->vMapObjs->nSize - 1; k >= 0; k-- )
361 {
362 pNode = p->vMapObjs->pArray[k];
363 if ( pNode->nRefAct[2] == 0 )
364 continue;
365 if ( !Map_NodeIsAnd(pNode) )
366 continue;
367 // verify that the required times are propagated correctly
368 // if ( pNode->pCutBest[0] && (pNode->nRefAct[0] > 0 || pNode->pCutBest[1] == NULL) )
369 if ( pNode->pCutBest[0] && pNode->tRequired[0].Worst < MAP_FLOAT_LARGE/2 )
370 {
371 Map_MatchComputeReqTimes( pNode->pCutBest[0], 0, ptReqOutTest );
372 // assert( ptReqOutTest->Rise < pNode->tRequired[0].Rise + p->fEpsilon );
373 // assert( ptReqOutTest->Fall < pNode->tRequired[0].Fall + p->fEpsilon );
374 }
375 // if ( pNode->pCutBest[1] && (pNode->nRefAct[1] > 0 || pNode->pCutBest[0] == NULL) )
376 if ( pNode->pCutBest[1] && pNode->tRequired[1].Worst < MAP_FLOAT_LARGE/2 )
377 {
378 Map_MatchComputeReqTimes( pNode->pCutBest[1], 1, ptReqOutTest );
379 // assert( ptReqOutTest->Rise < pNode->tRequired[1].Rise + p->fEpsilon );
380 // assert( ptReqOutTest->Fall < pNode->tRequired[1].Fall + p->fEpsilon );
381 }
382 }
383 */
384 }
Map_TimeComputeRequiredGlobal(Map_Man_t * p)385 void Map_TimeComputeRequiredGlobal( Map_Man_t * p )
386 {
387 int fUseConMan = Scl_ConIsRunning() && Scl_ConHasOutReqs();
388 Map_Time_t * ptTime, * ptTimeA;
389 int fPhase, i;
390 // update the required times according to the target
391 p->fRequiredGlo = Map_TimeComputeArrivalMax( p );
392 if ( p->DelayTarget != -1 )
393 {
394 if ( p->fRequiredGlo > p->DelayTarget + p->fEpsilon )
395 {
396 if ( p->fMappingMode == 1 )
397 printf( "Cannot meet the target required times (%4.2f). Continue anyway.\n", p->DelayTarget );
398 }
399 else if ( p->fRequiredGlo < p->DelayTarget - p->fEpsilon )
400 {
401 if ( p->fMappingMode == 1 && p->fVerbose )
402 printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->fRequiredGlo, p->DelayTarget );
403 p->fRequiredGlo = p->DelayTarget;
404 }
405 }
406 // clean the required times
407 for ( i = 0; i < p->vMapObjs->nSize; i++ )
408 {
409 p->vMapObjs->pArray[i]->tRequired[0].Rise = MAP_FLOAT_LARGE;
410 p->vMapObjs->pArray[i]->tRequired[0].Fall = MAP_FLOAT_LARGE;
411 p->vMapObjs->pArray[i]->tRequired[0].Worst = MAP_FLOAT_LARGE;
412 p->vMapObjs->pArray[i]->tRequired[1].Rise = MAP_FLOAT_LARGE;
413 p->vMapObjs->pArray[i]->tRequired[1].Fall = MAP_FLOAT_LARGE;
414 p->vMapObjs->pArray[i]->tRequired[1].Worst = MAP_FLOAT_LARGE;
415 }
416 // set the required times for the POs
417 for ( i = 0; i < p->nOutputs; i++ )
418 {
419 fPhase = !Map_IsComplement(p->pOutputs[i]);
420 ptTime = Map_Regular(p->pOutputs[i])->tRequired + fPhase;
421 ptTimeA = Map_Regular(p->pOutputs[i])->tArrival + fPhase;
422
423 if ( fUseConMan )
424 {
425 float Value = Scl_ConGetOutReqFloat(i);
426 // if external required time can be achieved, use it
427 if ( Value > 0 && ptTimeA->Worst <= Value )//&& Value <= p->fRequiredGlo )
428 ptTime->Rise = ptTime->Fall = ptTime->Worst = Value;
429 // if external required cannot be achieved, set the earliest possible arrival time
430 else if ( Value > 0 && ptTimeA->Worst > Value )
431 ptTime->Rise = ptTime->Fall = ptTime->Worst = ptTimeA->Worst;
432 // otherwise, set the global required time
433 else
434 ptTime->Rise = ptTime->Fall = ptTime->Worst = p->fRequiredGlo;
435 }
436 else
437 {
438 // if external required time can be achieved, use it
439 if ( p->pOutputRequireds && p->pOutputRequireds[i].Worst > 0 && ptTimeA->Worst <= p->pOutputRequireds[i].Worst )//&& p->pOutputRequireds[i].Worst <= p->fRequiredGlo )
440 ptTime->Rise = ptTime->Fall = ptTime->Worst = p->pOutputRequireds[i].Worst;
441 // if external required cannot be achieved, set the earliest possible arrival time
442 else if ( p->pOutputRequireds && p->pOutputRequireds[i].Worst > 0 && ptTimeA->Worst > p->pOutputRequireds[i].Worst )
443 ptTime->Rise = ptTime->Fall = ptTime->Worst = ptTimeA->Worst;
444 // otherwise, set the global required time
445 else
446 ptTime->Rise = ptTime->Fall = ptTime->Worst = p->fRequiredGlo;
447 }
448 }
449 // visit nodes in the reverse topological order
450 Map_TimePropagateRequired( p );
451 }
452
453 ////////////////////////////////////////////////////////////////////////
454 /// END OF FILE ///
455 ////////////////////////////////////////////////////////////////////////
456
457
458 ABC_NAMESPACE_IMPL_END
459
460