src/spfd/spfdOpt.c File Reference
#include "spfdInt.h"
Include dependency graph for spfdOpt.c:
Go to the source code of this file.
Functions | |
| static int | CompareConvexFanoutCountAndDepth (const void *obj1, const void *obj2) |
| static int | CompareConvexSwitchedCapAndDepth (const void *obj1, const void *obj2) |
| int | SpfdNetworkOptimize (Ntk_Network_t *network, char *simFile, int percent, int frequency, int regionDepth) |
| Ntk_Node_t * | SpfdCheckIfWireIsRedundantOrReplaceable (Ntk_Network_t *network, SpfdApplData_t *applData, Ntk_Node_t *from, Ntk_Node_t *to, array_t *replaceArray) |
| Ntk_Node_t * | SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd (Ntk_Network_t *network, array_t *replaceArray, Ntk_Node_t *from, Ntk_Node_t *to, bdd_node *wireSpfd) |
| void | SpfdOptimizeFaninWires (Ntk_Network_t *network, Ntk_Node_t *maxNode, int regionDepth, boolean replRem) |
| void | SpfdOptimizeFanoutWires (Ntk_Network_t *network, Ntk_Node_t *maxNode, int regionDepth, boolean replRem) |
| void | SpfdOptimizeFaninNodes (Ntk_Network_t *network, Ntk_Node_t *maxNode, int regionDepth) |
| void | SpfdOptimizeWire (Ntk_Network_t *network, Ntk_Node_t *maxNode, Ntk_Node_t *ntkNode, int regionDepth, boolean replRem) |
| void | SpfdOptimizeNode (Ntk_Network_t *network, Ntk_Node_t *ntkNode, int regionDepth) |
Function Documentation
| static int CompareConvexFanoutCountAndDepth | ( | const void * | obj1, |
| const void * | obj2 | ||
| ) | [static] |
CFile***********************************************************************
FileName [spfdOpt.c]
PackageName [spfd]
Synopsis [Routines that implement spfd_pilo.]
Description [Routines that implement spfd_pilo.]
SeeAlso [spfdCmd.c spfdReg.c spfdProg.c]
Author [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.]AutomaticStart
Function********************************************************************
Synopsis [Compare the convex combination of fanout count and the node's topological depth.]
SideEffects [None]
Definition at line 1222 of file spfdOpt.c.
{
Ntk_Node_t *node1,*node2;
Ntk_Network_t *network;
float weight1,weight2;
float load1,load2;
int depth1,depth2;
node1 = *(Ntk_Node_t **)obj1;
node2 = *(Ntk_Node_t **)obj2;
assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
network = Ntk_NodeReadNetwork(node1);
if (Ntk_NodeTestIsPrimaryOutput(node1) ||
Ntk_NodeTestIsPrimaryInput(node1)) {
weight1 = -1.0;
} else {
load1 = Ntk_NodeReadNumFanouts(node1);
depth1 = Truesim_NetworkReadNodeDepth(network,node1);
weight1 = spfdAlpha * load1 + (1.0-spfdAlpha)*depth1;
}
if (Ntk_NodeTestIsPrimaryOutput(node2) ||
Ntk_NodeTestIsPrimaryInput(node2)) {
weight2 = -1.0;
} else {
load2 = Ntk_NodeReadNumFanouts(node2);
depth2 = Truesim_NetworkReadNodeDepth(network,node2);
weight2 = spfdAlpha * load2 + (1.0-spfdAlpha)*depth2;
}
if (weight1 > weight2)
return -1;
else if (weight1 == weight2)
return 0;
else
return 1;
} /* End of CompareConvexFanoutCountAndDepth */
Here is the call graph for this function:
Here is the caller graph for this function:
| static int CompareConvexSwitchedCapAndDepth | ( | const void * | obj1, |
| const void * | obj2 | ||
| ) | [static] |
Function********************************************************************
Synopsis [Compare the convex combination of switched capacitance and topological depth of two nodes.]
SideEffects [None]
Definition at line 1274 of file spfdOpt.c.
{
Ntk_Node_t *node1,*node2;
Ntk_Network_t *network;
float weight1,weight2;
float switch1,switch2;
float load1,load2;
int depth1,depth2;
node1 = *(Ntk_Node_t **)obj1;
node2 = *(Ntk_Node_t **)obj2;
assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
network = Ntk_NodeReadNetwork(node1);
if (Ntk_NodeTestIsPrimaryOutput(node1) ||
Ntk_NodeTestIsPrimaryInput(node1)) {
weight1 = -1.0;
} else {
switch1 = Truesim_NetworkReadNodeSwitchingProb(network,node1);
load1 = Truesim_NetworkReadNodeLoad(network,node1);
depth1 = Truesim_NetworkReadNodeDepth(network,node1);
weight1 = spfdAlpha * load1 * switch1 + (1.0-spfdAlpha)*depth1;
}
if (Ntk_NodeTestIsPrimaryOutput(node2) ||
Ntk_NodeTestIsPrimaryInput(node2)) {
weight2 = -1.0;
} else {
switch2 = Truesim_NetworkReadNodeSwitchingProb(network,node2);
load2 = Truesim_NetworkReadNodeLoad(network,node2);
depth2 = Truesim_NetworkReadNodeDepth(network,node2);
weight2 = spfdAlpha * load2 * switch2 + (1.0-spfdAlpha)*depth2;
}
if (weight1 > weight2)
return -1;
else if (weight1 == weight2)
return 0;
else
return 1;
} /* End of CompareConvexSwitchedCapAndDepth */
Here is the call graph for this function:
Here is the caller graph for this function:
| Ntk_Node_t* SpfdCheckIfWireIsRedundantOrReplaceable | ( | Ntk_Network_t * | network, |
| SpfdApplData_t * | applData, | ||
| Ntk_Node_t * | from, | ||
| Ntk_Node_t * | to, | ||
| array_t * | replaceArray | ||
| ) |
Function********************************************************************
Synopsis [Checks if the SPFD for 'from' --> 'to' is empty. If yes, the wire is removed. If not, nodes in 'replaceArray' are examined to check for replacability. If a node is found, that node is returned.]
SideEffects [None]
Definition at line 458 of file spfdOpt.c.
{
bdd_manager *ddManager = applData->ddManager;
bdd_node *result,*ddTemp,*ddTemp2,*var,*varAux;
bdd_node *toSpfd,*wireSpfd,*logicZero;
int i,index;
Ntk_Node_t *fanin,*tempNode,*replNode;
st_table *wireTable = applData->currWireTable;
st_table *wiresRemoved = applData->wiresRemoved;
st_table *sinkTable;
/* Possible replacement node */
replNode = NIL(Ntk_Node_t);
logicZero = bdd_read_logic_zero(ddManager);
/* Check if this wire has already been removed. */
if (!(st_lookup(wiresRemoved,(char *)from,&sinkTable) &&
st_lookup(sinkTable,(char *)to,&tempNode))) {
bdd_ref(result = bdd_read_one(ddManager));
/* Compute the characteristic function of pairs of minterms cannot
be distinguished any fanin of 'to'. Let f_i be the ith fanin of
'to'. We compute result = \prod f_i == f'_i, where f_i != from */
Ntk_NodeForEachFanin(to,i,fanin) {
var = bdd_bdd_ith_var(ddManager,Ntk_NodeReadMddId(fanin));
index = SpfdNodeReadAuxId(applData,fanin);
varAux = bdd_bdd_ith_var(ddManager,index);
if (fanin != from) {
bdd_ref(ddTemp = bdd_bdd_xnor(ddManager,var,varAux)); /* XNOR */
bdd_ref(ddTemp2 = bdd_bdd_and(ddManager,result,ddTemp));
bdd_recursive_deref(ddManager,result);
bdd_recursive_deref(ddManager,ddTemp);
result = ddTemp2;
}
}
/* Finally put in f_i == f_i', where f_i = from) */
var = bdd_bdd_ith_var(ddManager,Ntk_NodeReadMddId(from));
index = SpfdNodeReadAuxId(applData,from);
varAux = bdd_bdd_ith_var(ddManager,index);
bdd_ref(ddTemp = bdd_bdd_xor(ddManager,var,varAux));
bdd_ref(ddTemp2 = bdd_bdd_and(ddManager,result,ddTemp));
bdd_recursive_deref(ddManager,result);
bdd_recursive_deref(ddManager,ddTemp);
result = ddTemp2;
/* Compute AND of result and the SPFD of 'to'. */
toSpfd = SpfdNodeReadSpfd(applData,to);
if (toSpfd == NIL(bdd_node)) {
(void) fprintf(vis_stderr,
"** spfd error: Spfd expected but not found.\n");
exit(0);
}
bdd_ref(wireSpfd = bdd_bdd_and(ddManager,toSpfd,result));
bdd_recursive_deref(ddManager,result);
if (wireSpfd == logicZero) { /* Can the wire be removed? */
if (spfdVerbose > 1)
(void) fprintf(vis_stdout,
"** spfd info: Target wire %s --> %s has empty spfd.\n",
Ntk_NodeReadName(from),Ntk_NodeReadName(to));
/* Insert the wire into wireTable */
if (st_lookup(wireTable,(char *)from,&sinkTable)) {
st_insert(sinkTable,(char *)to,(char *)to);
} else {
sinkTable = st_init_table(st_ptrcmp,st_ptrhash);
st_insert(sinkTable,(char *)to,(char *)to);
st_insert(wireTable,(char *)from,(char *)sinkTable);
}
bdd_recursive_deref(ddManager,wireSpfd);
} else if (replaceArray != NIL(array_t)) {
/* Try for replacement. Exit after finding the first one. Here the
assumption is that the nodes are sorted according to some
criterion. */
replNode = SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd(network,replaceArray,
from,to,wireSpfd);
bdd_recursive_deref(ddManager,wireSpfd);
} else {
bdd_recursive_deref(ddManager,wireSpfd);
}
}
return replNode;
} /* End of SpfdCheckIfWireIsRedundantOrReplaceable */
Here is the call graph for this function:
Here is the caller graph for this function:
| int SpfdNetworkOptimize | ( | Ntk_Network_t * | network, |
| char * | simFile, | ||
| int | percent, | ||
| int | frequency, | ||
| int | regionDepth | ||
| ) |
AutomaticEnd Function********************************************************************
Synopsis [Optimize the network by performing wire/node removal, wire replacement and LUT reprogramming to reduce the number of wires and nodes and the overall switching activity of the circuit.]
Description [Optimize the network by performing wire/node removal, wire replacement and LUT reprogramming to reduce the number of wires and nodes and the overall switching activity of the circuit. The algorithm iteratively selects a node, 'maxNode', (based on the heuristic selected) and examines all the fanout/fanin wires to determine if any one them can be removed or replaced by another wire. For each wire selected, fanout cluster if computed up to a depth 'regionDepth'. SPFD are computed only for these cluster nodes. Any wire, internal to the cluster, that has an empty SPFD is removed. Cluster nodes are then reprogrammed by choosing an alternative implementation derived from the node SPFD.
After the cluster nodes are optimized, 'maxNode' is locked and is not optimized in future iterations. The algorithm ends when there are no more nodes to be optimized.
The argument 'simFile' (if not NULL) specifies the vectors used to simulate the circuit in order to compute circuit node switching activity. Vector simulations are performed every 'frequency' iterations. 'regionDepth' specifies the depth of the cluster from the 'maxNode'.]
SideEffects [None]
Definition at line 100 of file spfdOpt.c.
{
SpfdApplData_t *applData;
Ntk_Node_t *node,*maxNode;
int stop,iter,status;
float randomValue;
array_t *nodeArray;
lsGen gen;
st_generator *stGen;
char *dummy;
boolean replRem;
array_t *inputArray,*patternArray,*intPatternArray;
char *optName;
/* To keep the compiler happy */
inputArray = patternArray = intPatternArray = NIL(array_t);
/* Check if both wire removal and replacement are to be done */
optName = Cmd_FlagReadByName("spfd_repl_rem");
if (optName && (strcmp(optName,"yes") == 0)) {
replRem = TRUE;
} else {
replRem = FALSE;
}
/* First initialize the simulation package. This will also levelize
the nodes in the network. The level info is stored in local data
structure of 'truesim' package'. This is needed even if we do not
perform vector simulation. */
Truesim_InitializeSimulation(network,NIL(char),0,-1,0,NIL(st_table));
if (spfdPerfSim) { /* Perform simulation? */
/* Array of primary input nodes */
inputArray = array_alloc(Ntk_Node_t *,0);
/* Array of simulation vectors */
patternArray = array_alloc(char *,0);
status = Truesim_ReadSimulationVectors(network,simFile,
inputArray,patternArray);
/* Error while reading simulation vectors */
if (!status) {
array_free(inputArray);
array_free(patternArray);
(void) fprintf(vis_stdout, "** spfd error: Error reading simulation"
" vector file. \n");
return 0;
}
Truesim_ZeroDelayPatternSimulate(network,inputArray,patternArray);
/* Select a random start for the set of internal simulation
vectors. We simulate only a portion of vectors (during
optimization iterations) to get a coarse estimate of circuit
node switching activities. */
randomValue = ((double)util_random()/(double)(MODULUS1 - 2));
if (randomValue > (double) (1.0 - ((double)percent)/((double)100)))
randomValue = (1.0 - ((double)percent)/((double)100))/2.0;
/* Partial set of simulation vectors */
intPatternArray = SpfdFetchInternalPatternArray(patternArray,percent,
randomValue);
}
/* Initialize the package application data structure */
applData = SpfdInitializeApplData(network);
iter = 1;
do {
if (spfdVerbose > 2) {
(void) fprintf(vis_stdout, "** spfd info: Iteration %d\n",iter);
}
nodeArray = array_alloc(Ntk_Node_t *,0);
/* Collect circuit nodes, later needed to be sorted. Only the
internal nodes will be sorted.*/
switch (spfdMethod) {
case REDUCE_FANIN_WIRES:
case OPTIMIZE_MAX_NODE:
Ntk_NetworkForEachNode(network,gen,node) {
if (!Ntk_NodeTestIsPrimaryOutput(node) &&
!Ntk_NodeTestIsPrimaryInput(node) &&
!SpfdNodeReadLocked(applData,node))
array_insert_last(Ntk_Node_t *,nodeArray,node);
}
break;
case OPTIMIZE_FANIN_NODES:
Ntk_NetworkForEachNode(network,gen,node) {
if (!Ntk_NodeTestIsPrimaryInput(node) &&
!SpfdNodeReadLocked(applData,node))
array_insert_last(Ntk_Node_t *,nodeArray,node);
}
break;
case REDUCE_FANOUT_WIRES:
Ntk_NetworkForEachNode(network,gen,node) {
if (!SpfdNodeReadLocked(applData,node))
array_insert_last(Ntk_Node_t *,nodeArray,node);
}
break;
}
/* Find the node with max. fanout/switched cap., or a random node */
maxNode = SpfdFindNode(network,nodeArray);
if (!maxNode)
stop = 1;
else
stop = 0;
array_free(nodeArray);
/* Optimize. */
if (!stop) {
switch (spfdMethod) {
case REDUCE_FANIN_WIRES:
SpfdOptimizeFaninWires(network,maxNode,regionDepth,replRem);
break;
case OPTIMIZE_MAX_NODE:
SpfdOptimizeNode(network,maxNode,regionDepth);
break;
case OPTIMIZE_FANIN_NODES:
SpfdOptimizeFaninNodes(network,maxNode,regionDepth);
break;
case REDUCE_FANOUT_WIRES:
SpfdOptimizeFanoutWires(network,maxNode,regionDepth,replRem);
break;
}
/* If the network has changed (structurally), update the depth
information to reflect the change in the network.*/
if (spfdNtkChanged) {
Truesim_NetworkUpdateNodeTopologicalDepth(network);
spfdNtkChanged = FALSE;
}
if (spfdPerfSim && (iter % frequency == 0)) {
Truesim_ZeroDelayPatternSimulate(network,inputArray,intPatternArray);
}
}
iter++;
} while (!stop);
if (spfdPerfSim) {
/* End simulation; free memory */
Truesim_QuitSimulation(network);
array_free(inputArray);
array_free(patternArray);
}
/* Print the number of wires removed and delete the sinkTable. */
fprintf(vis_stdout,"** spfd info: # of wires removed = %d\n",
spfdNumWiresRem - spfdWiresAdded);
fprintf(vis_stdout,"** spfd info: # of nodes removed = %d\n",
st_count(applData->nodesRemoved));
/* Free the memory for each node */
st_foreach_item(applData->nodesRemoved,stGen,&node,&dummy) {
if (node) Ntk_NodeFree(node);
}
return 1;
} /* End of SpfdNetworkOptimize */
Here is the call graph for this function:
Here is the caller graph for this function:
| void SpfdOptimizeFaninNodes | ( | Ntk_Network_t * | network, |
| Ntk_Node_t * | maxNode, | ||
| int | regionDepth | ||
| ) |
Function********************************************************************
Synopsis [Optimize all the fanin nodes of maxNode.]
SideEffects [None]
Definition at line 851 of file spfdOpt.c.
{
SpfdApplData_t *applData;
array_t *faninArray;
Ntk_Node_t *ntkNode;
char *dummy;
int i;
applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
SPFD_NETWORK_APPL_KEY);
/* Optimize fanin nodes one at a time. The fanin node with higher
switched capacitance will be optimized first. */
faninArray = array_dup(Ntk_NodeReadFanins(maxNode));
if (spfdPerfSim)
array_sort(faninArray,CompareConvexSwitchedCapAndDepth);
else
array_sort(faninArray,CompareConvexFanoutCountAndDepth);
for (i = array_n(faninArray) - 1; i >=0; i--) {
boolean skip = FALSE;
ntkNode = array_fetch(Ntk_Node_t *,faninArray,i);
if (st_lookup(applData->nodesRemoved,(char *)ntkNode,(char **)&dummy)) {
skip = TRUE;
}
if (!skip)
SpfdOptimizeNode(network,ntkNode,regionDepth);
}
array_free(faninArray);
/* Lock the node */
SpfdNodeSetLocked(applData,maxNode,TRUE);
return ;
} /* End of SpfdOptimizeFaninNodes */
Here is the call graph for this function:
Here is the caller graph for this function:
| void SpfdOptimizeFaninWires | ( | Ntk_Network_t * | network, |
| Ntk_Node_t * | maxNode, | ||
| int | regionDepth, | ||
| boolean | replRem | ||
| ) |
Function********************************************************************
Synopsis [Try to remove/replace the fanin wires of maxNode.]
SideEffects [None]
SeeAlso [SpfdOptimizeFanoutWires]
Definition at line 734 of file spfdOpt.c.
{
SpfdApplData_t *applData;
array_t *faninArray;
Ntk_Node_t *ntkNode,*fanout;
char *dummy;
int i,j;
applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
SPFD_NETWORK_APPL_KEY);
/* replace/remove the fanin wire of maxNode one at a time. The fanin
node with higher switched capacitance will be optimized first. */
faninArray = array_dup(Ntk_NodeReadFanins(maxNode));
if (spfdPerfSim)
array_sort(faninArray,CompareConvexSwitchedCapAndDepth);
else
array_sort(faninArray,CompareConvexFanoutCountAndDepth);
for (i = array_n(faninArray) - 1; i >=0; i--) {
boolean skip;
ntkNode = array_fetch(Ntk_Node_t *,faninArray,i);
if (!st_lookup(applData->nodesRemoved,(char *)ntkNode,(char **)&dummy)) {
skip = TRUE;
/* Check if the current fanin node is still in the support of
maxNode. */
Ntk_NodeForEachFanout(ntkNode,j,fanout) {
if (fanout == maxNode) {
skip = FALSE;
break;
}
}
} else {
skip = TRUE;
}
if (!skip)
SpfdOptimizeWire(network,ntkNode,maxNode,regionDepth,replRem);
}
array_free(faninArray);
/* Lock the node */
SpfdNodeSetLocked(applData,maxNode,TRUE);
return ;
} /* End of SpfdOptimizeFaninWires */
Here is the call graph for this function:
Here is the caller graph for this function:
| void SpfdOptimizeFanoutWires | ( | Ntk_Network_t * | network, |
| Ntk_Node_t * | maxNode, | ||
| int | regionDepth, | ||
| boolean | replRem | ||
| ) |
Function********************************************************************
Synopsis [Try to remove/replace the fanout wires of maxNode.]
SideEffects [None]
SeeAlso [SpfdOptimizeFaninWires]
Definition at line 796 of file spfdOpt.c.
{
SpfdApplData_t *applData;
array_t *fanoutArray;
Ntk_Node_t *ntkNode,*fanout;
int i,j;
applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
SPFD_NETWORK_APPL_KEY);
/* replace/remove the fanout wires of maxNode one at a time. The fanout
node with higher switched capacitance will be optimized first. */
fanoutArray = array_dup(Ntk_NodeReadFanouts(maxNode));
if (spfdPerfSim)
array_sort(fanoutArray,CompareConvexSwitchedCapAndDepth);
else
array_sort(fanoutArray,CompareConvexFanoutCountAndDepth);
for (i = array_n(fanoutArray) - 1; i >=0; i--) {
boolean skip;
ntkNode = array_fetch(Ntk_Node_t *,fanoutArray,i);
skip = TRUE;
/* Check if the maxNode is still in the support of fanout. */
Ntk_NodeForEachFanout(maxNode,j,fanout) {
if (fanout == ntkNode) {
skip = FALSE;
break;
}
}
if (!skip)
SpfdOptimizeWire(network,maxNode,ntkNode,regionDepth,replRem);
}
array_free(fanoutArray);
/* Lock the node */
SpfdNodeSetLocked(applData,maxNode,TRUE);
return ;
} /* End of SpfdOptimizeFanoutWires */
Here is the call graph for this function:
Here is the caller graph for this function:
| void SpfdOptimizeNode | ( | Ntk_Network_t * | network, |
| Ntk_Node_t * | ntkNode, | ||
| int | regionDepth | ||
| ) |
Function********************************************************************
Synopsis [Optimize the ntkNode. This is done by computing its SPFD derived from the output cluster. The cluster is formed of those nodes that are within 'regionDepth' in the fanout of ntkNode. Both wire removal and replacement are performed if 'replRem' is true.]
SideEffects [None]
Definition at line 1081 of file spfdOpt.c.
{
SpfdApplData_t *applData;
st_table *wiresRemoved,*sinkTable;
st_generator *stGen;
Ntk_Node_t *tempNode;
array_t *regionArray;
int num;
/* Package application data structure */
applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
SPFD_NETWORK_APPL_KEY);
/* Skip POs */
if (Ntk_NodeTestIsPrimaryOutput(ntkNode))
return;
/* regionArray is an array of nodes sorted according to their depth. */
regionArray = SpfdNodeComputeFanoutRegion(applData,ntkNode,regionDepth);
/* Analyze region's BDD requirements */
SpfdComputeRequiredGlobalBdds(network,applData);
/* Analyze auxilarry BDD ID requirements */
SpfdAllocateOrReuseAuxVariables(network,applData);
/* Order the fanin of internal and boundary nodes */
if (spfdPerfSim) {
SpfdOrderFaninOfRegionNodes(network,applData,
SpfdSwitchedCapAndDepthCompare);
} else {
SpfdOrderFaninOfRegionNodes(network,applData,
SpfdFanoutCountAndDepthCompare);
}
/* Set the spfds for nodes in the region. The spfds are reduced to a
single pair and the localAlt is set to one of the components of the
single pair SPFD. */
SpfdRegionComputeSinglePairSpfd(network,applData,regionArray);
/* Remove the spfd of ntkNode as it was not deleted in
SpfdRegionComputeSinglePairSpfd */
/* SPFD of ntkNode is no longer needed. */
SpfdNodeDeleteSpfd(applData,ntkNode);
/* Check to see if wires have been found to be
redundant/replaceable. If no wires are to be
removed/replaced, then decide whether or not to reprogram. */
if (st_count(applData->currWireTable) == 0 &&
!spfdReprogNoWire) {
/* In this case just clean up currBddReq, localAlt and
globalAlt. */
st_table *currBddReq;
st_generator *stGen;
Ntk_Node_t *regNode;
bdd_node *bdd1;
bdd_manager *ddManager;
int j;
ddManager = applData->ddManager;
currBddReq = applData->currBddReq;
/* Clean up currBddReq */
st_foreach_item(currBddReq,stGen,®Node,&bdd1) {
bdd_recursive_deref(ddManager,bdd1);
}
st_free_table(currBddReq);
applData->currBddReq = NIL(st_table);
/* Clean up localAlt and globalAlt of region nodes */
arrayForEachItem(Ntk_Node_t *,regionArray,j,regNode) {
SpfdNodeDeleteGlobalAlternative(applData,regNode);
SpfdNodeDeleteLocalAlt(applData,regNode);
}
} else {
/* Now reprogram the nodes in the region. */
SpfdReprogramRegionNodes(network,applData,regionArray);
}
/* Clean up auxIds and piAltVars*/
SpfdCleanUpAuxIds(applData);
/* Free stuff used only for the current wire */
if (applData->currXCube) {
bdd_recursive_deref(applData->ddManager,applData->currXCube);
applData->currXCube = NIL(bdd_node);
}
if (applData->currRegionNodes) {
st_free_table(applData->currRegionNodes);
applData->currRegionNodes = NIL(st_table);
}
if (applData->currInUseVars) {
st_free_table(applData->currInUseVars);
applData->currInUseVars = NIL(st_table);
}
num = st_count(applData->currWireTable);
assert(num == 0);
num = st_count(applData->currReplaceTable);
assert(num == 0);
/* Update the total number of wires removed */
wiresRemoved = applData->wiresRemoved;
if (st_count(wiresRemoved) > 0) {
st_foreach_item(wiresRemoved,stGen,&tempNode,
&sinkTable){
spfdNumWiresRem += st_count(sinkTable);
}
/* free the wiresRemoved contents */
st_foreach(wiresRemoved,SpfdStTableClean,NIL(char));
}
/* Free regionArray (cluster) */
array_free(regionArray);
/* Lock the node */
SpfdNodeSetLocked(applData,ntkNode,TRUE);
return ;
} /* End of SpfdOptimizeNode */
Here is the call graph for this function:
Here is the caller graph for this function:
| void SpfdOptimizeWire | ( | Ntk_Network_t * | network, |
| Ntk_Node_t * | maxNode, | ||
| Ntk_Node_t * | ntkNode, | ||
| int | regionDepth, | ||
| boolean | replRem | ||
| ) |
Function********************************************************************
Synopsis [Optimize the cluster of nodes in the fanout the wire maxNode --> ntkNode. The cluster is formed of those nodes that are within 'regionDepth' of this wire. Both wire removal and replacement are performed if 'replRem' is true.]
SideEffects [None]
Definition at line 903 of file spfdOpt.c.
{
SpfdApplData_t *applData;
array_t *replArray;
st_table *wiresRemoved,*sinkTable;
st_generator *stGen;
Ntk_Node_t *tempNode,*replNode;
array_t *regionArray;
int num;
/* Package application data structure */
applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
SPFD_NETWORK_APPL_KEY);
/* Skip POs */
if (Ntk_NodeTestIsPrimaryOutput(ntkNode))
return;
/* regionArray is an array of nodes sorted according to their depth. */
regionArray = SpfdNodeComputeFanoutRegion(applData,ntkNode,regionDepth);
/* Analyze region's BDD requirements */
SpfdComputeRequiredGlobalBdds(network,applData);
/* Analyze auxilarry BDD ID requirements */
SpfdAllocateOrReuseAuxVariables(network,applData);
/* Order the fanin of internal and boundary nodes */
if (spfdPerfSim) {
SpfdOrderFaninOfRegionNodes(network,applData,
SpfdSwitchedCapAndDepthCompare);
} else {
SpfdOrderFaninOfRegionNodes(network,applData,
SpfdFanoutCountAndDepthCompare);
}
/* Set the spfds for nodes in the region. The spfds are reduced to a
single pair and the localAlt is set to one of the components of the
single pair SPFD. */
SpfdRegionComputeSinglePairSpfd(network,applData,regionArray);
/* Now check if the spfd of wire maxNode --> ntkNode is
empty. Remove the spfd of ntkNode as it was not deleted in
SpfdRegionComputeSinglePairSpfd */
/* Compute array of potential candidates for replacement */
if (replRem)
replArray = SpfdNodeComputeTFIUntilDepth(ntkNode,regionDepth);
else
replArray = NIL(array_t);
replNode = SpfdCheckIfWireIsRedundantOrReplaceable(network,applData,
maxNode,ntkNode,
replArray);
/* SPFD of ntkNode is no longer needed. */
SpfdNodeDeleteSpfd(applData,ntkNode);
if (replArray)
array_free(replArray);
/* Check to see if wires have been found to be
redundant/replaceable. If no wires are to be
removed/replaced, then decide whether or not to reprogram. */
if (st_count(applData->currWireTable) == 0 &&
st_count(applData->currReplaceTable) == 0 &&
!spfdReprogNoWire) {
/* In this case just clean up currBddReq, localAlt
and globalAlt. */
st_table *currBddReq;
st_generator *stGen;
Ntk_Node_t *regNode;
bdd_node *bdd1;
bdd_manager *ddManager;
int j;
ddManager = applData->ddManager;
currBddReq = applData->currBddReq;
/* Clean up currBddReq */
st_foreach_item(currBddReq,stGen,®Node,&bdd1) {
bdd_recursive_deref(ddManager,bdd1);
}
st_free_table(currBddReq);
applData->currBddReq = NIL(st_table);
/* Clean up localAlt and globalAlt of region nodes */
arrayForEachItem(Ntk_Node_t *,regionArray,j,regNode) {
SpfdNodeDeleteGlobalAlternative(applData,regNode);
SpfdNodeDeleteLocalAlt(applData,regNode);
}
} else {
/* Now reprogram the nodes in the region. */
SpfdReprogramRegionNodes(network,applData,regionArray);
}
/* In this subroutine we have only a single wire
replaced. Delete just that data */
if (replNode) {
SpfdNodeDeleteGlobalAlternative(applData,replNode);
SpfdNodeSetAuxId(applData,replNode,-1);
st_delete(applData->currReplaceTable,&ntkNode,
&sinkTable);
st_free_table(sinkTable);
/* A small caveat: sometimes a wire added can be later
removed. Check if the replNode --> ntkNode still exists. If
not set replNode to NULL. */
wiresRemoved = applData->wiresRemoved;
if (st_lookup(wiresRemoved,(char *)replNode,&sinkTable) &&
st_lookup(sinkTable,(char *)ntkNode,NIL(char *))) {
/* Reduce the number of wires added and delete
replNode->ntkNode from wiresRemoved table */
spfdWiresAdded--;
st_delete(sinkTable,&ntkNode,NIL(char *));
if (st_count(sinkTable) < 1) {
st_delete(wiresRemoved,&replNode,&sinkTable);
st_free_table(sinkTable);
}
replNode = NIL(Ntk_Node_t);
}
}
/* Clean up auxIds and piAltVars*/
SpfdCleanUpAuxIds(applData);
/* Free stuff used only for the current wire */
if (applData->currXCube) {
bdd_recursive_deref(applData->ddManager,applData->currXCube);
applData->currXCube = NIL(bdd_node);
}
if (applData->currRegionNodes) {
st_free_table(applData->currRegionNodes);
applData->currRegionNodes = NIL(st_table);
}
if (applData->currInUseVars) {
st_free_table(applData->currInUseVars);
applData->currInUseVars = NIL(st_table);
}
num = st_count(applData->currWireTable);
assert(num == 0);
num = st_count(applData->currReplaceTable);
assert(num == 0);
/* Update the total number of wires removed. */
wiresRemoved = applData->wiresRemoved;
if (st_count(wiresRemoved) > 0) {
st_foreach_item(wiresRemoved,stGen,&tempNode,
&sinkTable){
spfdNumWiresRem += st_count(sinkTable);
}
/* free the wiresRemoved contents */
st_foreach(wiresRemoved,SpfdStTableClean,NIL(char));
}
/* Free regionArray (cluster) */
array_free(regionArray);
return ;
} /* End of SpfdOptimizeWire */
Here is the call graph for this function:
Here is the caller graph for this function:
| Ntk_Node_t* SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd | ( | Ntk_Network_t * | network, |
| array_t * | replaceArray, | ||
| Ntk_Node_t * | from, | ||
| Ntk_Node_t * | to, | ||
| bdd_node * | wireSpfd | ||
| ) |
Function********************************************************************
Synopsis [Checks if the global functions implemented by nodes in 'replaceArray' satisfy the SPFD, 'wireSpfd' of 'from' --> 'to'.]
SideEffects [None]
Definition at line 561 of file spfdOpt.c.
{
SpfdApplData_t *applData;
bdd_manager *ddManager;
st_table *leavesTable,*inUseVars,*replaceTable;
st_table *sinkTable,*currBddReq;
bdd_t *mddOne;
lsGen gen;
Ntk_Node_t *fanin,*node,*replNode;
Ntk_Node_t *foundNode;
array_t *nodeMvfs,*nodeBdds;
bdd_node *bdd1,*xCube,*yVar;
bdd_node **tempVars,**firstCompose,**secondCompose;
bdd_node *step1,*step2,*step3,*step4,*step5;
bdd_node *logicZero;
int i,j,size,replId,id,auxId;
applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
SPFD_NETWORK_APPL_KEY);
ddManager = applData->ddManager;
inUseVars = applData->currInUseVars;
replaceTable = applData->currReplaceTable;
currBddReq = applData->currBddReq;
mddOne = bdd_one(ddManager);
logicZero = bdd_read_logic_zero(ddManager);
/* Collect the leaf nodes of the network. */
leavesTable = st_init_table(st_ptrcmp, st_ptrhash);
Ntk_NetworkForEachCombInput(network,gen,node) {
st_insert(leavesTable,(char *)node,(char *) -1);
}
/* Compute the global MVFs of the nodes in replaceArray */
nodeMvfs = Ntm_NetworkBuildMvfs(network,replaceArray,leavesTable,mddOne);
bdd_free(mddOne);
st_free_table(leavesTable);
/* Collect node global Bdds */
nodeBdds = array_alloc(bdd_node *,0);
arrayForEachItem(Ntk_Node_t *,replaceArray,i,node) {
Mvf_Function_t *mvf;
mvf = array_fetch(Mvf_Function_t *,nodeMvfs,i);
bdd1 = bdd_extract_node_as_is(array_fetch(bdd_t *,mvf,1));
bdd_ref(bdd1);
array_insert_last(bdd_node *,nodeBdds,bdd1);
}
Mvf_FunctionArrayFree(nodeMvfs);
/* Now check one at a time if global function satisfies wireSpfd */
foundNode = NIL(Ntk_Node_t);
xCube = applData->currXCube;
arrayForEachItem(Ntk_Node_t *,nodeBdds,i,bdd1) {
int idAllocated;
idAllocated = 0;
replNode = array_fetch(Ntk_Node_t *,replaceArray,i);
replId = Ntk_NodeReadMddId(replNode);
/* Check if replId is already in use. This is possible is outside
the cluster. */
if (st_lookup(inUseVars,(char *)(long)replId,NIL(char *))) {
/* Allocate yVar and yAuxVar for replNode */
tempVars = SpfdAllocateTemporaryVariables(ddManager,inUseVars,1);
yVar = tempVars[0];
idAllocated = 1;
FREE(tempVars);
} else { /* replId not in use */
yVar = bdd_bdd_ith_var(ddManager,replId);
}
/* Now perform the following steps, using two compositions. */
/* 1. step1 = yVar == bdd1
2. step2 = wireSpfd(Y,Y') --> wireSpfd(x,Y')
3. step3 = \exists_x step1 * step2
4. step4 = step3(yVar,Y') --> step3(yVar,x)
5. step5 = \exists_x step1 * step4
If step5 == logicZero, then replNode is a candidate */
/* Prepare compose arrays for the above steps */
size = bdd_num_vars(ddManager);
firstCompose = ALLOC(bdd_node *,size);
secondCompose = ALLOC(bdd_node *,size);
for (j = 0; j < size; j++) {
firstCompose[j] = bdd_bdd_ith_var(ddManager,j);
secondCompose[j] = bdd_bdd_ith_var(ddManager,j);
}
Ntk_NodeForEachFanin(to,j,fanin) {
id = Ntk_NodeReadMddId(fanin);
auxId = SpfdNodeReadAuxId(applData,fanin);
st_lookup(currBddReq,(char *)fanin,(char **)&firstCompose[id]);
secondCompose[auxId] = firstCompose[id];
}
bdd_ref(step1 = bdd_bdd_xnor(ddManager,yVar,bdd1));
bdd_ref(step2 = bdd_bdd_vector_compose(ddManager,wireSpfd,firstCompose));
FREE(firstCompose);
bdd_ref(step3 = bdd_bdd_and_abstract(ddManager,step1,step2,xCube));
bdd_recursive_deref(ddManager,step2);
bdd_ref(step4 = bdd_bdd_vector_compose(ddManager,step3,secondCompose));
bdd_recursive_deref(ddManager,step3);
FREE(secondCompose);
bdd_ref(step5 = bdd_bdd_and_abstract(ddManager,step1,step4,xCube));
bdd_recursive_deref(ddManager,step4);
bdd_recursive_deref(ddManager,step1);
/* Now if step5 is zero, then return replNode as the candidate. I will use
the globalAlt field of the node to store the global BDD. This way I
don't have to recompute the global BDD later. */
if (step5 == logicZero) {
bdd_recursive_deref(ddManager,step5);
bdd_ref(bdd1);
SpfdNodeSetGlobalAlternative(applData,replNode,bdd1);
/* Allocate an auxId for this node. It will be needed during
reprogramming. */
if (idAllocated) {
auxId = bdd_node_read_index(yVar);
} else {
tempVars = SpfdAllocateTemporaryVariables(ddManager,inUseVars,1);
auxId = bdd_node_read_index(tempVars[0]);
FREE(tempVars);
}
SpfdNodeSetAuxId(applData,replNode,auxId);
st_insert(inUseVars,(char *)(long)replId,(char *)-1);
st_insert(inUseVars,(char *)(long)auxId,(char *)-1);
/* Insert information in replaceTable */
if (st_lookup(replaceTable,(char *)to,&sinkTable)) {
st_insert(sinkTable,(char *)from,(char *)replNode);
} else {
sinkTable = st_init_table(st_ptrcmp,st_ptrhash);
st_insert(sinkTable,(char *)from,(char *)replNode);
st_insert(replaceTable,(char *)to,(char *)sinkTable);
}
foundNode = replNode;
break;
} else {
bdd_recursive_deref(ddManager,step5);
/* release the id */
if (idAllocated) {
id = bdd_node_read_index(yVar);
st_delete(inUseVars, &id, NIL(char *));
}
}
}
/* Free the nodeBdds */
arrayForEachItem(bdd_node *,nodeBdds,i,bdd1) {
bdd_recursive_deref(ddManager,bdd1);
}
array_free(nodeBdds);
return foundNode;
} /* End of SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd */
Here is the call graph for this function:
Here is the caller graph for this function:
