Internal data structures for the spfd package. 

static Tbl_Table_t * 
BuildNewTable(
  Ntk_Network_t * network, 
  Ntk_Node_t * ntkNode, 
  mdd_t * mddFunc 
)
Update the Table data structure of ntkNode. See tbl package for more details on the Table data structure.

Side Effects None

Defined in spfdProg.c 

static int 
CommandSpfdNetworkOptimize(
  Hrc_Manager_t ** hmgr, 
  int  argc, 
  char ** argv 
)
Implements SPFD-based placement independent logic optimization command, spfd_pilo, for combinational circuits mapped to LUT-based FPGAs.

Side Effects The network is changed to reflect the wires/nodes removed or replaced. The internal function of the nodes is also changed. The partition attached to the network is changed accordingly.

Defined in spfdCmd.c 

static int 
CommandSpfdPlaceOptimize(
  Hrc_Manager_t ** hmgr, 
  int  argc, 
  char ** argv 
)
Implements SPFD-based simultaneous placement and logic optimization command, spfd_pdlo, for combinational circuits mapped to LUT-based FPGAs.

Side Effects The network is changed to reflect the wires/nodes removed or replaced. The internal function of the nodes is also changed. The partition attached to the network is changed accordingly.

Defined in spfdCmd.c 

static int 
CompareConvexFanoutCountAndDepth(
  char ** obj1, 
  char ** obj2 
)
Compare the convex combination of fanout count and the node's topological depth.

Side Effects None

Defined in spfdOpt.c 

static int 
CompareConvexSwitchedCapAndDepth(
  char ** obj1, 
  char ** obj2 
)
Compare the convex combination of switched capacitance and topological depth of two nodes.

Side Effects None

Defined in spfdOpt.c 

static bdd_node * 
ComputeAuxRel(
  SpfdApplData_t * applData, 
  bdd_node * faninRel, 
  Ntk_Node_t * from, 
  int  piSwap 
)
Convert faninRel which is interms of Y, to Y', the auxillary variables.

Side Effects None

Defined in spfdSpfd.c 

static bdd_node * 
NodeComputeGeneralProbability(
  Ntk_Network_t * network, 
  bdd_manager * ddManager, 
  Ntk_Node_t * regNode, 
  bdd_node * result 
)
Returns the ADD representing the signal probability of regNode. 'result' is the BDD which has in support the variables in the fanin of regNode.

Side Effects None

Defined in spfdCommon.c 

static enum st_retval 
NodeDataFree(
  char * key, 
  char * value, 
  char * arg 
)
Free SpfdNodeData_t

Side Effects None

Defined in spfdClean.c 

bdd_node * 
SpfdAddEqual(
  bdd_manager * ddManager, 
  bdd_node ** f, 
  bdd_node ** g 
)
Returns a BDD containing minterms such that the discriminant for those minterms in f is equal to that in g. Used in bdd_add_apply().

Side Effects None

See Also cuddAddApply.c
Defined in spfdUtil.c 

void 
SpfdAllocateOrReuseAuxVariables(
  Ntk_Network_t * network, 
  SpfdApplData_t * applData 
)
Recyle existing BDD variables or allocate new ones.

Side Effects The BDD manager is changed accordingly to reflect the addition of new variables.

Defined in spfdUtil.c 

bdd_node ** 
SpfdAllocateTemporaryVariables(
  bdd_manager * ddManager, 
  st_table * inUseVars, 
  int  num 
)
Allocate num of BDD variables.

Side Effects None

Defined in spfdUtil.c 

void 
SpfdApplFreeCallback(
  void * data 
)
Routine to free the application data structure attached by this package to network. Certain fields of the SpfdApplData_t are freed earlier.

Side Effects None

Defined in spfdClean.c 

Ntk_Node_t * 
SpfdCheckIfWireIsRedundantOrReplaceable(
  Ntk_Network_t * network, 
  SpfdApplData_t * applData, 
  Ntk_Node_t * from, 
  Ntk_Node_t * to, 
  array_t * replaceArray 
)
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.

Side Effects None

Defined in spfdOpt.c 

void 
SpfdCleanUpAuxIds(
  SpfdApplData_t * applData 
)
Return auxillay BDD ids to the pool.

Side Effects None

Defined in spfdClean.c 

