See {@link ptolemy.domains.sdf.optimize.OptimizingSDFDirector}, {@link ptolemy.domains.sdf.optimize.OptimizingSDFScheduler} and {@link ptolemy.domains.sdf.optimize.BufferingProfile} for more information.
@see ptolemy.domains.sdf.optimize.OptimizingSDFDirector @see ptolemy.domains.sdf.optimize.OptimizingSDFScheduler @see ptolemy.domains.sdf.optimize.BufferingProfile @author Marc Geilen @version $Id: OptimalScheduleFinder.java 70402 2014-10-23 00:52:20Z cxh $ @since Ptolemy II 10.0 @Pt.ProposedRating Red (mgeilen) @Pt.AcceptedRating Red () */ public class OptimalScheduleFinder { /** * Construct an instance of the OptimalScheduleFinder. Creates an object * associated with the OptimizingSDFSchedule scheduler and using * the optimization criterion criterion to find an optimized schedule. * @param scheduler scheduler * @param criterion optimization criterion */ public OptimalScheduleFinder(OptimizingSDFScheduler scheduler, OptimizationCriteria criterion) { _myScheduler = scheduler; _optimizationCriterion = criterion; } /** * Make a schedule using a greedy (non-optimizing algorithm). * @param firingVector repetition vector * @return the computed schedule */ public Schedule makeScheduleGreedy(Map firingVector) { Schedule result = null; try { // instantiate the model _instantiateAnalysisModel(firingVector); // determine the state vector indices _setStateIndices(); // run a greedy exploration // keeping toExplore sorted on maximal progress makes it greedy _SortedSetOfStates toExplore = new _SortedSetOfStates( new _StateComparatorMaximumProgress()); // add the initial state toExplore.add(initialState()); // store the end state when found _State optimalEndState = null; // to be set to true as soon as end state is found boolean scheduleFound = false; // continue searching until a schedule has been found while (!scheduleFound && !toExplore.isEmpty()) { // take the first state to further explore from our sorted list _State state = toExplore.removeFirstState(); // test if it is an end state, in which case we are ready. if (state.isEndState()) { // found !! optimalEndState = state; scheduleFound = true; } else { // try all possible actions (actor firings) enabled from this state Iterator actorIterator = _actors.iterator(); while (actorIterator.hasNext()) { // for each actor a ... _Actor actor = (_Actor) actorIterator.next(); // check first if 'actor' is exclusively enabled to give // preference to exclusive firing // (although perhaps we should not be assuming that from the sorted set) if (actor.isExclusiveEnabled(state)) { // it is enabled. Create a new state accordingly _State newState = state.clone(state); // fire the actor actor.fireExclusive(newState); // update the value to be optimized depending on the optimization criterion if (_optimizationCriterion == OptimizationCriteria.BUFFERS) { newState.value = Math.max( _channels.channelSize(newState) + actor.exclusiveBuffers, newState.value); } else if (_optimizationCriterion == OptimizationCriteria.EXECUTIONTIME) { newState.value = state.value + actor.exclusiveExecutionTime; } // add the new state to the list of states to be explored toExplore.add(newState); } // try also firing non-exclusive // check if a is enabled for a shared firing if (actor.isEnabled(state)) { // it is enabled. Create a new state accordingly _State newState = state.clone(state); // fire the actor actor.fire(newState); // update the value to be optimized depending on the optimization criterion if (_optimizationCriterion == OptimizationCriteria.BUFFERS) { newState.value = Math.max( _channels.channelSize(newState) + actor.sharedBuffers, newState.value); } else if (_optimizationCriterion == OptimizationCriteria.EXECUTIONTIME) { newState.value = state.value + actor.sharedExecutionTime; } // add the new state to the list of states to be explored toExplore.add(newState); } } } } // Completed the search. Did we find anything? if (scheduleFound) { // yes, then turn it into a schedule. result = _buildSchedule(optimalEndState); } } catch (IllegalActionException exception) { // oops, something happened... } // return the schedule return result; } /** * Make a schedule using an exhaustive BFS-like optimizing algorithm. * @param firingVector repetition vector * @return the computed schedule */ public Schedule makeSchedule(Map firingVector) { Schedule result = null; try { // instantiate the model _instantiateAnalysisModel(firingVector); // determine the state vector indices _setStateIndices(); // run a state-space exploration // keeping toExplore sorted on memory usage ensures that the minimum memory // schedule is found first. _SortedSetOfStates toExplore = new _SortedSetOfStates(); // add the initial state toExplore.add(initialState()); // store the end state when found _State optimalEndState = null; // to be set to true as soon as end state is found boolean scheduleFound = false; // continue searching until a schedule has been found while (!scheduleFound && !toExplore.isEmpty()) { // take the first state to further explore from our sorted list _State state = toExplore.removeFirstState(); // test if it is an end state, in which case we are ready. if (state.isEndState()) { // found !! optimalEndState = state; scheduleFound = true; } else { // try all possible actions (actor firings) enabled from this state Iterator actorIterator = _actors.iterator(); while (actorIterator.hasNext()) { // for each actor a ... _Actor actor = (_Actor) actorIterator.next(); // check first if a is exclusively enabled to give // preference to exclusive firing // (although perhaps we should not be assuming that from the sorted set) if (actor.isExclusiveEnabled(state)) { // it is enabled. Create a new state accordingly _State newState = state.clone(state); // fire the actor actor.fireExclusive(newState); // update the value to be optimized depending on the optimization criterion if (_optimizationCriterion == OptimizationCriteria.BUFFERS) { newState.value = Math.max( _channels.channelSize(newState) + actor.exclusiveBuffers, newState.value); } else if (_optimizationCriterion == OptimizationCriteria.EXECUTIONTIME) { newState.value = state.value + actor.exclusiveExecutionTime; } // add the new state to the list of states to be explored toExplore.add(newState); } // try also firing non-exclusive // check if a is enabled for a shared firing if (actor.isEnabled(state)) { // it is enabled. Create a new state accordingly _State newState = state.clone(state); // fire the actor actor.fire(newState); // update the value to be optimized depending on the optimization criterion if (_optimizationCriterion == OptimizationCriteria.BUFFERS) { newState.value = Math.max( _channels.channelSize(newState) + actor.sharedBuffers, newState.value); } else if (_optimizationCriterion == OptimizationCriteria.EXECUTIONTIME) { newState.value = state.value + actor.sharedExecutionTime; } // add the new state to the list of states to be explored toExplore.add(newState); } } } } // Completed the search. Did we find anything? if (scheduleFound) { // yes, then turn it into a schedule. result = _buildSchedule(optimalEndState); } } catch (IllegalActionException e) { // oops, something happened... } // return the schedule return result; } /////////////////////////////////////////////////////////////////// //// protected fields //// /** * Instantiate the analysis model from the core model. * @param firingVector contains repetition vector information * @exception IllegalActionException if model information inconsistent */ protected void _instantiateAnalysisModel(Map firingVector) throws IllegalActionException { // initialize lists and maps _actors = new _ListOfActors(); _actorMap = new _TwoWayHashMap(); _channels = new _ListOfChannels(); _channelMap = new _TwoWayHashMap(); // create the actors Iterator actorIterator = firingVector.entrySet().iterator(); while (actorIterator.hasNext()) { int sharedBuffers, exclusiveBuffers, sharedExecutionTime, exclusiveExecutionTime; Map.Entry pair = (Map.Entry) actorIterator.next(); ptolemy.actor.Actor actor = (ptolemy.actor.Actor) pair.getKey(); // if it is an actor which implements our BufferingProfile if (actor instanceof BufferingProfile) { BufferingProfile actorWithBufferingProfile = (BufferingProfile) actor; // set the profile accordingly sharedBuffers = actorWithBufferingProfile.sharedBuffers(); exclusiveBuffers = actorWithBufferingProfile.exclusiveBuffers(); sharedExecutionTime = actorWithBufferingProfile .sharedExecutionTime(); exclusiveExecutionTime = actorWithBufferingProfile .exclusiveExecutionTime(); } else { // set the profile to default values sharedBuffers = 0; exclusiveBuffers = 0; sharedExecutionTime = 0; exclusiveExecutionTime = 0; } // create a model actor _Actor modelActor = new _Actor(actor.getName(), (Integer) pair.getValue(), sharedBuffers, exclusiveBuffers, sharedExecutionTime, exclusiveExecutionTime); // add the actor _actors.add(modelActor); // remember the link to the real actor _actorMap.put(modelActor, actor); // create a channel for every output port List portList = actor.outputPortList(); Iterator portIterator = portList.iterator(); while (portIterator.hasNext()) { TypedIOPort port = (TypedIOPort) portIterator.next(); _Channel channel = new _Channel(); // set the number of initial tokens channel.initialTokens = DFUtilities .getTokenInitProduction(port); // add the channel to the list _channels.add(channel); // remember the link to the IOPort _channelMap.put(port, channel); } } // create the actor ports actorIterator = firingVector.keySet().iterator(); while (actorIterator.hasNext()) { // for every actor... ptolemy.actor.Actor actor = (ptolemy.actor.Actor) actorIterator .next(); _Actor modelActor = (_Actor) _actorMap.getBW(actor); List portList = actor.outputPortList(); Iterator portIterator = portList.iterator(); while (portIterator.hasNext()) { // for every output port of the actor TypedIOPort port = (TypedIOPort) portIterator.next(); // get the rate of the port int rate = DFUtilities.getRate(port); // get the channel of this port _Channel channel = (_Channel) _channelMap.getFW(port); // create the model port _Port modelPort = new _Port(rate, channel); // add the new port to the actor modelActor.addPort(modelPort); } portList = actor.inputPortList(); portIterator = portList.iterator(); while (portIterator.hasNext()) { // for every input port of the actor TypedIOPort port = (TypedIOPort) portIterator.next(); // get the rate of the port int rate = DFUtilities.getRate(port); // get the producing IOPort List sourcePortList = port.sourcePortList(); // input port may have more than one source if it is a multiport // make a port in this model for every input port connected for (int i = 0; i < sourcePortList.size(); i++) { // get the channel of the producing port _Channel channel = (_Channel) _channelMap .getFW(sourcePortList.get(i)); // if the source port is not related to a channel, then it is an external port // and we do not care about it. if (channel != null) { // otherwise set the rate (negative, because it is an input port) _Port modelPort = new _Port(-rate, channel); // add the new port to the actor modelActor.addPort(modelPort); } } } } } /** * the state of the channel in the channel array has one integer at stateIndex * indicating the number of tokens in the channel and another integer at stateIndex+1 * indicating how many consumer are still to read the token * I need to remember per receiver how many tokens there are for that receiver. * If a token is produced, then the value increases for all consumers. When a consumer * reads it decreases only for that consumer. */ protected static class _Channel { /** * Construct a instance of Channel and initialize nrConsumers to 0. */ _Channel() { _numberOfConsumers = 0; } /** * The number of initial tokens on the channel. */ int initialTokens; /** * Assign stateIndex and returns the next available index to be assigned * to the next channel, depending on the number of consumers of this channel. * @param index state index for the channel * @return index for the next component */ int assignStateIndex(int index) { assert _numberOfConsumers > 0; _stateIndex = index; return index + _numberOfConsumers; } /** * Called for any input port to be connected to the channel. Returns an index * into the state vector for this port to manage the number of remaining tokens * to be read. * @return index for the new port */ int assignPortIndex() { int nextIndex = _numberOfConsumers; _numberOfConsumers++; return nextIndex; } /** * Get the number of available tokens to the consuming port with index 'portIndex' * in state 'state'. * @param portIndex port index * @param state state * @return the number of available tokens in the channel to port with index i */ int tokens(int portIndex, _State state) { return state.channelContent[_stateIndex + portIndex]; } /** * Get the number of exclusively available tokens to the consuming port with * index 'portIndex' in state 'state'. * @param portIndex port index * @param state state * @return the number of exclusively available tokens in the channel to port with index i */ int exclusiveTokens(int portIndex, _State state) { int myTokens = tokens(portIndex, state); int max = myTokens; // we can only use them exclusively if all others have already consumed them for (int j = 0; j < _numberOfConsumers; j++) { if (j != portIndex) { max = Math.min(max, myTokens - tokens(j, state)); } } if (max < 0) { max = 0; } return max; } /** * Add new tokens into the channel. * @param state state to be updated * @param rate number of tokens to add */ void addTokens(_State state, int rate) { // add tokens for all consuming ports for (int i = 0; i < _numberOfConsumers; i++) { state.channelContent[_stateIndex + i] += rate; } } /** * Remove tokens from the channel for given port. * @param state state to be updated * @param portIndex port index * @param rate number of tokens to remove */ void removeTokens(_State state, int portIndex, int rate) { state.channelContent[_stateIndex + portIndex] += rate; // rate is negative } /** * Initialize the state 'state' to this channel's initial state * by putting the appropriate number of initial tokens in it. * @param state state to be initialized */ void setInitialState(_State state) { for (int j = 0; j < _numberOfConsumers; j++) { state.channelContent[_stateIndex + j] = initialTokens; } } /** * return the amount of memory taken by the channel content. * which is the maximum number of tokens still to be read by any * consumer * @param state state * @return amount of memory occupied by channel content */ int channelSize(_State state) { int result = 0; for (int i = 0; i < _numberOfConsumers; i++) { result = Math.max(result, state.channelContent[i]); } return result; } /** * The number of actors consuming from this channel. */ int _numberOfConsumers = -1; /** * Index of this channel into the global state vector. */ int _stateIndex; } /** * A list of channels, based on LinkedList. */ @SuppressWarnings("serial") protected static class _ListOfChannels extends LinkedList { /** * Count the overall memory taken by channels in the list in state 'state'. * @param state state * @return total memory size occupied by channels */ int channelSize(_State state) { Iterator channelIterator = iterator(); int result = 0; // iterate over channels in the list while (channelIterator.hasNext()) { _Channel channel = (_Channel) channelIterator.next(); // add up channel size result += channel.channelSize(state); } return result; } } /** * A port of an actor, connected to a channel. * A port as a rate determining the number of tokens produced/consumed in * a firing of its actor. * Negative rates represent input ports, positive rates output ports. */ protected static class _Port { /** * Construct an instance of _Port with rate rate and for channel * channel. * @param rate port rate (negative for input port) * @param channel channel to which it is bound */ _Port(int rate, _Channel channel) { _rate = rate; _channel = channel; } /** * Assign index to the port into the channel state vector * only if it is an input port. */ void assignIndex() { if (_rate < 0) { _portIndex = _channel.assignPortIndex(); } } /** * test if the port is enabled, i.e. if the associated channel has enough * tokens on this port to fire in state s * @param state state * @return true if it is enabled */ boolean isEnabled(_State state) { // an output port is always enabled if (_rate >= 0) { return true; } // otherwise check tokens, recall that rate is negative return _channel.tokens(_portIndex, state) + _rate >= 0; } /** * test if the port is enabled for exclusive firing, i.e. if the associated * channel has enough tokens on this port to fire exclusively in state s * @param state state * @return true if it is enabled */ boolean isExclusiveEnabled(_State state) { // an output port is always enabled if (_rate >= 0) { return true; } // otherwise check tokens, recall that rate is negative return _channel.exclusiveTokens(_portIndex, state) + _rate >= 0; } /** * Fire the port by accounting the numbers of tokens. * @param state state to use for firing */ void fire(_State state) { if (_rate > 0) { // producing port _channel.addTokens(state, _rate); } else { // consuming port _channel.removeTokens(state, _portIndex, _rate); } } /** * The index for this port into the channel's state vector. */ int _portIndex; /** * the port rate, negative if input port */ int _rate; /** * The channel associated with the port. */ _Channel _channel; } /** * A list of ports, based on LinkedList. */ @SuppressWarnings("serial") protected static class _ListOfPorts extends LinkedList { } /** * A model of an actor. Containing the firing profile, its count in the repetition * vector and a number of ports. */ protected static class _Actor { /** * Construct an instance of Actor, providing its name, repetition vector * count and profile information. * @param name name for the actor * @param repetitionCount repetition vector entry of the actor * @param sharedBuffersNeeded number of frame buffers needed for shared firing * @param exclusiveBuffersNeeded number of frame buffers needed for exclusive firing * @param sharedExecutionTimeNeeded execution time needed for share firing * @param exclusiveExecutionTimeNeeded execution time needed for exclusive firing */ protected _Actor(String name, int repetitionCount, int sharedBuffersNeeded, int exclusiveBuffersNeeded, int sharedExecutionTimeNeeded, int exclusiveExecutionTimeNeeded) { _name = name; _repetitionCount = repetitionCount; sharedBuffers = sharedBuffersNeeded; exclusiveBuffers = exclusiveBuffersNeeded; sharedExecutionTime = sharedExecutionTimeNeeded; exclusiveExecutionTime = exclusiveExecutionTimeNeeded; _ports = new _ListOfPorts(); } /** * The number of frame buffers the actor requires in a shared firing. */ int sharedBuffers; /** * The number of frame buffers the actor requires in an exclusive firing. */ int exclusiveBuffers; /** * Execution time (estimate) for the actor for a shared firing. */ int sharedExecutionTime; /** * Execution time (estimate) for the actor for an exclusive firing. */ int exclusiveExecutionTime; /** * Assign stateIndex to actor and its ports and returns the index for * the next component. * @param index index to assign to the actor * @return index to assign to next actor */ int assignStateIndex(int index) { // iterate over ports to assign index to ports in channel state vector Iterator portIterator = _ports.iterator(); while (portIterator.hasNext()) { _Port port = (_Port) portIterator.next(); port.assignIndex(); } // index for actor _stateIndex = index; return index + 1; } /** * Test whether the actor is enabled for a shared firing in given state state. * @param state state * @return true if enabled */ boolean isEnabled(_State state) { // no more firings needed in iteration if (state.actorContent[_stateIndex] == 0) { return false; } // test if all ports are enabled Iterator portIterator = _ports.iterator(); while (portIterator.hasNext()) { _Port port = (_Port) portIterator.next(); if (!port.isEnabled(state)) { return false; } } // all are enabled, go ahead return true; } /** * Test whether the actor is enabled for an exclusive firing in given state state. * @param state state * @return true if enabled */ boolean isExclusiveEnabled(_State state) { // no more firings needed in iteration if (state.actorContent[_stateIndex] == 0) { return false; } // test if all ports are enabled Iterator portIterator = _ports.iterator(); while (portIterator.hasNext()) { _Port port = (_Port) portIterator.next(); if (!port.isExclusiveEnabled(state)) { return false; } } // all are enabled, go ahead return true; } /** * adapt state 'state' according to a shared firing. Assumes it is enabled. * @param state state */ void fire(_State state) { // fire all ports Iterator portIterator = _ports.iterator(); while (portIterator.hasNext()) { _Port port = (_Port) portIterator.next(); port.fire(state); } // one less firing remaining in iteration state.actorContent[_stateIndex]--; // remember in the state which actor fired state.firingActor = this; // mark that the firing is shared, not exclusive state.firingExclusive = false; } /** * adapt state 'state' according to an exclusive firing. Assumes it is enabled. * @param state state */ void fireExclusive(_State state) { // fire all ports Iterator portIterator = _ports.iterator(); while (portIterator.hasNext()) { _Port port = (_Port) portIterator.next(); port.fire(state); } // one less firing remaining in iteration state.actorContent[_stateIndex]--; // remember in the state which actor fired state.firingActor = this; // mark that the firing is shared, not exclusive state.firingExclusive = true; } /** * Add a port to the actor. * @param port port to add */ void addPort(_Port port) { _ports.add(port); } /** * Initialize state of to initial state of the network. Specifically, set * the count for this actor to the number of firings in one iteration. * @param state state to initialize */ void setInitialState(_State state) { state.actorContent[_stateIndex] = _repetitionCount; } /** * index for the actor into the global state vector */ int _stateIndex; /** * A list of ports of the actor, both input and output ports. */ _ListOfPorts _ports; /** * The name of the actor. */ String _name; /** * Count for the actor in the repetition vector of the graph. */ int _repetitionCount; } /** * A list of actors, derived from LinkedList. */ @SuppressWarnings("serial") protected static class _ListOfActors extends LinkedList { } /** * State models a global state of the SDF graph and remembers the actor that was * fired to reach it. * It consists of two integer array containing the channel content and * the actor states (remaining number of firings to complete an iteration) * respectively. * Moreover, it memorizes the firing to reach the state, which actor fired and * whether the firing was exclusive. A state is typically first cloned from its * predecessor state and then an actor firing is executed on it. * It also maintains a link to its predecessor state. This way the path to reach * this state can be reconstructed. It also maintain an optimization 'value' * associated with the path leading to this state. This value is used for * optimization. */ protected static class _State { /** * Construct an instance of State, with a reference to a previous state. * @param thePreviousState link to previous state */ _State(_State thePreviousState) { previousState = thePreviousState; } /** * Create new state by cloning state 'state' and marking * s as its predecessor state. * @param state state to clone * @return the new state */ _State clone(_State state) { _State result = new _State(state); // copy global graph state result.channelContent = channelContent.clone(); result.actorContent = actorContent.clone(); // copy value result.value = value; return result; } /** * true if the firing to reach the state was exclusive. */ boolean firingExclusive; /** * The actor that was fired to reach this state. * remains nil for the initial state. */ _Actor firingActor; /** * Link to the previous state. */ _State previousState; // actual state information /** * Array to store all channel content. * Channels and input ports within those channels are given their unique * index into this array. */ int[] channelContent; /** * Array to store all actor content, remaining number of firings. * Actors are given their unique index into this array. */ int[] actorContent; /** * Value to be optimized, smaller is better. */ int value; /** * Test whether this is a valid end state, i.e. whether all actors have * completed their required number of firings. * @return true is end state */ boolean isEndState() { // test all actors for (int element : actorContent) { if (element > 0) { return false; } } return true; } /** * Determine the number of remaining firings. * @return number of remaining firings */ int getFiringsToCompletion() { int result = 0; for (int element : actorContent) { result += element; } return result; } } /** * A set of states, based on HashSet. */ @SuppressWarnings("serial") protected static class _SetOfStates extends HashSet { } /** * An abstract super class for Comparators to maintain a sorted * list of states. */ @SuppressWarnings("serial") protected static abstract class _StateComparator implements Comparator, Serializable { } /** * A Comparator to maintain a sorted list of states, sorted on their value. */ @SuppressWarnings("serial") protected static class _StateComparatorLowestValue extends _StateComparator { /** * compare two states on their value. If values tie, then sort * on arbitrary other criteria * @param o1 first object to compare * @param o2 second object to compare * @return -1 if o1