/**CFile*********************************************************************** FileName [partGroup.c] PackageName [part] Synopsis [Routines for grouping vertices.] Description [The first method groups vertices based on the hierachy of the system. Normally, the hierachy is formed in the early phase of the design. We use this information to group latches. The method expects the high level description languages to BLIF conversion utilities such as vl2mv to preserve the original hierachy. The second method is explained in the following paper. H. Cho, G. D. Hachtel, E. Macii, B. Plessier, F. Somenzi," A Structural Approach to State Space Decomposition for Approximate Reachability Analysis," ICCD, pp.236-239, 1994. Traversal," EDAC. This method groups vertices based on the latch dependency(relation between latches) and the latch correlation(resemblance of latches in terms of the support variables.] Author [Woohyuk Lee, Jae-Young Jang] Copyright [Copyright (c) 1994-1996 The Regents of the Univ. of California. All rights reserved. Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software. IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.] ******************************************************************************/ #include "partInt.h" static char rcsid[] UNUSED = "$Id: partGroup.c,v 1.51 2005/04/28 14:15:50 fabio Exp $"; /*---------------------------------------------------------------------------*/ /* Constant declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Type declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Structure declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Variable declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Macro declarations */ /*---------------------------------------------------------------------------*/ /**AutomaticStart*************************************************************/ /*---------------------------------------------------------------------------*/ /* Static function prototypes */ /*---------------------------------------------------------------------------*/ static char * PartCreateDependencyMatrix(Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex); static float * PartCreateCorrelationMatrixFromSupport(Part_SubsystemInfo_t *partSubInfo); static float * PartCreateCorrelationMatrixFromBDD(Part_SubsystemInfo_t *partSubInfo); static float PartVertexComputeCorrelation(int index1, int index2, array_t *arrayOfInputSupportTable, Part_SubsystemInfo_t *partSubInfo); static array_t * PartVertexComputeAgreement(mdd_manager *mddMgr, int index1, int index2, array_t *arrayOfBddArray); static float * PartCreateAffinityMatrix(char *arrayOfConnectivity, float *arrayOfCorrelation, Part_SubsystemInfo_t *partSubInfo); static array_t * PartGetConnectedComponent(float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *indexToPtr); static void PartFindCC(int *next, int *ccId, array_t *arrayOfCCIndex, float *arrayOfAffinity, array_t *arrayOfFrom, Part_SubsystemInfo_t *PartSubInfo); static array_t * PartBreakingAggregating(array_t *arrayOfInit, float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex, char *arrayOfDependency); static array_t * PartBreakingBigConnectedComponent(array_t *arrayOfCC, array_t *ccCheck, array_t *arrayOfSeed, float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex); static array_t * PartAggregating(array_t *arrayOfSmall, float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex); static array_t * PartCreateSubSystemWithGroupIndex(Part_SubsystemInfo_t *partSubInfo, array_t *arrayOfLatchNames, array_t *arrayOfGroupIndex); static Ntk_Node_t * PartSelectCloseNode(Ntk_Node_t *seed, array_t *arrayOfCC, array_t *ccCheck, float *arrayOfAffinity, st_table *ptrToIndex); static int PartSelectCloseSeedIndex(Ntk_Node_t *variable, array_t *arrayOfSeed, float *arrayOfAffinity, st_table *ptrToIndex, array_t *seedFull, int bound); static Ntk_Node_t * PartSelectFarNode(Ntk_Node_t *seed, array_t *cc, array_t *ccCheck, float *arrayOfAffinity, st_table *ptrToIndex); static float * PartGetGroupMatrixRegular(array_t *arrayOfCluster, char *arrayOfGivenMatrix, st_table *ptrToIndex, int nVertices); static float * PartGetGroupMatrixSym(array_t *arrayOfCluster, float *arrayOfGivenMatrix, st_table *ptrToIndex); static int PartSelectCCIndexOfMinSupport(array_t *arrayOfSmall, array_t *ccCheck, Part_SubsystemInfo_t *partSubInfo); static Ntk_Node_t * PartSelectNodeOfMinSupport(array_t *cc, array_t *ccCheck, Part_SubsystemInfo_t *partSubInfo); static int PartSelectFarCCIndex(int seedIndex, array_t *arrayOfSmall, float *arrayOfGroupAff, Part_SubsystemInfo_t *partSubInfo, array_t *ccCheck); static int PartSelectCloseCCIndex(int seedIndex, array_t *arrayOfSmall, float *arrayOfGroupAff, array_t *ccCheck); static Part_Subsystem_t* PartCreateSingleSubSystem(array_t *arrayOfNodes, Ntk_Network_t *network); static array_t * PartReadLatchNameFromLatchInput(Ntk_Network_t *network, Ntk_Node_t *latchInput); static void PartArrayOfArrayFree(array_t *arrayOfMatrix); static float PartGetElementFromSymMatrix(float *matrix, int i, int j); static void PartPrintArrayArray(void *arrayOfMatrix, int nVertices, int type); static int strCompare(const void * name1, const void * name2); static int numCompare(const void * num1, const void * num2); static array_t *PartCreateSubsystemWithCTL(Part_SubsystemInfo_t *, array_t *, array_t *, boolean , boolean ); static array_t *PartCreateSubsystemWithCtlAndLtl(Part_SubsystemInfo_t *, array_t *, array_t *, array_t *, boolean , boolean, boolean ); /**AutomaticEnd***************************************************************/ /*---------------------------------------------------------------------------*/ /* Definition of exported functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [From the given latch data inputs, create array of sub-partitions.] Description [From the given latch data inputs, create array of sub-partitions of vertices. Latch data inputs are given as "latchDataInputNames" and includes subset of all latches in a system. Since the vertices are defined as the latch-input nodes, one may think of the process as grouping of latches in the network. "amc_sizeof_group" value may be set by the user by using the set command from the vis shell. The function uses this value to limit the number of vertices(latches) in a single group(subsystem). More vertices in a subsystem implies its representation is closer to the exact system. When the value is not given by the user, the default value of 8 vertices(latches) is used. The routine uses hierachical grouping method. That is, the latches in the same sub-processes(i.e. same .subckt in BLIF format), are grouped together whenever possible. Initial partition must be performed before executing this routine.] SideEffects [] SeeAlso [] ******************************************************************************/ array_t * Part_PartGroupVeriticesBasedOnHierarchy( Ntk_Network_t *network, array_t *latchDataInputNames) { graph_t *partition; array_t *arrayOfPartition = NIL(array_t); array_t *arrayOfGroups = NIL(array_t); array_t *arrayOfLatches = NIL(array_t); array_t *arrayOfLatchSort = NIL(array_t); st_table *vertexTable = NIL(st_table); int numOfVertex, reset; int i, j, k; char *numberOfVertexInGroup; char *flagValue; char *latchName, *name; st_table *latchDataInputNameTable; Part_Subsystem_t *testSubsystem; partition = Part_NetworkReadPartition(network); if (partition == NIL(graph_t)) { error_append("Network has no partition. Cannot create sub machines."); return (NIL(array_t)); } /* * Convert graph of vertices into array of table of vertices. */ numberOfVertexInGroup = Cmd_FlagReadByName("amc_sizeof_group"); if (numberOfVertexInGroup != NIL(char)) { numOfVertex = atoi(numberOfVertexInGroup); reset = atoi(numberOfVertexInGroup); } else { /* default value */ numOfVertex = 8; reset = 8; } latchDataInputNameTable = st_init_table(strcmp, st_strhash); arrayForEachItem(char *, latchDataInputNames, i, name) { st_insert(latchDataInputNameTable, (char *)name, (char *)NULL); } /* * In the first phase, group latches by the processes. * That is, group latches that are within same sub-circuit. */ arrayOfGroups = array_alloc(array_t *, 0); { Ntk_Node_t *latch; lsGen gen; char *groupName = util_strsav(" "); arrayOfLatchSort = array_alloc(char *, 0); Ntk_NetworkForEachLatch(network, gen, latch) { Ntk_Node_t *latchInput = Ntk_LatchReadDataInput(latch); char *latchInputName = Ntk_NodeReadName(latchInput); vertex_t *vertex = Part_PartitionFindVertexByName(partition, latchInputName); if ((vertex != NIL(vertex_t)) && (st_lookup(latchDataInputNameTable, latchInputName, NIL(char *)))) { array_insert_last(char *, arrayOfLatchSort, Ntk_NodeReadName(latch)); } } array_sort(arrayOfLatchSort, strCompare); arrayForEachItem(char *, arrayOfLatchSort, i, latchName) { char *suffixLatchName, *currentGroupName; suffixLatchName = util_strsav(latchName); /* Extract out group name into the string "groupName" and leave rest in suffixLatchName. */ currentGroupName = strtok(suffixLatchName, "."); if (strcmp(groupName, currentGroupName)) { if (strcmp(groupName, " ")) { array_insert_last(array_t *, arrayOfGroups, arrayOfLatches); } FREE(groupName); groupName = util_strsav(currentGroupName); arrayOfLatches = array_alloc(char *, 0); } FREE(currentGroupName); array_insert_last(char *, arrayOfLatches, latchName); } FREE(groupName); } array_free(arrayOfLatchSort); st_free_table(latchDataInputNameTable); /* Fill in the last arrayOfLatches */ array_insert_last(array_t *, arrayOfGroups, arrayOfLatches); /* * In the second phase, further break latch group into * smaller group size according to the "amc_sizeof_group". */ arrayOfPartition = array_alloc(Part_Subsystem_t *, 0); arrayForEachItem(array_t *, arrayOfGroups, k, arrayOfLatches) { char *latchName; int numOfLatches = array_n(arrayOfLatches); arrayForEachItem(char *, arrayOfLatches, i, latchName) { if (numOfVertex == reset) vertexTable = st_init_table(strcmp, st_strhash); st_insert(vertexTable, latchName, (char *)NULL); if ((numOfVertex == 1) || (numOfLatches == i+1)) { /* testSubsystem freed by calling function */ testSubsystem = ALLOC(Part_Subsystem_t, 1); testSubsystem->vertexNameTable = vertexTable; testSubsystem->subsystemFanIn = NIL(array_t); testSubsystem->subsystemFanOut = NIL(array_t); array_insert_last(Part_Subsystem_t *, arrayOfPartition, testSubsystem); numOfVertex = reset; } else numOfVertex--; } /* End of arrayForEachItem(arrayOfLatches) */ } /* End of arrayForEachItem(arrayOfGroups) */ /* Free arrayOfGroups, arrayOfLatches */ arrayForEachItem(array_t *, arrayOfGroups, i, arrayOfLatches) { array_free(arrayOfLatches); } array_free(arrayOfGroups); /* * Currently this function is used only from amc package. * When the function gets popular use parameter passing rather that this * ugly method. */ flagValue = Cmd_FlagReadByName("amc_use_MBM"); if (flagValue != NIL(char)) { array_t *latchNodeArray; array_t *faninNodeArray; array_t *faninLatchArray; /* * Fill in the subsystem dependencies using the latch dependencies. */ arrayForEachItem(Part_Subsystem_t *, arrayOfPartition, i, testSubsystem) { array_t *fanInArray = array_alloc(int, 0); st_table *vertexTable = testSubsystem->vertexNameTable; st_generator *stGen; char *latchName; Ntk_Node_t *latchNode; latchNodeArray = array_alloc(Ntk_Node_t *, 0); faninLatchArray = array_alloc(Ntk_Node_t *, 0); /* Convert table of latch names into array of latch nodes */ st_foreach_item(vertexTable, stGen, &latchName, NIL(char *)) { latchNode = Ntk_NetworkFindNodeByName(network, latchName); array_insert_last(Ntk_Node_t *, latchNodeArray, latchNode); } /* Find the transitive fanin nodes */ faninNodeArray = Ntk_NodeComputeCombinationalSupport(network, latchNodeArray, FALSE); /* Find the transitive fanin latches from the fanin nodes */ if (array_n(faninNodeArray) != 0) { int x; arrayForEachItem(Ntk_Node_t *, faninNodeArray, x, latchNode) { if (Ntk_NodeTestIsLatch(latchNode) == TRUE) { array_insert_last(Ntk_Node_t *, faninLatchArray, latchNode); } } } /* Find the fanin subsystems */ if (array_n(faninLatchArray) != 0) { Part_Subsystem_t *scanSubsystem; int y; arrayForEachItem(Part_Subsystem_t *, arrayOfPartition, j, scanSubsystem) { /* Scan subsystems that aren't the currently considered subsytem */ st_table *otherVertexTable = scanSubsystem->vertexNameTable; if (i != j) { arrayForEachItem(Ntk_Node_t *, faninLatchArray, y, latchNode) { char *latchName = Ntk_NodeReadName(latchNode); if (st_lookup(otherVertexTable, latchName, NIL(char *))) { array_insert_last(int, fanInArray, j); break; } } /* end of arrayForEachItem(Ntk_Node_t *) */ } /* end of if (i != j) */ } } /* end of if (array_n(faninLatchArray) != 0) */ /* Update fanInArray into the subsystem */ testSubsystem->subsystemFanIn = fanInArray; array_free(latchNodeArray); array_free(faninNodeArray); array_free(faninLatchArray); } /* end of arrayForEachItem(Part_Subsystem_t *) */ } /* end of if (!flagValue) */ /* * Currently this function is used only from amc package. * When the function gets popular use parameter passing rather that this * ugly method. */ flagValue = Cmd_FlagReadByName("amc_use_MBM"); if (flagValue != NIL(char)) { st_table *fanOutDependencies = Ntk_NetworkComputeLatchDependencies(network); /* * Fill in the fanout dependencies of subsystems. */ arrayForEachItem(Part_Subsystem_t *, arrayOfPartition, i, testSubsystem) { array_t *fanOutArray = array_alloc(int, 0); st_table *vertexTable = testSubsystem->vertexNameTable; st_generator *stGen; char *latchName; st_table *everyFanOuts = st_init_table(st_ptrcmp, st_ptrhash); /* * For the latches in this subsystem, * find all latches that transitively fanouts from the latches * inside this subsystem. Store it in a hash table, "everyFanOuts". */ st_foreach_item(vertexTable, stGen, &latchName, NIL(char *)) { Ntk_Node_t *latchNode; lsList fanOutLatchList; lsGen gen; lsGeneric data; latchNode = Ntk_NetworkFindNodeByName(network, latchName); st_lookup(fanOutDependencies, latchNode, &fanOutLatchList); /* Obtain all fanout latches coming from latches of this subsystem */ gen = lsStart(fanOutLatchList); while (lsNext(gen, &data, LS_NH) == LS_OK) { st_insert(everyFanOuts, data, NULL); } (void) lsFinish(gen); lsDestroy(fanOutLatchList, (void (*) (lsGeneric)) NULL); } /* * Scan subsystems that aren't the currently considered subsytem. */ { Part_Subsystem_t *scanSubsystem; arrayForEachItem(Part_Subsystem_t *, arrayOfPartition, j, scanSubsystem) { st_table *otherVertexTable = scanSubsystem->vertexNameTable; if (i != j) { st_generator *stGen; Ntk_Node_t *latchNode; st_foreach_item(everyFanOuts, stGen, &latchNode, NULL) { char *latchName = Ntk_NodeReadName(latchNode); if (st_lookup(otherVertexTable, latchName, NIL(char *))) { array_insert_last(int, fanOutArray, j); break; } } /* end of */ } /* end of if (i != j) */ } /* end of arrayForEachItem(Part_Subsystem_t *) */ } st_free_table(everyFanOuts); /* Update fanOutArray into the subsystem */ testSubsystem->subsystemFanOut = fanOutArray; } /* end of arrayForEachItem(Part_Subsystem_t *) */ /* Free dependency hash table */ st_free_table(fanOutDependencies); } return(arrayOfPartition); } /**Function******************************************************************** Synopsis [Create sub-systems based on latch relation] Description [Create sub-systems based on latch dependency, connectivity, correlation, and affinity. If arrayOfFunctionNames(latch data inputs) is given, only those nodes are considered to make sub-systems. If arrayOfGroup- Index(Ii) is given with arrayOfFunctionNames(Fi), Fi is put in Ii'th sub-system.] SideEffects [] ******************************************************************************/ array_t * Part_PartCreateSubsystems( Part_SubsystemInfo_t *subInfo, array_t *arrayOfLatchNames, array_t *arrayOfGroupIndex) { if (subInfo->verbosity > 0) { if (arrayOfLatchNames != NIL(array_t)) { fprintf(vis_stdout, "Grouping: Array of latch data is given.\n"); fprintf(vis_stdout, "Grouping: All latches related to the array will be grouped.\n"); } else if (Part_NetworkReadPartition(subInfo->network) == NIL(graph_t)) { fprintf(vis_stdout, "Grouping: Network has no partition.\n"); fprintf(vis_stdout, "Grouping: All latches in network will be grouped.\n"); } else { fprintf(vis_stdout, "Grouping: Network has a partition.\n"); fprintf(vis_stdout, "Grouping: All latches in partition will be grouped.\n"); } } return(PartCreateSubsystem(subInfo, arrayOfLatchNames, arrayOfGroupIndex)); } /**Function******************************************************************** Synopsis [Create sub-partitions based on latch relation] Description [Create sub-partition based on latch dependency, connectivity, correlation, and affinity. The first sub-system includes latches in CTL formula, and latches with strong affinity are put in next sub-system. If dynamicIncrease is TRUE, the first sub-system which has stringest realtion with given formula and the second sub-system with all other latches are returned.] SideEffects [] ******************************************************************************/ array_t * Part_PartCreateSubsystemsWithCTL( Part_SubsystemInfo_t *subInfo, array_t *ctlArray, array_t *fairArray, boolean dynamicIncrease, boolean dynamicAndDependency) { if (subInfo->verbosity > 0 ){ fprintf(vis_stdout,"Grouping: All latches related to "); fprintf(vis_stdout,"the CTL will be grouped.\n"); } return (PartCreateSubsystemWithCTL(subInfo, ctlArray, fairArray, dynamicIncrease,dynamicAndDependency)); } /**Function******************************************************************** Synopsis [Create sub-partitions based on latch relation] Description [Create sub-partition based on latch dependency, connectivity, correlation, and affinity. The first sub-system includes latches in CTL formula, and latches with strong affinity are put in next sub-system. If dynamicIncrease is TRUE, the first sub-system which has stringest realtion with given formula and the second sub-system with all other latches are returned.] SideEffects [] ******************************************************************************/ array_t * Part_PartCreateSubsystemsWithCtlAndLtl( Part_SubsystemInfo_t *subInfo, array_t *ctlArray, array_t *ltlArray, array_t *fairArray, boolean dynamicIncrease, boolean dynamicAndDependency, boolean strictBound) { if (subInfo->verbosity > 0 ){ fprintf(vis_stdout,"Grouping: All latches related to "); fprintf(vis_stdout,"the CTL/LTL/fairness will be grouped.\n"); } return (PartCreateSubsystemWithCtlAndLtl(subInfo, ctlArray, ltlArray, fairArray, dynamicIncrease, dynamicAndDependency, strictBound)); } /**Function******************************************************************** Synopsis [Read the table attached to a partitioned subsystem.] SideEffects [] ******************************************************************************/ st_table * Part_PartitionSubsystemReadVertexTable( Part_Subsystem_t *partitionedSubsystem) { return(partitionedSubsystem->vertexNameTable); } /**Function******************************************************************** Synopsis [Read fan-in array attached to partitioned subsystem] SideEffects [] ******************************************************************************/ array_t * Part_PartitionSubsystemReadFanIn( Part_Subsystem_t *partitionedSubsystem) { return(partitionedSubsystem->subsystemFanIn); } /**Function******************************************************************** Synopsis [Read fan-out array attached to partitioned subsystem] SideEffects [] ******************************************************************************/ array_t * Part_PartitionSubsystemReadFanOut( Part_Subsystem_t *partitionedSubsystem) { return(partitionedSubsystem->subsystemFanOut); } /**Function******************************************************************** Synopsis [Initialize info structure for partitioning subsystem] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ Part_SubsystemInfo_t * Part_PartitionSubsystemInfoInit( Ntk_Network_t *network) { Part_SubsystemInfo_t *partSubInfo; partSubInfo = ALLOC(Part_SubsystemInfo_t, 1); /* * set values as defaults */ partSubInfo->network = network; partSubInfo->arrayOfVertex = NIL(array_t); partSubInfo->numberOfVertex = 0; partSubInfo->partBM = Part_BFix_v; partSubInfo->con_factor = PART_SUB_CON_FACTOR; partSubInfo->cor_factor = PART_SUB_COR_FACTOR; partSubInfo->aff_factor = PART_SUB_AFF_FACTOR; partSubInfo->threshold = 0.0; partSubInfo->bound = 8; partSubInfo->verbosity = 0; partSubInfo->corMethod = Part_CorrelationDefault; partSubInfo->dupLatchTable = st_init_table(strcmp, st_strhash); partSubInfo->latchNameTable = st_init_table(strcmp, st_strhash); return(partSubInfo); } /**Function******************************************************************** Synopsis [Free info structure for partitioning subsystem] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ void Part_PartitionSubsystemInfoFree( Part_SubsystemInfo_t *partSubInfo) { st_generator *stGen; char *latchInputName; array_t *latchNames; array_free(partSubInfo->arrayOfVertex); st_foreach_item(partSubInfo->dupLatchTable, stGen, &latchInputName, &latchNames) { array_free(latchNames); } st_free_table(partSubInfo->dupLatchTable); st_free_table(partSubInfo->latchNameTable); FREE(partSubInfo); } /**Function******************************************************************** Synopsis [Free subsystem structure for partitioning subsystem] SideEffects [] SeeAlso [Part_Subsystem] ******************************************************************************/ void Part_PartitionSubsystemFree( Part_Subsystem_t *partSubsystem) { st_free_table(partSubsystem->vertexNameTable); array_free(partSubsystem->subsystemFanIn); array_free(partSubsystem->subsystemFanOut); FREE(partSubsystem); } /**Function******************************************************************** Synopsis [Set breaking method of subsystem info] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ void Part_PartitionSubsystemInfoSetBreakingMethod( Part_SubsystemInfo_t *subInfo, Part_BMethod bMethod) { subInfo->partBM = bMethod; } /**Function******************************************************************** Synopsis [Set bound of subsystem info] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ void Part_PartitionSubsystemInfoSetBound( Part_SubsystemInfo_t *subInfo, int bound) { subInfo->bound = bound; } /**Function******************************************************************** Synopsis [Set threshold of subsystem info] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ void Part_PartitionSubsystemInfoSetThreshold( Part_SubsystemInfo_t *subInfo, float threshold) { subInfo->threshold = threshold; } /**Function******************************************************************** Synopsis [Set verbosity of subsystem info] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ void Part_PartitionSubsystemInfoSetVerbosity( Part_SubsystemInfo_t *subInfo, int verbosity) { subInfo->verbosity = verbosity; } /**Function******************************************************************** Synopsis [Set method for correlation] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ void Part_PartitionSubsystemInfoSetCorrelationMethod( Part_SubsystemInfo_t *subInfo, Part_CMethod corMethod) { subInfo->corMethod = corMethod; } /**Function******************************************************************** Synopsis [Set affinity factor] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ void Part_PartitionSubsystemInfoSetAffinityFactor( Part_SubsystemInfo_t *subInfo, float affinity) { subInfo->aff_factor = affinity; } /**Function******************************************************************** Synopsis [Create a sub-system with given latch data input in arrayOfNodes] SideEffects [] SeeAlso [] ******************************************************************************/ Part_Subsystem_t* Part_PartCreateSingleSubSystem( array_t *arrayOfNodes, Ntk_Network_t *network) { return PartCreateSingleSubSystem(arrayOfNodes, network); } /*---------------------------------------------------------------------------*/ /* Definition of internal functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Create an array of partitioned subsystems from array of latches] Description [This is a main function to get subsystems. At first, look at the circuit topology and next state functions, get the latch affinity. Find the connected components to cluster latches which are stronly dependent or correlated on each other. After that, divide clusters bigger than the given bound and aggregate smaller clusters. This function is called with network and partition graph. If arrayOfFunctionNames are not NULL, this function generates sub-system with those latch-data-inputs in that array. If arrayOfGroupIndex is not NILL and size of this array is same as the size of arrayOfFunctionNames, this function uses these two arrays as predefined grouping information and creates sub-systems.] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ array_t * PartCreateSubsystem( Part_SubsystemInfo_t *partSubInfo, array_t *arrayOfLatchNames, array_t *arrayOfGroupIndex) { char *arrayOfDependency = NIL(char); float *arrayOfCorrelation = NIL(float); float *arrayOfAffinity; array_t *arrayOfInit; st_table *indexToPtrInfo; /* index to pointer table */ st_table *ptrToIndexInfo; /* pointer to index table */ array_t *result; Ntk_Node_t *node; char *functionName; char *latchName; lsList vertexList; lsGen gen; int i; vertex_t *vertex; array_t *initArray; array_t *arrayOfVertex; Ntk_Network_t *network = partSubInfo->network; graph_t *partition = Part_NetworkReadPartition(network); long initialTime = 0; long finalTime; if (partition == NIL(graph_t)) { if (partSubInfo->corMethod == Part_CorrelationWithBDD) { error_append("Network has no partition. Correlation "); error_append("with MDD operation can not be used.\n"); return NIL(array_t); } } if (arrayOfGroupIndex != NIL(array_t)) { if (!arrayOfLatchNames) { error_append("Latch name array is not given.\n"); result = NIL(array_t); } if (array_n(arrayOfLatchNames) != array_n(arrayOfGroupIndex)) { error_append("Given function names and index have different size.\n"); result = NIL(array_t); } } if (arrayOfLatchNames && arrayOfGroupIndex) { result = PartCreateSubSystemWithGroupIndex(partSubInfo, arrayOfLatchNames, arrayOfGroupIndex); return result; } arrayOfVertex = array_alloc(Ntk_Node_t *, 0); /* * Convert graph vertices into array of array of vertices. */ if (partSubInfo->verbosity > 2) { fprintf(vis_stdout, "\nGroupting: List of latches\n"); fprintf(vis_stdout, "----------------------------\n"); } if (arrayOfLatchNames != NIL(array_t)) { Ntk_Node_t *latchNode, *latchInputNode; char *otherLatchName; array_t *latchNameArray; arrayForEachItem(char *, arrayOfLatchNames, i, latchName) { latchNode = Ntk_NetworkFindNodeByName(network, latchName); latchInputNode = Ntk_LatchReadDataInput(latchNode); functionName = Ntk_NodeReadName(latchInputNode); if (partSubInfo->verbosity > 2) fprintf(vis_stdout, "%s\n", latchName); if (st_lookup(partSubInfo->latchNameTable, functionName, &otherLatchName)) { if (st_lookup(partSubInfo->dupLatchTable, functionName, &latchNameArray)) { array_insert_last(char *, latchNameArray, latchName); } else { latchNameArray = array_alloc(char *, 0); array_insert_last(char *, latchNameArray, otherLatchName); array_insert_last(char *, latchNameArray, latchName); st_insert(partSubInfo->dupLatchTable, (char *)functionName, (char *)latchNameArray); } continue; } st_insert(partSubInfo->latchNameTable, (char *)functionName, (char *)latchName); array_insert_last(Ntk_Node_t *, arrayOfVertex, latchInputNode); } } else if (partition == NIL(graph_t)) { Ntk_NetworkForEachNode(network, gen, node) { if (Ntk_NodeTestIsLatchDataInput(node)) { array_insert_last(Ntk_Node_t *, arrayOfVertex, node); arrayOfLatchNames = PartReadLatchNameFromLatchInput(network, node); functionName = Ntk_NodeReadName(node); latchName = array_fetch(char *, arrayOfLatchNames, 0); st_insert(partSubInfo->latchNameTable, (char *)functionName, (char *)latchName); if (array_n(arrayOfLatchNames) > 1) { st_insert(partSubInfo->dupLatchTable, (char *)functionName, (char *)arrayOfLatchNames); if (partSubInfo->verbosity > 2) { char *nname; arrayForEachItem(char *, arrayOfLatchNames, i, nname) { fprintf(vis_stdout, "%s\n", nname); } } } else { array_free(arrayOfLatchNames); if (partSubInfo->verbosity > 2) fprintf(vis_stdout, "%s\n", latchName); } } } /* End of Ntk_NetworkForEachNode */ } else { vertexList = g_get_vertices(partition); lsForEachItem(vertexList, gen, vertex) { char *nodeName = PartVertexReadName(vertex); node = Ntk_NetworkFindNodeByName(network, nodeName); if (Ntk_NodeTestIsLatchDataInput(node)) { array_insert_last(Ntk_Node_t *, arrayOfVertex, node); arrayOfLatchNames = PartReadLatchNameFromLatchInput(network, node); functionName = Ntk_NodeReadName(node); latchName = array_fetch(char *, arrayOfLatchNames, 0); st_insert(partSubInfo->latchNameTable, (char *)functionName, (char *)latchName); if (array_n(arrayOfLatchNames) > 1) { st_insert(partSubInfo->dupLatchTable, (char *)functionName, (char *)arrayOfLatchNames); if (partSubInfo->verbosity > 2) { char *nname; arrayForEachItem(char *, arrayOfLatchNames, i, nname) { fprintf(vis_stdout, "%s\n", nname); } } } else { array_free(arrayOfLatchNames); if (partSubInfo->verbosity > 2) fprintf(vis_stdout, "%s\n", latchName); } } } } if (partSubInfo->verbosity > 2) { fprintf(vis_stdout, "Total # of latch data input = %d\n", array_n(arrayOfVertex)); } partSubInfo->arrayOfVertex = arrayOfVertex; partSubInfo->numberOfVertex = array_n(arrayOfVertex); /* * table from index to pointer and pointer to index */ indexToPtrInfo = st_init_table(st_numcmp, st_numhash); ptrToIndexInfo = st_init_table(st_ptrcmp, st_ptrhash); arrayForEachItem(Ntk_Node_t *, partSubInfo->arrayOfVertex, i, node) { st_insert(indexToPtrInfo, (char *)(long)i, (char *)node); st_insert(ptrToIndexInfo, (char *)node, (char *)(long)i); } /* * get a dependency matrix */ if (partSubInfo->aff_factor > 0.0) { if (partSubInfo->verbosity > 0) initialTime = util_cpu_time(); arrayOfDependency = PartCreateDependencyMatrix(partSubInfo, ptrToIndexInfo); if (partSubInfo->verbosity > 0) { finalTime = util_cpu_time(); fprintf(vis_stdout, "time for computing dependency = %g\n", (double)(finalTime - initialTime) / 1000.0); } } /* * get a correlation matrix */ if (partSubInfo->aff_factor != 1.0) { if (partSubInfo->verbosity > 0) initialTime = util_cpu_time(); if (partSubInfo->corMethod == Part_CorrelationWithBDD) arrayOfCorrelation = PartCreateCorrelationMatrixFromBDD(partSubInfo); else if ((partSubInfo->corMethod == Part_CorrelationWithSupport) || (partSubInfo->corMethod == Part_CorrelationDefault)) { arrayOfCorrelation = PartCreateCorrelationMatrixFromSupport(partSubInfo); } if (partSubInfo->verbosity > 0) { finalTime = util_cpu_time(); fprintf(vis_stdout, "time for computing correlation = %g\n", (double)(finalTime - initialTime) / 1000.0); } } if (partSubInfo->verbosity > 2) { if (arrayOfDependency) { fprintf(vis_stdout, "\nGrouping: Dependency\n"); fprintf(vis_stdout, "--------------------\n"); PartPrintArrayArray(arrayOfDependency, partSubInfo->numberOfVertex, 1); } if (arrayOfCorrelation) { fprintf(vis_stdout, "\nGrouping: Correlation\n"); fprintf(vis_stdout, "---------------------\n"); PartPrintArrayArray(arrayOfCorrelation, partSubInfo->numberOfVertex, 0); } } /* * get an affinity matrix, arrayOfCorrelation is freed. */ if (partSubInfo->verbosity > 0) initialTime = util_cpu_time(); arrayOfAffinity = PartCreateAffinityMatrix(arrayOfDependency, arrayOfCorrelation, partSubInfo); FREE(arrayOfCorrelation); if (partSubInfo->verbosity > 0) { finalTime = util_cpu_time(); fprintf(vis_stdout, "time for computing affinity = %g\n", (double)(finalTime - initialTime) / 1000.0); } if (partSubInfo->verbosity > 2) { fprintf(vis_stdout, "\nGrouping: Affinity\n"); fprintf(vis_stdout, "------------------\n"); PartPrintArrayArray(arrayOfAffinity, partSubInfo->numberOfVertex, 0); } /* * get an initial subsysytm by searching for connected component in * vertex affinity matrix */ if (partSubInfo->verbosity > 0) initialTime = util_cpu_time(); arrayOfInit = PartGetConnectedComponent(arrayOfAffinity, partSubInfo, indexToPtrInfo); if (partSubInfo->verbosity > 0) { finalTime = util_cpu_time(); fprintf(vis_stdout, "time for computing connected component = %g\n", (double)(finalTime - initialTime) / 1000.0); } if (partSubInfo->verbosity > 2) { fprintf(vis_stdout, "\nGrouping: Initial connected component size\n"); fprintf(vis_stdout, "------------------------------------------\n\n"); arrayForEachItem(array_t *, arrayOfInit, i, initArray) { fprintf(vis_stdout, "%3d group: size = %d\n", i, array_n(initArray)); } } /* * get a final subsystem by breaking big connected components and * aggregating small connected components. */ if (partSubInfo->verbosity > 0) initialTime = util_cpu_time(); result = PartBreakingAggregating(arrayOfInit, arrayOfAffinity, partSubInfo, ptrToIndexInfo, arrayOfDependency); if (partSubInfo->verbosity > 0) { finalTime = util_cpu_time(); fprintf(vis_stdout, "time for breaking and aggregating = %g\n", (double)(finalTime - initialTime) / 1000.0); } array_free(arrayOfInit); if (partSubInfo->verbosity >= 2) { Part_Subsystem_t *sub; char *latchName; st_generator *stGen; fprintf(vis_stdout, "\nGrouping: List of subsytem latches\n"); fprintf(vis_stdout, "----------------------------------\n\n"); arrayForEachItem(Part_Subsystem_t *, result, i, sub) { fprintf(vis_stdout, "[Subsystem %3d]\n", i); st_foreach_item(sub->vertexNameTable, stGen, &latchName, NIL(char *)) { fprintf(vis_stdout, "%s\n", latchName); } fprintf(vis_stdout, "\n"); } } if (partSubInfo->verbosity >= 1) { (void)fprintf(vis_stdout, "\nGrouping: grouping options\n"); (void)fprintf(vis_stdout, "--------------------------\n\n"); (void)fprintf(vis_stdout, "Threshold : %f\n", partSubInfo->threshold); (void)fprintf(vis_stdout, "bound : %d\n", partSubInfo->bound); (void)fprintf(vis_stdout, "connectivity factor: %f\n", partSubInfo->con_factor); (void)fprintf(vis_stdout, "correlation factor : %f\n", partSubInfo->cor_factor); (void)fprintf(vis_stdout, "affinity factor : %f\n", partSubInfo->aff_factor); (void)fprintf(vis_stdout, "\n"); } st_free_table(indexToPtrInfo); st_free_table(ptrToIndexInfo); FREE(arrayOfDependency); FREE(arrayOfAffinity); return result; } /*---------------------------------------------------------------------------*/ /* Definition of static functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Create an array of subsystems from properties] Description [The first couple of sub-systems include nodes which are in CTL formulae. A node with biggest affinity is included in the next sub-system until the number of nodes is less than bound. If dynamicIncrease is FALSE, get all sub-systems with all support variables of CTL formula. If TRUE, the first sub-system includes variables in CTL and the second sub-system includes others.] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ static array_t * PartCreateSubsystemWithCTL( Part_SubsystemInfo_t *partSubInfo, array_t *ctlArray, array_t *fairArray, boolean dynamicIncrease, boolean dynamicAndDependency) { return PartCreateSubsystemWithCtlAndLtl(partSubInfo, ctlArray, NIL(array_t), fairArray, dynamicIncrease, dynamicAndDependency, FALSE); } /**Function******************************************************************** Synopsis [Create an array of subsystems from properties] Description [The first couple of sub-systems include nodes which are in CTL/LTL/fairness formulae. A node with biggest affinity is included in the next sub-system until the number of nodes is less than bound. If dynamicIncrease is FALSE, get all sub-systems with all support variables of CTL formula. If TRUE, the first sub-system includes variables in CTL and the second sub-system includes others. When strictBound is FALSE, all the latches appearing in the formulae are put into the first subsystem -- making it possibly larger than the bound. Otherwise, no subsystem will have more than 'bound' latches.] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ static array_t * PartCreateSubsystemWithCtlAndLtl( Part_SubsystemInfo_t *partSubInfo, array_t *ctlArray, array_t *ltlArray, array_t *fairArray, boolean dynamicIncrease, boolean dynamicAndDependency, boolean strictBound) { int i, j, index, maxSize, maxIndex, leftNodes, numSeed; array_t *result = NIL(array_t); Ntk_Network_t *network = partSubInfo->network; lsList latchNodeList; lsGen gen; char *arrayOfDependency = NIL(char); float *arrayOfCorrelation = NIL(float); float *arrayOfAffinity = NIL(float); array_t *arrayTemp = NIL(array_t); array_t *arrayOfVertex = NIL(array_t); array_t *arrayOfLatchNames = NIL(array_t); st_table *vertexToArrayOfLatchNames = NIL(st_table); array_t *arrayOfLatchNodeName = NIL(array_t); Ntk_Node_t *node = NIL(Ntk_Node_t); float affinity; char *name = NIL(char); st_table *indexToPtrInfo = NIL(st_table); st_table *ptrToIndexInfo = NIL(st_table); array_t *check = NIL(array_t); array_t *tempCheck = NIL(array_t); array_t *tempCC = NIL(array_t); st_generator *stGen = NIL(st_generator); array_t *arrayOfSeed = NIL(array_t); Ntk_Node_t *seedLast = NIL(Ntk_Node_t); Ntk_Node_t *seedNext = NIL(Ntk_Node_t); array_t *arrayOfBreak = NIL(array_t); array_t *arrayOfNodes = NIL(array_t); array_t *arrayOfIndex = NIL(array_t); st_table *dataInputNodes = NIL(st_table); Part_Subsystem_t *sub = NIL(Part_Subsystem_t); int numIncluded; float prevAffinity; if (ctlArray == NIL(array_t) && ltlArray == NIL(array_t)){ return NIL(array_t); } /* * arrayOfLatchNodeName <-- COI latch names */ latchNodeList = lsCreate(); PartGetLatchListFromCtlAndLtl(network, ctlArray, ltlArray, fairArray, latchNodeList, FALSE); arrayOfLatchNodeName = array_alloc(Ntk_Node_t *, 0); lsForEachItem(latchNodeList, gen, node){ array_insert_last(char *, arrayOfLatchNodeName, Ntk_NodeReadName(node)); } lsDestroy(latchNodeList, (void (*)(lsGeneric))0); /* * arrayOfVertex <-- COI latch datainput nodes */ array_sort(arrayOfLatchNodeName, strCompare); arrayOfVertex = array_alloc(Ntk_Node_t *, 0); vertexToArrayOfLatchNames = st_init_table(st_ptrcmp, st_ptrhash); /* multiple latch may correspond to the same dataInput */ arrayForEachItem(char *, arrayOfLatchNodeName, i, name){ node = Ntk_NetworkFindNodeByName(network, name); node = Ntk_LatchReadDataInput(node); if (!st_lookup(vertexToArrayOfLatchNames, node, &arrayOfLatchNames) ) { arrayOfLatchNames = array_alloc(char *, 0); array_insert_last(char *, arrayOfLatchNames, name); st_insert(vertexToArrayOfLatchNames, node, arrayOfLatchNames); array_insert_last(Ntk_Node_t *, arrayOfVertex, node); }else array_insert_last(char *, arrayOfLatchNames, name); } /* * Print a list of latch names. */ if (partSubInfo->verbosity >= 2){ fprintf(vis_stdout,"\nGroupting: List of latches\n"); fprintf(vis_stdout,"------------------------\n\n"); arrayForEachItem(char *, arrayOfLatchNodeName, i, name){ fprintf(vis_stdout,"%s\n", name); } } array_free(arrayOfLatchNodeName); /* * dataInputNodes <-- formulae latch datainput nodes */ latchNodeList = lsCreate(); PartGetLatchListFromCtlAndLtl(network, ctlArray, ltlArray, fairArray, latchNodeList, TRUE); dataInputNodes = st_init_table( st_ptrcmp, st_ptrhash ); lsForEachItem(latchNodeList, gen, node) { Ntk_Node_t *dataInputNode = Ntk_LatchReadDataInput(node); if (!st_is_member(dataInputNodes, (char *)dataInputNode)) st_insert(dataInputNodes, (char *)dataInputNode, NIL(char)); } lsDestroy(latchNodeList, (void (*)(lsGeneric))0); /* * table from index to pointer and pointer to index */ partSubInfo->arrayOfVertex = arrayOfVertex; partSubInfo->numberOfVertex = array_n(arrayOfVertex); indexToPtrInfo = st_init_table(st_numcmp, st_numhash); ptrToIndexInfo = st_init_table(st_ptrcmp, st_ptrhash); arrayForEachItem(Ntk_Node_t *, partSubInfo->arrayOfVertex, i, node){ st_insert(indexToPtrInfo, (char *)(long)i, (char *)node); st_insert(ptrToIndexInfo, (char *)node, (char *)(long)i); } check = array_alloc(int, partSubInfo->numberOfVertex); for(i=0;inumberOfVertex;i++){ array_insert(int, check, i, 0); } leftNodes = partSubInfo->numberOfVertex; arrayOfIndex = array_alloc(int, st_count(dataInputNodes)); result = array_alloc(Part_Subsystem_t *, 0); /* * If (1) number of formula nodes is smaller than bound, or (2) * strictBound is FALSE, or (3) dynamicIncrease is TRUE, create a * subsystem and put all formula nodes in the sub-system */ if ( !strictBound || st_count(dataInputNodes) <= partSubInfo->bound || dynamicIncrease ) { int numNodesInFirstSubsys; if (!strictBound || st_count(dataInputNodes) <= partSubInfo->bound) numNodesInFirstSubsys = st_count(dataInputNodes); else numNodesInFirstSubsys = partSubInfo->bound; arrayOfNodes = array_alloc(Ntk_Node_t *, st_count(dataInputNodes)); i=0; st_foreach_item(dataInputNodes, stGen, &node, NULL) { if (i == numNodesInFirstSubsys) break; st_lookup_int(ptrToIndexInfo, node, &index); array_insert(int, check, index, 1); array_insert(int, arrayOfIndex, i, index); array_insert(Ntk_Node_t *, arrayOfNodes, i++, node); } sub = PartCreateSingleSubSystem(arrayOfNodes, network); leftNodes -= array_n(arrayOfNodes); array_insert_last(Part_Subsystem_t *, result, sub); array_free(arrayOfNodes); if (dynamicIncrease) { /* the second subsystem <-- remaining latches in dataInputTable * the thrid subsystem <-- other COI latches */ if ( dynamicAndDependency ) { if ( st_count(dataInputNodes) == numNodesInFirstSubsys ) array_insert_last(Part_Subsystem_t *, result, NIL(Part_Subsystem_t)); else { arrayOfNodes = array_alloc(Ntk_Node_t *, 0); i=0; st_foreach_item(dataInputNodes, stGen, &node, NULL) { st_lookup_int(ptrToIndexInfo, node, &index); if (array_fetch(int, check, index)==0){ array_insert(int, check, index, 1); array_insert(int, arrayOfIndex, i, index); array_insert_last(Ntk_Node_t *, arrayOfNodes, node); } } sub = PartCreateSingleSubSystem(arrayOfNodes, network); leftNodes -= array_n(arrayOfNodes); array_insert_last(Part_Subsystem_t *, result, sub); array_free(arrayOfNodes); } } if (leftNodes > 0){ arrayOfNodes = array_alloc(Ntk_Node_t *, 0); arrayForEachItem(Ntk_Node_t *, partSubInfo->arrayOfVertex, i, node){ if (array_fetch(int, check, i)==0) array_insert_last(Ntk_Node_t *, arrayOfNodes, node); } sub = PartCreateSingleSubSystem(arrayOfNodes, network); array_free(arrayOfNodes); }else{ sub = NIL(Part_Subsystem_t); } array_insert_last(Part_Subsystem_t *, result, sub); array_free(check); array_free(arrayOfIndex); st_free_table(ptrToIndexInfo); st_free_table(indexToPtrInfo); st_free_table(dataInputNodes); return result; } /*if dynamicIncrease*/ }else { /* * If we don't want to put all formula nodes in the 1st subsystem, * we need to break them into several pieces. */ } /* * get a affinity matrix (dependency matrix, correlation matrix) */ arrayOfDependency = PartCreateDependencyMatrix(partSubInfo, ptrToIndexInfo); if (partSubInfo->corMethod == Part_CorrelationWithBDD) arrayOfCorrelation = PartCreateCorrelationMatrixFromBDD(partSubInfo); else if ((partSubInfo->corMethod == Part_CorrelationWithSupport) || (partSubInfo->corMethod == Part_CorrelationDefault)) arrayOfCorrelation = PartCreateCorrelationMatrixFromSupport(partSubInfo); arrayOfAffinity = PartCreateAffinityMatrix(arrayOfDependency, arrayOfCorrelation, partSubInfo); if (partSubInfo->verbosity > 2 ){ fprintf(vis_stdout,"\nGrouping: Dependency\n"); fprintf(vis_stdout,"--------------------\n"); PartPrintArrayArray(arrayOfDependency, partSubInfo->numberOfVertex, 1); fprintf(vis_stdout,"\nGrouping: Correlation\n"); fprintf(vis_stdout,"---------------------\n"); PartPrintArrayArray(arrayOfCorrelation, partSubInfo->numberOfVertex, 0); fprintf(vis_stdout,"\nGrouping: Affinity\n"); fprintf(vis_stdout,"------------------\n"); PartPrintArrayArray(arrayOfAffinity, partSubInfo->numberOfVertex, 0); } FREE(arrayOfDependency); FREE(arrayOfCorrelation); /* If number of formula nodes are bigger than bound, break down into * bounded sized subsystems. */ if (st_count(dataInputNodes) > partSubInfo->bound && strictBound ){ tempCheck = array_alloc(int, partSubInfo->numberOfVertex); tempCC = array_alloc(Ntk_Node_t *, partSubInfo->numberOfVertex); for(i=0; inumberOfVertex; i++){ array_insert(int, tempCheck, i, 1); array_insert(Ntk_Node_t *, tempCC, i, (Ntk_Node_t *)0); } i = 0; st_foreach_item(dataInputNodes, stGen, &node, NULL) { st_lookup_int(ptrToIndexInfo, node, &index); array_insert(int, arrayOfIndex, i++, index); array_insert(int, check, index, 1); array_insert(int, tempCheck, index, 0); array_insert(Ntk_Node_t *, tempCC, index, node); } numSeed = (int) ceil((double)st_count(dataInputNodes)/(double)(partSubInfo->bound)); arrayOfSeed = array_alloc(Ntk_Node_t *, numSeed); seedLast = PartSelectNodeOfMinSupport(tempCC, tempCheck, partSubInfo); array_insert(Ntk_Node_t *, arrayOfSeed, 0, seedLast); for (i=1; i< numSeed; i++){ seedNext = PartSelectFarNode(seedLast, tempCC, tempCheck, arrayOfAffinity, ptrToIndexInfo); array_insert(Ntk_Node_t *, arrayOfSeed, i, seedNext); seedLast = seedNext; } /* * Break formula nodes, put into table and insert into final result */ arrayOfBreak = PartBreakingBigConnectedComponent(tempCC, tempCheck, arrayOfSeed, arrayOfAffinity, partSubInfo, ptrToIndexInfo); array_free(tempCheck); array_free(tempCC); array_free(arrayOfSeed); assert(array_n(arrayOfBreak) > 0); maxSize = -1; maxIndex = -1; /* don't care value to suppress warning */ arrayForEachItem(array_t *, arrayOfBreak, i, arrayOfNodes){ if (array_n(arrayOfNodes)>maxSize){ maxIndex = i; maxSize = array_n(arrayOfNodes); } } arrayOfNodes = array_fetch(array_t *, arrayOfBreak, maxIndex); sub = PartCreateSingleSubSystem(arrayOfNodes, network); leftNodes -= array_n(arrayOfNodes); array_insert_last(Part_Subsystem_t *, result, sub); arrayForEachItem(array_t *, arrayOfBreak, i, arrayOfNodes){ if (i != maxIndex){ sub = PartCreateSingleSubSystem(arrayOfNodes, network); leftNodes -= array_n(arrayOfNodes); array_insert_last(Part_Subsystem_t *, result, sub); } } PartArrayOfArrayFree(arrayOfBreak); }/* if (st_count(dataInputNodes) > partSubInfo->bound && strictBound)*/ st_free_table(dataInputNodes); /* * Create new affinity matrix. Now new affinity is defined from * sub-system(s) created above to left nodes. */ arrayTemp = NIL(array_t); if (leftNodes > 0){ arrayTemp = array_alloc(float, partSubInfo->numberOfVertex); arrayForEachItem(int, arrayOfIndex, i, index){ for(j=0;jnumberOfVertex;j++){ affinity = PartGetElementFromSymMatrix(arrayOfAffinity,index,j); if (i==0){ array_insert(float, arrayTemp, j, affinity); } else { prevAffinity = array_fetch(float, arrayTemp, j); array_insert(float, arrayTemp, j, affinity + prevAffinity); } } } array_free(arrayOfIndex); FREE(arrayOfAffinity); if (partSubInfo->verbosity > 2 ){ fprintf(vis_stdout,"\nGrouping:: combinded affinity\n"); fprintf(vis_stdout,"------------------\n"); arrayForEachItem(float, arrayTemp, i, affinity){ fprintf(vis_stdout, "%.10f ", affinity); } fprintf(vis_stdout, "\n"); } }else{ array_free(arrayOfIndex); FREE(arrayOfAffinity); } /* * Create sub-system by choosing a nodes with biggest new affinity */ while( leftNodes > 0 ){ numIncluded = 0; arrayOfVertex = array_alloc(Ntk_Node_t *, 0); while ((numIncluded < partSubInfo->bound) && (leftNodes > 0)){ /* * The node with maximum affinity to formula nodes is included * in next sub-system until number of nodes reaches to bound */ prevAffinity = -1.0; maxIndex = 0; arrayForEachItem( float, arrayTemp, i, affinity){ if ( array_fetch(int, check, i) != 1 ){ if (affinity >= prevAffinity){ prevAffinity = affinity; maxIndex = i; } } } st_lookup(indexToPtrInfo, (char *)(long)maxIndex, &node); array_insert_last(Ntk_Node_t *, arrayOfVertex, node); array_insert(int, check, maxIndex, 1); numIncluded++; leftNodes--; } sub = PartCreateSingleSubSystem(arrayOfVertex, network); array_free(arrayOfVertex); array_insert_last(Part_Subsystem_t *, result, sub); } array_free(check); if (arrayTemp != NIL(array_t)) array_free(arrayTemp); st_free_table(ptrToIndexInfo); st_free_table(indexToPtrInfo); if (partSubInfo->verbosity >= 2){ Part_Subsystem_t *sub; char *latchName; st_generator *stGen; fprintf(vis_stdout,"\nGrouping: List of subsytem latches\n"); fprintf(vis_stdout,"----------------------------------\n\n"); arrayForEachItem(Part_Subsystem_t *, result, i, sub){ fprintf(vis_stdout,"[Subsystem %3d]\n",i); st_foreach_item(sub->vertexNameTable, stGen, &latchName, NIL(char *) ){ fprintf(vis_stdout,"%s\n",latchName); } fprintf(vis_stdout,"\n"); } } return result; } /**Function******************************************************************** Synopsis [Create the vertex dependency matrix] Description [vertex 1 depends on vertex 2, if the support of the function attatched to vertex 1 contains vertex 2] SideEffects [] ******************************************************************************/ static char * PartCreateDependencyMatrix( Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex) { char *result; array_t *arrayNodeFrom; int i, j, k; Ntk_Node_t *node, *latchInputNode; array_t *arrayOfSupport; Ntk_Network_t *network = partSubInfo->network; int index, size; size = partSubInfo->numberOfVertex; result = ALLOC(char, size * size); (void)memset((void *)result, 0, sizeof(char) * size * size); for (i = 0; i < partSubInfo->numberOfVertex; i++) { node = array_fetch(Ntk_Node_t *, partSubInfo->arrayOfVertex, i); arrayNodeFrom = array_alloc(Ntk_Node_t *, 1); array_insert(Ntk_Node_t *, arrayNodeFrom, 0, node); arrayOfSupport = Ntk_NodeComputeCombinationalSupport(network, arrayNodeFrom, FALSE); array_free(arrayNodeFrom); arrayForEachItem(Ntk_Node_t *, arrayOfSupport, j, node) { if (!Ntk_NodeTestIsLatch(node)) continue; latchInputNode = Ntk_LatchReadDataInput(node); if (st_lookup_int(ptrToIndex, (char *)latchInputNode, &k)) { index = i * partSubInfo->numberOfVertex + k; result[index] = 1; } else { fprintf(vis_stderr, "** part error: can't find the latch input index.\n"); } } array_free(arrayOfSupport); } return result; } /**Function******************************************************************** Synopsis [Create the latch Correlation Matrix] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ static float * PartCreateCorrelationMatrixFromSupport( Part_SubsystemInfo_t *partSubInfo) { int i, j; float *result; float correlation; array_t *arrayOfSupport; st_table *tableOfSupport; array_t *arrayOfSupportTable; array_t *arrayNodeFrom; Ntk_Node_t *nodeFrom, *node; Ntk_Network_t *network = partSubInfo->network; int index; result = ALLOC(float, partSubInfo->numberOfVertex * (partSubInfo->numberOfVertex - 1) / 2); arrayOfSupportTable = array_alloc(st_table *, partSubInfo->numberOfVertex); for (i = 0; i < partSubInfo->numberOfVertex; i++) { nodeFrom = array_fetch(Ntk_Node_t *, partSubInfo->arrayOfVertex, i); arrayNodeFrom = array_alloc(Ntk_Node_t *, 1); array_insert(Ntk_Node_t *, arrayNodeFrom, 0, nodeFrom); arrayOfSupport = Ntk_NodeComputeCombinationalSupport(network, arrayNodeFrom, FALSE); array_free(arrayNodeFrom); tableOfSupport = st_init_table(st_ptrcmp, st_ptrhash); arrayForEachItem(Ntk_Node_t *, arrayOfSupport, j, node) { st_insert(tableOfSupport, (char *)node, (char *)NULL); } array_free(arrayOfSupport); array_insert(st_table *, arrayOfSupportTable, i, tableOfSupport); } for (i = 1; i < partSubInfo->numberOfVertex; i++) { for (j = 0; j < i; j++) { correlation = PartVertexComputeCorrelation(i, j, arrayOfSupportTable, partSubInfo); index = i * (i - 1) / 2 + j; result[index] = correlation; } }/* end of for */ for (i = 0; i < partSubInfo->numberOfVertex; i++) st_free_table(array_fetch(st_table *, arrayOfSupportTable, i)); array_free(arrayOfSupportTable); return result; } /**Function******************************************************************** Synopsis [Create the latch Correlation Matrix] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ static float * PartCreateCorrelationMatrixFromBDD( Part_SubsystemInfo_t *partSubInfo) { int i, j; float *result; array_t *agreeArray; array_t *arrayOfMddArray; float agreement; float correlation = 0.0; char *name; Ntk_Node_t *node; Mvf_Function_t *mvf; vertex_t *vertex; graph_t *partition = Part_NetworkReadPartition(partSubInfo->network); mdd_manager *mddmgr = PartPartitionReadMddManager(partition); int index; result = ALLOC(float, partSubInfo->numberOfVertex * (partSubInfo->numberOfVertex - 1) / 2); arrayOfMddArray = array_alloc(array_t *, partSubInfo->numberOfVertex); for (i = 0; i < partSubInfo->numberOfVertex; i++) { node = array_fetch(Ntk_Node_t *, partSubInfo->arrayOfVertex, i); name = Ntk_NodeReadName(node); vertex = Part_PartitionFindVertexByName(partition, name); mvf = Part_VertexReadFunction(vertex); array_insert(array_t *, arrayOfMddArray, i, (array_t *)mvf); } for (i = 1; i < partSubInfo->numberOfVertex; i++) { for (j = 0; j < i; j++) { int k; agreeArray = PartVertexComputeAgreement(mddmgr, i, j, arrayOfMddArray); correlation = 0.0; arrayForEachItem(float, agreeArray, k, agreement) { correlation += (float)pow(1.0 - 4.0 * agreement * (1.0 - agreement), partSubInfo->cor_factor); } correlation /= (float)array_n(agreeArray); array_free(agreeArray); index = i * (i - 1) / 2 + j; result[index] = correlation; } }/* end of for */ array_free(arrayOfMddArray); return result; } /**Function******************************************************************** Synopsis [Gets the latch Correlation between two vertices] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ static float PartVertexComputeCorrelation( int index1, int index2, array_t *arrayOfInputSupportTable, Part_SubsystemInfo_t *partSubInfo) { st_generator *stGen; st_table *inputSupportTable1; st_table *inputSupportTable2; int sameSupportCount; float correlation; int inputSupportCount; Ntk_Node_t *node; sameSupportCount = 0; inputSupportTable1 = array_fetch(st_table *, arrayOfInputSupportTable, index1); inputSupportTable2 = array_fetch(st_table *, arrayOfInputSupportTable, index2); st_foreach_item(inputSupportTable1, stGen, &node, NULL) { if (st_is_member(inputSupportTable2, node)) { sameSupportCount++; } } inputSupportCount = st_count(inputSupportTable1) + st_count(inputSupportTable2) - sameSupportCount; if (inputSupportCount != 0) { correlation = (float)pow((double)sameSupportCount / (double)inputSupportCount, (double)partSubInfo->cor_factor); } else { correlation = 0.0; } return correlation; } /**Function******************************************************************** Synopsis [Gets the latch Correlation between two vertices] SideEffects [] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ static array_t * PartVertexComputeAgreement( mdd_manager *mddMgr, int index1, int index2, array_t *arrayOfMddArray) { int i, j; float agreement; mdd_t *mddFrom, *mddTo; array_t *mddArrayFrom, *mddArrayTo; array_t *agreeArray = array_alloc(float, 0); mddArrayFrom = array_fetch(array_t *, arrayOfMddArray, index1); mddArrayTo = array_fetch(array_t *, arrayOfMddArray, index2); arrayForEachItem(mdd_t *, mddArrayFrom, i, mddFrom) { arrayForEachItem(mdd_t *, mddArrayTo, j, mddTo) { agreement = bdd_correlation(mddFrom, mddTo); array_insert_last(float, agreeArray, agreement); } } return agreeArray; } /**Function******************************************************************** Synopsis [Create the latch Affinity Matrix] Description [Affinity is a convex function of connectivity and correlation. For circuits which are more primary input sensitive, the latch correlation seems to be more important, while for circuit which are more state sensitive, the latch connectivity seems to be more important.The aff_factor controls the weight of two sides. The bigger the aff_factor is, the more weight is given to the latch connectivity.] SideEffects [Each row element of arrayOfCorreletion is freed] SeeAlso [Part_SubsystemInfo] ******************************************************************************/ static float * PartCreateAffinityMatrix( char *arrayOfDependency, float *arrayOfCorrelation, Part_SubsystemInfo_t *partSubInfo) { float *result; int i, j; float dep1, dep2; float connectivity = 0.0; float correlation = 0.0; float affinity; int index; result = ALLOC(float, partSubInfo->numberOfVertex * (partSubInfo->numberOfVertex - 1) / 2); for (i = 1; i < partSubInfo->numberOfVertex; i++) { for (j = 0; j < i; j++) { if (arrayOfDependency) { dep1 = dep2 = 0.0; index = i * partSubInfo->numberOfVertex + j; if (arrayOfDependency[index] == 1) dep1 = 1.0; index = j * partSubInfo->numberOfVertex + i; if (arrayOfDependency[index] == 1) dep2 = 1.0; connectivity = (dep1 + dep2 + (partSubInfo->con_factor - 2) * dep1 * dep2) / partSubInfo->con_factor; } else connectivity = 0.0; if (arrayOfCorrelation) correlation = PartGetElementFromSymMatrix(arrayOfCorrelation, i, j); else correlation = 0.0; /* * affinity is a convex function of connectivity and correlation */ affinity = partSubInfo->aff_factor * connectivity + (1.0 - partSubInfo->aff_factor) * correlation; index = i * (i - 1) / 2 + j; result[index] = affinity; } } return result; } /**Function******************************************************************** Synopsis [Gets Conected Components of vertices] Description [The affinity matrix is considered as graph, and higher value than threshold is considered edge between two verticies. And connected components are found by searching the graph] SideEffects [] SeeAlso [] ******************************************************************************/ static array_t * PartGetConnectedComponent( float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *indexToPtr) { array_t *arrayOfCCs; /* array of connected component */ array_t *connectedComponent; array_t *arrayOfFrom; array_t *arrayOfCCIndex; /* keep ccId of each vertex */ float affinity, affmax; float affsum, density, nonZeroCount; int next; /* serching connected component from this index */ int ccId; /* each connected component gets its own ccId */ int ccIndex; int i, size; Ntk_Node_t *node; next = 0; /* keep the smallest index of vertex not included in CC */ ccId = 0; /* give ccId to each CC */ affmax = 0.0; affsum = 0.0; nonZeroCount = 0; arrayOfCCIndex = array_alloc(int, partSubInfo->numberOfVertex); /* * Initially, all vertecies are included in one component */ for (i = 0; i < partSubInfo->numberOfVertex; i++) { array_insert(int, arrayOfCCIndex, i, 0); } /* * If the threshold is not defined, get an average of affinity in the matrix * and a density. Threshold is assigned between average of affinity and * the maximum value of affinity according to density. If the matrix is * dense(sparse), threshold goes up(goes down). */ if (partSubInfo->threshold == 0.0) { size = partSubInfo->numberOfVertex * (partSubInfo->numberOfVertex - 1) / 2; for (i = 0; i < size; i++) { affinity = arrayOfAffinity[i]; if (affmax < affinity) { affmax = affinity; } if (affinity > 0.0) { nonZeroCount += 1.0; } affsum += affinity; } density = nonZeroCount / pow((double)partSubInfo->numberOfVertex, 2.0); partSubInfo->threshold = (float)((affsum / nonZeroCount) + (affmax - affsum / nonZeroCount) * density); } /* * Get a connected component from the vertex which is pointed by 'next' * with its index. The 'next' is updated during searching CC in the function * PartFindCC */ while (next < partSubInfo->numberOfVertex) { ccId++; array_insert(int, arrayOfCCIndex, next, ccId); if (next == partSubInfo->numberOfVertex - 1) { break; } arrayOfFrom = array_alloc(int, 1); array_insert(int, arrayOfFrom, 0, next); PartFindCC(&next, &ccId, arrayOfCCIndex, arrayOfAffinity, arrayOfFrom, partSubInfo); } /* * initialize arrayOfCCs, which is the result. */ arrayOfCCs = array_alloc(array_t *, ccId); for (i = 0; i < ccId; i++) { connectedComponent = array_alloc(Ntk_Node_t *, 0); array_insert(array_t *, arrayOfCCs, i, connectedComponent); } /* * change index to vertex pointer and insert into each CC */ arrayForEachItem(int, arrayOfCCIndex, i, ccIndex) { st_lookup(indexToPtr, (char *)(long)i, &node); connectedComponent = array_fetch(array_t *, arrayOfCCs, ccIndex-1); array_insert_last(Ntk_Node_t *, connectedComponent, node); } array_free(arrayOfCCIndex); return arrayOfCCs; } /**Function******************************************************************** Synopsis [Get a conected component of vertices.] SideEffects [The connected component is searched from 'arrayFrom' and each vertex in that connected component gets the index of the current connected component. And 'next' points the next possible vertex] SeeAlso [] ******************************************************************************/ static void PartFindCC( int *next, int *ccId, array_t *arrayOfCCIndex, float *arrayOfAffinity, array_t *arrayOfFrom, Part_SubsystemInfo_t *partSubInfo) { int i, j, from; int arrayInd; float connected; array_t *arrayOfReached; /* * Update next in order to let next keep the smallest vertex index which * is not traversed. */ (*next)++; while (1) { if (*next == partSubInfo->numberOfVertex) { array_free(arrayOfFrom); return; } if (array_fetch(int, arrayOfCCIndex, *next) != 0) { (*next)++; } else { break; } } arrayOfReached = array_alloc(int, 0); /* Reached set from arrayOfFrom */ /* * Find all vertecies which can be traversed from arrayOfFrom * and update next */ while (array_n(arrayOfFrom) > 0) { arrayForEachItem(int, arrayOfFrom, i, from) { for (j = 0; j < partSubInfo->numberOfVertex; j++) { connected = PartGetElementFromSymMatrix(arrayOfAffinity, from, j); arrayInd = array_fetch(int, arrayOfCCIndex, j); if (connected > partSubInfo->threshold && arrayInd == 0) { array_insert_last(int, arrayOfReached, j); array_insert(int, arrayOfCCIndex, j, *ccId); if (*next == j) { (*next)++; while (1) { if (*next == partSubInfo->numberOfVertex) { array_free(arrayOfReached); array_free(arrayOfFrom); return; } if (array_fetch(int, arrayOfCCIndex, *next) != 0) { (*next)++; } else { break; } }/* end of while */ }/* end if */ } }/* end for */ }/* end of arrayForEachItem(arrayOfFrom) */ array_free(arrayOfFrom); arrayOfFrom = arrayOfReached; /* Traverse with new reached set */ arrayOfReached = array_alloc(int, 0); }/* end of while */ array_free(arrayOfFrom); array_free(arrayOfReached); return; } /**Function******************************************************************** Synopsis [Gets an sub-partitions with bounded size] Description [Break the connected component which has more verteices than bound and aggregate the connected components which have less vertecies than bound.] SideEffects [] SeeAlso [] ******************************************************************************/ static array_t * PartBreakingAggregating( array_t *arrayOfInit, float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex, char *arrayOfDependency) { array_t *arrayOfAggregate; array_t *arrayOfSeed; array_t *arrayOfSmall; array_t *arrayOfBreak; array_t *arrayOfFinal; array_t *arrayOfCCVertex; array_t *arrayVertex; array_t *arrayOfNew; array_t *cc; array_t *ccCheck; /* check cc which is included in final result */ float *groupDependency; st_table *tableOfCC; float groupDep; int i, j, k, l; array_t *arrayOfLatchNames; char *name; Part_Subsystem_t *sub; Part_Subsystem_t *subIn; Part_Subsystem_t *subOut; Ntk_Node_t *seedlast, *seednext, *node; char *funcName; arrayOfSmall = array_alloc(array_t *, 0); arrayOfFinal = array_alloc(Part_Subsystem_t *, 0); arrayOfCCVertex = array_alloc(array_t *, 0); if (partSubInfo->bound == 0) { partSubInfo->bound = partSubInfo->numberOfVertex / array_n(arrayOfInit); } arrayForEachItem(array_t *, arrayOfInit, i, cc) { if (array_n(cc) > partSubInfo->bound) { /* * If cc has more vertecies than bound, calculate how many seeds are needed * and get those seeds which are far away from each others */ ccCheck = array_alloc(int, array_n(cc)); for (j = 0; j < array_n(cc); j++) { array_insert(int, ccCheck, j, 0); } /* * The first seed is the vertex which has the smallest support and * choose the next vertex which is the farthest from last seed */ arrayOfSeed = array_alloc(Ntk_Node_t *, 0); seedlast = PartSelectNodeOfMinSupport(cc, ccCheck, partSubInfo); array_insert_last(Ntk_Node_t *, arrayOfSeed, seedlast); for (j = 1; j < ceil((double)array_n(cc) / (double)(partSubInfo->bound)); j++) { seednext = PartSelectFarNode(seedlast, cc, ccCheck, arrayOfAffinity, ptrToIndex); array_insert_last(Ntk_Node_t *, arrayOfSeed, seednext); seedlast = seednext; } /* * Break big CC, put into table and insert into final result */ arrayOfBreak = PartBreakingBigConnectedComponent(cc, ccCheck, arrayOfSeed, arrayOfAffinity, partSubInfo, ptrToIndex); array_free(ccCheck); array_free(arrayOfSeed); arrayForEachItem(array_t *, arrayOfBreak, j, arrayOfNew) { if (array_n(arrayOfNew) == partSubInfo->bound) { tableOfCC = st_init_table(strcmp, st_strhash); arrayVertex = array_alloc(Ntk_Node_t *, array_n(arrayOfNew)); arrayForEachItem(Ntk_Node_t *, arrayOfNew, k, node) { funcName = Ntk_NodeReadName(node); if (st_lookup(partSubInfo->dupLatchTable, funcName, &arrayOfLatchNames)) { arrayForEachItem(char *, arrayOfLatchNames, l, name) { st_insert(tableOfCC, (char *)name, (char *)NULL); } } else { if (st_lookup(partSubInfo->latchNameTable, (char *)funcName, (char **)&name)) { st_insert(tableOfCC, (char *)name, (char *)NULL); } else error_append("can't find the latch name."); } array_insert(Ntk_Node_t *, arrayVertex, k, node); } sub = ALLOC(Part_Subsystem_t, 1); sub->vertexNameTable = tableOfCC; sub->subsystemFanIn = array_alloc(int, 0); sub->subsystemFanOut = array_alloc(int, 0); array_insert_last(Part_Subsystem_t *, arrayOfFinal, sub); array_insert_last(array_t *, arrayOfCCVertex, arrayVertex); array_free(arrayOfNew); } else { array_insert_last(array_t *, arrayOfSmall, arrayOfNew); } }/* end of arrayForEachItem(arrayOfBreak) */ array_free(arrayOfBreak); array_free(cc); } else if (array_n(cc) < partSubInfo->bound) { /* * If cc has less nodes than bound, put into arrayOfSmall */ array_insert_last(array_t *, arrayOfSmall, cc); } else { /* * If cc has same number of verteices as bound, put into table and * insert into final result */ tableOfCC = st_init_table(strcmp, st_strhash); arrayVertex = array_alloc(Ntk_Node_t *, array_n(cc)); arrayForEachItem(Ntk_Node_t *, cc, j, node) { funcName = Ntk_NodeReadName(node); if (st_lookup(partSubInfo->dupLatchTable, funcName, &arrayOfLatchNames)) { arrayForEachItem(char *, arrayOfLatchNames, l, name) { st_insert(tableOfCC, (char *)name, (char *)NULL); } } else { if (st_lookup(partSubInfo->latchNameTable, (char *)funcName, (char **)&name)) { st_insert(tableOfCC, (char *)name, (char *)NULL); } else error_append("can't find the latch name."); } array_insert(Ntk_Node_t *, arrayVertex, j, node); } sub = ALLOC(Part_Subsystem_t, 1); sub->vertexNameTable = tableOfCC; sub->subsystemFanIn = array_alloc(int, 0); sub->subsystemFanOut = array_alloc(int, 0); array_insert_last(Part_Subsystem_t *, arrayOfFinal, sub); array_insert_last(array_t *, arrayOfCCVertex, arrayVertex); array_free(cc); } } /* * aggregate small cc, put into table and insert into final resault */ arrayOfAggregate = PartAggregating(arrayOfSmall, arrayOfAffinity, partSubInfo, ptrToIndex); array_free(arrayOfSmall); arrayForEachItem(array_t *, arrayOfAggregate, i, arrayOfNew) { tableOfCC = st_init_table(strcmp, st_strhash); arrayVertex = array_alloc(Ntk_Node_t *, array_n(arrayOfNew)); arrayForEachItem(Ntk_Node_t *, arrayOfNew, j, node) { funcName = Ntk_NodeReadName(node); if (st_lookup(partSubInfo->dupLatchTable, funcName, &arrayOfLatchNames)) { arrayForEachItem(char *, arrayOfLatchNames, l, name) { st_insert(tableOfCC, (char *)name, (char *)NULL); } } else { if (st_lookup(partSubInfo->latchNameTable, (char *)funcName, (char **)&name)) { st_insert(tableOfCC, (char *)name, (char *)NULL); } else error_append("can't find the latch name."); } array_insert(Ntk_Node_t *, arrayVertex, j, node); } sub = ALLOC(Part_Subsystem_t, 1); sub->vertexNameTable = tableOfCC; sub->subsystemFanIn = array_alloc(int, 0); sub->subsystemFanOut = array_alloc(int, 0); array_insert_last(Part_Subsystem_t *, arrayOfFinal, sub); array_insert_last(array_t *, arrayOfCCVertex, arrayVertex); array_free(arrayOfNew); }/* end of arrayForEachItem(arrayOfAggregate) */ array_free(arrayOfAggregate); /* * Get group dependency, which is dependency between two subsystems from * dependency between vertecies */ groupDependency = PartGetGroupMatrixRegular(arrayOfCCVertex, arrayOfDependency, ptrToIndex, partSubInfo->numberOfVertex); if (partSubInfo->verbosity >= 2) { int index; fprintf(vis_stdout, "\nGrouping: Group Dependency\n"); fprintf(vis_stdout, "--------------------------\n"); for (i = 0; i < array_n(arrayOfCCVertex); i++) { for (j = 0; j < array_n(arrayOfCCVertex); j++) { index = i * array_n(arrayOfCCVertex) + j; fprintf(vis_stdout, "%4.3f ", groupDependency[index]); } fprintf(vis_stdout, "\n"); } } for (i = 0; i < array_n(arrayOfCCVertex); i++) { subIn = array_fetch(Part_Subsystem_t *, arrayOfFinal, i); for (j = 0; j < array_n(arrayOfCCVertex); j++) { subOut = array_fetch(Part_Subsystem_t *, arrayOfFinal, j); if (i != j) { int index; index = i * array_n(arrayOfCCVertex) + j; groupDep = groupDependency[index]; if (groupDep > 0.0) { array_insert_last(int, subIn ->subsystemFanIn, j); array_insert_last(int, subOut->subsystemFanOut, i); } } } } PartArrayOfArrayFree(arrayOfCCVertex); FREE(groupDependency); return arrayOfFinal; } /**Function******************************************************************** Synopsis [Create subsystems accoring to arrayOfGroupIndex] Description [Each latch data input L(i) in array arrayOfLatchDataInputNamesi is put in I(i)'th subsystem. I is arrayOfGroupIndex. Index should start from 0 to n as sequence.] SideEffects [] SeeAlso [] ******************************************************************************/ static array_t * PartCreateSubSystemWithGroupIndex( Part_SubsystemInfo_t *partSubInfo, array_t *arrayOfLatchNames, array_t *arrayOfGroupIndex) { int i, j; array_t *result; char *latchName; array_t *arrayOfGroupVertex; array_t *arrayOfVertex; array_t *arrayOfLatchDataInputNames; Ntk_Node_t *node, *latchNode, *latchInputNode; Part_Subsystem_t *sub; st_table *groupIndexTable; st_table **faninIndexTable, **fanoutIndexTable; char *name; array_t *arrayOfSupport; st_generator *stGen; int nLatches; int nGroups = 0; int preIndex, newIndex; long index; char *otherLatchName; array_t *latchNameArray; nLatches = array_n(arrayOfLatchNames); /* reassign group index with counting the number of groups */ groupIndexTable = st_init_table(st_numcmp, st_numhash); preIndex = -1; arrayForEachItem(int, arrayOfGroupIndex, i, index) { if (index == preIndex || st_lookup_int(groupIndexTable, (char *)index, &newIndex)) { if (index != newIndex) array_insert(int, arrayOfGroupIndex, i, newIndex); } else { st_insert(groupIndexTable, (char *)index, (char *)(long)nGroups); newIndex = nGroups++; if (index != newIndex) array_insert(int, arrayOfGroupIndex, i, newIndex); } preIndex = (int) index; } st_free_table(groupIndexTable); groupIndexTable = st_init_table(strcmp, st_strhash); faninIndexTable = ALLOC(st_table *, nGroups); fanoutIndexTable = ALLOC(st_table *, nGroups); for (i = 0; i < nGroups; i++) { faninIndexTable[i] = st_init_table(st_numcmp, st_numhash); fanoutIndexTable[i] = st_init_table(st_numcmp, st_numhash); } /* makes an array of latch input names from latch names */ arrayOfLatchDataInputNames = array_alloc(char *, 0); arrayForEachItem(char *, arrayOfLatchNames, i, latchName) { latchNode = Ntk_NetworkFindNodeByName(partSubInfo->network, latchName); latchInputNode = Ntk_LatchReadDataInput(latchNode); name = Ntk_NodeReadName(latchInputNode); array_insert_last(char *, arrayOfLatchDataInputNames, name); } result = array_alloc(Part_Subsystem_t *, nGroups); arrayOfGroupVertex = array_alloc(array_t *, nGroups); /* creates subsystems */ for (i = 0; i < nGroups; i++) { sub = ALLOC(Part_Subsystem_t, 1); sub->vertexNameTable = st_init_table(strcmp, st_strhash); sub->subsystemFanIn = array_alloc(int, 0); sub->subsystemFanOut = array_alloc(int, 0); arrayOfVertex = array_alloc(Ntk_Node_t *, 0); array_insert(Part_Subsystem_t *, result, i, sub); array_insert(array_t *, arrayOfGroupVertex, i, arrayOfVertex); } /* makes group index table and fills in the vertex name table */ for (i = 0; i < nLatches; i++) { index = (long) array_fetch(int, arrayOfGroupIndex, i); name = array_fetch(char *, arrayOfLatchDataInputNames, i); latchName = array_fetch(char *, arrayOfLatchNames, i); sub = array_fetch(Part_Subsystem_t *, result, (int) index); latchNode = Ntk_NetworkFindNodeByName(partSubInfo->network, latchName); latchName = Ntk_NodeReadName(latchNode); st_insert(sub->vertexNameTable, (char *)latchName, (char *)NULL); if (st_lookup(partSubInfo->latchNameTable, name, &otherLatchName)) { if (st_lookup(partSubInfo->dupLatchTable, name, &latchNameArray)) { array_insert_last(char *, latchNameArray, latchName); } else { latchNameArray = array_alloc(char *, 0); array_insert_last(char *, latchNameArray, otherLatchName); array_insert_last(char *, latchNameArray, latchName); st_insert(partSubInfo->dupLatchTable, name, latchNameArray); } continue; } st_insert(partSubInfo->latchNameTable, name, latchName); st_insert(groupIndexTable, name, (char *)index); arrayOfVertex = array_fetch(array_t *, arrayOfGroupVertex, (int)index); node = Ntk_NetworkFindNodeByName(partSubInfo->network, name); array_insert_last(Ntk_Node_t *, arrayOfVertex, node); } /* computes fanin and fanout table for each group */ for (i = 0; i < nGroups; i++) { arrayOfVertex = array_fetch(array_t *, arrayOfGroupVertex, i); arrayOfSupport = Ntk_NodeComputeCombinationalSupport(partSubInfo->network, arrayOfVertex, FALSE); arrayForEachItem(Ntk_Node_t *, arrayOfSupport, j, node) { if (!Ntk_NodeTestIsLatch(node)) continue; name = Ntk_NodeReadName(Ntk_LatchReadDataInput(node)); if (st_lookup(groupIndexTable, name, &index)) { if (index == i) continue; st_insert(faninIndexTable[i], (char *)index, NIL(char)); st_insert(fanoutIndexTable[index], (char *)(long)i, NIL(char)); } } array_free(arrayOfSupport); } /* makes fanin and fanout array for each subsystem */ for (i = 0; i < nGroups; i++) { sub = array_fetch(Part_Subsystem_t *, result, i); st_foreach_item(faninIndexTable[i], stGen, &index, NULL) { array_insert_last(int, sub->subsystemFanIn, (int) index); } st_free_table(faninIndexTable[i]); array_sort(sub->subsystemFanIn, numCompare); st_foreach_item(fanoutIndexTable[i], stGen, &index, NULL) { array_insert_last(int, sub->subsystemFanOut, (int) index); } st_free_table(fanoutIndexTable[i]); array_sort(sub->subsystemFanOut, numCompare); } FREE(faninIndexTable); FREE(fanoutIndexTable); array_free(arrayOfLatchDataInputNames); st_free_table(groupIndexTable); PartArrayOfArrayFree(arrayOfGroupVertex); return result; } /**Function******************************************************************** Synopsis [Gets bounded size blocks from big CC, Breaking] Description [Gets bounded size blocks from big connected component] SideEffects [] SeeAlso [] ******************************************************************************/ static array_t * PartBreakingBigConnectedComponent( array_t *arrayOfCC, array_t *ccCheck, array_t *arrayOfSeed, float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex) { array_t *result; /* array of groups with the proper size */ array_t *resultRow; /* a group with the proper size */ array_t *arrayTemp; array_t *seedFull; /* array of seeds */ int i, count; int totalCount; /* how many vertixes are already computed */ int indexOfSeed; /* index of the seed which is closest from the vertex */ Ntk_Node_t *seed, *variable, *pick; result = array_alloc(array_t *, array_n(arrayOfSeed)); for (i = 0; i < array_n(arrayOfSeed); i++) { arrayTemp = array_alloc(Ntk_Node_t *, 0); seed = array_fetch(Ntk_Node_t *, arrayOfSeed, i); array_insert_last(Ntk_Node_t *, arrayTemp, seed); array_insert(array_t *, result, i, arrayTemp); } switch (partSubInfo->partBM) { /* * Breaking Static Round Robin Seed Choice * Fixed order of seeds and each seed find the closest vertex */ case Part_BSRR_s: totalCount = array_n(arrayOfSeed); arrayForEachItem(Ntk_Node_t *, arrayOfSeed, i, seed) { count = 1; resultRow = array_fetch(array_t *, result, i); while ((count < partSubInfo->bound) && (totalCount < array_n(arrayOfCC))) { pick = PartSelectCloseNode(seed, arrayOfCC, ccCheck, arrayOfAffinity, ptrToIndex); array_insert_last(Ntk_Node_t *, resultRow, pick); count++; totalCount++; seed = pick; } } break; /* * Breaking Fixed Order State Variable Choice * Fixed order of vertecies and each vertex find the closest seed */ case Part_BFix_v: /* * Fixed order of nodes and each node find the closest seed */ seedFull = array_alloc(int, 0); for (i = 0; i < array_n(arrayOfSeed); i++) { array_insert_last(int, seedFull, 1); } arrayForEachItem(Ntk_Node_t *, arrayOfCC, i, variable) { if (array_fetch(int, ccCheck, i) != 1) { indexOfSeed = PartSelectCloseSeedIndex(variable, arrayOfSeed, arrayOfAffinity, ptrToIndex, seedFull, partSubInfo->bound); resultRow = array_fetch(array_t *, result, indexOfSeed); array_insert_last(Ntk_Node_t *, resultRow, variable); array_insert(int, ccCheck, i, 1); } } array_free(seedFull); break; default: break; } return result; } /**Function******************************************************************** Synopsis [Gets bounded size blocks from small connected components.] Description [The small connected components are aggregated by 'Static Round Robin Cluster Seed Algorithm(Fixed order of seed and each seed choose the closest connected component)'.] SideEffects [] ******************************************************************************/ static array_t * PartAggregating( array_t *arrayOfSmall, float *arrayOfAffinity, Part_SubsystemInfo_t *partSubInfo, st_table *ptrToIndex) { float *arrayOfGroupAff; array_t *result; array_t *arraySeed; array_t *arraySeedIndex; array_t *arrayTemp; array_t *arrayRow; array_t *cc; array_t *ccCheck; array_t *seed; int i, j; int count; /* total number of vertices in all small connected components */ int pick, keepInd; int seedLast, seedNew, seedIndex; int numberOfSeed; boolean isDone; array_t *keep = array_alloc(int, 0); count = 0; arrayForEachItem(array_t *, arrayOfSmall, i, cc) { count += array_n(cc); } numberOfSeed = (int) ceil((double)count/(double)partSubInfo->bound); arrayOfGroupAff = PartGetGroupMatrixSym(arrayOfSmall, arrayOfAffinity, ptrToIndex); if (partSubInfo->verbosity >= 2) { fprintf(vis_stdout, "\nGrouping: Group affinity of initial "); fprintf(vis_stdout, "connected component\n"); fprintf(vis_stdout, "------------------------------------"); fprintf(vis_stdout, "-------------------\n"); PartPrintArrayArray(arrayOfGroupAff, array_n(arrayOfSmall), 0); } ccCheck = array_alloc(int, array_n(arrayOfSmall)); for (i = 0; i < array_n(arrayOfSmall); i++) { array_insert(int, ccCheck, i, 0); } /* * The first seed is the cc which has minmum support and the next * is the farthest cc */ seedLast = PartSelectCCIndexOfMinSupport(arrayOfSmall, ccCheck, partSubInfo); result = array_alloc(array_t *, numberOfSeed); arraySeed = array_alloc(array_t *, numberOfSeed); arraySeedIndex = array_alloc(int, numberOfSeed); for (i = 0; i < numberOfSeed; i++) { seed = array_fetch(array_t *, arrayOfSmall, seedLast); array_insert(array_t *, arraySeed, i, seed); array_insert(int, arraySeedIndex, i, seedLast); array_insert(array_t *, result, i, seed); if (ibound) { array_append(arrayRow, arrayTemp); array_free(arrayTemp); isDone = FALSE; } else { /* * If pick cc is too big to be appended to seed, find new cc */ array_insert_last(int, keep, pick); pick = PartSelectCloseCCIndex(seedIndex, arrayOfSmall, arrayOfGroupAff, ccCheck); while (pick != -1) { arrayTemp = array_fetch(array_t *, arrayOfSmall, pick); if (array_n(array_fetch(array_t *, arrayOfSmall, seedIndex)) + array_n(arrayTemp) <= partSubInfo->bound) { array_append(arrayRow, arrayTemp); array_free(arrayTemp); isDone = FALSE; break; } else { array_insert_last(int, keep, pick); pick = PartSelectCloseCCIndex(seedIndex, arrayOfSmall, arrayOfGroupAff, ccCheck); } } /* end while */ if (pick == -1) { count--; } arrayForEachItem(int, keep, j, keepInd) { array_insert(int, ccCheck, keepInd, 0); } array_free(keep); keep = array_alloc(int, 0); } /* end if */ } else { count--; }/* end if */ }/* end arrayForEachItem */ /* * If all seeds fail to find suitable cc and not all cc is assigned, * get a new seed. */ if (count < array_n(arrayOfSmall) && isDone) { seedIndex = PartSelectCCIndexOfMinSupport(arrayOfSmall, ccCheck, partSubInfo); count++; seed = array_fetch(array_t *, arrayOfSmall, seedIndex); array_insert_last(array_t *, arraySeed, seed); array_insert_last(int, arraySeedIndex, seedIndex); array_insert_last(array_t *, result, seed); isDone = FALSE; } } array_free(arraySeed); array_free(arraySeedIndex); array_free(keep); array_free(ccCheck); FREE(arrayOfGroupAff); return result; } /**Function******************************************************************** Synopsis [Select the closest node from seed and return node pointer] SideEffects [The Corresponding flag of ccCheck is set after selection] ******************************************************************************/ static Ntk_Node_t * PartSelectCloseNode( Ntk_Node_t *seed, array_t *arrayOfCC, array_t *ccCheck, float *arrayOfAffinity, st_table *ptrToIndex) { int i; float affinity; float big; /* The bigest value of affinity of vertecies*/ int bigInd; /* the index of node with the biggest affinity */ int col; int row; Ntk_Node_t *node, *pick; big = -1.0; bigInd = 0; /* to avoid warning */ pick = NIL(Ntk_Node_t); st_lookup_int(ptrToIndex, (char *)seed, &row); arrayForEachItem(Ntk_Node_t *, arrayOfCC, i, node) { if (array_fetch(int, ccCheck, i) != 1) { st_lookup_int(ptrToIndex, (char *)node, &col); affinity = PartGetElementFromSymMatrix(arrayOfAffinity, row, col); if (affinity > big) { big = affinity; pick = node; bigInd = i; } } } array_insert(int, ccCheck, bigInd, 1); return pick; } /**Function******************************************************************** Synopsis [Select the closest seed from node and return seed index] SideEffects [] ******************************************************************************/ static int PartSelectCloseSeedIndex( Ntk_Node_t *variable, array_t *arrayOfSeed, float *arrayOfAffinity, st_table *ptrToIndex, array_t *seedFull, int bound) { float affinity; int i; float big; int pick, row, col; Ntk_Node_t *node; big = -1.0; pick = -1; st_lookup_int(ptrToIndex, (char *)variable, &row); arrayForEachItem(Ntk_Node_t *, arrayOfSeed, i, node) { st_lookup_int(ptrToIndex, (char *)node, &col); affinity = PartGetElementFromSymMatrix(arrayOfAffinity, row, col); if (affinity > big && array_fetch(int, seedFull, i) < bound) { big = affinity; pick = i; } } array_insert(int, seedFull, pick, array_fetch(int, seedFull, pick) + 1); return pick; } /**Function******************************************************************** Synopsis [Select the farthest node from seed and return node pointer] SideEffects [The Corresponding flag of ccCheck is set after selection] ******************************************************************************/ static Ntk_Node_t * PartSelectFarNode( Ntk_Node_t *seed, array_t *cc, array_t *ccCheck, float *arrayOfAffinity, st_table *ptrToIndex) { float affinity; int i; float small; /* the smallest affinity of vertecies */ int smallInd; /* index of vertex with the smallest affinity */ int col; int row; Ntk_Node_t *node, *pick; small = (float)BIG_NUMBER; smallInd = 0; /* to avoid warning */ pick = NIL(Ntk_Node_t); st_lookup_int(ptrToIndex, (char *)seed, &row); arrayForEachItem(Ntk_Node_t *, cc, i, node) { if (array_fetch(int, ccCheck, i) != 1) { st_lookup_int(ptrToIndex, (char *)node, &col); affinity = PartGetElementFromSymMatrix(arrayOfAffinity, row, col); if (affinity < small) { small = affinity; pick = node; smallInd = i; } } } array_insert(int, ccCheck, smallInd, 1); return pick; } /**Function******************************************************************** Synopsis [Get group matrix as regular matrix from given matrix according to the given clusters] Description [Get matrix relation between each cluster, the values beetween each cluster are added] SideEffects [] ******************************************************************************/ static float * PartGetGroupMatrixRegular( array_t *arrayOfCluster, char *arrayOfGivenMatrix, st_table *ptrToIndex, int nVertices) { float *arrayOfGroupMatrix; /* final result */ array_t *arrayClusterRow; array_t *arrayClusterCol; float subSum; int row, col, i, j, k, l; Ntk_Node_t *nodeRow, *nodeCol; int index, size; size = array_n(arrayOfCluster); arrayOfGroupMatrix = ALLOC(float, size * size); arrayForEachItem(array_t *, arrayOfCluster, i, arrayClusterRow) { arrayForEachItem(array_t *, arrayOfCluster, j, arrayClusterCol) { if (i != j) { subSum = 0.0; arrayForEachItem(Ntk_Node_t *, arrayClusterRow, k, nodeRow) { st_lookup_int(ptrToIndex, (char *)nodeRow, &row); arrayForEachItem(Ntk_Node_t *, arrayClusterCol, l, nodeCol) { st_lookup_int(ptrToIndex, (char *)nodeCol, &col); index = row * nVertices + col; if (arrayOfGivenMatrix[index] == 1) subSum += 1.0; } } index = i * size + j; arrayOfGroupMatrix[index] = subSum / (float)(array_n(arrayClusterRow) * array_n(arrayClusterCol)); } else { index = i * size + j; arrayOfGroupMatrix[index] = 0.0; } } } return arrayOfGroupMatrix; } /**Function******************************************************************** Synopsis [Get group matrix as symetric matrix from given matrix according to the given clusters] Description [Get matrix relation between each cluster, the values beetween each cluster are added] SideEffects [] ******************************************************************************/ static float * PartGetGroupMatrixSym( array_t *arrayOfCluster, float *arrayOfGivenMatrix, st_table *ptrToIndex) { float *arrayOfGroupMatrix; /* final result */ array_t *arrayClusterRow; array_t *arrayClusterCol; float subSum; int row, col, i, j, k, l; Ntk_Node_t *nodeRow, *nodeCol; int index, size; size = array_n(arrayOfCluster); arrayOfGroupMatrix = ALLOC(float, size * (size - 1) / 2); for (i = 0; i < size; i++) { arrayClusterRow = array_fetch(array_t *, arrayOfCluster, i); for (j = 0; j < i; j++) { arrayClusterCol = array_fetch(array_t *, arrayOfCluster, j); if (i == j) { index = i * (i - 1) / 2 + j; arrayOfGroupMatrix[index] = 0.0; } else { subSum = 0.0; arrayForEachItem(Ntk_Node_t *, arrayClusterRow, k, nodeRow) { st_lookup_int(ptrToIndex, (char *)nodeRow, &row); arrayForEachItem(Ntk_Node_t *, arrayClusterCol, l, nodeCol) { st_lookup_int(ptrToIndex, (char *)nodeCol, &col); subSum += PartGetElementFromSymMatrix(arrayOfGivenMatrix, row, col); } } index = i * (i - 1) / 2 + j; arrayOfGroupMatrix[index] = subSum / (float)((array_n(arrayClusterRow)) * array_n(arrayClusterCol)); } } } return arrayOfGroupMatrix; } /**Function******************************************************************** Synopsis [Select a connected component with minimum support variables] SideEffects [The Corresponding flag of ccCheck is set after selection] ******************************************************************************/ static int PartSelectCCIndexOfMinSupport( array_t *arrayOfSmall, array_t *ccCheck, Part_SubsystemInfo_t *partSubInfo) { array_t *cc; array_t *support; int i, count, minCount, minIndex; minCount = BIG_NUMBER; minIndex = -1; for (i = 0; i < array_n(ccCheck); i++) { if (array_fetch(int, ccCheck, i) != 1) { cc = array_fetch(array_t *, arrayOfSmall, i); support = Ntk_NodeComputeCombinationalSupport( partSubInfo->network, cc, TRUE); count = array_n(support); array_free(support); if (count < minCount) { minIndex = i; minCount = count; } } } if (minIndex != -1) { array_insert(int, ccCheck, minIndex, 1); } return minIndex; } /**Function******************************************************************** Synopsis [Select a node with minimum support variables in network node set cc] SideEffects [The Corresponding flag of ccCheck is set after selection] ******************************************************************************/ static Ntk_Node_t * PartSelectNodeOfMinSupport( array_t *cc, array_t *ccCheck, Part_SubsystemInfo_t *partSubInfo) { array_t *support; array_t *nodeArray; int i, minInd, count, min; Ntk_Node_t *node; Ntk_Node_t *minNode = NIL(Ntk_Node_t); if (array_n(cc) == 0) { return NIL(Ntk_Node_t); } min = BIG_NUMBER; minInd = 0; /* to avoid warning */ arrayForEachItem(Ntk_Node_t *, cc, i, node) { if (array_fetch(int, ccCheck, i) != 1) { nodeArray = array_alloc(Ntk_Node_t *, 1); array_insert(Ntk_Node_t *, nodeArray, 0, node); support = Ntk_NodeComputeCombinationalSupport( partSubInfo->network, nodeArray, TRUE); count = array_n(support); if (count < min) { minNode = node; min = count; minInd = i; } array_free(support); array_free(nodeArray); } } array_insert(int, ccCheck, minInd, 1); return minNode; } /**Function******************************************************************** Synopsis [Select an index of connected component from seed connected component] SideEffects [The Corresponding flag of ccCheck is set after selection] ******************************************************************************/ static int PartSelectFarCCIndex( int seedIndex, array_t *arrayOfSmall, float *arrayOfGroupAff, Part_SubsystemInfo_t *partSubInfo, array_t *ccCheck) { array_t *col; int i; float groupAff; float min; int minIndex; min = (float)BIG_NUMBER; minIndex = -1; arrayForEachItem(array_t *, arrayOfSmall, i, col) { if (array_fetch(int, ccCheck, i) != 1) { groupAff = PartGetElementFromSymMatrix(arrayOfGroupAff, seedIndex, i); if (groupAff < min) { minIndex = i; min = groupAff; } } } if (minIndex != -1) { array_insert(int, ccCheck, minIndex, 1); } return minIndex; } /**Function******************************************************************** Synopsis [Select an index of closest connected component from seed connected component] SideEffects [] ******************************************************************************/ static int PartSelectCloseCCIndex( int seedIndex, array_t *arrayOfSmall, float *arrayOfGroupAff, array_t *ccCheck) { int i; float groupAff; float max; int maxIndex; max = -1.0; maxIndex = -1; for (i = 0; i < array_n(ccCheck); i++) { if (array_fetch(int, ccCheck, i) != 1) { groupAff = PartGetElementFromSymMatrix(arrayOfGroupAff, seedIndex, i); if (groupAff > max) { maxIndex = i; max = groupAff; } } } if (maxIndex != -1) { array_insert(int, ccCheck, maxIndex, 1); } return maxIndex; } /**Function******************************************************************** Synopsis [Create a sub-system with given latch-data-input nodes] SideEffects [] SeeAlso [] ******************************************************************************/ static Part_Subsystem_t* PartCreateSingleSubSystem( array_t *arrayOfNodes, Ntk_Network_t *network) { int i, j; char *name; Ntk_Node_t *node; st_table *vertexNameTable; array_t *arrayOfLatchNames; Part_Subsystem_t *sub; if (array_n(arrayOfNodes) == 0 || arrayOfNodes == NIL(array_t)) { return NIL(Part_Subsystem_t); } vertexNameTable = st_init_table(strcmp, st_strhash); arrayForEachItem(Ntk_Node_t *, arrayOfNodes, i, node) { arrayOfLatchNames = PartReadLatchNameFromLatchInput(network, node); arrayForEachItem(char *, arrayOfLatchNames, j, name) { st_insert(vertexNameTable, (char *)name, (char *)NULL); } array_free(arrayOfLatchNames); } sub = ALLOC(Part_Subsystem_t, 1); sub->vertexNameTable = vertexNameTable; sub->subsystemFanIn = NIL(array_t); sub->subsystemFanOut = NIL(array_t); return sub; } /**Function******************************************************************** Synopsis [Gets Latch Name from Latch Data Input] SideEffects [] SeeAlso [] ******************************************************************************/ static array_t * PartReadLatchNameFromLatchInput( Ntk_Network_t *network, Ntk_Node_t *latchInput) { lsGen gen; Ntk_Node_t *latch, *temp1; char *latchName = NIL(char); array_t *arrayOfLatchNames; arrayOfLatchNames = array_alloc(char *, 0); Ntk_NetworkForEachLatch(network, gen, latch) { temp1 = Ntk_LatchReadDataInput(latch); if (temp1 == latchInput) { latchName = Ntk_NodeReadName(latch); array_insert_last(char *, arrayOfLatchNames, latchName); } } /* end of Ntk_NetworkForEachLatch */ return arrayOfLatchNames; } /**Function******************************************************************** Synopsis [Free array of array] SideEffects [] ******************************************************************************/ static void PartArrayOfArrayFree( array_t *arrayOfMatrix) { array_t *arrayRow; int i; arrayForEachItem(array_t *, arrayOfMatrix, i, arrayRow) { array_free(arrayRow); } array_free(arrayOfMatrix); } /**Function******************************************************************** Synopsis [Get matrix(i,j) from symetric matrix] SideEffects [] ******************************************************************************/ static float PartGetElementFromSymMatrix( float *matrix, int i, int j) { int index; if (i == j) return(0.0); if (i < j) { int tmp; tmp = i; i = j; j = tmp; } index = i * (i - 1) / 2 + j; return(matrix[index]); } /**Function******************************************************************** Synopsis [Print array of array] Description [If type is 0, arrayArray is float regular matrix. If type = 1, arrayArray is char type symertic matrix.] SideEffects [] ******************************************************************************/ static void PartPrintArrayArray( void *arrayArray, int nVertices, int type) { int i, j; float num; int index; if (type == 0) { /* numerical data * symetric matrix */ for (i = 0; i < nVertices; i++) { for (j = 0; j < nVertices; j++) { num = PartGetElementFromSymMatrix((float *)arrayArray, i, j); fprintf(vis_stdout, "%4.3f ", num); } fprintf(vis_stdout, "\n"); } } else if (type == 1) { /* char data & regular */ for (i = 0; i < nVertices; i++) { for (j = 0; j < nVertices; j++) { index = i * nVertices + j; if (((char *)arrayArray)[index] == 1) { fprintf(vis_stdout, "1 "); } else { fprintf(vis_stdout, "0 "); } } fprintf(vis_stdout, "\n"); } } fprintf(vis_stdout, "\n"); } /**Function******************************************************************** Synopsis [Compare procedure for string comparison.] Description [Compare procedure for string comparison.] SideEffects [] ******************************************************************************/ static int strCompare( const void *name1, const void *name2) { return(strcmp(*(char **)name1, *(char **)name2)); } /* end of strCompare */ /**Function******************************************************************** Synopsis [Compare procedure for number comparison.] Description [Compare procedure for number comparison.] SideEffects [] ******************************************************************************/ static int numCompare( const void *num1, const void *num2) { return(*(int *)num1 > *(int *)num2); } /* end of strCompare */