source: vis_dev/vis-2.3/src/spfd/spfdOpt.c @ 54

Last change on this file since 54 was 14, checked in by cecile, 13 years ago

vis2.3
File size: 42.3 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [spfdOpt.c]
4
5  PackageName [spfd]
6
7  Synopsis [Routines that implement spfd_pilo.]
8
9  Description [Routines that implement spfd_pilo.]
10
11  SeeAlso     [spfdCmd.c spfdReg.c spfdProg.c]
12
13  Author      [Balakrishna Kumthekar]
14
15  Copyright [This file was created at the University of Colorado at Boulder.
16  The University of Colorado at Boulder makes no warranty about the suitability
17  of this software for any purpose.  It is presented on an AS IS basis.]
18
19******************************************************************************/
20
21#include "spfdInt.h"
22
23/*---------------------------------------------------------------------------*/
24/* Constant declarations                                                     */
25/*---------------------------------------------------------------------------*/
26
27
28/*---------------------------------------------------------------------------*/
29/* Type declarations                                                         */
30/*---------------------------------------------------------------------------*/
31
32
33/*---------------------------------------------------------------------------*/
34/* Structure declarations                                                    */
35/*---------------------------------------------------------------------------*/
36
37
38/*---------------------------------------------------------------------------*/
39/* Variable declarations                                                     */
40/*---------------------------------------------------------------------------*/
41
42
43/*---------------------------------------------------------------------------*/
44/* Macro declarations                                                        */
45/*---------------------------------------------------------------------------*/
46
47
48/**AutomaticStart*************************************************************/
49
50/*---------------------------------------------------------------------------*/
51/* Static function prototypes                                                */
52/*---------------------------------------------------------------------------*/
53
54static int CompareConvexFanoutCountAndDepth(const void *obj1, const void *obj2);
55static int CompareConvexSwitchedCapAndDepth(const void *obj1, const void *obj2);
56
57/**AutomaticEnd***************************************************************/
58
59
60/*---------------------------------------------------------------------------*/
61/* Definition of exported functions                                          */
62/*---------------------------------------------------------------------------*/
63
64
65/*---------------------------------------------------------------------------*/
66/* Definition of internal functions                                          */
67/*---------------------------------------------------------------------------*/
68/**Function********************************************************************
69
70  Synopsis [Optimize the network by performing wire/node removal, wire
71  replacement and LUT reprogramming to reduce the number of wires and
72  nodes and the overall switching activity of the circuit.]
73
74  Description [Optimize the network by performing wire/node removal,
75  wire replacement and LUT reprogramming to reduce the number of wires
76  and nodes and the overall switching activity of the circuit. The
77  algorithm iteratively selects a node, 'maxNode', (based on the
78  heuristic selected) and examines all the fanout/fanin wires to determine
79  if any one them can be removed or replaced by another wire. For each
80  wire selected, fanout cluster if computed up to a depth
81  'regionDepth'. SPFD are computed only for these cluster nodes. Any
82  wire, internal to the cluster, that has an empty SPFD is
83  removed. Cluster nodes are then reprogrammed by choosing an
84  alternative implementation derived from the node SPFD.
85
86  After the cluster nodes are optimized, 'maxNode' is locked and is not
87  optimized in future iterations. The algorithm ends when there are no
88  more nodes to be optimized.
89
90  The argument 'simFile' (if not NULL) specifies the vectors used to
91  simulate the circuit in order to compute circuit node switching
92  activity. Vector simulations are performed every 'frequency'
93  iterations. 'regionDepth' specifies the depth of the cluster from
94  the 'maxNode'.]
95 
96  SideEffects [None]
97
98******************************************************************************/
99int
100SpfdNetworkOptimize(
101  Ntk_Network_t *network,
102  char *simFile,
103  int percent,
104  int frequency,
105  int regionDepth)
106{
107  SpfdApplData_t *applData;
108  Ntk_Node_t *node,*maxNode;
109  int stop,iter,status;
110  float randomValue;
111  array_t *nodeArray;
112  lsGen gen;
113  st_generator *stGen;
114  char *dummy;
115  boolean replRem;
116  array_t *inputArray,*patternArray,*intPatternArray;
117  char *optName;
118 
119  /* To keep the compiler happy */
120  inputArray = patternArray = intPatternArray = NIL(array_t);
121
122  /* Check if both wire removal and replacement are to be done */
123  optName = Cmd_FlagReadByName("spfd_repl_rem");
124  if (optName && (strcmp(optName,"yes") == 0)) {
125    replRem = TRUE;
126  } else {
127    replRem = FALSE;
128  }
129
130  /* First initialize the simulation package. This will also levelize
131     the nodes in the network. The level info is stored in local data
132     structure of 'truesim' package'. This is needed even if we do not
133     perform vector simulation. */
134  Truesim_InitializeSimulation(network,NIL(char),0,-1,0,NIL(st_table));
135  if (spfdPerfSim) { /* Perform simulation? */
136    /* Array of primary input nodes */
137    inputArray = array_alloc(Ntk_Node_t *,0);
138    /* Array of simulation vectors */
139    patternArray = array_alloc(char *,0);
140    status = Truesim_ReadSimulationVectors(network,simFile,
141                                           inputArray,patternArray);
142    /* Error while reading simulation vectors */
143    if (!status) {
144      array_free(inputArray);
145      array_free(patternArray);
146      (void) fprintf(vis_stdout, "** spfd error: Error reading simulation"
147                     " vector file. \n");
148      return 0;
149    }
150    Truesim_ZeroDelayPatternSimulate(network,inputArray,patternArray);
151
152    /* Select a random start for the set of internal simulation
153       vectors. We simulate only a portion of vectors (during
154       optimization iterations) to get a coarse estimate of circuit
155       node switching activities. */
156    randomValue = ((double)util_random()/(double)(MODULUS1 - 2));
157    if (randomValue > (double) (1.0 - ((double)percent)/((double)100)))
158      randomValue = (1.0 - ((double)percent)/((double)100))/2.0;
159    /* Partial set of simulation vectors */
160    intPatternArray = SpfdFetchInternalPatternArray(patternArray,percent,
161                                                    randomValue);
162  }
163 
164  /* Initialize the package application data structure */
165  applData = SpfdInitializeApplData(network);
166  iter = 1;
167
168  do {
169    if (spfdVerbose > 2) {
170      (void) fprintf(vis_stdout, "** spfd info: Iteration %d\n",iter);
171    }
172    nodeArray = array_alloc(Ntk_Node_t *,0);
173
174    /* Collect circuit nodes, later needed to be sorted. Only the
175       internal nodes will be sorted.*/
176    switch (spfdMethod) {
177    case REDUCE_FANIN_WIRES:
178    case OPTIMIZE_MAX_NODE:
179      Ntk_NetworkForEachNode(network,gen,node) {
180        if (!Ntk_NodeTestIsPrimaryOutput(node) &&
181            !Ntk_NodeTestIsPrimaryInput(node) &&
182            !SpfdNodeReadLocked(applData,node)) 
183          array_insert_last(Ntk_Node_t *,nodeArray,node);
184      }
185      break;
186    case OPTIMIZE_FANIN_NODES:
187      Ntk_NetworkForEachNode(network,gen,node) {
188        if (!Ntk_NodeTestIsPrimaryInput(node) &&
189            !SpfdNodeReadLocked(applData,node)) 
190          array_insert_last(Ntk_Node_t *,nodeArray,node);
191      }
192      break;
193    case REDUCE_FANOUT_WIRES:
194      Ntk_NetworkForEachNode(network,gen,node) {
195        if (!SpfdNodeReadLocked(applData,node)) 
196          array_insert_last(Ntk_Node_t *,nodeArray,node);
197      }
198      break;
199    }
200   
201    /* Find the node with max. fanout/switched cap., or a random node */
202    maxNode = SpfdFindNode(network,nodeArray);
203    if (!maxNode)
204      stop = 1;
205    else 
206      stop = 0;
207    array_free(nodeArray);
208   
209    /* Optimize. */
210    if (!stop) {
211      switch (spfdMethod) {
212      case REDUCE_FANIN_WIRES:
213        SpfdOptimizeFaninWires(network,maxNode,regionDepth,replRem);
214        break;
215      case OPTIMIZE_MAX_NODE:
216        SpfdOptimizeNode(network,maxNode,regionDepth);
217        break;
218      case OPTIMIZE_FANIN_NODES:
219        SpfdOptimizeFaninNodes(network,maxNode,regionDepth);
220        break;
221      case REDUCE_FANOUT_WIRES:
222        SpfdOptimizeFanoutWires(network,maxNode,regionDepth,replRem);
223        break;
224      }
225      /* If the network has changed (structurally), update the depth
226         information to reflect the change in the network.*/
227      if (spfdNtkChanged) {
228        Truesim_NetworkUpdateNodeTopologicalDepth(network);
229        spfdNtkChanged = FALSE;
230      }
231      if (spfdPerfSim && (iter % frequency == 0)) {
232        Truesim_ZeroDelayPatternSimulate(network,inputArray,intPatternArray);
233      }
234    }
235    iter++;
236  } while (!stop);
237 
238  if (spfdPerfSim) {
239    /* End simulation; free memory */
240    Truesim_QuitSimulation(network);
241    array_free(inputArray);
242    array_free(patternArray);
243  }
244 
245  /* Print the number of wires removed and delete the sinkTable. */
246  fprintf(vis_stdout,"** spfd info: # of wires removed = %d\n",
247          spfdNumWiresRem - spfdWiresAdded);
248  fprintf(vis_stdout,"** spfd info: # of nodes removed = %d\n",
249          st_count(applData->nodesRemoved));
250
251  /* Free the memory for each node */
252  st_foreach_item(applData->nodesRemoved,stGen,&node,&dummy) {
253    if (node) Ntk_NodeFree(node);
254  }
255 
256  return 1;
257 
258} /* End of SpfdNetworkOptimize */
259
260#if 0
261/**Function********************************************************************
262
263  Synopsis [Optimize the cluster of nodes in the fanout of each fanout
264  wire of maxNode. The cluster is formed of those nodes that are
265  within 'regionDepth' of the fanout wire. Both wire removal and
266  replacement are performed if 'replRem' is true.]
267
268  SideEffects        [None]
269
270******************************************************************************/
271void
272SpfdProcessFanoutWires(
273  Ntk_Network_t *network,
274  Ntk_Node_t *maxNode,
275  int regionDepth,
276  boolean replRem)
277{
278  SpfdApplData_t *applData;
279  array_t *fanoutArray,*replArray;
280  st_table *wiresRemoved,*sinkTable;
281  st_generator *stGen;
282  Ntk_Node_t *ntkNode,*tempNode,*replNode;
283  int i,num;
284
285  /* Package application data structure */
286  applData = Ntk_NetworkReadApplInfo(network,SPFD_NETWORK_APPL_KEY);
287
288  fanoutArray = array_dup(Ntk_NodeReadFanouts(maxNode));
289  for (i = array_n(fanoutArray) - 1; i >=0; i--) {
290    ntkNode = array_fetch(Ntk_Node_t *,fanoutArray,i);
291   
292    /* Skip POs */
293    if (Ntk_NodeTestIsPrimaryOutput(ntkNode))
294      continue;
295
296    /* Could be removed during an earlier iteration */
297    if (!st_lookup(applData->nodesRemoved,(char *)ntkNode,NIL(char *))) {
298      array_t *regionArray;
299 
300      /* regionArray is an array of nodes sorted according to their depth. */
301      regionArray = SpfdNodeComputeFanoutRegion(applData,ntkNode,regionDepth);
302
303      /* Analyze region's BDD requirements */
304      SpfdComputeRequiredGlobalBdds(network,applData);
305
306      /* Analyze auxilarry BDD ID requirements */
307      SpfdAllocateOrReuseAuxVariables(network,applData);
308
309      /* Order the fanin of internal and boundary nodes */
310      if (spfdPerfSim) {
311        SpfdOrderFaninOfRegionNodes(network,applData,
312                                    SpfdSwitchedCapAndDepthCompare);
313      } else {
314        SpfdOrderFaninOfRegionNodes(network,applData,
315                                    SpfdFanoutCountAndDepthCompare);
316      }
317   
318      /* Set the spfds for nodes in the region. The spfds are reduced to a
319         single pair and the localAlt is set to one of the components of the
320         single pair SPFD. */
321      SpfdRegionComputeSinglePairSpfd(network,applData,regionArray);
322
323      /* Now check if the spfd of wire maxNode --> ntkNode is
324         empty. Remove the spfd of ntkNode as it was not deleted in
325         SpfdRegionComputeSinglePairSpfd */
326      /* Compute array of potential candidates for replacement */
327      if (replRem)
328        replArray = SpfdNodeComputeTFIUntilDepth(ntkNode,regionDepth);
329      else
330        replArray = NIL(array_t);
331      replNode = SpfdCheckIfWireIsRedundantOrReplaceable(network,applData,
332                                                         maxNode,ntkNode,
333                                                         replArray);
334      /* No longer needed. */
335      SpfdNodeDeleteSpfd(applData,ntkNode);
336      if (replArray)
337        array_free(replArray);
338     
339      /* Check to see if wires have been found to be
340         redundant/replaceable. If no wires are to be
341         removed/replaced, then decide whether or not to reprogram. */
342      if (st_count(applData->currWireTable) == 0 &&
343          st_count(applData->currReplaceTable) == 0 &&
344          !spfdReprogNoWire) {
345        /* In this case just clean up currBddReq, localAlt
346           and globalAlt. */
347        st_table *currBddReq;
348        st_generator *stGen;
349        Ntk_Node_t *regNode;
350        bdd_node *bdd1;
351        bdd_manager *ddManager;
352        int j;
353
354        ddManager = applData->ddManager;
355        currBddReq = applData->currBddReq;
356       
357        /* Clean up currBddReq */
358        st_foreach_item(currBddReq,stGen,(char **)&regNode,(char **)&bdd1) {
359          bdd_recursive_deref(ddManager,bdd1);
360        }
361        st_free_table(currBddReq);
362        applData->currBddReq = NIL(st_table);
363
364        /* Clean up localAlt and globalAlt of region nodes */
365        arrayForEachItem(Ntk_Node_t *,regionArray,j,regNode) {
366          SpfdNodeDeleteGlobalAlternative(applData,regNode);
367          SpfdNodeDeleteLocalAlt(applData,regNode);
368        }
369      } else {
370        /* Now reprogram the nodes in the region. */
371        SpfdReprogramRegionNodes(network,applData,regionArray);
372      }
373
374      /* In this subroutine we have only a single wire
375         replaced. Delete just that data */
376      if (replNode) {
377        SpfdNodeDeleteGlobalAlternative(applData,replNode);
378        SpfdNodeSetAuxId(applData,replNode,-1);
379        st_delete(applData->currReplaceTable,(char **)&ntkNode,
380                  (char **)&sinkTable);
381        st_free_table(sinkTable);
382       
383        /* A small caveat: sometimes a wire added can be later
384           removed. Check if the replNode --> ntkNode still exists. If
385           not set replNode to NULL. */
386        wiresRemoved = applData->wiresRemoved;
387        if (st_lookup(wiresRemoved,(char *)replNode,(char **)&sinkTable) &&
388            st_lookup(sinkTable,(char *)ntkNode,NIL(char *))) {
389          /* Reduce the number of wires added and delete
390             replNode->ntkNode from wiresRemoved table */
391          spfdWiresAdded--;
392          st_delete(sinkTable,(char **)&ntkNode,NIL(char *));
393          if (st_count(sinkTable) < 1) {
394            st_delete(wiresRemoved,(char **)&replNode,(char **)&sinkTable);
395            st_free_table(sinkTable);
396          }
397          replNode = NIL(Ntk_Node_t);
398        }
399      }
400     
401      /* Clean up auxIds and piAltVars*/
402      SpfdCleanUpAuxIds(applData);
403     
404      /* Free stuff used only for the current iteration */
405      if (applData->currXCube) {
406        bdd_recursive_deref(applData->ddManager,applData->currXCube);
407        applData->currXCube = NIL(bdd_node);
408      }
409      if (applData->currRegionNodes) {
410        st_free_table(applData->currRegionNodes);
411        applData->currRegionNodes = NIL(st_table);
412      }
413      if (applData->currInUseVars) {
414        st_free_table(applData->currInUseVars);
415        applData->currInUseVars = NIL(st_table);
416      }
417
418      num = st_count(applData->currWireTable);
419      assert(num == 0);
420
421      num = st_count(applData->currReplaceTable);
422      assert(num == 0);
423     
424      /* Update the total number of wires removed */
425      wiresRemoved = applData->wiresRemoved;
426      if (st_count(wiresRemoved) > 0) {
427        st_foreach_item(wiresRemoved,stGen,(char **)&tempNode,
428                        (char **)&sinkTable){
429          spfdNumWiresRem += st_count(sinkTable);
430        }
431       
432        /* free the wiresRemoved contents */
433        st_foreach(wiresRemoved,SpfdStTableClean,NIL(char));
434      }
435     
436      /* Free regionArray (cluster) */
437      array_free(regionArray);
438    }
439  }
440  array_free(fanoutArray);
441 
442  /* Lock the node */
443  SpfdNodeSetLocked(applData,maxNode,TRUE);
444 
445} /* End of SpfdProcessFanoutWires */
446#endif
447
448/**Function********************************************************************
449
450  Synopsis [Checks if the SPFD for 'from' --> 'to' is empty. If yes,
451  the wire is removed. If not, nodes in 'replaceArray' are examined to
452  check for replacability. If a node is found, that node is returned.]
453
454  SideEffects        [None]
455
456******************************************************************************/
457Ntk_Node_t *
458SpfdCheckIfWireIsRedundantOrReplaceable(
459  Ntk_Network_t *network,
460  SpfdApplData_t *applData,
461  Ntk_Node_t *from,
462  Ntk_Node_t *to,
463  array_t *replaceArray)
464{
465  bdd_manager *ddManager = applData->ddManager;
466  bdd_node *result,*ddTemp,*ddTemp2,*var,*varAux;
467  bdd_node *toSpfd,*wireSpfd,*logicZero;
468  int i,index;
469  Ntk_Node_t *fanin,*tempNode,*replNode;
470  st_table *wireTable = applData->currWireTable;
471  st_table *wiresRemoved = applData->wiresRemoved;
472  st_table *sinkTable;
473
474  /* Possible replacement node */
475  replNode = NIL(Ntk_Node_t);
476  logicZero = bdd_read_logic_zero(ddManager);
477
478  /* Check if this wire has already been removed. */
479  if (!(st_lookup(wiresRemoved,(char *)from,&sinkTable) &&
480      st_lookup(sinkTable,(char *)to,&tempNode))) {
481 
482    bdd_ref(result = bdd_read_one(ddManager));
483
484    /* Compute the characteristic function of pairs of minterms cannot
485       be distinguished any fanin of 'to'. Let f_i be the ith fanin of
486       'to'. We compute result = \prod f_i == f'_i, where f_i != from */
487    Ntk_NodeForEachFanin(to,i,fanin) {
488      var = bdd_bdd_ith_var(ddManager,Ntk_NodeReadMddId(fanin));
489      index = SpfdNodeReadAuxId(applData,fanin);
490      varAux = bdd_bdd_ith_var(ddManager,index);
491     
492      if (fanin != from) {
493        bdd_ref(ddTemp = bdd_bdd_xnor(ddManager,var,varAux)); /* XNOR */
494        bdd_ref(ddTemp2 = bdd_bdd_and(ddManager,result,ddTemp));
495        bdd_recursive_deref(ddManager,result);
496        bdd_recursive_deref(ddManager,ddTemp);
497        result = ddTemp2;
498      }
499    }
500    /* Finally put in f_i == f_i', where f_i = from) */
501    var = bdd_bdd_ith_var(ddManager,Ntk_NodeReadMddId(from));
502    index = SpfdNodeReadAuxId(applData,from);
503    varAux = bdd_bdd_ith_var(ddManager,index);
504    bdd_ref(ddTemp = bdd_bdd_xor(ddManager,var,varAux));
505    bdd_ref(ddTemp2 = bdd_bdd_and(ddManager,result,ddTemp));
506    bdd_recursive_deref(ddManager,result);
507    bdd_recursive_deref(ddManager,ddTemp);
508    result = ddTemp2;
509
510    /* Compute AND of result and the SPFD of 'to'. */
511    toSpfd = SpfdNodeReadSpfd(applData,to);
512    if (toSpfd == NIL(bdd_node)) {
513      (void) fprintf(vis_stderr,
514                     "** spfd error: Spfd expected but not found.\n");
515      exit(0);
516    }
517    bdd_ref(wireSpfd = bdd_bdd_and(ddManager,toSpfd,result));
518    bdd_recursive_deref(ddManager,result);
519
520    if (wireSpfd == logicZero) { /* Can the wire be removed? */
521      if (spfdVerbose > 1)
522        (void) fprintf(vis_stdout,
523                       "** spfd info: Target wire %s --> %s has empty spfd.\n",
524                       Ntk_NodeReadName(from),Ntk_NodeReadName(to));
525
526      /* Insert the wire into wireTable */
527      if (st_lookup(wireTable,(char *)from,&sinkTable)) {
528        st_insert(sinkTable,(char *)to,(char *)to);
529      } else {
530        sinkTable = st_init_table(st_ptrcmp,st_ptrhash);
531        st_insert(sinkTable,(char *)to,(char *)to);
532        st_insert(wireTable,(char *)from,(char *)sinkTable);
533      }
534      bdd_recursive_deref(ddManager,wireSpfd);
535    } else if (replaceArray != NIL(array_t)) {
536      /* Try for replacement. Exit after finding the first one. Here the
537         assumption is that the nodes are sorted according to some
538         criterion. */
539      replNode = SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd(network,replaceArray,
540                                                           from,to,wireSpfd);
541      bdd_recursive_deref(ddManager,wireSpfd);
542    } else {
543      bdd_recursive_deref(ddManager,wireSpfd);
544    }
545  }
546 
547  return replNode;
548 
549} /* End of SpfdCheckIfWireIsRedundantOrReplaceable */
550
551
552/**Function********************************************************************
553
554  Synopsis [Checks if the global functions implemented by nodes in
555  'replaceArray' satisfy the SPFD, 'wireSpfd' of 'from' --> 'to'.]
556
557  SideEffects        [None]
558
559******************************************************************************/
560Ntk_Node_t *
561SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd(
562  Ntk_Network_t *network,
563  array_t *replaceArray,
564  Ntk_Node_t *from,
565  Ntk_Node_t *to,
566  bdd_node *wireSpfd)
567{
568  SpfdApplData_t *applData;
569  bdd_manager *ddManager;
570  st_table *leavesTable,*inUseVars,*replaceTable;
571  st_table *sinkTable,*currBddReq;
572  bdd_t *mddOne;
573  lsGen gen;
574  Ntk_Node_t *fanin,*node,*replNode;
575  Ntk_Node_t *foundNode;
576  array_t *nodeMvfs,*nodeBdds;
577  bdd_node *bdd1,*xCube,*yVar;
578  bdd_node **tempVars,**firstCompose,**secondCompose;
579  bdd_node *step1,*step2,*step3,*step4,*step5;
580  bdd_node *logicZero;
581  int i,j,size,replId,id,auxId;
582 
583  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
584                                                        SPFD_NETWORK_APPL_KEY);
585  ddManager = applData->ddManager;
586  inUseVars = applData->currInUseVars;
587  replaceTable = applData->currReplaceTable;
588  currBddReq = applData->currBddReq;
589 
590  mddOne = bdd_one(ddManager);
591  logicZero = bdd_read_logic_zero(ddManager);
592 
593  /* Collect the leaf nodes of the network. */
594  leavesTable = st_init_table(st_ptrcmp, st_ptrhash);
595  Ntk_NetworkForEachCombInput(network,gen,node) {
596    st_insert(leavesTable,(char *)node,(char *) -1);
597  }
598
599  /* Compute the global MVFs of the nodes in replaceArray */
600  nodeMvfs = Ntm_NetworkBuildMvfs(network,replaceArray,leavesTable,mddOne);
601  bdd_free(mddOne);
602  st_free_table(leavesTable);
603
604  /* Collect node global Bdds */
605  nodeBdds = array_alloc(bdd_node *,0);
606  arrayForEachItem(Ntk_Node_t *,replaceArray,i,node) {
607    Mvf_Function_t *mvf;
608    mvf = array_fetch(Mvf_Function_t *,nodeMvfs,i);
609    bdd1 = bdd_extract_node_as_is(array_fetch(bdd_t *,mvf,1));
610    bdd_ref(bdd1);
611    array_insert_last(bdd_node *,nodeBdds,bdd1);
612  }
613  Mvf_FunctionArrayFree(nodeMvfs);
614
615  /* Now check one at a time if global function satisfies wireSpfd */
616  foundNode = NIL(Ntk_Node_t);
617  xCube = applData->currXCube;
618  arrayForEachItem(Ntk_Node_t *,nodeBdds,i,bdd1) {
619    int idAllocated;
620
621    idAllocated = 0;
622    replNode = array_fetch(Ntk_Node_t *,replaceArray,i);
623    replId = Ntk_NodeReadMddId(replNode);
624    /* Check if replId is already in use. This is possible is outside
625       the cluster. */
626    if (st_lookup(inUseVars,(char *)(long)replId,NIL(char *))) {
627      /* Allocate yVar and yAuxVar for replNode */
628      tempVars = SpfdAllocateTemporaryVariables(ddManager,inUseVars,1);
629      yVar = tempVars[0];
630      idAllocated = 1;
631      FREE(tempVars);
632    } else { /* replId not in use */
633      yVar = bdd_bdd_ith_var(ddManager,replId);
634    }
635
636    /* Now perform the following steps, using two compositions. */
637    /* 1. step1 = yVar == bdd1
638       2. step2 = wireSpfd(Y,Y') --> wireSpfd(x,Y')
639       3. step3 = \exists_x step1 * step2
640       4. step4 = step3(yVar,Y') --> step3(yVar,x)
641       5. step5 = \exists_x step1 * step4
642
643       If step5 == logicZero, then replNode is a candidate */
644
645    /* Prepare compose arrays for the above steps */
646    size = bdd_num_vars(ddManager);
647    firstCompose = ALLOC(bdd_node *,size);
648    secondCompose = ALLOC(bdd_node *,size);
649    for (j = 0; j < size; j++) {
650      firstCompose[j] = bdd_bdd_ith_var(ddManager,j);
651      secondCompose[j] = bdd_bdd_ith_var(ddManager,j);
652    }
653
654    Ntk_NodeForEachFanin(to,j,fanin) {
655      id = Ntk_NodeReadMddId(fanin);
656      auxId = SpfdNodeReadAuxId(applData,fanin);
657      st_lookup(currBddReq,(char *)fanin,(char **)&firstCompose[id]);
658      secondCompose[auxId] = firstCompose[id];
659    }
660
661    bdd_ref(step1 = bdd_bdd_xnor(ddManager,yVar,bdd1));
662    bdd_ref(step2 = bdd_bdd_vector_compose(ddManager,wireSpfd,firstCompose));
663    FREE(firstCompose);
664    bdd_ref(step3 = bdd_bdd_and_abstract(ddManager,step1,step2,xCube));
665    bdd_recursive_deref(ddManager,step2);
666    bdd_ref(step4 = bdd_bdd_vector_compose(ddManager,step3,secondCompose));
667    bdd_recursive_deref(ddManager,step3);
668    FREE(secondCompose);
669    bdd_ref(step5 = bdd_bdd_and_abstract(ddManager,step1,step4,xCube));
670    bdd_recursive_deref(ddManager,step4);
671    bdd_recursive_deref(ddManager,step1);
672
673    /* Now if step5 is zero, then return replNode as the candidate. I will use
674       the globalAlt field of the node to store the global BDD. This way I
675       don't have to recompute the global BDD later.  */
676    if (step5 == logicZero) {
677      bdd_recursive_deref(ddManager,step5);
678      bdd_ref(bdd1);
679      SpfdNodeSetGlobalAlternative(applData,replNode,bdd1);
680
681      /* Allocate an auxId for this node. It will be needed during
682         reprogramming. */
683      if (idAllocated) {
684        auxId = bdd_node_read_index(yVar);
685      } else {
686        tempVars = SpfdAllocateTemporaryVariables(ddManager,inUseVars,1);
687        auxId = bdd_node_read_index(tempVars[0]);
688        FREE(tempVars);
689      }
690      SpfdNodeSetAuxId(applData,replNode,auxId);
691      st_insert(inUseVars,(char *)(long)replId,(char *)-1);
692      st_insert(inUseVars,(char *)(long)auxId,(char *)-1);
693     
694      /* Insert information in replaceTable */
695      if (st_lookup(replaceTable,(char *)to,&sinkTable)) {
696        st_insert(sinkTable,(char *)from,(char *)replNode);
697      } else {
698        sinkTable = st_init_table(st_ptrcmp,st_ptrhash);
699        st_insert(sinkTable,(char *)from,(char *)replNode);
700        st_insert(replaceTable,(char *)to,(char *)sinkTable);
701      }
702      foundNode = replNode;
703      break;
704    } else {
705      bdd_recursive_deref(ddManager,step5);
706      /* release the id */
707      if (idAllocated) {
708        id = bdd_node_read_index(yVar);
709        st_delete(inUseVars, &id, NIL(char *));
710      }
711    }
712  }
713
714  /* Free the nodeBdds */
715  arrayForEachItem(bdd_node *,nodeBdds,i,bdd1) {
716    bdd_recursive_deref(ddManager,bdd1);
717  }
718  array_free(nodeBdds);
719
720  return foundNode;
721} /* End of SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd */
722
723
724/**Function********************************************************************
725
726  Synopsis           [Try to remove/replace the fanin wires of maxNode.]
727
728  SideEffects        [None]
729
730  SeeAlso            [SpfdOptimizeFanoutWires]
731
732******************************************************************************/
733void
734SpfdOptimizeFaninWires(
735  Ntk_Network_t *network,
736  Ntk_Node_t *maxNode,
737  int regionDepth,
738  boolean replRem)
739{
740  SpfdApplData_t *applData;
741  array_t *faninArray;
742  Ntk_Node_t *ntkNode,*fanout;
743  char *dummy;
744  int i,j;
745
746  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
747                                                        SPFD_NETWORK_APPL_KEY);
748 
749  /* replace/remove the fanin wire of maxNode one at a time. The fanin
750     node with higher switched capacitance will be optimized first. */
751  faninArray = array_dup(Ntk_NodeReadFanins(maxNode));
752  if (spfdPerfSim)
753    array_sort(faninArray,CompareConvexSwitchedCapAndDepth);
754  else
755    array_sort(faninArray,CompareConvexFanoutCountAndDepth);
756
757  for (i = array_n(faninArray) - 1; i >=0; i--) {
758    boolean skip;
759    ntkNode = array_fetch(Ntk_Node_t *,faninArray,i);
760    if (!st_lookup(applData->nodesRemoved,(char *)ntkNode,(char **)&dummy)) {
761      skip = TRUE;
762      /* Check if the current fanin node is still in the support of
763         maxNode. */
764      Ntk_NodeForEachFanout(ntkNode,j,fanout) {
765        if (fanout == maxNode) {
766          skip = FALSE;
767          break;
768        }
769      }
770    } else {
771      skip = TRUE;
772    }
773    if (!skip)
774      SpfdOptimizeWire(network,ntkNode,maxNode,regionDepth,replRem);
775  }
776  array_free(faninArray);
777
778  /* Lock the node */
779  SpfdNodeSetLocked(applData,maxNode,TRUE);
780 
781  return ;
782 
783} /* End of SpfdOptimizeFaninWires */
784
785
786/**Function********************************************************************
787
788  Synopsis           [Try to remove/replace the fanout wires of maxNode.]
789
790  SideEffects        [None]
791
792  SeeAlso            [SpfdOptimizeFaninWires]
793
794******************************************************************************/
795void
796SpfdOptimizeFanoutWires(
797  Ntk_Network_t *network,
798  Ntk_Node_t *maxNode,
799  int regionDepth,
800  boolean replRem)
801{
802  SpfdApplData_t *applData;
803  array_t *fanoutArray;
804  Ntk_Node_t *ntkNode,*fanout;
805  int i,j;
806 
807  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
808                                                        SPFD_NETWORK_APPL_KEY);
809
810  /* replace/remove the fanout wires of maxNode one at a time. The fanout
811     node with higher switched capacitance will be optimized first. */
812  fanoutArray = array_dup(Ntk_NodeReadFanouts(maxNode));
813  if (spfdPerfSim)
814    array_sort(fanoutArray,CompareConvexSwitchedCapAndDepth);
815  else
816    array_sort(fanoutArray,CompareConvexFanoutCountAndDepth);
817
818
819  for (i = array_n(fanoutArray) - 1; i >=0; i--) {
820    boolean skip;
821    ntkNode = array_fetch(Ntk_Node_t *,fanoutArray,i);
822    skip = TRUE;
823    /* Check if the maxNode is still in the support of fanout. */
824    Ntk_NodeForEachFanout(maxNode,j,fanout) {
825      if (fanout == ntkNode) {
826        skip = FALSE;
827        break;
828      }
829    }
830    if (!skip)   
831      SpfdOptimizeWire(network,maxNode,ntkNode,regionDepth,replRem);
832  }
833  array_free(fanoutArray);
834
835  /* Lock the node */
836  SpfdNodeSetLocked(applData,maxNode,TRUE);
837 
838  return ;
839 
840} /* End of SpfdOptimizeFanoutWires */
841
842
843/**Function********************************************************************
844
845  Synopsis           [Optimize all the fanin nodes of maxNode.]
846
847  SideEffects        [None]
848
849******************************************************************************/
850void
851SpfdOptimizeFaninNodes(
852  Ntk_Network_t *network,
853  Ntk_Node_t *maxNode,
854  int regionDepth)
855{
856  SpfdApplData_t *applData;
857  array_t *faninArray;
858  Ntk_Node_t *ntkNode;
859  char *dummy;
860  int i;
861
862  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
863                                                        SPFD_NETWORK_APPL_KEY);
864
865  /* Optimize fanin nodes one at a time. The fanin node with higher
866     switched capacitance will be optimized first. */
867  faninArray = array_dup(Ntk_NodeReadFanins(maxNode));
868  if (spfdPerfSim)
869    array_sort(faninArray,CompareConvexSwitchedCapAndDepth);
870  else
871    array_sort(faninArray,CompareConvexFanoutCountAndDepth);
872
873  for (i = array_n(faninArray) - 1; i >=0; i--) {
874    boolean skip = FALSE;
875    ntkNode = array_fetch(Ntk_Node_t *,faninArray,i);
876    if (st_lookup(applData->nodesRemoved,(char *)ntkNode,(char **)&dummy)) {
877      skip = TRUE;
878    }
879    if (!skip)
880      SpfdOptimizeNode(network,ntkNode,regionDepth);
881  }
882  array_free(faninArray);
883
884  /* Lock the node */
885  SpfdNodeSetLocked(applData,maxNode,TRUE);
886 
887  return ;
888 
889} /* End of SpfdOptimizeFaninNodes */
890
891
892/**Function********************************************************************
893
894  Synopsis [Optimize the cluster of nodes in the fanout the wire
895  maxNode --> ntkNode. The cluster is formed of those nodes that are
896  within 'regionDepth' of this wire. Both wire removal and replacement
897  are performed if 'replRem' is true.]
898
899  SideEffects        [None]
900
901******************************************************************************/
902void
903SpfdOptimizeWire(
904  Ntk_Network_t *network,
905  Ntk_Node_t *maxNode,
906  Ntk_Node_t *ntkNode,
907  int regionDepth,
908  boolean replRem)
909{
910  SpfdApplData_t *applData;
911  array_t *replArray;
912  st_table *wiresRemoved,*sinkTable;
913  st_generator *stGen;
914  Ntk_Node_t *tempNode,*replNode;
915  array_t *regionArray;
916  int num;
917
918  /* Package application data structure */
919  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
920                                                        SPFD_NETWORK_APPL_KEY);
921
922  /* Skip POs */
923  if (Ntk_NodeTestIsPrimaryOutput(ntkNode))
924    return;
925 
926  /* regionArray is an array of nodes sorted according to their depth. */
927  regionArray = SpfdNodeComputeFanoutRegion(applData,ntkNode,regionDepth);
928
929  /* Analyze region's BDD requirements */
930  SpfdComputeRequiredGlobalBdds(network,applData);
931 
932  /* Analyze auxilarry BDD ID requirements */
933  SpfdAllocateOrReuseAuxVariables(network,applData);
934 
935  /* Order the fanin of internal and boundary nodes */
936  if (spfdPerfSim) {
937    SpfdOrderFaninOfRegionNodes(network,applData,
938                                SpfdSwitchedCapAndDepthCompare);
939  } else {
940    SpfdOrderFaninOfRegionNodes(network,applData,
941                                SpfdFanoutCountAndDepthCompare);
942  }
943   
944  /* Set the spfds for nodes in the region. The spfds are reduced to a
945     single pair and the localAlt is set to one of the components of the
946     single pair SPFD. */
947  SpfdRegionComputeSinglePairSpfd(network,applData,regionArray);
948 
949  /* Now check if the spfd of wire maxNode --> ntkNode is
950     empty. Remove the spfd of ntkNode as it was not deleted in
951     SpfdRegionComputeSinglePairSpfd */
952  /* Compute array of potential candidates for replacement */
953  if (replRem)
954    replArray = SpfdNodeComputeTFIUntilDepth(ntkNode,regionDepth);
955  else
956    replArray = NIL(array_t);
957  replNode = SpfdCheckIfWireIsRedundantOrReplaceable(network,applData,
958                                                     maxNode,ntkNode,
959                                                     replArray);
960  /* SPFD of ntkNode is no longer needed. */
961  SpfdNodeDeleteSpfd(applData,ntkNode);
962  if (replArray)
963    array_free(replArray);
964     
965  /* Check to see if wires have been found to be
966     redundant/replaceable. If no wires are to be
967     removed/replaced, then decide whether or not to reprogram. */
968  if (st_count(applData->currWireTable) == 0 &&
969      st_count(applData->currReplaceTable) == 0 &&
970      !spfdReprogNoWire) {
971    /* In this case just clean up currBddReq, localAlt
972       and globalAlt. */
973    st_table *currBddReq;
974    st_generator *stGen;
975    Ntk_Node_t *regNode;
976    bdd_node *bdd1;
977    bdd_manager *ddManager;
978    int j;
979   
980    ddManager = applData->ddManager;
981    currBddReq = applData->currBddReq;
982   
983    /* Clean up currBddReq */
984    st_foreach_item(currBddReq,stGen,&regNode,&bdd1) {
985      bdd_recursive_deref(ddManager,bdd1);
986    }
987    st_free_table(currBddReq);
988    applData->currBddReq = NIL(st_table);
989   
990    /* Clean up localAlt and globalAlt of region nodes */
991    arrayForEachItem(Ntk_Node_t *,regionArray,j,regNode) {
992      SpfdNodeDeleteGlobalAlternative(applData,regNode);
993      SpfdNodeDeleteLocalAlt(applData,regNode);
994    }
995  } else {
996    /* Now reprogram the nodes in the region. */
997    SpfdReprogramRegionNodes(network,applData,regionArray);
998  }
999 
1000  /* In this subroutine we have only a single wire
1001     replaced. Delete just that data */
1002  if (replNode) {
1003    SpfdNodeDeleteGlobalAlternative(applData,replNode);
1004    SpfdNodeSetAuxId(applData,replNode,-1);
1005    st_delete(applData->currReplaceTable,&ntkNode,
1006              &sinkTable);
1007    st_free_table(sinkTable);
1008   
1009    /* A small caveat: sometimes a wire added can be later
1010       removed. Check if the replNode --> ntkNode still exists. If
1011       not set replNode to NULL. */
1012    wiresRemoved = applData->wiresRemoved;
1013    if (st_lookup(wiresRemoved,(char *)replNode,&sinkTable) &&
1014        st_lookup(sinkTable,(char *)ntkNode,NIL(char *))) {
1015      /* Reduce the number of wires added and delete
1016         replNode->ntkNode from wiresRemoved table */
1017      spfdWiresAdded--;
1018      st_delete(sinkTable,&ntkNode,NIL(char *));
1019      if (st_count(sinkTable) < 1) {
1020        st_delete(wiresRemoved,&replNode,&sinkTable);
1021        st_free_table(sinkTable);
1022      }
1023      replNode = NIL(Ntk_Node_t);
1024    }
1025  }
1026     
1027  /* Clean up auxIds and piAltVars*/
1028  SpfdCleanUpAuxIds(applData);
1029 
1030  /* Free stuff used only for the current wire */
1031  if (applData->currXCube) {
1032    bdd_recursive_deref(applData->ddManager,applData->currXCube);
1033    applData->currXCube = NIL(bdd_node);
1034  }
1035  if (applData->currRegionNodes) {
1036    st_free_table(applData->currRegionNodes);
1037    applData->currRegionNodes = NIL(st_table);
1038  }
1039  if (applData->currInUseVars) {
1040    st_free_table(applData->currInUseVars);
1041    applData->currInUseVars = NIL(st_table);
1042  }
1043 
1044  num = st_count(applData->currWireTable);
1045  assert(num == 0);
1046 
1047  num = st_count(applData->currReplaceTable);
1048  assert(num == 0);
1049 
1050  /* Update the total number of wires removed. */
1051  wiresRemoved = applData->wiresRemoved;
1052  if (st_count(wiresRemoved) > 0) {
1053    st_foreach_item(wiresRemoved,stGen,&tempNode,
1054                    &sinkTable){
1055      spfdNumWiresRem += st_count(sinkTable);
1056    }
1057   
1058    /* free the wiresRemoved contents */
1059    st_foreach(wiresRemoved,SpfdStTableClean,NIL(char));
1060  }
1061 
1062  /* Free regionArray (cluster) */
1063  array_free(regionArray);
1064 
1065  return ;
1066 
1067} /* End of SpfdOptimizeWire */
1068
1069
1070/**Function********************************************************************
1071
1072  Synopsis [Optimize the ntkNode. This is done by computing its SPFD
1073  derived from the output cluster. The cluster is formed of those
1074  nodes that are within 'regionDepth' in the fanout of ntkNode. Both
1075  wire removal and replacement are performed if 'replRem' is true.]
1076
1077  SideEffects        [None]
1078
1079******************************************************************************/
1080void
1081SpfdOptimizeNode(
1082  Ntk_Network_t *network,
1083  Ntk_Node_t *ntkNode,
1084  int regionDepth)
1085{
1086  SpfdApplData_t *applData;
1087  st_table *wiresRemoved,*sinkTable;
1088  st_generator *stGen;
1089  Ntk_Node_t *tempNode;
1090  array_t *regionArray;
1091  int num;
1092
1093  /* Package application data structure */
1094  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
1095                                                        SPFD_NETWORK_APPL_KEY);
1096
1097  /* Skip POs */
1098  if (Ntk_NodeTestIsPrimaryOutput(ntkNode))
1099    return;
1100 
1101  /* regionArray is an array of nodes sorted according to their depth. */
1102  regionArray = SpfdNodeComputeFanoutRegion(applData,ntkNode,regionDepth);
1103
1104  /* Analyze region's BDD requirements */
1105  SpfdComputeRequiredGlobalBdds(network,applData);
1106 
1107  /* Analyze auxilarry BDD ID requirements */
1108  SpfdAllocateOrReuseAuxVariables(network,applData);
1109 
1110  /* Order the fanin of internal and boundary nodes */
1111  if (spfdPerfSim) {
1112    SpfdOrderFaninOfRegionNodes(network,applData,
1113                                SpfdSwitchedCapAndDepthCompare);
1114  } else {
1115    SpfdOrderFaninOfRegionNodes(network,applData,
1116                                SpfdFanoutCountAndDepthCompare);
1117  }
1118   
1119  /* Set the spfds for nodes in the region. The spfds are reduced to a
1120     single pair and the localAlt is set to one of the components of the
1121     single pair SPFD. */
1122  SpfdRegionComputeSinglePairSpfd(network,applData,regionArray);
1123 
1124  /* Remove the spfd of ntkNode as it was not deleted in
1125     SpfdRegionComputeSinglePairSpfd */
1126
1127  /* SPFD of ntkNode is no longer needed. */
1128  SpfdNodeDeleteSpfd(applData,ntkNode);
1129     
1130  /* Check to see if wires have been found to be
1131     redundant/replaceable. If no wires are to be
1132     removed/replaced, then decide whether or not to reprogram. */
1133  if (st_count(applData->currWireTable) == 0 &&
1134      !spfdReprogNoWire) {
1135    /* In this case just clean up currBddReq, localAlt and
1136       globalAlt. */
1137    st_table *currBddReq;
1138    st_generator *stGen;
1139    Ntk_Node_t *regNode;
1140    bdd_node *bdd1;
1141    bdd_manager *ddManager;
1142    int j;
1143   
1144    ddManager = applData->ddManager;
1145    currBddReq = applData->currBddReq;
1146   
1147    /* Clean up currBddReq */
1148    st_foreach_item(currBddReq,stGen,&regNode,&bdd1) {
1149      bdd_recursive_deref(ddManager,bdd1);
1150    }
1151    st_free_table(currBddReq);
1152    applData->currBddReq = NIL(st_table);
1153   
1154    /* Clean up localAlt and globalAlt of region nodes */
1155    arrayForEachItem(Ntk_Node_t *,regionArray,j,regNode) {
1156      SpfdNodeDeleteGlobalAlternative(applData,regNode);
1157      SpfdNodeDeleteLocalAlt(applData,regNode);
1158    }
1159  } else {
1160    /* Now reprogram the nodes in the region. */
1161    SpfdReprogramRegionNodes(network,applData,regionArray);
1162  }
1163 
1164  /* Clean up auxIds and piAltVars*/
1165  SpfdCleanUpAuxIds(applData);
1166 
1167  /* Free stuff used only for the current wire */
1168  if (applData->currXCube) {
1169    bdd_recursive_deref(applData->ddManager,applData->currXCube);
1170    applData->currXCube = NIL(bdd_node);
1171  }
1172  if (applData->currRegionNodes) {
1173    st_free_table(applData->currRegionNodes);
1174    applData->currRegionNodes = NIL(st_table);
1175  }
1176  if (applData->currInUseVars) {
1177    st_free_table(applData->currInUseVars);
1178    applData->currInUseVars = NIL(st_table);
1179  }
1180 
1181  num = st_count(applData->currWireTable);
1182  assert(num == 0);
1183 
1184  num = st_count(applData->currReplaceTable);
1185  assert(num == 0);
1186 
1187  /* Update the total number of wires removed */
1188  wiresRemoved = applData->wiresRemoved;
1189  if (st_count(wiresRemoved) > 0) {
1190    st_foreach_item(wiresRemoved,stGen,&tempNode,
1191                    &sinkTable){
1192      spfdNumWiresRem += st_count(sinkTable);
1193    }
1194   
1195    /* free the wiresRemoved contents */
1196    st_foreach(wiresRemoved,SpfdStTableClean,NIL(char));
1197  }
1198 
1199  /* Free regionArray (cluster) */
1200  array_free(regionArray);
1201 
1202  /* Lock the node */
1203  SpfdNodeSetLocked(applData,ntkNode,TRUE);
1204
1205  return ;
1206 
1207} /* End of SpfdOptimizeNode */
1208
1209
1210/*---------------------------------------------------------------------------*/
1211/* Definition of static functions                                            */
1212/*---------------------------------------------------------------------------*/
1213/**Function********************************************************************
1214
1215  Synopsis [Compare the convex combination of fanout count and the
1216  node's topological depth.]
1217
1218  SideEffects        [None]
1219
1220******************************************************************************/
1221static int
1222CompareConvexFanoutCountAndDepth(
1223  const void *obj1,
1224  const void *obj2)
1225{
1226  Ntk_Node_t *node1,*node2;
1227  Ntk_Network_t *network;
1228  float weight1,weight2;
1229  float load1,load2;
1230  int depth1,depth2;
1231 
1232  node1 = *(Ntk_Node_t **)obj1;
1233  node2 = *(Ntk_Node_t **)obj2;
1234  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
1235  network = Ntk_NodeReadNetwork(node1);
1236
1237  if (Ntk_NodeTestIsPrimaryOutput(node1) ||
1238      Ntk_NodeTestIsPrimaryInput(node1)) {
1239    weight1 = -1.0;
1240  } else {
1241    load1 = Ntk_NodeReadNumFanouts(node1);
1242    depth1 = Truesim_NetworkReadNodeDepth(network,node1);
1243    weight1 = spfdAlpha * load1 + (1.0-spfdAlpha)*depth1;
1244  }
1245
1246  if (Ntk_NodeTestIsPrimaryOutput(node2) ||
1247      Ntk_NodeTestIsPrimaryInput(node2)) {
1248    weight2 = -1.0;
1249  } else {
1250    load2 = Ntk_NodeReadNumFanouts(node2);
1251    depth2 = Truesim_NetworkReadNodeDepth(network,node2);
1252    weight2 = spfdAlpha * load2 + (1.0-spfdAlpha)*depth2;
1253  }
1254 
1255  if (weight1 > weight2)
1256    return -1;
1257  else if (weight1 == weight2)
1258    return 0;
1259  else
1260    return 1;
1261
1262} /* End of CompareConvexFanoutCountAndDepth */
1263
1264
1265/**Function********************************************************************
1266
1267  Synopsis [Compare the convex combination of switched capacitance and
1268  topological depth of two nodes.]
1269
1270  SideEffects        [None]
1271
1272******************************************************************************/
1273static int
1274CompareConvexSwitchedCapAndDepth(
1275  const void *obj1,
1276  const void *obj2)
1277{
1278  Ntk_Node_t *node1,*node2;
1279  Ntk_Network_t *network;
1280  float weight1,weight2;
1281  float switch1,switch2;
1282  float load1,load2;
1283  int depth1,depth2;
1284 
1285  node1 = *(Ntk_Node_t **)obj1;
1286  node2 = *(Ntk_Node_t **)obj2;
1287  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
1288  network = Ntk_NodeReadNetwork(node1);
1289
1290  if (Ntk_NodeTestIsPrimaryOutput(node1) ||
1291      Ntk_NodeTestIsPrimaryInput(node1)) {
1292    weight1 = -1.0;
1293  } else {
1294    switch1 = Truesim_NetworkReadNodeSwitchingProb(network,node1);
1295    load1 = Truesim_NetworkReadNodeLoad(network,node1);
1296    depth1 = Truesim_NetworkReadNodeDepth(network,node1);
1297    weight1 = spfdAlpha * load1 * switch1 + (1.0-spfdAlpha)*depth1;
1298  }
1299
1300  if (Ntk_NodeTestIsPrimaryOutput(node2) ||
1301      Ntk_NodeTestIsPrimaryInput(node2)) {
1302    weight2 = -1.0;
1303  } else {
1304    switch2 = Truesim_NetworkReadNodeSwitchingProb(network,node2);
1305    load2 = Truesim_NetworkReadNodeLoad(network,node2);
1306    depth2 = Truesim_NetworkReadNodeDepth(network,node2);
1307    weight2 = spfdAlpha * load2 * switch2 + (1.0-spfdAlpha)*depth2;
1308  }
1309 
1310  if (weight1 > weight2)
1311    return -1;
1312  else if (weight1 == weight2)
1313    return 0;
1314  else
1315    return 1;
1316
1317} /* End of CompareConvexSwitchedCapAndDepth */
Note: See TracBrowser for help on using the repository browser.