Package ptolemy.domains.sdf.kernel

Class SDFScheduler

  • All Implemented Interfaces:
    java.lang.Cloneable, Changeable, Debuggable, DebugListener, Derivable, ModelErrorHandler, MoMLExportable, Moveable, Nameable, ValueListener
    Direct Known Subclasses:
    CachedSDFScheduler, DistributedSDFScheduler, OptimizingSDFScheduler, PthalesScheduler, SDFModularScheduler, SDFTestScheduler
    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.

    In addition, an input port may initially have available input tokens. This is indicated by a tokenInitConsumption parameter on the input port.

    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, tokenInitProduction, and tokenInitConsumption 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$
    Author:
    Stephen Neuendorffer and Brian Vogel
    See Also:
    Scheduler, SampleDelay
    Pt.AcceptedRating:
    Green (neuendor)
    Pt.ProposedRating:
    Green (neuendor)

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

      • _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)

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

      • _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.