bdd_node * 
SpfdComputeNodeArrayRelation(
  SpfdApplData_t * applData, 
  st_table * currBddReq, 
  array_t * nodeBdds, 
  array_t * nodeArray, 
  boolean  useMddIds, 
  int * piSwap 
)
Compute the relation of the functions specified in either nodeBdds and currBddReq. If 'useMddIds' is TRUE use node (from nodeArray) MDD ids else use node aux Ids. Return value of 'piSwap' is used in the calling function only when 'useMddIds' is TRUE.

Side Effects None

Defined in spfdUtil.c 

bdd_node ** 
SpfdComputeParameters(
  SpfdApplData_t * applData, 
  st_table * SCC 
)
Given a set of 'num' (st_count(SCC)) pairs of functions, compute 'num' binary variables and allocate BDD ids to those variables such that their level is above all the variables in the support of the functions in SCC.

Side Effects None

Defined in spfdUtil.c 

void 
SpfdComputeRequiredGlobalBdds(
  Ntk_Network_t * network, 
  SpfdApplData_t * applData 
)
Global BDDs are required during the computation of SPFDs for cluster members. We compute them once and use it when needed. Also, these BDDs are removed when they are no longer required. Gloabl BDDs are required for all nodes in the cluster and their respective fanin nodes.

Side Effects None

Defined in spfdCommon.c 

int 
SpfdDepthCompare(
  char ** obj1, 
  char ** obj2 
)
Compare the topological depth of two nodes.

Side Effects None

Defined in spfdUtil.c 

int 
SpfdDescendDepthCompare(
  char ** obj1, 
  char ** obj2 
)
Same as SpfdDepthCompare, but the nodes will be sorted in descending order when used by qsort.

Side Effects None

Defined in spfdUtil.c 

int 
SpfdFanoutCountAndDepthCompare(
  char ** obj1, 
  char ** obj2 
)
Compare the convex combination of fanout count and the node's topological depth.

Side Effects None

Defined in spfdUtil.c 

array_t * 
SpfdFetchInternalPatternArray(
  array_t * patternArray, 
  int  percent, 
  double  randomValue 
)
Extract 'percent'% vectors from the patternArray.

Side Effects None

Defined in spfdUtil.c 

Ntk_Node_t * 
SpfdFindNode(
  Ntk_Network_t * network, 
  array_t * nodeArray 
)
optional

Side Effects required

See Also optional
Defined in spfdUtil.c 

SpfdApplData_t * 
SpfdInitializeApplData(
  Ntk_Network_t * network 
)
Initialize the application data structure of the package.

Side Effects None

Defined in spfdUtil.c 

void 
SpfdMddCreateVariables(
  mdd_manager * mgr, 
  int  numVarsToBeAdded, 
  int  level 
)
This procedure calls the mdd_create_variables in order to create new variables. IMPORTANT: The mdd_create_variables procedure creates the variables in succession. So if new variables are required that are not in succession, those will not be created and hence cannot be used. This procedure takes as arguments the DD manager and the number of variables that need to be added to the manager.

Side Effects It modifies the manager->hook->mdd field.

Defined in spfdUtil.c 

void 
SpfdNetworkAddWire(
  Ntk_Network_t * network, 
  Ntk_Node_t * from, 
  Ntk_Node_t * to 
)
Add a wire from --> to

Side Effects None

Defined in spfdProg.c 

int 
SpfdNetworkOptimize(
  Ntk_Network_t * network, 
  char * simFile, 
  int  percent, 
  int  frequency, 
  int  regionDepth 
)
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'.

Side Effects None

Defined in spfdOpt.c 

void 
SpfdNetworkRemoveWire(
  Ntk_Network_t * network, 
  Ntk_Node_t * from, 
  Ntk_Node_t * to 
)
Remove the wire from --> to.

Side Effects None

Defined in spfdProg.c 

int 
SpfdNetworkWriteBlifFile(
  Ntk_Network_t * network, 
  char * fileName 
)
Print the network in BLIF format to fileName.

Side Effects None

Defined in spfdUtil.c 

array_t * 
SpfdNodeComputeFanoutRegion(
  SpfdApplData_t * applData, 
  Ntk_Node_t * startNode, 
  int  regionDepth 
)
Find a cluster of nodes that are within regionDepth of startNode.

Side Effects None

Defined in spfdReg.c 

bdd_node * 
SpfdNodeComputeOptParams(
  SpfdApplData_t * applData, 
  Ntk_Node_t * regNode, 
  bdd_node * result, 
  bdd_node ** parameters, 
  int  numIsfs 
)
Collapse the SCCs in a node's SPFD into a binary SPFD by appropriately choosing a binary value associated with each of the SCCs. This function is used only when signal probabilites are known, i.e, only when vector simulation is performed. 'result' is the characteristic function of the set of SCCs combined with the parameters. For example, if {(E1_i,E0_i)} is the set of bipartite SCCs, result(Y,P) = sum (p_i*E1_i + bar{p}_i*E0_i). This function computes assignments to p_i such that the 'result' has lower switching activity than the previous implementation at regNode.

