mapss.dif.mdsdf
Class MDSDFGraph

java.lang.Object
  mocgraph.Graph
      mocgraph.DirectedGraph
          mapss.dif.DIFGraph
              mapss.dif.mdsdf.MDSDFGraph

All Implemented Interfaces:

java.lang.Cloneable

public class MDSDFGraph
extends DIFGraph

Information and computations associated with MDSDFGraph. Multidimensional synchronous dataflow is proposed by E. A. Lee and further developed by P. K. Murthy. Please refer to "Multidimensional Synchronous Dataflow" by P. K. Murthy and E. A. Lee.

The algorithm to compute multidimensional repetitions is based on Figure 3.5 in "Software Synthesis from Dataflow Graphs" by S. S. Bhattacharyya, P. K. Murthy, and E. A. Lee, and is modified from that SDF algorithm to support multi-dimensions.

Mix-dimensionality is supported in the MDSDFGraph, which means the multidimensional production rate and consumption rate can have different dimensionality and edges can have different dimensionality.

For synchronizing between mismatched dimensionality, the fewer dimensionality is assumed to be lower ones in the larger dimensionality, and the remaining dimensions are assumed to be 1.

Version:

$Id: MDSDFGraph.java 1687 2007-05-08 01:38:09Z jerryhsu $

Author:

Chia-Jui Hsu

Field Summary

protected int	_dimensionality
protected java.util.HashMap	_repetitionMap
protected int[][]	_repetitions

Constructor Summary

MDSDFGraph()
Construct an empty MDSDF graph.

MDSDFGraph(int nodeCount)
Construct an empty MDSDF graph with enough storage allocated for the specified number of nodes.

MDSDFGraph(int nodeCount, int edgeCount)
Construct an empty MDSDF graph with enough storage allocated for the specified number of edges, and number of nodes.

Method Summary

protected boolean	_checkConsistency()
protected void	_computeNodeRepetition(mocgraph.Node node)
int	computeDimensionality() Compute the dimensionality of the MDSDF graph.
java.util.HashMap	computeRepetitions() Compute the multidimensional repetitions of the MDSDF graph.
int	getDimensionality() Get the computed dimensionality of the MDSDF graph.
int[]	getRepetition(mocgraph.Node node) Get the computed multidimensional repetition of node.
java.util.HashMap	getRepetitions() Get the computed multidimensional repetitions of the MDSDF graph.
boolean	validEdgeWeight(java.lang.Object weight) Verify edge weight for MDSDF graph.
boolean	validNodeWeight(java.lang.Object weight) Verify node weight for MDSDF graph.

Methods inherited from class mapss.dif.DIFGraph

_getAttributeContainer, _registerEdge, _registerNode, _removeAttributeContainer, _removeReferenceFromAttributes, _setAttributeContainer, addEdge, addEdge, equals, getAttribute, getAttribute, getAttributeByContent, getAttributeByContent, getAttributeDescriptions, getAttributeDescriptions, getAttributeNames, getAttributeNames, getAttributes, getAttributes, getAttributesByContent, getAttributesByContent, getEdge, getName, getName, getNode, getObject, getParameter, getParameterNames, getParameters, hashCode, hideEdge, mergeGraph, mirror, mirror, removeAllAttributes, removeAllAttributes, removeAttribute, removeAttribute, removeAttribute, removeAttribute, removeEdge, removeNode, removeParameter, restoreEdge, setAttribute, setAttribute, setName, setName, setParameter, subgraph, subgraph

Methods inherited from class mocgraph.DirectedGraph

_connect, _connectedSubGraph, _disconnect, _initializeAnalyses, backwardReachableNodes, backwardReachableNodes, backwardReachableNodes, backwardReachableNodes, cycleNodeCollection, cycleNodes, edgeExists, edgeExists, inputEdgeCount, inputEdges, isAcyclic, outputEdgeCount, outputEdges, predecessorEdges, predecessors, reachableNodes, reachableNodes, reachableNodes, reachableNodes, sccDecomposition, selfLoopEdgeCount, sinkNodeCount, sinkNodes, sourceNodeCount, sourceNodes, subgraphs, successorEdges, successors, toDirectedAcyclicGraph, topologicalSort, topologicalSort, transitiveClosure

