mapss.dif.csdf.sdf.sched
Class MCBStrategy

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

All Implemented Interfaces:

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

public class MCBStrategy
extends DIFScheduleStrategy

A base scheduler using multirate cycle breaking framework. The scheduler computes a schedule by removing qualified graph edges in a hope to make it acyclic. Efficient acyclic schedulers can be applied then.

In this class, _cycleBreaking(SDFGraph), _acyclicScheduling(SDFGraph, int), _tightScheduling(SDFGraph, int), and _computeSchedule(SDFGraph, int) are to be refined according to a specific algorithm. This base class implements edge removal with largest normalized delays (delay / TNSE). Generic topological sorting is implemented in acyclic scheduling while nothing is currently done in tight scheduling.

Version:

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

Author:

Mingyung Ko

Constructor Summary

MCBStrategy(SDFGraph graph)
Constructor for a given SDF graph.

Method Summary

protected mocgraph.sched.ScheduleElement	_acyclicScheduling(SDFGraph graph, int graphRepetitions) Acyclic scheduling for the given graph.
protected mocgraph.sched.ScheduleElement	_computeSchedule(SDFGraph graph, int graphRepetitions) Compute the schedule for the given SDF graph.
protected java.util.Collection	_cycleBreaking(SDFGraph graph) Cycle breaking rule for the graph.
protected boolean	_isTight(SDFGraph graph) Test the graph's tight inter-dependency.
protected void	_putBackEdges(SDFGraph graph) Edges to put back into graph.
protected void	_removeEdges(SDFGraph graph, java.util.Collection edgeCollection) Remove edges from the given graph.
protected mocgraph.sched.ScheduleElement	_tightScheduling(SDFGraph graph, int graphRepetitions) Tight scheduling for the given graph.
mocgraph.sched.Schedule	schedule() Compute the multirate cycle breaking schedule.

Methods inherited from class mapss.dif.DIFScheduleStrategy

getClusterManager, graph, toString, valid

Methods inherited from class java.lang.Object

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

Constructor Detail

MCBStrategy

public MCBStrategy(SDFGraph graph)

Constructor for a given SDF graph.

Parameters:

graph - The given SDF graph.

Method Detail

schedule

public mocgraph.sched.Schedule schedule()

Compute the multirate cycle breaking schedule.

Specified by:

schedule in interface mocgraph.sched.ScheduleAnalyzer

Overrides:

schedule in class DIFScheduleStrategy

Returns:

The schedule.

_acyclicScheduling

protected mocgraph.sched.ScheduleElement _acyclicScheduling(SDFGraph graph,
                                                            int graphRepetitions)

Acyclic scheduling for the given graph. The graph must be acyclic and assumes at least 2 nodes.

The implementation is just a generic topologically sorted and linear schedule. Users can refine this method.

Parameters:

graph - The given graph in SDFGraph.

graphRepetitions - Repetitions for the given graph.

Returns:

The acyclic schedule.

_computeSchedule

protected mocgraph.sched.ScheduleElement _computeSchedule(SDFGraph graph,
                                                          int graphRepetitions)

Compute the schedule for the given SDF graph. The method handles the special case of one-node graph.

Parameters:

graph - The given graph.

graphRepetitions - Repetitions for the given graph.

Returns:

The result Ptolemy schedule.

_cycleBreaking

protected java.util.Collection _cycleBreaking(SDFGraph graph)

Cycle breaking rule for the graph. The candidate edges to remove to break cycles are return as a collection. However, these edges are not actually removed from graph. To remove edges, please use _removeEdges(SDFGraph, Collection).

The implementation here is to select the edge with largest normalized delays (delay / TNSE). However, users can redefine this method.

Parameters:

graph - The given SDFGraph to break cycles.

Returns:

The collection of edges to remove to break cycles.

_isTight

protected boolean _isTight(SDFGraph graph)

Test the graph's tight inter-dependency.

Returns:

True if the graph is tightly interdependent.

_putBackEdges

protected void _putBackEdges(SDFGraph graph)

Edges to put back into graph. This method is usually executed before tight scheduling.

Parameters:

graph - The given SDFGraph.

edges - The edges to put back.

_removeEdges

protected void _removeEdges(SDFGraph graph,
                            java.util.Collection edgeCollection)

Remove edges from the given graph. The removed edges are kept in _removedEdgesMap for possibe future putting back.

Parameters:

graph - The given SDFGraph.

edgeCollection - The edges to remove.

_tightScheduling

protected mocgraph.sched.ScheduleElement _tightScheduling(SDFGraph graph,
                                                          int graphRepetitions)

Tight scheduling for the given graph. The method assumes an input graph with at least 2 nodes.

FIXME: There is no implementation so far and users should define this method.

Parameters:

graph - The given SDFGraph.

graphRepetitions - Repetitions for the given graph.

Returns:

The tight schedule.