source: vis_dev/vis-2.3/src/part/partFine.c @ 43

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

vis2.3
File size: 17.9 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [partFine.c]
4
5  PackageName [part]
6
7  Synopsis [Implements the partition of the network with respect to a
8  list of nodes provided by the user.]
9
10  Description [The network is composed of an arbitrary set of nodes, each of
11  them implementing some function. This partitioning method will produce a
12  graph representing the network in which the nodes specified in a list will be
13  preserved in the graph structure. Different heuristics will control the
14  structure of the rest of the partition.]
15
16  SeeAlso     [partInOut.c partTotal.c]
17
18  Author      [HoonSang Jin]
19
20  Copyright   [This file was created at the University of Colorado at
21  Boulder.  The University of Colorado at Boulder makes no warranty
22  about the suitability of this software for any purpose.  It is
23  presented on an AS IS basis.]
24
25******************************************************************************/
26
27#include "partInt.h"
28
29static char rcsid[] UNUSED = "$Id: partFine.c,v 1.5 2005/04/30 04:00:38 fabio Exp $";
30
31/*---------------------------------------------------------------------------*/
32/* Constant declarations                                                     */
33/*---------------------------------------------------------------------------*/
34
35
36/*---------------------------------------------------------------------------*/
37/* Structure declarations                                                    */
38/*---------------------------------------------------------------------------*/
39
40
41/*---------------------------------------------------------------------------*/
42/* Type declarations                                                         */
43/*---------------------------------------------------------------------------*/
44
45
46/*---------------------------------------------------------------------------*/
47/* Variable declarations                                                     */
48/*---------------------------------------------------------------------------*/
49
50
51/*---------------------------------------------------------------------------*/
52/* Macro declarations                                                        */
53/*---------------------------------------------------------------------------*/
54
55#define PartVertexReadGeneric(vPtr)  ((PartVertexInfo_t *)(vPtr)->user_data)->generic
56#define PartVertexReadGeneric1(vPtr)  ((PartVertexInfo_t *)(vPtr)->user_data)->generic1
57#define BASIC_PARTITION_UNIT 15
58
59/**AutomaticStart*************************************************************/
60
61/*---------------------------------------------------------------------------*/
62/* Static function prototypes                                                */
63/*---------------------------------------------------------------------------*/
64
65static  int             Part_IsFanoutInverter(Ntk_Node_t *node);
66
67/**AutomaticEnd***************************************************************/
68
69
70/*---------------------------------------------------------------------------*/
71/* Definition of exported functions                                          */
72/*---------------------------------------------------------------------------*/
73
74
75/*---------------------------------------------------------------------------*/
76/* Definition of internal functions                                          */
77/*---------------------------------------------------------------------------*/
78
79
80/**Function********************************************************************
81
82  Synopsis [Implements the partition with respect to the given list of
83  nodes.]
84
85  Description []
86
87  SideEffects []
88
89  SeeAlso     [PartPartitionTotal PartPartitionInputsOutputs]
90
91******************************************************************************/
92void
93PartPartitionFineGrain(
94  Ntk_Network_t *network,
95  graph_t       *partition,
96  mdd_t         *careSet)
97{
98  Ntk_Node_t     *node;            /* Pointer to iterate over nodes */
99  Mvf_Function_t *mddFunction;     /* Pointer to a MDD */
100  mdd_manager    *manager;         /* Mdd manager in the partition */
101  st_table       *tableOfLeaves;   /* To store the leaves of the graph */
102  st_table       *mddIdToNodeName; /* For quick lookup of node's name */
103  array_t        *arrayOfMvf;      /* To store the next state functions */
104  array_t        *arrayOfRoots;    /* To store the roots of the graph */
105  lsList         sinkList;         /* Vertices representing comb. outputs */
106  lsGen          gen;              /* To iterate over lists */
107  vertex_t       *toVertex;        /* Will hold the current function vertex */
108  int            i;                /* Index for loops */
109  long           mddId;            /* Will hold the mddId being processed */
110  st_table       *mddSupport;      /* To store the support of the Mvf_Function */
111  st_generator   *stGen;           /* To iterate over the MddIds of the support */
112  vertex_t       *fromVertex;      /* Will hold the current vertex in the support */
113  array_t        *singletonMvfArray;
114  array_t        *singletonArrayOfRoots;
115  array_t        *tmpArrayOfMvf;
116  Mvf_Function_t *nodeMvf;
117  lsList         sortedListOfNodes;     
118  array_t        *sortedArrayOfPartitionNodes;
119  array_t        *unsortedArrayOfPartitionNodes;
120  st_table       *tableOfPartitionNodes;
121  Ntk_Node_t     *fanin, *fanout;
122
123  manager = PartPartitionReadMddManager(partition);
124 
125  /* Make the combinational input  nodes into leaves */
126  tableOfLeaves = st_init_table(st_ptrcmp, st_ptrhash);
127  mddIdToNodeName = st_init_table(st_numcmp, st_numhash);
128  Ntk_NetworkForEachCombInput(network, gen, node) {
129    if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID)
130      Ord_NetworkAssignMddIdForNode(network, node);
131    st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );
132    st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node), 
133              Ntk_NodeReadName(node));
134  }
135
136  unsortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0); 
137  tableOfPartitionNodes = st_init_table(st_ptrcmp, st_ptrhash);
138  /* Make the target node list for partition */
139  Ntk_NetworkForEachNode(network, gen, node) {
140    if(Ntk_NodeTestIsShadow(node))      continue;
141    else if(Ntk_NodeTestIsCombInput(node))      continue;
142    else if(Ntk_NodeTestIsCombOutput(node))     continue;
143    else if(Ntk_NodeReadNumFanouts(node) == 1) { 
144      fanout = Part_GetFanoutFreeLogic(node);
145      if(Ntk_NodeTestIsCombOutput(fanout));
146      else if(Ntk_NodeReadNumFanins(node) > 10);
147      else if(Ntk_NodeReadNumFanins(fanout) == 1)       continue;
148      else if(!Part_CheckLeafNodeCondition(node, tableOfPartitionNodes, 5, 10)) {
149        if(Ntk_NodeReadNumFanins(node) == 1) {
150           fanin = Part_GetFaninFreeLogic(node);
151           if(!fanin)   continue;
152           if(Ntk_NodeTestIsCombInput(fanin))   continue;
153        }
154        continue;
155      }
156/**
157      if(Part_IsFanoutInverter(node))   continue;
158      if(Ntk_NodeReadNumFanins(node) == 1)      continue;
159**/
160    }
161    /**
162    else if(Ntk_NodeReadNumFanins(node) == 1) {
163       fanin = Part_GetFaninFreeLogic(node);
164       if(!fanin)       continue;
165       if(Ntk_NodeTestIsCombInput(fanin))       continue;
166    }
167    **/
168
169    array_insert_last(Ntk_Node_t *, unsortedArrayOfPartitionNodes, node);
170    st_insert(tableOfPartitionNodes, (char *) node, (char *) (long) (-1));
171  }
172
173  /* create sorted array of partition nodes */
174  sortedListOfNodes = Ntk_NetworkComputeTopologicalOrder(network, 
175                               unsortedArrayOfPartitionNodes, tableOfLeaves);
176
177  sortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0); 
178  lsForEachItem(sortedListOfNodes, gen, node){
179    /* sortedListOfNodes includes many internal nodes, need to filter them out */
180    if(st_is_member(tableOfPartitionNodes, (char *) node)){
181      array_insert_last(Ntk_Node_t *, sortedArrayOfPartitionNodes, node);
182      if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID) 
183        Ord_NetworkAssignMddIdForNode(network, node);
184    }   
185  }
186  array_free(unsortedArrayOfPartitionNodes);
187  lsDestroy(sortedListOfNodes, (void (*)(lsGeneric))0); 
188  st_free_table(tableOfPartitionNodes);
189     
190
191  tmpArrayOfMvf = array_alloc(Mvf_Function_t *, 0);
192  for(i=0; i < array_n(sortedArrayOfPartitionNodes); i++){
193    node = array_fetch(Ntk_Node_t *, sortedArrayOfPartitionNodes, i);
194    singletonArrayOfRoots = array_alloc(Ntk_Node_t *, 0);
195    array_insert_last(Ntk_Node_t *, singletonArrayOfRoots, node);
196    singletonMvfArray = Ntm_NetworkBuildMvfs(network, singletonArrayOfRoots, 
197                                             tableOfLeaves, careSet);
198    nodeMvf = array_fetch(Mvf_Function_t *, singletonMvfArray, 0);
199    array_insert_last(Mvf_Function_t *, tmpArrayOfMvf, nodeMvf);
200    array_free(singletonMvfArray);
201    array_free(singletonArrayOfRoots);
202   
203    if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID){
204      Ord_NetworkAssignMddIdForNode(network, node);
205    }
206    st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );   
207    st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node), 
208                Ntk_NodeReadName(node));
209
210  }
211
212
213  arrayOfRoots = array_alloc(Ntk_Node_t *, 0);
214  Ntk_NetworkForEachCombOutput(network, gen, node) {
215    array_insert_last(Ntk_Node_t *, arrayOfRoots, node);
216  }
217  arrayOfMvf = Ntm_NetworkBuildMvfs(network, arrayOfRoots, tableOfLeaves, 
218                                    careSet);
219
220  array_append(arrayOfRoots, sortedArrayOfPartitionNodes);
221  array_append(arrayOfMvf, tmpArrayOfMvf);
222  array_free(sortedArrayOfPartitionNodes);
223  array_free(tmpArrayOfMvf);
224
225
226  /* Create one vertex for every component of arrayOfMvf */
227  for (i=0; i < array_n(arrayOfRoots); i++) {
228    node = array_fetch(Ntk_Node_t *, arrayOfRoots, i);
229    mddId = Ntk_NodeReadMddId(node);
230
231    /* obtain the function attached to the node */
232    mddFunction = array_fetch(Mvf_Function_t *, arrayOfMvf, i);
233
234
235    toVertex = g_add_vertex(partition);
236   
237    /* Update the look-up tables in the graph */
238    st_insert(PartPartitionReadNameToVertex(partition),
239              Ntk_NodeReadName(node), (char *)toVertex);
240    if (mddId != -1) {
241      st_insert(PartPartitionReadMddIdToVertex(partition),
242                (char *)(long) mddId, (char *)toVertex);
243    } 
244    toVertex->user_data = 
245      (gGeneric)PartVertexInfoCreateSingle(Ntk_NodeReadName(node), 
246                                           mddFunction, 
247                                           mddId);
248  } 
249 
250  /* Read the list of vertices on the graph */
251  sinkList = lsCopy(g_get_vertices(partition), (lsGeneric (*)(lsGeneric))0);
252
253  /*
254   * For every function on every combinational output, compute the
255   * support and create vertices in the graph when needed
256   */
257  lsForEachItem(sinkList, gen, toVertex) {
258    mddFunction = PartVertexReadFunction(toVertex);
259    mddSupport = PartCreateFunctionSupportTable(mddFunction);
260
261    /*
262     * Create one edge (and one vertex if necessary) for every element
263     * in mddSupport
264     */
265    st_foreach_item(mddSupport, stGen, &mddId, NULL) {
266      char *name;
267
268      /* Create vertex with the information if needed */
269      if (st_lookup(PartPartitionReadMddIdToVertex(partition), 
270                    (char *)(long) mddId, &fromVertex) == 0) {
271        fromVertex = g_add_vertex(partition);
272       
273        st_lookup(mddIdToNodeName, (char *)(long) mddId, &name);
274
275        /* Update the look-up tables in the graph */
276        st_insert(PartPartitionReadNameToVertex(partition), 
277                  name, (char *)fromVertex);
278        st_insert(PartPartitionReadMddIdToVertex(partition),
279                  (char *)(long) mddId, (char *)fromVertex);
280       
281        /* Create vertex data */
282        fromVertex->user_data = 
283          (gGeneric)PartVertexInfoCreateSingle(name,
284                                               Mvf_FunctionCreateFromVariable(manager,mddId),
285                                               mddId);
286      } 
287     
288      /*
289       * Add the edge to the graph. Make sure a self loop is not added. The
290       * self loop may be produced by a mdd that has in its support the same
291       * variables that represent the mddId of the node.
292       */
293      if (fromVertex != toVertex) {
294        g_add_edge(fromVertex, toVertex);
295      } /* End of if */
296     
297    } /* End of st_foreach_item */
298   
299    /* Clean the support table */
300    st_free_table(mddSupport);
301  } /* End of lsForEachItem */
302 
303  /* Clean up */
304  st_free_table(mddIdToNodeName);
305  st_free_table(tableOfLeaves);
306  array_free(arrayOfRoots);
307  lsDestroy(sinkList, (void (*)(lsGeneric))0);
308  /*
309   * The contents of this array (array of mdds) is not deallocated because the
310   * information has been transferred to the partition structure. All the
311   * functions are stored now as part of the vertex information.
312   */
313  array_free(arrayOfMvf);
314  fprintf(stdout, "NOTICE : current peak memory = %ld\n",
315  bdd_read_peak_memory(manager));
316
317} /* End of PartPartitionCut */
318
319
320/**Function********************************************************************
321
322  Synopsis [Check if the fanout of given node is inverter.]
323
324  Description [ Check if the fanout of given node is inverter.]
325
326  SideEffects []
327
328  SeeAlso     [PartPartitionTotal PartPartitionInputsOutputs]
329
330******************************************************************************/
331int 
332Part_IsFanoutInverter(Ntk_Node_t *node)
333{
334  Ntk_Node_t *fanout;
335
336  fanout = Part_GetFanoutFreeLogic(node);
337  if(!fanout)   return(1);
338  if(Ntk_NodeReadNumFanins(fanout) == 1)        return(1);
339  else                                  return(0);
340
341}
342
343/**Function********************************************************************
344
345  Synopsis [Check if the node can be assumed as leaf node based on given threshold.]
346
347  Description [ This function identify the leaf node for fine grain partition based on threshold.]
348
349  SideEffects []
350
351  SeeAlso     [PartPartitionTotal PartPartitionInputsOutputs]
352
353******************************************************************************/
354int
355Part_CheckLeafNodeCondition(Ntk_Node_t *node, 
356                            st_table *leafTable,
357                            int fanoutFreeLimit,
358                            int numVariableLimit)
359{
360  int nVar, nDepth, i;
361  Ntk_Node_t *fanout, *tnode, *tfanin;
362  st_table *ownTable;
363
364
365  nVar = Ntk_NodeReadNumFanins(node);
366  nDepth = 0;
367  fanout = node;
368  ownTable = st_init_table(st_ptrcmp, st_ptrhash);
369  while(1) {
370    if(nDepth > fanoutFreeLimit)return(1);
371    if(nVar > numVariableLimit) return(1);
372
373    if(!st_lookup(leafTable, fanout, &tnode)) {
374       fanout = Part_GetFanoutFreeLogic(fanout);
375       if(fanout == 0)  break;
376       if(Ntk_NodeTestIsCombInput(fanout))      break;
377       if(Ntk_NodeTestIsCombOutput(fanout))     break;
378    }
379    else break;
380    nDepth++;
381    if(fanout == 0)     break;
382    nVar += Img_CutCalcTransitiveFanin(leafTable, ownTable, fanout,
383    node, numVariableLimit);
384    if(nVar > numVariableLimit) {
385      st_free_table(ownTable);
386      return(1);
387    }
388  }
389
390  Ntk_NodeForEachFanin(node, i, tfanin) {
391    if(tfanin == 0)     continue;
392    if(Ntk_NodeReadNumFanouts(tfanin) != 1)     continue;
393    nVar += Img_CutCalcTransitiveFanin(leafTable, ownTable, tfanin, 0, numVariableLimit)-1;
394    if(nVar > numVariableLimit) {       
395      st_free_table(ownTable);
396      return(1);
397    }
398  }
399  if(nVar > numVariableLimit) {
400    st_free_table(ownTable);
401    return(1);
402  }
403/**
404  fanin = node;
405  nDepth = 0;
406  while(1) {
407    if(nDepth > fanoutFreeLimit)return(1);
408    if(nVar > numVariableLimit) return(1);
409    if(!st_lookup(leafTable, (char *)fanin, (char **)&tnode)) {
410
411      Ntk_NodeForEachFanin(fanin, i, tfanin) {
412        if(tfanin == 0) continue;
413        if(Ntk_NodeReadNumFanouts(tfanin) != 1) continue;
414        nVar += Ntk_NodeReadNumFanins(tfanin) - 1;
415      }
416      if(nVar > numVariableLimit)       return(1);
417
418      fanin = Part_GetFaninFreeLogic(fanin);
419      if(fanin == 0)    break;
420      if(Ntk_NodeTestIsCombInput(fanin))        break;
421      if(Ntk_NodeTestIsCombOutput(fanin))       break;
422
423    }
424    else break;
425    nDepth++;
426   
427  }
428**/
429  return(0);
430}
431
432/**Function********************************************************************
433
434  Synopsis [Compute the number of support variables of given node.]
435
436  Description [ Compute the number of support variables of given node.]
437
438  SideEffects []
439
440  SeeAlso     [PartPartitionTotal PartPartitionInputsOutputs]
441
442******************************************************************************/
443int
444Img_CutCalcTransitiveFanin(st_table *table, 
445                           st_table *ownTable,
446                           Ntk_Node_t *node, 
447                           Ntk_Node_t *fanin,
448                           int limit)
449{
450  int i, nVar;
451  Ntk_Node_t *tfanin, *tnode;
452
453  nVar = 0;
454  Ntk_NodeForEachFanin(node, i, tfanin) {
455    if(tfanin == fanin) continue;
456    if(tfanin == 0)     continue;
457    if(Ntk_NodeReadNumFanouts(tfanin) != 1){
458      if(!st_lookup(ownTable, tfanin, &tnode)) {
459        st_insert(ownTable, tfanin, tfanin);
460        nVar++;
461      }
462      continue;
463    }
464    if(Ntk_NodeTestIsCombInput(tfanin)) {
465      if(!st_lookup(ownTable, tfanin, &tnode)) {
466        st_insert(ownTable, tfanin, tfanin);
467        nVar++;
468      }
469      continue;
470    }
471    if(Ntk_NodeTestIsCombOutput(tfanin)) {
472      if(!st_lookup(ownTable, tfanin, &tnode)) {
473        st_insert(ownTable, tfanin, tfanin);
474        nVar++;
475      }
476      continue;
477    }
478    if(!st_lookup(table, tfanin, &tnode)) {
479      nVar += Img_CutCalcTransitiveFanin(table, ownTable, tfanin,  0, limit);
480    }
481    else
482      nVar++;
483    if(nVar > limit)    return(nVar);
484  }
485  return(nVar);
486}
487
488/**Function********************************************************************
489
490  Synopsis [Check if the fanin of given node is fanout free.]
491
492  Description [Check if the fanin of given node is fanout free.]
493
494  SideEffects []
495
496  SeeAlso     [PartPartitionTotal PartPartitionInputsOutputs]
497
498******************************************************************************/
499Ntk_Node_t *
500Part_GetFaninFreeLogic(Ntk_Node_t *node)
501{
502  int i;
503  Ntk_Node_t *fanin;
504
505  Ntk_NodeForEachFanin(node, i, fanin) {
506    if(Ntk_NodeReadNumFanouts(fanin) != 1)      continue;
507    return(fanin); 
508  }
509  return(0);
510}
511
512/**Function********************************************************************
513
514  Synopsis [Check if the fanout of given node is fanout free.]
515
516  Description [Check if the fanout of given node is fanout free.]
517
518  SideEffects []
519
520  SeeAlso     [PartPartitionTotal PartPartitionInputsOutputs]
521
522******************************************************************************/
523Ntk_Node_t *
524Part_GetFanoutFreeLogic(Ntk_Node_t *node)
525{
526  int i;
527  Ntk_Node_t *fanout;
528
529  if(Ntk_NodeReadNumFanouts(node) != 1) return(0);
530  Ntk_NodeForEachFanout(node, i, fanout) {
531    return(fanout); 
532  }
533  return(0);
534}
Note: See TracBrowser for help on using the repository browser.