ptolemy.actor.util
Class CausalityInterfaceForComposites

java.lang.Object
  ptolemy.actor.util.DefaultCausalityInterface
      ptolemy.actor.util.CausalityInterfaceForComposites

All Implemented Interfaces:

CausalityInterface

Direct Known Subclasses:

EnabledComposite.CausalityInterfaceForEnabledComposite, FSMCausalityInterface, FSMCausalityInterface, MirrorCausalityInterface, MirrorCausalityInterface, TDLCausalityInterface

public class CausalityInterfaceForComposites
extends DefaultCausalityInterface

This class elaborates its base class by providing an algorithm for inferring the causality interface of a composite actor from the causality interfaces of its component actors and their interconnection topology.

Since:

Ptolemy II 8.0

Version:

$Id: CausalityInterfaceForComposites.java 57044 2010-01-27 22:41:05Z cxh $

Author:

Edward A. Lee

Accepted Rating:

Red (eal)

Proposed Rating:

Yellow (eal)

Nested Class Summary

private class

CausalityInterfaceForComposites.ActorComparator Comparator used to sort the actors.

Field Summary

protected long	_actorDepthVersion Workspace version when actor depth was last computed.
protected java.util.Map<Actor,java.lang.Integer>	_actorToDepth A table giving the depths of actors.
protected long	_dependencyVersion The workspace version where the dependency was last updated.
protected java.util.Map<IOPort,java.util.Collection<IOPort>>	_equivalenceClasses Computed equivalence classes of input ports.
protected java.util.Map<IOPort,java.util.Map<IOPort,Dependency>>	_forwardDependencies Computed dependencies between input ports and output ports of the associated actor.
private java.util.Map<IOPort,java.lang.Integer>	_portToDepth A table giving the depths of ports.
protected java.util.Map<IOPort,java.util.Map<IOPort,Dependency>>	_reverseDependencies Computed reverse dependencies (the key is now an output port).

Fields inherited from class ptolemy.actor.util.DefaultCausalityInterface

_actor, _backwardPrunedDependencies, _defaultDependency, _delayDependencies, _EMPTY_COLLECTION, _forwardPrunedDependencies

Constructor Summary

CausalityInterfaceForComposites(Actor actor, Dependency defaultDependency)
Construct a causality interface for the specified actor.

Method Summary

protected void	_computeActorDepth() Compute the depth of ports and actors.
private void	_computeInputDepth(IOPort inputPort, java.util.Set<IOPort> visitedInputs, java.util.Set<IOPort> visitedOutputs) Compute the depth of the specified input port.
private void	_computeOutputPortDepth(IOPort outputPort, java.util.Set<IOPort> visitedInputs, java.util.Set<IOPort> visitedOutputs) Compute the depth of the specified output port.
private boolean	_recordDependency(IOPort inputPort, IOPort port, java.util.Map<IOPort,Dependency> map, Dependency dependency, java.util.Map<IOPort,java.util.Collection<IOPort>> dependsOnInputsMap) Record a dependency of the specified port on the specified input port in the specified map.
private void	_setDependency(IOPort inputPort, java.util.Map<IOPort,Dependency> map, java.util.Collection<IOPort> portsToProcess, java.util.Map<IOPort,java.util.Collection<IOPort>> dependsOnInputsMap) Set the dependency from the specified inputPort to all ports that are reachable via the portsToProcess ports.
void	checkForCycles() Check the associated composite actor for causality cycles.
java.util.Collection<IOPort>	dependentPorts(IOPort port) Return a collection of the ports in the associated actor that depend on or are depended on by the specified port.
java.lang.String	describeDepths() Return a string that describes the depths of actors and their ports.
java.util.Collection<IOPort>	equivalentPorts(IOPort input) Return a set of the input ports in this actor that are in an equivalence class with the specified input.
Dependency	getDependency(IOPort input, IOPort output) Return the dependency between the specified input port and the specified output port.
int	getDepthOfActor(Actor actor) Return the depth of an actor contained (deeply) by the associated composite actor.
int	getDepthOfPort(IOPort ioPort) Return the depth of a port of the associated actor or an actor contained by it.
void	invalidate() Indicate that the cached causality information is invalid.
void	removeDependency(IOPort inputPort, IOPort outputPort) Remove the dependency that the specified output port has on the specified input port.
java.util.List<Actor>	topologicalSort() Return a list of the actors deeply contained within the associated composite actor sorted by actor depth.