Side Effects None

Defined in spfdCommon.c 

st_table * 
SpfdNodeComputeSCCs(
  SpfdApplData_t * applData, 
  Ntk_Node_t * regNode, 
  bdd_node ** tempVars 
)
Compute the strongly connected components in the SPFD of regNode. 'tempVars' are extra variables required during this computation. For detailed description please refer to: Subarnarekha Sinha and Robert K. Brayton. Implementation and use of SPFDs in optimizaing Boolean networks. In International Conference on Computer Aided Design, 1998.

Side Effects None

Defined in spfdSpfd.c 

bdd_node * 
SpfdNodeComputeSpfdFromFanouts(
  SpfdApplData_t * applData, 
  Ntk_Node_t * from 
)
Compute the SPFD of 'from', as the union of SPFDs of its fanout wires.

Side Effects None

Defined in spfdSpfd.c 

bdd_node * 
SpfdNodeComputeSpfdFromOnAndOffSet(
  SpfdApplData_t * applData, 
  Ntk_Node_t * regNode, 
  bdd_node * bdd1, 
  bdd_node * bdd0 
)
Given two functions represented by bdd1 and bdd0, compute its SPFD.

Side Effects None

Defined in spfdSpfd.c 

array_t * 
SpfdNodeComputeTFIUntilDepth(
  Ntk_Node_t * startNode, 
  int  regionDepth 
)
The returned array contains the nodes in TFI of startNode, except the immediate fanin of startNode.

Side Effects None

Defined in spfdReg.c 

