source: vis_dev/vis-2.3/src/part/partGroup.c @ 23

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

vis2.3
File size: 105.5 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [partGroup.c]
4
5  PackageName [part]
6
7  Synopsis    [Routines for grouping vertices.]
8
9  Description [The first method groups vertices based on the hierachy of the
10  system.  Normally, the hierachy is formed in the early phase of the
11  design. We use this information to group latches. The method expects the
12  high level description languages to BLIF conversion utilities such as vl2mv
13  to preserve the original hierachy. The second method is explained in the
14  following paper.
15    H. Cho, G. D. Hachtel, E. Macii, B. Plessier, F. Somenzi," A
16    Structural Approach to State Space Decomposition for Approximate
17    Reachability Analysis," ICCD, pp.236-239, 1994. Traversal," EDAC.
18  This method groups vertices based on the latch dependency(relation between
19  latches) and the latch correlation(resemblance of latches in terms of the
20  support variables.]
21
22  Author      [Woohyuk Lee, Jae-Young Jang]
23
24  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
25  All rights reserved.
26
27  Permission is hereby granted, without written agreement and without license
28  or royalty fees, to use, copy, modify, and distribute this software and its
29  documentation for any purpose, provided that the above copyright notice and
30  the following two paragraphs appear in all copies of this software.
31
32  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
33  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
34  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
35  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36
37  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
38  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
39  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
40  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
41  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
42
43******************************************************************************/
44
45#include "partInt.h"
46
47static char rcsid[] UNUSED = "$Id: partGroup.c,v 1.51 2005/04/28 14:15:50 fabio Exp $";
48
49/*---------------------------------------------------------------------------*/
50/* Constant declarations                                                     */
51/*---------------------------------------------------------------------------*/
52
53
54/*---------------------------------------------------------------------------*/
55/* Type declarations                                                         */
56/*---------------------------------------------------------------------------*/
57
58
59/*---------------------------------------------------------------------------*/
60/* Structure declarations                                                    */
61/*---------------------------------------------------------------------------*/
62
63
64/*---------------------------------------------------------------------------*/
65/* Variable declarations                                                     */
66/*---------------------------------------------------------------------------*/
67
68
69/*---------------------------------------------------------------------------*/
70/* Macro declarations                                                        */
71/*---------------------------------------------------------------------------*/
72
73
74/**AutomaticStart*************************************************************/
75
76/*---------------------------------------------------------------------------*/
77/* Static function prototypes                                                */
78/*---------------------------------------------------------------------------*/
79
80static char * PartCreateDependencyMatrix(Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex);
81static float * PartCreateCorrelationMatrixFromSupport(Part_SubsystemInfo_t *partSubInfo);
82static float * PartCreateCorrelationMatrixFromBDD(Part_SubsystemInfo_t *partSubInfo);
83static float PartVertexComputeCorrelation(int index1, int index2, array_t *arrayOfInputSupportTable, Part_SubsystemInfo_t *partSubInfo);
84static array_t * PartVertexComputeAgreement(mdd_manager *mddMgr, int index1, int index2, array_t *arrayOfBddArray);
85static float * PartCreateAffinityMatrix(char *arrayOfConnectivity, float *arrayOfCorrelation, Part_SubsystemInfo_t *partSubInfo);
86static array_t * PartGetConnectedComponent(float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *indexToPtr);
87static void PartFindCC(int *next, int *ccId, array_t *arrayOfCCIndex, float *arrayOfAffinity, array_t *arrayOfFrom, Part_SubsystemInfo_t *PartSubInfo);
88static array_t * PartBreakingAggregating(array_t *arrayOfInit, float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex, char *arrayOfDependency);
89static array_t * PartBreakingBigConnectedComponent(array_t *arrayOfCC, array_t *ccCheck, array_t *arrayOfSeed, float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex);
90static array_t * PartAggregating(array_t *arrayOfSmall, float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex);
91static array_t * PartCreateSubSystemWithGroupIndex(Part_SubsystemInfo_t *partSubInfo, array_t *arrayOfLatchNames, array_t *arrayOfGroupIndex);
92static Ntk_Node_t * PartSelectCloseNode(Ntk_Node_t *seed, array_t *arrayOfCC, array_t *ccCheck, float *arrayOfAffinity, st_table *ptrToIndex);
93static int PartSelectCloseSeedIndex(Ntk_Node_t *variable, array_t *arrayOfSeed, float *arrayOfAffinity, st_table *ptrToIndex, array_t *seedFull, int bound);
94static Ntk_Node_t * PartSelectFarNode(Ntk_Node_t *seed, array_t *cc, array_t *ccCheck, float *arrayOfAffinity, st_table *ptrToIndex);
95static float * PartGetGroupMatrixRegular(array_t *arrayOfCluster, char *arrayOfGivenMatrix, st_table *ptrToIndex, int nVertices);
96static float * PartGetGroupMatrixSym(array_t *arrayOfCluster, float *arrayOfGivenMatrix, st_table *ptrToIndex);
97static int PartSelectCCIndexOfMinSupport(array_t *arrayOfSmall, array_t *ccCheck, Part_SubsystemInfo_t *partSubInfo);
98static Ntk_Node_t * PartSelectNodeOfMinSupport(array_t *cc, array_t *ccCheck, Part_SubsystemInfo_t *partSubInfo);
99static int PartSelectFarCCIndex(int seedIndex, array_t *arrayOfSmall, float *arrayOfGroupAff, Part_SubsystemInfo_t *partSubInfo, array_t *ccCheck);
100static int PartSelectCloseCCIndex(int seedIndex, array_t *arrayOfSmall, float *arrayOfGroupAff, array_t *ccCheck);
101static Part_Subsystem_t* PartCreateSingleSubSystem(array_t *arrayOfNodes, Ntk_Network_t *network);
102static array_t * PartReadLatchNameFromLatchInput(Ntk_Network_t *network, Ntk_Node_t *latchInput);
103static void PartArrayOfArrayFree(array_t *arrayOfMatrix);
104static float PartGetElementFromSymMatrix(float *matrix, int i, int j);
105static void PartPrintArrayArray(void *arrayOfMatrix, int nVertices, int type);
106static int strCompare(const void * name1, const void * name2);
107static int numCompare(const void * num1, const void * num2);
108static array_t *PartCreateSubsystemWithCTL(Part_SubsystemInfo_t *, array_t *, array_t *, boolean , boolean );
109static array_t *PartCreateSubsystemWithCtlAndLtl(Part_SubsystemInfo_t *, array_t *, array_t *, array_t *, boolean , boolean, boolean );
110
111
112/**AutomaticEnd***************************************************************/
113
114
115/*---------------------------------------------------------------------------*/
116/* Definition of exported functions                                          */
117/*---------------------------------------------------------------------------*/
118
119/**Function********************************************************************
120
121  Synopsis    [From the given latch data inputs, create array of
122  sub-partitions.]
123
124  Description [From the given latch data inputs, create array of sub-partitions
125  of vertices. Latch data inputs are given as "latchDataInputNames" and
126  includes subset of all latches in a system.  Since the vertices are defined
127  as the latch-input nodes, one may think of the process as grouping of
128  latches in the network.  "amc_sizeof_group" value may be set by the user by
129  using the set command from the vis shell. The function uses this value to
130  limit the number of vertices(latches) in a single group(subsystem). More
131  vertices in a subsystem implies its representation is closer to the exact
132  system.  When the value is not given by the user, the default value of 8
133  vertices(latches) is used. The routine uses hierachical grouping method.
134  That is, the latches in the same sub-processes(i.e. same .subckt in BLIF
135  format), are grouped together whenever possible.
136
137  Initial partition must be performed before executing this routine.]
138
139  SideEffects []
140
141  SeeAlso     []
142
143******************************************************************************/
144array_t *
145Part_PartGroupVeriticesBasedOnHierarchy(
146  Ntk_Network_t *network,
147  array_t *latchDataInputNames)
148{
149  graph_t       *partition;
150  array_t       *arrayOfPartition = NIL(array_t);
151  array_t       *arrayOfGroups = NIL(array_t);
152  array_t       *arrayOfLatches = NIL(array_t);
153  array_t       *arrayOfLatchSort = NIL(array_t);
154  st_table      *vertexTable = NIL(st_table);
155  int           numOfVertex, reset;
156  int           i, j, k;
157  char          *numberOfVertexInGroup;
158  char          *flagValue;
159  char          *latchName, *name;
160  st_table      *latchDataInputNameTable;
161  Part_Subsystem_t *testSubsystem;
162
163  partition = Part_NetworkReadPartition(network);
164  if (partition == NIL(graph_t)) {
165    error_append("Network has no partition. Cannot create sub machines.");
166    return (NIL(array_t));
167  }
168
169  /*
170   * Convert graph of vertices into array of table of vertices.
171   */
172
173  numberOfVertexInGroup = Cmd_FlagReadByName("amc_sizeof_group");
174  if (numberOfVertexInGroup != NIL(char)) {
175    numOfVertex = atoi(numberOfVertexInGroup);
176    reset = atoi(numberOfVertexInGroup);
177  }
178  else {
179    /* default value */
180    numOfVertex = 8;
181    reset = 8;
182  }
183
184  latchDataInputNameTable = st_init_table(strcmp, st_strhash);
185
186  arrayForEachItem(char *, latchDataInputNames, i, name) {
187    st_insert(latchDataInputNameTable, (char *)name, (char *)NULL);
188  }
189
190  /*
191   * In the first phase, group latches by the processes.
192   * That is, group latches that are within same sub-circuit.
193   */
194
195  arrayOfGroups = array_alloc(array_t *, 0);
196
197  {
198    Ntk_Node_t  *latch;
199    lsGen       gen;
200    char        *groupName = util_strsav(" ");
201
202    arrayOfLatchSort = array_alloc(char *, 0);
203    Ntk_NetworkForEachLatch(network, gen, latch) {
204      Ntk_Node_t *latchInput = Ntk_LatchReadDataInput(latch);
205      char *latchInputName = Ntk_NodeReadName(latchInput);
206      vertex_t *vertex = Part_PartitionFindVertexByName(partition,
207                                                        latchInputName);
208      if ((vertex != NIL(vertex_t)) &&
209          (st_lookup(latchDataInputNameTable, latchInputName, NIL(char *)))) {
210        array_insert_last(char *, arrayOfLatchSort, Ntk_NodeReadName(latch));
211      }
212    }
213    array_sort(arrayOfLatchSort, strCompare);
214
215    arrayForEachItem(char *, arrayOfLatchSort, i, latchName) {
216      char *suffixLatchName, *currentGroupName;
217
218      suffixLatchName = util_strsav(latchName);
219
220      /* Extract out group name into the string "groupName" and leave
221         rest in suffixLatchName. */
222
223      currentGroupName = strtok(suffixLatchName, ".");
224
225      if (strcmp(groupName, currentGroupName)) {
226        if (strcmp(groupName, " ")) {
227          array_insert_last(array_t *, arrayOfGroups, arrayOfLatches);
228        }
229        FREE(groupName);
230        groupName = util_strsav(currentGroupName);
231        arrayOfLatches = array_alloc(char *, 0);
232      }
233      FREE(currentGroupName);
234      array_insert_last(char *, arrayOfLatches, latchName);
235    }
236    FREE(groupName);
237  }
238
239  array_free(arrayOfLatchSort);
240  st_free_table(latchDataInputNameTable);
241
242  /* Fill in the last arrayOfLatches */
243  array_insert_last(array_t *, arrayOfGroups, arrayOfLatches);
244
245  /*
246   * In the second phase, further break latch group into
247   * smaller group size according to the "amc_sizeof_group".
248   */
249
250  arrayOfPartition = array_alloc(Part_Subsystem_t *, 0);
251
252  arrayForEachItem(array_t *, arrayOfGroups, k, arrayOfLatches) {
253    char        *latchName;
254    int         numOfLatches = array_n(arrayOfLatches);
255
256    arrayForEachItem(char *, arrayOfLatches, i, latchName) {
257
258      if (numOfVertex == reset)
259        vertexTable = st_init_table(strcmp, st_strhash);
260
261      st_insert(vertexTable, latchName, (char *)NULL);
262
263      if ((numOfVertex == 1) || (numOfLatches == i+1)) {
264        /* testSubsystem freed by calling function  */
265        testSubsystem = ALLOC(Part_Subsystem_t, 1);
266        testSubsystem->vertexNameTable = vertexTable;
267        testSubsystem->subsystemFanIn = NIL(array_t);
268        testSubsystem->subsystemFanOut = NIL(array_t);
269
270        array_insert_last(Part_Subsystem_t *, arrayOfPartition, testSubsystem);
271        numOfVertex = reset;
272      }
273      else
274        numOfVertex--;
275    } /* End of arrayForEachItem(arrayOfLatches) */
276  } /* End of arrayForEachItem(arrayOfGroups) */
277
278  /* Free arrayOfGroups, arrayOfLatches */
279  arrayForEachItem(array_t *, arrayOfGroups, i, arrayOfLatches) {
280    array_free(arrayOfLatches);
281  }
282  array_free(arrayOfGroups);
283
284  /*
285   * Currently this function is used only from amc package.
286   * When the function gets popular use parameter passing rather that this
287   * ugly method.
288   */
289  flagValue = Cmd_FlagReadByName("amc_use_MBM");
290  if (flagValue != NIL(char)) {
291    array_t     *latchNodeArray;
292    array_t     *faninNodeArray;
293    array_t     *faninLatchArray;
294
295    /*
296     * Fill in the subsystem dependencies using the latch dependencies.
297     */
298
299    arrayForEachItem(Part_Subsystem_t *, arrayOfPartition, i, testSubsystem) {
300      array_t           *fanInArray = array_alloc(int, 0);
301      st_table          *vertexTable = testSubsystem->vertexNameTable;
302      st_generator      *stGen;
303      char              *latchName;
304      Ntk_Node_t        *latchNode;
305
306      latchNodeArray = array_alloc(Ntk_Node_t *, 0);
307      faninLatchArray = array_alloc(Ntk_Node_t *, 0);
308
309      /* Convert table of latch names into array of latch nodes */
310      st_foreach_item(vertexTable, stGen, &latchName, NIL(char *)) {
311        latchNode = Ntk_NetworkFindNodeByName(network, latchName);
312        array_insert_last(Ntk_Node_t *, latchNodeArray, latchNode);
313      }
314
315      /* Find the transitive fanin nodes */
316      faninNodeArray = Ntk_NodeComputeCombinationalSupport(network,
317                        latchNodeArray, FALSE);
318
319      /* Find the transitive fanin latches from the fanin nodes */
320      if (array_n(faninNodeArray) != 0) {
321        int x;
322        arrayForEachItem(Ntk_Node_t *, faninNodeArray, x, latchNode) {
323          if (Ntk_NodeTestIsLatch(latchNode) == TRUE) {
324            array_insert_last(Ntk_Node_t *, faninLatchArray, latchNode);
325          }
326        }
327      }
328
329      /* Find the fanin subsystems */
330      if (array_n(faninLatchArray) != 0) {
331        Part_Subsystem_t *scanSubsystem;
332        int y;
333
334        arrayForEachItem(Part_Subsystem_t *, arrayOfPartition, j,
335                scanSubsystem) {
336          /* Scan subsystems that aren't the currently considered subsytem */
337          st_table      *otherVertexTable = scanSubsystem->vertexNameTable;
338
339          if (i != j) {
340            arrayForEachItem(Ntk_Node_t *, faninLatchArray, y, latchNode) {
341              char *latchName = Ntk_NodeReadName(latchNode);
342              if (st_lookup(otherVertexTable, latchName, NIL(char *))) {
343                array_insert_last(int, fanInArray, j);
344                break;
345              }
346            } /* end of arrayForEachItem(Ntk_Node_t *) */
347          } /* end of if (i != j) */
348        }
349      } /* end of if (array_n(faninLatchArray) != 0) */
350
351      /* Update fanInArray into the subsystem */
352      testSubsystem->subsystemFanIn = fanInArray;
353
354      array_free(latchNodeArray);
355      array_free(faninNodeArray);
356      array_free(faninLatchArray);
357    } /* end of arrayForEachItem(Part_Subsystem_t *) */
358  } /* end of if (!flagValue) */
359
360  /*
361   * Currently this function is used only from amc package.
362   * When the function gets popular use parameter passing rather that this
363   * ugly method.
364   */
365
366  flagValue = Cmd_FlagReadByName("amc_use_MBM");
367  if (flagValue != NIL(char)) {
368    st_table *fanOutDependencies = Ntk_NetworkComputeLatchDependencies(network);
369
370    /*
371     * Fill in the fanout dependencies of subsystems.
372     */
373    arrayForEachItem(Part_Subsystem_t *, arrayOfPartition, i, testSubsystem) {
374      array_t           *fanOutArray = array_alloc(int, 0);
375      st_table          *vertexTable = testSubsystem->vertexNameTable;
376      st_generator      *stGen;
377      char              *latchName;
378      st_table          *everyFanOuts = st_init_table(st_ptrcmp, st_ptrhash);
379
380      /*
381       * For the latches in this subsystem,
382       * find all latches that transitively fanouts from the latches
383       * inside this subsystem. Store it in a hash table, "everyFanOuts".
384       */
385      st_foreach_item(vertexTable, stGen, &latchName, NIL(char *)) {
386        Ntk_Node_t      *latchNode;
387        lsList          fanOutLatchList;
388        lsGen           gen;
389        lsGeneric       data;
390
391        latchNode = Ntk_NetworkFindNodeByName(network, latchName);
392        st_lookup(fanOutDependencies, latchNode, &fanOutLatchList);
393
394        /* Obtain all fanout latches coming from latches of this subsystem */
395        gen = lsStart(fanOutLatchList);
396        while (lsNext(gen, &data, LS_NH) == LS_OK) {
397          st_insert(everyFanOuts, data, NULL);
398        }
399        (void) lsFinish(gen);
400        lsDestroy(fanOutLatchList, (void (*) (lsGeneric)) NULL);
401      }
402
403      /*
404       * Scan subsystems that aren't the currently considered subsytem.
405       */
406      {
407        Part_Subsystem_t *scanSubsystem;
408        arrayForEachItem(Part_Subsystem_t *, arrayOfPartition, j,
409                scanSubsystem) {
410          st_table      *otherVertexTable = scanSubsystem->vertexNameTable;
411
412          if (i != j) {
413            st_generator        *stGen;
414            Ntk_Node_t          *latchNode;
415
416            st_foreach_item(everyFanOuts, stGen, &latchNode, NULL) {
417              char *latchName = Ntk_NodeReadName(latchNode);
418              if (st_lookup(otherVertexTable, latchName, NIL(char *))) {
419                array_insert_last(int, fanOutArray, j);
420                break;
421              }
422            } /* end of  */
423          } /* end of if (i != j) */
424        } /* end of arrayForEachItem(Part_Subsystem_t *) */
425      }
426
427      st_free_table(everyFanOuts);
428
429      /* Update fanOutArray into the subsystem */
430      testSubsystem->subsystemFanOut = fanOutArray;
431    } /* end of arrayForEachItem(Part_Subsystem_t *) */
432
433    /* Free dependency hash table */
434    st_free_table(fanOutDependencies);
435  }
436
437  return(arrayOfPartition);
438}
439
440/**Function********************************************************************
441
442  Synopsis    [Create sub-systems based on latch relation]
443
444  Description [Create sub-systems based on latch dependency, connectivity,
445  correlation, and affinity. If arrayOfFunctionNames(latch data inputs) is
446  given, only those nodes are considered to make sub-systems. If arrayOfGroup-
447  Index(Ii) is given with arrayOfFunctionNames(Fi), Fi is put in Ii'th
448  sub-system.]
449
450  SideEffects []
451
452******************************************************************************/
453array_t *
454Part_PartCreateSubsystems(
455  Part_SubsystemInfo_t *subInfo,
456  array_t *arrayOfLatchNames,
457  array_t *arrayOfGroupIndex)
458{
459  if (subInfo->verbosity > 0) {
460    if (arrayOfLatchNames != NIL(array_t)) {
461      fprintf(vis_stdout, "Grouping: Array of latch data is given.\n");
462      fprintf(vis_stdout,
463        "Grouping: All latches related to the array will be grouped.\n");
464    } else if (Part_NetworkReadPartition(subInfo->network) == NIL(graph_t)) {
465      fprintf(vis_stdout, "Grouping: Network has no partition.\n");
466      fprintf(vis_stdout,
467        "Grouping: All latches in network will be grouped.\n");
468    } else {
469      fprintf(vis_stdout, "Grouping: Network has a partition.\n");
470      fprintf(vis_stdout,
471        "Grouping: All latches in partition will be grouped.\n");
472    }
473  }
474  return(PartCreateSubsystem(subInfo, arrayOfLatchNames, arrayOfGroupIndex));
475}
476
477/**Function********************************************************************
478
479  Synopsis    [Create sub-partitions based on latch relation]
480
481  Description [Create sub-partition based on latch dependency, connectivity,
482  correlation, and affinity. The first sub-system includes latches in CTL
483  formula, and latches with strong affinity are put in next sub-system. If
484  dynamicIncrease is TRUE, the first sub-system which has stringest realtion
485  with given formula and the second sub-system with all other latches are
486  returned.]
487
488  SideEffects []
489
490******************************************************************************/
491array_t *
492Part_PartCreateSubsystemsWithCTL(
493  Part_SubsystemInfo_t *subInfo,
494  array_t *ctlArray,
495  array_t *fairArray,
496  boolean dynamicIncrease,
497  boolean dynamicAndDependency)
498{
499  if (subInfo->verbosity > 0 ){
500    fprintf(vis_stdout,"Grouping: All latches related to ");
501    fprintf(vis_stdout,"the CTL will be grouped.\n");
502  }
503  return (PartCreateSubsystemWithCTL(subInfo, ctlArray, fairArray,
504                             dynamicIncrease,dynamicAndDependency));
505}
506
507/**Function********************************************************************
508
509  Synopsis    [Create sub-partitions based on latch relation]
510
511  Description [Create sub-partition based on latch dependency, connectivity,
512  correlation, and affinity. The first sub-system includes latches in CTL
513  formula, and latches with strong affinity are put in next sub-system. If
514  dynamicIncrease is TRUE, the first sub-system which has stringest realtion
515  with given formula and the second sub-system with all other latches are
516  returned.]
517
518  SideEffects []
519
520******************************************************************************/
521array_t *
522Part_PartCreateSubsystemsWithCtlAndLtl(
523  Part_SubsystemInfo_t *subInfo,
524  array_t *ctlArray,
525  array_t *ltlArray,
526  array_t *fairArray,
527  boolean dynamicIncrease,
528  boolean dynamicAndDependency,
529  boolean strictBound)
530{
531  if (subInfo->verbosity > 0 ){
532    fprintf(vis_stdout,"Grouping: All latches related to ");
533    fprintf(vis_stdout,"the CTL/LTL/fairness will be grouped.\n");
534  }
535  return (PartCreateSubsystemWithCtlAndLtl(subInfo, ctlArray, ltlArray,
536                                           fairArray,
537                                           dynamicIncrease,
538                                           dynamicAndDependency,
539                                           strictBound));
540}
541
542
543/**Function********************************************************************
544
545  Synopsis    [Read the table attached to a partitioned subsystem.]
546
547  SideEffects []
548
549******************************************************************************/
550st_table *
551Part_PartitionSubsystemReadVertexTable(
552  Part_Subsystem_t *partitionedSubsystem)
553{
554  return(partitionedSubsystem->vertexNameTable);
555}
556
557/**Function********************************************************************
558
559  Synopsis    [Read fan-in array attached to partitioned subsystem]
560
561  SideEffects []
562
563******************************************************************************/
564array_t *
565Part_PartitionSubsystemReadFanIn(
566  Part_Subsystem_t *partitionedSubsystem)
567{
568  return(partitionedSubsystem->subsystemFanIn);
569}
570
571/**Function********************************************************************
572
573  Synopsis    [Read fan-out array attached to partitioned subsystem]
574
575  SideEffects []
576
577******************************************************************************/
578array_t *
579Part_PartitionSubsystemReadFanOut(
580  Part_Subsystem_t *partitionedSubsystem)
581{
582  return(partitionedSubsystem->subsystemFanOut);
583}
584
585
586/**Function********************************************************************
587
588  Synopsis    [Initialize info structure for partitioning subsystem]
589
590  SideEffects []
591
592  SeeAlso     [Part_SubsystemInfo]
593
594******************************************************************************/
595Part_SubsystemInfo_t *
596Part_PartitionSubsystemInfoInit(
597  Ntk_Network_t *network)
598{
599  Part_SubsystemInfo_t *partSubInfo;
600
601  partSubInfo = ALLOC(Part_SubsystemInfo_t, 1);
602
603 /*
604  * set values as defaults
605  */
606  partSubInfo->network = network;
607  partSubInfo->arrayOfVertex = NIL(array_t);
608  partSubInfo->numberOfVertex = 0;
609  partSubInfo->partBM = Part_BFix_v;
610  partSubInfo->con_factor = PART_SUB_CON_FACTOR;
611  partSubInfo->cor_factor = PART_SUB_COR_FACTOR;
612  partSubInfo->aff_factor = PART_SUB_AFF_FACTOR;
613  partSubInfo->threshold = 0.0;
614  partSubInfo->bound = 8;
615  partSubInfo->verbosity = 0;
616  partSubInfo->corMethod = Part_CorrelationDefault;
617  partSubInfo->dupLatchTable = st_init_table(strcmp, st_strhash);
618  partSubInfo->latchNameTable = st_init_table(strcmp, st_strhash);
619  return(partSubInfo);
620}
621
622/**Function********************************************************************
623
624  Synopsis    [Free info structure for partitioning subsystem]
625
626  SideEffects []
627
628  SeeAlso     [Part_SubsystemInfo]
629
630******************************************************************************/
631void
632Part_PartitionSubsystemInfoFree(
633  Part_SubsystemInfo_t *partSubInfo)
634{
635  st_generator  *stGen;
636  char          *latchInputName;
637  array_t       *latchNames;
638
639  array_free(partSubInfo->arrayOfVertex);
640  st_foreach_item(partSubInfo->dupLatchTable, stGen, &latchInputName,
641        &latchNames) {
642    array_free(latchNames);
643  }
644  st_free_table(partSubInfo->dupLatchTable);
645  st_free_table(partSubInfo->latchNameTable);
646  FREE(partSubInfo);
647}
648
649
650/**Function********************************************************************
651
652  Synopsis    [Free subsystem structure for partitioning subsystem]
653
654  SideEffects []
655
656  SeeAlso     [Part_Subsystem]
657
658******************************************************************************/
659void
660Part_PartitionSubsystemFree(
661  Part_Subsystem_t *partSubsystem)
662{
663  st_free_table(partSubsystem->vertexNameTable);
664  array_free(partSubsystem->subsystemFanIn);
665  array_free(partSubsystem->subsystemFanOut);
666  FREE(partSubsystem);
667}
668
669/**Function********************************************************************
670
671  Synopsis    [Set breaking method of subsystem info]
672
673  SideEffects []
674
675  SeeAlso     [Part_SubsystemInfo]
676
677******************************************************************************/
678void
679Part_PartitionSubsystemInfoSetBreakingMethod(
680  Part_SubsystemInfo_t *subInfo,
681  Part_BMethod bMethod)
682{
683  subInfo->partBM = bMethod;
684}
685
686
687/**Function********************************************************************
688
689  Synopsis    [Set bound of subsystem info]
690
691  SideEffects []
692
693  SeeAlso     [Part_SubsystemInfo]
694
695******************************************************************************/
696void
697Part_PartitionSubsystemInfoSetBound(
698  Part_SubsystemInfo_t *subInfo,
699  int bound)
700{
701  subInfo->bound = bound;
702}
703
704/**Function********************************************************************
705
706  Synopsis    [Set threshold of subsystem info]
707
708  SideEffects []
709
710  SeeAlso     [Part_SubsystemInfo]
711
712******************************************************************************/
713void
714Part_PartitionSubsystemInfoSetThreshold(
715  Part_SubsystemInfo_t *subInfo,
716  float threshold)
717{
718  subInfo->threshold = threshold;
719}
720
721
722/**Function********************************************************************
723
724  Synopsis    [Set verbosity of subsystem info]
725
726  SideEffects []
727
728  SeeAlso     [Part_SubsystemInfo]
729
730******************************************************************************/
731void
732Part_PartitionSubsystemInfoSetVerbosity(
733  Part_SubsystemInfo_t *subInfo,
734  int verbosity)
735{
736  subInfo->verbosity = verbosity;
737}
738
739
740/**Function********************************************************************
741
742  Synopsis    [Set method for correlation]
743
744  SideEffects []
745
746  SeeAlso     [Part_SubsystemInfo]
747
748******************************************************************************/
749void
750Part_PartitionSubsystemInfoSetCorrelationMethod(
751  Part_SubsystemInfo_t *subInfo,
752  Part_CMethod corMethod)
753{
754  subInfo->corMethod = corMethod;
755}
756
757/**Function********************************************************************
758
759  Synopsis    [Set affinity factor]
760
761  SideEffects []
762
763  SeeAlso     [Part_SubsystemInfo]
764
765******************************************************************************/
766void
767Part_PartitionSubsystemInfoSetAffinityFactor(
768  Part_SubsystemInfo_t *subInfo,
769  float affinity)
770{
771  subInfo->aff_factor = affinity;
772}
773
774
775/**Function********************************************************************
776
777  Synopsis    [Create a sub-system with given latch data input in arrayOfNodes]
778
779  SideEffects []
780
781  SeeAlso     []
782
783******************************************************************************/
784Part_Subsystem_t*
785Part_PartCreateSingleSubSystem(
786  array_t *arrayOfNodes,
787  Ntk_Network_t *network)
788{
789  return PartCreateSingleSubSystem(arrayOfNodes, network);
790}
791
792
793/*---------------------------------------------------------------------------*/
794/* Definition of internal functions                                          */
795/*---------------------------------------------------------------------------*/
796
797
798/**Function********************************************************************
799
800  Synopsis    [Create an array of partitioned subsystems from array of latches]
801
802  Description [This is a main function to get subsystems. At first, look at
803  the circuit topology and next state functions, get the latch affinity.
804  Find the connected components to cluster latches which are stronly dependent
805  or correlated on each other.
806  After that, divide clusters bigger than the given bound and aggregate
807  smaller clusters. This function is called with network and partition graph.
808  If arrayOfFunctionNames are not NULL, this function generates sub-system with
809  those latch-data-inputs in that array. If arrayOfGroupIndex is not NILL and
810  size of this array is same as the size of arrayOfFunctionNames, this function
811  uses these two arrays as predefined grouping information and creates
812  sub-systems.]
813
814  SideEffects []
815
816  SeeAlso     [Part_SubsystemInfo]
817
818******************************************************************************/
819array_t *
820PartCreateSubsystem(
821  Part_SubsystemInfo_t *partSubInfo,
822  array_t *arrayOfLatchNames,
823  array_t *arrayOfGroupIndex)
824{
825  char          *arrayOfDependency = NIL(char);
826  float         *arrayOfCorrelation = NIL(float);
827  float         *arrayOfAffinity;
828  array_t       *arrayOfInit;
829  st_table      *indexToPtrInfo; /* index to pointer table */
830  st_table      *ptrToIndexInfo; /* pointer to index table */
831  array_t       *result;
832  Ntk_Node_t    *node;
833  char          *functionName;
834  char          *latchName;
835  lsList        vertexList;
836  lsGen         gen;
837  int           i;
838  vertex_t      *vertex;
839  array_t       *initArray;
840  array_t       *arrayOfVertex;
841  Ntk_Network_t *network = partSubInfo->network;
842  graph_t       *partition = Part_NetworkReadPartition(network);
843  long          initialTime = 0;
844  long          finalTime;
845
846  if (partition == NIL(graph_t)) {
847    if (partSubInfo->corMethod == Part_CorrelationWithBDD) {
848       error_append("Network has no partition. Correlation ");
849       error_append("with MDD operation can not be used.\n");
850       return NIL(array_t);
851    }
852  }
853  if (arrayOfGroupIndex != NIL(array_t)) {
854    if (!arrayOfLatchNames) {
855      error_append("Latch name array is not given.\n");
856      result = NIL(array_t);
857    }
858    if (array_n(arrayOfLatchNames) != array_n(arrayOfGroupIndex)) {
859      error_append("Given function names and index have different size.\n");
860      result = NIL(array_t);
861    }
862  }
863
864  if (arrayOfLatchNames && arrayOfGroupIndex) {
865    result = PartCreateSubSystemWithGroupIndex(partSubInfo,
866                arrayOfLatchNames, arrayOfGroupIndex);
867    return result;
868  }
869
870  arrayOfVertex = array_alloc(Ntk_Node_t *, 0);
871
872  /*
873   * Convert graph vertices into array of array of vertices.
874   */
875  if (partSubInfo->verbosity > 2) {
876    fprintf(vis_stdout, "\nGroupting: List of latches\n");
877    fprintf(vis_stdout, "----------------------------\n");
878  }
879  if (arrayOfLatchNames != NIL(array_t)) {
880    Ntk_Node_t  *latchNode, *latchInputNode;
881    char        *otherLatchName;
882    array_t     *latchNameArray;
883
884    arrayForEachItem(char *, arrayOfLatchNames, i, latchName) {
885      latchNode = Ntk_NetworkFindNodeByName(network, latchName);
886      latchInputNode = Ntk_LatchReadDataInput(latchNode);
887      functionName = Ntk_NodeReadName(latchInputNode);
888      if (partSubInfo->verbosity > 2)
889        fprintf(vis_stdout, "%s\n", latchName);
890      if (st_lookup(partSubInfo->latchNameTable, functionName,
891                &otherLatchName)) {
892        if (st_lookup(partSubInfo->dupLatchTable, functionName,
893            &latchNameArray)) {
894          array_insert_last(char *, latchNameArray, latchName);
895        } else {
896          latchNameArray = array_alloc(char *, 0);
897          array_insert_last(char *, latchNameArray, otherLatchName);
898          array_insert_last(char *, latchNameArray, latchName);
899          st_insert(partSubInfo->dupLatchTable, (char *)functionName,
900                (char *)latchNameArray);
901        }
902        continue;
903      }
904      st_insert(partSubInfo->latchNameTable, (char *)functionName,
905        (char *)latchName);
906      array_insert_last(Ntk_Node_t *, arrayOfVertex, latchInputNode);
907    }
908  } else if (partition == NIL(graph_t)) {
909    Ntk_NetworkForEachNode(network, gen, node) {
910      if (Ntk_NodeTestIsLatchDataInput(node)) {
911        array_insert_last(Ntk_Node_t *, arrayOfVertex, node);
912        arrayOfLatchNames = PartReadLatchNameFromLatchInput(network, node);
913        functionName = Ntk_NodeReadName(node);
914        latchName = array_fetch(char *, arrayOfLatchNames, 0);
915        st_insert(partSubInfo->latchNameTable, (char *)functionName,
916                (char *)latchName);
917        if (array_n(arrayOfLatchNames) > 1) {
918          st_insert(partSubInfo->dupLatchTable, (char *)functionName,
919                (char *)arrayOfLatchNames);
920          if (partSubInfo->verbosity > 2) {
921            char *nname;
922            arrayForEachItem(char *, arrayOfLatchNames, i, nname) {
923              fprintf(vis_stdout, "%s\n", nname);
924            }
925          }
926        } else {
927          array_free(arrayOfLatchNames);
928          if (partSubInfo->verbosity > 2)
929            fprintf(vis_stdout, "%s\n", latchName);
930        }
931      }
932    } /* End of Ntk_NetworkForEachNode */
933  } else {
934    vertexList = g_get_vertices(partition);
935    lsForEachItem(vertexList, gen, vertex) {
936      char *nodeName = PartVertexReadName(vertex);
937      node = Ntk_NetworkFindNodeByName(network, nodeName);
938      if (Ntk_NodeTestIsLatchDataInput(node)) {
939        array_insert_last(Ntk_Node_t *, arrayOfVertex, node);
940        arrayOfLatchNames = PartReadLatchNameFromLatchInput(network, node);
941        functionName = Ntk_NodeReadName(node);
942        latchName = array_fetch(char *, arrayOfLatchNames, 0);
943        st_insert(partSubInfo->latchNameTable, (char *)functionName,
944                (char *)latchName);
945        if (array_n(arrayOfLatchNames) > 1) {
946          st_insert(partSubInfo->dupLatchTable, (char *)functionName,
947                (char *)arrayOfLatchNames);
948          if (partSubInfo->verbosity > 2) {
949            char *nname;
950            arrayForEachItem(char *, arrayOfLatchNames, i, nname) {
951              fprintf(vis_stdout, "%s\n", nname);
952            }
953          }
954        } else {
955          array_free(arrayOfLatchNames);
956          if (partSubInfo->verbosity > 2)
957            fprintf(vis_stdout, "%s\n", latchName);
958        }
959      }
960    }
961  }
962
963  if (partSubInfo->verbosity > 2) {
964    fprintf(vis_stdout, "Total # of latch data input = %d\n",
965      array_n(arrayOfVertex));
966  }
967  partSubInfo->arrayOfVertex = arrayOfVertex;
968  partSubInfo->numberOfVertex = array_n(arrayOfVertex);
969
970 /*
971  * table from index to pointer and pointer to index
972  */
973  indexToPtrInfo = st_init_table(st_numcmp, st_numhash);
974  ptrToIndexInfo = st_init_table(st_ptrcmp, st_ptrhash);
975
976  arrayForEachItem(Ntk_Node_t *, partSubInfo->arrayOfVertex, i, node) {
977    st_insert(indexToPtrInfo, (char *)(long)i, (char *)node);
978    st_insert(ptrToIndexInfo, (char *)node, (char *)(long)i);
979  }
980
981 /*
982  * get a dependency matrix
983  */
984  if (partSubInfo->aff_factor > 0.0) {
985    if (partSubInfo->verbosity > 0)
986      initialTime = util_cpu_time();
987    arrayOfDependency = PartCreateDependencyMatrix(partSubInfo, ptrToIndexInfo);
988    if (partSubInfo->verbosity > 0) {
989      finalTime = util_cpu_time();
990      fprintf(vis_stdout, "time for computing dependency = %g\n",
991        (double)(finalTime - initialTime) / 1000.0);
992    }
993  }
994
995 /*
996  * get a correlation matrix
997  */
998  if (partSubInfo->aff_factor != 1.0) {
999    if (partSubInfo->verbosity > 0)
1000      initialTime = util_cpu_time();
1001    if (partSubInfo->corMethod == Part_CorrelationWithBDD)
1002      arrayOfCorrelation = PartCreateCorrelationMatrixFromBDD(partSubInfo);
1003    else if ((partSubInfo->corMethod == Part_CorrelationWithSupport) ||
1004             (partSubInfo->corMethod == Part_CorrelationDefault)) {
1005      arrayOfCorrelation = PartCreateCorrelationMatrixFromSupport(partSubInfo);
1006    }
1007    if (partSubInfo->verbosity > 0) {
1008      finalTime = util_cpu_time();
1009      fprintf(vis_stdout, "time for computing correlation = %g\n",
1010        (double)(finalTime - initialTime) / 1000.0);
1011    }
1012  }
1013
1014  if (partSubInfo->verbosity > 2) {
1015    if (arrayOfDependency) {
1016      fprintf(vis_stdout, "\nGrouping: Dependency\n");
1017      fprintf(vis_stdout, "--------------------\n");
1018      PartPrintArrayArray(arrayOfDependency, partSubInfo->numberOfVertex, 1);
1019    }
1020    if (arrayOfCorrelation) {
1021      fprintf(vis_stdout, "\nGrouping: Correlation\n");
1022      fprintf(vis_stdout, "---------------------\n");
1023      PartPrintArrayArray(arrayOfCorrelation, partSubInfo->numberOfVertex, 0);
1024    }
1025 }
1026
1027 /*
1028  * get an affinity matrix, arrayOfCorrelation is freed.
1029  */
1030  if (partSubInfo->verbosity > 0)
1031    initialTime = util_cpu_time();
1032  arrayOfAffinity = PartCreateAffinityMatrix(arrayOfDependency,
1033                        arrayOfCorrelation, partSubInfo);
1034  FREE(arrayOfCorrelation);
1035  if (partSubInfo->verbosity > 0) {
1036    finalTime = util_cpu_time();
1037    fprintf(vis_stdout, "time for computing affinity = %g\n",
1038      (double)(finalTime - initialTime) / 1000.0);
1039  }
1040
1041  if (partSubInfo->verbosity > 2) {
1042    fprintf(vis_stdout, "\nGrouping: Affinity\n");
1043    fprintf(vis_stdout, "------------------\n");
1044    PartPrintArrayArray(arrayOfAffinity, partSubInfo->numberOfVertex, 0);
1045  }
1046
1047 /*
1048  * get an initial subsysytm by searching for connected component in
1049  * vertex affinity matrix
1050  */
1051  if (partSubInfo->verbosity > 0)
1052    initialTime = util_cpu_time();
1053  arrayOfInit = PartGetConnectedComponent(arrayOfAffinity, partSubInfo,
1054                        indexToPtrInfo);
1055  if (partSubInfo->verbosity > 0) {
1056    finalTime = util_cpu_time();
1057    fprintf(vis_stdout, "time for computing connected component = %g\n",
1058      (double)(finalTime - initialTime) / 1000.0);
1059  }
1060
1061  if (partSubInfo->verbosity > 2) {
1062    fprintf(vis_stdout, "\nGrouping: Initial connected component size\n");
1063    fprintf(vis_stdout, "------------------------------------------\n\n");
1064    arrayForEachItem(array_t *, arrayOfInit, i, initArray) {
1065      fprintf(vis_stdout, "%3d group: size = %d\n", i, array_n(initArray));
1066    }
1067  }
1068
1069 /*
1070  * get a final subsystem by breaking big connected components and
1071  * aggregating small connected components.
1072  */
1073  if (partSubInfo->verbosity > 0)
1074    initialTime = util_cpu_time();
1075  result = PartBreakingAggregating(arrayOfInit, arrayOfAffinity, partSubInfo,
1076           ptrToIndexInfo, arrayOfDependency);
1077  if (partSubInfo->verbosity > 0) {
1078    finalTime = util_cpu_time();
1079    fprintf(vis_stdout, "time for breaking and aggregating = %g\n",
1080      (double)(finalTime - initialTime) / 1000.0);
1081  }
1082
1083  array_free(arrayOfInit);
1084
1085  if (partSubInfo->verbosity >= 2) {
1086    Part_Subsystem_t *sub;
1087    char *latchName;
1088    st_generator *stGen;
1089
1090    fprintf(vis_stdout, "\nGrouping: List of subsytem latches\n");
1091    fprintf(vis_stdout, "----------------------------------\n\n");
1092    arrayForEachItem(Part_Subsystem_t *, result, i, sub) {
1093      fprintf(vis_stdout, "[Subsystem %3d]\n", i);
1094      st_foreach_item(sub->vertexNameTable, stGen, &latchName, NIL(char *)) {
1095        fprintf(vis_stdout, "%s\n", latchName);
1096      }
1097      fprintf(vis_stdout, "\n");
1098    }
1099  }
1100
1101  if (partSubInfo->verbosity >= 1) {
1102    (void)fprintf(vis_stdout, "\nGrouping: grouping options\n");
1103    (void)fprintf(vis_stdout, "--------------------------\n\n");
1104    (void)fprintf(vis_stdout, "Threshold          : %f\n",
1105                partSubInfo->threshold);
1106    (void)fprintf(vis_stdout, "bound              : %d\n",
1107                partSubInfo->bound);
1108    (void)fprintf(vis_stdout, "connectivity factor: %f\n",
1109                partSubInfo->con_factor);
1110    (void)fprintf(vis_stdout, "correlation factor : %f\n",
1111                partSubInfo->cor_factor);
1112    (void)fprintf(vis_stdout, "affinity factor    : %f\n",
1113                partSubInfo->aff_factor);
1114    (void)fprintf(vis_stdout, "\n");
1115  }
1116
1117  st_free_table(indexToPtrInfo);
1118  st_free_table(ptrToIndexInfo);
1119  FREE(arrayOfDependency);
1120  FREE(arrayOfAffinity);
1121
1122  return result;
1123}
1124
1125/*---------------------------------------------------------------------------*/
1126/* Definition of static functions                                            */
1127/*---------------------------------------------------------------------------*/
1128
1129/**Function********************************************************************
1130
1131  Synopsis    [Create an array of subsystems from properties]
1132
1133  Description [The first couple of sub-systems include nodes which are in
1134  CTL formulae.  A node with biggest affinity is included in the next
1135  sub-system until the number of nodes is less than bound. If dynamicIncrease
1136  is FALSE, get all sub-systems with all support variables of CTL formula.
1137  If TRUE, the first sub-system includes variables in CTL and the second
1138  sub-system includes others.]
1139
1140  SideEffects []
1141
1142  SeeAlso     [Part_SubsystemInfo]
1143
1144******************************************************************************/
1145static
1146array_t *
1147PartCreateSubsystemWithCTL( 
1148  Part_SubsystemInfo_t *partSubInfo,
1149  array_t *ctlArray,
1150  array_t *fairArray,
1151  boolean dynamicIncrease,
1152  boolean dynamicAndDependency)
1153{
1154  return PartCreateSubsystemWithCtlAndLtl(partSubInfo, ctlArray, NIL(array_t),
1155                                          fairArray, dynamicIncrease,
1156                                          dynamicAndDependency, FALSE);
1157}
1158
1159/**Function********************************************************************
1160
1161  Synopsis    [Create an array of subsystems from properties]
1162
1163  Description [The first couple of sub-systems include nodes which are
1164  in CTL/LTL/fairness formulae.  A node with biggest affinity is
1165  included in the next sub-system until the number of nodes is less
1166  than bound. If dynamicIncrease is FALSE, get all sub-systems with
1167  all support variables of CTL formula.  If TRUE, the first sub-system
1168  includes variables in CTL and the second sub-system includes others.
1169
1170  When strictBound is FALSE, all the latches appearing in the formulae
1171  are put into the first subsystem -- making it possibly larger than
1172  the bound. Otherwise, no subsystem will have more than 'bound'
1173  latches.]
1174
1175  SideEffects []
1176
1177  SeeAlso     [Part_SubsystemInfo]
1178
1179******************************************************************************/
1180static
1181array_t *
1182PartCreateSubsystemWithCtlAndLtl(
1183  Part_SubsystemInfo_t *partSubInfo,
1184  array_t *ctlArray,
1185  array_t *ltlArray,
1186  array_t *fairArray,
1187  boolean dynamicIncrease,
1188  boolean dynamicAndDependency,
1189  boolean strictBound)
1190{
1191  int i, j, index, maxSize, maxIndex, leftNodes, numSeed;
1192  array_t *result = NIL(array_t);
1193  Ntk_Network_t *network = partSubInfo->network;
1194  lsList latchNodeList;
1195  lsGen  gen;
1196  char *arrayOfDependency = NIL(char);
1197  float *arrayOfCorrelation = NIL(float);
1198  float *arrayOfAffinity = NIL(float);
1199  array_t *arrayTemp = NIL(array_t);
1200  array_t *arrayOfVertex = NIL(array_t);
1201  array_t *arrayOfLatchNames = NIL(array_t);
1202  st_table *vertexToArrayOfLatchNames = NIL(st_table);
1203  array_t *arrayOfLatchNodeName = NIL(array_t);
1204  Ntk_Node_t *node = NIL(Ntk_Node_t);
1205  float affinity;
1206  char *name = NIL(char);
1207  st_table *indexToPtrInfo = NIL(st_table);
1208  st_table *ptrToIndexInfo = NIL(st_table);
1209  array_t *check = NIL(array_t);
1210  array_t *tempCheck = NIL(array_t);
1211  array_t *tempCC = NIL(array_t);
1212  st_generator *stGen = NIL(st_generator);
1213  array_t *arrayOfSeed = NIL(array_t);
1214  Ntk_Node_t *seedLast = NIL(Ntk_Node_t);
1215  Ntk_Node_t *seedNext = NIL(Ntk_Node_t);
1216  array_t *arrayOfBreak = NIL(array_t);
1217  array_t *arrayOfNodes = NIL(array_t);
1218  array_t *arrayOfIndex = NIL(array_t);
1219  st_table *dataInputNodes = NIL(st_table);
1220  Part_Subsystem_t *sub = NIL(Part_Subsystem_t);
1221  int numIncluded;
1222  float prevAffinity;
1223
1224  if (ctlArray == NIL(array_t) && ltlArray == NIL(array_t)){
1225    return NIL(array_t);
1226  }
1227
1228  /*
1229   * arrayOfLatchNodeName  <--  COI latch names
1230   */
1231  latchNodeList = lsCreate();
1232  PartGetLatchListFromCtlAndLtl(network, ctlArray, ltlArray,
1233                                fairArray, latchNodeList, FALSE);
1234  arrayOfLatchNodeName = array_alloc(Ntk_Node_t *, 0);
1235  lsForEachItem(latchNodeList, gen, node){
1236    array_insert_last(char *, arrayOfLatchNodeName, Ntk_NodeReadName(node));
1237  }
1238  lsDestroy(latchNodeList, (void (*)(lsGeneric))0);
1239
1240  /*
1241   * arrayOfVertex  <--  COI latch datainput nodes
1242   */
1243  array_sort(arrayOfLatchNodeName, strCompare);
1244  arrayOfVertex = array_alloc(Ntk_Node_t *, 0);
1245  vertexToArrayOfLatchNames = st_init_table(st_ptrcmp, st_ptrhash);
1246  /* multiple latch may correspond to the same  dataInput */ 
1247  arrayForEachItem(char *, arrayOfLatchNodeName, i, name){
1248    node = Ntk_NetworkFindNodeByName(network, name);
1249    node = Ntk_LatchReadDataInput(node);
1250    if (!st_lookup(vertexToArrayOfLatchNames, node, &arrayOfLatchNames) ) {
1251      arrayOfLatchNames = array_alloc(char *, 0);
1252      array_insert_last(char *, arrayOfLatchNames, name);
1253      st_insert(vertexToArrayOfLatchNames, node, arrayOfLatchNames);
1254     
1255      array_insert_last(Ntk_Node_t *, arrayOfVertex, node);
1256    }else 
1257      array_insert_last(char *, arrayOfLatchNames, name);
1258  }
1259
1260  /*
1261   * Print a list of latch names.
1262   */
1263  if (partSubInfo->verbosity >= 2){
1264    fprintf(vis_stdout,"\nGroupting: List of latches\n");
1265    fprintf(vis_stdout,"------------------------\n\n");
1266    arrayForEachItem(char *, arrayOfLatchNodeName, i, name){
1267      fprintf(vis_stdout,"%s\n", name);
1268    }
1269  }
1270  array_free(arrayOfLatchNodeName);
1271
1272
1273  /*
1274   * dataInputNodes <-- formulae latch datainput nodes
1275   */
1276  latchNodeList = lsCreate();
1277  PartGetLatchListFromCtlAndLtl(network, ctlArray, ltlArray,
1278                                fairArray, latchNodeList, TRUE);
1279  dataInputNodes = st_init_table( st_ptrcmp, st_ptrhash );
1280  lsForEachItem(latchNodeList, gen, node) {
1281    Ntk_Node_t *dataInputNode = Ntk_LatchReadDataInput(node);
1282    if (!st_is_member(dataInputNodes, (char *)dataInputNode))
1283      st_insert(dataInputNodes, (char *)dataInputNode, NIL(char));
1284  }
1285  lsDestroy(latchNodeList, (void (*)(lsGeneric))0);
1286
1287
1288 /*
1289  * table from index to pointer and pointer to index
1290  */
1291  partSubInfo->arrayOfVertex = arrayOfVertex;
1292  partSubInfo->numberOfVertex = array_n(arrayOfVertex);
1293
1294  indexToPtrInfo = st_init_table(st_numcmp, st_numhash);
1295  ptrToIndexInfo = st_init_table(st_ptrcmp, st_ptrhash);
1296
1297  arrayForEachItem(Ntk_Node_t *, partSubInfo->arrayOfVertex, i, node){
1298    st_insert(indexToPtrInfo, (char *)(long)i, (char *)node);
1299    st_insert(ptrToIndexInfo, (char *)node, (char *)(long)i);
1300  }
1301
1302  check = array_alloc(int, partSubInfo->numberOfVertex);
1303  for(i=0;i<partSubInfo->numberOfVertex;i++){
1304    array_insert(int, check, i, 0);
1305  }
1306
1307
1308  leftNodes = partSubInfo->numberOfVertex;
1309  arrayOfIndex = array_alloc(int, st_count(dataInputNodes));
1310  result = array_alloc(Part_Subsystem_t *, 0);
1311
1312
1313  /*
1314   * If (1) number of formula nodes is smaller than bound, or (2)
1315   * strictBound is FALSE, or (3) dynamicIncrease is TRUE, create a
1316   * subsystem and put all formula nodes in the sub-system
1317   */
1318  if ( !strictBound || st_count(dataInputNodes) <= partSubInfo->bound
1319       || dynamicIncrease ) {
1320    int numNodesInFirstSubsys;
1321
1322    if (!strictBound || st_count(dataInputNodes) <= partSubInfo->bound)
1323      numNodesInFirstSubsys = st_count(dataInputNodes);
1324    else 
1325      numNodesInFirstSubsys = partSubInfo->bound;
1326
1327    arrayOfNodes = array_alloc(Ntk_Node_t *, st_count(dataInputNodes));
1328    i=0;
1329    st_foreach_item(dataInputNodes, stGen, &node, NULL) {
1330      if (i == numNodesInFirstSubsys) break;
1331      st_lookup_int(ptrToIndexInfo, node, &index);
1332      array_insert(int, check, index, 1);
1333      array_insert(int, arrayOfIndex, i, index);
1334      array_insert(Ntk_Node_t *, arrayOfNodes, i++, node);
1335    }
1336    sub = PartCreateSingleSubSystem(arrayOfNodes, network);
1337    leftNodes -= array_n(arrayOfNodes);
1338    array_insert_last(Part_Subsystem_t *, result, sub);
1339    array_free(arrayOfNodes);
1340
1341    if (dynamicIncrease) {
1342      /* the second subsystem <-- remaining latches in dataInputTable
1343       * the thrid  subsystem <-- other COI latches
1344       */
1345      if ( dynamicAndDependency ) {
1346        if ( st_count(dataInputNodes) == numNodesInFirstSubsys )
1347          array_insert_last(Part_Subsystem_t *, result, NIL(Part_Subsystem_t));
1348        else {
1349          arrayOfNodes = array_alloc(Ntk_Node_t *, 0);
1350          i=0;
1351          st_foreach_item(dataInputNodes, stGen, &node, NULL) {
1352            st_lookup_int(ptrToIndexInfo, node, &index);
1353            if (array_fetch(int, check, index)==0){
1354              array_insert(int, check, index, 1);
1355              array_insert(int, arrayOfIndex, i, index);
1356              array_insert_last(Ntk_Node_t *, arrayOfNodes, node);
1357            }
1358          }
1359          sub = PartCreateSingleSubSystem(arrayOfNodes, network);
1360          leftNodes -= array_n(arrayOfNodes);
1361          array_insert_last(Part_Subsystem_t *, result, sub);
1362          array_free(arrayOfNodes);
1363        }
1364      }
1365     
1366      if (leftNodes > 0){
1367        arrayOfNodes = array_alloc(Ntk_Node_t *, 0);
1368        arrayForEachItem(Ntk_Node_t *, partSubInfo->arrayOfVertex, i, node){
1369          if (array_fetch(int, check, i)==0)
1370            array_insert_last(Ntk_Node_t *, arrayOfNodes, node);
1371        }
1372        sub = PartCreateSingleSubSystem(arrayOfNodes, network);
1373        array_free(arrayOfNodes);
1374      }else{
1375        sub = NIL(Part_Subsystem_t);
1376      }
1377      array_insert_last(Part_Subsystem_t *, result, sub);
1378
1379      array_free(check);
1380      array_free(arrayOfIndex);
1381      st_free_table(ptrToIndexInfo);
1382      st_free_table(indexToPtrInfo);
1383      st_free_table(dataInputNodes);
1384      return result;
1385    } /*if dynamicIncrease*/
1386
1387  }else {
1388    /*
1389     * If we don't want to put all formula nodes in the 1st subsystem,
1390     * we need to break them into several pieces.
1391     */
1392  }
1393
1394  /*
1395   * get a affinity matrix (dependency matrix, correlation matrix)
1396   */
1397  arrayOfDependency = PartCreateDependencyMatrix(partSubInfo, 
1398                                                 ptrToIndexInfo);
1399
1400  if (partSubInfo->corMethod == Part_CorrelationWithBDD)
1401    arrayOfCorrelation = PartCreateCorrelationMatrixFromBDD(partSubInfo);
1402  else if ((partSubInfo->corMethod == Part_CorrelationWithSupport) ||
1403           (partSubInfo->corMethod == Part_CorrelationDefault))
1404    arrayOfCorrelation = PartCreateCorrelationMatrixFromSupport(partSubInfo);
1405
1406  arrayOfAffinity = PartCreateAffinityMatrix(arrayOfDependency,
1407                                             arrayOfCorrelation, 
1408                                             partSubInfo);
1409 
1410  if (partSubInfo->verbosity > 2 ){
1411    fprintf(vis_stdout,"\nGrouping: Dependency\n");
1412    fprintf(vis_stdout,"--------------------\n");
1413    PartPrintArrayArray(arrayOfDependency, partSubInfo->numberOfVertex, 1);
1414    fprintf(vis_stdout,"\nGrouping: Correlation\n");
1415    fprintf(vis_stdout,"---------------------\n");
1416    PartPrintArrayArray(arrayOfCorrelation, partSubInfo->numberOfVertex, 0);
1417    fprintf(vis_stdout,"\nGrouping: Affinity\n");
1418    fprintf(vis_stdout,"------------------\n");
1419    PartPrintArrayArray(arrayOfAffinity, partSubInfo->numberOfVertex, 0);
1420  }
1421  FREE(arrayOfDependency);
1422  FREE(arrayOfCorrelation);
1423
1424
1425  /* If number of formula nodes are bigger than bound, break down into
1426   * bounded sized subsystems.
1427   */
1428  if (st_count(dataInputNodes) > partSubInfo->bound && strictBound ){
1429    tempCheck = array_alloc(int, partSubInfo->numberOfVertex);
1430    tempCC = array_alloc(Ntk_Node_t *, partSubInfo->numberOfVertex);
1431    for(i=0; i<partSubInfo->numberOfVertex; i++){
1432      array_insert(int, tempCheck, i, 1);
1433      array_insert(Ntk_Node_t *, tempCC, i, (Ntk_Node_t *)0);
1434    }
1435    i = 0;
1436    st_foreach_item(dataInputNodes, stGen, &node, NULL) {
1437      st_lookup_int(ptrToIndexInfo, node, &index);
1438      array_insert(int, arrayOfIndex, i++, index);
1439      array_insert(int, check, index, 1);
1440      array_insert(int, tempCheck, index, 0);
1441      array_insert(Ntk_Node_t *, tempCC, index, node);
1442    }
1443
1444    numSeed = (int) ceil((double)st_count(dataInputNodes)/(double)(partSubInfo->bound));
1445    arrayOfSeed = array_alloc(Ntk_Node_t *, numSeed);
1446    seedLast = PartSelectNodeOfMinSupport(tempCC,
1447                                          tempCheck, partSubInfo);
1448    array_insert(Ntk_Node_t *, arrayOfSeed, 0, seedLast);
1449    for (i=1; i< numSeed; i++){
1450      seedNext = PartSelectFarNode(seedLast, tempCC, tempCheck,
1451                                   arrayOfAffinity, ptrToIndexInfo);
1452      array_insert(Ntk_Node_t *, arrayOfSeed, i, seedNext);
1453      seedLast = seedNext;
1454    }
1455
1456   /*
1457    * Break formula nodes, put into table and insert into final result
1458    */
1459    arrayOfBreak = PartBreakingBigConnectedComponent(tempCC, tempCheck,
1460          arrayOfSeed, arrayOfAffinity, partSubInfo, ptrToIndexInfo);
1461    array_free(tempCheck);
1462    array_free(tempCC);
1463    array_free(arrayOfSeed);
1464
1465    assert(array_n(arrayOfBreak) > 0);
1466    maxSize = -1;
1467    maxIndex = -1; /* don't care value to suppress warning */
1468    arrayForEachItem(array_t *, arrayOfBreak, i, arrayOfNodes){
1469      if (array_n(arrayOfNodes)>maxSize){
1470        maxIndex = i;
1471        maxSize = array_n(arrayOfNodes);
1472      }
1473    }
1474    arrayOfNodes = array_fetch(array_t *, arrayOfBreak, maxIndex);
1475    sub = PartCreateSingleSubSystem(arrayOfNodes, network);
1476    leftNodes -= array_n(arrayOfNodes);
1477    array_insert_last(Part_Subsystem_t *, result, sub);
1478    arrayForEachItem(array_t *, arrayOfBreak, i, arrayOfNodes){
1479      if (i != maxIndex){
1480        sub = PartCreateSingleSubSystem(arrayOfNodes, network);
1481        leftNodes -= array_n(arrayOfNodes);
1482        array_insert_last(Part_Subsystem_t *, result, sub);
1483      }
1484    }
1485    PartArrayOfArrayFree(arrayOfBreak);
1486  }/* if (st_count(dataInputNodes) > partSubInfo->bound && strictBound)*/
1487  st_free_table(dataInputNodes);
1488
1489
1490  /*
1491   * Create new affinity matrix. Now new affinity is defined from
1492   * sub-system(s) created above to left nodes.
1493   */
1494  arrayTemp = NIL(array_t);
1495
1496  if (leftNodes > 0){
1497    arrayTemp = array_alloc(float, partSubInfo->numberOfVertex);
1498    arrayForEachItem(int, arrayOfIndex, i, index){
1499      for(j=0;j<partSubInfo->numberOfVertex;j++){
1500        affinity = PartGetElementFromSymMatrix(arrayOfAffinity,index,j);
1501        if (i==0){
1502          array_insert(float, arrayTemp, j, affinity);
1503        } else {
1504           prevAffinity = array_fetch(float, arrayTemp, j);
1505           array_insert(float, arrayTemp, j, affinity + prevAffinity);
1506        }
1507      }
1508    }
1509 
1510    array_free(arrayOfIndex);
1511    FREE(arrayOfAffinity);
1512
1513    if (partSubInfo->verbosity > 2 ){
1514      fprintf(vis_stdout,"\nGrouping:: combinded affinity\n");
1515      fprintf(vis_stdout,"------------------\n");
1516      arrayForEachItem(float, arrayTemp, i, affinity){
1517        fprintf(vis_stdout, "%.10f ", affinity);
1518      }
1519      fprintf(vis_stdout, "\n");
1520    }
1521  }else{
1522    array_free(arrayOfIndex);
1523    FREE(arrayOfAffinity);
1524  }
1525     
1526  /*
1527   * Create sub-system by choosing a nodes with biggest new affinity
1528   */
1529  while( leftNodes > 0 ){
1530    numIncluded = 0;
1531    arrayOfVertex = array_alloc(Ntk_Node_t *, 0);
1532    while ((numIncluded < partSubInfo->bound) && (leftNodes > 0)){
1533     /*
1534      * The node with maximum affinity to formula nodes is included
1535      * in next sub-system until number of nodes reaches to bound
1536      */
1537      prevAffinity = -1.0;
1538      maxIndex = 0;
1539      arrayForEachItem( float, arrayTemp, i, affinity){
1540        if ( array_fetch(int, check, i) != 1 ){
1541          if (affinity >= prevAffinity){
1542            prevAffinity = affinity;
1543            maxIndex = i;
1544          }
1545        }
1546      }
1547      st_lookup(indexToPtrInfo, (char *)(long)maxIndex, &node);
1548      array_insert_last(Ntk_Node_t *, arrayOfVertex, node);
1549      array_insert(int, check, maxIndex, 1);
1550      numIncluded++;
1551      leftNodes--;
1552    }
1553    sub = PartCreateSingleSubSystem(arrayOfVertex, network);
1554    array_free(arrayOfVertex);
1555    array_insert_last(Part_Subsystem_t *, result, sub);
1556  }
1557
1558  array_free(check);
1559  if (arrayTemp != NIL(array_t))
1560    array_free(arrayTemp);
1561  st_free_table(ptrToIndexInfo);
1562  st_free_table(indexToPtrInfo);
1563
1564
1565  if (partSubInfo->verbosity >= 2){
1566    Part_Subsystem_t *sub;
1567    char *latchName;
1568    st_generator *stGen;
1569
1570    fprintf(vis_stdout,"\nGrouping: List of subsytem latches\n");
1571    fprintf(vis_stdout,"----------------------------------\n\n");
1572    arrayForEachItem(Part_Subsystem_t *, result, i, sub){
1573      fprintf(vis_stdout,"[Subsystem %3d]\n",i);
1574      st_foreach_item(sub->vertexNameTable, stGen, &latchName, NIL(char *) ){
1575        fprintf(vis_stdout,"%s\n",latchName);
1576      }
1577      fprintf(vis_stdout,"\n");
1578    }
1579  }
1580
1581  return result;
1582}
1583
1584
1585/**Function********************************************************************
1586
1587  Synopsis    [Create the vertex dependency matrix]
1588
1589  Description [vertex 1 depends on vertex 2, if the support of the function
1590  attatched to vertex 1 contains vertex 2]
1591
1592  SideEffects []
1593
1594******************************************************************************/
1595static char *
1596PartCreateDependencyMatrix(
1597  Part_SubsystemInfo_t *partSubInfo,
1598  st_table *ptrToIndex)
1599{
1600  char          *result;
1601  array_t       *arrayNodeFrom;
1602  int           i, j, k;
1603  Ntk_Node_t    *node, *latchInputNode;
1604  array_t       *arrayOfSupport;
1605  Ntk_Network_t *network = partSubInfo->network;
1606  int           index, size;
1607
1608  size = partSubInfo->numberOfVertex;
1609  result = ALLOC(char, size * size);
1610  (void)memset((void *)result, 0, sizeof(char) * size * size);
1611
1612  for (i = 0; i < partSubInfo->numberOfVertex; i++) {
1613    node = array_fetch(Ntk_Node_t *, partSubInfo->arrayOfVertex, i);
1614    arrayNodeFrom = array_alloc(Ntk_Node_t *, 1);
1615    array_insert(Ntk_Node_t *, arrayNodeFrom, 0, node);
1616    arrayOfSupport = Ntk_NodeComputeCombinationalSupport(network,
1617                                                         arrayNodeFrom, 
1618                                                         FALSE);
1619    array_free(arrayNodeFrom);
1620    arrayForEachItem(Ntk_Node_t *, arrayOfSupport, j, node) {
1621      if (!Ntk_NodeTestIsLatch(node))
1622        continue;
1623      latchInputNode = Ntk_LatchReadDataInput(node);
1624      if (st_lookup_int(ptrToIndex, (char *)latchInputNode, &k)) {
1625        index = i * partSubInfo->numberOfVertex + k;
1626        result[index] = 1;
1627      } else {
1628        fprintf(vis_stderr,
1629                "** part error: can't find the latch input index.\n");
1630      }
1631    }
1632    array_free(arrayOfSupport);
1633  }
1634  return result;
1635}
1636
1637
1638/**Function********************************************************************
1639
1640  Synopsis    [Create the latch Correlation Matrix]
1641
1642  SideEffects []
1643
1644  SeeAlso     [Part_SubsystemInfo]
1645******************************************************************************/
1646static float *
1647PartCreateCorrelationMatrixFromSupport(
1648  Part_SubsystemInfo_t *partSubInfo)
1649{
1650  int i, j;
1651  float *result;
1652  float correlation;
1653  array_t *arrayOfSupport;
1654  st_table *tableOfSupport;
1655  array_t *arrayOfSupportTable;
1656  array_t *arrayNodeFrom;
1657  Ntk_Node_t *nodeFrom, *node;
1658  Ntk_Network_t *network = partSubInfo->network;
1659  int index;
1660
1661  result = ALLOC(float,
1662         partSubInfo->numberOfVertex * (partSubInfo->numberOfVertex - 1) / 2);
1663
1664  arrayOfSupportTable = array_alloc(st_table *, partSubInfo->numberOfVertex);
1665
1666  for (i = 0; i < partSubInfo->numberOfVertex; i++) {
1667    nodeFrom = array_fetch(Ntk_Node_t *, partSubInfo->arrayOfVertex, i);
1668    arrayNodeFrom = array_alloc(Ntk_Node_t *, 1);
1669    array_insert(Ntk_Node_t *, arrayNodeFrom, 0, nodeFrom);
1670    arrayOfSupport = Ntk_NodeComputeCombinationalSupport(network,
1671                                                         arrayNodeFrom, 
1672                                                         FALSE);
1673    array_free(arrayNodeFrom);
1674    tableOfSupport = st_init_table(st_ptrcmp, st_ptrhash);
1675    arrayForEachItem(Ntk_Node_t *, arrayOfSupport, j, node) {
1676      st_insert(tableOfSupport, (char *)node, (char *)NULL);
1677    }
1678    array_free(arrayOfSupport);
1679    array_insert(st_table *, arrayOfSupportTable, i, tableOfSupport);
1680  }
1681
1682  for (i = 1; i < partSubInfo->numberOfVertex; i++) {
1683    for (j = 0; j < i; j++) {
1684      correlation = PartVertexComputeCorrelation(i, j, arrayOfSupportTable,
1685                        partSubInfo);
1686      index = i * (i - 1) / 2 + j;
1687      result[index] = correlation;
1688    }
1689  }/* end of for */
1690
1691  for (i = 0; i < partSubInfo->numberOfVertex; i++)
1692    st_free_table(array_fetch(st_table *, arrayOfSupportTable, i));
1693  array_free(arrayOfSupportTable);
1694
1695  return result;
1696}
1697
1698
1699/**Function********************************************************************
1700
1701  Synopsis    [Create the latch Correlation Matrix]
1702
1703  SideEffects []
1704
1705  SeeAlso     [Part_SubsystemInfo]
1706******************************************************************************/
1707static float *
1708PartCreateCorrelationMatrixFromBDD(
1709  Part_SubsystemInfo_t *partSubInfo)
1710{
1711  int           i, j;
1712  float         *result;
1713  array_t       *agreeArray;
1714  array_t       *arrayOfMddArray;
1715  float         agreement;
1716  float         correlation = 0.0;
1717  char          *name;
1718  Ntk_Node_t    *node;
1719  Mvf_Function_t *mvf;
1720  vertex_t      *vertex;
1721  graph_t       *partition = Part_NetworkReadPartition(partSubInfo->network);
1722  mdd_manager   *mddmgr = PartPartitionReadMddManager(partition);
1723  int           index;
1724
1725  result = ALLOC(float,
1726         partSubInfo->numberOfVertex * (partSubInfo->numberOfVertex - 1) / 2);
1727
1728  arrayOfMddArray = array_alloc(array_t *, partSubInfo->numberOfVertex);
1729  for (i = 0; i < partSubInfo->numberOfVertex; i++) {
1730    node = array_fetch(Ntk_Node_t *, partSubInfo->arrayOfVertex, i);
1731    name = Ntk_NodeReadName(node);
1732    vertex = Part_PartitionFindVertexByName(partition, name);
1733    mvf = Part_VertexReadFunction(vertex);
1734    array_insert(array_t *, arrayOfMddArray, i, (array_t *)mvf);
1735  }
1736
1737  for (i = 1; i < partSubInfo->numberOfVertex; i++) {
1738    for (j = 0; j < i; j++) {
1739      int k;
1740      agreeArray = PartVertexComputeAgreement(mddmgr, i, j, arrayOfMddArray);
1741      correlation = 0.0;
1742      arrayForEachItem(float, agreeArray, k, agreement) {
1743        correlation += (float)pow(1.0 - 4.0 * agreement * (1.0 - agreement),
1744                                    partSubInfo->cor_factor);
1745      }
1746      correlation /= (float)array_n(agreeArray);
1747      array_free(agreeArray);
1748      index = i * (i - 1) / 2 + j;
1749      result[index] = correlation;
1750    }
1751  }/* end of for */
1752
1753  array_free(arrayOfMddArray);
1754  return result;
1755}
1756
1757
1758/**Function********************************************************************
1759
1760  Synopsis    [Gets the latch Correlation between two vertices]
1761
1762  SideEffects []
1763
1764  SeeAlso     [Part_SubsystemInfo]
1765******************************************************************************/
1766static float
1767PartVertexComputeCorrelation(
1768  int index1,
1769  int index2,
1770  array_t *arrayOfInputSupportTable,
1771  Part_SubsystemInfo_t *partSubInfo)
1772{
1773  st_generator *stGen;
1774  st_table *inputSupportTable1;
1775  st_table *inputSupportTable2;
1776  int sameSupportCount;
1777  float correlation;
1778  int inputSupportCount;
1779  Ntk_Node_t *node;
1780
1781  sameSupportCount = 0;
1782  inputSupportTable1 = array_fetch(st_table *, arrayOfInputSupportTable,
1783                                index1);
1784  inputSupportTable2 = array_fetch(st_table *, arrayOfInputSupportTable,
1785                                index2);
1786
1787  st_foreach_item(inputSupportTable1, stGen, &node, NULL) {
1788    if (st_is_member(inputSupportTable2, node)) {
1789      sameSupportCount++;
1790    }
1791  }
1792
1793  inputSupportCount = st_count(inputSupportTable1) +
1794                        st_count(inputSupportTable2) - sameSupportCount;
1795  if (inputSupportCount != 0) {
1796    correlation = (float)pow((double)sameSupportCount /
1797                             (double)inputSupportCount,
1798                             (double)partSubInfo->cor_factor);
1799  } else {
1800    correlation = 0.0;
1801  }
1802  return correlation;
1803}
1804
1805
1806/**Function********************************************************************
1807
1808  Synopsis    [Gets the latch Correlation between two vertices]
1809
1810  SideEffects []
1811
1812  SeeAlso     [Part_SubsystemInfo]
1813******************************************************************************/
1814static array_t *
1815PartVertexComputeAgreement(
1816  mdd_manager *mddMgr,
1817  int index1,
1818  int index2,
1819  array_t *arrayOfMddArray)
1820{
1821  int i, j;
1822  float agreement;
1823  mdd_t *mddFrom, *mddTo;
1824  array_t *mddArrayFrom, *mddArrayTo;
1825  array_t *agreeArray = array_alloc(float, 0);
1826
1827  mddArrayFrom = array_fetch(array_t *, arrayOfMddArray, index1);
1828  mddArrayTo   = array_fetch(array_t *, arrayOfMddArray, index2);
1829  arrayForEachItem(mdd_t *, mddArrayFrom, i, mddFrom) {
1830    arrayForEachItem(mdd_t *, mddArrayTo, j, mddTo) {
1831      agreement = bdd_correlation(mddFrom, mddTo);
1832      array_insert_last(float, agreeArray, agreement);
1833    }
1834  }
1835
1836  return agreeArray;
1837}
1838
1839
1840/**Function********************************************************************
1841
1842  Synopsis    [Create the latch Affinity Matrix]
1843
1844  Description [Affinity is a convex function of connectivity and correlation.
1845  For circuits which are more primary input sensitive, the latch
1846  correlation seems to be more important, while for circuit which are more
1847  state sensitive, the latch connectivity seems to be more important.The
1848  aff_factor controls the weight of two sides. The bigger the aff_factor is,
1849  the more weight is given to the latch connectivity.]
1850
1851  SideEffects [Each row element of arrayOfCorreletion is freed]
1852
1853  SeeAlso     [Part_SubsystemInfo]
1854******************************************************************************/
1855static float *
1856PartCreateAffinityMatrix(
1857  char *arrayOfDependency,
1858  float *arrayOfCorrelation,
1859  Part_SubsystemInfo_t *partSubInfo)
1860{
1861  float *result;
1862  int i, j;
1863  float dep1, dep2;
1864  float connectivity = 0.0;
1865  float correlation = 0.0;
1866  float affinity;
1867  int   index;
1868
1869  result = ALLOC(float,
1870         partSubInfo->numberOfVertex * (partSubInfo->numberOfVertex - 1) / 2);
1871
1872  for (i = 1; i < partSubInfo->numberOfVertex; i++) {
1873    for (j = 0; j < i; j++) {
1874      if (arrayOfDependency) {
1875        dep1 = dep2 = 0.0;
1876        index = i * partSubInfo->numberOfVertex + j;
1877        if (arrayOfDependency[index] == 1)
1878        dep1 = 1.0;
1879        index = j * partSubInfo->numberOfVertex + i;
1880        if (arrayOfDependency[index] == 1)
1881        dep2 = 1.0;
1882        connectivity = (dep1 + dep2 +
1883                        (partSubInfo->con_factor - 2) * dep1 * dep2) /
1884                        partSubInfo->con_factor;
1885      } else
1886        connectivity = 0.0;
1887
1888      if (arrayOfCorrelation)
1889        correlation = PartGetElementFromSymMatrix(arrayOfCorrelation, i, j);
1890      else
1891        correlation = 0.0;
1892
1893     /*
1894      * affinity is a convex function of connectivity and correlation
1895      */
1896      affinity = partSubInfo->aff_factor * connectivity +
1897                (1.0 - partSubInfo->aff_factor) * correlation;
1898      index = i * (i - 1) / 2 + j;
1899      result[index] = affinity;
1900    }
1901  }
1902  return result;
1903}
1904
1905/**Function********************************************************************
1906
1907  Synopsis    [Gets Conected Components of vertices]
1908
1909  Description [The affinity matrix is considered as graph, and higher value than
1910  threshold is considered edge between two verticies. And connected components
1911  are found by searching the graph]
1912
1913  SideEffects []
1914
1915  SeeAlso     []
1916******************************************************************************/
1917static array_t *
1918PartGetConnectedComponent(
1919  float *arrayOfAffinity,
1920  Part_SubsystemInfo_t *partSubInfo,
1921  st_table *indexToPtr)
1922{
1923  array_t  *arrayOfCCs; /* array of connected component */
1924  array_t  *connectedComponent;
1925  array_t  *arrayOfFrom;
1926  array_t  *arrayOfCCIndex; /* keep ccId of each vertex */
1927  float    affinity, affmax;
1928  float   affsum, density, nonZeroCount;
1929  int      next; /* serching connected component from this index */
1930  int      ccId; /* each connected component gets its own ccId */
1931  int      ccIndex;
1932  int      i, size;
1933  Ntk_Node_t *node;
1934
1935  next = 0;   /* keep the smallest index of vertex not included in CC */
1936  ccId = 0;   /* give ccId to each CC */
1937  affmax = 0.0;
1938  affsum = 0.0;
1939  nonZeroCount = 0;
1940
1941  arrayOfCCIndex = array_alloc(int, partSubInfo->numberOfVertex);
1942 /*
1943  * Initially, all vertecies are included in one component
1944  */
1945  for (i = 0; i < partSubInfo->numberOfVertex; i++) {
1946    array_insert(int, arrayOfCCIndex, i, 0);
1947  }
1948 /*
1949  * If the threshold is not defined, get an average of affinity in the matrix
1950  * and a density. Threshold is assigned between average of affinity and
1951  * the maximum value of affinity according to density. If the matrix is
1952  * dense(sparse), threshold goes up(goes down).
1953  */
1954  if (partSubInfo->threshold == 0.0) {
1955    size = partSubInfo->numberOfVertex * (partSubInfo->numberOfVertex - 1) / 2;
1956    for (i = 0; i < size; i++) {
1957      affinity = arrayOfAffinity[i];
1958      if (affmax < affinity) {
1959        affmax = affinity;
1960      }
1961      if (affinity > 0.0) {
1962        nonZeroCount += 1.0;
1963      }
1964      affsum += affinity;
1965    }
1966    density = nonZeroCount / pow((double)partSubInfo->numberOfVertex, 2.0);
1967    partSubInfo->threshold = (float)((affsum / nonZeroCount) +
1968                                (affmax - affsum / nonZeroCount) * density);
1969  }
1970
1971 /*
1972  * Get a connected component from the vertex which is pointed by 'next'
1973  * with its index. The 'next' is updated during searching CC in the function
1974  * PartFindCC
1975  */
1976  while (next < partSubInfo->numberOfVertex) {
1977    ccId++;
1978    array_insert(int, arrayOfCCIndex, next, ccId);
1979    if (next == partSubInfo->numberOfVertex - 1) {
1980      break;
1981    }
1982    arrayOfFrom = array_alloc(int, 1);
1983    array_insert(int, arrayOfFrom, 0, next);
1984    PartFindCC(&next, &ccId, arrayOfCCIndex, arrayOfAffinity, arrayOfFrom,
1985                partSubInfo);
1986  }
1987
1988 /*
1989  * initialize arrayOfCCs, which is the result.
1990  */
1991  arrayOfCCs = array_alloc(array_t *, ccId);
1992  for (i = 0; i < ccId; i++) {
1993    connectedComponent = array_alloc(Ntk_Node_t *, 0);
1994    array_insert(array_t *, arrayOfCCs, i, connectedComponent);
1995  }
1996
1997 /*
1998  * change index to vertex pointer and insert into each CC
1999  */
2000  arrayForEachItem(int, arrayOfCCIndex, i, ccIndex) {
2001    st_lookup(indexToPtr, (char *)(long)i, &node);
2002    connectedComponent = array_fetch(array_t *, arrayOfCCs, ccIndex-1);
2003    array_insert_last(Ntk_Node_t *, connectedComponent, node);
2004
2005  }
2006  array_free(arrayOfCCIndex);
2007  return arrayOfCCs;
2008}
2009
2010/**Function********************************************************************
2011
2012  Synopsis    [Get a conected component of vertices.]
2013
2014  SideEffects [The connected component is searched from 'arrayFrom' and
2015  each vertex in that connected component gets the index of the current
2016  connected component. And 'next' points the next possible vertex]
2017
2018  SeeAlso     []
2019******************************************************************************/
2020static void
2021PartFindCC(
2022  int *next,
2023  int *ccId,
2024  array_t *arrayOfCCIndex,
2025  float *arrayOfAffinity,
2026  array_t *arrayOfFrom,
2027  Part_SubsystemInfo_t *partSubInfo)
2028{
2029  int i, j, from;
2030  int arrayInd;
2031  float connected;
2032  array_t *arrayOfReached;
2033
2034 /*
2035  * Update next in order to let next keep the smallest vertex index which
2036  * is not traversed.
2037  */
2038  (*next)++;
2039  while (1) {
2040    if (*next == partSubInfo->numberOfVertex) {
2041      array_free(arrayOfFrom);
2042      return;
2043    }
2044    if (array_fetch(int, arrayOfCCIndex, *next) != 0) {
2045      (*next)++;
2046    } else {
2047      break;
2048    }
2049  }
2050
2051  arrayOfReached = array_alloc(int, 0); /* Reached set from arrayOfFrom */
2052
2053  /*
2054  * Find all vertecies which can be traversed from arrayOfFrom
2055  * and update next
2056  */
2057  while (array_n(arrayOfFrom) > 0) {
2058    arrayForEachItem(int, arrayOfFrom, i, from) {
2059      for (j = 0; j < partSubInfo->numberOfVertex; j++) {
2060        connected = PartGetElementFromSymMatrix(arrayOfAffinity, from, j);
2061        arrayInd = array_fetch(int, arrayOfCCIndex, j);
2062        if (connected > partSubInfo->threshold && arrayInd == 0) {
2063          array_insert_last(int, arrayOfReached, j);
2064          array_insert(int, arrayOfCCIndex, j, *ccId);
2065          if (*next == j) {
2066            (*next)++;
2067            while (1) {
2068              if (*next == partSubInfo->numberOfVertex) {
2069                array_free(arrayOfReached);
2070                array_free(arrayOfFrom);
2071                return;
2072              }
2073              if (array_fetch(int, arrayOfCCIndex, *next) != 0) {
2074                (*next)++;
2075              } else {
2076                break;
2077              }
2078            }/* end of while */
2079          }/* end if */
2080        }
2081      }/* end for */
2082    }/* end of arrayForEachItem(arrayOfFrom) */
2083    array_free(arrayOfFrom);
2084    arrayOfFrom = arrayOfReached;  /* Traverse with new reached set */
2085    arrayOfReached = array_alloc(int, 0);
2086  }/* end of while */
2087  array_free(arrayOfFrom);
2088  array_free(arrayOfReached);
2089  return;
2090}
2091
2092/**Function********************************************************************
2093
2094  Synopsis    [Gets an sub-partitions with bounded size]
2095
2096  Description [Break the connected component which has more verteices than
2097  bound and aggregate the connected components which have less vertecies
2098  than bound.]
2099
2100  SideEffects []
2101
2102  SeeAlso     []
2103******************************************************************************/
2104static array_t *
2105PartBreakingAggregating(
2106  array_t       *arrayOfInit,
2107  float         *arrayOfAffinity,
2108  Part_SubsystemInfo_t *partSubInfo,
2109  st_table      *ptrToIndex,
2110  char          *arrayOfDependency)
2111{
2112  array_t       *arrayOfAggregate;
2113  array_t       *arrayOfSeed;
2114  array_t       *arrayOfSmall;
2115  array_t       *arrayOfBreak;
2116  array_t       *arrayOfFinal;
2117  array_t       *arrayOfCCVertex;
2118  array_t       *arrayVertex;
2119  array_t       *arrayOfNew;
2120  array_t       *cc;
2121  array_t       *ccCheck; /* check cc which is included in final result */
2122  float         *groupDependency;
2123  st_table      *tableOfCC;
2124  float         groupDep;
2125  int           i, j, k, l;
2126  array_t       *arrayOfLatchNames;
2127  char          *name;
2128  Part_Subsystem_t *sub;
2129  Part_Subsystem_t *subIn;
2130  Part_Subsystem_t *subOut;
2131  Ntk_Node_t    *seedlast, *seednext, *node;
2132  char          *funcName;
2133
2134  arrayOfSmall = array_alloc(array_t *, 0);
2135  arrayOfFinal = array_alloc(Part_Subsystem_t *, 0);
2136  arrayOfCCVertex = array_alloc(array_t *, 0);
2137
2138  if (partSubInfo->bound == 0) {
2139    partSubInfo->bound = partSubInfo->numberOfVertex / array_n(arrayOfInit);
2140  }
2141
2142  arrayForEachItem(array_t *, arrayOfInit, i, cc) {
2143    if (array_n(cc) > partSubInfo->bound) {
2144     /*
2145      * If cc has more vertecies than bound, calculate how many seeds are needed
2146      * and get those seeds which are far away from each others
2147      */
2148      ccCheck = array_alloc(int, array_n(cc));
2149      for (j = 0; j < array_n(cc); j++) {
2150        array_insert(int, ccCheck, j, 0);
2151      }
2152
2153     /*
2154      * The first seed is the vertex which has the smallest support and
2155      * choose the next vertex which is the farthest from last seed
2156      */
2157      arrayOfSeed = array_alloc(Ntk_Node_t *, 0);
2158      seedlast = PartSelectNodeOfMinSupport(cc, ccCheck, partSubInfo);
2159      array_insert_last(Ntk_Node_t *, arrayOfSeed, seedlast);
2160      for (j = 1; j < ceil((double)array_n(cc) / (double)(partSubInfo->bound));
2161           j++) {
2162        seednext = PartSelectFarNode(seedlast, cc, ccCheck, arrayOfAffinity,
2163                        ptrToIndex);
2164        array_insert_last(Ntk_Node_t *, arrayOfSeed, seednext);
2165        seedlast = seednext;
2166      }
2167     /*
2168      * Break big CC, put into table and insert into final result
2169      */
2170      arrayOfBreak = PartBreakingBigConnectedComponent(cc, ccCheck,
2171            arrayOfSeed, arrayOfAffinity, partSubInfo, ptrToIndex);
2172      array_free(ccCheck);
2173      array_free(arrayOfSeed);
2174
2175      arrayForEachItem(array_t *, arrayOfBreak, j, arrayOfNew) {
2176        if (array_n(arrayOfNew) == partSubInfo->bound) {
2177          tableOfCC = st_init_table(strcmp, st_strhash);
2178          arrayVertex = array_alloc(Ntk_Node_t *, array_n(arrayOfNew));
2179          arrayForEachItem(Ntk_Node_t *, arrayOfNew, k, node) {
2180            funcName = Ntk_NodeReadName(node);
2181            if (st_lookup(partSubInfo->dupLatchTable, funcName,
2182                &arrayOfLatchNames)) {
2183              arrayForEachItem(char *, arrayOfLatchNames, l, name) {
2184                st_insert(tableOfCC, (char *)name, (char *)NULL);
2185              }
2186            } else {
2187              if (st_lookup(partSubInfo->latchNameTable, (char *)funcName,
2188                        (char **)&name)) {
2189                st_insert(tableOfCC, (char *)name, (char *)NULL);
2190              } else
2191                error_append("can't find the latch name.");
2192            }
2193            array_insert(Ntk_Node_t *, arrayVertex, k, node);
2194          }
2195          sub = ALLOC(Part_Subsystem_t, 1);
2196          sub->vertexNameTable = tableOfCC;
2197          sub->subsystemFanIn = array_alloc(int, 0);
2198          sub->subsystemFanOut = array_alloc(int, 0);
2199          array_insert_last(Part_Subsystem_t *, arrayOfFinal, sub);
2200          array_insert_last(array_t *, arrayOfCCVertex, arrayVertex);
2201          array_free(arrayOfNew);
2202        } else {
2203          array_insert_last(array_t *, arrayOfSmall, arrayOfNew);
2204        }
2205      }/* end of arrayForEachItem(arrayOfBreak) */
2206      array_free(arrayOfBreak);
2207      array_free(cc);
2208    } else if (array_n(cc) < partSubInfo->bound) {
2209     /*
2210      * If cc has less nodes than bound, put into arrayOfSmall
2211      */
2212      array_insert_last(array_t *, arrayOfSmall, cc);
2213    } else {
2214     /*
2215      * If cc has same number of verteices as bound, put into table and
2216      * insert into final result
2217      */
2218      tableOfCC = st_init_table(strcmp, st_strhash);
2219      arrayVertex = array_alloc(Ntk_Node_t *, array_n(cc));
2220      arrayForEachItem(Ntk_Node_t *, cc, j, node) {
2221        funcName = Ntk_NodeReadName(node);
2222        if (st_lookup(partSubInfo->dupLatchTable, funcName,
2223                &arrayOfLatchNames)) {
2224          arrayForEachItem(char *, arrayOfLatchNames, l, name) {
2225            st_insert(tableOfCC, (char *)name, (char *)NULL);
2226          }
2227        } else {
2228          if (st_lookup(partSubInfo->latchNameTable, (char *)funcName,
2229                (char **)&name)) {
2230            st_insert(tableOfCC, (char *)name, (char *)NULL);
2231          } else
2232            error_append("can't find the latch name.");
2233        }
2234        array_insert(Ntk_Node_t *, arrayVertex, j, node);
2235      }
2236      sub = ALLOC(Part_Subsystem_t, 1);
2237      sub->vertexNameTable = tableOfCC;
2238      sub->subsystemFanIn = array_alloc(int, 0);
2239      sub->subsystemFanOut = array_alloc(int, 0);
2240      array_insert_last(Part_Subsystem_t *, arrayOfFinal, sub);
2241      array_insert_last(array_t *, arrayOfCCVertex, arrayVertex);
2242      array_free(cc);
2243    }
2244  }
2245
2246 /*
2247  * aggregate small cc, put into table and insert into final resault
2248  */
2249  arrayOfAggregate = PartAggregating(arrayOfSmall, arrayOfAffinity,
2250                        partSubInfo, ptrToIndex);
2251
2252  array_free(arrayOfSmall);
2253
2254  arrayForEachItem(array_t *, arrayOfAggregate, i, arrayOfNew) {
2255    tableOfCC = st_init_table(strcmp, st_strhash);
2256    arrayVertex = array_alloc(Ntk_Node_t *, array_n(arrayOfNew));
2257    arrayForEachItem(Ntk_Node_t *, arrayOfNew, j, node) {
2258      funcName = Ntk_NodeReadName(node);
2259      if (st_lookup(partSubInfo->dupLatchTable, funcName,
2260                    &arrayOfLatchNames)) {
2261        arrayForEachItem(char *, arrayOfLatchNames, l, name) {
2262          st_insert(tableOfCC, (char *)name, (char *)NULL);
2263        }
2264      } else {
2265        if (st_lookup(partSubInfo->latchNameTable, (char *)funcName,
2266                (char **)&name)) {
2267          st_insert(tableOfCC, (char *)name, (char *)NULL);
2268        } else
2269          error_append("can't find the latch name.");
2270      }
2271      array_insert(Ntk_Node_t *, arrayVertex, j, node);
2272    }
2273    sub = ALLOC(Part_Subsystem_t, 1);
2274    sub->vertexNameTable = tableOfCC;
2275    sub->subsystemFanIn = array_alloc(int, 0);
2276    sub->subsystemFanOut = array_alloc(int, 0);
2277    array_insert_last(Part_Subsystem_t *, arrayOfFinal, sub);
2278    array_insert_last(array_t *, arrayOfCCVertex, arrayVertex);
2279    array_free(arrayOfNew);
2280  }/* end of arrayForEachItem(arrayOfAggregate) */
2281
2282  array_free(arrayOfAggregate);
2283
2284 /*
2285  * Get group dependency, which is dependency between two subsystems from
2286  * dependency between vertecies
2287  */
2288  groupDependency = PartGetGroupMatrixRegular(arrayOfCCVertex,
2289                        arrayOfDependency, ptrToIndex,
2290                        partSubInfo->numberOfVertex);
2291
2292  if (partSubInfo->verbosity >= 2) {
2293    int index;
2294    fprintf(vis_stdout, "\nGrouping: Group Dependency\n");
2295    fprintf(vis_stdout, "--------------------------\n");
2296    for (i = 0; i < array_n(arrayOfCCVertex); i++) {
2297      for (j = 0; j < array_n(arrayOfCCVertex); j++) {
2298        index = i * array_n(arrayOfCCVertex) + j;
2299        fprintf(vis_stdout, "%4.3f ", groupDependency[index]);
2300      }
2301      fprintf(vis_stdout, "\n");
2302    }
2303  }
2304
2305  for (i = 0; i < array_n(arrayOfCCVertex); i++) {
2306    subIn = array_fetch(Part_Subsystem_t *, arrayOfFinal, i);
2307    for (j = 0; j < array_n(arrayOfCCVertex); j++) {
2308      subOut = array_fetch(Part_Subsystem_t *, arrayOfFinal, j);
2309      if (i != j) {
2310        int     index;
2311
2312        index = i * array_n(arrayOfCCVertex) + j;
2313        groupDep = groupDependency[index];
2314        if (groupDep > 0.0) {
2315          array_insert_last(int, subIn ->subsystemFanIn, j);
2316          array_insert_last(int, subOut->subsystemFanOut, i);
2317        }
2318      }
2319    }
2320  }
2321  PartArrayOfArrayFree(arrayOfCCVertex);
2322  FREE(groupDependency);
2323  return arrayOfFinal;
2324}
2325
2326/**Function********************************************************************
2327
2328  Synopsis    [Create subsystems accoring to arrayOfGroupIndex]
2329
2330  Description [Each latch data input L(i) in array arrayOfLatchDataInputNamesi
2331  is put in I(i)'th subsystem. I is arrayOfGroupIndex. Index should start from
2332  0 to n as sequence.]
2333
2334  SideEffects []
2335
2336  SeeAlso     []
2337******************************************************************************/
2338static array_t *
2339PartCreateSubSystemWithGroupIndex(
2340  Part_SubsystemInfo_t *partSubInfo,
2341  array_t *arrayOfLatchNames,
2342  array_t *arrayOfGroupIndex)
2343{
2344  int           i, j;
2345  array_t       *result;
2346  char          *latchName;
2347  array_t       *arrayOfGroupVertex;
2348  array_t       *arrayOfVertex;
2349  array_t       *arrayOfLatchDataInputNames;
2350  Ntk_Node_t    *node, *latchNode, *latchInputNode;
2351  Part_Subsystem_t *sub;
2352  st_table      *groupIndexTable;
2353  st_table      **faninIndexTable, **fanoutIndexTable;
2354  char          *name;
2355  array_t       *arrayOfSupport;
2356  st_generator  *stGen;
2357  int           nLatches;
2358  int           nGroups = 0;
2359  int           preIndex, newIndex;
2360  long          index;
2361  char          *otherLatchName;
2362  array_t       *latchNameArray;
2363
2364  nLatches = array_n(arrayOfLatchNames);
2365
2366  /* reassign group index with counting the number of groups */
2367  groupIndexTable = st_init_table(st_numcmp, st_numhash);
2368  preIndex = -1;
2369  arrayForEachItem(int, arrayOfGroupIndex, i, index) {
2370    if (index == preIndex ||
2371        st_lookup_int(groupIndexTable, (char *)index, &newIndex)) {
2372      if (index != newIndex)
2373        array_insert(int, arrayOfGroupIndex, i, newIndex);
2374    } else {
2375      st_insert(groupIndexTable, (char *)index, (char *)(long)nGroups);
2376      newIndex = nGroups++;
2377      if (index != newIndex)
2378        array_insert(int, arrayOfGroupIndex, i, newIndex);
2379    }
2380    preIndex = (int) index;
2381  }
2382  st_free_table(groupIndexTable);
2383
2384  groupIndexTable = st_init_table(strcmp, st_strhash);
2385  faninIndexTable = ALLOC(st_table *, nGroups);
2386  fanoutIndexTable = ALLOC(st_table *, nGroups);
2387  for (i = 0; i < nGroups; i++) {
2388    faninIndexTable[i] = st_init_table(st_numcmp, st_numhash);
2389    fanoutIndexTable[i] = st_init_table(st_numcmp, st_numhash);
2390  }
2391
2392  /* makes an array of latch input names from latch names */
2393  arrayOfLatchDataInputNames = array_alloc(char *, 0);
2394  arrayForEachItem(char *, arrayOfLatchNames, i, latchName) {
2395    latchNode = Ntk_NetworkFindNodeByName(partSubInfo->network, latchName);
2396    latchInputNode = Ntk_LatchReadDataInput(latchNode);
2397    name = Ntk_NodeReadName(latchInputNode);
2398    array_insert_last(char *, arrayOfLatchDataInputNames, name);
2399  }
2400
2401  result = array_alloc(Part_Subsystem_t *, nGroups);
2402  arrayOfGroupVertex = array_alloc(array_t *, nGroups);
2403
2404  /* creates subsystems */
2405  for (i = 0; i < nGroups; i++) {
2406    sub = ALLOC(Part_Subsystem_t, 1);
2407    sub->vertexNameTable = st_init_table(strcmp, st_strhash);
2408    sub->subsystemFanIn = array_alloc(int, 0);
2409    sub->subsystemFanOut = array_alloc(int, 0);
2410    arrayOfVertex = array_alloc(Ntk_Node_t *, 0);
2411    array_insert(Part_Subsystem_t *, result, i, sub);
2412    array_insert(array_t *, arrayOfGroupVertex, i, arrayOfVertex);
2413  }
2414
2415  /* makes group index table and fills in the vertex name table */
2416  for (i = 0; i < nLatches; i++) {
2417    index = (long) array_fetch(int, arrayOfGroupIndex, i);
2418    name = array_fetch(char *, arrayOfLatchDataInputNames, i);
2419    latchName = array_fetch(char *, arrayOfLatchNames, i);
2420
2421    sub = array_fetch(Part_Subsystem_t *, result, (int) index);
2422    latchNode = Ntk_NetworkFindNodeByName(partSubInfo->network, latchName);
2423    latchName = Ntk_NodeReadName(latchNode);
2424    st_insert(sub->vertexNameTable, (char *)latchName, (char *)NULL);
2425
2426    if (st_lookup(partSubInfo->latchNameTable, name, &otherLatchName)) {
2427      if (st_lookup(partSubInfo->dupLatchTable, name, &latchNameArray)) {
2428        array_insert_last(char *, latchNameArray, latchName);
2429      } else {
2430        latchNameArray = array_alloc(char *, 0);
2431        array_insert_last(char *, latchNameArray, otherLatchName);
2432        array_insert_last(char *, latchNameArray, latchName);
2433        st_insert(partSubInfo->dupLatchTable, name, latchNameArray);
2434      }
2435      continue;
2436    }
2437
2438    st_insert(partSubInfo->latchNameTable, name, latchName);
2439    st_insert(groupIndexTable, name, (char *)index);
2440
2441    arrayOfVertex = array_fetch(array_t *, arrayOfGroupVertex, (int)index);
2442    node = Ntk_NetworkFindNodeByName(partSubInfo->network, name);
2443    array_insert_last(Ntk_Node_t *, arrayOfVertex, node);
2444  }
2445
2446  /* computes fanin and fanout table for each group */
2447  for (i = 0; i < nGroups; i++) {
2448    arrayOfVertex = array_fetch(array_t *, arrayOfGroupVertex, i);
2449    arrayOfSupport = Ntk_NodeComputeCombinationalSupport(partSubInfo->network,
2450        arrayOfVertex, FALSE);
2451    arrayForEachItem(Ntk_Node_t *, arrayOfSupport, j, node) {
2452      if (!Ntk_NodeTestIsLatch(node))
2453        continue;
2454      name = Ntk_NodeReadName(Ntk_LatchReadDataInput(node));
2455      if (st_lookup(groupIndexTable, name, &index)) {
2456        if (index == i)
2457          continue;
2458        st_insert(faninIndexTable[i], (char *)index, NIL(char));
2459        st_insert(fanoutIndexTable[index], (char *)(long)i, NIL(char));
2460      }
2461    }
2462    array_free(arrayOfSupport);
2463  }
2464
2465  /* makes fanin and fanout array for each subsystem */
2466  for (i = 0; i < nGroups; i++) {
2467    sub = array_fetch(Part_Subsystem_t *, result, i);
2468    st_foreach_item(faninIndexTable[i], stGen, &index, NULL) {
2469      array_insert_last(int, sub->subsystemFanIn, (int) index);
2470    }
2471    st_free_table(faninIndexTable[i]);
2472    array_sort(sub->subsystemFanIn, numCompare);
2473    st_foreach_item(fanoutIndexTable[i], stGen, &index, NULL) {
2474      array_insert_last(int, sub->subsystemFanOut, (int) index);
2475    }
2476    st_free_table(fanoutIndexTable[i]);
2477    array_sort(sub->subsystemFanOut, numCompare);
2478  }
2479
2480  FREE(faninIndexTable);
2481  FREE(fanoutIndexTable);
2482  array_free(arrayOfLatchDataInputNames);
2483  st_free_table(groupIndexTable);
2484  PartArrayOfArrayFree(arrayOfGroupVertex);
2485  return result;
2486}
2487
2488/**Function********************************************************************
2489
2490  Synopsis    [Gets bounded size blocks from big CC, Breaking]
2491
2492  Description [Gets bounded size blocks from big connected component]
2493
2494  SideEffects []
2495
2496  SeeAlso     []
2497******************************************************************************/
2498static array_t *
2499PartBreakingBigConnectedComponent(
2500  array_t *arrayOfCC,
2501  array_t *ccCheck,
2502  array_t *arrayOfSeed,
2503  float *arrayOfAffinity,
2504  Part_SubsystemInfo_t *partSubInfo,
2505  st_table *ptrToIndex)
2506{
2507  array_t *result;    /* array of groups with the proper size */
2508  array_t *resultRow; /* a group with the proper size */
2509  array_t *arrayTemp;
2510  array_t *seedFull;  /* array of seeds */
2511  int i, count;
2512  int totalCount;     /* how many vertixes are already computed */
2513  int indexOfSeed;    /* index of the seed which is closest from the vertex */
2514  Ntk_Node_t *seed, *variable, *pick;
2515
2516  result = array_alloc(array_t *, array_n(arrayOfSeed));
2517
2518  for (i = 0; i < array_n(arrayOfSeed); i++) {
2519    arrayTemp = array_alloc(Ntk_Node_t *, 0);
2520    seed = array_fetch(Ntk_Node_t *, arrayOfSeed, i);
2521    array_insert_last(Ntk_Node_t *, arrayTemp, seed);
2522    array_insert(array_t *, result, i, arrayTemp);
2523  }
2524
2525  switch (partSubInfo->partBM) {
2526   /*
2527    * Breaking Static Round Robin Seed Choice
2528    * Fixed order of seeds and each seed find the closest vertex
2529    */
2530    case Part_BSRR_s:
2531      totalCount = array_n(arrayOfSeed);
2532      arrayForEachItem(Ntk_Node_t *, arrayOfSeed, i, seed) {
2533        count = 1;
2534        resultRow = array_fetch(array_t *, result, i);
2535        while ((count < partSubInfo->bound) &&
2536              (totalCount < array_n(arrayOfCC))) {
2537          pick = PartSelectCloseNode(seed, arrayOfCC, ccCheck,
2538                        arrayOfAffinity, ptrToIndex);
2539          array_insert_last(Ntk_Node_t *, resultRow, pick);
2540          count++;
2541          totalCount++;
2542          seed = pick;
2543        }
2544      }
2545      break;
2546   /*
2547    * Breaking Fixed Order State Variable Choice
2548    * Fixed order of vertecies and each vertex find the closest seed
2549    */
2550    case Part_BFix_v:
2551     /*
2552      * Fixed order of nodes and each node find the closest seed
2553      */
2554      seedFull = array_alloc(int, 0);
2555      for (i = 0; i < array_n(arrayOfSeed); i++) {
2556        array_insert_last(int, seedFull, 1);
2557
2558      }
2559      arrayForEachItem(Ntk_Node_t *, arrayOfCC, i, variable) {
2560        if (array_fetch(int, ccCheck, i) != 1) {
2561          indexOfSeed = PartSelectCloseSeedIndex(variable, arrayOfSeed,
2562                arrayOfAffinity, ptrToIndex, seedFull, partSubInfo->bound);
2563          resultRow = array_fetch(array_t *, result, indexOfSeed);
2564          array_insert_last(Ntk_Node_t *, resultRow, variable);
2565          array_insert(int, ccCheck, i, 1);
2566        }
2567      }
2568      array_free(seedFull);
2569      break;
2570    default:
2571      break;
2572  }
2573  return result;
2574}
2575
2576
2577/**Function********************************************************************
2578
2579  Synopsis    [Gets bounded size blocks from small connected components.]
2580
2581  Description [The small connected components are aggregated by 'Static
2582  Round Robin Cluster Seed Algorithm(Fixed order of seed and each seed
2583  choose the closest connected component)'.]
2584
2585  SideEffects []
2586
2587******************************************************************************/
2588static array_t *
2589PartAggregating(
2590  array_t *arrayOfSmall,
2591  float *arrayOfAffinity,
2592  Part_SubsystemInfo_t *partSubInfo,
2593  st_table *ptrToIndex)
2594{
2595  float *arrayOfGroupAff;
2596  array_t *result;
2597  array_t *arraySeed;
2598  array_t *arraySeedIndex;
2599  array_t *arrayTemp;
2600  array_t *arrayRow;
2601  array_t *cc;
2602  array_t *ccCheck;
2603  array_t *seed;
2604  int i, j;
2605  int count;  /* total number of vertices in all small connected components */
2606  int pick, keepInd;
2607  int seedLast, seedNew, seedIndex;
2608  int numberOfSeed;
2609  boolean isDone;
2610  array_t *keep = array_alloc(int, 0);
2611
2612  count = 0;
2613
2614  arrayForEachItem(array_t *, arrayOfSmall, i, cc) {
2615    count += array_n(cc);
2616  }
2617
2618  numberOfSeed = (int) ceil((double)count/(double)partSubInfo->bound);
2619
2620  arrayOfGroupAff = PartGetGroupMatrixSym(arrayOfSmall, arrayOfAffinity,
2621                        ptrToIndex);
2622
2623  if (partSubInfo->verbosity >= 2) {
2624    fprintf(vis_stdout, "\nGrouping: Group affinity of initial ");
2625    fprintf(vis_stdout, "connected component\n");
2626    fprintf(vis_stdout, "------------------------------------");
2627    fprintf(vis_stdout, "-------------------\n");
2628    PartPrintArrayArray(arrayOfGroupAff, array_n(arrayOfSmall), 0);
2629  }
2630
2631  ccCheck = array_alloc(int, array_n(arrayOfSmall));
2632  for (i = 0; i < array_n(arrayOfSmall); i++) {
2633    array_insert(int, ccCheck, i, 0);
2634  }
2635
2636 /*
2637  * The first seed is the cc which has minmum support and the next
2638  * is the farthest cc
2639  */
2640  seedLast = PartSelectCCIndexOfMinSupport(arrayOfSmall,
2641             ccCheck, partSubInfo);
2642
2643  result = array_alloc(array_t *, numberOfSeed);
2644  arraySeed = array_alloc(array_t *, numberOfSeed);
2645  arraySeedIndex = array_alloc(int, numberOfSeed);
2646
2647  for (i = 0; i < numberOfSeed; i++) {
2648    seed = array_fetch(array_t *, arrayOfSmall, seedLast);
2649    array_insert(array_t *, arraySeed, i, seed);
2650    array_insert(int, arraySeedIndex, i, seedLast);
2651    array_insert(array_t *, result, i, seed);
2652    if (i<numberOfSeed-1) {
2653      seedNew = PartSelectFarCCIndex(seedLast, arrayOfSmall, arrayOfGroupAff,
2654                        partSubInfo, ccCheck);
2655      seedLast = seedNew;
2656    }
2657  }
2658
2659 /*
2660  * Static Round Robin Cluster Seed: Fixed order of seed and each seed
2661  * choose the closest connected component
2662  */
2663  isDone = FALSE;
2664  count = array_n(arraySeed);
2665  while ((!isDone) && count < array_n(arrayOfSmall)) {
2666    isDone = TRUE;
2667    arrayForEachItem(int, arraySeedIndex, i, seedIndex) {
2668      arrayRow = array_fetch(array_t *, result, i);
2669      pick = PartSelectCloseCCIndex(seedIndex, arrayOfSmall,
2670             arrayOfGroupAff, ccCheck);
2671      count++;
2672      /* check if not all cc is assigned */
2673      if (pick != -1) {
2674        arrayTemp = array_fetch(array_t *, arrayOfSmall, pick);
2675        if (array_n(array_fetch(array_t *, arrayOfSmall, seedIndex)) +
2676            array_n(arrayTemp) <= partSubInfo->bound) {
2677          array_append(arrayRow, arrayTemp);
2678          array_free(arrayTemp);
2679          isDone = FALSE;
2680        } else {
2681         /*
2682          * If pick cc is too big to be appended to seed, find new cc
2683          */
2684          array_insert_last(int, keep, pick);
2685          pick = PartSelectCloseCCIndex(seedIndex, arrayOfSmall,
2686                        arrayOfGroupAff, ccCheck);
2687          while (pick != -1) {
2688            arrayTemp = array_fetch(array_t *, arrayOfSmall, pick);
2689            if (array_n(array_fetch(array_t *, arrayOfSmall, seedIndex)) +
2690                array_n(arrayTemp) <= partSubInfo->bound) {
2691              array_append(arrayRow, arrayTemp);
2692              array_free(arrayTemp);
2693              isDone = FALSE;
2694              break;
2695            } else {
2696              array_insert_last(int, keep, pick);
2697              pick = PartSelectCloseCCIndex(seedIndex, arrayOfSmall,
2698                        arrayOfGroupAff, ccCheck);
2699            }
2700          } /* end while */
2701          if (pick == -1) {
2702            count--;
2703          }
2704          arrayForEachItem(int, keep, j, keepInd) {
2705            array_insert(int, ccCheck, keepInd, 0);
2706          }
2707          array_free(keep);
2708          keep = array_alloc(int, 0);
2709        } /* end if */
2710      } else {
2711        count--;
2712      }/* end if */
2713    }/* end arrayForEachItem */
2714   /*
2715    * If all seeds fail to find suitable cc and not all cc is assigned,
2716    *  get a new seed.
2717    */
2718    if (count < array_n(arrayOfSmall) && isDone) {
2719      seedIndex = PartSelectCCIndexOfMinSupport(arrayOfSmall,
2720                        ccCheck, partSubInfo);
2721      count++;
2722      seed = array_fetch(array_t *, arrayOfSmall, seedIndex);
2723      array_insert_last(array_t *, arraySeed, seed);
2724      array_insert_last(int, arraySeedIndex, seedIndex);
2725      array_insert_last(array_t *, result, seed);
2726      isDone = FALSE;
2727    }
2728  }
2729  array_free(arraySeed);
2730  array_free(arraySeedIndex);
2731  array_free(keep);
2732  array_free(ccCheck);
2733  FREE(arrayOfGroupAff);
2734  return result;
2735}
2736
2737/**Function********************************************************************
2738
2739  Synopsis    [Select the closest node from seed and return node pointer]
2740
2741  SideEffects [The Corresponding flag of ccCheck is set after selection]
2742
2743******************************************************************************/
2744static Ntk_Node_t *
2745PartSelectCloseNode(
2746  Ntk_Node_t    *seed,
2747  array_t       *arrayOfCC,
2748  array_t       *ccCheck,
2749  float         *arrayOfAffinity,
2750  st_table      *ptrToIndex)
2751{
2752  int           i;
2753  float         affinity;
2754  float         big; /* The bigest value of affinity of vertecies*/
2755  int           bigInd; /* the index of node with the biggest affinity */
2756  int           col;
2757  int           row;
2758  Ntk_Node_t    *node, *pick;
2759
2760  big = -1.0;
2761  bigInd = 0; /* to avoid warning */
2762  pick = NIL(Ntk_Node_t);
2763
2764  st_lookup_int(ptrToIndex, (char *)seed, &row);
2765
2766  arrayForEachItem(Ntk_Node_t *, arrayOfCC, i, node) {
2767    if (array_fetch(int, ccCheck, i) != 1) {
2768      st_lookup_int(ptrToIndex, (char *)node, &col);
2769      affinity = PartGetElementFromSymMatrix(arrayOfAffinity, row, col);
2770      if (affinity > big) {
2771         big = affinity;
2772         pick = node;
2773         bigInd = i;
2774      }
2775    }
2776  }
2777  array_insert(int, ccCheck, bigInd, 1);
2778  return pick;
2779}
2780
2781/**Function********************************************************************
2782
2783  Synopsis    [Select the closest seed from node and return seed index]
2784
2785  SideEffects []
2786
2787******************************************************************************/
2788static int
2789PartSelectCloseSeedIndex(
2790  Ntk_Node_t    *variable,
2791  array_t       *arrayOfSeed,
2792  float         *arrayOfAffinity,
2793  st_table      *ptrToIndex,
2794  array_t       *seedFull,
2795  int           bound)
2796{
2797  float         affinity;
2798  int           i;
2799  float         big;
2800  int           pick, row, col;
2801  Ntk_Node_t    *node;
2802
2803  big = -1.0;
2804  pick = -1;
2805
2806  st_lookup_int(ptrToIndex, (char *)variable, &row);
2807
2808  arrayForEachItem(Ntk_Node_t *, arrayOfSeed, i, node) {
2809    st_lookup_int(ptrToIndex, (char *)node, &col);
2810    affinity = PartGetElementFromSymMatrix(arrayOfAffinity, row, col);
2811    if (affinity > big && array_fetch(int, seedFull, i) < bound) {
2812      big = affinity;
2813      pick = i;
2814    }
2815  }
2816  array_insert(int, seedFull, pick, array_fetch(int, seedFull, pick) + 1);
2817  return pick;
2818}
2819
2820/**Function********************************************************************
2821
2822  Synopsis    [Select the farthest node from seed and return node pointer]
2823
2824  SideEffects [The Corresponding flag of ccCheck is set after selection]
2825
2826******************************************************************************/
2827static Ntk_Node_t *
2828PartSelectFarNode(
2829  Ntk_Node_t *seed,
2830  array_t *cc,
2831  array_t *ccCheck,
2832  float *arrayOfAffinity,
2833  st_table *ptrToIndex)
2834{
2835  float         affinity;
2836  int           i;
2837  float         small; /* the smallest affinity of vertecies */
2838  int           smallInd; /* index of vertex with the smallest affinity */
2839  int           col;
2840  int           row;
2841  Ntk_Node_t    *node, *pick;
2842
2843  small = (float)BIG_NUMBER;
2844  smallInd = 0; /* to avoid warning */
2845  pick = NIL(Ntk_Node_t);
2846
2847  st_lookup_int(ptrToIndex, (char *)seed, &row);
2848  arrayForEachItem(Ntk_Node_t *, cc, i, node) {
2849    if (array_fetch(int, ccCheck, i) != 1) {
2850      st_lookup_int(ptrToIndex, (char *)node, &col);
2851      affinity = PartGetElementFromSymMatrix(arrayOfAffinity, row, col);
2852      if (affinity < small) {
2853         small = affinity;
2854         pick = node;
2855         smallInd = i;
2856      }
2857    }
2858  }
2859  array_insert(int, ccCheck, smallInd, 1);
2860  return pick;
2861}
2862
2863
2864/**Function********************************************************************
2865
2866  Synopsis    [Get group matrix as regular matrix from given matrix
2867  according to the given clusters]
2868
2869  Description [Get matrix relation between each cluster, the values
2870  beetween
2871  each cluster are added]
2872
2873  SideEffects []
2874
2875******************************************************************************/
2876static float *
2877PartGetGroupMatrixRegular(
2878  array_t *arrayOfCluster,
2879  char *arrayOfGivenMatrix,
2880  st_table *ptrToIndex,
2881  int nVertices)
2882{
2883  float         *arrayOfGroupMatrix;  /* final result */
2884  array_t       *arrayClusterRow;
2885  array_t       *arrayClusterCol;
2886  float         subSum;
2887  int           row, col, i, j, k, l;
2888  Ntk_Node_t    *nodeRow, *nodeCol;
2889  int           index, size;
2890
2891  size = array_n(arrayOfCluster);
2892  arrayOfGroupMatrix = ALLOC(float, size * size);
2893
2894  arrayForEachItem(array_t *, arrayOfCluster, i, arrayClusterRow) {
2895    arrayForEachItem(array_t *, arrayOfCluster, j, arrayClusterCol) {
2896      if (i != j) {
2897        subSum = 0.0;
2898        arrayForEachItem(Ntk_Node_t *, arrayClusterRow, k, nodeRow) {
2899          st_lookup_int(ptrToIndex, (char *)nodeRow, &row);
2900          arrayForEachItem(Ntk_Node_t *, arrayClusterCol, l, nodeCol) {
2901            st_lookup_int(ptrToIndex, (char *)nodeCol, &col);
2902            index = row * nVertices + col;
2903            if (arrayOfGivenMatrix[index] == 1)
2904              subSum += 1.0;
2905          }
2906        }
2907        index = i * size + j;
2908        arrayOfGroupMatrix[index] = subSum /
2909                (float)(array_n(arrayClusterRow) * array_n(arrayClusterCol));
2910      } else {
2911        index = i * size + j;
2912        arrayOfGroupMatrix[index] = 0.0;
2913      }
2914    }
2915  }
2916  return arrayOfGroupMatrix;
2917}
2918
2919/**Function********************************************************************
2920
2921  Synopsis    [Get group matrix as symetric matrix from given matrix according
2922  to the given clusters]
2923
2924  Description [Get matrix relation between each cluster, the values beetween
2925  each cluster are added]
2926
2927  SideEffects []
2928
2929******************************************************************************/
2930static float *
2931PartGetGroupMatrixSym(
2932  array_t  *arrayOfCluster,
2933  float  *arrayOfGivenMatrix,
2934  st_table *ptrToIndex)
2935{
2936  float         *arrayOfGroupMatrix;  /* final result */
2937  array_t       *arrayClusterRow;
2938  array_t       *arrayClusterCol;
2939  float         subSum;
2940  int           row, col, i, j, k, l;
2941  Ntk_Node_t    *nodeRow, *nodeCol;
2942  int           index, size;
2943
2944  size = array_n(arrayOfCluster);
2945  arrayOfGroupMatrix = ALLOC(float, size * (size - 1) / 2);
2946
2947  for (i = 0; i < size; i++) {
2948    arrayClusterRow = array_fetch(array_t *, arrayOfCluster, i);
2949    for (j = 0; j < i; j++) {
2950      arrayClusterCol = array_fetch(array_t *, arrayOfCluster, j);
2951      if (i == j) {
2952        index = i * (i - 1) / 2 + j;
2953        arrayOfGroupMatrix[index] = 0.0;
2954      } else {
2955        subSum = 0.0;
2956        arrayForEachItem(Ntk_Node_t *, arrayClusterRow, k, nodeRow) {
2957          st_lookup_int(ptrToIndex, (char *)nodeRow, &row);
2958          arrayForEachItem(Ntk_Node_t *, arrayClusterCol, l, nodeCol) {
2959            st_lookup_int(ptrToIndex, (char *)nodeCol, &col);
2960            subSum += PartGetElementFromSymMatrix(arrayOfGivenMatrix, row, col);
2961          }
2962        }
2963        index = i * (i - 1) / 2 + j;
2964        arrayOfGroupMatrix[index] = subSum /
2965                (float)((array_n(arrayClusterRow)) * array_n(arrayClusterCol));
2966      }
2967    }
2968  }
2969  return arrayOfGroupMatrix;
2970}
2971
2972/**Function********************************************************************
2973
2974  Synopsis    [Select a connected component with minimum support variables]
2975
2976  SideEffects [The Corresponding flag of ccCheck is set after selection]
2977
2978******************************************************************************/
2979static int
2980PartSelectCCIndexOfMinSupport(
2981  array_t *arrayOfSmall,
2982  array_t *ccCheck,
2983  Part_SubsystemInfo_t *partSubInfo)
2984{
2985  array_t       *cc;
2986  array_t       *support;
2987  int           i, count, minCount, minIndex;
2988
2989  minCount = BIG_NUMBER;
2990  minIndex = -1;
2991
2992  for (i = 0; i < array_n(ccCheck); i++) {
2993    if (array_fetch(int, ccCheck, i) != 1) {
2994      cc = array_fetch(array_t *, arrayOfSmall, i);
2995      support = Ntk_NodeComputeCombinationalSupport(
2996        partSubInfo->network, cc, TRUE);
2997      count = array_n(support);
2998      array_free(support);
2999      if (count < minCount) {
3000        minIndex = i;
3001        minCount = count;
3002      }
3003    }
3004  }
3005  if (minIndex != -1) {
3006    array_insert(int, ccCheck, minIndex, 1);
3007  }
3008  return minIndex;
3009}
3010
3011/**Function********************************************************************
3012
3013  Synopsis    [Select a node with minimum support variables in network node
3014  set cc]
3015
3016  SideEffects [The Corresponding flag of ccCheck is set after selection]
3017
3018******************************************************************************/
3019static Ntk_Node_t *
3020PartSelectNodeOfMinSupport(
3021  array_t *cc,
3022  array_t *ccCheck,
3023  Part_SubsystemInfo_t *partSubInfo)
3024{
3025  array_t       *support;
3026  array_t       *nodeArray;
3027  int           i, minInd, count, min;
3028  Ntk_Node_t    *node;
3029  Ntk_Node_t    *minNode = NIL(Ntk_Node_t);
3030
3031  if (array_n(cc) == 0) {
3032    return NIL(Ntk_Node_t);
3033  }
3034
3035  min = BIG_NUMBER;
3036  minInd = 0; /* to avoid warning */
3037  arrayForEachItem(Ntk_Node_t *, cc, i, node) {
3038    if (array_fetch(int, ccCheck, i) != 1) {
3039      nodeArray = array_alloc(Ntk_Node_t *, 1);
3040      array_insert(Ntk_Node_t *, nodeArray, 0, node);
3041      support = Ntk_NodeComputeCombinationalSupport(
3042                        partSubInfo->network, nodeArray, TRUE);
3043      count = array_n(support);
3044      if (count < min) {
3045        minNode = node;
3046        min = count;
3047        minInd = i;
3048      }
3049      array_free(support);
3050      array_free(nodeArray);
3051    }
3052  }
3053  array_insert(int, ccCheck, minInd, 1);
3054  return minNode;
3055}
3056
3057/**Function********************************************************************
3058
3059  Synopsis    [Select an index of connected component from seed connected
3060  component]
3061
3062  SideEffects [The Corresponding flag of ccCheck is set after selection]
3063
3064******************************************************************************/
3065static int
3066PartSelectFarCCIndex(
3067  int seedIndex,
3068  array_t *arrayOfSmall,
3069  float *arrayOfGroupAff,
3070  Part_SubsystemInfo_t *partSubInfo,
3071  array_t *ccCheck)
3072{
3073  array_t *col;
3074  int i;
3075  float groupAff;
3076  float min;
3077  int minIndex;
3078
3079  min = (float)BIG_NUMBER;
3080  minIndex = -1;
3081
3082  arrayForEachItem(array_t *, arrayOfSmall, i, col) {
3083    if (array_fetch(int, ccCheck, i) != 1) {
3084      groupAff = PartGetElementFromSymMatrix(arrayOfGroupAff, seedIndex, i);
3085      if (groupAff < min) {
3086        minIndex = i;
3087        min = groupAff;
3088      }
3089    }
3090  }
3091  if (minIndex != -1) {
3092    array_insert(int, ccCheck, minIndex, 1);
3093  }
3094  return minIndex;
3095}
3096
3097/**Function********************************************************************
3098
3099  Synopsis    [Select an index of closest connected component from seed
3100  connected component]
3101
3102  SideEffects []
3103
3104******************************************************************************/
3105static int
3106PartSelectCloseCCIndex(
3107  int seedIndex,
3108  array_t *arrayOfSmall,
3109  float *arrayOfGroupAff,
3110  array_t *ccCheck)
3111{
3112  int i;
3113  float groupAff;
3114  float max;
3115  int maxIndex;
3116
3117  max = -1.0;
3118  maxIndex = -1;
3119
3120  for (i = 0; i < array_n(ccCheck); i++) {
3121    if (array_fetch(int, ccCheck, i) != 1) {
3122      groupAff = PartGetElementFromSymMatrix(arrayOfGroupAff, seedIndex, i);
3123      if (groupAff > max) {
3124        maxIndex = i;
3125        max = groupAff;
3126      }
3127    }
3128  }
3129  if (maxIndex != -1) {
3130    array_insert(int, ccCheck, maxIndex, 1);
3131  }
3132  return maxIndex;
3133}
3134
3135
3136/**Function********************************************************************
3137
3138  Synopsis    [Create a sub-system with given latch-data-input nodes]
3139
3140  SideEffects []
3141
3142  SeeAlso     []
3143******************************************************************************/
3144static Part_Subsystem_t*
3145PartCreateSingleSubSystem(
3146  array_t *arrayOfNodes,
3147  Ntk_Network_t *network)
3148{
3149  int           i, j;
3150  char          *name;
3151  Ntk_Node_t    *node;
3152  st_table      *vertexNameTable;
3153  array_t       *arrayOfLatchNames;
3154  Part_Subsystem_t *sub;
3155
3156  if (array_n(arrayOfNodes) == 0 || arrayOfNodes == NIL(array_t)) {
3157    return NIL(Part_Subsystem_t);
3158  }
3159
3160  vertexNameTable = st_init_table(strcmp, st_strhash);
3161  arrayForEachItem(Ntk_Node_t *, arrayOfNodes, i, node) {
3162    arrayOfLatchNames = PartReadLatchNameFromLatchInput(network, node);
3163    arrayForEachItem(char *, arrayOfLatchNames, j, name) {
3164      st_insert(vertexNameTable, (char *)name, (char *)NULL);
3165    }
3166    array_free(arrayOfLatchNames);
3167  }
3168  sub = ALLOC(Part_Subsystem_t, 1);
3169  sub->vertexNameTable = vertexNameTable;
3170  sub->subsystemFanIn = NIL(array_t);
3171  sub->subsystemFanOut = NIL(array_t);
3172
3173  return sub;
3174}
3175
3176/**Function********************************************************************
3177
3178  Synopsis    [Gets Latch Name from Latch Data Input]
3179
3180  SideEffects []
3181
3182  SeeAlso     []
3183******************************************************************************/
3184static array_t *
3185PartReadLatchNameFromLatchInput(
3186  Ntk_Network_t *network,
3187  Ntk_Node_t *latchInput)
3188{
3189  lsGen         gen;
3190  Ntk_Node_t    *latch, *temp1;
3191  char          *latchName = NIL(char);
3192  array_t       *arrayOfLatchNames;
3193
3194  arrayOfLatchNames = array_alloc(char *, 0);
3195  Ntk_NetworkForEachLatch(network, gen, latch) {
3196    temp1 = Ntk_LatchReadDataInput(latch);
3197    if (temp1 == latchInput) {
3198      latchName = Ntk_NodeReadName(latch);
3199      array_insert_last(char *, arrayOfLatchNames, latchName);
3200    }
3201  } /* end of Ntk_NetworkForEachLatch */
3202
3203  return arrayOfLatchNames;
3204}
3205
3206/**Function********************************************************************
3207
3208  Synopsis    [Free array of array]
3209
3210  SideEffects []
3211
3212******************************************************************************/
3213static void
3214PartArrayOfArrayFree(
3215  array_t *arrayOfMatrix)
3216{
3217  array_t *arrayRow;
3218  int i;
3219
3220  arrayForEachItem(array_t *, arrayOfMatrix, i, arrayRow) {
3221    array_free(arrayRow);
3222  }
3223  array_free(arrayOfMatrix);
3224}
3225
3226/**Function********************************************************************
3227
3228  Synopsis    [Get matrix(i,j) from symetric matrix]
3229
3230  SideEffects []
3231
3232******************************************************************************/
3233static float
3234PartGetElementFromSymMatrix(
3235  float *matrix,
3236  int i,
3237  int j)
3238{
3239  int index;
3240
3241  if (i == j)
3242    return(0.0);
3243  if (i < j) {
3244    int tmp;
3245
3246    tmp = i;
3247    i = j;
3248    j = tmp;
3249  }
3250  index = i * (i - 1) / 2 + j;
3251  return(matrix[index]);
3252}
3253
3254/**Function********************************************************************
3255
3256  Synopsis    [Print array of array]
3257
3258  Description [If type is 0, arrayArray is float regular matrix. If type = 1,
3259   arrayArray is char type symertic matrix.]
3260
3261  SideEffects []
3262
3263******************************************************************************/
3264static void
3265PartPrintArrayArray(
3266  void *arrayArray,
3267  int nVertices,
3268  int type)
3269{
3270  int i, j;
3271  float num;
3272  int index;
3273
3274  if (type == 0) { /* numerical data * symetric matrix */
3275    for (i = 0; i < nVertices; i++) {
3276      for (j = 0; j < nVertices; j++) {
3277        num = PartGetElementFromSymMatrix((float *)arrayArray, i, j);
3278        fprintf(vis_stdout, "%4.3f ", num);
3279      }
3280      fprintf(vis_stdout, "\n");
3281    }
3282  } else if (type == 1) { /* char data & regular */
3283    for (i = 0; i < nVertices; i++) {
3284      for (j = 0; j < nVertices; j++) {
3285        index = i * nVertices + j;
3286        if (((char *)arrayArray)[index] == 1) {
3287          fprintf(vis_stdout, "1 ");
3288        } else {
3289          fprintf(vis_stdout, "0 ");
3290        }
3291      }
3292      fprintf(vis_stdout, "\n");
3293    }
3294  }
3295  fprintf(vis_stdout, "\n");
3296}
3297
3298/**Function********************************************************************
3299
3300  Synopsis    [Compare procedure for string comparison.]
3301
3302  Description [Compare procedure for string comparison.]
3303
3304  SideEffects []
3305
3306******************************************************************************/
3307static int
3308strCompare(
3309  const void *name1,
3310  const void *name2)
3311{
3312    return(strcmp(*(char **)name1, *(char **)name2));
3313} /* end of strCompare */
3314
3315/**Function********************************************************************
3316
3317  Synopsis    [Compare procedure for number comparison.]
3318
3319  Description [Compare procedure for number comparison.]
3320
3321  SideEffects []
3322
3323******************************************************************************/
3324static int
3325numCompare(
3326  const void *num1,
3327  const void *num2)
3328{
3329    return(*(int *)num1 > *(int *)num2);
3330} /* end of strCompare */
Note: See TracBrowser for help on using the repository browser.