#include "partInt.h"
Include dependency graph for partInOut.c:
Go to the source code of this file.
Functions | |
| graph_t * | Part_CreatePartitionFromMvfs (mdd_manager *manager, st_table *nameToMvf, st_table *nameToId, st_table *leafTable, char *partName) |
| graph_t * | Part_NetworkCreatePartitionFromMvfs (Ntk_Network_t *network, st_table *nameToMvf) |
| void | PartPartitionInputsOutputs (Ntk_Network_t *network, graph_t *partition, lsList rootList, lsList leaveList, mdd_t *careSet) |
| int | PartPartitionInOutChangeRoots (Ntk_Network_t *network, graph_t *partition, lsList rootList, int verbosity) |
Variables | |
| static char rcsid[] | UNUSED = "$Id: partInOut.c,v 1.15 2005/04/16 14:52:45 fabio Exp $" |
Function Documentation
| graph_t* Part_CreatePartitionFromMvfs | ( | mdd_manager * | manager, |
| st_table * | nameToMvf, | ||
| st_table * | nameToId, | ||
| st_table * | leafTable, | ||
| char * | partName | ||
| ) |
AutomaticStart AutomaticEnd Function********************************************************************
Synopsis [Creates the graph representing a set of Mvfs as functions of the variables in the collective support of the specified Mvfs. A copy of the Mvf function is stored in vertex.]
Description [The input nameToMvf is a table which provides the names and the corresponding Mvfs functions. The procedure works as follows. For each function, a vertex in the graph is created. For each variable in the support of a given MVF, a vertex is created (if one doesn't already exist), and an edge is added from the that vertex to that MVF. The support of an MVF is taken as the union of the support of its constituent MDDs. The table nameToId is optional and can be NULL. It provides a map from the name of the MVF to its mddId. leafTable provides the pair (mddId, name) for each variable in the support of the MVFs. partName can be NULL in which case the name of the partition would be "dummy".]
SideEffects []
SeeAlso [Part_NetworkCreatePartition Part_NetworkCreatePartitionFromMvfs]
Definition at line 74 of file partInOut.c.
{
graph_t *partition;
Mvf_Function_t *mddFunction;
vertex_t *toVertex;
lsList sinkList;
lsGen gen;
st_table *mddIdToNodeName;
st_generator *stGen;
char *str;
long mddId;
/* Initialize variables */
mddIdToNodeName = leafTable;
/* Allocate the new partition to be returned */
partition = g_alloc();
if (partName) {
partition->user_data =
(gGeneric)PartPartitionInfoCreate(partName,manager,Part_InOut_c);
} /* End of if */
else {
partition->user_data =
(gGeneric)PartPartitionInfoCreate("dummy",manager,Part_InOut_c);
} /* End of if-then-else */
/* Create vertices for the functions in nameToMvf */
st_foreach_item(nameToMvf,stGen,&str,&mddFunction) {
toVertex = g_add_vertex(partition);
/* Update the look-up tables in the graph */
st_insert(PartPartitionReadNameToVertex(partition),str,toVertex);
if (nameToId) {
if (st_lookup(nameToId, str, &mddId)) {
st_insert(PartPartitionReadMddIdToVertex(partition),
(char *)mddId, toVertex);
} /* End of if */
} /* End of if */
/* Fill in the fields of the data attached to the vertex */
toVertex->user_data =
(gGeneric)PartVertexInfoCreateSingle(str,
Mvf_FunctionDuplicate(mddFunction),
mddId);
}
/* Read the list of vertices on the graph */
sinkList = lsCopy(g_get_vertices(partition), (lsGeneric (*)(lsGeneric))0);
/*
* For every function on every combinational output, compute the
* support and create vertices in the graph when needed
*/
lsForEachItem(sinkList, gen, toVertex) {
st_table *mddSupport; /* Support of the Mvf_Function */
st_generator *stGen; /* To iterate over the MddIds of the support */
vertex_t *fromVertex; /* Holds the current vertex in the support */
/* Obtain an array of mdd_t * */
mddFunction = PartVertexReadFunction(toVertex);
/* Compute the support of the set of mdds*/
mddSupport = PartCreateFunctionSupportTable(mddFunction);
/*
* Create one edge (and one vertex if necessary) for every element
* in mddSupport
*/
st_foreach_item(mddSupport, stGen, &mddId, NULL) {
char *name;
/* Create vertex with the information if needed */
if (st_lookup(PartPartitionReadMddIdToVertex(partition),
(char *)mddId, &fromVertex) == 0) {
fromVertex = g_add_vertex(partition);
st_lookup(mddIdToNodeName, (char *)mddId, &name);
/* Update the look-up tables in the graph */
st_insert(PartPartitionReadNameToVertex(partition),
name, (char *)fromVertex);
st_insert(PartPartitionReadMddIdToVertex(partition),
(char *)(long) mddId, (char *)fromVertex);
/* Create vertex data */
fromVertex->user_data =
(gGeneric)PartVertexInfoCreateSingle(name,
Mvf_FunctionCreateFromVariable(manager,mddId),
mddId);
} /* End of if */
/*
* Add the edge to the graph. Make sure a self loop is not added.
* The self loop may be produced by a mdd that has in its support
* the same variables that represent the mddId of the node.
*/
if (fromVertex != toVertex) {
g_add_edge(fromVertex, toVertex);
} /* End of if */
} /* End of st_foreach_item */
/* Clean the support table */
st_free_table(mddSupport);
} /* End of lsForEachItem */
lsDestroy(sinkList, (void (*)(lsGeneric))0);
return partition;
} /* End of Part_CreatePartitionFromMvfs */
Here is the call graph for this function:
| graph_t* Part_NetworkCreatePartitionFromMvfs | ( | Ntk_Network_t * | network, |
| st_table * | nameToMvf | ||
| ) |
Function********************************************************************
Synopsis [Creates the graph representing the combinational outputs as functions of the combinational inputs given as input a network and Mvf functions representing the combinational outputs. A copy of the Mvf function is stored in vertex.]
Description [The input nameToMvf is a table which provides the names of the nodes and their corresponding Mvfs functions. The procedure works as follows. For each combinational output, a vertex in the graph is created. For each combinational input in the support of a given combinational output MVF, a vertex is created (if one doesn't already exist), and an edge is added from the combinational input to the combinational output. The support of an MVF is taken as the union of the support of its constituent MDDs.]
SideEffects []
SeeAlso [Part_NetworkCreatePartition Part_CreatePartitionFromMvfs]
Definition at line 212 of file partInOut.c.
{
graph_t *partition;
Ntk_Node_t *node;
Mvf_Function_t *mddFunction;
vertex_t *toVertex;
mdd_manager *manager;
lsList sinkList;
lsGen gen;
st_table *mddIdToNodeName;
st_generator *stGen;
char *ntkName;
char *str;
long mddId;
/* Initialize variables */
manager = Ntk_NetworkReadMddManager(network);
ntkName = Ntk_NetworkReadName(network);
/* Allocate the new partition to be returned */
partition = g_alloc();
partition->user_data =
(gGeneric)PartPartitionInfoCreate(ntkName,manager,Part_InOut_c);
/* Create vertices for the functions in nameToMvf */
st_foreach_item(nameToMvf,stGen,&str,&mddFunction) {
node = Ntk_NetworkFindNodeByName(network,str);
if (node == NIL(Ntk_Node_t)) {
fprintf(vis_stderr,"%s has no corresponding node in network \n",
str);
Part_PartitionFree(partition);
return NIL(graph_t);
}
mddId = Ntk_NodeReadMddId(node);
toVertex = g_add_vertex(partition);
/* Update the look-up tables in the graph */
st_insert(PartPartitionReadNameToVertex(partition),str,
(char *)toVertex);
if (mddId != NTK_UNASSIGNED_MDD_ID) {
st_insert(PartPartitionReadMddIdToVertex(partition),
(char *)(long) mddId, (char *)toVertex);
}
/* Fill in the fields of the data attached to the vertex */
toVertex->user_data =
(gGeneric)PartVertexInfoCreateSingle(str,
Mvf_FunctionDuplicate(mddFunction),
mddId);
}
/* Create a table for all the combinational inputs */
mddIdToNodeName = st_init_table(st_numcmp, st_numhash);
Ntk_NetworkForEachCombInput(network, gen, node) {
st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node),
Ntk_NodeReadName(node));
}
/* Read the list of vertices on the graph */
sinkList = lsCopy(g_get_vertices(partition), (lsGeneric (*)(lsGeneric))0);
/*
* For every function on every combinational output, compute the
* support and create vertices in the graph when needed
*/
lsForEachItem(sinkList, gen, toVertex) {
st_table *mddSupport; /* Support of the Mvf_Function */
st_generator *stGen; /* To iterate over the MddIds of the support */
vertex_t *fromVertex; /* Holds the current vertex in the support */
/* Obtain an array of mdd_t * */
mddFunction = PartVertexReadFunction(toVertex);
/* Compute the support of the set of mdds*/
mddSupport = PartCreateFunctionSupportTable(mddFunction);
/*
* Create one edge (and one vertex if necessary) for every element
* in mddSupport
*/
st_foreach_item(mddSupport, stGen, &mddId, NULL) {
char *name;
/* Create vertex with the information if needed */
if (st_lookup(PartPartitionReadMddIdToVertex(partition),
(char *)mddId, &fromVertex) == 0) {
fromVertex = g_add_vertex(partition);
st_lookup(mddIdToNodeName, (char *)mddId, &name);
/* Update the look-up tables in the graph */
st_insert(PartPartitionReadNameToVertex(partition),
name, (char *)fromVertex);
st_insert(PartPartitionReadMddIdToVertex(partition),
(char *)(long) mddId, (char *)fromVertex);
/* Create vertex data */
fromVertex->user_data =
(gGeneric)PartVertexInfoCreateSingle(name,
Mvf_FunctionCreateFromVariable(manager,mddId),
mddId);
} /* End of if */
/*
* Add the edge to the graph. Make sure a self loop is not added.
* The self loop may be produced by a mdd that has in its support
* the same variables that represent the mddId of the node.
*/
if (fromVertex != toVertex) {
g_add_edge(fromVertex, toVertex);
} /* End of if */
} /* End of st_foreach_item */
/* Clean the support table */
st_free_table(mddSupport);
} /* End of lsForEachItem */
st_free_table(mddIdToNodeName);
lsDestroy(sinkList, (void (*)(lsGeneric))0);
return partition;
} /* End of Part_NetworkCreatePartitionFromMvfs */
Here is the call graph for this function:
Here is the caller graph for this function:
| int PartPartitionInOutChangeRoots | ( | Ntk_Network_t * | network, |
| graph_t * | partition, | ||
| lsList | rootList, | ||
| int | verbosity | ||
| ) |
Function********************************************************************
Synopsis [Creates the graph representing the combinational outputs as functions of the combinational inputs.]
Description [The procedure works as follows. It calls the function Ntm_NetworkBuildMvfs with the combinational outputs as roots and the combinational inputs as leaves to obtain the multi-valued functions for every combinational output. For each combinational output, a vertex in the graph is created. For each combinational input in the support of a given combinational output MVF, a vertex is created for the combinational input (if one doesn't already exist), and an edge is added from the combinational input to the combinational output. The support of an MVF is taken as the union of the support of its constituent MDDs.]
SideEffects []
SeeAlso [Part_NetworkCreatePartition]
Definition at line 545 of file partInOut.c.
{
Ntk_Node_t *node; /* Pointer to iterate over nodes */
mdd_manager *manager; /* Mdd manager in the partition */
lsList newRootList;
lsList vertexList;
lsGen gen; /* To iterate over lists */
vertex_t *vertex;
char *vertexName;
long initialTime, finalTime;
st_table *rootNodesTable = st_init_table(st_ptrcmp, st_ptrhash);
mdd_t *careSet;
int prevNumOfLatchDataInput = 0;
int prevNumOfPrimaryOutput = 0;
int newNumOfLatchDataInput = 0;
int newNumOfPrimaryOutput = 0;
int overlapNumOfLatchDataInput = 0;
int overlapNumOfPrimaryOutPut = 0;
initialTime = util_cpu_time();
manager = PartPartitionReadMddManager(partition);
vertexList = g_get_vertices(partition);
lsForEachItem(vertexList, gen, vertex){
vertexName = PartVertexReadName(vertex);
node = Ntk_NetworkFindNodeByName(network, vertexName);
if (Ntk_NodeTestIsCombOutput(node)){
st_insert(rootNodesTable, (char *)node, (char *)(long)(-1));
if (Ntk_NodeTestIsLatchDataInput(node)){
prevNumOfLatchDataInput++;
}else if (Ntk_NodeTestIsPrimaryOutput(node)){
prevNumOfPrimaryOutput++;
}
}
}
newRootList = lsCreate();
lsForEachItem(rootList, gen, node){
if (!(st_is_member(rootNodesTable, (char *)node))){
lsNewEnd(newRootList, (lsGeneric)node, LS_NH);
if (Ntk_NodeTestIsLatchDataInput(node)){
newNumOfLatchDataInput++;
}else if (Ntk_NodeTestIsPrimaryOutput(node)){
newNumOfPrimaryOutput++;
}
}else{
if (Ntk_NodeTestIsLatchDataInput(node)){
overlapNumOfLatchDataInput++;
}else if (Ntk_NodeTestIsPrimaryOutput(node)){
overlapNumOfPrimaryOutPut++;
}
}
}
st_free_table(rootNodesTable);
if (lsLength(newRootList) > 0){
careSet = mdd_one(manager);
PartPartitionInputsOutputs(network, partition, newRootList,
(lsList)0, careSet);
mdd_free(careSet);
}
lsDestroy(newRootList, (void (*)(lsGeneric))0);
finalTime = util_cpu_time();
if (verbosity >= 2){
fprintf(vis_stdout, "PART: Partition is changed.\n");
fprintf(vis_stdout, "PART: Old - %d next state functions\n",
prevNumOfLatchDataInput);
fprintf(vis_stdout, "PART: Old - %d primary outputs\n",
prevNumOfPrimaryOutput);
fprintf(vis_stdout, "PART: New - %d next state functions\n",
prevNumOfLatchDataInput + newNumOfLatchDataInput);
fprintf(vis_stdout, "PART: New - %d primary outputs\n",
prevNumOfPrimaryOutput + newNumOfPrimaryOutput);
fprintf(vis_stdout, "PART: Partitioning time = %10ld\n",
(finalTime - initialTime) / 1000);
Part_PartitionPrintStats(vis_stdout, partition, FALSE);
}
/*
* Is partition increased?
*/
if (newNumOfLatchDataInput + newNumOfPrimaryOutput > 0){
return 1;
}else{
return 0;
}
} /* End of PartPartitionInOutChangeRoots */
Here is the call graph for this function:
Here is the caller graph for this function:
| void PartPartitionInputsOutputs | ( | Ntk_Network_t * | network, |
| graph_t * | partition, | ||
| lsList | rootList, | ||
| lsList | leaveList, | ||
| mdd_t * | careSet | ||
| ) |
Function********************************************************************
Synopsis [Creates the graph representing the combinational outputs as functions of the combinational inputs.]
Description [The procedure works as follows. It calls the function Ntm_NetworkBuildMvfs with the combinational outputs as roots and the combinational inputs as leaves to obtain the multi-valued functions for every combinational output. For each combinational output, a vertex in the graph is created. For each combinational input in the support of a given combinational output MVF, a vertex is created for the combinational input (if one doesn't already exist), and an edge is added from the combinational input to the combinational output. The support of an MVF is taken as the union of the support of its constituent MDDs.]
SideEffects []
SeeAlso [Part_NetworkCreatePartition]
Definition at line 364 of file partInOut.c.
{
Ntk_Node_t *node; /* Pointer to iterate over nodes */
Mvf_Function_t *mddFunction; /* Pointer to a MDD */
mdd_manager *manager; /* Mdd manager in the partition */
st_table *tableOfLeaves; /* To store the leaves of the graph */
st_table *mddIdToNodeName; /* For quick lookup of node's name */
array_t *arrayOfMvf; /* To store the next state functions */
array_t *arrayOfRoots; /* To store the roots of the graph */
lsList sinkList; /* Vertices representing comb. outputs */
lsGen gen; /* To iterate over lists */
vertex_t *toVertex; /* Will hold the current function vertex */
int i; /* Index for loops */
long mddId; /* Will hold the mddId being processed */
manager = PartPartitionReadMddManager(partition);
/* Take the nodes in leaveList as the leaves */
tableOfLeaves = st_init_table(st_ptrcmp, st_ptrhash);
mddIdToNodeName = st_init_table(st_numcmp, st_numhash);
if (leaveList == (lsList)0) {
Ntk_NetworkForEachCombInput(network, gen, node) {
st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );
st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node),
Ntk_NodeReadName(node));
}
} /* End of then */
else {
lsForEachItem(leaveList, gen, node) {
st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );
st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node),
Ntk_NodeReadName(node));
}
} /* End of if-then-else */
/* Take the nodes in rootList as the roots */
if (rootList == (lsList)0) {
arrayOfRoots = array_alloc(Ntk_Node_t *,
Ntk_NetworkReadNumCombOutputs(network));
i = 0;
Ntk_NetworkForEachCombOutput(network, gen, node) {
array_insert(Ntk_Node_t *, arrayOfRoots, i++, node);
}
} /* End of then */
else {
arrayOfRoots = array_alloc(Ntk_Node_t *, lsLength(rootList));
i = 0;
lsForEachItem(rootList, gen, node) {
array_insert(Ntk_Node_t *, arrayOfRoots, i++, node);
}
} /* End of if-then-else */
/* Build the next state functions as a function of the inputs */
arrayOfMvf = Ntm_NetworkBuildMvfs(network, arrayOfRoots, tableOfLeaves,
careSet);
/* Create one vertex for every component of arrayOfMvf */
for (i=0; i < array_n(arrayOfRoots); i++) {
node = array_fetch(Ntk_Node_t *, arrayOfRoots, i);
mddId = Ntk_NodeReadMddId(node);
/* obtain the function attached to the node */
mddFunction = array_fetch(Mvf_Function_t *, arrayOfMvf, i);
toVertex = g_add_vertex(partition);
/* Update the look-up tables in the graph */
st_insert(PartPartitionReadNameToVertex(partition),
Ntk_NodeReadName(node), (char *)toVertex);
if (mddId != NTK_UNASSIGNED_MDD_ID) {
st_insert(PartPartitionReadMddIdToVertex(partition),
(char *)(long) mddId, (char *)toVertex);
} /* End of if */
toVertex->user_data =
(gGeneric)PartVertexInfoCreateSingle(Ntk_NodeReadName(node),
mddFunction,
mddId);
} /* End of for */
/* Read the list of vertices on the graph */
sinkList = lsCopy(g_get_vertices(partition), (lsGeneric (*)(lsGeneric))0);
/*
* For every function on every combinational output, compute the
* support and create vertices in the graph when needed
*/
lsForEachItem(sinkList, gen, toVertex) {
st_table *mddSupport; /* To store the support of the Mvf_Function */
st_generator *stGen; /* To iterate over the MddIds of the support */
vertex_t *fromVertex; /* Will hold the current vertex in the support */
/* Obtain an array of mdd_t * */
mddFunction = PartVertexReadFunction(toVertex);
/* Compute the support of the set of mdds*/
mddSupport = PartCreateFunctionSupportTable(mddFunction);
/*
* Create one edge (and one vertex if necessary) for every element
* in mddSupport
*/
st_foreach_item(mddSupport, stGen, &mddId, NULL) {
char *name;
/* Create vertex with the information if needed */
if (st_lookup(PartPartitionReadMddIdToVertex(partition),
(char *)mddId, &fromVertex) == 0) {
fromVertex = g_add_vertex(partition);
st_lookup(mddIdToNodeName, (char *)mddId, &name);
/* Update the look-up tables in the graph */
st_insert(PartPartitionReadNameToVertex(partition),
name, (char *)fromVertex);
st_insert(PartPartitionReadMddIdToVertex(partition),
(char *)(long) mddId, (char *)fromVertex);
/* Create vertex data */
fromVertex->user_data =
(gGeneric)PartVertexInfoCreateSingle(name,
Mvf_FunctionCreateFromVariable(manager,mddId),
mddId);
} /* End of if */
/*
* Add the edge to the graph. Make sure a self loop is not added. The
* self loop may be produced by a mdd that has in its support the same
* variables that represent the mddId of the node.
*/
if (fromVertex != toVertex) {
g_add_edge(fromVertex, toVertex);
} /* End of if */
} /* End of st_foreach_item */
/* Clean the support table */
st_free_table(mddSupport);
} /* End of lsForEachItem */
/* Clean up */
st_free_table(mddIdToNodeName);
st_free_table(tableOfLeaves);
array_free(arrayOfRoots);
lsDestroy(sinkList, (void (*)(lsGeneric))0);
/*
* The contents of this array (array of mdds) is not deallocated because the
* information has been transferred to the partition structure. All the
* functions are stored now as part of the vertex information.
*/
array_free(arrayOfMvf);
} /* End of PartPartitionInputsOutputs */
Here is the call graph for this function:
Here is the caller graph for this function:
Variable Documentation
char rcsid [] UNUSED = "$Id: partInOut.c,v 1.15 2005/04/16 14:52:45 fabio Exp $" [static] |
CFile***********************************************************************
FileName [partInOut.c]
PackageName [part]
Synopsis [Implements the partition of a network considering only the functions at the combinational outputs in terms of the combinational inputs.]
Description [This module creates a partition where each combinational output is defined in terms of the combinational inputs. More specifically, for each combinational output and for some combinational inputs, there is a vertex in the partition (a combinational input doesn't appear if no combinational output depends on it). There is an edge from combinational input x to combinational output y if the multi-valued function (MVF) for y depends on x. Every vertex in the graph has a vertex name and an MVF (for combinational inputs, the MVF is the trivial variable function). In addition, each combinational input has an MDD id; a combinational output may or may not have an MDD id.]
SeeAlso [partPart.c]
Author [Abelardo Pardo, Balakrishna Kumthekar]
Copyright [This file was created at the University of Colorado at Boulder. The University of Colorado at Boulder makes no warranty about the suitability of this software for any purpose. It is presented on an AS IS basis.]
Definition at line 35 of file partInOut.c.