Methods inherited from class ptolemy.actor.util.DefaultCausalityInterface

_growDependencies, declareDelayDependency, getActor, getDefaultDependency, toString

Methods inherited from class java.lang.Object

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

Field Detail

_actorDepthVersion

protected long _actorDepthVersion

Workspace version when actor depth was last computed.

_actorToDepth

protected java.util.Map<Actor,java.lang.Integer> _actorToDepth

A table giving the depths of actors.

_dependencyVersion

protected long _dependencyVersion

The workspace version where the dependency was last updated.

_equivalenceClasses

protected java.util.Map<IOPort,java.util.Collection<IOPort>> _equivalenceClasses

Computed equivalence classes of input ports.

_forwardDependencies

protected java.util.Map<IOPort,java.util.Map<IOPort,Dependency>> _forwardDependencies

Computed dependencies between input ports and output ports of the associated actor.

_reverseDependencies

protected java.util.Map<IOPort,java.util.Map<IOPort,Dependency>> _reverseDependencies

Computed reverse dependencies (the key is now an output port).

_portToDepth

private java.util.Map<IOPort,java.lang.Integer> _portToDepth

A table giving the depths of ports.

Constructor Detail

CausalityInterfaceForComposites

public CausalityInterfaceForComposites(Actor actor,
                                       Dependency defaultDependency)
                                throws java.lang.IllegalArgumentException

Construct a causality interface for the specified actor.

Parameters:

actor - The actor for which this is a causality interface. This is required to be an instance of CompositeEntity.

defaultDependency - The default dependency of an output port on an input port.

Throws:

java.lang.IllegalArgumentException - If the actor parameter is not an instance of CompositeEntity.

Method Detail

checkForCycles

public void checkForCycles()
                    throws IllegalActionException

Check the associated composite actor for causality cycles. If a cycle is found, throw an exception. This method has as a side effect computing the depths of actors and ports within the composite, so subsequent queries for those depths will be low cost.

Throws:

IllegalActionException - If a cycle is found.

dependentPorts

public java.util.Collection<IOPort> dependentPorts(IOPort port)
                                            throws IllegalActionException

Return a collection of the ports in the associated actor that depend on or are depended on by the specified port. A port X depends on a port Y if X is an output and Y is an input and getDependency(X,Y) returns oTimesIdentity() of the default dependency specified in the constructor.

This class presumes (but does not check) that the argument is a port contained by the associated actor. If the actor is an input, then it returns a collection of all the outputs. If the actor is output, then it returns a collection of all the inputs.

Derived classes may override this, but they may need to also override getDependency(IOPort, IOPort) and equivalentPorts(IOPort) to be consistent.

Specified by:

dependentPorts in interface CausalityInterface

Overrides:

dependentPorts in class DefaultCausalityInterface

Parameters:

port - The port to find the dependents of.

Returns:

a collection of ports that depend on or are depended on by the specified port.

Throws:

IllegalActionException - Not thrown in this base class.

describeDepths

public java.lang.String describeDepths()
                                throws IllegalActionException

Return a string that describes the depths of actors and their ports.

Returns:

s string that describes the depths of actors and their ports.

Throws:

IllegalActionException - If there is a causality loop.

See Also:

getDepthOfActor(Actor), getDepthOfPort(IOPort)

equivalentPorts

public java.util.Collection<IOPort> equivalentPorts(IOPort input)
                                             throws IllegalActionException

Return a set of the input ports in this actor that are in an equivalence class with the specified input. The returned result includes the specified input port.

An equivalence class is defined as follows. If input ports X and Y each have a dependency equal to oTimesIdentity() on any common port or on two equivalent ports or on the state of the associated actor, then they are in an equivalence class. That is, there is a causal dependency. They are also in the same equivalence class if there is a port Z in an equivalence class with X and in an equivalence class with Y. Moreover, if the actor has any instance of ParameterPort among its input ports, then all input ports are in an equivalence class. Otherwise, they are not in the same equivalence class. In this base class, we assume the actor has no state and return the equivalence classes determined only by the common dependence of output ports.

Specified by:

equivalentPorts in interface CausalityInterface

Overrides:

equivalentPorts in class DefaultCausalityInterface

Parameters:

input - The port to find the equivalence class of.

Returns:

