mapss.dif.csdf.sdf.sched
Class DPPOStrategy

java.lang.Object
  mapss.dif.DIFScheduleStrategy
      mapss.dif.csdf.sdf.sched.DPPOStrategy

All Implemented Interfaces:

mocgraph.analysis.analyzer.Analyzer, mocgraph.analysis.analyzer.GraphAnalyzer, mocgraph.sched.ScheduleAnalyzer

Direct Known Subclasses:

ABMLBDPPOStrategy, BDPPOStrategy, GDPPOStrategy, SDPPOStrategy

public abstract class DPPOStrategy
extends DIFScheduleStrategy

The base class of Dynamic Programming Post Optimization (DPPO). No particular optimization objective is targeted and this class is therefore abstract. The key method is _optimumFor(int, int) for the implementation. Subclasses are meant to implement it ONLY and nothing else should be modified.

Version:

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

Author:

Mingyung Ko

Field Summary

protected java.util.List	_lexicalOrder The given lexical order of nodes for DPPO.
protected int	_tableDimension The dimension of the dynamic programming table.

Fields inherited from class mapss.dif.DIFScheduleStrategy

_clusterManager

Constructor Summary

DPPOStrategy(SDFGraph graph, java.util.List lexicalOrder)
Constructor for a given graph and a lexical order.

DPPOStrategy(SDFGraph graph, java.util.List lexicalOrder, DPPOTableElement element)
Constructor for a given graph, a lexical order, and the type of dynamic programming table element.

Method Summary

protected int	_bufferCost(mocgraph.Edge edge, int i, int j) Compute the given edge's buffer cost in the subgraph induced by the index range.
protected void	_computeDPPO() Dynamic programming computation.
protected mocgraph.sched.ScheduleElement	_computeSchedule(int left, int right, int repetition) Compute an SDF schedule from the DPPO results.
protected java.util.Collection	_crossingSDFEdges(int i, int j, int split) The SDF edges crossing the given split in the range from i to j.
protected DPPOTableElement	_DPPOTableElement(int i, int j) Get the element of the DPPO table.
protected abstract void	_optimumFor(int i, int j) The optimal results along the elements with index i to j.
protected java.util.Collection	_SDFEdges(int i, int j) Get the SDF edges for given nodes.
protected java.util.Collection	_SDFNodes(int i, int j) Get SDF nodes for the given lexical order indices.
protected void	_verifyIndices(int i, int j) Verify the given pair of indices and a split.
protected void	_verifyIndices(int i, int j, int split) Verify the given pair of indices and a split.
double	optimalCost() Return the optimal cost.
mocgraph.sched.Schedule	schedule() Construct an SDF schedule from the DPPO computation.
void	setLexicalOrder(java.util.List order) Set the lexical order of SDF actors.
java.lang.String	toString() A desrciption of the scheduler.

Methods inherited from class mapss.dif.DIFScheduleStrategy

getClusterManager, graph, valid

Methods inherited from class java.lang.Object

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

Field Detail

_lexicalOrder

protected java.util.List _lexicalOrder

The given lexical order of nodes for DPPO.

_tableDimension

protected int _tableDimension

The dimension of the dynamic programming table. It is equal to the length of lexical order.

Constructor Detail

DPPOStrategy

public DPPOStrategy(SDFGraph graph,
                    java.util.List lexicalOrder)

Constructor for a given graph and a lexical order.

Parameters:

graph - The given SDF graph.

lexicalOrder - The lexical order in the form of List.

DPPOStrategy

public DPPOStrategy(SDFGraph graph,
                    java.util.List lexicalOrder,
                    DPPOTableElement element)

Constructor for a given graph, a lexical order, and the type of dynamic programming table element.

Parameters:

graph - The given SDF graph.

lexicalOrder - The lexical order in the form of List.

element - The type of dynamic programming table element.

Method Detail

optimalCost

public double optimalCost()

Return the optimal cost.

Returns:

The optimal cost in double.

schedule

public mocgraph.sched.Schedule schedule()

Construct an SDF schedule from the DPPO computation.

Specified by:

schedule in interface mocgraph.sched.ScheduleAnalyzer

Overrides:

schedule in class DIFScheduleStrategy

Returns:

An SDF schedule.

setLexicalOrder

public void setLexicalOrder(java.util.List order)

Set the lexical order of SDF actors.

Parameters:

order - The desired lexical order.

toString

public java.lang.String toString()

A desrciption of the scheduler.

Specified by:

toString in interface mocgraph.analysis.analyzer.Analyzer

Overrides:

toString in class DIFScheduleStrategy

Returns:

A text description.

_bufferCost

protected int _bufferCost(mocgraph.Edge edge,
                          int i,
                          int j)

Compute the given edge's buffer cost in the subgraph induced by the index range.

Parameters:

edge - The edge.

i - The index of the starting node.

j - The index of the ending node.

Returns:

The buffer cost.

_computeDPPO

protected void _computeDPPO()

Dynamic programming computation.

_computeSchedule

protected mocgraph.sched.ScheduleElement _computeSchedule(int left,
                                                          int right,
                                                          int repetition)

Compute an SDF schedule from the DPPO results.

Parameters:

left - Lexical ordering index of the leftmost node.

right - Lexical ordering index of the rightmost node.

repetition - The repetition count of the node sequence.

Returns:

A schedule in mocgraph.sched representation.

_crossingSDFEdges

protected java.util.Collection _crossingSDFEdges(int i,
                                                 int j,
                                                 int split)

The SDF edges crossing the given split in the range from i to j.

Parameters:

i - The index of the starting node.

j - The index of the ending node.

split - The split position.

Returns:

The SDF edges across the split.

_DPPOTableElement

protected DPPOTableElement _DPPOTableElement(int i,
                                             int j)

Get the element of the DPPO table. DPPO assumes a given lexical ordering of nodes. Index number i should be less or equal to j.

Parameters:

i - The index of the starting (left) node

j - The index of the ending (right) node

Returns:

The desired element in DPPOMatrixElement.

_optimumFor

protected abstract void _optimumFor(int i,
                                    int j)

The optimal results along the elements with index i to j. In the implementation, the optimal cost, split, and any relevant attributes should be computed and stored.

Parameters:

i - The element with index i.

j - The element with index j.

_SDFEdges

protected java.util.Collection _SDFEdges(int i,
                                         int j)

Get the SDF edges for given nodes. The nodes are specified by their index range in the lexical order. The result returned is edges of the subgraph induced from the specified nodes.

Parameters:

i - The index of the starting node.

j - The index of the ending node.

Returns:

The induced SDF edges.

_SDFNodes

protected java.util.Collection _SDFNodes(int i,
                                         int j)

Get SDF nodes for the given lexical order indices.

Parameters:

i - The index of the starting node.

j - The index of the ending node.

Returns:

The correspondent SDF nodes.

_verifyIndices

protected void _verifyIndices(int i,
                              int j)

Verify the given pair of indices and a split. The index pair declares a section of the whole lexical order. The pair has to obey the sequence and boundaries of the lexical order.

Parameters:

i - The starting index.

j - The ending index.

Throws:

java.lang.IllegalArgumentException - Exception is thrown if boundaries are violated or i > j.

_verifyIndices

protected void _verifyIndices(int i,
                              int j,
                              int split)

Verify the given pair of indices and a split. The index pair declares a section of the whole lexical order. The pair has to obey the sequence and boundaries of the lexical order. The split position should only occur within the specified section.

Parameters:

i - The starting index.

j - The ending index.

split - The split position.

Throws:

java.lang.IllegalArgumentException - Exception is thrown if boundaries are violated, i > j, or illegal split position is specified.