static int 
CommandDynamicVarOrdering(
  Hrc_Manager_t ** hmgr, 
  int  argc, 
  char ** argv 
)
Implements the dynamic_var_ordering command.

Defined in ordCmd.c 

static int 
CommandPrintBddStats(
  Hrc_Manager_t ** hmgr, 
  int  argc, 
  char ** argv 
)
Implements the print_bdd_stats command.

Defined in ordCmd.c 

static int 
CommandReadOrder(
  Hrc_Manager_t ** hmgr, 
  int  argc, 
  char ** argv 
)
Implements the read_order command.

See Also CommandStaticOrder CommandWriteOrder
Defined in ordCmd.c 

static int 
CommandStaticOrder(
  Hrc_Manager_t ** hmgr, 
  int  argc, 
  char ** argv 
)
Implements the static_order command.

See Also CommandWriteOrder
Defined in ordCmd.c 

static int 
CommandWriteOrder(
  Hrc_Manager_t ** hmgr, 
  int  argc, 
  char ** argv 
)
Implements the write_order command.

Side Effects none

Defined in ordCmd.c 

static char * 
DynOrderTypeConvertToString(
  bdd_reorder_type_t  method 
)
Converts a dynamic ordering method type to a string. This string must NOT be freed by the caller.

Defined in ordCmd.c 

static int 
IntegersCompare(
  char ** obj1, 
  char ** obj2 
)
Used to sort an array of integers in ascending order.

Defined in ordIo.c 

static lsList 
LatchNSListConvertToLatchDataInputList(
  lsList  latchNSList 
)
Converts a list of latch next state nodes to the corresponding list of latch data input nodes.

Defined in ordMain.c 

static int * 
LatchPermutationCompute(
  Proc_Com_Graph * PCG, 
  int  choice, 
  int  verbose 
)
optional

Side Effects required

See Also optional
Defined in ordPerm.c 

static void 
MddGroupVariables(
  mdd_manager * mddMgr, 
  int  initMddId, 
  int  blockSize 
)
Group all bdd vars corresponding to mdd vars initMddId to initMddId + blockSize in a block which will not be reordered internally. Ths bdd's corresponding to these mdd's should be contiguous; if not the function will fail.

Defined in ordMain.c 

static boolean 
NameStringProcess(
  char * nameString, 
  Ntk_Network_t * network, 
  lsList  nodeList, 
  int  verbose 
)
Processes the name of a node. If there is no node in network with name nameString, then the function writes a message in error_string, and returns FALSE. If the corresponding node is found, then the node is added to the end of nodeList; else, nothing is done. In either case, TRUE is returned.

Defined in ordIo.c 

static void 
NetworkAddDanglingNodesToOrderList(
  Ntk_Network_t * network, 
  lsList  nodeOrderList, of Ntk_Node_t*
  st_table * nodeToHandle Ntk_Node_t* to lsHandle
)
Adds to the end of nodeOrderList all network nodes that are not yet present in nodeOrderList. This is used to pick up those (dangling) nodes that weren't in the transitive fanins of the roots in the call to OrdNetworkOrderTFIOfRoots. nodeToHandle is a hash table mapping each node in nodeOrderList to its handle in the list; dangling nodes are inserted into this table.

Side Effects nodeOrderList and nodeToHandle will be modified if dangling nodes exist.

See Also OrdNetworkOrderTFIOfRoots
Defined in ordMain.c 

static void 
NetworkAddNSVarsToOrderList(
  Ntk_Network_t * network, 
  lsList  nodeOrderList, of Ntk_Node_t
  st_table * nodeToHandle, Ntk_Node_t* to lsHandle
  boolean  nsAfterSupport 
)
Adds to nodeOrderList all next state variables. If nsAfterSupport is TRUE, then for a given latch, its NS variable is added in nodeOrderList just after the latch's corresponding dataInput node. If nsAfterSupport is FALSE, then for a given latch, its NS variable is added in nodeOrderList just after the latch (i.e. its present state variable). (If the latch itself is not present yet in the nodeOrderList, then first adds latch to the end of the ordering.)

nodeToHandle is a hash table mapping each node in nodeOrderList to its handle in the list; next state nodes are inserted into this table.

Side Effects nodeOrderList and nodeToHandle will be modified if latches exist.

See Also OrdNetworkOrderTFIOfRoots
Defined in ordMain.c 

