ptolemy.domains.sdf.kernel
Class SDFScheduler

java.lang.Object
  extended byptolemy.kernel.util.NamedObj
      extended byptolemy.kernel.util.Attribute
          extended byptolemy.actor.sched.Scheduler
              extended byptolemy.domains.sdf.kernel.BaseSDFScheduler
                  extended byptolemy.domains.sdf.kernel.SDFScheduler
All Implemented Interfaces:
ptolemy.kernel.util.Changeable, java.lang.Cloneable, ptolemy.kernel.util.Debuggable, ptolemy.kernel.util.DebugListener, ptolemy.kernel.util.Derivable, ptolemy.kernel.util.ModelErrorHandler, ptolemy.kernel.util.MoMLExportable, ptolemy.kernel.util.Nameable, java.io.Serializable, ptolemy.kernel.util.ValueListener

public class SDFScheduler
extends BaseSDFScheduler
implements ptolemy.kernel.util.ValueListener

A scheduler that implements basic scheduling of SDF graphs. This class calculates the SDF schedule in two phases. First, the balance equations for the rates between actors are solved to determine the firing vector (also known as the repetitions vector). The firing vector is the least integer solution such that the number of tokens created on each channel of each relation is equal to the number of tokens consumed. In some cases, no solution exists. Such graphs are not executable under SDF.

Then the actors are ordered such that each actor only fires when the scheduler has determined that enough tokens will be present on its input ports to allow it to fire. In cases where the dataflow graph is cyclic, a valid firing vector exists, but no actor can fire, since they all depend on the output of another actor. This situation is known as deadlock. Deadlock must be prevented in SDF by manually inserting delay actors, which represent initial tokens on each relation. Such delay actors are responsible for creating tokens during initialization that will prevent deadlock. These actors set the tokenInitProduction parameter of their output ports to represent the number of tokens they will create during initialization. The SDFScheduler uses this parameter to break the dependency in a cyclic graph.

Note that this scheduler only ensures that the number of firings is minimal. Most notably, it does not attempt to minimize the size of the buffers that are associated with each relation. The resulting schedule is a linear schedule (as opposed to a looped schedule) and is not suitable for multiprocessing environments.

Any actors may be scheduled by this scheduler, which will, by default, assume homogeneous behavior for each actor. (i.e. each output port produces one token for each firing, and each input port consumes one token on each firing, and no tokens are created during initialization.) If this is not the case then parameters named tokenConsumptionRate, tokenProductionRate, and tokenInitProduction must be set. The SDFIOPort class provides easier access to these parameters.

Note that reconstructing the schedule is expensive, so the schedule is locally cached for as long as possible, and mutations under SDF should be avoided.

Note that this scheduler supports actors with 0-rate ports as long as the graph is not equivalent to a disconnected graph. This scheduler is somewhat conservative in this respect.

Disconnected graphs are supported if the SDF Director parameter allowDisconnectedGraphs is true.

Since:
Ptolemy II 0.2
Version:
$Id: SDFScheduler.java,v 1.178 2004/04/13 19:05:17 cxh Exp $
Author:
Stephen Neuendorffer and Brian Vogel
See Also:
Scheduler, SDFIOPort, SampleDelay, Serialized Form
Accepted Rating:
Green (neuendor)
Proposed Rating:
Green (neuendor)

Nested Class Summary
 
Nested classes inherited from class ptolemy.kernel.util.NamedObj
ptolemy.kernel.util.NamedObj.ContainedObjectsIterator
 
Field Summary
 
Fields inherited from class ptolemy.domains.sdf.kernel.BaseSDFScheduler
VERBOSE
 
Fields inherited from class ptolemy.actor.sched.Scheduler
_DEFAULT_SCHEDULER_NAME
 
Fields inherited from class ptolemy.kernel.util.NamedObj
_changeListeners, _changeLock, _changeRequests, _debugging, _debugListeners, _elementName, _isPersistent, _workspace, ATTRIBUTES, CLASSNAME, COMPLETE, CONTENTS, DEEP, FULLNAME, LINKS
 
Constructor Summary
SDFScheduler()
          Construct a scheduler with no container(director) in the default workspace, the name of the scheduler is "Scheduler".
SDFScheduler(ptolemy.actor.Director container, java.lang.String name)
          Construct a scheduler in the given container with the given name.
