#include "partInt.h"
Include dependency graph for partPartial.c:
Go to the source code of this file.
Functions | |
| void | PartPartitionPartial (Ntk_Network_t *network, graph_t *partition, lsList rootList, lsList leaveList, mdd_t *careSet, lsList nodeList, int inTermsOfCombInputs) |
Variables | |
| static char rcsid[] | UNUSED = "$Id: partPartial.c,v 1.10 2005/04/16 14:52:45 fabio Exp $" |
Function Documentation
| void PartPartitionPartial | ( | Ntk_Network_t * | network, |
| graph_t * | partition, | ||
| lsList | rootList, | ||
| lsList | leaveList, | ||
| mdd_t * | careSet, | ||
| lsList | nodeList, | ||
| int | inTermsOfCombInputs | ||
| ) |
AutomaticStart AutomaticEnd Function********************************************************************
Synopsis [Implements the partition with respect to the given list of nodes.]
SideEffects []
SeeAlso [PartPartitionTotal PartPartitionInputsOutputs]
Definition at line 87 of file partPartial.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 */
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 */
char *nodeName;
array_t *singletonMvfArray;
array_t *singletonArrayOfRoots;
array_t *tmpArrayOfMvf;
Mvf_Function_t *nodeMvf;
lsList sortedListOfNodes;
array_t *sortedArrayOfPartitionNodes;
array_t *unsortedArrayOfPartitionNodes;
st_table *tableOfPartitionNodes;
array_t *validNodeArray;
array_t *invalidNodeArray;
int chars_printed;
assert(rootList == (lsList)0);
assert(leaveList == (lsList)0);
manager = PartPartitionReadMddManager(partition);
invalidNodeArray = array_alloc(char *, 0);
validNodeArray = array_alloc(char *, 0);
/* check that nodes in nodeList are valid ones */
lsForEachItem(nodeList, gen, nodeName){
node = Ntk_NetworkFindNodeByName(network, nodeName);
if(node == NIL(Ntk_Node_t)){
array_insert_last(char *, invalidNodeArray, nodeName);
}
else{
array_insert_last(char *, validNodeArray, nodeName);
}
}
if(array_n(invalidNodeArray) > 0){
fprintf(stdout, "The following node(s) are being ignored in the partition:\n");
chars_printed = 0;
for(i = 0; i < array_n(invalidNodeArray); i++){
fprintf(stdout, "%s ", array_fetch(char *, invalidNodeArray, i));
chars_printed += strlen(array_fetch(char *, invalidNodeArray, i));
if(chars_printed >60){
chars_printed = 0;
fprintf(stdout, "\n");
}
}
fprintf(stdout, "\nThey are either invalid names or have been swept away at \n");
fprintf(stdout, "the end of the flatten_network command. Use <flatten_network -s> \n");
fprintf(stdout, "to avoid performing a sweep after the flatten command, \n");
}
array_free(invalidNodeArray);
/* Make the combinational input nodes into leaves */
tableOfLeaves = st_init_table(st_ptrcmp, st_ptrhash);
mddIdToNodeName = st_init_table(st_numcmp, st_numhash);
Ntk_NetworkForEachCombInput(network, gen, node) {
st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );
st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node),
Ntk_NodeReadName(node));
}
/* create temporary array and table of partition nodes */
unsortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0);
tableOfPartitionNodes = st_init_table(st_ptrcmp, st_ptrhash);
for(i = 0; i < array_n(validNodeArray); i++){
nodeName = array_fetch(char *, validNodeArray, i);
node = Ntk_NetworkFindNodeByName(network, nodeName);
assert(!Ntk_NodeTestIsShadow(node));
/* make sure that the node is not a CI or CO */
if(!Ntk_NodeTestIsCombInput(node) && !Ntk_NodeTestIsCombOutput(node)){
array_insert_last(Ntk_Node_t *, unsortedArrayOfPartitionNodes, node);
st_insert(tableOfPartitionNodes, (char *) node, (char *) (long) (-1));
}
}
array_free(validNodeArray);
/* create sorted array of partition nodes */
sortedListOfNodes = Ntk_NetworkComputeTopologicalOrder(network, unsortedArrayOfPartitionNodes, tableOfLeaves);
sortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0);
lsForEachItem(sortedListOfNodes, gen, node){
/* sortedListOfNodes includes many internal nodes, need to filter them out */
if(st_is_member(tableOfPartitionNodes, (char *) node)){
array_insert_last(Ntk_Node_t *, sortedArrayOfPartitionNodes, node);
}
}
array_free(unsortedArrayOfPartitionNodes);
lsDestroy(sortedListOfNodes, (void (*)(lsGeneric))0);
st_free_table(tableOfPartitionNodes);
/* Create mvfs for nodes in sortedArrayOfPartitionNodes */
tmpArrayOfMvf = array_alloc(Mvf_Function_t *, 0);
for(i=0; i < array_n(sortedArrayOfPartitionNodes); i++){
node = array_fetch(Ntk_Node_t *, sortedArrayOfPartitionNodes, i);
singletonArrayOfRoots = array_alloc(Ntk_Node_t *, 0);
array_insert_last(Ntk_Node_t *, singletonArrayOfRoots, node);
singletonMvfArray = Ntm_NetworkBuildMvfs(network, singletonArrayOfRoots,
tableOfLeaves, careSet);
nodeMvf = array_fetch(Mvf_Function_t *, singletonMvfArray, 0);
array_insert_last(Mvf_Function_t *, tmpArrayOfMvf, nodeMvf);
array_free(singletonMvfArray);
array_free(singletonArrayOfRoots);
/* now create an mddId for this node, and make it a leaf */
if(inTermsOfCombInputs == 0){
if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID){
Ord_NetworkAssignMddIdForNode(network, node);
}
st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );
st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node),
Ntk_NodeReadName(node));
}
}
/* Make the combinational output nodes into roots */
arrayOfRoots = array_alloc(Ntk_Node_t *, 0);
Ntk_NetworkForEachCombOutput(network, gen, node) {
array_insert_last(Ntk_Node_t *, arrayOfRoots, node);
}
/* build mvfs of nodes in arrayOfMvf in terms of partition nodes and comb inputs */
arrayOfMvf = Ntm_NetworkBuildMvfs(network, arrayOfRoots, tableOfLeaves,
careSet);
array_append(arrayOfRoots, sortedArrayOfPartitionNodes);
array_append(arrayOfMvf, tmpArrayOfMvf);
array_free(sortedArrayOfPartitionNodes);
array_free(tmpArrayOfMvf);
/* 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 = (long) 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 != -1) {
st_insert(PartPartitionReadMddIdToVertex(partition),
(char *)mddId, (char *)toVertex);
}
toVertex->user_data =
(gGeneric)PartVertexInfoCreateSingle(Ntk_NodeReadName(node),
mddFunction,
(int) 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) {
mddFunction = PartVertexReadFunction(toVertex);
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 *) mddId, (char *)fromVertex);
/* Create vertex data */
fromVertex->user_data =
(gGeneric)PartVertexInfoCreateSingle(name,
Mvf_FunctionCreateFromVariable(manager, (int) mddId),
(int) mddId);
}
/*
* 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 PartPartitionPartial */
Here is the call graph for this function:
Here is the caller graph for this function:
Variable Documentation
char rcsid [] UNUSED = "$Id: partPartial.c,v 1.10 2005/04/16 14:52:45 fabio Exp $" [static] |
CFile***********************************************************************
FileName [partPartial.c]
PackageName [part]
Synopsis [Implements the partition of the network with respect to a list of nodes provided by the user.]
Description [The network is composed of an arbitrary set of nodes, each of them implementing some function. This partitioning method will produce a graph representing the network in which the nodes specified in a list will be preserved in the graph structure. Different heuristics will control the structure of the rest of the partition.]
SeeAlso [partInOut.c partTotal.c]
Author [Sunil P Khatri]
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 29 of file partPartial.c.
