edu.byu.ece.edif.tools.replicate.nmr
Class NMRGraphUtilities

java.lang.Object
  extended by edu.byu.ece.edif.tools.replicate.nmr.NMRGraphUtilities

public class NMRGraphUtilities
extends java.lang.Object

A set of utilities to work with strongly connected components (SCCs), including methods to break apart large SCCs into smaller, more manageable units. Triplication of SCCs for a given list of EdifEdges is also performed by this class.

Author:
Michael Wirthlin, Brian Pratt, Keith Morgan
See Also:
SCCDepthFirstSearch

Field Summary
protected static boolean DEBUG
           
static int DEFAULT_SCC_SORT_TYPE
           
 
Constructor Summary
NMRGraphUtilities()
           
 
Method Summary
private static void _decomposeSCC(AbstractEdifGraph graph, java.util.List sccList, java.util.List singleNodeSCCs, BasicDepthFirstSearchTree scc)
          Internal helper method for tmrSCCsUsingSCCDecomposition method.
static int computeFanin(java.lang.Object node, AbstractEdifGraph graph, int levels)
           
static java.util.Collection<EdifPortRef> createAfterFFsCutset(AbstractEdifGraph graph, NMRArchitecture nmrArch)
           
static java.util.List<Edge> createBasicDecompositionCutset(AbstractEdifGraph graph, SCCDepthFirstSearch sccs, NMRArchitecture arch)
           
static java.util.Collection<EdifPortRef> createBeforeFFsCutset(AbstractEdifGraph graph, NMRArchitecture nmrArch)
           
static java.util.Collection<Edge> createDecomposeValidCutSet(AbstractEdifGraph graph, BasicDepthFirstSearchTree scc, NMRArchitecture arch)
          Create a valid set of cuts which break all feedback in the given SCC.
static java.util.Collection<EdifPortRef> createDecomposeValidCutSetFanout(AbstractEdifGraph graph, SCCDepthFirstSearch sccs, NMRArchitecture arch)
          Create a valid set of cuts which break all feedback in the given SCC.
static java.util.Collection<EdifPortRef> createDecomposeValidCutSetFFFanout(AbstractEdifGraph graph, SCCDepthFirstSearch sccs, NMRArchitecture arch)
          Performs a cut by choosing outputs of Flip-flops first.
static java.util.Collection<EdifPortRef> createHighestFFFaninCutset(AbstractEdifGraph graph, SCCDepthFirstSearch sccs, NMRArchitecture arch)
          The highest fanin flip-flop is the flip-flop with the most nets leading into the D input going five levels of instances backwards.
static java.util.Collection<EdifPortRef> createHighestFFFaninOutputCutset(AbstractEdifGraph graph, SCCDepthFirstSearch sccs, NMRArchitecture arch)
          The highest fanin flip-flop is the flip-flop with the most nets leading into the D input going five levels of instances backwards.
static java.util.Collection createValidCutSet(DirectedGraph graph, BasicDepthFirstSearchTree tree, NMRArchitecture arch)
          Deprecated. This method does NOT examine all cutset possibilities; use createDecomposeValidCutSet(AbstractEdifGraph, BasicDepthFirstSearchTree, NMRArchitecture) instead.
static SCCDepthFirstSearch decomposeSCC(AbstractEdifGraph graph, BasicDepthFirstSearchTree sccTree)
          Given a Strongly-Connected Component (SCC), identify a set of edges in the graph that, when cut, will "break" or decompose the SCC into one or more trees, each of which is not an SCC.
static java.util.Collection<Edge> findBadEdges(java.util.Collection<Edge> edges, NMRArchitecture arch)
          Finds and returns any "bad" edges in the collection of edges.
protected static java.util.Collection<EdifPortRefEdge> getBadEdges(java.util.Collection<EdifPortRefEdge> edges, NMRArchitecture arch)
           
static boolean hasBadEdge(java.util.Collection edges, NMRArchitecture arch)
          Determines whether there are any "bad" edges in the collection of edges.
static boolean isSCC(DirectedGraph graph)
          Checks whether the given graph is a strongly-connected component or not.
static void main(java.lang.String[] args)
           
static boolean nmrSCCsUsingSCCDecomposition(SCCDepthFirstSearch sccDFS, NMRArchitecture arch, ReplicationUtilizationTracker capacity, boolean allowSCCDecomposition, int sortType, ReplicationType replicationType, boolean override)
          Determines how many SCCs can be triplicated using the given capacity object.
