#include "partInt.h"
Include dependency graph for partFine.c:
Go to the source code of this file.
Defines | |
| #define | PartVertexReadGeneric(vPtr) ((PartVertexInfo_t *)(vPtr)->user_data)->generic |
| #define | PartVertexReadGeneric1(vPtr) ((PartVertexInfo_t *)(vPtr)->user_data)->generic1 |
| #define | BASIC_PARTITION_UNIT 15 |
Functions | |
| static int | Part_IsFanoutInverter (Ntk_Node_t *node) |
| void | PartPartitionFineGrain (Ntk_Network_t *network, graph_t *partition, mdd_t *careSet) |
| int | Part_CheckLeafNodeCondition (Ntk_Node_t *node, st_table *leafTable, int fanoutFreeLimit, int numVariableLimit) |
| int | Img_CutCalcTransitiveFanin (st_table *table, st_table *ownTable, Ntk_Node_t *node, Ntk_Node_t *fanin, int limit) |
| Ntk_Node_t * | Part_GetFaninFreeLogic (Ntk_Node_t *node) |
| Ntk_Node_t * | Part_GetFanoutFreeLogic (Ntk_Node_t *node) |
Variables | |
| static char rcsid[] | UNUSED = "$Id: partFine.c,v 1.5 2005/04/30 04:00:38 fabio Exp $" |
Define Documentation
| #define BASIC_PARTITION_UNIT 15 |
Definition at line 57 of file partFine.c.
| #define PartVertexReadGeneric | ( | vPtr | ) | ((PartVertexInfo_t *)(vPtr)->user_data)->generic |
Definition at line 55 of file partFine.c.
| #define PartVertexReadGeneric1 | ( | vPtr | ) | ((PartVertexInfo_t *)(vPtr)->user_data)->generic1 |
Definition at line 56 of file partFine.c.
Function Documentation
| int Img_CutCalcTransitiveFanin | ( | st_table * | table, |
| st_table * | ownTable, | ||
| Ntk_Node_t * | node, | ||
| Ntk_Node_t * | fanin, | ||
| int | limit | ||
| ) |
Function********************************************************************
Synopsis [Compute the number of support variables of given node.]
Description [ Compute the number of support variables of given node.]
SideEffects []
SeeAlso [PartPartitionTotal PartPartitionInputsOutputs]
Definition at line 444 of file partFine.c.
{
int i, nVar;
Ntk_Node_t *tfanin, *tnode;
nVar = 0;
Ntk_NodeForEachFanin(node, i, tfanin) {
if(tfanin == fanin) continue;
if(tfanin == 0) continue;
if(Ntk_NodeReadNumFanouts(tfanin) != 1){
if(!st_lookup(ownTable, tfanin, &tnode)) {
st_insert(ownTable, tfanin, tfanin);
nVar++;
}
continue;
}
if(Ntk_NodeTestIsCombInput(tfanin)) {
if(!st_lookup(ownTable, tfanin, &tnode)) {
st_insert(ownTable, tfanin, tfanin);
nVar++;
}
continue;
}
if(Ntk_NodeTestIsCombOutput(tfanin)) {
if(!st_lookup(ownTable, tfanin, &tnode)) {
st_insert(ownTable, tfanin, tfanin);
nVar++;
}
continue;
}
if(!st_lookup(table, tfanin, &tnode)) {
nVar += Img_CutCalcTransitiveFanin(table, ownTable, tfanin, 0, limit);
}
else
nVar++;
if(nVar > limit) return(nVar);
}
return(nVar);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| int Part_CheckLeafNodeCondition | ( | Ntk_Node_t * | node, |
| st_table * | leafTable, | ||
| int | fanoutFreeLimit, | ||
| int | numVariableLimit | ||
| ) |
Function********************************************************************
Synopsis [Check if the node can be assumed as leaf node based on given threshold.]
Description [ This function identify the leaf node for fine grain partition based on threshold.]
SideEffects []
SeeAlso [PartPartitionTotal PartPartitionInputsOutputs]
fanin = node; nDepth = 0; while(1) { if(nDepth > fanoutFreeLimit)return(1); if(nVar > numVariableLimit) return(1); if(!st_lookup(leafTable, (char *)fanin, (char **)&tnode)) {
Ntk_NodeForEachFanin(fanin, i, tfanin) { if(tfanin == 0) continue; if(Ntk_NodeReadNumFanouts(tfanin) != 1) continue; nVar += Ntk_NodeReadNumFanins(tfanin) - 1; } if(nVar > numVariableLimit) return(1);
fanin = Part_GetFaninFreeLogic(fanin); if(fanin == 0) break; if(Ntk_NodeTestIsCombInput(fanin)) break; if(Ntk_NodeTestIsCombOutput(fanin)) break;
} else break; nDepth++;
}
Definition at line 355 of file partFine.c.
{
int nVar, nDepth, i;
Ntk_Node_t *fanout, *tnode, *tfanin;
st_table *ownTable;
nVar = Ntk_NodeReadNumFanins(node);
nDepth = 0;
fanout = node;
ownTable = st_init_table(st_ptrcmp, st_ptrhash);
while(1) {
if(nDepth > fanoutFreeLimit)return(1);
if(nVar > numVariableLimit) return(1);
if(!st_lookup(leafTable, fanout, &tnode)) {
fanout = Part_GetFanoutFreeLogic(fanout);
if(fanout == 0) break;
if(Ntk_NodeTestIsCombInput(fanout)) break;
if(Ntk_NodeTestIsCombOutput(fanout)) break;
}
else break;
nDepth++;
if(fanout == 0) break;
nVar += Img_CutCalcTransitiveFanin(leafTable, ownTable, fanout,
node, numVariableLimit);
if(nVar > numVariableLimit) {
st_free_table(ownTable);
return(1);
}
}
Ntk_NodeForEachFanin(node, i, tfanin) {
if(tfanin == 0) continue;
if(Ntk_NodeReadNumFanouts(tfanin) != 1) continue;
nVar += Img_CutCalcTransitiveFanin(leafTable, ownTable, tfanin, 0, numVariableLimit)-1;
if(nVar > numVariableLimit) {
st_free_table(ownTable);
return(1);
}
}
if(nVar > numVariableLimit) {
st_free_table(ownTable);
return(1);
}
return(0);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| Ntk_Node_t* Part_GetFaninFreeLogic | ( | Ntk_Node_t * | node | ) |
Function********************************************************************
Synopsis [Check if the fanin of given node is fanout free.]
Description [Check if the fanin of given node is fanout free.]
SideEffects []
SeeAlso [PartPartitionTotal PartPartitionInputsOutputs]
Definition at line 500 of file partFine.c.
{
int i;
Ntk_Node_t *fanin;
Ntk_NodeForEachFanin(node, i, fanin) {
if(Ntk_NodeReadNumFanouts(fanin) != 1) continue;
return(fanin);
}
return(0);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| Ntk_Node_t* Part_GetFanoutFreeLogic | ( | Ntk_Node_t * | node | ) |
Function********************************************************************
Synopsis [Check if the fanout of given node is fanout free.]
Description [Check if the fanout of given node is fanout free.]
SideEffects []
SeeAlso [PartPartitionTotal PartPartitionInputsOutputs]
Definition at line 524 of file partFine.c.
{
int i;
Ntk_Node_t *fanout;
if(Ntk_NodeReadNumFanouts(node) != 1) return(0);
Ntk_NodeForEachFanout(node, i, fanout) {
return(fanout);
}
return(0);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| int Part_IsFanoutInverter | ( | Ntk_Node_t * | node | ) | [static] |
AutomaticStart
Function********************************************************************
Synopsis [Check if the fanout of given node is inverter.]
Description [ Check if the fanout of given node is inverter.]
SideEffects []
SeeAlso [PartPartitionTotal PartPartitionInputsOutputs]
Definition at line 332 of file partFine.c.
{
Ntk_Node_t *fanout;
fanout = Part_GetFanoutFreeLogic(node);
if(!fanout) return(1);
if(Ntk_NodeReadNumFanins(fanout) == 1) return(1);
else return(0);
}
Here is the call graph for this function:
| void PartPartitionFineGrain | ( | Ntk_Network_t * | network, |
| graph_t * | partition, | ||
| mdd_t * | careSet | ||
| ) |
AutomaticEnd Function********************************************************************
Synopsis [Implements the partition with respect to the given list of nodes.]
Description []
SideEffects []
SeeAlso [PartPartitionTotal PartPartitionInputsOutputs]
if(Part_IsFanoutInverter(node)) continue; if(Ntk_NodeReadNumFanins(node) == 1) continue;
else if(Ntk_NodeReadNumFanins(node) == 1) { fanin = Part_GetFaninFreeLogic(node); if(!fanin) continue; if(Ntk_NodeTestIsCombInput(fanin)) continue; }
Definition at line 93 of file partFine.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 */
array_t *singletonMvfArray;
array_t *singletonArrayOfRoots;
array_t *tmpArrayOfMvf;
Mvf_Function_t *nodeMvf;
lsList sortedListOfNodes;
array_t *sortedArrayOfPartitionNodes;
array_t *unsortedArrayOfPartitionNodes;
st_table *tableOfPartitionNodes;
Ntk_Node_t *fanin, *fanout;
manager = PartPartitionReadMddManager(partition);
/* 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) {
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));
}
unsortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0);
tableOfPartitionNodes = st_init_table(st_ptrcmp, st_ptrhash);
/* Make the target node list for partition */
Ntk_NetworkForEachNode(network, gen, node) {
if(Ntk_NodeTestIsShadow(node)) continue;
else if(Ntk_NodeTestIsCombInput(node)) continue;
else if(Ntk_NodeTestIsCombOutput(node)) continue;
else if(Ntk_NodeReadNumFanouts(node) == 1) {
fanout = Part_GetFanoutFreeLogic(node);
if(Ntk_NodeTestIsCombOutput(fanout));
else if(Ntk_NodeReadNumFanins(node) > 10);
else if(Ntk_NodeReadNumFanins(fanout) == 1) continue;
else if(!Part_CheckLeafNodeCondition(node, tableOfPartitionNodes, 5, 10)) {
if(Ntk_NodeReadNumFanins(node) == 1) {
fanin = Part_GetFaninFreeLogic(node);
if(!fanin) continue;
if(Ntk_NodeTestIsCombInput(fanin)) continue;
}
continue;
}
}
array_insert_last(Ntk_Node_t *, unsortedArrayOfPartitionNodes, node);
st_insert(tableOfPartitionNodes, (char *) node, (char *) (long) (-1));
}
/* 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);
if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID)
Ord_NetworkAssignMddIdForNode(network, node);
}
}
array_free(unsortedArrayOfPartitionNodes);
lsDestroy(sortedListOfNodes, (void (*)(lsGeneric))0);
st_free_table(tableOfPartitionNodes);
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);
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));
}
arrayOfRoots = array_alloc(Ntk_Node_t *, 0);
Ntk_NetworkForEachCombOutput(network, gen, node) {
array_insert_last(Ntk_Node_t *, arrayOfRoots, node);
}
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 = 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 *)(long) mddId, (char *)toVertex);
}
toVertex->user_data =
(gGeneric)PartVertexInfoCreateSingle(Ntk_NodeReadName(node),
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) {
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 *)(long) mddId, &fromVertex) == 0) {
fromVertex = g_add_vertex(partition);
st_lookup(mddIdToNodeName, (char *)(long) 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);
}
/*
* 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);
fprintf(stdout, "NOTICE : current peak memory = %ld\n",
bdd_read_peak_memory(manager));
} /* End of PartPartitionCut */
Here is the call graph for this function:
Here is the caller graph for this function:
Variable Documentation
char rcsid [] UNUSED = "$Id: partFine.c,v 1.5 2005/04/30 04:00:38 fabio Exp $" [static] |
CFile***********************************************************************
FileName [partFine.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 [HoonSang Jin]
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 partFine.c.
