spfdAPI.c

Routines to read, delete and update data structures used in the package.

spfdClean.c

Routines to free memory when not needed.

spfdCmd.c

Interface functions for commands spfd_pilo and spfd_pdlo.

spfdCommon.c

Essential routines required during SPFD computation.

spfdOpt.c

Routines that implement spfd_pilo.

spfdProg.c

Routines that perform reprogramming of LUTs (nodes) in the circuit.

spfdReg.c

Routines to compute a cluster of nodes for optimization.

spfdSpfd.c

Routines to perform SPFD computation.

spfdUtil.c

Utility routines for the spfd package.

By: Balakrishna Kumthekar

Routines to read, delete and update data structures used in the package.

See AlsospfdUtil.c spfdClean.c

SpfdNodeReadLocked()

Returns whether the node is locked.

SpfdNodeReadAuxId()

Read the auxillary BDD id associated with the node.

SpfdNodeSetAuxId()

Set the auxillary BDD id for the node

SpfdNodeReadSpfd()

Read the node's spfd.

SpfdNodeDeleteSpfd()

Free the BDD representing the spfd of the node.

SpfdNodeSetSpfd()

Set the node's spfd

SpfdNodeReadParameters()

Read the array of BDD variables (parameters) associated with the spfd of the node.

SpfdNodeDeleteParameters()

Free the array of BDD variables (parameters) associated with the spfd of the node.

SpfdNodeSetParameters()

Set the array of BDD variables (parameters) associated with the spfd of the node.

SpfdNodeReadFaninOrder()

Read the sorted array of fanin nodes.

SpfdNodeDeleteFaninOrder()

Delete the sorted array of fanin nodes.

SpfdNodeSetFaninOrder()

Set the array faninOrder required during SPFD computation.

SpfdNodeReadGlobalAlternative()

Read the global BDD of the node. The global BDD is derived from the node's spfd.

SpfdNodeDeleteGlobalAlternative()

Delete the global BDD of the node. The global BDD is derived from the node's spfd.

SpfdNodeSetGlobalAlternative()

Set the BDD as the node's global BDD.

SpfdNodeReadLocalAlt()

Read the local BDD, which is in terms of the node's immediate fanin.

SpfdNodeDeleteLocalAlt()

Delete the local BDD, which is in terms of the node's immediate fanin.

SpfdNodeSetLocalAlt()

Set localAlt as the local BDD. localAlt is in terms of the node's immediate fanin.

SpfdNodeSetLocked()

Set the node as locked.

SpfdNodeReadNumParams()

Read the number of parameters associated with the node's SPFD.

SpfdNodeReadNetIndex()

This is used to get the index of the source of the net data structure used in VPR.

By: Balakrishna Kumthekar

Routines to free memory when not needed.

See AlsospfdAPI.c spfdUtil.c

SpfdApplFreeCallback()

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

SpfdStBddFree()

Free BDDs stored in a st_table.

SpfdStTableClean()

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.

SpfdReleaseAndCleanNodeData()

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.

SpfdReleaseAlternatePiIds()

Release those alternate PI ids that are no longer necessary. This is necessary as we resuse the BDD variable IDs.

SpfdCleanUpAuxIds()

Return auxillay BDD ids to the pool.

NodeDataFree()

Free SpfdNodeData_t

By: Balakrishna Kumthekar

Interface functions for commands spfd_pilo and spfd_pdlo.

See AlsospfdOpt.c

Spfd_Init()

This function initializes the spfd package.

Spfd_End()

This function ends the spfd package.

CommandSpfdNetworkOptimize()

Implements SPFD-based placement independent logic optimization command, spfd_pilo, for combinational circuits mapped to LUT-based FPGAs.

CommandSpfdPlaceOptimize()

Implements SPFD-based simultaneous placement and logic optimization command, spfd_pdlo, for combinational circuits mapped to LUT-based FPGAs.

TimeOutHandle()

Handle function for timeout.

TestIsNetworkMultipleValued()

Checks whether the network has multiple valued signals.

SpfdSimultaneousPlacementAndLogicOpt()

Dummy function

By: Balakrishna Kumthekar

Essential routines required during SPFD computation.

See AlsospfdSpfd.c

SpfdRegionComputeSinglePairSpfd()

Compute SPFDs for the nodes in regionArray, i.e., the cluster. regionArray is sorted in the increasing order of topological depth.

SpfdNodeComputeOptParams()

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.

SpfdNodeReduceSCCToSinglePair()

Reduce the set of SCCs in a SPFD to a single SCC, i.e, to reduce to a binary SPFD.

SpfdComputeRequiredGlobalBdds()

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.

