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

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

public class MoreFrequentVoting
extends java.lang.Object

This class contains methods used to insert voters in a design represented in an EdifGraph structure. The class gives the user the ability to specify the desired frequency of voters to be inserted throughout the design.

Author:
Brian Pratt

Constructor Summary
MoreFrequentVoting()
           
 
Method Summary
static java.util.Set<Edge> breadthFirstVoterInsertion(EdifCellInstanceGraph graph, NMRArchitecture nmrArch, Edge startEdge, java.util.Collection<Edge> previouslyCutEdges, int insertionThreshold, boolean forward)
           
static java.util.Collection<Edge> getEdifEdgesFromPortRefs(EdifCellInstanceGraph graph, java.util.Collection<EdifPortRef> cutSet)
          Obtains the correct EdifEdges in the graph corresponding to the given EdifPortRef objects.
static java.util.Collection<Edge> insertVotersByLogicLevels(EdifCellInstanceGraph graph, NMRArchitecture nmrArch, java.util.Collection<Edge> startEdges, java.util.Collection<Edge> previouslyCutEdges, int insertionThreshold, boolean forward, boolean backward)
          Determines the locations where voters should be inserted in a given design (represented by an EdifGraph).
static java.util.Collection<Edge> insertVotersByLogicLevels(EdifCellInstanceGraph connectivityGraph, NMRArchitecture nmrArch, java.util.Collection<Edge> previouslyCutEdges, int insertionThreshold)
          Locates the Edges where voters should be inserted in a graph given a threshold of levels of logic between voters.
static java.util.Collection<Edge> insertVotersByLogicLevels(EdifCellInstanceGraph connectivityGraph, NMRArchitecture nmrArch, int insertionThreshold)
          Locates the Edges where voters should be inserted in a graph given a threshold of levels of logic between voters.
static java.util.Collection<Edge> partitionGraphWithVoters(EdifCellInstanceGraph connectivityGraph, NMRArchitecture nmrArch, java.util.Collection<Edge> previouslyCutEdges, int numberOfPartitions)
          Determines locations to insert voters in order to partition the graph into X partitions.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

MoreFrequentVoting

public MoreFrequentVoting()
Method Detail

insertVotersByLogicLevels

public static java.util.Collection<Edge> insertVotersByLogicLevels(EdifCellInstanceGraph connectivityGraph,
                                                                   NMRArchitecture nmrArch,
                                                                   int insertionThreshold)
Locates the Edges where voters should be inserted in a graph given a threshold of levels of logic between voters. Does a breadth-first search to find the voter locations.

NOTE: this algorithm is not sophisticated and can give poor results if the wrong threshold is given as the design will not be partitioned evenly.

Parameters:
connectivityGraph -
nmrArch -
insertionThreshold -
Returns:
A Collection of EdifEdges where voters should be inserted

insertVotersByLogicLevels

public static java.util.Collection<Edge> insertVotersByLogicLevels(EdifCellInstanceGraph connectivityGraph,
                                                                   NMRArchitecture nmrArch,
                                                                   java.util.Collection<Edge> previouslyCutEdges,
                                                                   int insertionThreshold)
Locates the Edges where voters should be inserted in a graph given a threshold of levels of logic between voters. Does a breadth-first search to find the voter locations.

NOTE: this algorithm is not sophisticated and can give poor results if the wrong threshold is given as the design will not be partitioned evenly.

Parameters:
connectivityGraph -
nmrArch -
previouslyCutEdges -
insertionThreshold -
Returns:
A Collection of EdifEdges where voters should be inserted

insertVotersByLogicLevels

public static java.util.Collection<Edge> insertVotersByLogicLevels(EdifCellInstanceGraph graph,
                                                                   NMRArchitecture nmrArch,
                                                                   java.util.Collection<Edge> startEdges,
                                                                   java.util.Collection<Edge> previouslyCutEdges,
                                                                   int insertionThreshold,
                                                                   boolean forward,
                                                                   boolean backward)
Determines the locations where voters should be inserted in a given design (represented by an EdifGraph). The frequency of voters is determined by the 'insertionThreshold' argument.

As an example, this method can be used on a component graph (SCCs are collapsed), with the "startEdges" Collection containing all of the EdifEdges which are connected to the top-level outputs of the (flattened) graph, with false and true passed in for the forward and backward parameters, respectively.

TODO: Should this method include resource tracking information? (for each voter that is added) Can we estimate how may voters will be inserted for a given graph and insertionThreshold?

Parameters:
graph -
nmrArch -
startEdges - A Collection of EdifEdges the voter insertion should start from
previouslyCutEdges -
insertionThreshold -
forward -
backward -
Returns:
A Collection of EdifEdges where voters should be inserted

breadthFirstVoterInsertion

public static java.util.Set<Edge> breadthFirstVoterInsertion(EdifCellInstanceGraph graph,
                                                             NMRArchitecture nmrArch,
                                                             Edge startEdge,
                                                             java.util.Collection<Edge> previouslyCutEdges,
                                                             int insertionThreshold,
                                                             boolean forward)

getEdifEdgesFromPortRefs

public static java.util.Collection<Edge> getEdifEdgesFromPortRefs(EdifCellInstanceGraph graph,
                                                                  java.util.Collection<EdifPortRef> cutSet)
Obtains the correct EdifEdges in the graph corresponding to the given EdifPortRef objects.

Parameters:
graph - The EdifCellInstanceGraph graph the Edges are located in
cutSet - The EdifPortRefs to obtain the EdifEdges of
Returns:
A Collection of EdifEdges corresponding to the given EdifPortRef objects in the given graph

partitionGraphWithVoters

public static java.util.Collection<Edge> partitionGraphWithVoters(EdifCellInstanceGraph connectivityGraph,
                                                                  NMRArchitecture nmrArch,
                                                                  java.util.Collection<Edge> previouslyCutEdges,
                                                                  int numberOfPartitions)
Determines locations to insert voters in order to partition the graph into X partitions. The spacing between voters is chosen so as to try and create partitions of equal size.

Parameters:
connectivityGraph -
nmrArch -
previouslyCutEdges -
numberOfPartitions -
Returns:
A Collection of EdifEdges where voters should be inserted