void 
SpfdNodeDeleteFaninOrder(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Delete the sorted array of fanin nodes.

Side Effects None

Defined in spfdAPI.c 

void 
SpfdNodeDeleteGlobalAlternative(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Delete the global BDD of the node. The global BDD is derived from the node's spfd.

Side Effects None

See Also SpfdNodeReadGlobalAlternative
Defined in spfdAPI.c 

void 
SpfdNodeDeleteLocalAlt(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Delete the local BDD, which is in terms of the node's immediate fanin.

Side Effects None

Defined in spfdAPI.c 

void 
SpfdNodeDeleteParameters(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Free the array of BDD variables (parameters) associated with the spfd of the node.

Side Effects None

Defined in spfdAPI.c 

void 
SpfdNodeDeleteSpfd(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Free the BDD representing the spfd of the node.

Side Effects None

Defined in spfdAPI.c 

int 
SpfdNodeReadAuxId(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Read the auxillary BDD id associated with the node.

Side Effects None

Defined in spfdAPI.c 

array_t * 
SpfdNodeReadFaninOrder(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Read the sorted array of fanin nodes.

Side Effects None

Defined in spfdAPI.c 

bdd_node * 
SpfdNodeReadGlobalAlternative(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Read the global BDD of the node. The global BDD is derived from the node's spfd.

Side Effects SpfdNodeDeleteGlobalAlternative

Defined in spfdAPI.c 

bdd_node * 
SpfdNodeReadLocalAlt(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Read the local BDD, which is in terms of the node's immediate fanin.

Side Effects None

Defined in spfdAPI.c 

bdd_node * 
SpfdNodeReadLocalBdd(
  Ntk_Network_t * network, 
  Ntk_Node_t * node 
)
The node's BDD is returned as it is without increasing the reference count.

Side Effects None

Defined in spfdUtil.c 

boolean 
SpfdNodeReadLocked(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Returns whether the node is locked.

Side Effects None

Defined in spfdAPI.c 

int 
SpfdNodeReadNetIndex(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
This is used to get the index of the source of the net data structure used in VPR.

Side Effects None

Defined in spfdAPI.c 

int 
SpfdNodeReadNumParams(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Read the number of parameters associated with the node's SPFD.

Side Effects None

Defined in spfdAPI.c 

bdd_node ** 
SpfdNodeReadParameters(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Read the array of BDD variables (parameters) associated with the spfd of the node.

Side Effects None

Defined in spfdAPI.c 

bdd_node * 
SpfdNodeReadSpfd(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node 
)
Read the node's spfd.

Side Effects None

Defined in spfdAPI.c 

void 
SpfdNodeReduceSCCToSinglePair(
  SpfdApplData_t * applData, 
  Ntk_Node_t * regNode, 
  st_table * SCC 
)
Reduce the set of SCCs in a SPFD to a single SCC, i.e, to reduce to a binary SPFD.

Side Effects None

Defined in spfdCommon.c 

void 
SpfdNodeSetAuxId(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node, 
  int  auxId 
)
Set the auxillary BDD id for the node

Side Effects None

Defined in spfdAPI.c 

void 
SpfdNodeSetFaninOrder(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node, 
  array_t * faninOrder 
)
Set the array faninOrder required during SPFD computation.

Side Effects None

Defined in spfdAPI.c 

void 
SpfdNodeSetGlobalAlternative(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node, 
  bdd_node * alternative 
)
Set the BDD as the node's global BDD.

Side Effects None

Defined in spfdAPI.c 

void 
SpfdNodeSetLocalAlt(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node, 
  bdd_node * localAlt 
)
Set localAlt as the local BDD. localAlt is in terms of the node's immediate fanin.

Side Effects None

Defined in spfdAPI.c 

void 
SpfdNodeSetLocked(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node, 
  boolean  locked 
)
Set the node as locked.

Side Effects None

Defined in spfdAPI.c 

void 
SpfdNodeSetParameters(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node, 
  bdd_node ** parameters, 
  int  numParams 
)
Set the array of BDD variables (parameters) associated with the spfd of the node.

Side Effects None

Defined in spfdAPI.c 

void 
SpfdNodeSetSpfd(
  SpfdApplData_t * applData, 
  Ntk_Node_t * node, 
  bdd_node * spfd 
)
Set the node's spfd

Side Effects None

Defined in spfdAPI.c 

void 
SpfdNodesInTFO(
  Ntk_Network_t * network, 
  Ntk_Node_t * node, 
  st_table * tfoNodes 
)
Returns in tfoNodes, the nodes in the transitive fanout of node.

Side Effects None

Defined in spfdReg.c 

void 
SpfdOptimizeFaninNodes(
  Ntk_Network_t * network, 
  Ntk_Node_t * maxNode, 
  int  regionDepth 
)
Optimize all the fanin nodes of maxNode.

Side Effects None

Defined in spfdOpt.c 

void 
SpfdOptimizeFaninWires(
  Ntk_Network_t * network, 
  Ntk_Node_t * maxNode, 
  int  regionDepth, 
  boolean  replRem 
)
Try to remove/replace the fanin wires of maxNode.

Side Effects None

See Also SpfdOptimizeFanoutWires
Defined in spfdOpt.c 

void 
SpfdOptimizeFanoutWires(
  Ntk_Network_t * network, 
  Ntk_Node_t * maxNode, 
  int  regionDepth, 
  boolean  replRem 
)
Try to remove/replace the fanout wires of maxNode.

Side Effects None

See Also SpfdOptimizeFaninWires
Defined in spfdOpt.c 

void 
SpfdOptimizeNode(
  Ntk_Network_t * network, 
  Ntk_Node_t * ntkNode, 
  int  regionDepth 
)
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.

Side Effects None

Defined in spfdOpt.c 

void 
SpfdOptimizeWire(
  Ntk_Network_t * network, 
  Ntk_Node_t * maxNode, 
  Ntk_Node_t * ntkNode, 
  int  regionDepth, 
  boolean  replRem 
)
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.

Side Effects None

Defined in spfdOpt.c 

void 
SpfdOrderFaninOfRegionNodes(
  Ntk_Network_t * network, 
  SpfdApplData_t * applData, 
  int  (*compareFunc)(char **, char **) 
)
Fanin nodes of each cluster node is ordered according to the 'compareFunc'. The fanin nodes need to be ordered during SPFD computation.

Side Effects None

Defined in spfdUtil.c 

void 
SpfdProcessFanoutWires(
  Ntk_Network_t * network, 
  Ntk_Node_t * maxNode, 
  int  regionDepth, 
  boolean  replRem 
)
Optimize the cluster of nodes in the fanout of each fanout wire of maxNode. The cluster is formed of those nodes that are within 'regionDepth' of the fanout wire. Both wire removal and replacement are performed if 'replRem' is true.

Side Effects None

Defined in spfdOpt.c 

void 
SpfdRegionComputeSinglePairSpfd(
  Ntk_Network_t * network, 
  SpfdApplData_t * applData, 
  array_t * regionArray 
)
Compute SPFDs for the nodes in regionArray, i.e., the cluster. regionArray is sorted in the increasing order of topological depth.

Side Effects None

Defined in spfdCommon.c 

void 
SpfdReleaseAlternatePiIds(
  SpfdApplData_t * applData, 
  Ntk_Node_t * regNode, 
  st_table * nodeTable 
)
Release those alternate PI ids that are no longer necessary. This is necessary as we resuse the BDD variable IDs.

Side Effects None

Defined in spfdClean.c 

void 
SpfdReleaseAndCleanNodeData(
  SpfdApplData_t * applData, 
  Ntk_Node_t * regNode, 
  st_table * nodeTable 
)
Release those ids that will no longer be necessary, also delete global and local BDDs. After an alternate implementation at 'regNode' is found, BDDs (local function, global function, BDD variable ID and auxillary BDD ID) at its fanin may no longer be necessary. nodeTable stores the pair . 'count' indicates how may times the BDDs at that node will be accessed. Such BDDs are freed when appropriate, i.e., 'count' = 0.

Side Effects None

Defined in spfdClean.c 

void 
SpfdReprogramNode(
  Ntk_Network_t * network, 
  SpfdApplData_t * applData, 
  Ntk_Node_t * regNode 
)
Update the regNode's Table data structure based on the alternate implementation chosen for it in SpfdReprogramRegionNodes.

Side Effects None

Defined in spfdProg.c 

void 
SpfdReprogramRegionNodes(
  Ntk_Network_t * network, 
  SpfdApplData_t * applData, 
  array_t * regionArray 
)
Reprogram the nodes in the 'regionArray' based on an alternate implementation selected from the SPFDs. The cluster nodes are reprogrammed in the increasing order of their topological depth. When a node is being reprogrammed all of its fanin have either been reprogrammed or have retained their original implementation.

Side Effects None

Defined in spfdProg.c 

static int 
SpfdSimultaneousPlacementAndLogicOpt(
  Ntk_Network_t * network, 
  char * netFile, 
  char * archFile, 
  char * placeFile, 
  char * routeFile, 
  char * netOutFile, 
  int  regionDepth 
)
Dummy function

Side Effects None

Defined in spfdCmd.c 

enum st_retval 
SpfdStBddFree(
  char * key, 
  char * value, 
  char * arg 
)
Free BDDs stored in a st_table.

Side Effects None

Defined in spfdClean.c 

enum st_retval 
SpfdStTableClean(
  char * key, 
  char * value, 
  char * arg 
)
This function frees the table stored as 'value' in an st_table and returns ST_DELETE so that memory allocated for 'key' is also freed. In the end the table is 'cleaned' but not 'freed.

Side Effects None

Defined in spfdClean.c 

bdd_node * 
SpfdSwapPiAndAltPi(
  SpfdApplData_t * applData, 
  bdd_node * fun 
)
Swap the BDD variables of primary inputs and it's auxillary BDD ids.

Side Effects None

Defined in spfdUtil.c 

int 
SpfdSwitchedCapAndDepthCompare(
  char ** obj1, 
  char ** obj2 
)
Compare the convex combination of switched capacitance and topological depth of two nodes.

Side Effects None

Defined in spfdUtil.c 

Ntk_Node_t * 
SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd(
  Ntk_Network_t * network, 
  array_t * replaceArray, 
  Ntk_Node_t * from, 
  Ntk_Node_t * to, 
  bdd_node * wireSpfd 
)
Checks if the global functions implemented by nodes in 'replaceArray' satisfy the SPFD, 'wireSpfd' of 'from' --> 'to'.

Side Effects None

Defined in spfdOpt.c 

void 
Spfd_End(
    
)
This function ends the spfd package.

Side Effects None

See Also Spfd_Init
Defined in spfdCmd.c 

void 
Spfd_Init(
    
)
This function initializes the spfd package.

Side Effects None

See Also Spfd_End
Defined in spfdCmd.c 

static void 
TableAddCube(
  Tbl_Table_t * table, 
  array_t * faninIdArray, 
  array_t * cube, 
  int  value 
)
convert a cube into a row entry of the Table. See tbl package for more details.

Side Effects None

Defined in spfdProg.c 

static int 
TestIsNetworkMultipleValued(
  Ntk_Network_t * network 
)
Checks whether the network has multiple valued signals. Returns 1 if true, else 0.

Side Effects None

Defined in spfdCmd.c 

static void 
TimeOutHandle(
    
)
This function is called when the time out occurs.

Defined in spfdCmd.c
Last updated on 20010517 18h00
Contact 
©2002-2018 U.C. Regents