set of the input ports in this actor that are in an equivalence class with the specified input.

Throws:

IllegalActionException - If the argument is not contained by the associated actor.

getDependency

public Dependency getDependency(IOPort input,
                                IOPort output)
                         throws IllegalActionException

Return the dependency between the specified input port and the specified output port. This is done by traversing the network of actors from the input ports. For each output port reachable from an input port, its dependency on the input port is determined by composing the dependencies along all paths from the input port to the output port using oPlus() and oTimes() operators of the dependencies. For any output port that is not reachable from an input port, the dependency on that input port is set to the oPlusIdentity() of the default dependency given in the constructor.

When called for the first time since a change in the model structure, this method performs the complete analysis of the graph and caches the result. Subsequent calls just look up the result. Note that the complete analysis can be quite expensive. For each input port, it traverses the graph to find all ports reachable from that input port, and tracks the dependencies. In the worst case, the complexity can be N*M^2, where N is the number of input ports and M is the total number of ports in the composite (including the ports of all contained actors). The algorithm used, however, is optimized for typical Ptolemy II models, so in most cases the algorithm completes in time on the order of N*D, where D is the length of the longest chain of ports from an input port to an output port.

Specified by:

getDependency in interface CausalityInterface

Overrides:

getDependency in class DefaultCausalityInterface

Parameters:

input - The input port.

output - The output port, or null to update the dependencies (and record equivalence classes) without requiring there to be an output port.

Returns:

The dependency between the specified input port and the specified output port, or null if a null output is port specified.

Throws:

IllegalActionException - Not thrown in this base class.

getDepthOfActor

public int getDepthOfActor(Actor actor)
                    throws IllegalActionException

Return the depth of an actor contained (deeply) by the associated composite actor. The depth of an actor is the minimum depth of the output ports. If there are no output ports, then the depth of the actor it is the maximum depth of the input ports. If there are no input ports or output ports, the depth is zero.

Parameters:

actor - An actor whose depth is requested.

Returns:

An integer indicating the depth of the given actor.

Throws:

IllegalActionException - If the actor is not within the associated actor.

See Also:

getDepthOfPort(IOPort)

getDepthOfPort

public int getDepthOfPort(IOPort ioPort)
                   throws IllegalActionException

Return the depth of a port of the associated actor or an actor contained by it. The depth of an output port is the maximum of the depth of all the input ports it directly depends on, or zero if there are no such input ports. The depth of an input port is maximum of the "source depths" of all the input ports in the same equivalence class with the specified port. The "source depth" of an input port is one plus the maximum depth of all output ports that directly source data to it, or zero if there are no such ports.

Parameters:

ioPort - A port whose depth is requested.

Returns:

An integer representing the depth of the specified ioPort.

Throws:

IllegalActionException - If the ioPort does not have a depth (this should not occur if the ioPort is under the control of this director).

See Also:

getDepthOfActor(Actor)

invalidate

public void invalidate()

Indicate that the cached causality information is invalid.

removeDependency

public void removeDependency(IOPort inputPort,
                             IOPort outputPort)

Remove the dependency that the specified output port has on the specified input port. Specifically, calling this method ensures that subsequent calls to getDependency(inputPort, outputPort) will return defaultDependency.oPlusIdentity(). It also adjusts what is returned by equivalentPorts(IOPort) and dependentPorts(IOPort).

Specified by:

removeDependency in interface CausalityInterface

Overrides:

removeDependency in class DefaultCausalityInterface

Parameters:

inputPort - The input port.

outputPort - The output port that does not depend on the input port.

See Also:

getDependency(IOPort, IOPort)

topologicalSort

public java.util.List<Actor> topologicalSort()
                                      throws IllegalActionException

Return a list of the actors deeply contained within the associated composite actor sorted by actor depth. For actors that have the same depth, the ordering is the order returned by CompositeEntity.deepEntityList(). This method always creates a new list.

Returns:

A sorted list of actors.

Throws:

IllegalActionException - If a cycle is found.

_computeActorDepth

protected void _computeActorDepth()
                           throws IllegalActionException

