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