NodeComputeGeneralProbability()

Returns the ADD representing the signal probability of regNode. 'result' is the BDD which has in support the variables in the fanin of regNode.

By: Balakrishna Kumthekar

Routines that implement spfd_pilo.

See AlsospfdCmd.c spfdReg.c spfdProg.c

SpfdNetworkOptimize()

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.

SpfdProcessFanoutWires()

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.

SpfdCheckIfWireIsRedundantOrReplaceable()

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.

SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd()

Checks if the global functions implemented by nodes in 'replaceArray' satisfy the SPFD, 'wireSpfd' of 'from' --> 'to'.

SpfdOptimizeFaninWires()

Try to remove/replace the fanin wires of maxNode.

SpfdOptimizeFanoutWires()

Try to remove/replace the fanout wires of maxNode.

SpfdOptimizeFaninNodes()

Optimize all the fanin nodes of maxNode.

SpfdOptimizeWire()

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.

SpfdOptimizeNode()

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.

CompareConvexFanoutCountAndDepth()

Compare the convex combination of fanout count and the node's topological depth.

CompareConvexSwitchedCapAndDepth()

Compare the convex combination of switched capacitance and topological depth of two nodes.

By: Balakrishna Kumthekar

Routines that perform reprogramming of LUTs (nodes) in the circuit. Wire removal/addition operations are also performed.

See AlsospfdOpt.c spfdSpfd.c

SpfdReprogramRegionNodes()

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.

SpfdReprogramNode()

Update the regNode's Table data structure based on the alternate implementation chosen for it in SpfdReprogramRegionNodes.

SpfdNetworkRemoveWire()

Remove the wire from --> to.

SpfdNetworkAddWire()

Add a wire from --> to

BuildNewTable()

Update the Table data structure of ntkNode. See tbl package for more details on the Table data structure.

TableAddCube()

convert a cube into a row entry of the Table. See tbl package for more details.

By: Balakrishna Kumthekar

Routines to compute a cluster of nodes for optimization.

See AlsospfdOpt.c

SpfdNodeComputeFanoutRegion()

Find a cluster of nodes that are within regionDepth of startNode.

SpfdNodeComputeTFIUntilDepth()

The returned array contains the nodes in TFI of startNode, except the immediate fanin of startNode.

SpfdNodesInTFO()

Returns in tfoNodes, the nodes in the transitive fanout of node.

By: Balakrishna Kumthekar

Routines to perform SPFD computation.

See AlsospfdProg.c

SpfdNodeComputeSpfdFromOnAndOffSet()

Given two functions represented by bdd1 and bdd0, compute its SPFD.

SpfdNodeComputeSpfdFromFanouts()

Compute the SPFD of 'from', as the union of SPFDs of its fanout wires.

SpfdNodeComputeSCCs()

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.

ComputeAuxRel()

Convert faninRel which is interms of Y, to Y', the auxillary variables.

By: Balakrishna Kumthekar

Utility routines for the spfd package.

See AlsospfdAPI.c

SpfdInitializeApplData()

Initialize the application data structure of the package.

SpfdComputeParameters()

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.

SpfdAllocateTemporaryVariables()

Allocate num of BDD variables.

SpfdAllocateOrReuseAuxVariables()

Recyle existing BDD variables or allocate new ones.

SpfdOrderFaninOfRegionNodes()

Fanin nodes of each cluster node is ordered according to the 'compareFunc'. The fanin nodes need to be ordered during SPFD computation.

SpfdSwitchedCapAndDepthCompare()

Compare the convex combination of switched capacitance and topological depth of two nodes.

SpfdFanoutCountAndDepthCompare()

Compare the convex combination of fanout count and the node's topological depth.

SpfdDepthCompare()

Compare the topological depth of two nodes.

SpfdDescendDepthCompare()

Same as SpfdDepthCompare, but the nodes will be sorted in descending order when used by qsort.

SpfdMddCreateVariables()

This procedure calls the mdd_create_variables in order to create new variables.

SpfdAddEqual()

Returns a BDD containing minterms such that the discriminant for those minterms in f is equal to that in g.

SpfdNetworkWriteBlifFile()

Print the network in BLIF format to fileName.

SpfdComputeNodeArrayRelation()

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.

SpfdSwapPiAndAltPi()

Swap the BDD variables of primary inputs and it's auxillary BDD ids.

SpfdNodeReadLocalBdd()

The node's BDD is returned as it is without increasing the reference count.

SpfdFetchInternalPatternArray()

Extract 'percent'% vectors from the patternArray.

SpfdFindNode()

Selects a random node or according to fanout count or switched capacitance.