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