Methods inherited from class mocgraph.Graph

_addEdge, _connectEdge, _disconnectEdge, _emptyGraph, _registerChange, addAnalysis, addEdge, addEdge, addEdge, addEdges, addGraph, addNode, addNode, addNodes, addNodeWeight, addNodeWeights, changeCount, clone, cloneAs, connectedComponents, containsEdge, containsEdgeWeight, containsNode, containsNodeWeight, edge, edge, edgeCount, edgeLabel, edgeLabel, edges, edges, edges, edgeWeight, hidden, hiddenEdgeCount, hiddenEdges, incidentEdgeCount, incidentEdges, neighborEdges, neighbors, node, node, nodeCount, nodeLabel, nodeLabel, nodes, nodes, nodes, nodeWeight, selfLoopEdgeCount, selfLoopEdges, selfLoopEdges, toString, validateWeight, validateWeight, validateWeight, validateWeight, weightArray

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

_dimensionality

protected int _dimensionality

_repetitionMap

protected java.util.HashMap _repetitionMap

_repetitions

protected int[][] _repetitions

Constructor Detail

MDSDFGraph

public MDSDFGraph()

Construct an empty MDSDF graph.

MDSDFGraph

public MDSDFGraph(int nodeCount)

Construct an empty MDSDF graph with enough storage allocated for the specified number of nodes.

Parameters:

nodeCount - The number of nodes.

MDSDFGraph

public MDSDFGraph(int nodeCount,
                  int edgeCount)

Construct an empty MDSDF graph with enough storage allocated for the specified number of edges, and number of nodes.

Parameters:

nodeCount - The integer specifying the number of nodes

edgeCount - The integer specifying the number of edges

Method Detail

computeDimensionality

public int computeDimensionality()

Compute the dimensionality of the MDSDF graph. The dimensionality of a MDSDF graph is the maximum dimensionality among all edges.

Returns:

The dimensionality of the MDSDF graph.

computeRepetitions

public java.util.HashMap computeRepetitions()

Compute the multidimensional repetitions of the MDSDF graph.

Returns:

The computed multidimensional repetitions of the MDSDF graph in HashMap, i.e., Node to int[].

Throws:

java.lang.RuntimeException - If the MDSDF graph is inconsistent.

getDimensionality

public int getDimensionality()

Get the computed dimensionality of the MDSDF graph. The dimensionality of a MDSDF graph is the maximum dimensionality among all edges.

Returns:

The dimensionality of the MDSDF graph.

See Also:

computeDimensionality

getRepetition

public int[] getRepetition(mocgraph.Node node)

Get the computed multidimensional repetition of node. The dimensionality of the multidimensional repetition is equal to the dimensionality of the graph.

Parameters:

node -

Returns:

The computed multidimensional repetition of node.

getRepetitions

public java.util.HashMap getRepetitions()

Get the computed multidimensional repetitions of the MDSDF graph. The dimensionality of the multidimensional repetition of every node is equal to the dimensionality of the graph.

Returns:

The computed multidimensional repetitions of the MDSDF graph in HashMap, i.e., Node to int[].

validEdgeWeight

public boolean validEdgeWeight(java.lang.Object weight)

Verify edge weight for MDSDF graph.

Overrides:

validEdgeWeight in class DIFGraph

Parameters:

weight - The edge weight to verify.

Returns:

True if the given edge weight is valid for MDSDF graph.

validNodeWeight

public boolean validNodeWeight(java.lang.Object weight)

Verify node weight for MDSDF graph.

Overrides:

validNodeWeight in class DIFGraph

Parameters:

weight - The node weight to verify.

Returns:

True if the given node weight is valid for MDSDF graph.

_checkConsistency

protected boolean _checkConsistency()

_computeNodeRepetition

protected void _computeNodeRepetition(mocgraph.Node node)