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

Last change on this file since 64 was 14, checked in by cecile, 15 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.