Compute the depth of ports and actors. The actor depth is typically used to prioritize firings in response to pure events (fireAt() calls). The port depth is used to prioritize firings due to input events. Lower depths translate into higher priorities, with the lowest value being zero. The depth of an actor is the minimum depth of the output ports. This typically causes the actor to fire as early as possible to produce an output on those output ports in response to a pure event, but no earlier than the firings of actors that may source it data that the firing may depend on. If there are no output ports, then the depth of the actor it is the maximum depth of the input ports. This typically delays the response to fireAt() until all input events with the same tag have arrived. If there are no input ports or output ports, the depth is zero.

Throws:

IllegalActionException - If a zero-delay loop is found.

_computeInputDepth

private void _computeInputDepth(IOPort inputPort,
                                java.util.Set<IOPort> visitedInputs,
                                java.util.Set<IOPort> visitedOutputs)
                         throws IllegalActionException

Compute the depth of the specified input port. The depth of an input port is maximum of the "source depths" of all the input ports in the same equivalence class with the specified port. An equivalence class is defined as follows. If ports X and Y each have a dependency not equal to the default depenency's oPlusIdentity(), then they are in an equivalence class. That is, there is a causal dependency. They are also in the same equivalence class if there is a port Z in an equivalence class with X and in an equivalence class with Y. Otherwise, they are not in the same equivalence class. If there are no output ports, then all the input ports are in a single equivalence class.

The "source depth" of an input port is one plus the maximum depth of all output ports that directly source data to it, or zero if there are no such ports. This delays the firing of this actor until all source actors have fired. As a side effect, this method also sets the depth of all the input ports in the same equivalence class, as well as all upstream ports up to a break with non-causal relationship. It also detects and reports dependency cycles. The entry point to this method is _computeActorDepth().

Parameters:

inputPort - The port to compute the depth of.

visitedInputs - The set of input ports that have been visited in this round.

visitedOutputs - The set of output ports that have been visited in this round.

Throws:

IllegalActionException - If a zero-delay loop is found.

See Also:

_computeActorDepth()

_computeOutputPortDepth

private void _computeOutputPortDepth(IOPort outputPort,
                                     java.util.Set<IOPort> visitedInputs,
                                     java.util.Set<IOPort> visitedOutputs)
                              throws IllegalActionException

Compute the depth of the specified output port. The depth of an output port is the maximum of the depth of all the input ports it directly depends on, or zero if there are no such input ports. The entry point to this method is _computeActorDepth().

Parameters:

outputPort - The actor to compute the depth of.

visitedInputs - The set of input ports that have been visited in this round.

visitedOutputs - The set of output ports that have been visited in this round.

Throws:

IllegalActionException - If a zero-delay loop is found.

See Also:

_computeActorDepth()

_recordDependency

private boolean _recordDependency(IOPort inputPort,
                                  IOPort port,
                                  java.util.Map<IOPort,Dependency> map,
                                  Dependency dependency,
                                  java.util.Map<IOPort,java.util.Collection<IOPort>> dependsOnInputsMap)
                           throws IllegalActionException

Record a dependency of the specified port on the specified input port in the specified map. The map records all the dependencies for this particular input port. If there was a prior dependency already that was less than this one, then update the dependency using its oPlus() method. If the dependency is equal to the oPlusIdentity(), then do not record it and return false. Return true if the dependency was newly set or modified from a previously recorded dependency. Return false if no change was made to a previous dependency.

Parameters:

inputPort - The source port.

port - The destination port, which may be an output port of the associated actor, or any port in a contained actor.

map - The map in which to record the dependency.

dependency - The dependency map for ports reachable from the input port.

dependsOnInputsMap - The map from ports in the model to input ports that they depend on, used to construct the equivalence classes.

Returns:

True if the dependency was changed.

Throws:

IllegalActionException

_setDependency

private void _setDependency(IOPort inputPort,
                            java.util.Map<IOPort,Dependency> map,
                            java.util.Collection<IOPort> portsToProcess,
                            java.util.Map<IOPort,java.util.Collection<IOPort>> dependsOnInputsMap)
                     throws IllegalActionException

Set the dependency from the specified inputPort to all ports that are reachable via the portsToProcess ports. The results are stored in the specified map.

Parameters:

inputPort - An input port of this actor.

map - A map of dependencies from this input port to all reachable ports, built by this method. The map is required to contain all ports in portsToProcess on entry.

portsToProcess - Ports connected to the input port directly or indirectly.

dependsOnInputsMap - The map from ports in the model to input ports that they depend on, used to construct the equivalence classes.

Throws:

IllegalActionException - Not thrown in this base class.