ptolemy.domains.sdf.kernel
Class SDFScheduler

java.lang.Object
  ptolemy.kernel.util.NamedObj
      ptolemy.kernel.util.Attribute
          ptolemy.actor.sched.Scheduler
              ptolemy.domains.sdf.kernel.BaseSDFScheduler
                  ptolemy.domains.sdf.kernel.SDFScheduler

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, Changeable, Debuggable, DebugListener, Derivable, ModelErrorHandler, MoMLExportable, Moveable, Nameable, ValueListener

Direct Known Subclasses:

CachedSDFScheduler, DistributedSDFScheduler

public class SDFScheduler
extends BaseSDFScheduler
implements 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 57046 2010-01-27 23:35:53Z cxh $

Author:

Stephen Neuendorffer and Brian Vogel

See Also:

Scheduler, SampleDelay, Serialized Form

Accepted Rating:

Green (neuendor)

Proposed Rating:

Green (neuendor)

Nested Class Summary

Nested classes/interfaces inherited from class ptolemy.kernel.util.NamedObj

NamedObj.ContainedObjectsIterator

Field Summary

protected java.util.Map	_externalRates Mmaps from external ports to the number of tokens that that port will produce or consume in each firing.
protected java.util.Map	_firingVector A map from actors to an integer representing the number of times the actor will fire.
private Fraction	_minusOne A fraction equal to -1.
protected java.util.List	_rateVariables The list of rate variables that this scheduler is listening to for rate changes.
Parameter	constrainBufferSizes If true, then buffer sizes are fixed according to the schedule, and attempts to write to the buffer that cause the buffer to exceed the schedule size result in an exception.

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, _verbose, _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(Director container, java.lang.String name)
Construct a scheduler in the given container with the given name.

SDFScheduler(Workspace workspace)
Construct a scheduler in the given workspace with the name "Scheduler".

Method Summary

private void	_assertDynamicRateVariable(CompositeActor model, Variable variable, java.util.List rateVariables, ConstVariableModelAnalysis analysis)
private void	_checkDirectInputOutputConnection(CompositeActor container, java.util.Map externalRates) Update the The external rates of those directly connected input and output ports to be 1.
protected void	_checkDynamicRateVariables(CompositeActor model, java.util.List rateVariables) Populate the given set with the dynamic rate variables in the model.
protected int	_computeMaximumFirings(Actor currentActor) Determine the number of times the given actor can fire, based on the number of tokens that are present on its inputs.
protected int	_countUnfulfilledInputs(Actor actor, java.util.List actorList, boolean resetCapacity) Count the number of input ports in the given actor that must be fulfilled before the actor can fire.
protected int	_getFiringCount(Entity entity) Return the number of firings associated with the given entity.
protected Schedule	_getSchedule() Return the scheduling sequence.
private void	_init() Create the parameter constrainBufferSizes and set its default value and type constraints.
private void	_listenToRateVariable(Variable variable, java.util.List rateVariables) Add this scheduler as a value listener to the given variable and add the variable to the given list.
private ComponentEntity	_pickZeroRatePortActor(java.util.List actorList) Search the given list of actors for one that contains at least one port that has zero rate.
private void	_propagatePort(CompositeActor container, IOPort currentPort, java.util.Map entityToFiringsPerIteration, java.util.Map externalRates, java.util.LinkedList remainingActors, java.util.LinkedList pendingActors, java.util.Set clusteredActors, java.util.Set clusteredExternalPorts) Propagate the number of fractional firings decided for this actor through the specified port.
private Schedule	_scheduleConnectedActors(java.util.Map externalRates, java.util.List actorList, CompositeActor container) Create a schedule for a set of actors.
protected void	_simulateExternalInputs(IOPort port, int count, java.util.List actorList, java.util.LinkedList readyToScheduleActorList) Simulate the consumption of tokens from the given external input port.
protected boolean	_simulateInputConsumption(Actor currentActor, int firingCount) Simulate the consumption of tokens by the actor during execution of the given number of firings.
private void	_simulateTokensCreated(IOPort outputPort, int createdTokens, java.util.List actorList, java.util.LinkedList readyToScheduleActorList) Simulate the creation of tokens by the given output port when its actor fires.
protected java.util.Map	_solveBalanceEquations(CompositeActor container, java.util.List actorList, java.util.Map externalRates) Solve the balance equations for the list of connected Actors.
protected void	_vectorizeFirings(int vectorizationFactor, java.util.Map entityToFiringsPerIteration, java.util.Map externalRates) Multiply all of the repetition rates by the given vectorizationFactor.
java.lang.Object	clone(Workspace workspace) Clone the scheduler into the specified workspace.
void	declareRateDependency() Declare the rate dependency on any external ports of the model.
java.util.Map	getExternalRates() Get the external port rates.
int	getFiringCount(Entity entity) Create the schedule.
void	valueChanged(Settable settable) React to the fact that the specified Settable has changed by invalidating the schedule.