static boolean 
NetworkCheckSuppliedNodeList(
  Ntk_Network_t * network, 
  lsList  suppliedNodeList, 
  Ord_OrderType  orderType 
)
Returns TRUE if the set of nodes in suppliedNodeList matches the set of nodes in network specified by orderType; else returns FALSE and writes a message to error_string. OrderType should be one of the following: 1) Ord_All_c: should match the set of all nodes in network; 2) Ord_InputAndLatch_c: should match the set of inputs (primary + pseudo), latches, and next state nodes; 3) Ord_NextStateNode_c: should match the set of next state nodes; number should be the number of latches; 4) Ord_Partial_c: returns TRUE automatically.

Defined in ordCmd.c 

static lsList 
NetworkComputeLatchOrder(
  Ntk_Network_t * network, 
  int  verbose 
)
Computes an ordering on the latches, to be used for variable ordering. Returns a list of the corresponding latch data inputs (Ntk_Node_t *) giving the ordering. Implements the algorithm given in Aziz et al, "BDD Variable Ordering for Interacting FSMs", DAC 1994, p. 283.

Side Effects Creates a file in /tmp.

See Also NetworkOrderNodes
Defined in ordPerm.c 

static OrderingState_t * 
NetworkInitializeOrderingState(
  Ntk_Network_t * network 
)
Allocates and initializes data structure needed to maintain the state of the variable ordering routine.

See Also OrderingStateFree
Defined in ordNodes.c 

static lsList 
NetworkOrderTFIOfRootsByAppending(
  Ntk_Network_t * network, 
  lsList  roots, list of Ntk_Node_t
  st_table * nodeToHandle, modified
  int  verbose 
)
Orders the nodes of a network by the appending method. The parameters are the same as in OrdNetworkOrderTFIOfRoots.

This function implements the algorithm of Malik, et al. "Logic Verification using Binary Decision Diagrams in a Logic Synthesis Environment," ICCAD, 1988. The ordering returned is a topological ordering. The algorithm works as follows. For every root, a topological ordering on the tfi nodes not yet ordered is generated by DFS. The ordered obtained starting from a root is appended to the order already found.

Side Effects nodeToHandle table is modified

See Also OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByAppending
Defined in ordNodes.c 

static lsList 
NetworkOrderTFIOfRootsByInterleaving(
  Ntk_Network_t * network, 
  lsList  roots, list of Ntk_Node_t
  st_table * nodeToHandle, modified
  int  verbose 
)
Orders the nodes of a network by the interleaving method. The parameters are the same as in OrdNetworkOrderTFIOfRoots.

This function implements Algorithm 2 of Fujii, et al. "Inteleaving Based Variable Ordering Methods for Ordered Binary Decision Diagrams," ICCAD, 1993. The ordering returned is a topological ordering. The algorithm is a modified DFS that keeps track of an insertion point so that variables in the tfi of the second and successive outputs be properly interleaved with the variables already ordered.

Side Effects nodeToHandle table is modified

See Also OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByInterleaving
Defined in ordNodes.c 

static lsList 
NetworkOrderTFIOfRootsByMerging(
  Ntk_Network_t * network, 
  lsList  roots, list of Ntk_Node_t
  Ord_ListMergeMethod  method, 
  st_table * nodeToHandle, modified
  int  verbose 
)
Orders the nodes of a network by the merging method. The parameters are the same as in OrdNetworkOrderTFIOfRoots.

This function implements an algorithm alluded to in Section 3.2 of Fujii et al., "Interleaving Based Variable Ordering Methods for OBDDs", ICCAD 1993, p. 38. The ordering returned is a topological ordering. The algorithm works as follows. For every node, a topological ordering on the tfi nodes is created and stored at the node. This is done recursively. For leaves of the recursion, a trivial list of length 1 is created. For the general case, the order lists at the fanins are merged together, and then the node itself is appended to the end of the list. The merging is done from the highest priority fanin to the lowest priority, where a "merge right" or "merge right" is performed, depending on the value of method. Nodes with greater depth have higher priority.

TODO: This function is consuming more memory than is necessary. Specifically, a node list is computed and stored at each network node. Currently, this list is not freed until the very end of the node ordering computation. Instead, a reference count could be precomputed for each node, and when this falls to zero, the list can be immediately freed.

Side Effects nodeToHandle table is modified

