mapss.dif.csdf.sdf.sched
Class ProcedureStrategy

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

All Implemented Interfaces:

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

public class ProcedureStrategy
extends DIFScheduleStrategy

A recursive procedure implementation. This is a generalized version of two-node graph scheduler (See TwoNodeStrategy). SDF graphs usually can be clustered in a hierarchical way so that each level has exactly two nodes (super or basic). Such schedules are also termed R-schedule (Regular Schedule). Two-node graph scheduling techniques can be then applied to each level for buffer cost optimization.

ABMLBDPPOStrategy provides a good R-schedule choice for procedural implementation. ABMLBDPPOStrategy is a DPPO scheduling technique using ABMLB as the optimization criterion.

Version:

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

Author:

Mingyung Ko

Field Summary

Fields inherited from class mapss.dif.DIFScheduleStrategy

_clusterManager

Constructor Summary

ProcedureStrategy(SDFGraph graph)
Constructor with a given graph.

ProcedureStrategy(SDFGraph graph, mocgraph.sched.Schedule rSchedule)
Constructor with a given graph and a valid R-schedule.

Method Summary

ProcedureSynthesis	getProcedureSynthesis() Get the procedure synthesis results in ProcedureSynthesis.
int	hierarchicalABMLB() Compute ABMLB for edges in all hierarchical level of the associated R-Schedule.
static int	hierarchicalABMLB(mocgraph.sched.ScheduleElement rScheduleElement, SDFGraph graph) Compute ABMLB for edges in all hierarchical level of an R-Schedule.
int	procedureCount() Get the number of procedures.
mocgraph.sched.Schedule	schedule() Construct the recursive procedural implementation schedule.
java.lang.String	toString() A desrciption of the scheduler.
java.util.Collection	uniformEdges() Get the uniform edges from the associated R-schedule.
static java.util.Collection	uniformEdges(mocgraph.sched.ScheduleElement rScheduleElement, SDFGraph graph) Get the uniform edges from an R-schedule element and the associated SDF graph.

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

Constructor Detail

ProcedureStrategy

public ProcedureStrategy(SDFGraph graph)

Constructor with a given graph. The default R-schedule is set to that generated by ABMLBDPPOStrategy with APGANStrategy lexical order.

Parameters:

graph - The given SDF graph.

ProcedureStrategy

public ProcedureStrategy(SDFGraph graph,
                         mocgraph.sched.Schedule rSchedule)

Constructor with a given graph and a valid R-schedule.

Parameters:

graph - The given SDF graph.

rSchedule - An R-schedule.

Method Detail

getProcedureSynthesis

public ProcedureSynthesis getProcedureSynthesis()

Get the procedure synthesis results in ProcedureSynthesis. Specifically, it is a CompactProcedureSynthesis that is returned.

For example, given a schedule (2 A B) (3 C (5 D (A B))), the following 4 procedures will be synthesized:
p0 = (2 p1) (3 p2)
p1 = (A B)
p2 = (C (5 p3))
p3 = (D p1)
Please note that p1 is called in two places, p0 and p3.

Returns:

The procedure synthesis results.

See Also:

also {@link ProcedureSynthesis}.

hierarchicalABMLB

public int hierarchicalABMLB()

Compute ABMLB for edges in all hierarchical level of the associated R-Schedule. The result is an ideal ABMLB bound rather than actual buffer cost.

Returns:

The hierarchical ABMLB bound.

hierarchicalABMLB

public static int hierarchicalABMLB(mocgraph.sched.ScheduleElement rScheduleElement,
                                    SDFGraph graph)

Compute ABMLB for edges in all hierarchical level of an R-Schedule. The result is an ideal ABMLB bound rather than actual buffer cost.

Parameters:

rScheduleElement - The R-Schedule.

graph - The SDF graph.

Returns:

The hierarchical ABMLB bound.

procedureCount

public int procedureCount()

Get the number of procedures. The count indicates the required number of static procedure instantiations in the synthesis, rather than the dynamic invocations.

Returns:

The number of procedures.

schedule

public mocgraph.sched.Schedule schedule()

Construct the recursive procedural implementation schedule.

Specified by:

schedule in interface mocgraph.sched.ScheduleAnalyzer

Overrides:

schedule in class DIFScheduleStrategy

Returns:

The recursive procedure schedule.

uniformEdges

public java.util.Collection uniformEdges()

Get the uniform edges from the associated R-schedule. Uniform edges are edges with token production and consumption rates multiple one another. Uniformaty degrades the performance of procedural implementation.

Returns:

The uniform edges.

uniformEdges

public static java.util.Collection uniformEdges(mocgraph.sched.ScheduleElement rScheduleElement,
                                                SDFGraph graph)

Get the uniform edges from an R-schedule element and the associated SDF graph. Uniform edges are edges with token production and consumption rates multiple one another. Uniformaty degrades the performance of procedural implementation.

The SDF graph is the original (flattened) graph, not an induced subgraph from some node cluster.

Parameters:

rScheduleElement - The R-schedule element to get uniform edges.

graph - The original (flattened) SDF graph associated with the schedule element.

Returns:

The collection of uniform edges.

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.