source: vis_dev/vis-2.3/src/part/partPartial.c @ 93

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

vis2.3
File size: 12.9 KB
RevLine 
[14]1/**CFile***********************************************************************
2
3  FileName    [partPartial.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      [Sunil P Khatri]
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: partPartial.c,v 1.10 2005/04/16 14:52:45 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
56/**AutomaticStart*************************************************************/
57
58/*---------------------------------------------------------------------------*/
59/* Static function prototypes                                                */
60/*---------------------------------------------------------------------------*/
61
62
63/**AutomaticEnd***************************************************************/
64
65
66/*---------------------------------------------------------------------------*/
67/* Definition of exported functions                                          */
68/*---------------------------------------------------------------------------*/
69
70
71/*---------------------------------------------------------------------------*/
72/* Definition of internal functions                                          */
73/*---------------------------------------------------------------------------*/
74
75
76/**Function********************************************************************
77
78  Synopsis [Implements the partition with respect to the given list of
79  nodes.]
80
81  SideEffects []
82
83  SeeAlso     [PartPartitionTotal PartPartitionInputsOutputs]
84
85******************************************************************************/
86void
87PartPartitionPartial(
88  Ntk_Network_t *network,
89  graph_t       *partition,
90  lsList        rootList,
91  lsList        leaveList,
92  mdd_t         *careSet,
93  lsList        nodeList,
94  int           inTermsOfCombInputs)
95{
96  Ntk_Node_t     *node;            /* Pointer to iterate over nodes */
97  Mvf_Function_t *mddFunction;     /* Pointer to a MDD */
98  mdd_manager    *manager;         /* Mdd manager in the partition */
99  st_table       *tableOfLeaves;   /* To store the leaves of the graph */
100  st_table       *mddIdToNodeName; /* For quick lookup of node's name */
101  array_t        *arrayOfMvf;      /* To store the next state functions */
102  array_t        *arrayOfRoots;    /* To store the roots of the graph */
103  lsList         sinkList;         /* Vertices representing comb. outputs */
104  lsGen          gen;              /* To iterate over lists */
105  vertex_t       *toVertex;        /* Will hold the current function vertex */
106  int            i;                /* Index for loops */
107  long           mddId;            /* Will hold the mddId being processed */
108  st_table       *mddSupport;      /* To store the support of the Mvf_Function */
109  st_generator   *stGen;           /* To iterate over the MddIds of the support */
110  vertex_t       *fromVertex;      /* Will hold the current vertex in the support */
111  char           *nodeName;
112  array_t        *singletonMvfArray;
113  array_t        *singletonArrayOfRoots;
114  array_t        *tmpArrayOfMvf;
115  Mvf_Function_t *nodeMvf;
116  lsList         sortedListOfNodes;     
117  array_t        *sortedArrayOfPartitionNodes;
118  array_t        *unsortedArrayOfPartitionNodes;
119  st_table       *tableOfPartitionNodes;
120  array_t        *validNodeArray;
121  array_t        *invalidNodeArray;
122  int            chars_printed;
123
124  assert(rootList == (lsList)0);
125  assert(leaveList == (lsList)0);
126  manager = PartPartitionReadMddManager(partition);
127  invalidNodeArray = array_alloc(char *, 0);
128  validNodeArray = array_alloc(char *, 0);
129 
130  /* check that nodes in nodeList are valid ones */
131  lsForEachItem(nodeList, gen, nodeName){
132    node = Ntk_NetworkFindNodeByName(network, nodeName);
133    if(node == NIL(Ntk_Node_t)){
134      array_insert_last(char *, invalidNodeArray, nodeName);
135    }
136    else{
137      array_insert_last(char *, validNodeArray, nodeName);     
138    }
139  }
140  if(array_n(invalidNodeArray) > 0){
141    fprintf(stdout, "The following node(s) are being ignored in the partition:\n");
142    chars_printed = 0;
143    for(i = 0; i < array_n(invalidNodeArray); i++){
144      fprintf(stdout, "%s ", array_fetch(char *, invalidNodeArray, i));
145      chars_printed += strlen(array_fetch(char *, invalidNodeArray, i));
146      if(chars_printed >60){
147        chars_printed = 0;
148        fprintf(stdout, "\n");
149      }
150    }
151    fprintf(stdout, "\nThey are either invalid names or have been swept away at \n");
152    fprintf(stdout, "the end of the flatten_network command. Use <flatten_network -s> \n");
153    fprintf(stdout, "to avoid performing a sweep after the flatten command, \n");       
154  }
155  array_free(invalidNodeArray);
156 
157
158  /* Make the combinational input  nodes into leaves */
159  tableOfLeaves = st_init_table(st_ptrcmp, st_ptrhash);
160  mddIdToNodeName = st_init_table(st_numcmp, st_numhash);
161  Ntk_NetworkForEachCombInput(network, gen, node) {
162    st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );
163    st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node), 
164              Ntk_NodeReadName(node));
165  }
166 
167  /* create temporary array and table of partition nodes */
168  unsortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0); 
169  tableOfPartitionNodes = st_init_table(st_ptrcmp, st_ptrhash);
170  for(i = 0; i < array_n(validNodeArray); i++){
171    nodeName = array_fetch(char *, validNodeArray, i);
172    node = Ntk_NetworkFindNodeByName(network, nodeName);
173    assert(!Ntk_NodeTestIsShadow(node));
174    /* make sure that the node is not a CI or CO */
175    if(!Ntk_NodeTestIsCombInput(node) && !Ntk_NodeTestIsCombOutput(node)){
176      array_insert_last(Ntk_Node_t *, unsortedArrayOfPartitionNodes, node);
177      st_insert(tableOfPartitionNodes, (char *) node, (char *) (long) (-1));
178    }
179  }
180  array_free(validNodeArray);
181
182  /* create sorted array of partition nodes */
183  sortedListOfNodes = Ntk_NetworkComputeTopologicalOrder(network, unsortedArrayOfPartitionNodes, tableOfLeaves);
184  sortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0); 
185  lsForEachItem(sortedListOfNodes, gen, node){
186    /* sortedListOfNodes includes many internal nodes, need to filter them out */
187    if(st_is_member(tableOfPartitionNodes, (char *) node)){
188      array_insert_last(Ntk_Node_t *, sortedArrayOfPartitionNodes, node);     
189    }   
190  }
191  array_free(unsortedArrayOfPartitionNodes);
192  lsDestroy(sortedListOfNodes, (void (*)(lsGeneric))0); 
193  st_free_table(tableOfPartitionNodes);
194     
195
196  /* Create mvfs for nodes in sortedArrayOfPartitionNodes */
197  tmpArrayOfMvf = array_alloc(Mvf_Function_t *, 0);
198  for(i=0; i < array_n(sortedArrayOfPartitionNodes); i++){
199    node = array_fetch(Ntk_Node_t *, sortedArrayOfPartitionNodes, i);
200    singletonArrayOfRoots = array_alloc(Ntk_Node_t *, 0);
201    array_insert_last(Ntk_Node_t *, singletonArrayOfRoots, node);
202    singletonMvfArray = Ntm_NetworkBuildMvfs(network, singletonArrayOfRoots, 
203                                             tableOfLeaves, careSet);
204    nodeMvf = array_fetch(Mvf_Function_t *, singletonMvfArray, 0);
205    array_insert_last(Mvf_Function_t *, tmpArrayOfMvf, nodeMvf);
206    array_free(singletonMvfArray);
207    array_free(singletonArrayOfRoots);
208
209    /* now create an mddId for this node, and make it a leaf */
210    if(inTermsOfCombInputs == 0){
211      if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID){
212        Ord_NetworkAssignMddIdForNode(network, node);
213      }
214      st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );   
215      st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node), 
216                Ntk_NodeReadName(node));
217    }
218  }
219
220  /* Make the combinational output nodes into roots */
221  arrayOfRoots = array_alloc(Ntk_Node_t *, 0);
222  Ntk_NetworkForEachCombOutput(network, gen, node) {
223    array_insert_last(Ntk_Node_t *, arrayOfRoots, node);
224  }
225
226  /* build mvfs of nodes in arrayOfMvf in terms of partition nodes and comb inputs */
227  arrayOfMvf = Ntm_NetworkBuildMvfs(network, arrayOfRoots, tableOfLeaves, 
228                                    careSet);
229  array_append(arrayOfRoots, sortedArrayOfPartitionNodes);
230  array_append(arrayOfMvf, tmpArrayOfMvf);
231  array_free(sortedArrayOfPartitionNodes);
232  array_free(tmpArrayOfMvf);
233
234  /* Create one vertex for every component of arrayOfMvf */
235  for (i=0; i < array_n(arrayOfRoots); i++) {
236    node = array_fetch(Ntk_Node_t *, arrayOfRoots, i);
237    mddId = (long) Ntk_NodeReadMddId(node);
238
239    /* obtain the function attached to the node */
240    mddFunction = array_fetch(Mvf_Function_t *, arrayOfMvf, i);
241    toVertex = g_add_vertex(partition);
242   
243    /* Update the look-up tables in the graph */
244    st_insert(PartPartitionReadNameToVertex(partition),
245              Ntk_NodeReadName(node), (char *)toVertex);
246    if (mddId != -1) {
247      st_insert(PartPartitionReadMddIdToVertex(partition),
248                (char *)mddId, (char *)toVertex);
249    } 
250    toVertex->user_data = 
251      (gGeneric)PartVertexInfoCreateSingle(Ntk_NodeReadName(node), 
252                                           mddFunction, 
253                                           (int) mddId);
254  } 
255 
256  /* Read the list of vertices on the graph */
257  sinkList = lsCopy(g_get_vertices(partition), (lsGeneric (*)(lsGeneric))0);
258
259  /*
260   * For every function on every combinational output, compute the
261   * support and create vertices in the graph when needed
262   */
263  lsForEachItem(sinkList, gen, toVertex) {
264    mddFunction = PartVertexReadFunction(toVertex);
265    mddSupport = PartCreateFunctionSupportTable(mddFunction);
266
267    /*
268     * Create one edge (and one vertex if necessary) for every element
269     * in mddSupport
270     */
271    st_foreach_item(mddSupport, stGen, &mddId, NULL) {
272      char *name;
273
274      /* Create vertex with the information if needed */
275      if (st_lookup(PartPartitionReadMddIdToVertex(partition), 
276                    (char *)mddId, &fromVertex) == 0) {
277        fromVertex = g_add_vertex(partition);
278       
279        st_lookup(mddIdToNodeName, (char *)mddId, &name);
280
281        /* Update the look-up tables in the graph */
282        st_insert(PartPartitionReadNameToVertex(partition), 
283                  name, (char *)fromVertex);
284        st_insert(PartPartitionReadMddIdToVertex(partition),
285                  (char *) mddId, (char *)fromVertex);
286       
287        /* Create vertex data */
288        fromVertex->user_data = 
289          (gGeneric)PartVertexInfoCreateSingle(name,
290                                               Mvf_FunctionCreateFromVariable(manager, (int) mddId),
291                                               (int) mddId);
292      } 
293     
294      /*
295       * Add the edge to the graph. Make sure a self loop is not added. The
296       * self loop may be produced by a mdd that has in its support the same
297       * variables that represent the mddId of the node.
298       */
299      if (fromVertex != toVertex) {
300        g_add_edge(fromVertex, toVertex);
301      } /* End of if */
302     
303    } /* End of st_foreach_item */
304   
305    /* Clean the support table */
306    st_free_table(mddSupport);
307  } /* End of lsForEachItem */
308 
309  /* Clean up */
310  st_free_table(mddIdToNodeName);
311  st_free_table(tableOfLeaves);
312  array_free(arrayOfRoots);
313  lsDestroy(sinkList, (void (*)(lsGeneric))0);
314  /*
315   * The contents of this array (array of mdds) is not deallocated because the
316   * information has been transferred to the partition structure. All the
317   * functions are stored now as part of the vertex information.
318   */
319  array_free(arrayOfMvf);
320
321} /* End of PartPartitionPartial */
322
323/*---------------------------------------------------------------------------*/
324/* Definition of static functions                                            */
325/*---------------------------------------------------------------------------*/
Note: See TracBrowser for help on using the repository browser.