mapss.dif.csdf.sdf.sched
Class APGANStrategy

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

All Implemented Interfaces:

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

public class APGANStrategy
extends DIFScheduleStrategy

Acyclic Pair-wise Grouping of Adjacent Nodes (APGAN) scheduler for SDF graphs. It is described in the book "Software Synthesis from Dataflow Graphs" by Shuvra S. Bhattacharyya, Praveen K. Murthy, and Edward A. Lee, chapter 7.

This program provides a basic APGAN and can be accommodated to arbitrary clustering priority or tie-breaking rules. For the accommodation, #_candidates() or #_tieBreak() are the methods to be overrided.

Version:

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

Author:

Mingyung Ko

Constructor Summary

APGANStrategy(SDFGraph graph)
Constructor of APGAN.

Method Summary

protected java.util.List	_ascendentEdges() Sort the edges in ascendent orders.
protected java.util.List	_descendentEdges() Sort the edges in descendent orders.
protected java.util.List	_prioritizedEdges() A prioritized list of edges.
protected boolean	_testAcyclicClustering(mocgraph.Edge edge) Test acyclic clustering of the adjacent nodes represented by the given edge.
protected int	_tieBreak(mocgraph.Edge edge1, mocgraph.Edge edge2) Impose priorities on edges with same values.
protected int	_valueOf(mocgraph.Edge edge) Value definition for an edge.
mocgraph.sched.Schedule	gdppoSchedule() Get a GDPPO schedule (see GDPPOStrategy) with a lexical order derived by APGAN.
mocgraph.sched.Schedule	schedule() Run APGAN clustering and then expand it to a 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

APGANStrategy

public APGANStrategy(SDFGraph graph)

Constructor of APGAN. APGAN performs clustering and the graph topology will be changed. Therefore, graph cloning is needed and is done here.

Parameters:

graph - The given SDF graph

Method Detail

gdppoSchedule

public mocgraph.sched.Schedule gdppoSchedule()

Get a GDPPO schedule (see GDPPOStrategy) with a lexical order derived by APGAN. In usual, GDPPO is called to post optimize APGAN result. This method provides the integrated function.

Returns:

The GDPPO schedule with APGAN lexical order.

schedule

public mocgraph.sched.Schedule schedule()

Run APGAN clustering and then expand it to a schedule. Arbitrary for #_candidates()

Specified by:

schedule in interface mocgraph.sched.ScheduleAnalyzer

Overrides:

schedule in class DIFScheduleStrategy

Returns:

An empty schedule in the base scheduler.

Throws:

java.lang.RuntimeException - No valid nodes to cluster: error with candidate/tie-break law

_ascendentEdges

protected final java.util.List _ascendentEdges()

Sort the edges in ascendent orders. Edge values are defined by GCD of ending nodes' repetition counts.

Returns:

The ascendent edge list.

_descendentEdges

protected final java.util.List _descendentEdges()

Sort the edges in descendent orders. Edge values are defined by GCD of ending nodes' repetition counts.

Returns:

The descendent edge list.

_prioritizedEdges

protected java.util.List _prioritizedEdges()

A prioritized list of edges. Candidate adjacent nodes are clustered accroding to the list. By default, priority is given to the larger GCD of source and sink nodes' repetition counts.

Returns:

The prioritized edges

_testAcyclicClustering

protected boolean _testAcyclicClustering(mocgraph.Edge edge)

Test acyclic clustering of the adjacent nodes represented by the given edge.

Parameters:

The - edge whose ending nodes are to be clustered.

Returns:

True if the clustering leads to acyclic topology; false otherwise.

_tieBreak

protected int _tieBreak(mocgraph.Edge edge1,
                        mocgraph.Edge edge2)

Impose priorities on edges with same values. See also _valueOf(Edge). In exploring candidate nodes to cluster, these edges sometimes exist. They cause edge sorting ambiguous. A tie breaking rule is usually necessary to evaluate an exact order.

It's positivity or negativity of the returned value that matters. If edge1 is preferrable to edge2, than a negative number is returned. Otherwise, a positive number is returned. By default, the less label number the more preferrable an edge is.

Parameters:

edge1 - The first edge.

edge2 - The second edge.

Returns:

A comparison indicator in sorting.

_valueOf

protected int _valueOf(mocgraph.Edge edge)

Value definition for an edge. The value returned is for sorting purpose. By default, it is defined as GCD of the ending nodes' repetition counts.

Parameters:

edge - The edge to get value.

Returns:

The associated value.