mapss.dif.csdf.sdf.sched
Class CDPPOStrategy

java.lang.Object
  mapss.dif.csdf.sdf.sched.CDPPOStrategy

public class CDPPOStrategy
extends java.lang.Object

The DPPO for code size optimization. CDPPO is an adapted DPPO approach to minimize code size for arbitrary, not restricted to single appearance, schedules. CDPPO does NOT require an SDF graph as input. The primary input is an schedule, no matter flattened or hierarchicaly looped. Therefore, the input data is potentially large, even in exponential order of the associated SDF graph. For more details about CDPPO, please reference

"Renesting Single Appearance Schedules to Minimize Buffer Memory" by S. S. Bhattacharyya, P. K. Murthy, and E. A. Lee. Memo UCB/ERL M95/43, Electronics Research Lab., UC Berkeley, April 1995.

or

"Multidimensional exploration of software implementations for DSP algorithms" by E. Zitzler, J. Teich, and S. S. Bhattacharyya. Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, pages 83-98, February 2000.

CAUTION: This class does NOT extend DPPOStrategy nor DIFScheduleStrategy.

Version:

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

Author:

Mingyung Ko

Constructor Summary

CDPPOStrategy(java.util.List objectList)
Constructor for an arbitrary list of objects.

CDPPOStrategy(mocgraph.sched.ScheduleElement schedule)
Constructor for a schedule.

CDPPOStrategy(mocgraph.sched.ScheduleElement schedule, java.util.Map actorSizeMap, int loopSize)
Constructor for a given graph, a list of actor firings, map for actors to their code sizes, and code size for loops.

Method Summary

protected boolean	_compareScheduleBody(mocgraph.sched.ScheduleElement s1, mocgraph.sched.ScheduleElement s2) Compare the top-level schedule loops' bodies of two schedules.
protected void	_optimumFor(int i, int j) The optimal results along the elements with index i to j.
protected CDPPOTableElement	_tableElement(int i, int j) Get the element of the CDPPO table.
int	codeSize() Return the optimum code size of the CDPPO computation.
mocgraph.sched.Schedule	schedule() Construct an SDF schedule from the DPPO computation.
java.lang.String	toString() A desrciption of the scheduler.

Methods inherited from class java.lang.Object

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

Constructor Detail

CDPPOStrategy

public CDPPOStrategy(java.util.List objectList)

Constructor for an arbitrary list of objects. In this situation, CDPPO acts as an compression tool for an arbitrary object list. Objects are assumed to have code size of one and loops have zero costs.

Parameters:

objectList - The list of objects.

CDPPOStrategy

public CDPPOStrategy(mocgraph.sched.ScheduleElement schedule)

Constructor for a schedule. Actors have default code size of one and loops have size zero.

Parameters:

actorFirings - The actor firing sequence.

CDPPOStrategy

public CDPPOStrategy(mocgraph.sched.ScheduleElement schedule,
                     java.util.Map actorSizeMap,
                     int loopSize)

Constructor for a given graph, a list of actor firings, map for actors to their code sizes, and code size for loops.

Parameters:

graph - The given SDF graph.

actorFirings - The actor firing sequence.

Method Detail

codeSize

public int codeSize()

Return the optimum code size of the CDPPO computation.

Returns:

The optimum code size.

schedule

public mocgraph.sched.Schedule schedule()

Construct an SDF schedule from the DPPO computation.

Returns:

An SDF schedule.

toString

public java.lang.String toString()

A desrciption of the scheduler.

Overrides:

toString in class java.lang.Object

Returns:

A text description.

_compareScheduleBody

protected boolean _compareScheduleBody(mocgraph.sched.ScheduleElement s1,
                                       mocgraph.sched.ScheduleElement s2)

Compare the top-level schedule loops' bodies of two schedules. The comparison is actor firings based (flattened), not loop structure based (hierarchical). See also DIFScheduleUtilities.compareScheduleByActorFirings( ScheduleElement, ScheduleElement).

Parameters:

s1 - The first schedule.

s2 - The second schedule.

Returns:

True if the loop bodies are equivalent; false otherwise.

_optimumFor

protected 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.

_tableElement

protected CDPPOTableElement _tableElement(int i,
                                          int j)

Get the element of the CDPPO table.

Parameters:

i - The index of the starting (left) node

j - The index of the ending (right) node

Returns:

The desired element.