static java.util.Collection smallestCutSet(DirectedGraph graph, BasicDepthFirstSearchTree tree, NMRArchitecture arch)
           
static java.util.Collection validCutSet(DirectedGraph graph, BasicDepthFirstSearchTree tree, NMRArchitecture arch)
          Identify a valid set of edges that completely removes feedback in the given DFSTree.
static java.util.Collection validCutSet(SCCDepthFirstSearch sccs, NMRArchitecture arch)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEFAULT_SCC_SORT_TYPE

public static final int DEFAULT_SCC_SORT_TYPE
See Also:
Constant Field Values

DEBUG

protected static boolean DEBUG
Constructor Detail

NMRGraphUtilities

public NMRGraphUtilities()
Method Detail

main

public static void main(java.lang.String[] args)

createBasicDecompositionCutset

public static java.util.List<Edge> createBasicDecompositionCutset(AbstractEdifGraph graph,
                                                                  SCCDepthFirstSearch sccs,
                                                                  NMRArchitecture arch)

createAfterFFsCutset

public static java.util.Collection<EdifPortRef> createAfterFFsCutset(AbstractEdifGraph graph,
                                                                     NMRArchitecture nmrArch)

createBeforeFFsCutset

public static java.util.Collection<EdifPortRef> createBeforeFFsCutset(AbstractEdifGraph graph,
                                                                      NMRArchitecture nmrArch)

createDecomposeValidCutSet

public static java.util.Collection<Edge> createDecomposeValidCutSet(AbstractEdifGraph graph,
                                                                    BasicDepthFirstSearchTree scc,
                                                                    NMRArchitecture arch)
Create a valid set of cuts which break all feedback in the given SCC. This method breaks up the SCC little by little instead of generating the entire cutset at once. Thus, cuts are determined in sets, breaking the problem up when a full cutset is not immediately found.

Parameters:
graph - The top-level graph
scc - A BasicDepthFirstSearchTree object representing an SCC in the top-level graph
arch - The TMRArchitecture, needed to determine good/bad cuts
Returns:
A Collection of EdifEdges making up a valid set of cuts to break all feedback in the given SCC

createHighestFFFaninCutset

public static java.util.Collection<EdifPortRef> createHighestFFFaninCutset(AbstractEdifGraph graph,
                                                                           SCCDepthFirstSearch sccs,
                                                                           NMRArchitecture arch)
The highest fanin flip-flop is the flip-flop with the most nets leading into the D input going five levels of instances backwards.

Parameters:
graph -
sccs -
arch -
Returns:

createHighestFFFaninOutputCutset

public static java.util.Collection<EdifPortRef> createHighestFFFaninOutputCutset(AbstractEdifGraph graph,
                                                                                 SCCDepthFirstSearch sccs,
                                                                                 NMRArchitecture arch)
The highest fanin flip-flop is the flip-flop with the most nets leading into the D input going five levels of instances backwards.

Parameters:
graph -
sccs -
arch -
Returns:

computeFanin

public static int computeFanin(java.lang.Object node,
                               AbstractEdifGraph graph,
                               int levels)

createDecomposeValidCutSetFanout

public static java.util.Collection<EdifPortRef> createDecomposeValidCutSetFanout(AbstractEdifGraph graph,
                                                                                 SCCDepthFirstSearch sccs,
                                                                                 NMRArchitecture arch)
Create a valid set of cuts which break all feedback in the given SCC. This method breaks up the SCC little by little instead of generating the entire cutset at once. Thus, cuts are determined in sets, breaking the problem up when a full cutset is not immediately found. This algorithm will cut the edges with the highest fanout first.

Parameters:
graph - The top-level graph
scc - A BasicDepthFirstSearchTree object representing an SCC in the top-level graph
arch - The TMRArchitecture, needed to determine good/bad cuts
Returns:
A Collection of EdifEdges making up a valid set of cuts to break all feedback in the given SCC

createDecomposeValidCutSetFFFanout

public static java.util.Collection<EdifPortRef> createDecomposeValidCutSetFFFanout(AbstractEdifGraph graph,
                                                                                   SCCDepthFirstSearch sccs,
                                                                                   NMRArchitecture arch)
Performs a cut by choosing outputs of Flip-flops first.


getBadEdges

protected static java.util.Collection<EdifPortRefEdge> getBadEdges(java.util.Collection<EdifPortRefEdge> edges,
                                                                   NMRArchitecture arch)

createValidCutSet

@Deprecated
public static java.util.Collection createValidCutSet(DirectedGraph graph,
                                                                BasicDepthFirstSearchTree tree,
                                                                NMRArchitecture arch)
