source: vis_dev/vis-2.3/src/spfd/spfdCommon.c @ 25

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

vis2.3
File size: 19.0 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [spfdCommon.c]
4
5  PackageName [spfd]
6
7  Synopsis [Essential routines required during SPFD computation.]
8
9  Description [Essential routines required during SPFD computation.]
10
11  SeeAlso     [spfdSpfd.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 bdd_node * NodeComputeGeneralProbability(Ntk_Network_t *network, bdd_manager *ddManager, Ntk_Node_t *regNode, bdd_node *result);
55
56/**AutomaticEnd***************************************************************/
57
58
59/*---------------------------------------------------------------------------*/
60/* Definition of exported functions                                          */
61/*---------------------------------------------------------------------------*/
62
63
64/*---------------------------------------------------------------------------*/
65/* Definition of internal functions                                          */
66/*---------------------------------------------------------------------------*/
67/**Function********************************************************************
68
69  Synopsis [Compute SPFDs for the nodes in regionArray, i.e., the
70  cluster. regionArray is sorted in the increasing order of
71  topological depth.]
72
73  SideEffects [None]
74
75******************************************************************************/
76void
77SpfdRegionComputeSinglePairSpfd(
78  Ntk_Network_t *network,
79  SpfdApplData_t *applData,
80  array_t *regionArray)
81{
82  Ntk_Node_t *node,*fanin,*fanout;
83  int i,j,bound,maxFanin;
84  long id;
85  int numNodes,numFanin;
86  boolean isPi,boundOrPO;
87  st_table *nodeCountTable = NIL(st_table);
88  st_table *regionNodes = applData->currRegionNodes;
89  st_table *inUseVars = applData->currInUseVars;
90  bdd_manager *ddManager = applData->ddManager;
91  bdd_node **tempVars,*spfd,*localAlt;
92 
93  numFanin = -1; /* To keep compiler happy. */
94  /* Delete node spfds when not needed */
95  nodeCountTable = st_init_table(st_ptrcmp,st_ptrhash);
96  arrayForEachItem(Ntk_Node_t *,regionArray,j,node) {
97    int num = 0;
98    Ntk_NodeForEachFanin(node,i,fanin) {
99      /* spfds for boundary nodes, PI, PO are not derived from their
100         fanouts. */
101      if (st_lookup(regionNodes,(char *)fanin,&bound) &&
102          !bound &&
103          !Ntk_NodeTestIsPrimaryInput(fanin) &&
104          !Ntk_NodeTestIsPrimaryOutput(fanin)) {
105        num++;
106      }
107    }
108    if (num) {
109      int *count;
110      count = ALLOC(int,1);
111      *count = num;
112      st_insert(nodeCountTable,(char *)node,(char *)count);
113    }
114  }
115
116  /* Allocate temporary variables that MIGHT BE required during the
117     computation of SCCs. We will allocate maxFanin temporary
118     variables. */
119  maxFanin = -1;
120  arrayForEachItem(Ntk_Node_t *,regionArray,i,node) {
121    numFanin = Ntk_NodeReadNumFanins(node);
122    if (numFanin > maxFanin)
123      maxFanin = numFanin;
124  }
125  tempVars = SpfdAllocateTemporaryVariables(ddManager,inUseVars,maxFanin);
126 
127  /* Compute spfd and localAlt for all the nodes in the region. */
128  numNodes = array_n(regionArray);
129  for (i = numNodes-1; i >= 0; i--) {
130    node = array_fetch(Ntk_Node_t *,regionArray,i);
131    st_lookup(regionNodes,(char *)node,&bound);
132
133    /* Is it a boundary node or is it primary output? For such nodes,
134       we dont not derive SPFDs from their fanouts. Their SPFDs are
135       derived from their current function impelementation */
136    boundOrPO = (bound || Ntk_NodeTestIsPrimaryOutput(node));
137    isPi = Ntk_NodeTestIsPrimaryInput(node);
138   
139    if (isPi) {
140      spfd = NIL(bdd_node);
141    } else if (boundOrPO) {
142      spfd = SpfdNodeComputeSpfdFromOnAndOffSet(applData,node,
143                                                  NIL(bdd_node),
144                                                  NIL(bdd_node));
145    } else { /* Internal node */
146      spfd = SpfdNodeComputeSpfdFromFanouts(applData,node);
147    }
148    /* Set node's spfd */
149    SpfdNodeSetSpfd(applData,node,spfd);
150    /* Set node's localAlt */
151    if (isPi) {
152      SpfdNodeSetLocalAlt(applData,node,NIL(bdd_node));
153    } else if (boundOrPO) {
154      bdd_ref(localAlt = SpfdNodeReadLocalBdd(network,node));
155      SpfdNodeSetLocalAlt(applData,node,localAlt);
156    } else { /* Internal node */
157      int numSCC;
158      st_table *SCC;
159      SCC = SpfdNodeComputeSCCs(applData,node,tempVars);
160      numSCC = st_count(SCC);
161      if (numSCC == 0) {
162        bdd_node *logicZero;
163        if (spfdVerbose > 1)
164          (void) fprintf(vis_stdout,
165                         "** spfd info: node %s is redundant.\n",
166                         Ntk_NodeReadName(node));
167        /* Set the localAlt to empty. */
168        bdd_ref(logicZero = bdd_read_logic_zero(ddManager));
169        SpfdNodeSetLocalAlt(applData,node,logicZero);
170      } else {
171        /* Reduce the spfd to a single pair. SCC components are dereferenced in
172           the function. The localAlt is also set to one of the components of
173           the single pair */
174        SpfdNodeReduceSCCToSinglePair(applData,node,SCC);
175      }
176      st_free_table(SCC);
177    }
178    /* Clean nodeCountTable if the present node is an internal node. */
179    if (!bound &&
180        !Ntk_NodeTestIsPrimaryInput(node) &&
181        !Ntk_NodeTestIsPrimaryOutput(node)) {
182      Ntk_NodeForEachFanout(node,j,fanout) {
183        int *count;
184        if (st_lookup(nodeCountTable,(char *)fanout,&count)) {
185          (*count)--;
186          if (*count == 0) {
187            st_delete(nodeCountTable,&fanout,&count);
188            SpfdNodeDeleteSpfd(applData,fanout);
189            FREE(count);
190          }
191        }
192      }
193    }
194  }
195
196  /* Some of the internal nodes' spfd might not be deleted via
197     nodeCountTable. Delete them explicitly. SPFD of the first node is
198     needed. It will be deleted later in the calling function. */
199  for (i = 1; i < numNodes; i++) {
200    node = array_fetch(Ntk_Node_t *,regionArray,i);
201    SpfdNodeDeleteSpfd(applData,node);
202  }
203  /* Delete the fanin order arrays for region nodes */
204  arrayForEachItem(Ntk_Node_t *,regionArray,i,node) {
205    SpfdNodeDeleteFaninOrder(applData,node);
206  }
207  for (i = 0; i < numFanin; i++) {
208    id = (long) bdd_node_read_index(tempVars[i]);
209    st_delete(inUseVars,&id,NIL(char *));
210  }
211  FREE(tempVars);
212
213  /* Assert that nodeCountTable is empty */
214  assert(st_count(nodeCountTable) == 0);
215  st_free_table(nodeCountTable);
216
217  return;
218
219} /* End of SpfdRegionComputeSinglePairSpfd */
220
221
222/**Function********************************************************************
223
224  Synopsis [Collapse the SCCs in a node's SPFD into a binary SPFD by
225  appropriately choosing a binary value associated with each of the
226  SCCs. This function is used only when signal probabilites are known,
227  i.e, only when vector simulation is performed. 'result' is the
228  characteristic function of the set of SCCs combined with the
229  parameters. For example, if {(E1_i,E0_i)} is the set of bipartite SCCs,
230
231  result(Y,P) = \sum (p_i*E1_i + \bar{p}_i*E0_i). This function computes
232  assignments to p_i such that the 'result' has lower switching
233  activity than the previous implementation at regNode.]
234
235  SideEffects [None]
236
237******************************************************************************/
238bdd_node *
239SpfdNodeComputeOptParams(
240  SpfdApplData_t *applData,
241  Ntk_Node_t *regNode,
242  bdd_node *result,
243  bdd_node **parameters,
244  int numIsfs)
245{
246  bdd_manager *ddManager = applData->ddManager;
247  Ntk_Network_t *network = Ntk_NodeReadNetwork(regNode);
248  bdd_node *genProb,*offGenProb;
249  bdd_node *diff,*maxDiff,*optComb;
250  bdd_node *ddTemp,*prevSwitching,*newSwitching;
251  float prob,switching;
252 
253  /* Compute the new node probability in terms of parameters introduced */
254  genProb = NodeComputeGeneralProbability(network,ddManager,regNode,result);
255  bdd_ref(offGenProb = bdd_add_apply(ddManager,bdd_add_minus,
256                                     bdd_read_one(ddManager),genProb));
257  bdd_ref(newSwitching = bdd_add_apply(ddManager,bdd_add_times,
258                                       genProb,offGenProb));
259  bdd_recursive_deref(ddManager,genProb);
260  bdd_recursive_deref(ddManager,offGenProb);
261 
262  /* Compute the previous power dissipated */
263  ddTemp = SpfdNodeReadLocalBdd(network,regNode);
264  prob = Truesim_BddNodeComputeProbability(network,ddTemp);
265  switching = prob*(1.0-prob);
266  bdd_ref(prevSwitching = bdd_add_const(ddManager,switching));
267
268  /* Find the combination of parameters that give max power savings,
269     i.e. max(prevPowerAdd - newPowerAdd) */
270  bdd_ref(diff = bdd_add_apply(ddManager,bdd_add_minus,prevSwitching,
271                               newSwitching));
272  bdd_recursive_deref(ddManager,prevSwitching);
273  bdd_recursive_deref(ddManager,newSwitching);
274
275  /* Find the max. difference */
276  bdd_ref(maxDiff = bdd_add_find_max(ddManager,diff));
277
278  if (bdd_add_value(maxDiff) <= 0.0) {
279    bdd_recursive_deref(ddManager,diff);
280    bdd_recursive_deref(ddManager,maxDiff);
281
282    optComb = NIL(bdd_node);
283  } else {
284    /* Find minterms with max. difference */
285    bdd_ref(optComb = bdd_add_apply(ddManager,SpfdAddEqual,maxDiff,diff));
286    bdd_recursive_deref(ddManager,maxDiff);
287    bdd_recursive_deref(ddManager,diff);
288
289    /* optComb (an ADD) can be a cube, i.e., more than one
290       minterm. Pick a minterm. Convert optComb to a BDD */
291    bdd_ref(maxDiff = bdd_add_bdd_threshold(ddManager,optComb,(double) 1.0));
292    bdd_recursive_deref(ddManager,optComb);
293    optComb = maxDiff;
294
295    /* Pick one cube */
296    bdd_ref(maxDiff = bdd_bdd_pick_one_minterm(ddManager,optComb,parameters,
297                                               numIsfs));
298    bdd_recursive_deref(ddManager,optComb);
299    optComb = maxDiff;
300  }
301
302  return optComb;
303 
304} /* End of SpfdNodeComputeOptParams */
305
306
307/**Function********************************************************************
308
309  Synopsis [Reduce the set of SCCs in a SPFD to a single SCC, i.e, to
310  reduce to a binary SPFD. ]
311
312  SideEffects [None]
313
314******************************************************************************/
315void
316SpfdNodeReduceSCCToSinglePair(
317  SpfdApplData_t *applData,
318  Ntk_Node_t *regNode,
319  st_table *SCC)
320{
321  Ntk_Network_t *network = Ntk_NodeReadNetwork(regNode);
322  st_table *inUseVars = applData->currInUseVars;
323  bdd_manager *ddManager = applData->ddManager;
324  bdd_node **parameters;
325  bdd_node *bdd1,*bdd0,*result,*spfd;
326  bdd_node *optComb;
327  st_generator *stGen;
328  int numIsfs;
329  int i;
330  long lid;
331
332  numIsfs = st_count(SCC);
333  /* Allocate numIsfs binary valued parameters, one for each SCC. */
334  parameters = SpfdComputeParameters(applData,SCC);
335
336  /* Compute the general form representation for the local alternate
337     function */
338  bdd_ref(result = bdd_read_logic_zero(ddManager));
339  i = 0;
340  st_foreach_item(SCC,stGen,&bdd1,&bdd0) {
341    bdd_node *ddTemp,*ddTemp2;
342    bdd_ref(ddTemp = bdd_bdd_ite(ddManager,parameters[i],bdd1,bdd0));
343    bdd_recursive_deref(ddManager,bdd1);
344    bdd_recursive_deref(ddManager,bdd0);
345    bdd_ref(ddTemp2 = bdd_bdd_or(ddManager,ddTemp,result));
346    bdd_recursive_deref(ddManager,ddTemp);
347    bdd_recursive_deref(ddManager,result);
348    result = ddTemp2;
349    i++;
350  }
351
352  if (!spfdPerfSim) { /* No switching activity info. available */
353    /* Choose one combination of parameters */
354    bdd_ref(optComb = bdd_bdd_compute_cube(ddManager,parameters,
355                                           NIL(int),numIsfs));
356  } else {
357    /* Compute the combination of parameters that reduce switching */
358    optComb = SpfdNodeComputeOptParams(applData,regNode,result,
359                                       parameters,numIsfs);
360  }
361
362  if (optComb) { /* If such a combination exists */
363    bdd_node *E1y,*E0y; /* BDDs for the care ON-set and care OFF-set,
364                           respectively,  of the optimal ISF found in the
365                           previous step. */
366    bdd_node *imgOptComb;
367    bdd_node **notParams;
368    int size,i,id;
369
370    /* Compute the lhs (care ON-set) of the ISF */
371    bdd_ref(E1y = bdd_bdd_cofactor(ddManager,result,optComb));
372    /* Compute the rhs (care OFF-set) of the ISF */
373    size = bdd_num_vars(ddManager);
374    notParams = ALLOC(bdd_node *,size);
375    for (i = 0; i < size; i++) {
376      bdd_ref(notParams[i] = bdd_bdd_ith_var(ddManager,i));
377    }
378    for (i = 0; i < numIsfs; i++) {
379      id = bdd_node_read_index(parameters[i]);
380      bdd_recursive_deref(ddManager,notParams[id]);
381      bdd_ref(notParams[id] = bdd_not_bdd_node(parameters[i]));
382    }
383    bdd_ref(imgOptComb = bdd_bdd_vector_compose(ddManager,optComb,notParams));
384    bdd_recursive_deref(ddManager,optComb);
385    bdd_ref(E0y = bdd_bdd_cofactor(ddManager,result,imgOptComb));
386    bdd_recursive_deref(ddManager,result);
387    bdd_recursive_deref(ddManager,imgOptComb);
388
389    /* Compute the spfd of E1y and E0y */
390    spfd = SpfdNodeComputeSpfdFromOnAndOffSet(applData,regNode,E1y,E0y);
391    SpfdNodeDeleteSpfd(applData,regNode);
392    SpfdNodeSetSpfd(applData,regNode,spfd);
393
394    /* Set E1y as the localAlt */
395    SpfdNodeSetLocalAlt(applData,regNode,E1y);
396    bdd_recursive_deref(ddManager,E0y);
397   
398    /* Free notParams */
399    for (i = 0; i < size; i++) {
400      bdd_recursive_deref(ddManager,notParams[i]);
401    }
402    FREE(notParams);
403  } else { /* Compute alternate spfd from local function */
404    bdd_node *bdd1,*bdd0;
405    bdd_recursive_deref(ddManager,result);
406
407    /* Set localAlt Bdd */
408    bdd_ref(bdd1 = SpfdNodeReadLocalBdd(network,regNode));
409    bdd_ref(bdd0 = bdd_not_bdd_node(bdd1));
410
411    /* Set the new spfd */
412    spfd = SpfdNodeComputeSpfdFromOnAndOffSet(applData,regNode,bdd1,bdd0);
413    SpfdNodeDeleteSpfd(applData,regNode);
414    SpfdNodeSetSpfd(applData,regNode,spfd);
415
416    /* Set bdd1 as the localAlt */
417    SpfdNodeSetLocalAlt(applData,regNode,bdd1);
418    bdd_recursive_deref(ddManager,bdd0);
419  }
420
421  /* Free the parameters */
422  for (i = 0; i < numIsfs; i++) {
423    lid = (long) bdd_node_read_index(parameters[i]);
424    st_delete(inUseVars,&lid,NIL(char *));
425  }
426  FREE(parameters);
427 
428  return;
429 
430} /* End of SpfdNodeReduceSCCToSinglePair */
431
432
433/**Function********************************************************************
434
435  Synopsis [Global BDDs are required during the computation of SPFDs
436  for cluster members. We compute them once and use it when
437  needed. Also, these BDDs are removed when they are no longer
438  required. Gloabl BDDs are required for all nodes in the cluster and
439  their respective fanin nodes.]
440
441  SideEffects [None]
442
443******************************************************************************/
444void
445SpfdComputeRequiredGlobalBdds(
446  Ntk_Network_t *network,
447  SpfdApplData_t *applData)
448{
449  st_table *regionNodes,*rootTable,*leavesTable;
450  st_table *currBddReq;
451  array_t *rootArray,*nodeMvfs;
452  st_generator *stGen;
453  Ntk_Node_t *node,*fanin;
454  char *dummy;
455  int i;
456  lsGen gen;
457  bdd_t *mddOne;
458  bdd_node *bdd1;
459  bdd_manager *ddManager = applData->ddManager;
460  mddOne = bdd_one(ddManager);
461
462  /* Collect cluster nodes and also their fanin nodes */
463  regionNodes = applData->currRegionNodes;
464  rootTable = st_init_table(st_ptrcmp,st_ptrhash);
465  st_foreach_item(regionNodes,stGen,&node,&dummy) {
466    Ntk_NodeForEachFanin(node,i,fanin) {
467      st_insert(rootTable,(char *)fanin,(char *)-1);
468    }
469  }
470
471  /* Convert rootTable to rootArray for use by Ntm_NetworkBuildMvfs */
472  rootArray = array_alloc(Ntk_Node_t *,0);
473  st_foreach_item(rootTable,stGen,&node,&dummy) {
474    array_insert_last(Ntk_Node_t *,rootArray,node);
475  }
476  st_free_table(rootTable);
477 
478  /* Collect the leaf nodes in the network. */
479  leavesTable = st_init_table(st_ptrcmp, st_ptrhash);
480  Ntk_NetworkForEachCombInput(network,gen,node) {
481    st_insert(leavesTable,(char *)node,(char *) -1);
482  }
483
484  /* Compute the Mvfs for the nodes in rootArray */
485  nodeMvfs = Ntm_NetworkBuildMvfs(network,rootArray,leavesTable,mddOne);
486  bdd_free(mddOne);
487  st_free_table(leavesTable);
488 
489  /* Extract the BDDs and put them in currBddReq */
490  currBddReq = applData->currBddReq = st_init_table(st_ptrcmp,st_ptrhash);
491  arrayForEachItem(Ntk_Node_t *,rootArray,i,node) {
492    Mvf_Function_t *mvf;
493    mvf = array_fetch(Mvf_Function_t *,nodeMvfs,i);
494    bdd1 = bdd_extract_node_as_is(array_fetch(bdd_t *,mvf,1));
495    bdd_ref(bdd1);
496    st_insert(currBddReq,(char *)node,(char *)bdd1);
497  }
498  array_free(rootArray);
499  Mvf_FunctionArrayFree(nodeMvfs);
500
501  return;
502
503} /* End of SpfdComputeRequiredGlobalBdds */
504
505/*---------------------------------------------------------------------------*/
506/* Definition of static functions                                            */
507/*---------------------------------------------------------------------------*/
508/**Function********************************************************************
509
510  Synopsis [Returns the ADD representing the signal probability of
511  regNode. 'result' is the BDD which has in support the variables in
512  the fanin of regNode.]
513
514  SideEffects [None]
515
516******************************************************************************/
517static bdd_node *
518NodeComputeGeneralProbability(
519  Ntk_Network_t *network,
520  bdd_manager *ddManager,
521  Ntk_Node_t *regNode,
522  bdd_node *result)
523{
524  int size,k,id;
525  bdd_node **onArray,**offArray;
526  bdd_node *resultAdd,*genProb;
527  Ntk_Node_t *fanin;
528  float prob;
529 
530  size = bdd_num_vars(ddManager);
531  onArray = ALLOC(bdd_node *,size);
532  offArray = ALLOC(bdd_node *,size);
533  for (k = 0; k < size; k++) {
534    bdd_ref(onArray[k] = bdd_add_ith_var(ddManager,k));
535    bdd_ref(offArray[k] = bdd_add_ite(ddManager,onArray[k],
536                                      bdd_read_zero(ddManager),
537                                      bdd_read_one(ddManager)));
538  }
539 
540  Ntk_NodeForEachFanin(regNode,k,fanin) {
541    id = Ntk_NodeReadMddId(fanin);
542    bdd_recursive_deref(ddManager,onArray[id]);
543    bdd_recursive_deref(ddManager,offArray[id]);
544    prob = Truesim_NetworkReadNodeProbability(network,fanin);
545    bdd_ref(onArray[id] = bdd_add_const(ddManager,prob));
546    bdd_ref(offArray[id] = bdd_add_const(ddManager,1.0-prob));
547  }
548
549  bdd_ref(resultAdd = bdd_bdd_to_add(ddManager,result));
550  genProb = (bdd_node *)bdd_add_general_vector_compose(ddManager,resultAdd,
551                                                      onArray,offArray);
552  bdd_ref(genProb);
553  bdd_recursive_deref(ddManager,resultAdd);
554
555  return genProb;
556 
557} /* End of NodeComputeGeneralProbability */
Note: See TracBrowser for help on using the repository browser.