Methods inherited from class ptolemy.domains.sdf.kernel.BaseSDFScheduler

_declareDependency, _saveBufferSizes, _saveContainerRates, _saveFiringCounts

Methods inherited from class ptolemy.actor.sched.Scheduler

getSchedule, isValid, setContainer, setValid

Methods inherited from class ptolemy.kernel.util.Attribute

_checkContainer, _getContainedObject, _propagateExistence, getContainer, moveDown, moveToFirst, moveToIndex, moveToLast, moveUp, setName, updateContent

Methods inherited from class ptolemy.kernel.util.NamedObj

_addAttribute, _adjustOverride, _attachText, _cloneFixAttributeFields, _debug, _debug, _debug, _debug, _debug, _description, _exportMoMLContents, _getIndentPrefix, _isMoMLSuppressed, _markContentsDerived, _propagateValue, _recordDecoratedAttributes, _removeAttribute, _splitName, _stripNumericSuffix, _validateSettables, addChangeListener, addDebugListener, attributeChanged, attributeList, attributeList, attributeTypeChanged, clone, containedObjectsIterator, deepContains, depthInHierarchy, description, description, event, executeChangeRequests, exportMoML, exportMoML, exportMoML, exportMoML, exportMoML, exportMoMLPlain, getAttribute, getAttribute, getAttributes, getChangeListeners, getClassName, getDecoratorAttribute, getDecoratorAttributes, getDerivedLevel, getDerivedList, getDisplayName, getElementName, getFullName, getModelErrorHandler, getName, getName, getPrototypeList, getSource, handleModelError, isDeferringChangeRequests, isOverridden, isPersistent, lazyContainedObjectsIterator, message, propagateExistence, propagateValue, propagateValues, removeChangeListener, removeDebugListener, requestChange, setClassName, setDeferringChangeRequests, setDerivedLevel, setDisplayName, setModelErrorHandler, setPersistent, setSource, sortContainedObjects, toplevel, toString, uniqueName, validateSettables, workspace

Methods inherited from class java.lang.Object

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

Field Detail

constrainBufferSizes

public Parameter constrainBufferSizes

If true, then buffer sizes are fixed according to the schedule, and attempts to write to the buffer that cause the buffer to exceed the schedule size result in an exception. This method works by setting the capacity of the receivers if the value is true. This parameter is a boolean that defaults to true.

_firingVector

protected java.util.Map _firingVector

A map from actors to an integer representing the number of times the actor will fire.

_minusOne

private Fraction _minusOne

A fraction equal to -1. Used in several places to indicate an actor for which we have not determined the number of times it will fire.

_externalRates

protected java.util.Map _externalRates

Mmaps from external ports to the number of tokens that that port will produce or consume in each firing. It gets populated with the fractional production ratios and is used in the end to set final rates on external ports.

