source: vis_dev/vis-2.3/src/spfd/spfdUtil.c

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

vis2.3
File size: 29.7 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [spfdUtil.c]
4
5  PackageName [spfd]
6
7  Synopsis [Utility routines for the spfd package.]
8
9  Description [Utility routines for the spfd package.]
10
11  SeeAlso     [spfdAPI.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
54
55/**AutomaticEnd***************************************************************/
56
57
58/*---------------------------------------------------------------------------*/
59/* Definition of exported functions                                          */
60/*---------------------------------------------------------------------------*/
61
62/*---------------------------------------------------------------------------*/
63/* Definition of internal functions                                          */
64/*---------------------------------------------------------------------------*/
65
66/**Function********************************************************************
67
68  Synopsis    [Initialize the application data structure of the package.]
69
70  SideEffects [None]
71
72******************************************************************************/
73SpfdApplData_t *
74SpfdInitializeApplData(
75  Ntk_Network_t *network)
76{
77  SpfdApplData_t *applData;
78  SpfdNodeData_t *data;
79  st_table *nodeToData;
80  lsGen gen;
81  Ntk_Node_t *node;
82 
83  applData = ALLOC(SpfdApplData_t, 1);
84
85  Ntk_NetworkAddApplInfo(network, SPFD_NETWORK_APPL_KEY,
86                         (Ntk_ApplInfoFreeFn) SpfdApplFreeCallback,
87                         (void *) applData);
88
89  nodeToData = applData->nodeToData = st_init_table(st_ptrcmp, st_ptrhash);
90  applData->ddManager = Ntk_NetworkReadMddManager(network);
91  applData->currXCube = NIL(bdd_node);
92  applData->currRegionNodes = NIL(st_table);
93  applData->currBddReq = NIL(st_table);
94  applData->currInUseVars = NIL(st_table);
95  applData->currPiAltVars = NIL(st_table);
96  /* Will be freed when the application quits */
97  applData->currWireTable = st_init_table(st_ptrcmp,st_ptrhash);
98  applData->currReplaceTable = st_init_table(st_ptrcmp,st_ptrhash); 
99  applData->wiresRemoved = st_init_table(st_ptrcmp,st_ptrhash);
100  applData->nodesRemoved = st_init_table(st_ptrcmp,st_ptrhash);
101  applData->placeData = NIL(SpfdPlaceData_t);
102
103  Ntk_NetworkForEachNode(network,gen,node) {
104    data = ALLOC(SpfdNodeData_t,1);
105    data->spfd = NIL(bdd_node);
106    data->localAlt = NIL(bdd_node);
107    data->alternative = NIL(bdd_node);
108    data->faninOrder = NIL(array_t);
109    data->parameters = NIL(bdd_node *);
110    data->numParams = 0;
111    data->auxId = -1;
112    data->locked = FALSE;
113   
114    st_insert(nodeToData,(char *)node,(char *)data);
115  }
116
117  return applData;
118
119} /* End of SpfdInitializeApplData */
120
121
122/**Function********************************************************************
123
124  Synopsis [Given a set of 'num' (st_count(SCC)) pairs of functions,
125  compute 'num' binary variables and allocate BDD ids to those
126  variables such that their level is above all the variables in the
127  support of the functions in SCC.]
128
129  SideEffects [None]
130
131******************************************************************************/
132bdd_node **
133SpfdComputeParameters(
134  SpfdApplData_t *applData,
135  st_table *SCC)
136{
137  bdd_manager *ddManager = applData->ddManager;
138  st_table *inUseVars = applData->currInUseVars;
139  int id,i,minLevel,size,used;
140  int index,numIsfs;
141  char *dummy;
142  st_generator *stGen;
143  bdd_node *bdd1,*bdd0;
144  bdd_node **parameters;
145
146  minLevel = bdd_num_vars(ddManager);
147  /* Find the topmost level among the SCC components SCC(Y,P) */
148  st_foreach_item(SCC,stGen,&bdd1,&bdd0) {
149    int level1,level0,tempInt;
150    level1 = bdd_get_level_from_id(ddManager,bdd_node_read_index(bdd1));
151    level0 = bdd_get_level_from_id(ddManager,bdd_node_read_index(bdd0));
152    tempInt = (level1 < level0) ? level1 : level0;
153    minLevel = (minLevel < tempInt) ? minLevel : tempInt;
154  }
155
156  numIsfs = st_count(SCC);
157  size = bdd_num_vars(ddManager);
158  used = st_count(inUseVars);
159 
160  /* Allocate required number of new variables above minLevel */
161  if (size - used < numIsfs) {
162    SpfdMddCreateVariables(ddManager,(numIsfs)-(size-used),minLevel);
163  }
164
165  /* Assign the parameters */
166  size = bdd_num_vars(ddManager);
167  index = numIsfs;
168  parameters = ALLOC(bdd_node *,numIsfs);
169  /* Assign the parameter variables */
170  for (i = 0; i < size; i++) {
171    if (index == 0)
172      break;
173    id = bdd_get_id_from_level(ddManager,i);
174    if (!st_lookup(inUseVars,(char *)(long)id,(char **)&dummy)) {
175      parameters[numIsfs-index] = bdd_bdd_ith_var(ddManager,id);
176      st_insert(inUseVars,(char *)(long)id,(char *)-1);
177      index--;
178    }
179  }
180
181  return parameters;
182} /* End of SpfdComputeParameters */
183
184
185/**Function********************************************************************
186
187  Synopsis    [Allocate num of BDD variables.]
188
189  SideEffects [None]
190
191******************************************************************************/
192bdd_node **
193SpfdAllocateTemporaryVariables(
194  bdd_manager *ddManager,
195  st_table *inUseVars,
196  int num)
197{
198  int size,used,i,index,id;
199  char *dummy;
200  bdd_node **tempVars;
201
202  tempVars = ALLOC(bdd_node *,num);
203  size = bdd_num_vars(ddManager);
204  used = st_count(inUseVars);
205  if (size - used < num) {
206    /* Create variables at the end */
207    SpfdMddCreateVariables(ddManager,num-(size-used),size);
208  }
209  size = bdd_num_vars(ddManager);
210  index = num;
211  /* Assign the temporary variables */
212  for (i = size-1; i >= 0; i--) {
213    if (index == 0)
214      break;
215    id = bdd_get_id_from_level(ddManager,i);
216    if (!st_lookup(inUseVars,(char *)(long)id,(char **)&dummy)) {
217      tempVars[num-index] = bdd_bdd_ith_var(ddManager,id);
218      st_insert(inUseVars,(char *)(long)id,(char *)-1);
219      index--;
220    }
221  }
222
223  return tempVars;
224} /* End of SpfdAllocateTemporaryVariables */
225
226
227/**Function********************************************************************
228
229  Synopsis [Recyle existing BDD variables or allocate new ones.]
230
231  SideEffects [The BDD manager is changed accordingly to reflect the
232  addition of new variables.]
233
234******************************************************************************/
235void
236SpfdAllocateOrReuseAuxVariables(
237  Ntk_Network_t *network,
238  SpfdApplData_t *applData)
239{
240  st_table *currBddReq = applData->currBddReq;
241  bdd_manager *ddManager = applData->ddManager;
242  bdd_node *bdd1,*piSupport;
243  int numBdds,piSize,regSize,size,newVars;
244  int level,regNumVars;
245  int numPiAlt,index;
246  int *piIds;
247  Ntk_Node_t *node;
248  st_generator *stGen;
249  st_table *inUseVars,*nodeToData,*piAltVars;
250  lsGen gen;
251
252  numBdds = st_count(currBddReq);
253 
254  /* Check if any region nodes are PIs */
255  piAltVars = st_init_table(st_numcmp,st_numhash);
256  numPiAlt = 0;
257  st_foreach_item(currBddReq,stGen,&node,&bdd1) {
258    if (Ntk_NodeTestIsPrimaryInput(node)) {
259      int id = Ntk_NodeReadMddId(node);
260      st_insert(piAltVars,(char *)(long)id,(char *)(long)id);
261      numPiAlt++;
262    }
263  }
264
265  /* Put the variable ids in piSupport in inUseVars */
266  inUseVars = st_init_table(st_numcmp,st_numhash);
267
268  /* To be on the safe side we do not reuse PI bdd ids */
269  piSize = Ntk_NetworkReadNumPrimaryInputs(network);
270  piIds = ALLOC(int,piSize);
271  index = 0;
272  Ntk_NetworkForEachPrimaryInput(network,gen,node) {
273    int id;
274    id = Ntk_NodeReadMddId(node);
275    st_insert(inUseVars,(char *)(long)id,(char *)-1);
276    piIds[index] = id;
277    index++;
278  }
279  bdd_ref(piSupport = bdd_indices_to_cube(ddManager,piIds,piSize));
280  FREE(piIds);
281 
282  if (applData->currXCube) {
283    (void) fprintf(vis_stdout,
284                   "** spfd warning: Possible memory leak.\n");
285  }
286  applData->currXCube = piSupport;
287
288  regSize = numBdds;
289  size = bdd_num_vars(ddManager);
290  regNumVars = 2*regSize+piSize+numPiAlt;
291  if (size < regNumVars) {
292    newVars = regNumVars - size;
293    SpfdMddCreateVariables(ddManager,newVars,0);
294  } 
295 
296  /* Put the BDD ids of regionNodes and their immediate fanin in inUseVars */
297  st_foreach_item(currBddReq,stGen,&node,NIL(char *)) {
298    st_insert(inUseVars,(char *)(long)Ntk_NodeReadMddId(node),(char *)-1);
299  }
300   
301  /* Assign auxillary ids to region nodes and their immediate fanin.  */
302  nodeToData = applData->nodeToData;
303  level = 0;
304  size = bdd_num_vars(ddManager);
305  st_foreach_item(currBddReq,stGen,&node,NIL(char *)) {
306    int id;
307    while (level < size) {
308      id = bdd_get_id_from_level(ddManager,level);
309      if (!st_lookup(inUseVars,(char *)(long)id,NIL(char *))) {
310        SpfdNodeData_t *nodeData;
311        st_lookup(nodeToData,(char *)node,&nodeData);
312        nodeData->auxId = id;
313        st_insert(inUseVars,(char *)(long)id,(char *)-1);
314        level++;
315        break;
316      }
317      level++;
318    }
319  }
320
321  /* Assign alternate ids (these are in addition to auxIds) to those nodes in
322     currBddReq which are PIs */
323  st_foreach_item(currBddReq,stGen,&node,NIL(char *)) {
324    if (Ntk_NodeTestIsPrimaryInput(node)) {
325      int nodeId = Ntk_NodeReadMddId(node);
326      while (level < size) {
327        int id = bdd_get_id_from_level(ddManager,level);
328        if (!st_lookup(inUseVars,(char *)(long)id,NIL(char *))) {
329          st_insert(piAltVars,(char *)(long)nodeId,(char *)(long)id);
330          st_insert(inUseVars,(char *)(long)id,(char *)-1);
331          level++;
332          break;
333        }
334        level++;
335      }
336    }
337  }
338
339  if (applData->currInUseVars) {
340    (void) fprintf(vis_stdout,
341                   "** spfd warning: Possible memory leak.\n");
342  }
343  applData->currInUseVars = inUseVars;
344
345  if (applData->currPiAltVars) {
346    (void) fprintf(vis_stdout,
347                   "** spfd warning: Possible memory leak.\n");
348  }
349  applData->currPiAltVars = piAltVars;
350
351  return;
352 
353} /* End of SpfdAllocateOrReuseAuxVariables */
354
355
356/**Function********************************************************************
357
358  Synopsis [Fanin nodes of each cluster node is ordered according to
359  the 'compareFunc'. The fanin nodes need to be ordered during SPFD
360  computation.]
361
362  SideEffects        [None]
363
364******************************************************************************/
365void
366SpfdOrderFaninOfRegionNodes(
367  Ntk_Network_t *network,
368  SpfdApplData_t *applData,
369  int (*compareFunc)(const void *, const void *))
370{
371  SpfdNodeData_t *nodeData;
372  st_table *nodeToData = applData->nodeToData;
373  st_table *regionNodes = applData->currRegionNodes;
374  st_generator *stGen;
375  Ntk_Node_t *regNode,*fanin;
376  int i,bound;
377  boolean found;
378 
379  st_foreach_item(regionNodes,stGen,&regNode,NIL(char *)) {
380    array_t *tempArray;
381    /* Atleast one fanin of regNode should be in regionNodes */
382    found = FALSE;
383    Ntk_NodeForEachFanin(regNode,i,fanin) {
384      if (st_lookup(regionNodes,(char *)fanin,&bound) &&
385          !bound &&
386          !Ntk_NodeTestIsPrimaryInput(fanin) &&
387          !Ntk_NodeTestIsPrimaryOutput(fanin)) {
388        found = TRUE;
389        break;
390      }
391    }
392    if (found) {
393      tempArray = array_dup(Ntk_NodeReadFanins(regNode));
394      array_sort(tempArray,compareFunc);
395      st_lookup(nodeToData,(char *)regNode,&nodeData);
396      if (nodeData->faninOrder) {
397        (void) fprintf(vis_stdout,
398                       "** spfd warning: Possible memory leak.\n");
399      }
400      nodeData->faninOrder = tempArray;
401    }
402  }
403
404  return;
405} /* End of SpfdOrderFaninOfRegionNodes */
406
407
408/**Function********************************************************************
409
410  Synopsis [Compare the convex combination of switched capacitance and
411  topological depth of two nodes.]
412
413  SideEffects        [None]
414
415******************************************************************************/
416int
417SpfdSwitchedCapAndDepthCompare(
418  const void *obj1,
419  const void *obj2)
420{
421  SpfdApplData_t *applData;
422  st_table *regionNodes;
423  Ntk_Node_t *node1,*node2;
424  Ntk_Network_t *network;
425  float weight1,weight2;
426  float switch1,switch2;
427  float load1,load2;
428  int depth1,depth2;
429  int status;
430  int dummy;
431 
432  node1 = *(Ntk_Node_t **)obj1;
433  node2 = *(Ntk_Node_t **)obj2;
434  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
435  network = Ntk_NodeReadNetwork(node1);
436  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
437                                                        SPFD_NETWORK_APPL_KEY);
438  regionNodes = applData->currRegionNodes;
439
440  status = st_lookup(regionNodes,(char *)node1,&dummy);
441  if (!status || dummy ||
442      Ntk_NodeTestIsPrimaryOutput(node1) ||
443      Ntk_NodeTestIsPrimaryInput(node1)) {
444    weight1 = -1.0;
445  } else {
446    switch1 = Truesim_NetworkReadNodeSwitchingProb(network,node1);
447    load1 = Truesim_NetworkReadNodeLoad(network,node1);
448    depth1 = Truesim_NetworkReadNodeDepth(network,node1);
449    weight1 = spfdAlpha * load1 * switch1 + (1.0-spfdAlpha)*depth1;
450  }
451
452  status = st_lookup(regionNodes,(char *)node2,&dummy);
453  if (!status || dummy ||
454      Ntk_NodeTestIsPrimaryOutput(node2) ||
455      Ntk_NodeTestIsPrimaryInput(node2)) {
456    weight2 = -1.0;
457  } else {
458    switch2 = Truesim_NetworkReadNodeSwitchingProb(network,node2);
459    load2 = Truesim_NetworkReadNodeLoad(network,node2);
460    depth2 = Truesim_NetworkReadNodeDepth(network,node2);
461    weight2 = spfdAlpha * load2 * switch2 + (1.0-spfdAlpha)*depth2;
462  }
463 
464  if (weight1 > weight2)
465    return -1;
466  else if (weight1 == weight2)
467    return 0;
468  else
469    return 1;
470
471} /* End of SpfdSwitchedCapAndDepthCompare */
472
473
474/**Function********************************************************************
475
476  Synopsis [Compare the convex combination of fanout count and the
477  node's topological depth.]
478
479  SideEffects        [None]
480
481******************************************************************************/
482int
483SpfdFanoutCountAndDepthCompare(
484  const void *obj1,
485  const void *obj2)
486{
487  SpfdApplData_t *applData;
488  st_table *regionNodes;
489  Ntk_Node_t *node1,*node2;
490  Ntk_Network_t *network;
491  float weight1,weight2;
492  float load1,load2;
493  int depth1,depth2;
494  int status;
495  int dummy;
496 
497  node1 = *(Ntk_Node_t **)obj1;
498  node2 = *(Ntk_Node_t **)obj2;
499  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
500  network = Ntk_NodeReadNetwork(node1);
501  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
502                                                        SPFD_NETWORK_APPL_KEY);
503  regionNodes = applData->currRegionNodes;
504
505  status = st_lookup(regionNodes,(char *)node1,&dummy);
506  if (!status || dummy ||
507      Ntk_NodeTestIsPrimaryOutput(node1) ||
508      Ntk_NodeTestIsPrimaryInput(node1)) {
509    weight1 = -1.0;
510  } else {
511    load1 = Ntk_NodeReadNumFanouts(node1);
512    depth1 = Truesim_NetworkReadNodeDepth(network,node1);
513    weight1 = spfdAlpha * load1 + (1.0-spfdAlpha)*depth1;
514  }
515
516  status = st_lookup(regionNodes,(char *)node2,&dummy);
517  if (!status || dummy ||
518      Ntk_NodeTestIsPrimaryOutput(node2) ||
519      Ntk_NodeTestIsPrimaryInput(node2)) {
520    weight2 = -1.0;
521  } else {
522    load2 = Ntk_NodeReadNumFanouts(node2);
523    depth2 = Truesim_NetworkReadNodeDepth(network,node2);
524    weight2 = spfdAlpha * load2 + (1.0-spfdAlpha)*depth2;
525  }
526
527  if (weight1 > weight2)
528    return -1;
529  else if (weight1 == weight2)
530    return 0;
531  else
532    return 1;
533
534} /* End of SpfdFanoutContAndDepthCompare */
535
536
537/**Function********************************************************************
538
539  Synopsis    [Compare the topological depth of two nodes.]
540
541  SideEffects [None]
542
543******************************************************************************/
544int
545SpfdDepthCompare(
546  const void *obj1,
547  const void *obj2)
548{
549  Ntk_Network_t *network;
550  Ntk_Node_t *node1 = *(Ntk_Node_t **)obj1;
551  Ntk_Node_t *node2 = *(Ntk_Node_t **)obj2;
552  int depth1,depth2;
553 
554  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
555  network = Ntk_NodeReadNetwork(node1);
556
557  depth1 = Truesim_NetworkReadNodeDepth(network,node1);
558  depth2 = Truesim_NetworkReadNodeDepth(network,node2);
559
560  if (depth1 < depth2)
561    return -1;
562  else if (depth1 == depth2)
563    return 0;
564  else
565    return 1;
566 
567} /* End of SpfdDepthCompare */
568
569
570/**Function********************************************************************
571
572  Synopsis [Same as SpfdDepthCompare, but the nodes will be sorted in
573  descending order when used by qsort.]
574
575  SideEffects [None]
576
577******************************************************************************/
578int
579SpfdDescendDepthCompare(
580  const void *obj1,
581  const void *obj2)
582{
583  Ntk_Network_t *network;
584  Ntk_Node_t *node1 = *(Ntk_Node_t **)obj1;
585  Ntk_Node_t *node2 = *(Ntk_Node_t **)obj2;
586  int depth1,depth2;
587 
588  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
589  network = Ntk_NodeReadNetwork(node1);
590
591  depth1 = Truesim_NetworkReadNodeDepth(network,node1);
592  depth2 = Truesim_NetworkReadNodeDepth(network,node2);
593
594  if (depth1 > depth2)
595    return -1;
596  else if (depth1 == depth2)
597    return 0;
598  else
599    return 1;
600 
601} /* End of SpfdDescendDepthCompare */
602
603
604/**Function********************************************************************
605
606  Synopsis [This procedure calls the mdd_create_variables in order to create
607  new variables.]
608 
609  Description [ This procedure calls the mdd_create_variables in order to
610  create new variables. IMPORTANT: The mdd_create_variables
611  procedure creates the variables in succession. So if new variables are
612  required that are not in succession, those will not be created and hence
613  cannot be used. This procedure takes as arguments the DD manager and the
614  number of variables that need to be added to the manager.]
615
616  SideEffects [It modifies the manager->hook->mdd field.]
617
618  SeeAlso []
619
620******************************************************************************/
621void
622SpfdMddCreateVariables(mdd_manager *mgr,     
623                   int numVarsToBeAdded,
624                   int level)
625{
626    array_t *mvar_values;
627    array_t *mvar_names = NIL(array_t);
628    array_t *mvar_strides = NIL(array_t);
629    int i,two_values,idBeforeLevel,size;
630
631    if (level > (size = bdd_num_vars(mgr)))
632      level = size;
633    if (level <= 0)
634      idBeforeLevel = bdd_get_id_from_level(mgr,0);
635    else
636      idBeforeLevel = bdd_get_id_from_level(mgr,level-1);
637
638    if (numVarsToBeAdded <= 0) return;
639   
640    /* Create 2 mvar values 0,1 */
641    mvar_values = array_alloc(int, numVarsToBeAdded);   
642
643    /* Assume we create only Bdd variables here */
644    two_values = 2;
645    for(i = 0; i < numVarsToBeAdded; i++) {
646      array_insert(int, mvar_values, i, two_values);
647    }
648
649    /* creates the mdd variables and updates the mvar_list field */
650    mdd_create_variables_after(mgr, idBeforeLevel,mvar_values, 
651                               mvar_names, mvar_strides);
652   
653    array_free(mvar_values);
654
655} /* End of SpfdMddCreateVariables */
656
657
658/**Function********************************************************************
659
660  Synopsis [Returns a BDD containing minterms such that the discriminant for
661  those minterms in f is equal to that in g.]
662
663  Description [Returns a BDD containing minterms such that the discriminant for
664  those minterms in f is equal to that in g. Used in bdd_add_apply().]
665
666  SideEffects [None]
667
668  SeeAlso     [cuddAddApply.c]
669
670******************************************************************************/
671bdd_node *
672SpfdAddEqual(
673  bdd_manager *ddManager,
674  bdd_node **f,
675  bdd_node **g)
676{
677  bdd_node *zero, *one;
678
679  zero = bdd_read_zero(ddManager);
680  one = bdd_read_one(ddManager);
681
682  if(*f == *g) {
683    return one;
684  }
685
686  if(bdd_is_constant(*f) && bdd_is_constant(*g)) {
687      return zero;
688  }
689  return NULL;
690}
691
692/**Function********************************************************************
693
694  Synopsis           [Print the network in BLIF format to fileName.]
695
696  SideEffects        [None]
697
698******************************************************************************/
699int
700SpfdNetworkWriteBlifFile(
701  Ntk_Network_t *network,
702  char *fileName)
703{
704  lsGen gen;
705  Ntk_Node_t *node;
706  FILE *fp;
707  int nameLen;
708  char *name;
709 
710  if ((fp = Cmd_FileOpen(fileName,"w",NIL(char *),1)) == NIL(FILE)) {
711    (void) fprintf(vis_stderr,
712                   "** spfd error: Could not open %s for writing.\n",
713                   fileName);
714    return 0;
715  }
716
717  (void) fprintf(fp,".model %s\n",Ntk_NetworkReadName(network));
718  (void) fprintf(fp,".inputs ");
719  nameLen = 0;
720  Ntk_NetworkForEachPrimaryInput(network,gen,node) {
721    name = Ntk_NodeReadName(node);
722    (void) fprintf(fp,"%s ",name);
723    nameLen += (strlen(name));
724    if (nameLen > 65) {
725      (void) fprintf(fp,"\\\n");
726      nameLen = 0;
727    }
728  }
729  (void) fprintf(fp,"\n");
730
731  nameLen = 0;
732  (void) fprintf(fp,".outputs ");
733  Ntk_NetworkForEachPrimaryOutput(network,gen,node) {
734    name = Ntk_NodeReadName(node);
735    (void) fprintf(fp,"%s ",name);
736    nameLen += (strlen(name));
737    if (nameLen > 65) {
738      (void) fprintf(fp,"\\\n");
739      nameLen = 0;
740    }   
741  }
742  (void) fprintf(fp,"\n");
743 
744  Ntk_NetworkForEachNode(network,gen,node) {
745    if (!Ntk_NodeTestIsPrimaryInput(node)) {
746      if (Ntk_NodeReadNumFanins(node) > 0 ||
747          Ntk_NodeReadNumFanouts(node) > 0) {
748        Tbl_TableWriteBlifToFile(Ntk_NodeReadTable(node),fp);
749      } else if (Ntk_NodeTestIsPrimaryOutput(node)) {
750        /* Sometimes output node can be redundant. Very unlikely,
751           but output it anyway because we cannot skip primary
752           outputs of a network. */
753        (void) fprintf(fp,".names %s\n",Ntk_NodeReadName(node));
754      }
755    }
756  }
757
758  (void) fprintf(fp,".end\n");
759
760  fclose(fp);
761 
762  return 1;
763 
764} /* End of SpfdNetworkWriteBlifFile */
765
766
767/**Function********************************************************************
768
769  Synopsis [Compute the relation of the functions specified in either
770  nodeBdds and currBddReq. If 'useMddIds' is TRUE use node (from
771  nodeArray) MDD ids else use node aux Ids. Return value of 'piSwap' is
772  used in the calling function only when 'useMddIds' is TRUE. ]
773
774  SideEffects [None]
775
776  SeeAlso []
777
778******************************************************************************/
779bdd_node *
780SpfdComputeNodeArrayRelation(
781  SpfdApplData_t *applData,
782  st_table *currBddReq,
783  array_t *nodeBdds,
784  array_t *nodeArray,
785  boolean useMddIds,
786  int *piSwap)
787{
788  bdd_manager *ddManager = applData->ddManager;
789  st_table *piAltVars = applData->currPiAltVars;
790  Ntk_Node_t *node;
791  array_t *idArray;
792  bdd_node *ddTemp,*ddTemp2,*result;
793  bdd_node *bdd1,*var;
794  int j,id;
795
796  *piSwap = 0;
797
798  if (currBddReq) {
799    nodeBdds = array_alloc(bdd_node *,0);
800    arrayForEachItem(Ntk_Node_t *,nodeArray,j,node) {
801      st_lookup(currBddReq,(char *)node,&bdd1);
802      array_insert_last(bdd_node *,nodeBdds,bdd1);
803    }
804  }
805  idArray = array_alloc(int,0);
806  if (useMddIds) { /* Use node MDD Ids or alternate Ids for PIs */
807    int altId;
808    arrayForEachItem(Ntk_Node_t *,nodeArray,j,node) {
809      id = Ntk_NodeReadMddId(node);
810      if (Ntk_NodeTestIsPrimaryInput(node)) {
811        st_lookup(piAltVars,(char *)(long)id,&altId);
812        array_insert_last(int,idArray,altId);
813        *piSwap = 1;
814      } else {
815        array_insert_last(int,idArray,id);
816      }
817    }
818  } else { /* Use node Aux Ids */
819    arrayForEachItem(Ntk_Node_t *,nodeArray,j,node) {
820      array_insert_last(int,idArray,SpfdNodeReadAuxId(applData,node));
821    }   
822  }
823  bdd_ref(result = bdd_not_bdd_node(bdd_read_logic_zero(ddManager)));
824  arrayForEachItem(Ntk_Node_t *,nodeArray,j,node) {
825    bdd1 = array_fetch(bdd_node *,nodeBdds,j);
826    var = bdd_bdd_ith_var(ddManager,array_fetch(int,idArray,j));
827    bdd_ref(ddTemp = bdd_bdd_xnor(ddManager,var,bdd1));
828    bdd_ref(ddTemp2 = bdd_bdd_and(ddManager,ddTemp,result));
829    bdd_recursive_deref(ddManager,result);
830    bdd_recursive_deref(ddManager,ddTemp);
831    result = ddTemp2;
832  }
833
834  if (currBddReq)
835    array_free(nodeBdds);
836  array_free(idArray);
837 
838  return result;
839
840} /* End of SpfdComputeNodeArrayRelation */
841
842
843/**Function********************************************************************
844
845  Synopsis [Swap the BDD variables of primary inputs and it's
846  auxillary BDD ids.]
847
848  SideEffects [None]
849
850******************************************************************************/
851bdd_node *
852SpfdSwapPiAndAltPi(
853  SpfdApplData_t *applData,
854  bdd_node *fun)
855{
856  bdd_manager *ddManager = applData->ddManager;
857  bdd_node **fromVars;
858  bdd_node **toVars;
859  bdd_node *ddTemp;
860  st_table *piAltVars = applData->currPiAltVars;
861  st_generator *stGen;
862  int i,num = st_count(piAltVars);
863  int id,altId;
864     
865  fromVars = ALLOC(bdd_node *,num);
866  toVars = ALLOC(bdd_node *,num);
867  i = 0;
868  st_foreach_item_int(piAltVars,stGen,&id,&altId) {
869    fromVars[i] = bdd_bdd_ith_var(ddManager,altId);
870    toVars[i] = bdd_bdd_ith_var(ddManager,id);
871    i++;
872  }
873  bdd_ref(ddTemp = bdd_bdd_swap_variables(ddManager,fun,fromVars,toVars,num));
874
875  FREE(fromVars);
876  FREE(toVars);
877 
878  return ddTemp;
879} /* End of SpfdSwapPiAndAltPi */
880
881
882/**Function********************************************************************
883
884  Synopsis [The node's BDD is returned as it is without increasing the
885  reference count.]
886
887  SideEffects [None]
888
889******************************************************************************/
890bdd_node *
891SpfdNodeReadLocalBdd(
892  Ntk_Network_t *network,
893  Ntk_Node_t *node)
894{
895  vertex_t *vertexPtr;
896  Mvf_Function_t *mvf;
897  graph_t *partition =
898    (graph_t *) Ntk_NetworkReadApplInfo(network,PART_NETWORK_APPL_KEY);
899  bdd_node *bdd1;
900   
901  vertexPtr = Part_PartitionFindVertexByMddId(partition,
902                                              Ntk_NodeReadMddId(node));
903  mvf = Part_VertexReadFunction(vertexPtr);
904  bdd1 = bdd_extract_node_as_is(array_fetch(bdd_t *,mvf,1));
905
906  return bdd1;
907}
908
909
910/**Function********************************************************************
911
912  Synopsis           [Extract 'percent'\% vectors from the patternArray.]
913
914  SideEffects        [None]
915
916******************************************************************************/
917array_t *
918SpfdFetchInternalPatternArray(
919  array_t *patternArray,
920  int percent,
921  double randomValue)
922{
923  array_t *returnArray;
924  int numVectors,start,end,i;
925
926  /* For internal simulations use 1/10th of the total input pattern vectors */
927  numVectors = array_n(patternArray);
928
929  start = (int)(randomValue*(double)numVectors);
930  end = start + (int)(numVectors*percent/100); 
931 
932  returnArray = array_alloc(char *,0);
933  if (end == start) {
934    array_insert_last(char *,returnArray,
935                      array_fetch(char *,patternArray,start));
936    return returnArray;
937  }
938
939  /* Allocate end - start + 1 size of returnArray */
940  for (i = start; i < end; i++) {
941    array_insert_last(char *,returnArray,
942                      array_fetch(char *,patternArray,i));
943  }
944
945  return returnArray;
946}
947
948/**Function********************************************************************
949
950  Synopsis [Selects a random node or according to fanout count or
951  switched capacitance.]
952
953  Description        [optional]
954
955  SideEffects        [required]
956
957  SeeAlso            [optional]
958
959******************************************************************************/
960Ntk_Node_t *
961SpfdFindNode(
962  Ntk_Network_t *network,
963  array_t *nodeArray)
964{
965  Ntk_Node_t *node1,*maxNode = NIL(Ntk_Node_t);
966  int i;
967
968  if (!array_n(nodeArray))
969    return maxNode;
970 
971  if (spfdSortNodes == RANDOM) {
972    int index,num;
973    float randomValue;
974   
975    num = array_n(nodeArray);
976    if (num < 5) {
977      index = 0;
978    } else {
979      randomValue = ((double)util_random()/(double)(MODULUS1 - 2));
980      index = (int) (randomValue * (double)num);
981    }
982    maxNode = array_fetch(Ntk_Node_t *,nodeArray,index);
983  } else if (spfdSortNodes == MAXSWCAP) {
984    float swc1,maxSwc;
985    float switch1,load1;
986   
987    maxSwc = 0.0;
988    arrayForEachItem(Ntk_Node_t *,nodeArray,i,node1) {
989      switch1 = Truesim_NetworkReadNodeSwitchingProb(network,node1);
990      load1 = Truesim_NetworkReadNodeLoad(network,node1);
991      swc1 = load1 * switch1;
992     
993      if (swc1 > maxSwc) {
994        maxNode = node1;
995        maxSwc = swc1;
996      }
997    }
998  } else if (spfdSortNodes == MINSWCAP) {
999    float swc1,maxSwc;
1000    float switch1,load1;
1001   
1002    maxSwc = MAXINT;
1003    arrayForEachItem(Ntk_Node_t *,nodeArray,i,node1) {
1004      switch1 = Truesim_NetworkReadNodeSwitchingProb(network,node1);
1005      load1 = Truesim_NetworkReadNodeLoad(network,node1);
1006      swc1 = load1 * switch1;
1007     
1008      if (swc1 < maxSwc) {
1009        maxNode = node1;
1010        maxSwc = swc1;
1011      }
1012    }
1013  } else if (spfdSortNodes == MAXFANOUT) {
1014    int numFanout,maxFanout;
1015   
1016    maxFanout = 0;
1017    arrayForEachItem(Ntk_Node_t *,nodeArray,i,node1) {
1018      numFanout = Ntk_NodeReadNumFanouts(node1);
1019      if (numFanout > maxFanout) {
1020        maxNode = node1;
1021        maxFanout = numFanout;
1022      }
1023    }
1024  } else if (spfdSortNodes == MINFANOUT) {
1025    int numFanout,minFanout;
1026   
1027    minFanout = MAXINT;
1028    arrayForEachItem(Ntk_Node_t *,nodeArray,i,node1) {
1029      numFanout = Ntk_NodeReadNumFanouts(node1);
1030      if (numFanout < minFanout) {
1031        maxNode = node1;
1032        minFanout = numFanout;
1033      }
1034    }
1035  }
1036 
1037  return maxNode;
1038 
1039} /* End of SpfdFindNode */
1040
1041
1042/*---------------------------------------------------------------------------*/
1043/* Definition of static functions                                            */
1044/*---------------------------------------------------------------------------*/
1045
Note: See TracBrowser for help on using the repository browser.