mapss.dif.csdf.sdf.mem
Class DataPartitioning

java.lang.Object
  mapss.dif.csdf.sdf.mem.DataPartitioning

public class DataPartitioning
extends java.lang.Object

The class for data partitioning in dual homogeneous memory bank architectures. It is developed for Mingyung's research. Basically, an conflict graph should be provided. Generally, nodes representing data variables while edges' meaning depends on applications.

Version:

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

Author:

Mingyung Ko

Field Summary

protected ConflictGraph

_conflictGraph The conflict graph.

Constructor Summary

DataPartitioning(ConflictGraph conflictGraph)
A constructor with an conflict graph.

Method Summary

protected void	_alternateAssignment(mocgraph.Node seed) Alternate partition assignment for a given node as seed.
protected boolean	_linksExistFor(GraphPartition partition, mocgraph.Node node) Check existence of links between the partition and node.
protected GraphPartition	_minPartition(PartitionedGraph pGraph) The partition with minimal sum of node values.
protected void	_prioritizedAlternateAssignment(mocgraph.Node node) An SPF-like alternate assignment which favors partitioning conflicts.
protected void	_processNeighborsOf(mocgraph.Node node) Bank assignment for neighbor nodes of a seed.
ConflictGraph	consolidateSharedBuffersStrategy() Partitioning strategy with consolidated shared buffers.
void	initPartitions(int counts) Initialize partitions by the given counts.
int	minimalPartitionSize() Return the minimal partition size.
ConflictGraph	sharedSPFStrategy() An extended SPF strategy considering sharing conflicts.
ConflictGraph	SPFStrategy() The SPF heuristic for two memory banks.
ConflictGraph	SPFStrategy(int partitionCounts) The "Smallest Partition First (SPF)" strategy in solving data partitioning problems.
java.lang.String	toOPBDPString() Transform to OPBDP file format.
ConflictGraph	twoColoringStrategy() A two coloring algorithm.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

_conflictGraph

protected ConflictGraph _conflictGraph

The conflict graph.

Constructor Detail

DataPartitioning

public DataPartitioning(ConflictGraph conflictGraph)

A constructor with an conflict graph.

Parameters:

conflictGraph - The conflict graph to partition.

Method Detail

twoColoringStrategy

public ConflictGraph twoColoringStrategy()

A two coloring algorithm. Two coloring is of polynomial complexity.

Returns:

The result as a ConflictGraph.

SPFStrategy

public ConflictGraph SPFStrategy()

The SPF heuristic for two memory banks. See also SPFStrategy(int).

Returns:

The result as a ConflictGraph.

SPFStrategy

public ConflictGraph SPFStrategy(int partitionCounts)

The "Smallest Partition First (SPF)" strategy in solving data partitioning problems. It is basically a greedy approach. The algorithm is based on the fact of sparse connection of conflict graphs.

Parameters:

partitionCounts - The number of partitions available.

Returns:

The result as a ConflictGraph.

sharedSPFStrategy

public ConflictGraph sharedSPFStrategy()
                                throws DataPartitioningException

An extended SPF strategy considering sharing conflicts. It assumes two memory banks only.

Returns:

The result as a ConflictGraph.

Throws:

DataPartitioningException

consolidateSharedBuffersStrategy

public ConflictGraph consolidateSharedBuffersStrategy()
                                               throws DataPartitioningException

Partitioning strategy with consolidated shared buffers. Before actual partitioning, the strategy first consolidates shared buffers into single nodes and leads to a simpler conflict graph topology. After the consolidation, SPFStrategy() is invoked for actual partitioning.

Returns:

The result as a ConflictGraph.

Throws:

DataPartitioningException

initPartitions

public void initPartitions(int counts)

Initialize partitions by the given counts.

Parameters:

counts - Number of partitions to initialize.

minimalPartitionSize

public int minimalPartitionSize()

Return the minimal partition size. The size is not necessarily a sum of node sizes. Users should refer to the particular size calculation of a partitioning algorithm. However, by default, this method simply returns the sum of all node sizes.

Returns:

The minimal partition size in int.

toOPBDPString

public java.lang.String toOPBDPString()

Transform to OPBDP file format. OPBDP is an integer programming solver available on the site below. http://www.mpi-sb.mpg.de/units/ag2/software/opbdp/

Returns:

The format OPBDP accepts.

_alternateAssignment

protected void _alternateAssignment(mocgraph.Node seed)

Alternate partition assignment for a given node as seed. The assignment is for connected components (including one-node trivial singletons) only. This method is called both in SPF and max weighted edge cut approaches.

Parameters:

seed - The seed node.

_processNeighborsOf

protected void _processNeighborsOf(mocgraph.Node node)

Bank assignment for neighbor nodes of a seed. This is to facilitate _alternateAssignment(Node).

Parameters:

node - The node whose neighbors are to be processed.

_prioritizedAlternateAssignment

protected void _prioritizedAlternateAssignment(mocgraph.Node node)
                                        throws DataPartitioningException

An SPF-like alternate assignment which favors partitioning conflicts. While partitioning neighbors (of the node) are still alternately assigned, sharing conflicts are done so only the condition permits. The results guarantee maximum edge cut for partitioning conflicts just like SPF. Maximum edge cut is also tried for sharing conflicts only if the cut for partitioning conflicts is kept.

Parameters:

node - The node to start the alternate assignment.

Throws:

DataPartitioningException

_minPartition

protected GraphPartition _minPartition(PartitionedGraph pGraph)

The partition with minimal sum of node values.

Parameters:

pGraph - The partitioned graph.

Returns:

The minimal partition.

_linksExistFor

protected boolean _linksExistFor(GraphPartition partition,
                                 mocgraph.Node node)

Check existence of links between the partition and node.

Parameters:

partition - The partition.

node - The node.

Returns:

True if there are links between them, false otherwise.