_rateVariables

protected java.util.List _rateVariables

The list of rate variables that this scheduler is listening to for rate changes.

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(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(Director container,
                    java.lang.String name)
             throws IllegalActionException,
                    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:

IllegalActionException - If the attribute is not of an acceptable class for the container, or if the name contains a period.

NameDuplicationException - If the name coincides with an attribute already in the container.

Method Detail

clone

public java.lang.Object clone(Workspace workspace)
                       throws java.lang.CloneNotSupportedException

Clone the scheduler into the specified workspace. The new object is not added to the directory of that workspace (you must do this yourself if you want it there). The result is a new scheduler with no container, and no valid schedule.

Overrides:

clone in class Scheduler

Parameters:

workspace - The workspace for the cloned object.

Returns:

The new Scheduler.

Throws:

java.lang.CloneNotSupportedException - If one of the attributes cannot be cloned.

See Also:

NamedObj.exportMoML(Writer, int, String), NamedObj.setDeferringChangeRequests(boolean)

declareRateDependency

public void declareRateDependency()
                           throws 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:

IllegalActionException - If there is a problem setting the rate dependency on an external port.

getExternalRates

public java.util.Map getExternalRates()

Get the external port rates.

Returns:

a Map from external ports to the number of tokens that that port will produce or consume in each firing.

getFiringCount

public int getFiringCount(Entity entity)
                   throws IllegalActionException

Create the schedule. Return the number of times that the given entity will fire in a single iteration of the system.

Parameters:

entity - The entity that is being fired.

Returns:

The number of times that the given entity will fire

Throws:

IllegalActionException - If thrown by getSchedule().

valueChanged

public void valueChanged(Settable settable)

React to the fact that the specified Settable has changed by invalidating the schedule.

Specified by:

valueChanged in interface ValueListener

Parameters:

settable - The object that has changed value.

_checkDynamicRateVariables

protected void _checkDynamicRateVariables(CompositeActor model,
                                          java.util.List rateVariables)
                                   throws IllegalActionException

Populate the given set with the dynamic rate variables in the model.

Parameters:

model - The model.

rateVariables - A list of rate variables. Each element is a Variable.

Throws:

IllegalActionException - If throw while looking for dynamic rate parameters.

_computeMaximumFirings

protected int _computeMaximumFirings(Actor currentActor)
                              throws IllegalActionException

Determine the number of times the given actor can fire, based on the number of tokens that are present on its inputs.

Parameters:

currentActor - The actor.

Returns:

The number of times the actor can fire.

Throws:

IllegalActionException - If the rate parameters are invalid.

_countUnfulfilledInputs

protected int _countUnfulfilledInputs(Actor actor,
                                      java.util.List actorList,
                                      boolean resetCapacity)
                               throws IllegalActionException

Count the number of input ports in the given actor that must be fulfilled before the actor can fire. Ports that are connected to actors that we are not scheduling right now are assumed to be fulfilled. Ports that have more tokens waiting on each of their channels than their input consumption rate are also already fulfilled. All other ports are considered to be unfulfilled.

Parameters:

actor - The actor.

actorList - The list of actors that we are scheduling.

resetCapacity - If true, then reset the capacity of each receiver to infinite capacity (do this during initialization).

Returns:

The number of unfulfilled input ports of the given actor.

Throws:

IllegalActionException - If any called method throws it.

_getFiringCount

protected int _getFiringCount(Entity entity)

Return the number of firings associated with the given entity. The number of firings is stored in the _firingVector map, indexed by the entity.

Parameters:

entity - One of the actors we are scheduling.

Returns:

The number of firings.

_getSchedule

protected Schedule _getSchedule()
                         throws NotSchedulableException,
                                IllegalActionException

Return the scheduling sequence. An exception will be thrown if the graph is not schedulable. This occurs in the following circumstances:

• The graph is not a connected graph.
• No integer solution exists for the balance equations.
• The graph contains cycles without delays (deadlock).
• Multiple output ports are connected to the same broadcast relation. (equivalent to a non-deterministic merge)
• The vectorizationFactor parameter of the director does not contain a positive integer.

Overrides:

_getSchedule in class Scheduler

Returns:

A schedule of the deeply contained opaque entities in the firing order.

Throws:

NotSchedulableException - If the rates specified for the model imply that the model is not statically schedulable.

IllegalActionException - If the rate parameters of the model are not correct, or the computed rates for external ports are not correct.

See Also:

CompositeEntity.deepEntityList()

_solveBalanceEquations

protected java.util.Map _solveBalanceEquations(CompositeActor container,
                                               java.util.List actorList,
                                               java.util.Map externalRates)
                                        throws NotSchedulableException,
                                               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. Normalize this ratio into integer, which is the minimum number of firings of the actor to satisfy the balance equations.

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:

NotSchedulableException - If the graph is not consistent under the synchronous dataflow model, or if the graph is not connected.

IllegalActionException - If any called method throws it.

_vectorizeFirings

protected void _vectorizeFirings(int vectorizationFactor,
                                 java.util.Map entityToFiringsPerIteration,
                                 java.util.Map externalRates)

Multiply all of the repetition rates 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. Also, convert the two maps in the arguments to contain Integers rather than Fractions.

Parameters:

vectorizationFactor - An integer scaling factor to multiply the firing vector by.

entityToFiringsPerIteration - Map representing the firing vector.

externalRates - Map representing production rates of external ports.

_assertDynamicRateVariable

private void _assertDynamicRateVariable(CompositeActor model,
                                        Variable variable,
                                        java.util.List rateVariables,
                                        ConstVariableModelAnalysis analysis)
                                 throws IllegalActionException

Throws:

IllegalActionException

_checkDirectInputOutputConnection

private void _checkDirectInputOutputConnection(CompositeActor container,
                                               java.util.Map externalRates)

Update the The external rates of those directly connected input and output ports to be 1. So a direct connection will transfer one token in each execution of the schedule.

Parameters:

container - The container that is being scheduled.

externalRates - A map from external ports of container to the fractional rates of that port. The external rates of those directly connected input and output ports will be updated to be 1 during this method.

_init

private void _init()

Create the parameter constrainBufferSizes and set its default value and type constraints.

_listenToRateVariable

private void _listenToRateVariable(Variable variable,
                                   java.util.List rateVariables)

Add this scheduler as a value listener to the given variable and add the variable to the given list. If the list already includes the variable, or the variable is null, then do nothing.

Parameters:

variable - A variable, which is a rate variable that this scheduler uses for scheduling.

rateVariables - A list of rate variables.

_pickZeroRatePortActor

private ComponentEntity _pickZeroRatePortActor(java.util.List actorList)
                                        throws IllegalActionException

Search the given list of actors for one that contains at least one port that has zero rate.

Parameters:

actorList - The list of all of the actors to search.

Returns:

An actor that contains at least one zero rate port, or null if no actor has a zero rate port.

Throws:

IllegalActionException

_propagatePort

private void _propagatePort(CompositeActor container,
                            IOPort currentPort,
                            java.util.Map entityToFiringsPerIteration,
                            java.util.Map externalRates,
                            java.util.LinkedList remainingActors,
                            java.util.LinkedList pendingActors,
                            java.util.Set clusteredActors,
                            java.util.Set clusteredExternalPorts)
                     throws NotSchedulableException,
                            IllegalActionException

Propagate the number of fractional firings decided for this actor through the specified port. Compute the fractional firing ratio for each actor that is connected to the given port. If we have not previously computed the ratio for an actor, then store the value in the given map of firing ratios and move the actor from the remainingActors list to the pendingActors list. If the value has been previously computed and is not the same, then the model is not schedulable and an exception will be thrown. Note that ports directly contained by the given container are handled slightly differently from other ports. Most importantly, their rates are propagated to ports they are connected to on the inside, as opposed to ports they are connected to on the outside.

Parameters:

container - The actor that is being scheduled.

currentPort - The port that we are propagating from.

entityToFiringsPerIteration - The current Map of fractional firing ratios for each actor. This map will be updated if the ratio for any actor has not been previously computed.

externalRates - A map from external ports of container to the fractional rates of that port. This will be updated during this method.

remainingActors - The set of actors that have not had their fractional firing set. This will be updated during this method.

pendingActors - The set of actors that have had their rate set, but have not been propagated onwards. This will be updated during this method.

clusteredActors - The set of actors that are within one cluster, i.e., they are connected.

clusteredExternalPorts - The set of external ports that are connected with the same cluster of actors.

Throws:

NotSchedulableException - If the model is not schedulable.

IllegalActionException - If the expression for a rate parameter is not valid.

_scheduleConnectedActors

private Schedule _scheduleConnectedActors(java.util.Map externalRates,
                                          java.util.List actorList,
                                          CompositeActor container)
                                   throws NotSchedulableException

Create a schedule for a set of actors. Given a valid firing vector, simulate the scheduling of the actors until the end of one synchronous dataflow iteration. Each actor will appear in the schedule exactly the number of times that minimally solves the balance equations and in an order where each actor has sufficient tokens on its inputs to fire. Note that no claim is made that this is an optimal solution in any other sense.

Parameters:

externalRates - Map from external port to an Integer representing the number of tokens produced or consumed from that port during the course of an iteration.

actorList - The actors that need to be scheduled.

container - The container.

Returns:

An instance of the Schedule class, indicating the order in which actors should fire.

Throws:

NotSchedulableException - If the algorithm encounters an SDF graph that is not consistent with the firing vector, or detects an inconsistent internal state, or detects a graph that cannot be scheduled.

_simulateExternalInputs

protected void _simulateExternalInputs(IOPort port,
                                       int count,
                                       java.util.List actorList,
                                       java.util.LinkedList readyToScheduleActorList)
                                throws IllegalActionException

Simulate the consumption of tokens from the given external input port. This assumes the input ports have the number of tokens given by their rate.

Parameters:

port - The external input port.

count - The number of tokens assumed to be on that port.

actorList - The list of actors.

readyToScheduleActorList - The list of actors that are ready to be scheduled. This will be updated if any actors that receive tokens from outputPort are now ready to fire.

Throws:

IllegalActionException - If thrown while reading a token, setting the capacity of a receiver or counting unfulfilled input.s

_simulateInputConsumption

protected boolean _simulateInputConsumption(Actor currentActor,
                                            int firingCount)
                                     throws IllegalActionException

Simulate the consumption of tokens by the actor during execution of the given number of firings. Also determine whether enough tokens still remain at the inputs of the actor for it to fire again immediately.

Parameters:

currentActor - The actor to be fired.

firingCount - The number of firings.

Returns:

true If the actor can fire again.

Throws:

IllegalActionException - If the rate parameters are invalid.

_simulateTokensCreated

private void _simulateTokensCreated(IOPort outputPort,
                                    int createdTokens,
                                    java.util.List actorList,
                                    java.util.LinkedList readyToScheduleActorList)
                             throws IllegalActionException

Simulate the creation of tokens by the given output port when its actor fires. If any actors that receive tokens are then ready to fire, given that only actors in the actor list are being scheduled, then add those actors to the list of actors that are ready to schedule.

Parameters:

outputPort - The port that is creating the tokens.

createdTokens - The number of tokens to create.

actorList - The list of actors that are being scheduled.

readyToScheduleActorList - The list of actors that are ready to be scheduled. This will be updated if any actors that receive tokens from outputPort are now ready to fire.

Throws:

IllegalActionException