SDFScheduler(ptolemy.kernel.util.Workspace workspace)
          Construct a scheduler in the given workspace with the name "Scheduler".
 
Method Summary
protected  void _checkDynamicRateVariables(ptolemy.actor.CompositeActor model, java.util.List rateVariables)
           
protected  ptolemy.actor.sched.Schedule _getSchedule()
          Return the scheduling sequence.
protected  void _localMemberInitialize()
          Initialize the local data members of this object.
protected  void _normalizeFirings(int vectorizationFactor, java.util.Map entityToFiringsPerIteration, java.util.Map externalRates)
          Normalize fractional firing ratios into a firing vector that corresponds to a single SDF iteration.
protected  java.util.Map _solveBalanceEquations(ptolemy.actor.CompositeActor container, java.util.List actorList, java.util.Map externalRates)
          Solve the balance equations for the list of connected Actors.
 void declareRateDependency()
          Declare the rate dependency on any external ports of the model.
 java.util.Map getExternalRates()
          Get the external port rates.
 int getFiringCount(ptolemy.kernel.Entity entity)
          Create the schedule.
 void setContainerRates(java.util.Map externalRates)
          This method simply calls _saveContainerRates(Map externalRates).
 void valueChanged(ptolemy.kernel.util.Settable settable)
          React to the fact that the specified Settable has changed.
 
Methods inherited from class ptolemy.domains.sdf.kernel.BaseSDFScheduler
_declareDependency, _getChannel, _saveBufferSizes, _saveContainerRates, _saveFiringCounts
 
Methods inherited from class ptolemy.actor.sched.Scheduler
clone, getSchedule, isValid, setContainer, setValid
 
Methods inherited from class ptolemy.kernel.util.Attribute
_getContainedObject, _propagateExistence, getContainer, setName
 
Methods inherited from class ptolemy.kernel.util.NamedObj
_addAttribute, _attachText, _cloneFixAttributeFields, _debug, _debug, _debug, _debug, _debug, _description, _exportMoMLContents, _getIndentPrefix, _isMoMLSuppressed, _markContentsDerived, _propagateValue, _removeAttribute, _splitName, _stripNumericSuffix, addChangeListener, addDebugListener, attributeChanged, attributeList, attributeList, attributeTypeChanged, clone, containedObjectsIterator, deepContains, depthInHierarchy, description, description, event, executeChangeRequests, exportMoML, exportMoML, exportMoML, exportMoML, exportMoML, getAttribute, getAttribute, getAttributes, getChangeListeners, getClassName, getDerivedLevel, getDerivedList, getElementName, getFullName, getModelErrorHandler, getName, getName, getPrototypeList, getSource, handleModelError, isDeferringChangeRequests, isOverridden, isPersistent, message, propagateExistence, propagateValue, propagateValues, removeChangeListener, removeDebugListener, requestChange, setClassName, setDeferringChangeRequests, setDerivedLevel, setModelErrorHandler, setPersistent, setSource, toplevel, toString, uniqueName, validateSettables, workspace
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

SDFScheduler

public SDFScheduler()
Construct a scheduler with no container(director) in the default workspace, the name of the scheduler is "Scheduler".


SDFScheduler

public SDFScheduler(ptolemy.kernel.util.Workspace workspace)
Construct a scheduler in the given workspace with the name "Scheduler". If the workspace argument is null, use the default workspace. The scheduler is added to the list of objects in the workspace. Increment the version number of the workspace.

Parameters:
workspace - Object for synchronization and version tracking.

SDFScheduler

public SDFScheduler(ptolemy.actor.Director container,
                    java.lang.String name)
             throws ptolemy.kernel.util.IllegalActionException,
                    ptolemy.kernel.util.NameDuplicationException
Construct a scheduler in the given container with the given name. The container argument must not be null, or a NullPointerException will be thrown. This attribute will use the workspace of the container for synchronization and version counts. If the name argument is null, then the name is set to the empty string. Increment the version of the workspace.

Parameters:
container - The container.
name - The name of this attribute.
Throws:
ptolemy.kernel.util.IllegalActionException - If the attribute is not of an acceptable class for the container, or if the name contains a period.
ptolemy.kernel.util.NameDuplicationException - If the name coincides with an attribute already in the container.
Method Detail

declareRateDependency

public void declareRateDependency()
                           throws ptolemy.kernel.util.IllegalActionException
Declare the rate dependency on any external ports of the model. SDF directors should invoke this method once during preinitialize.

