edu.byu.ece.edif.util.graph
Class EdifCellDFS

java.lang.Object
  extended by edu.byu.ece.edif.util.graph.EdifCellDFS

public class EdifCellDFS
extends java.lang.Object

A depth first search algorithm using the EDIF classes only. This requires much less memory and is much faster than the Ptolemy graph version.

TODO:

Version:
$Id:EdifCellDFS.java 198 2008-04-16 21:14:21Z jamesfcarroll $
Author:
Mike Wirthlin

Field Summary
protected  java.util.List _backEdges
          A Collection of edges in the graph that complete a cycle.
(package private)  java.util.Map _depthMap
          The key to this map is a ECI.
protected  java.util.List _finished
          A list of Nodes in the graph in the order in which they finish
protected  java.util.Collection _forwardCrossEdges
           
protected  EdifCellInstanceGraph _ic
           
protected  java.util.Collection _instances
          The original graph used by this algorithm.
protected  java.util.Collection _treeRoots
          A list of root Nodes of trees in the forest.
protected  java.util.Collection _trees
           
protected  java.util.List _visited
          A list of Nodes in the graph in the order in which they are first visited.
protected static boolean DEBUG
           
 
Constructor Summary
EdifCellDFS(java.util.Collection c, EdifCellInstanceGraph ecic, java.util.List order, boolean invertDirection)
          Creates a depth-first forest of trees from the directed graph.
EdifCellDFS(EdifCell c)
           
EdifCellDFS(EdifCell c, EdifCellInstanceGraph ecic)
           
EdifCellDFS(EdifCell c, EdifCellInstanceGraph ecic, java.util.List order, boolean invertDirection)
           
EdifCellDFS(EdifCell c, java.util.List order, boolean invertDirection)
           
 
Method Summary
protected  void _search(java.util.List order, boolean invertDirection)
          This method performs the top-level depth first search on directed graph.
protected  void _search2(java.util.List order, boolean invertDirection)
           
protected  DFSTree _visitNonrecursive(EdifCellInstance eci1, boolean invertDirection)
          Perform a non-recursive depth-first visit of instances in an EdifCell.
 java.util.List getBackEdges()
           
 int getDepth(EdifCellInstance eci)
           
 java.util.List getFinishList()
           
 java.util.List getReverseFinishList()
           
 java.util.Collection getTreeRoots()
          Provides a Collection of Nodes in this graph where each Node is a root of a spanning tree.
static java.util.List invertList(java.util.List list)
           
protected  boolean isVisited(EdifCellInstance eci)
           
 void removeSingleNodeTrees()
           
static java.util.Collection sccDecomposition(java.util.Collection c, EdifCellInstanceGraph ecic)
           
static java.util.Collection sccDecomposition(EdifCell c)
          Graph like data structure Create more useful "trees" and return keep "net" connectivity information to recreate cycle feedback edges for "breaking" cycle Find cut-sets in wiring Identify simple adder feedback cycles extract counters and incrementers (combine 2-cell sccs) report as counters Ability to create "smart" adders/incrementers Find all 2-cell SCCs (Many of the larger SCCs have MUXCYs and are probably part of adders) Identify appropriate carry/next stage signal see if signal goes to another SCC (if so, combine) Characterize each SCC (or super SCC) # logic predecessors (cone of logic) # logic successors # SCC successors # feed-forward successors Graph structure: backward reachable instances (from a set of instances) forward reachable instances (from a set of instances) predecessor/successor "edges" (EPRS?) predecessor/successor instances (from a single instance) sink and source node(s) topological sort depth first search Represent a "collection" of instances as a node SCC decomposition
static java.util.Collection sccDecomposition(EdifCell cell, java.util.Collection c)
           
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

_instances

protected java.util.Collection _instances
The original graph used by this algorithm.


_visited

protected java.util.List _visited
A list of Nodes in the graph in the order in which they are first visited.


_finished

protected java.util.List _finished
A list of Nodes in the graph in the order in which they finish


_treeRoots

protected java.util.Collection _treeRoots
A list of root Nodes of trees in the forest.


_backEdges

protected java.util.List _backEdges
A Collection of edges in the graph that complete a cycle. TODO: there is no ordering in this List so change the List to a Collection


