#include "partInt.h"
Include dependency graph for partGroup.c:
Go to the source code of this file.
Functions | |
| 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) |
| array_t * | Part_PartGroupVeriticesBasedOnHierarchy (Ntk_Network_t *network, array_t *latchDataInputNames) |
| array_t * | Part_PartCreateSubsystems (Part_SubsystemInfo_t *subInfo, array_t *arrayOfLatchNames, array_t *arrayOfGroupIndex) |
| array_t * | Part_PartCreateSubsystemsWithCTL (Part_SubsystemInfo_t *subInfo, array_t *ctlArray, array_t *fairArray, boolean dynamicIncrease, boolean dynamicAndDependency) |
| array_t * | Part_PartCreateSubsystemsWithCtlAndLtl (Part_SubsystemInfo_t *subInfo, array_t *ctlArray, array_t *ltlArray, array_t *fairArray, boolean dynamicIncrease, boolean dynamicAndDependency, boolean strictBound) |
| st_table * | Part_PartitionSubsystemReadVertexTable (Part_Subsystem_t *partitionedSubsystem) |
| array_t * | Part_PartitionSubsystemReadFanIn (Part_Subsystem_t *partitionedSubsystem) |
| array_t * | Part_PartitionSubsystemReadFanOut (Part_Subsystem_t *partitionedSubsystem) |
| Part_SubsystemInfo_t * | Part_PartitionSubsystemInfoInit (Ntk_Network_t *network) |
| void | Part_PartitionSubsystemInfoFree (Part_SubsystemInfo_t *partSubInfo) |
| void | Part_PartitionSubsystemFree (Part_Subsystem_t *partSubsystem) |
| void | Part_PartitionSubsystemInfoSetBreakingMethod (Part_SubsystemInfo_t *subInfo, Part_BMethod bMethod) |
| void | Part_PartitionSubsystemInfoSetBound (Part_SubsystemInfo_t *subInfo, int bound) |
| void | Part_PartitionSubsystemInfoSetThreshold (Part_SubsystemInfo_t *subInfo, float threshold) |
| void | Part_PartitionSubsystemInfoSetVerbosity (Part_SubsystemInfo_t *subInfo, int verbosity) |
| void | Part_PartitionSubsystemInfoSetCorrelationMethod (Part_SubsystemInfo_t *subInfo, Part_CMethod corMethod) |
| void | Part_PartitionSubsystemInfoSetAffinityFactor (Part_SubsystemInfo_t *subInfo, float affinity) |
| Part_Subsystem_t * | Part_PartCreateSingleSubSystem (array_t *arrayOfNodes, Ntk_Network_t *network) |
| array_t * | PartCreateSubsystem (Part_SubsystemInfo_t *partSubInfo, array_t *arrayOfLatchNames, array_t *arrayOfGroupIndex) |
Variables | |
| static char rcsid[] | UNUSED = "$Id: partGroup.c,v 1.51 2005/04/28 14:15:50 fabio Exp $" |
Function Documentation
| static int numCompare | ( | const void * | num1, |
| const void * | num2 | ||
| ) | [static] |
Function********************************************************************
Synopsis [Compare procedure for number comparison.]
Description [Compare procedure for number comparison.]
SideEffects []
Definition at line 3325 of file partGroup.c.
{
return(*(int *)num1 > *(int *)num2);
} /* end of strCompare */
Here is the caller graph for this function:
| Part_Subsystem_t* Part_PartCreateSingleSubSystem | ( | array_t * | arrayOfNodes, |
| Ntk_Network_t * | network | ||
| ) |
Function********************************************************************
Synopsis [Create a sub-system with given latch data input in arrayOfNodes]
SideEffects []
SeeAlso []
Definition at line 785 of file partGroup.c.
{
return PartCreateSingleSubSystem(arrayOfNodes, network);
}
Here is the call graph for this function:
| array_t* Part_PartCreateSubsystems | ( | Part_SubsystemInfo_t * | subInfo, |
| array_t * | arrayOfLatchNames, | ||
| array_t * | arrayOfGroupIndex | ||
| ) |
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 []
Definition at line 454 of file partGroup.c.
{
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));
}
Here is the call graph for this function:
Here is the caller graph for this function:
| array_t* Part_PartCreateSubsystemsWithCTL | ( | Part_SubsystemInfo_t * | subInfo, |
| array_t * | ctlArray, | ||
| array_t * | fairArray, | ||
| boolean | dynamicIncrease, | ||
| boolean | 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 []
Definition at line 492 of file partGroup.c.
{
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));
}
Here is the call graph for this function:
Here is the caller graph for this function:
| array_t* Part_PartCreateSubsystemsWithCtlAndLtl | ( | Part_SubsystemInfo_t * | subInfo, |
| array_t * | ctlArray, | ||
| array_t * | ltlArray, | ||
| array_t * | fairArray, | ||
| boolean | dynamicIncrease, | ||
| boolean | dynamicAndDependency, | ||
| boolean | strictBound | ||
| ) |
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 []
Definition at line 522 of file partGroup.c.
{
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));
}
Here is the call graph for this function:
Here is the caller graph for this function:
| array_t* Part_PartGroupVeriticesBasedOnHierarchy | ( | Ntk_Network_t * | network, |
| array_t * | latchDataInputNames | ||
| ) |
AutomaticEnd 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 []
Definition at line 145 of file partGroup.c.
{
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);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| void Part_PartitionSubsystemFree | ( | Part_Subsystem_t * | partSubsystem | ) |
Function********************************************************************
Synopsis [Free subsystem structure for partitioning subsystem]
SideEffects []
SeeAlso [Part_Subsystem]
Definition at line 660 of file partGroup.c.
{
st_free_table(partSubsystem->vertexNameTable);
array_free(partSubsystem->subsystemFanIn);
array_free(partSubsystem->subsystemFanOut);
FREE(partSubsystem);
}
Here is the caller graph for this function:
| void Part_PartitionSubsystemInfoFree | ( | Part_SubsystemInfo_t * | partSubInfo | ) |
Function********************************************************************
Synopsis [Free info structure for partitioning subsystem]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 632 of file partGroup.c.
{
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);
}
Here is the caller graph for this function:
| Part_SubsystemInfo_t* Part_PartitionSubsystemInfoInit | ( | Ntk_Network_t * | network | ) |
Function********************************************************************
Synopsis [Initialize info structure for partitioning subsystem]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 596 of file partGroup.c.
{
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);
}
Here is the caller graph for this function:
| void Part_PartitionSubsystemInfoSetAffinityFactor | ( | Part_SubsystemInfo_t * | subInfo, |
| float | affinity | ||
| ) |
Function********************************************************************
Synopsis [Set affinity factor]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 767 of file partGroup.c.
{
subInfo->aff_factor = affinity;
}
Here is the caller graph for this function:
| void Part_PartitionSubsystemInfoSetBound | ( | Part_SubsystemInfo_t * | subInfo, |
| int | bound | ||
| ) |
Function********************************************************************
Synopsis [Set bound of subsystem info]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 697 of file partGroup.c.
{
subInfo->bound = bound;
}
Here is the caller graph for this function:
| void Part_PartitionSubsystemInfoSetBreakingMethod | ( | Part_SubsystemInfo_t * | subInfo, |
| Part_BMethod | bMethod | ||
| ) |
Function********************************************************************
Synopsis [Set breaking method of subsystem info]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 679 of file partGroup.c.
{
subInfo->partBM = bMethod;
}
| void Part_PartitionSubsystemInfoSetCorrelationMethod | ( | Part_SubsystemInfo_t * | subInfo, |
| Part_CMethod | corMethod | ||
| ) |
Function********************************************************************
Synopsis [Set method for correlation]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 750 of file partGroup.c.
{
subInfo->corMethod = corMethod;
}
Here is the caller graph for this function:
| void Part_PartitionSubsystemInfoSetThreshold | ( | Part_SubsystemInfo_t * | subInfo, |
| float | threshold | ||
| ) |
Function********************************************************************
Synopsis [Set threshold of subsystem info]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 714 of file partGroup.c.
{
subInfo->threshold = threshold;
}
| void Part_PartitionSubsystemInfoSetVerbosity | ( | Part_SubsystemInfo_t * | subInfo, |
| int | verbosity | ||
| ) |
Function********************************************************************
Synopsis [Set verbosity of subsystem info]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 732 of file partGroup.c.
{
subInfo->verbosity = verbosity;
}
Here is the caller graph for this function:
| array_t* Part_PartitionSubsystemReadFanIn | ( | Part_Subsystem_t * | partitionedSubsystem | ) |
Function********************************************************************
Synopsis [Read fan-in array attached to partitioned subsystem]
SideEffects []
Definition at line 565 of file partGroup.c.
{
return(partitionedSubsystem->subsystemFanIn);
}
Here is the caller graph for this function:
| array_t* Part_PartitionSubsystemReadFanOut | ( | Part_Subsystem_t * | partitionedSubsystem | ) |
Function********************************************************************
Synopsis [Read fan-out array attached to partitioned subsystem]
SideEffects []
Definition at line 579 of file partGroup.c.
{
return(partitionedSubsystem->subsystemFanOut);
}
Here is the caller graph for this function:
| st_table* Part_PartitionSubsystemReadVertexTable | ( | Part_Subsystem_t * | partitionedSubsystem | ) |
Function********************************************************************
Synopsis [Read the table attached to a partitioned subsystem.]
SideEffects []
Definition at line 551 of file partGroup.c.
{
return(partitionedSubsystem->vertexNameTable);
}
Here is the caller graph for this function:
| static array_t * PartAggregating | ( | array_t * | arrayOfSmall, |
| float * | arrayOfAffinity, | ||
| Part_SubsystemInfo_t * | partSubInfo, | ||
| st_table * | ptrToIndex | ||
| ) | [static] |
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 []
Definition at line 2589 of file partGroup.c.
{
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 (i<numberOfSeed-1) {
seedNew = PartSelectFarCCIndex(seedLast, arrayOfSmall, arrayOfGroupAff,
partSubInfo, ccCheck);
seedLast = seedNew;
}
}
/*
* Static Round Robin Cluster Seed: Fixed order of seed and each seed
* choose the closest connected component
*/
isDone = FALSE;
count = array_n(arraySeed);
while ((!isDone) && count < array_n(arrayOfSmall)) {
isDone = TRUE;
arrayForEachItem(int, arraySeedIndex, i, seedIndex) {
arrayRow = array_fetch(array_t *, result, i);
pick = PartSelectCloseCCIndex(seedIndex, arrayOfSmall,
arrayOfGroupAff, ccCheck);
count++;
/* check if not all cc is assigned */
if (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;
} 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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static void PartArrayOfArrayFree | ( | array_t * | arrayOfMatrix | ) | [static] |
Function********************************************************************
Synopsis [Free array of array]
SideEffects []
Definition at line 3214 of file partGroup.c.
{
array_t *arrayRow;
int i;
arrayForEachItem(array_t *, arrayOfMatrix, i, arrayRow) {
array_free(arrayRow);
}
array_free(arrayOfMatrix);
}
Here is the caller graph for this function:
| static array_t * PartBreakingAggregating | ( | array_t * | arrayOfInit, |
| float * | arrayOfAffinity, | ||
| Part_SubsystemInfo_t * | partSubInfo, | ||
| st_table * | ptrToIndex, | ||
| char * | arrayOfDependency | ||
| ) | [static] |
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 []
Definition at line 2105 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static array_t * PartBreakingBigConnectedComponent | ( | array_t * | arrayOfCC, |
| array_t * | ccCheck, | ||
| array_t * | arrayOfSeed, | ||
| float * | arrayOfAffinity, | ||
| Part_SubsystemInfo_t * | partSubInfo, | ||
| st_table * | ptrToIndex | ||
| ) | [static] |
Function********************************************************************
Synopsis [Gets bounded size blocks from big CC, Breaking]
Description [Gets bounded size blocks from big connected component]
SideEffects []
SeeAlso []
Definition at line 2499 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static float * PartCreateAffinityMatrix | ( | char * | arrayOfDependency, |
| float * | arrayOfCorrelation, | ||
| Part_SubsystemInfo_t * | partSubInfo | ||
| ) | [static] |
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]
Definition at line 1856 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static float * PartCreateCorrelationMatrixFromBDD | ( | Part_SubsystemInfo_t * | partSubInfo | ) | [static] |
Function********************************************************************
Synopsis [Create the latch Correlation Matrix]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 1708 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static float * PartCreateCorrelationMatrixFromSupport | ( | Part_SubsystemInfo_t * | partSubInfo | ) | [static] |
Function********************************************************************
Synopsis [Create the latch Correlation Matrix]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 1647 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static char * PartCreateDependencyMatrix | ( | Part_SubsystemInfo_t * | partSubInfo, |
| st_table * | ptrToIndex | ||
| ) | [static] |
AutomaticStart
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 []
Definition at line 1596 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static Part_Subsystem_t * PartCreateSingleSubSystem | ( | array_t * | arrayOfNodes, |
| Ntk_Network_t * | network | ||
| ) | [static] |
Function********************************************************************
Synopsis [Create a sub-system with given latch-data-input nodes]
SideEffects []
SeeAlso []
Definition at line 3145 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| array_t* PartCreateSubsystem | ( | Part_SubsystemInfo_t * | partSubInfo, |
| array_t * | arrayOfLatchNames, | ||
| array_t * | arrayOfGroupIndex | ||
| ) |
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]
Definition at line 820 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static array_t * PartCreateSubsystemWithCTL | ( | Part_SubsystemInfo_t * | partSubInfo, |
| array_t * | ctlArray, | ||
| array_t * | fairArray, | ||
| boolean | dynamicIncrease, | ||
| boolean | dynamicAndDependency | ||
| ) | [static] |
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]
Definition at line 1147 of file partGroup.c.
{
return PartCreateSubsystemWithCtlAndLtl(partSubInfo, ctlArray, NIL(array_t),
fairArray, dynamicIncrease,
dynamicAndDependency, FALSE);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static array_t * PartCreateSubsystemWithCtlAndLtl | ( | Part_SubsystemInfo_t * | partSubInfo, |
| array_t * | ctlArray, | ||
| array_t * | ltlArray, | ||
| array_t * | fairArray, | ||
| boolean | dynamicIncrease, | ||
| boolean | dynamicAndDependency, | ||
| boolean | strictBound | ||
| ) | [static] |
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]
Definition at line 1182 of file partGroup.c.
{
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;i<partSubInfo->numberOfVertex;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; i<partSubInfo->numberOfVertex; 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;j<partSubInfo->numberOfVertex;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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static array_t * PartCreateSubSystemWithGroupIndex | ( | Part_SubsystemInfo_t * | partSubInfo, |
| array_t * | arrayOfLatchNames, | ||
| array_t * | arrayOfGroupIndex | ||
| ) | [static] |
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 []
Definition at line 2339 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static void PartFindCC | ( | int * | next, |
| int * | ccId, | ||
| array_t * | arrayOfCCIndex, | ||
| float * | arrayOfAffinity, | ||
| array_t * | arrayOfFrom, | ||
| Part_SubsystemInfo_t * | partSubInfo | ||
| ) | [static] |
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 []
Definition at line 2021 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static array_t * PartGetConnectedComponent | ( | float * | arrayOfAffinity, |
| Part_SubsystemInfo_t * | partSubInfo, | ||
| st_table * | indexToPtr | ||
| ) | [static] |
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 []
Definition at line 1918 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static float PartGetElementFromSymMatrix | ( | float * | matrix, |
| int | i, | ||
| int | j | ||
| ) | [static] |
Function********************************************************************
Synopsis [Get matrix(i,j) from symetric matrix]
SideEffects []
Definition at line 3234 of file partGroup.c.
{
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]);
}
Here is the caller graph for this function:
| static float * PartGetGroupMatrixRegular | ( | array_t * | arrayOfCluster, |
| char * | arrayOfGivenMatrix, | ||
| st_table * | ptrToIndex, | ||
| int | nVertices | ||
| ) | [static] |
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 []
Definition at line 2877 of file partGroup.c.
{
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;
}
Here is the caller graph for this function:
| static float * PartGetGroupMatrixSym | ( | array_t * | arrayOfCluster, |
| float * | arrayOfGivenMatrix, | ||
| st_table * | ptrToIndex | ||
| ) | [static] |
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 []
Definition at line 2931 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static void PartPrintArrayArray | ( | void * | arrayArray, |
| int | nVertices, | ||
| int | type | ||
| ) | [static] |
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 []
Definition at line 3265 of file partGroup.c.
{
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");
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static array_t * PartReadLatchNameFromLatchInput | ( | Ntk_Network_t * | network, |
| Ntk_Node_t * | latchInput | ||
| ) | [static] |
Function********************************************************************
Synopsis [Gets Latch Name from Latch Data Input]
SideEffects []
SeeAlso []
Definition at line 3185 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static int PartSelectCCIndexOfMinSupport | ( | array_t * | arrayOfSmall, |
| array_t * | ccCheck, | ||
| Part_SubsystemInfo_t * | partSubInfo | ||
| ) | [static] |
Function********************************************************************
Synopsis [Select a connected component with minimum support variables]
SideEffects [The Corresponding flag of ccCheck is set after selection]
Definition at line 2980 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static int PartSelectCloseCCIndex | ( | int | seedIndex, |
| array_t * | arrayOfSmall, | ||
| float * | arrayOfGroupAff, | ||
| array_t * | ccCheck | ||
| ) | [static] |
Function********************************************************************
Synopsis [Select an index of closest connected component from seed connected component]
SideEffects []
Definition at line 3106 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static Ntk_Node_t * PartSelectCloseNode | ( | Ntk_Node_t * | seed, |
| array_t * | arrayOfCC, | ||
| array_t * | ccCheck, | ||
| float * | arrayOfAffinity, | ||
| st_table * | ptrToIndex | ||
| ) | [static] |
Function********************************************************************
Synopsis [Select the closest node from seed and return node pointer]
SideEffects [The Corresponding flag of ccCheck is set after selection]
Definition at line 2745 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static int PartSelectCloseSeedIndex | ( | Ntk_Node_t * | variable, |
| array_t * | arrayOfSeed, | ||
| float * | arrayOfAffinity, | ||
| st_table * | ptrToIndex, | ||
| array_t * | seedFull, | ||
| int | bound | ||
| ) | [static] |
Function********************************************************************
Synopsis [Select the closest seed from node and return seed index]
SideEffects []
Definition at line 2789 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static int PartSelectFarCCIndex | ( | int | seedIndex, |
| array_t * | arrayOfSmall, | ||
| float * | arrayOfGroupAff, | ||
| Part_SubsystemInfo_t * | partSubInfo, | ||
| array_t * | ccCheck | ||
| ) | [static] |
Function********************************************************************
Synopsis [Select an index of connected component from seed connected component]
SideEffects [The Corresponding flag of ccCheck is set after selection]
Definition at line 3066 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static Ntk_Node_t * PartSelectFarNode | ( | Ntk_Node_t * | seed, |
| array_t * | cc, | ||
| array_t * | ccCheck, | ||
| float * | arrayOfAffinity, | ||
| st_table * | ptrToIndex | ||
| ) | [static] |
Function********************************************************************
Synopsis [Select the farthest node from seed and return node pointer]
SideEffects [The Corresponding flag of ccCheck is set after selection]
Definition at line 2828 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static Ntk_Node_t * PartSelectNodeOfMinSupport | ( | array_t * | cc, |
| array_t * | ccCheck, | ||
| Part_SubsystemInfo_t * | partSubInfo | ||
| ) | [static] |
Function********************************************************************
Synopsis [Select a node with minimum support variables in network node set cc]
SideEffects [The Corresponding flag of ccCheck is set after selection]
Definition at line 3020 of file partGroup.c.
{
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;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static array_t * PartVertexComputeAgreement | ( | mdd_manager * | mddMgr, |
| int | index1, | ||
| int | index2, | ||
| array_t * | arrayOfMddArray | ||
| ) | [static] |
Function********************************************************************
Synopsis [Gets the latch Correlation between two vertices]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 1815 of file partGroup.c.
{
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;
}
Here is the caller graph for this function:
| static float PartVertexComputeCorrelation | ( | int | index1, |
| int | index2, | ||
| array_t * | arrayOfInputSupportTable, | ||
| Part_SubsystemInfo_t * | partSubInfo | ||
| ) | [static] |
Function********************************************************************
Synopsis [Gets the latch Correlation between two vertices]
SideEffects []
SeeAlso [Part_SubsystemInfo]
Definition at line 1767 of file partGroup.c.
{
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;
}
Here is the caller graph for this function:
| static int strCompare | ( | const void * | name1, |
| const void * | name2 | ||
| ) | [static] |
Function********************************************************************
Synopsis [Compare procedure for string comparison.]
Description [Compare procedure for string comparison.]
SideEffects []
Definition at line 3308 of file partGroup.c.
{
return(strcmp(*(char **)name1, *(char **)name2));
} /* end of strCompare */
Here is the caller graph for this function:
Variable Documentation
char rcsid [] UNUSED = "$Id: partGroup.c,v 1.51 2005/04/28 14:15:50 fabio Exp $" [static] |
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.]
Definition at line 47 of file partGroup.c.