Specified by:
declareRateDependency in class BaseSDFScheduler
Throws:
ptolemy.kernel.util.IllegalActionException

getExternalRates

public java.util.Map getExternalRates()
Get the external port rates.


getFiringCount

public int getFiringCount(ptolemy.kernel.Entity entity)
                   throws ptolemy.kernel.util.IllegalActionException
Create the schedule. Return the number of times that the given entity will fire in a single iteration of the system.

Throws:
ptolemy.kernel.util.IllegalActionException

setContainerRates

public void setContainerRates(java.util.Map externalRates)
                       throws ptolemy.actor.sched.NotSchedulableException,
                              ptolemy.kernel.util.IllegalActionException
This method simply calls _saveContainerRates(Map externalRates). It is used in HDF when a cached schedule is used instead of computing a new schedule.

Parameters:
externalRates - A map from external port to the rate of that port.
Throws:
ptolemy.actor.sched.NotSchedulableException - If an external port is both an input and an output, or neither an input or an output, or connected on the inside to ports that have different tokenInitProduction.
ptolemy.kernel.util.IllegalActionException - If any called method throws it.

valueChanged

public void valueChanged(ptolemy.kernel.util.Settable settable)
React to the fact that the specified Settable has changed. This class removes itself as a value listener from all rate parameters, and invalidates the schedule.

Specified by:
valueChanged in interface ptolemy.kernel.util.ValueListener
Parameters:
settable - The object that has changed value.

_getSchedule

protected ptolemy.actor.sched.Schedule _getSchedule()
                                             throws ptolemy.actor.sched.NotSchedulableException,
                                                    ptolemy.kernel.util.IllegalActionException
Return the scheduling sequence. An exception will be thrown if the graph is not schedulable. This occurs in the following circumstances:

Returns:
A schedule of the deeply contained opaque entities in the firing order.
Throws:
ptolemy.actor.sched.NotSchedulableException - If the rates specified for the model imply that the model is not statically schedulable.
ptolemy.kernel.util.IllegalActionException - If the rate parameters of the model are not correct, or the computed rates for external ports are not correct.

_localMemberInitialize

protected void _localMemberInitialize()
Initialize the local data members of this object.


_normalizeFirings

protected void _normalizeFirings(int vectorizationFactor,
                                 java.util.Map entityToFiringsPerIteration,
                                 java.util.Map externalRates)
Normalize fractional firing ratios into a firing vector that corresponds to a single SDF iteration. Multiply all of the fractions by the least common multiple (LCM) of their denominators and by the given vectorizationFactor. This factor is normally the integer value of the vectorizationFactor parameter of the director. Also multiply the production and consumption rates of the external ports of the model by the same amount.

Parameters:
vectorizationFactor - An integer scaling factor to multiply the firing vector by.
entityToFiringsPerIteration - Map of firing ratios to be normalized.
externalRates - Map of token production rates that will be scaled along with the entityToFiringsPerIteration map.
Throws:
ptolemy.kernel.util.InternalErrorException - If the calculated LCM does not normalize all of the fractions.

_solveBalanceEquations

protected java.util.Map _solveBalanceEquations(ptolemy.actor.CompositeActor container,
                                               java.util.List actorList,
                                               java.util.Map externalRates)
                                        throws ptolemy.actor.sched.NotSchedulableException,
                                               ptolemy.kernel.util.IllegalActionException
Solve the balance equations for the list of connected Actors. For each actor, determine the ratio that determines the rate at which it should fire relative to the other actors for the graph to be live and operate within bounded memory. This ratio is known as the fractional firing of the actor.

Parameters:
container - The container that is being scheduled.
actorList - The actors that we are interested in.
externalRates - A map from external ports of container to the fractional rates of that port. This starts out initialized with Fraction.ZERO and will be populated during this method.
Returns:
A map from each actor to its fractional firing.
Throws:
ptolemy.actor.sched.NotSchedulableException - If the graph is not consistent under the synchronous dataflow model, or if the graph is not connected.
ptolemy.kernel.util.IllegalActionException - If any called method throws it.

_checkDynamicRateVariables

protected void _checkDynamicRateVariables(ptolemy.actor.CompositeActor model,
                                          java.util.List rateVariables)
                                   throws ptolemy.kernel.util.IllegalActionException
Throws:
ptolemy.kernel.util.IllegalActionException