mapss.dif.csdf.sdf.sched
Class MBOTopSortStrategy

java.lang.Object
  mocgraph.analysis.strategy.CachedStrategy
      mapss.dif.graph.BaseTopSortStrategy
          mapss.dif.graph.DFSTopSortStrategy
              mapss.dif.csdf.sdf.sched.MBOTopSortStrategy

All Implemented Interfaces:

TopSortAnalyzer, mocgraph.analysis.analyzer.Analyzer, mocgraph.analysis.analyzer.GraphAnalyzer

public class MBOTopSortStrategy
extends DFSTopSortStrategy

A topological sorting algorithm for minimum buffer overlaps. The key points lie in the source nodes selection. We adopt a greedy way to pick sources with minimum output arcs. For the case of identical output arcs, sources with maximum input arcs are picked.

Version:

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

Author:

Mingyung Ko

Field Summary

protected java.util.List

_nodesUpOuts A sorted list of nodes by their increasing output degrees.

Constructor Summary

MBOTopSortStrategy(DIFGraph graph)
Constructor with a DIFGraph.

Method Summary

protected mocgraph.Node	_nextSource(mocgraph.DirectedGraph graph) Return the next source node in determining the top sort.
protected void	_setup() A preliminary step in computing topological sorting.

Methods inherited from class mapss.dif.graph.DFSTopSortStrategy

_compute

Methods inherited from class mapss.dif.graph.BaseTopSortStrategy

_validate, directedGraph, topSort, toString, valid

Methods inherited from class mocgraph.analysis.strategy.CachedStrategy

_convertResult, _result, cachingStatus, disableCaching, enableCaching, getCachedResult, graph, obsolete, reset, setCachedResult

Methods inherited from class java.lang.Object

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

Methods inherited from interface mocgraph.analysis.analyzer.GraphAnalyzer

graph

Field Detail

_nodesUpOuts

protected java.util.List _nodesUpOuts

A sorted list of nodes by their increasing output degrees.

Constructor Detail

MBOTopSortStrategy

public MBOTopSortStrategy(DIFGraph graph)

Constructor with a DIFGraph.

Parameters:

graph - The given SDF graph.

Method Detail

_nextSource

protected mocgraph.Node _nextSource(mocgraph.DirectedGraph graph)

Return the next source node in determining the top sort. This method is supposed to be overriden by specific source selection approach.

Overrides:

_nextSource in class DFSTopSortStrategy

Parameters:

graph - The graph to get the next source node.

Returns:

The next source node.

_setup

protected void _setup()

A preliminary step in computing topological sorting. This is a step executed in DFSTopSortStrategy._compute(). All nodes of the graph are sorted by their increasing output degrees.

Overrides:

_setup in class DFSTopSortStrategy