_forwardCrossEdges

protected java.util.Collection _forwardCrossEdges

_ic

protected EdifCellInstanceGraph _ic

_depthMap

java.util.Map _depthMap
The key to this map is a ECI. the Value is an Integer object that represents the depth in the tree of the node.


DEBUG

protected static boolean DEBUG

_trees

protected java.util.Collection _trees
Constructor Detail

EdifCellDFS

public EdifCellDFS(EdifCell c)

EdifCellDFS

public EdifCellDFS(EdifCell c,
                   EdifCellInstanceGraph ecic)

EdifCellDFS

public EdifCellDFS(java.util.Collection c,
                   EdifCellInstanceGraph ecic,
                   java.util.List order,
                   boolean invertDirection)
Creates a depth-first forest of trees from the directed graph.

Parameters:
g - The directed possibly cyclic graph to search
order - The order to process the Nodes
invertDirection - Perform the depth first search in an inverted order (i.e. invert the direction of all directed edges)

EdifCellDFS

public EdifCellDFS(EdifCell c,
                   EdifCellInstanceGraph ecic,
                   java.util.List order,
                   boolean invertDirection)

EdifCellDFS

public EdifCellDFS(EdifCell c,
                   java.util.List order,
                   boolean invertDirection)
Method Detail

getFinishList

public java.util.List getFinishList()

getBackEdges

public java.util.List getBackEdges()

getReverseFinishList

public java.util.List getReverseFinishList()

getTreeRoots

public java.util.Collection getTreeRoots()
Provides a Collection of Nodes in this graph where each Node is a root of a spanning tree.


invertList

public static java.util.List invertList(java.util.List list)

sccDecomposition

public static java.util.Collection sccDecomposition(EdifCell c)
Graph like data structure
  1. Create more useful "trees" and return
    • keep "net" connectivity information to recreate cycle
    • feedback edges for "breaking" cycle
  2. Find cut-sets in wiring
  3. Identify simple adder feedback cycles
    • extract counters and incrementers (combine 2-cell sccs)
    • report as counters
    • Ability to create "smart" adders/incrementers
    • Find all 2-cell SCCs (Many of the larger SCCs have MUXCYs and are probably part of adders)
    • Identify appropriate carry/next stage signal
    • see if signal goes to another SCC (if so, combine)
  4. Characterize each SCC (or super SCC)
    • # logic predecessors (cone of logic)
    • # logic successors
    • # SCC successors
    • # feed-forward successors
Graph structure:


sccDecomposition

public static java.util.Collection sccDecomposition(EdifCell cell,
                                                    java.util.Collection c)

sccDecomposition

public static java.util.Collection sccDecomposition(java.util.Collection c,
                                                    EdifCellInstanceGraph ecic)

removeSingleNodeTrees

public void removeSingleNodeTrees()

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

_search

protected void _search(java.util.List order,
                       boolean invertDirection)
This method performs the top-level depth first search on directed graph. The order in which the graph Nodes are visited is determined by the List parameter. This method will sequentially visit each Node in the list and call the recursive _visit method. The _visit method will visit all "successor" Nodes of the chosen Node (excluding feedback). When visit is completed, this method will choose the next unvisited item in the list. Each call to _visit from this method will create a new spanning tree in the depth first search.

Parameters:
order - Visit order of Nodes within the Graph
invertDirection - Direction of edges to visit. When true, depth first traversal will follow the opposite direction of the Edges. When false, the traversal will follow the forward direction of the Edges.

isVisited

protected boolean isVisited(EdifCellInstance eci)

_search2

protected void _search2(java.util.List order,
                        boolean invertDirection)

getDepth

public int getDepth(EdifCellInstance eci)

_visitNonrecursive

protected DFSTree _visitNonrecursive(EdifCellInstance eci1,
                                     boolean invertDirection)
Perform a non-recursive depth-first visit of instances in an EdifCell. This method uses an internal stack to manage the traversal through the circuit instead of recursion. This leads to significantly lower memory requirements (the recursive version would kill the JVM stack for large designs).

Parameters:
eci1 -
invertDirection -
Returns: