mapss.dif.csdf.sdf.mem
Class ConflictGraph

java.lang.Object
  mocgraph.Graph
      mapss.dif.csdf.sdf.mem.PartitionBase
          mapss.dif.csdf.sdf.mem.PartitionedGraph
              mapss.dif.csdf.sdf.mem.ConflictGraph

All Implemented Interfaces:

java.lang.Cloneable

public class ConflictGraph
extends PartitionedGraph

The conflict graph for data partitioning.

Version:

$Id: ConflictGraph.java 406 2007-05-10 14:27:07Z plishker $

Author:

Mingyung Ko

Constructor Summary

ConflictGraph()
A constructor.

ConflictGraph(mocgraph.Graph graph)
Constructor for a given graph.

Method Summary

java.util.Collection	getPartitioningConflicts() Get all the edges of partitioning conflicts.
java.util.Collection	getPartitioningNeighbors(mocgraph.Node node) Get neighbors with partitioning conflicts for the given node.
mocgraph.Node	getSDFBufferOf(mocgraph.Edge sdfEdge) Get the SDF buffer by a given SDF edge.
java.util.Collection	getSDFBuffers() Get all the nodes representing SDF buffers.
mocgraph.Edge	getSDFEdgeOf(mocgraph.Node buffer) Get the SDF edge corresponding to the given SDF buffer (represented as conflict graph node).
java.util.Collection	getSDFEdgesOf(GraphPartition partition) Get all the corresponding SDF edges for the given partition.
SDFGraph	getSDFGraph() Get the SDF graph associated with the conflict graph.
java.util.Collection	getSharingConflicts() Get all the edges of sharing conflicts.
java.util.Collection	getSharingNeighbors(mocgraph.Node node) Get neighbors with sharing conflicts for the given node.
boolean	isParallelismMaximized() Check whether all partitioning conflicts are in the edge cut.
boolean	isSDFBuffer(mocgraph.Node node) Check whether the given node is an SDF buffer.
boolean	isSharingConflict(mocgraph.Edge edge) Check whether the edge is a sharing conflict.
java.lang.String	partitionString() Display partitions in a text string.
void	removeSharingConflicts() Remove all the sharing conflict edges.
void	setPartitioningConflict(mocgraph.Edge edge) Set the edge as partitioning conflict.
void	setSDFBufferMapping(mocgraph.Node buffer, mocgraph.Edge sdfEdge) Set buffer mapping for a node.
void	setSDFGraph(SDFGraph sdfGraph) Set the associated SDF graph.
void	setSharingConflict(mocgraph.Edge edge) Set the edge as sharing conflict.
double	stateVariableCost(GraphPartition partition) Total state variable cost of the given partition.
void	updateSDFBufferCost(mocgraph.sched.Schedule schedule) Update SDF buffer sizes from a schedule.
void	updateSDFBufferCost(mocgraph.mapping.ToIntMapMapping sizes) Update SDF buffer sizes for nodes representing SDF buffers.

Methods inherited from class mapss.dif.csdf.sdf.mem.PartitionedGraph

addPartition, addPartitions, ascendentPartitions, descendentPartitions, dualOf, edgeCut, edgeCutOf, edgeCutOf, edgeCutString, edgeCutValueOf, edgeNonCutValueOf, getPartitions, partitionIndexOf, partitionIndexOf, partitionOf, partitionOf, partitionsOf, resetPartitions

Methods inherited from class mapss.dif.csdf.sdf.mem.PartitionBase

_checkGraphElement, ascendentListOf, descendentListOf, getIndex, removeEdge, removeNode, setElementValue, setElementValues, setIndex, valueOf

Methods inherited from class mocgraph.Graph

_addEdge, _connect, _connectEdge, _disconnect, _disconnectEdge, _emptyGraph, _initializeAnalyses, _registerChange, _registerEdge, _registerNode, addAnalysis, addEdge, addEdge, 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, equals, hashCode, hidden, hiddenEdgeCount, hiddenEdges, hideEdge, incidentEdgeCount, incidentEdges, neighborEdges, neighbors, node, node, nodeCount, nodeLabel, nodeLabel, nodes, nodes, nodes, nodeWeight, restoreEdge, selfLoopEdgeCount, selfLoopEdgeCount, selfLoopEdges, selfLoopEdges, subgraph, subgraph, toString, validateWeight, validateWeight, validateWeight, validateWeight, validEdgeWeight, validNodeWeight, weightArray

Methods inherited from class java.lang.Object

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

Constructor Detail

ConflictGraph

public ConflictGraph()

A constructor.

ConflictGraph

public ConflictGraph(mocgraph.Graph graph)

Constructor for a given graph. Construct the partitioned graph by duplicating all nodes and edges.

Parameters:

graph - The graph to construct from.

Method Detail

getPartitioningConflicts

public java.util.Collection getPartitioningConflicts()

Get all the edges of partitioning conflicts. The edges are returned in an unmodifiable form.

Returns:

The conflicts in an unmodifiable Collection.

getPartitioningNeighbors

public java.util.Collection getPartitioningNeighbors(mocgraph.Node node)

Get neighbors with partitioning conflicts for the given node. The neighbors are returned in an unmodifiable form.

Parameters:

node - The given node to get neighbors.

Returns:

The neighbors in an unmodifiable Collection.

getSharingConflicts

public java.util.Collection getSharingConflicts()

Get all the edges of sharing conflicts. The edges are returned in an unmodifiable form.

Returns:

The conflicts in an unmodifiable Collection.

getSharingNeighbors

public java.util.Collection getSharingNeighbors(mocgraph.Node node)

Get neighbors with sharing conflicts for the given node. The neighbors are returned in an unmodifiable form.

Parameters:

node - The given node to get neighbors.

Returns:

The neighbors in an unmodifiable Collection.

getSDFBufferOf

public mocgraph.Node getSDFBufferOf(mocgraph.Edge sdfEdge)

Get the SDF buffer by a given SDF edge. SDF buffers are represented as conflict graph nodes.

Parameters:

sdfEdge - The given SDF edge.

Returns:

The conflict graph node representing the SDF buffer.

getSDFBuffers

public java.util.Collection getSDFBuffers()

Get all the nodes representing SDF buffers. The nodes are returned in an unmodifiable form.

Returns:

Nodes of SDF buffers.

getSDFEdgeOf

public mocgraph.Edge getSDFEdgeOf(mocgraph.Node buffer)

Get the SDF edge corresponding to the given SDF buffer (represented as conflict graph node).

Parameters:

buffer - The given node representing an SDF buffer.

Returns:

The corresponding SDF edge.

getSDFEdgesOf

public java.util.Collection getSDFEdgesOf(GraphPartition partition)

Get all the corresponding SDF edges for the given partition.

Parameters:

partition - The given partition.

Returns:

The collection of the corresponding SDF edges.

getSDFGraph

public SDFGraph getSDFGraph()

Get the SDF graph associated with the conflict graph.

Returns:

The associated SDF graph.

isParallelismMaximized

public boolean isParallelismMaximized()

Check whether all partitioning conflicts are in the edge cut.

Returns:

True if the parallelism is maximal.

isSDFBuffer

public boolean isSDFBuffer(mocgraph.Node node)

Check whether the given node is an SDF buffer.

Parameters:

node - The node to check.

Returns:

True if the given node represents an SDF buffer.

isSharingConflict

public boolean isSharingConflict(mocgraph.Edge edge)

Check whether the edge is a sharing conflict.

Parameters:

edge - The edge to check.

Returns:

True if it is a sharing conflict edge.

partitionString

public java.lang.String partitionString()

Display partitions in a text string.

Overrides:

partitionString in class PartitionedGraph

Returns:

The output.

removeSharingConflicts

public void removeSharingConflicts()

Remove all the sharing conflict edges.

setSDFBufferMapping

public void setSDFBufferMapping(mocgraph.Node buffer,
                                mocgraph.Edge sdfEdge)

Set buffer mapping for a node. Conflict graph nodes represent SDF buffers (allocated for SDF edges) and program variables. Buffers are not implemented and simply represented as SDF edges.

Parameters:

buffer - The node representing SDF buffers.

sdfEdge - The SDF edge the buffer corresponds to.

setPartitioningConflict

public void setPartitioningConflict(mocgraph.Edge edge)

Set the edge as partitioning conflict. Value of a partitioning conflict edge equals to the maximal edge counts of an N-node graph. That is, the value equals N(N-1)/2.

Parameters:

edge - The partitioning conflict.

setSDFGraph

public void setSDFGraph(SDFGraph sdfGraph)

Set the associated SDF graph. SDF buffers are also incorporated as conflict graph nodes.

Parameters:

sdfGraph - The associated SDF graph.

setSharingConflict

public void setSharingConflict(mocgraph.Edge edge)

Set the edge as sharing conflict. Value of a sharing conflict edge equals one.

Parameters:

edge - The partitioning conflict.

stateVariableCost

public double stateVariableCost(GraphPartition partition)

Total state variable cost of the given partition. The cost excludes buffer sizes which are changing dynamically or not yet figured out.

Parameters:

partition - The partition.

Returns:

The capacity requirement (or memory space cost).

updateSDFBufferCost

public void updateSDFBufferCost(mocgraph.mapping.ToIntMapMapping sizes)

Update SDF buffer sizes for nodes representing SDF buffers.

Parameters:

sizes - The buffer costs.

updateSDFBufferCost

public void updateSDFBufferCost(mocgraph.sched.Schedule schedule)

Update SDF buffer sizes from a schedule. The schedule must be consistent with the associated SDF graph.

Parameters:

schedule - The schedule to derive the cost.