Deprecated. This method does NOT examine all cutset possibilities; use createDecomposeValidCutSet(AbstractEdifGraph, BasicDepthFirstSearchTree, NMRArchitecture) instead.

Create a valid cut set from scratch. Assuming that there is a valid cut set then there exists a depth-first search tree in which all back edges are not tagged as "bad". There are N different depth search trees for an SCC where N is the number of nodes in the tree. Each different tree is created by using a different node as the "start" node.


decomposeSCC

public static SCCDepthFirstSearch decomposeSCC(AbstractEdifGraph graph,
                                               BasicDepthFirstSearchTree sccTree)
Given a Strongly-Connected Component (SCC), identify a set of edges in the graph that, when cut, will "break" or decompose the SCC into one or more trees, each of which is not an SCC.

Parameters:
graph - The given SCC
sccTree - A valid topological order of the SCC
Returns:
An SCCDepthFirstSearch of the resulting AbstractEdifGraph. Why does this method require the entire graph? Why isn't the sccTree enough? -James C.

findBadEdges

public static java.util.Collection<Edge> findBadEdges(java.util.Collection<Edge> edges,
                                                      NMRArchitecture arch)
Finds and returns any "bad" edges in the collection of edges. Uses the TMRArchitecture for determining a bad cut edge.

Parameters:
edges -
arch -
Returns:
A Collection of "bad" Edge objects in the given Collection Edge objects.

hasBadEdge

public static boolean hasBadEdge(java.util.Collection edges,
                                 NMRArchitecture arch)
Determines whether there are any "bad" edges in the collection of edges. Uses the TMRArchitecture for determining a bad cut.

Parameters:
edges -
arch -
Returns:

isSCC

public static boolean isSCC(DirectedGraph graph)
Checks whether the given graph is a strongly-connected component or not. Warning: This method is terribly slow and inefficient. The object of creating the method was to have a sure way of judging a graph as an SCC or not. Thus it was designed to be accurate rather than efficient.

Parameters:
graph - The potential SCC (a DirectedGraph)
Returns:
true if the graph is an SCC, false otherwise

smallestCutSet

public static java.util.Collection smallestCutSet(DirectedGraph graph,
                                                  BasicDepthFirstSearchTree tree,
                                                  NMRArchitecture arch)

nmrSCCsUsingSCCDecomposition

public static boolean nmrSCCsUsingSCCDecomposition(SCCDepthFirstSearch sccDFS,
                                                   NMRArchitecture arch,
                                                   ReplicationUtilizationTracker capacity,
                                                   boolean allowSCCDecomposition,
                                                   int sortType,
                                                   ReplicationType replicationType,
                                                   boolean override)
Determines how many SCCs can be triplicated using the given capacity object. This method will explore SCC decomposition to include as many SCCs as possible.

Parameters:
sccDFS - The SCCDepthFirstSearch structure of the edif circuit
arch - The NMRArchitecture
capacity - The capacity object to use for testing SCC inclusion.
allowSCCDecomposition - This flag indicates that SCCs will be decomposed if they don't fit. If false, any SCCs that don't fit are skipped.
sortType - The method of SCC sorting used (3 = topological sorting)
edgeCutSet - An empty List for returning Edge objects that must be cut.
replicationFacotor - The replication factor to use (3=tmr, 2=dwc, etc.)
Returns:
true if ALL instances were triplicated, false otherwise

validCutSet

public static java.util.Collection validCutSet(DirectedGraph graph,
                                               BasicDepthFirstSearchTree tree,
                                               NMRArchitecture arch)
Identify a valid set of edges that completely removes feedback in the given DFSTree. Assume that the tree is a SCC.

Parameters:
graph -
tree -
arch -
Returns:
A Collection of

validCutSet

public static java.util.Collection validCutSet(SCCDepthFirstSearch sccs,
                                               NMRArchitecture arch)

_decomposeSCC

private static void _decomposeSCC(AbstractEdifGraph graph,
                                  java.util.List sccList,
                                  java.util.List singleNodeSCCs,
                                  BasicDepthFirstSearchTree scc)
Internal helper method for tmrSCCsUsingSCCDecomposition method. This method breaks up an SCC into smaller SCCs and single nodes. These are added to the internal structures used by the parent method.

Parameters:
graph - The top-level graph which contains this SCC
sccList - The List of SCCs to triplicate
singleNodeSCCs - The List of single nodes to triplicate later
scc - The SCC to decompose