See Also OrdNetworkOrderTFIOfRoots NodeOrderRecursivelyByMerging OrdNetworkComputeNodeDepths
Defined in ordNodes.c 

static array_t * 
NodeBuildBddIdArrayFromNtkNode(
  Ntk_Node_t * node 
)
Returns an array (of int's) of the indices of the BDD variables corresponding to the MDD variable of a node. It is the responsibility of the caller to free this array.

Defined in ordIo.c 

static array_t * 
NodeBuildBddLevelArrayFromNtkNode(
  Ntk_Node_t * node 
)
Returns an array (of int's) of the levels of the BDD variables corresponding to the MDD variable of a node. The level of a BDD variable is it place in the current variable ordering of the BDD manager. The returned array is sorted in ascending order. It is the responsibility of the caller to free this array.

Defined in ordIo.c 

static long 
NodeComputeDepth(
  Ntk_Node_t * node 
)
Computes the depth of a node.

See Also OrdNetworkComputeNodeDepths
Defined in ordMain.c 

static void 
NodeOrderRecursivelyByAppending(
  Ntk_Node_t * node, 
  lsList  orderList, 
  st_table * nodeToHandle, 
  int  verbose 
)
Orders the fanins of a node, and then orders the node itself. The fanins of a node are visited in order of decreasing depth. The node appears in the order just after its fanins, yielding a topological order. If node has already been visited, then simply return the order previously found.

Side Effects nodeToHandle table is modified

See Also NetworkOrderTFIOfRootsByAppending OrdNetworkComputeNodeDepths
Defined in ordNodes.c 

static void 
NodeOrderRecursivelyByInterleaving(
  Ntk_Node_t * node, 
  lsList  orderList, 
  st_table * nodeToHandle, 
  OrderingState_t * orderingState, 
  int  verbose 
)
Orders the fanins of a node, and then orders the node itself. The fanins of a node are visited in order of decreasing depth. The node appears in the order just after its fanins, yielding a topological order. If node has already been visited, then simply update the info on the output from which it was last reached, and change the insertion point.

Side Effects nodeToHandle table is modified

See Also NetworkOrderTFIOfRootsByAppending OrdNetworkComputeNodeDepths
Defined in ordNodes.c 

static lsList 
NodeOrderRecursivelyByMerging(
  Ntk_Node_t * node, 
  OrderingState_t * orderingState, 
  Ord_ListMergeMethod  method, 
  int  verbose 
)
Orders the fanins of a node, and then orders the node itself. The fanins of a node are visited in order of decreasing depth, and their orderings are merged. The node appears in the order just after its fanins, yielding a topological order. If node has already been visited, then simply return the order previously found.

See Also OrdNetworkComputeNodeDepths NetworkOrderTFIOfRootsByMerging
Defined in ordNodes.c 

static array_t * 
NodeReadBddLevelArray(
  Ntk_Node_t * node 
)
Gets the BDD level array of a node.

See Also NodeSetBddLevelArray NodesCompareBddLevelArray
Defined in ordIo.c 

static Ntk_Node_t * 
NodeReadFrom(
  Ntk_Node_t * node, 
  OrderingState_t * orderingState 
)
Gets the from node of a node. This is the root from which the node was last reached during DFS. Returns NULL if node is not in the from hash table of orderingState.

Side Effects none

See Also NodeSetFrom
Defined in ordNodes.c 

static lsList 
NodeReadOrderList(
  Ntk_Node_t * node, 
  OrderingState_t * orderingState 
)
Gets the order list of a node. This is a topological ordering of all the nodes in the transitive fanin of the node. Returns NULL if node is not in the nodeToOrderList hash table of orderingState.

See Also NodeSetOrderList
Defined in ordNodes.c 

static void 
NodeSetBddLevelArray(
  Ntk_Node_t * node, 
  array_t * bddLevelArray 
)
Sets the BDD level array of a node.

See Also NodeReadBddLevelArray
Defined in ordIo.c 

static void 
NodeSetDepth(
  Ntk_Node_t * node, 
  long  depth 
)
Sets the depth of a node.

See Also OrdNodeReadDepth
Defined in ordMain.c 

static void 
NodeSetFrom(
  Ntk_Node_t * node, 
  OrderingState_t * orderingState 
)
Sets the from root of a node to the current root.

Side Effects The from table of orderingState is modified.

See Also NodeReadFrom
Defined in ordNodes.c 

static void 
NodeSetOrderList(
  Ntk_Node_t * node, 
  lsList  orderList, 
  OrderingState_t * orderingState 
)
Sets the orderList of a node.

See Also NodeReadOrderList
Defined in ordNodes.c 

static int 
NodesCompareBddLevelArray(
  lsGeneric  node1, 
  lsGeneric  node2 
)
Used to sort an array of nodes in ascending order of lowest BDD level.

Defined in ordIo.c 

static int 
NodesCompareDepth(
  Ntk_Node_t * node1, 
  Ntk_Node_t * node2 
)
Compares depths of node1 and node2 for sorting; greater depth node should appear before a lower depth node. Ties are broken based on the node names; it's an error if the two nodes have the same name.

Defined in ordMain.c 

int 
OrdMakeNewVariableOrder(
  mdd_manager * mddMgr, 
  lsList  suppliedNodeList, 
  int  group, 
  int  verbose 
)
Makes new variable order. Returns 1 if not successful.

Defined in ordIo.c 

void 
OrdNetworkAssignMddIds(
  Ntk_Network_t * network, 
  Ord_OrderType  orderType, 
  lsList  orderList, 
  boolean  nsAfterSupport 
)
Assigns consecutive MDD ids to nodes in orderList. Ids are assigned starting from the number of variables in the MDD manager of network. (An MDD manager is created for the network if the network doesn't already have one.) OrderType can be Ord_All_c or Ord_InputAndLatch_c. If orderType is Ord_All_c, then all nodes in orderList are assigned an id. If orderType is Ord_InputAndLatch_c only primary inputs, pseudo input, latches, and latch NSs are assigned ids. Presently, nsAfterSupport is unused.

See Also OrdNetworkOrderTFIOfRoots Ntk_NetworkInitializeMddManager
Defined in ordMain.c 

void 
OrdNetworkComputeNodeDepths(
  Ntk_Network_t * network, 
  lsList  roots list of Ntk_Node_t
)
Computes the depth of each node in the transitive fanin of the list of roots. The depth of a node is defined inductively: latches, and nodes with no inputs, have depth 0. Otherwise, the depth of a node is 1 more than the maximum depth over the node's fanins. Intuitively, the depth of a node is the length of the longest (backward) path from the node to a latch, primary input, pseudo input, or constant.

Side Effects Uses undef field of Ntk_Node_t.

See Also Ord_NetworkOrderVariables
Defined in ordMain.c 

lsList 
OrdNetworkOrderRootsByDepth(
  Ntk_Network_t * network, 
  boolean  verbose 
)
Computes a total ordering on the combinational outputs of a network. First, the depth of each combinational output is calculated. The depth of a node is the longest path (going backwards) to a combinational input or constant. Then, the algorithm creates two lists: 1) data inputs to latches, and 2) all remaining combinational outputs. Next, each list is sorted in order of decreasing depth. Finally, the second list is appended to the first.

See Also Ord_NetworkOrderRoots OrdNetworkComputeNodeDepths
Defined in ordRoots.c 

lsList 
OrdNetworkOrderRootsByPerm(
  Ntk_Network_t * network, 
  int  verbose 
)
Computes a total ordering on the combinational outputs of a network. First, the algorithm orders the data inputs using the permutation algorithm (Aziz et al, "BDD Variable Ordering for Interacting FSMs", DAC 1994, p. 283). Then, it orders the remaining combinational outputs in order of decreasing depth. Finally, the second list is appended to the first.

See Also OrdNetworkComputeNodeDepths
Defined in ordPerm.c 

lsList 
OrdNetworkOrderTFIOfRoots(
  Ntk_Network_t * network, 
  lsList  roots, of Ntk_Node_t
  Ord_NodeMethod  nodeOrderMethod, 
  st_table * nodeToHandle, modified
  int  verbose 
)
Orders the nodes of a network that are in the transitive fanin of the list of roots, including the roots themselves. The roots are visited in the order given in the root list. Combinational inputs (primary inputs, pseudo inputs, and latches) and constants terminate the recursion. If you want a latch next state function to be a root, then the corresponding data input should be in the root list, not the latch itself. Note that next state variables are not included in the ordering; these should be added as a post-processing step.

The different node ordering methods are documented in the static_order command. If nodeMethod is Ord_NodesByDefault_c, then one of the ordering methods is called by default.

nodeToHandle should be an empty table created using st_init_table(st_ptrcmp, st_ptrhash). For every node in the returned list, there is an entry in nodeToHandle mapping the node to the node's handle in the returned list.

Side Effects nodeToHandle table is modified

See Also Ord_NetworkOrderRoots
Defined in ordNodes.c 

void 
OrdNodeAddToList(
  lsList  nodeList, 
  st_table * nodeTable, 
  Ntk_Node_t * node 
)
Inserts a node into a list, unless it already appears in the list.

Defined in ordRoots.c 

void 
OrdNodeListWrite(
  FILE * fp, 
  lsList  nodeList 
)
Prints the names of a list of nodes, one per line.

Defined in ordMain.c 

long 
OrdNodeReadDepth(
  Ntk_Node_t * node 
)
Reads the depth of a node.

See Also NodeSetDepth OrdNodesFromArrayCompareDepth OrdNodesFromListCompareDepth
Defined in ordMain.c 

int 
OrdNodesFromArrayCompareDepth(
  char ** node1, 
  char ** node2 
)
Compares the depth of two nodes in an array_t. Greater depth node should appear before a lower depth node.

Defined in ordMain.c 

int 
OrdNodesFromListCompareDepth(
  lsGeneric  node1, 
  lsGeneric  node2 
)
Compares the depth of two nodes in an lsList. Greater depth node should appear before a lower depth node.

Defined in ordMain.c 

void 
Ord_End(
    
)
Ends the order package.

See Also Ord_Init
Defined in ordCmd.c 

boolean 
Ord_FileReadNodeList(
  FILE * fp, 
  Ntk_Network_t * network, 
  lsList * nodeList, of Ntk_Node_t , for return
  int  verbose 
)
Parses a file and builds a node list corresponding to the names found in the first "column" of each line of the file. Any line starting with the comment character '#' or white space is ignored. If a name is found for which there doesn't exist a corresponding node in network, then a message is written to error_string, the partial node list is freed, and the function returns FALSE; otherwise, it returns TRUE, and a pointer to a list is returned.

Defined in ordIo.c 

void 
Ord_Init(
    
)
Initializes the order package.

See Also Ord_End
Defined in ordCmd.c 

void 
Ord_ListAppendList(
  lsList  list1, 
  lsList  list2 
)
Appends list2 into list1. List1 is modified; list2 is not changed.

Side Effects list1 is modified

Defined in ordMain.c 

void 
Ord_ListMergeLeftListUsingTable(
  lsList  list1, 
  lsList  list2, 
  st_table * dataToHandle1 
)
Merges left list2 into list1, using the provided table for efficiency. dataToHandle1 is a hash table mapping each item in list1 to its handle in list1.

This function implements the merge described in Algorithm 1 by Fujii et al., "Interleaving Based Variable Ordering Methods for OBDDs", ICCAD 1993, p. 38. For each item in list2: if item is already present in list1, do nothing; else if item is the head of list2, then insert item at the head of list1; else, insert item into list1 immediately following the location in list1 of the item's predessor item in list2. This has the effect of locating the items in list2 as far to the left as possible in list1, while still preserving the partial order for those elements of list2 not initially appearing in list1 (a "merge left"). Examples: 

  list1=abc, list2=dbe --> list1=dabec
  list1=abc, list2=deb --> list1=deabc.
Note that this merging is not commutative. That is, Ord_ListMergeLeftList(l1,l2) may give a different ordering than Ord_ListMergeLeftList(l2,l1).

Side Effects List1 is modified, and dataToHandle1 is modified to reflect the newly inserted items.

See Also Ord_ListMergeRightListUsingTable
Defined in ordMain.c 

void 
Ord_ListMergeListUsingTable(
  lsList  list1, 
  lsList  list2, 
  st_table * dataToHandle1, 
  Ord_ListMergeMethod  method 
)
Merges list2 into list1, using the provided table for efficiency. Calls Ord_ListMergeLeftListUsingTable or Ord_ListMergeRightListUsingTable depending on the value of method.

Side Effects list1 is modified

See Also Ord_ListMergeLeftListUsingTable Ord_ListMergeRightListUsingTable
Defined in ordMain.c 

void 
Ord_ListMergeList(
  lsList  list1, 
  lsList  list2, 
  Ord_ListMergeMethod  method 
)
Merges list2 into list1. Creates a hash table mapping the items of list1 to their handles in list1, and then calls Ord_ListMergeListUsingTable.

Side Effects list1 is modified

See Also Ord_ListMergeListUsingTable
Defined in ordMain.c 

void 
Ord_ListMergeRightListUsingTable(
  lsList  list1, 
  lsList  list2, 
  st_table * dataToHandle1 
)
Merges right list2 into list1, using the provided table for efficiency. This function is the same as Ord_ListMergeLeftListUsingTable, except that a "merge right" is done, rather than a "merge left". For each item in list2: if item is already present in list1, do nothing; else if item is the tail of list2, then insert item at the tail of list1; else, insert item into list1 immediately preceeding the location in list1 of the item's successor item in list2. This has the effect of locating the items in list2 as far to the right as possible in list1, while still preserving the partial order for those elements of list2 not initially appearing in list1 (a "merge right"). Examples: 
  list1=abc, list2=dbe --> list1=adbce
  list1=abc, list2=deb --> list1=adebc.

Side Effects List1 is modified, and dataToHandle1 is modified to reflect the newly inserted items.

See Also Ord_ListMergeLeftListUsingTable
Defined in ordMain.c 

void 
Ord_NetworkAssignMddIdForNode(
  Ntk_Network_t * network, 
  Ntk_Node_t * node 
)
Assigns an mddId to a node. If the node already has a valid mddId (i.e. it is not NTK_UNASSIGNED_MDD_ID), then nothing is done. Otherwise, the node is assigned an mddId, and this Id is created within the MDD manager of the network. (An MDD manager is created for the network if the network doesn't already have one.)

Defined in ordMain.c 

char ** 
Ord_NetworkGetCombInputNamesInOrder(
  Ntk_Network_t * network 
)
Returns a name array of combinational input variables in order.

Defined in ordIo.c 

lsList 
Ord_NetworkOrderNodes(
  Ntk_Network_t * network, 
  Ord_RootMethod  rootOrderMethod, 
  Ord_NodeMethod  nodeOrderMethod, 
  boolean  nsAfterSupport, 
  Ord_OrderType  generatedOrderType, Ord_All_c or Ord_InputAndLatch_c
  Ord_OrderType  suppliedOrderType, Ord_NextStateNode_c, Ord_Partial_c, or
Ord_Unassigned_c
  lsList  suppliedNodeList, list of nodes Ntk_Node_t* from ordering file
  int  verbose 
)
Orders the nodes of a network. The ordering is based solely on the topology of the network, and is intended to be suitable for deriving an MDD variable ordering by extracting those nodes for which MDD variables are needed. GeneratedOrderType can be either Ord_All_c or Ord_InputAndLatch_c. If it is Ord_All_c, then every node (and latch NS) in the network is ordered. If it is Ord_InputAndLatch_c, then every primary input, pseudo input, latch, and latch NS is ordered.

SuppliedOrderType can be any of the following values: Ord_NextStateNode_c, Ord_Partial_c, or Ord_Unassigned_c. If it is Ord_Unassigned_c, then suppliedNodeList is ignored, and there is no effect. If it is *not* Ord_Unassigned_c, then suppliedNodeList must be a non-empty list of (pointers to) nodes. SuppliedNodeList can be used to specify the relative order of some or the nodes.

If suppliedOrderType is Ord_NextStateNode_c, then suppliedNodeList should contain a complete list of next state nodes; the transitive fanins of the latches are visited according to the order of the next state nodes in suppliedNodeList. If suppliedOrderType is Ord_Partial_c, then suppliedNodeList may contain an arbitrary subset of network nodes; in this case, an ordering is found disregarding suppliedNodeList, and then this ordering is merged into the suppliedNodeList. No checks are made to insure that suppliedNodeList contains what is implied by the value of suppliedOrderType.

If nsAfterSupport is TRUE, then for a given latch, its next state variable is ordered just after the latch's corresponding dataInput node. If nsAfterSupport is FALSE, then for a given latch, its next state variable is ordered just after the latch (i.e. its present state variable). (If the latch itself is not present yet in the nodeOrderList, then first adds latch to the end of the ordering.)

See Also Ord_NetworkOrderVariables
Defined in ordMain.c 

lsList 
Ord_NetworkOrderRoots(
  Ntk_Network_t * network, 
  Ord_RootMethod  rootMethod, 
  lsList  partialOrder, 
  boolean  verbose 
)
Orders the combinational outputs of a network. The data inputs of latches always precede the other combinational outputs. This gives priority to finding the best ordering for the variables in the next state functions.

The different root ordering methods are documented in the static_order command. If rootMethod is Ord_RootsByDefault_c, then one of the ordering methods is called by default, depending on the number of latches in the network.

An arbitrary subset of roots can be specified in partialOrder. No check is made to determine if the nodes in partialOrder are contained within the set specified by orderType. If partialOrder is non-NULL, then a total order on the roots is computed according to rootMethod (as described above), and then the computed order is merged into the partialOrder.

See Also OrdNetworkOrderRootsByDepth OrdNetworkOrderRootsByPerm
Defined in ordRoots.c 

void 
Ord_NetworkOrderVariables(
  Ntk_Network_t * network, 
  Ord_RootMethod  rootOrderMethod, 
  Ord_NodeMethod  nodeOrderMethod, 
  boolean  nsAfterSupport, 
  Ord_OrderType  generatedOrderType, Ord_All_c or Ord_InputAndLatch_c
  Ord_OrderType  suppliedOrderType, no restrictions
  lsList  suppliedNodeList, list of nodes Ntk_Node_t* from ordering file
  int  verbose 
)
Orders the MDD variables of a network. The ordering is based solely on the topology of the network; the binary variables that make up the MDD variables are not interleaved. OutputOrderType can be either Ord_All_c or Ord_InputAndLatch_c. If it is Ord_All_c, then every node (and latch NS) in the network is assigned an MDD id. If it is Ord_InputAndLatch_c, then every primary input, pseudo input, latch, and latch NS is assigned an MDD id.

SuppliedOrderType can be any value of Ord_OrderType. If it is Ord_All_c or Ord_InputAndLatch_c, then suppliedNodeList must give an ordering of the network nodes (included in the set specified by suppliedOrderType). Otherwise, Ord_NetworkOrderNodes is called, with the same arguments as this function, to compute an ordering of the network nodes. In any case, the ordering of nodes is projected onto the set specified by generatedOrderType, and MDD ids are assigned (in order) to the nodes in the projection. The starting MDD id is the total number of variables currently in the MDD manager of the network. An MDD manager is created for the network if one doesn't already exist.

No checks are made to insure that suppliedNodeList contains what is implied by the value of suppliedOrderType. The MDD ids of nodes not specified by generatedOrderType are unaffected.

If nsAfterSupport is TRUE, then for a given latch, its next state variable is ordered just after the variables in the support of the latch's corresponding dataInput function.

If nsAfterSupport is FALSE, then for a given latch, its NS variable is ordered just after the corresponding present state variable. In this case, the ps variable and the ns variable are grouped together in the variable ordering, so that when reordering is performed they remain adjacent in the new variable ordering. Similarly, when an ordering is read from a file, NS variables immediately following corresponding PS variables are grouped together.

Side Effects Writes over the MDD id field of nodes.

See Also Ord_NetworkOrderNodes
Defined in ordMain.c 

int 
Ord_NetworkPrintVariableOrder(
  FILE * fp, 
  Ntk_Network_t * network, 
  Ord_OrderType  orderType Ord_All_c, Ord_InputAndLatch_c or Ord_NextStateNode_c
)
Prints to a file all the nodes specified by orderType. OrderType can be one of Ord_All_c, Ord_InputAndLatch_c or Ord_NextStateNode_c (see ord.h for the meaning of these types). For each node, prints the following: name, node type, MDD id, number of values in the range of the node output, and a list of the levels (in the current ordering) of the BDD variables that constitute this multi-valued variable. The nodes are printed to the file in ascending order of the lowest level corresponding BDD variable. If there exists a node in the class specified by orderType that doesn't have an mddId, then the routine writes a message to error_string, and returns 0. In all other cases, it writes to the file and then returns 1. It is the responsibility of the user to close the file.

Defined in ordIo.c 

boolean 
Ord_NetworkTestAreVariablesOrdered(
  Ntk_Network_t * network, 
  Ord_OrderType  orderType 
)
For each node of network that falls in the class given by orderType, checks that the node has an MDD id. If all such nodes have MDD ids, return 1, else returns 0. orderType can have one of 3 values: Ord_All_c, checks all nodes of network; Ord_InputAndLatch_c, checks all combinational inputs and latch next states; Ord_NextStateNode_c, checks all next state nodes. Returns 0 on the first such node not having an MDD id, and writes an error message in error_string. Also returns 0 if the network doesn't have an MDD manager.

Defined in ordCmd.c 

static void 
OrderingStateFree(
  OrderingState_t * orderingState 
)
Frees all memory associated with an ordering state.

See Also NetworkInitializeOrderingState
Defined in ordNodes.c 

static void 
OrderingStateSetLast(
  Ntk_Node_t * node, 
  st_table * nodeToHandle, 
  OrderingState_t * orderingState 
)
Updates the insertion point in orderingState. Assumes that node is already in nodeToHandle.

See Also NetworkInitializeOrderingState
Defined in ordNodes.c 

static bdd_reorder_type_t 
StringConvertToDynOrderType(
  char * string 
)
Converts a string to a dynamic ordering method type. If string is not "sift" or "window", then returns BDD_REORDER_NONE.

Defined in ordCmd.c 

static Ord_OrderType 
StringConvertToOrderType(
  char * string 
)
Converts a string to an order type. If string does not refer to one of the allowed order types, then returns Ord_Unassigned_c.

Defined in ordCmd.c 

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

Defined in ordCmd.c 

static void 
append_best_2(
  int * opt_perm, 
  int  loc, 
  Proc_Com_Graph * PCG 
)
optional

Side Effects required

See Also optional
Defined in ordPerm.c 

static void 
append_best(
  int * opt_perm, 
  int  loc, 
  Proc_Com_Graph * PCG 
)
Adds the next best element in the greedy sense as described for init_heur below.

Side Effects required

See Also optional
Defined in ordPerm.c 

static void 
append_touati_2(
  int * opt_perm, 
  int  loc, 
  Proc_Com_Graph * PCG 
)
optional

Side Effects required

See Also optional
Defined in ordPerm.c 

static double 
cost_2(
  int * opt_perm, 
  int  loc, 
  Proc_Com_Graph * PCG 
)
optional

Side Effects required

See Also optional
Defined in ordPerm.c 

static double 
cost_for_cut(
  Proc_Com_Graph * PCG, 
  int * perm, 
  int  end_of_set1 
)
Calculates the cost for a single cut that divides the permutation into 2.

Side Effects required

See Also optional
Defined in ordPerm.c 

static double 
cost_total(
  Proc_Com_Graph * PCG, 
  int * perm 
)
optional

Side Effects required

See Also optional
Defined in ordPerm.c 

static long int 
cost_touati_2(
  int * opt_perm, 
  int  loc, 
  Proc_Com_Graph * PCG 
)
optional

Side Effects required

See Also optional
Defined in ordPerm.c 

static void 
heur_2(
  Proc_Com_Graph * PCG, 
  int * opt_perm 
)
optional

Side Effects required

See Also optional
Defined in ordPerm.c 

static void 
heur_touati_la2(
  Proc_Com_Graph * PCG, 
  int * opt_perm 
)
optional

Side Effects required

See Also optional
Defined in ordPerm.c 

static void 
init_heur(
  Proc_Com_Graph * PCG, 
  int * opt_perm 
)
Returns an initial guess for the optimum permutation by forming it one element at a time at each step choosing the element that minimizes cost_for_cut for the set obtained by adding it to the first part of the permutation, writes the permutation to opt_perm.

Side Effects required

See Also optional
Defined in ordPerm.c 

static int * 
opt_proc_order(
  Proc_Com_Graph * PCG 
)
Returns the ordering of processes that minimizes the bound.

Side Effects required

See Also optional
Defined in ordPerm.c 

static int * 
opt_touati_order(
  Proc_Com_Graph * PCG 
)
Returns the ordering of processes that minimizes the bound.

Side Effects required

See Also optional
Defined in ordPerm.c 

static int * 
random_permutation(
  int  seed, 
  int  n_elts 
)
optional

Side Effects required

See Also optional
Defined in ordPerm.c 

static double 
rev_fac(
  int  num_rev_bits 
)
optional

Side Effects required

See Also optional
Defined in ordPerm.c 

static void 
swap(
  int * opt_perm, 
  int  i, 
  int  j 
)
optional

Side Effects required

See Also optional
Defined in ordPerm.c
Last updated on 20010517 18h00
Contact 
©2002-2018 U.C. Regents