001/* OptimalScheduleFinder is a strategy object to compute an optimal scheduler
002 * for an OptimizedSDFScheduler
003
004 Copyright (c) 1997-2014 The Regents of the University of California.
005 All rights reserved.
006 Permission is hereby granted, without written agreement and without
007 license or royalty fees, to use, copy, modify, and distribute this
008 software and its documentation for any purpose, provided that the above
009 copyright notice and the following two paragraphs appear in all copies
010 of this software.
011
012 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY
013 FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
014 ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
015 THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF
016 SUCH DAMAGE.
017
018 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
019 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
020 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
021 PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
022 CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
023 ENHANCEMENTS, OR MODIFICATIONS.
024 PT_COPYRIGHT_VERSION_2
025 COPYRIGHTENDKEY
026
027 */
028
029package ptolemy.domains.sdf.optimize;
030
031import java.io.Serializable;
032import java.util.Comparator;
033import java.util.HashMap;
034import java.util.HashSet;
035import java.util.Iterator;
036import java.util.LinkedList;
037import java.util.List;
038import java.util.Map;
039import java.util.TreeSet;
040
041import ptolemy.actor.TypedIOPort;
042import ptolemy.actor.sched.Firing;
043import ptolemy.actor.sched.Schedule;
044import ptolemy.actor.util.DFUtilities;
045import ptolemy.domains.sdf.optimize.OptimizingSDFDirector.OptimizationCriteria;
046import ptolemy.kernel.util.IllegalActionException;
047
048///////////////////////////////////////////////////////////////////
049////OptimalScheduleFinder
050
051/**
052<h1>Class comments</h1>
053An OptimalScheduleFinder encapsulates an algorithm to find an optimized schedule.
054In particular it implements a simple state space exploration algorithm to find a
055minimum buffer size schedule.
056<p>
057See {@link ptolemy.domains.sdf.optimize.OptimizingSDFDirector},
058{@link ptolemy.domains.sdf.optimize.OptimizingSDFScheduler} and
059{@link ptolemy.domains.sdf.optimize.BufferingProfile} for more information.
060</p>
061@see ptolemy.domains.sdf.optimize.OptimizingSDFDirector
062@see ptolemy.domains.sdf.optimize.OptimizingSDFScheduler
063@see ptolemy.domains.sdf.optimize.BufferingProfile
064
065@author Marc Geilen
066@version $Id$
067@since Ptolemy II 10.0
068@Pt.ProposedRating Red (mgeilen)
069@Pt.AcceptedRating Red ()
070 */
071
072public class OptimalScheduleFinder {
073
074    /**
075     * Construct an instance of the OptimalScheduleFinder. Creates an object
076     * associated with the OptimizingSDFSchedule <i>scheduler</i> and using
077     * the optimization criterion <i>criterion</i> to find an optimized schedule.
078     * @param scheduler scheduler
079     * @param criterion optimization criterion
080     */
081    public OptimalScheduleFinder(OptimizingSDFScheduler scheduler,
082            OptimizationCriteria criterion) {
083        _myScheduler = scheduler;
084        _optimizationCriterion = criterion;
085    }
086
087    /**
088     * Make a schedule using a greedy (non-optimizing algorithm).
089     * @param firingVector repetition vector
090     * @return the computed schedule
091     */
092    public Schedule makeScheduleGreedy(Map firingVector) {
093        Schedule result = null;
094        try {
095            // instantiate the model
096            _instantiateAnalysisModel(firingVector);
097
098            // determine the state vector indices
099            _setStateIndices();
100
101            // run a greedy exploration
102            // keeping toExplore sorted on maximal progress makes it greedy
103            _SortedSetOfStates toExplore = new _SortedSetOfStates(
104                    new _StateComparatorMaximumProgress());
105            // add the initial state
106            toExplore.add(initialState());
107            // store the end state when found
108            _State optimalEndState = null;
109            // to be set to true as soon as end state is found
110            boolean scheduleFound = false;
111
112            // continue searching until a schedule has been found
113            while (!scheduleFound && !toExplore.isEmpty()) {
114                // take the first state to further explore from our sorted list
115                _State state = toExplore.removeFirstState();
116                // test if it is an end state, in which case we are ready.
117                if (state.isEndState()) {
118                    // found !!
119                    optimalEndState = state;
120                    scheduleFound = true;
121                } else {
122                    // try all possible actions (actor firings) enabled from this state
123                    Iterator actorIterator = _actors.iterator();
124                    while (actorIterator.hasNext()) {
125                        // for each actor a ...
126                        _Actor actor = (_Actor) actorIterator.next();
127                        // check first if 'actor' is exclusively enabled to give
128                        // preference to exclusive firing
129                        // (although perhaps we should not be assuming that from the sorted set)
130                        if (actor.isExclusiveEnabled(state)) {
131                            // it is enabled. Create a new state accordingly
132                            _State newState = state.clone(state);
133                            // fire the actor
134                            actor.fireExclusive(newState);
135                            // update the value to be optimized depending on the optimization criterion
136                            if (_optimizationCriterion == OptimizationCriteria.BUFFERS) {
137                                newState.value = Math.max(
138                                        _channels.channelSize(newState)
139                                                + actor.exclusiveBuffers,
140                                        newState.value);
141                            } else if (_optimizationCriterion == OptimizationCriteria.EXECUTIONTIME) {
142                                newState.value = state.value
143                                        + actor.exclusiveExecutionTime;
144                            }
145                            // add the new state to the list of states to be explored
146                            toExplore.add(newState);
147                        }
148                        // try also firing non-exclusive
149                        // check if a is enabled for a shared firing
150                        if (actor.isEnabled(state)) {
151                            // it is enabled. Create a new state accordingly
152                            _State newState = state.clone(state);
153                            // fire the actor
154                            actor.fire(newState);
155                            // update the value to be optimized depending on the optimization criterion
156                            if (_optimizationCriterion == OptimizationCriteria.BUFFERS) {
157                                newState.value = Math.max(
158                                        _channels.channelSize(newState)
159                                                + actor.sharedBuffers,
160                                        newState.value);
161                            } else if (_optimizationCriterion == OptimizationCriteria.EXECUTIONTIME) {
162                                newState.value = state.value
163                                        + actor.sharedExecutionTime;
164                            }
165                            // add the new state to the list of states to be explored
166                            toExplore.add(newState);
167                        }
168                    }
169                }
170            }
171            // Completed the search. Did we find anything?
172            if (scheduleFound) {
173                // yes, then turn it into a schedule.
174                result = _buildSchedule(optimalEndState);
175            }
176
177        } catch (IllegalActionException exception) {
178            // oops, something happened...
179        }
180        // return the schedule
181        return result;
182    }
183
184    /**
185     * Make a schedule using an exhaustive BFS-like optimizing algorithm.
186     * @param firingVector repetition vector
187     * @return the computed schedule
188     */
189    public Schedule makeSchedule(Map firingVector) {
190        Schedule result = null;
191        try {
192            // instantiate the model
193            _instantiateAnalysisModel(firingVector);
194
195            // determine the state vector indices
196            _setStateIndices();
197
198            // run a state-space exploration
199            // keeping toExplore sorted on memory usage ensures that the minimum memory
200            // schedule is found first.
201            _SortedSetOfStates toExplore = new _SortedSetOfStates();
202            // add the initial state
203            toExplore.add(initialState());
204            // store the end state when found
205            _State optimalEndState = null;
206            // to be set to true as soon as end state is found
207            boolean scheduleFound = false;
208
209            // continue searching until a schedule has been found
210            while (!scheduleFound && !toExplore.isEmpty()) {
211                // take the first state to further explore from our sorted list
212                _State state = toExplore.removeFirstState();
213                // test if it is an end state, in which case we are ready.
214                if (state.isEndState()) {
215                    // found !!
216                    optimalEndState = state;
217                    scheduleFound = true;
218                } else {
219                    // try all possible actions (actor firings) enabled from this state
220                    Iterator actorIterator = _actors.iterator();
221                    while (actorIterator.hasNext()) {
222                        // for each actor a ...
223                        _Actor actor = (_Actor) actorIterator.next();
224                        // check first if a is exclusively enabled to give
225                        // preference to exclusive firing
226                        // (although perhaps we should not be assuming that from the sorted set)
227                        if (actor.isExclusiveEnabled(state)) {
228                            // it is enabled. Create a new state accordingly
229                            _State newState = state.clone(state);
230                            // fire the actor
231                            actor.fireExclusive(newState);
232                            // update the value to be optimized depending on the optimization criterion
233                            if (_optimizationCriterion == OptimizationCriteria.BUFFERS) {
234                                newState.value = Math.max(
235                                        _channels.channelSize(newState)
236                                                + actor.exclusiveBuffers,
237                                        newState.value);
238                            } else if (_optimizationCriterion == OptimizationCriteria.EXECUTIONTIME) {
239                                newState.value = state.value
240                                        + actor.exclusiveExecutionTime;
241                            }
242                            // add the new state to the list of states to be explored
243                            toExplore.add(newState);
244                        }
245                        // try also firing non-exclusive
246                        // check if a is enabled for a shared firing
247                        if (actor.isEnabled(state)) {
248                            // it is enabled. Create a new state accordingly
249                            _State newState = state.clone(state);
250                            // fire the actor
251                            actor.fire(newState);
252                            // update the value to be optimized depending on the optimization criterion
253                            if (_optimizationCriterion == OptimizationCriteria.BUFFERS) {
254                                newState.value = Math.max(
255                                        _channels.channelSize(newState)
256                                                + actor.sharedBuffers,
257                                        newState.value);
258                            } else if (_optimizationCriterion == OptimizationCriteria.EXECUTIONTIME) {
259                                newState.value = state.value
260                                        + actor.sharedExecutionTime;
261                            }
262                            // add the new state to the list of states to be explored
263                            toExplore.add(newState);
264                        }
265                    }
266                }
267            }
268            // Completed the search. Did we find anything?
269            if (scheduleFound) {
270                // yes, then turn it into a schedule.
271                result = _buildSchedule(optimalEndState);
272            }
273
274        } catch (IllegalActionException e) {
275            // oops, something happened...
276        }
277        // return the schedule
278        return result;
279    }
280
281    ///////////////////////////////////////////////////////////////////
282    ////                 protected fields                                  ////
283
284    /**
285     * Instantiate the analysis model from the core model.
286     * @param firingVector contains repetition vector information
287     * @exception IllegalActionException if model information inconsistent
288     */
289    protected void _instantiateAnalysisModel(Map firingVector)
290            throws IllegalActionException {
291
292        // initialize lists and maps
293        _actors = new _ListOfActors();
294        _actorMap = new _TwoWayHashMap();
295        _channels = new _ListOfChannels();
296        _channelMap = new _TwoWayHashMap();
297
298        // create the actors
299        Iterator actorIterator = firingVector.entrySet().iterator();
300        while (actorIterator.hasNext()) {
301            int sharedBuffers, exclusiveBuffers, sharedExecutionTime,
302                    exclusiveExecutionTime;
303            Map.Entry pair = (Map.Entry) actorIterator.next();
304            ptolemy.actor.Actor actor = (ptolemy.actor.Actor) pair.getKey();
305            // if it is an actor which implements our BufferingProfile
306            if (actor instanceof BufferingProfile) {
307                BufferingProfile actorWithBufferingProfile = (BufferingProfile) actor;
308                // set the profile accordingly
309                sharedBuffers = actorWithBufferingProfile.sharedBuffers();
310                exclusiveBuffers = actorWithBufferingProfile.exclusiveBuffers();
311                sharedExecutionTime = actorWithBufferingProfile
312                        .sharedExecutionTime();
313                exclusiveExecutionTime = actorWithBufferingProfile
314                        .exclusiveExecutionTime();
315            } else {
316                // set the profile to default values
317                sharedBuffers = 0;
318                exclusiveBuffers = 0;
319                sharedExecutionTime = 0;
320                exclusiveExecutionTime = 0;
321            }
322            // create a model actor
323            _Actor modelActor = new _Actor(actor.getName(),
324                    (Integer) pair.getValue(), sharedBuffers, exclusiveBuffers,
325                    sharedExecutionTime, exclusiveExecutionTime);
326            // add the actor
327            _actors.add(modelActor);
328            // remember the link to the real actor
329            _actorMap.put(modelActor, actor);
330
331            // create a channel for every output port
332            List portList = actor.outputPortList();
333            Iterator portIterator = portList.iterator();
334            while (portIterator.hasNext()) {
335                TypedIOPort port = (TypedIOPort) portIterator.next();
336                _Channel channel = new _Channel();
337                // set the number of initial tokens
338                channel.initialTokens = DFUtilities
339                        .getTokenInitProduction(port);
340                // add the channel to the list
341                _channels.add(channel);
342                // remember the link to the IOPort
343                _channelMap.put(port, channel);
344            }
345        }
346
347        // create the actor ports
348        actorIterator = firingVector.keySet().iterator();
349        while (actorIterator.hasNext()) {
350            // for every actor...
351            ptolemy.actor.Actor actor = (ptolemy.actor.Actor) actorIterator
352                    .next();
353            _Actor modelActor = (_Actor) _actorMap.getBW(actor);
354            List portList = actor.outputPortList();
355            Iterator portIterator = portList.iterator();
356            while (portIterator.hasNext()) {
357                // for every output port of the actor
358                TypedIOPort port = (TypedIOPort) portIterator.next();
359                // get the rate of the port
360                int rate = DFUtilities.getRate(port);
361                // get the channel of this port
362                _Channel channel = (_Channel) _channelMap.getFW(port);
363                // create the model port
364                _Port modelPort = new _Port(rate, channel);
365                // add the new port to the actor
366                modelActor.addPort(modelPort);
367            }
368            portList = actor.inputPortList();
369            portIterator = portList.iterator();
370            while (portIterator.hasNext()) {
371                // for every input port of the actor
372                TypedIOPort port = (TypedIOPort) portIterator.next();
373                // get the rate of the port
374                int rate = DFUtilities.getRate(port);
375                // get the producing IOPort
376                List sourcePortList = port.sourcePortList();
377                // input port may have more than one source if it is a multiport
378                // make a port in this model for every input port connected
379                for (int i = 0; i < sourcePortList.size(); i++) {
380                    // get the channel of the producing port
381                    _Channel channel = (_Channel) _channelMap
382                            .getFW(sourcePortList.get(i));
383                    // if the source port is not related to a channel, then it is an external port
384                    // and we do not care about it.
385                    if (channel != null) {
386                        // otherwise set the rate (negative, because it is an input port)
387                        _Port modelPort = new _Port(-rate, channel);
388                        // add the new port to the actor
389                        modelActor.addPort(modelPort);
390                    }
391                }
392            }
393        }
394    }
395
396    /**
397     * the state of the channel in the channel array has one integer at stateIndex
398     * indicating the number of tokens in the channel and another integer at stateIndex+1
399     * indicating how many consumer are still to read the token
400     * I need to remember per receiver how many tokens there are for that receiver.
401     * If a token is produced, then the value increases for all consumers. When a consumer
402     * reads it decreases only for that consumer.
403     */
404    protected static class _Channel {
405
406        /**
407         * Construct a instance of Channel and initialize nrConsumers to 0.
408         */
409        _Channel() {
410            _numberOfConsumers = 0;
411        }
412
413        /**
414         * The number of initial tokens on the channel.
415         */
416        int initialTokens;
417
418        /**
419         * Assign stateIndex and returns the next available index to be assigned
420         * to the next channel, depending on the number of consumers of this channel.
421         * @param index state index for the channel
422         * @return index for the next component
423         */
424        int assignStateIndex(int index) {
425            assert _numberOfConsumers > 0;
426            _stateIndex = index;
427            return index + _numberOfConsumers;
428        }
429
430        /**
431         * Called for any input port to be connected to the channel. Returns an index
432         * into the state vector for this port to manage the number of remaining tokens
433         * to be read.
434         * @return index for the new port
435         */
436        int assignPortIndex() {
437            int nextIndex = _numberOfConsumers;
438            _numberOfConsumers++;
439            return nextIndex;
440        }
441
442        /**
443         * Get the number of available tokens to the consuming port with index 'portIndex'
444         * in state 'state'.
445         * @param portIndex port index
446         * @param state state
447         * @return the number of available tokens in the channel to port with index i
448         */
449        int tokens(int portIndex, _State state) {
450            return state.channelContent[_stateIndex + portIndex];
451        }
452
453        /**
454         * Get the number of exclusively available tokens to the consuming port with
455         * index 'portIndex' in state 'state'.
456         * @param portIndex port index
457         * @param state state
458         * @return the number of exclusively available tokens in the channel to port with index i
459         */
460        int exclusiveTokens(int portIndex, _State state) {
461            int myTokens = tokens(portIndex, state);
462            int max = myTokens;
463            // we can only use them exclusively if all others have already consumed them
464            for (int j = 0; j < _numberOfConsumers; j++) {
465                if (j != portIndex) {
466                    max = Math.min(max, myTokens - tokens(j, state));
467                }
468            }
469            if (max < 0) {
470                max = 0;
471            }
472            return max;
473        }
474
475        /**
476         * Add new tokens into the channel.
477         * @param state state to be updated
478         * @param rate number of tokens to add
479         */
480        void addTokens(_State state, int rate) {
481            // add tokens for all consuming ports
482            for (int i = 0; i < _numberOfConsumers; i++) {
483                state.channelContent[_stateIndex + i] += rate;
484            }
485        }
486
487        /**
488         * Remove tokens from the channel for given port.
489         * @param state state to be updated
490         * @param portIndex port index
491         * @param rate number of tokens to remove
492         */
493        void removeTokens(_State state, int portIndex, int rate) {
494            state.channelContent[_stateIndex + portIndex] += rate; // rate is negative
495        }
496
497        /**
498         * Initialize the state 'state' to this channel's initial state
499         * by putting the appropriate number of initial tokens in it.
500         * @param state state to be initialized
501         */
502        void setInitialState(_State state) {
503            for (int j = 0; j < _numberOfConsumers; j++) {
504                state.channelContent[_stateIndex + j] = initialTokens;
505            }
506        }
507
508        /**
509         * return the amount of memory taken by the channel content.
510         * which is the maximum number of tokens still to be read by any
511         * consumer
512         * @param state state
513         * @return amount of memory occupied by channel content
514         */
515        int channelSize(_State state) {
516            int result = 0;
517            for (int i = 0; i < _numberOfConsumers; i++) {
518                result = Math.max(result, state.channelContent[i]);
519            }
520            return result;
521        }
522
523        /**
524         * The number of actors consuming from this channel.
525         */
526        int _numberOfConsumers = -1;
527
528        /**
529         * Index of this channel into the global state vector.
530         */
531        int _stateIndex;
532    }
533
534    /**
535     * A list of channels, based on LinkedList.
536     */
537    @SuppressWarnings("serial")
538    protected static class _ListOfChannels extends LinkedList {
539
540        /**
541         * Count the overall memory taken by channels in the list in state 'state'.
542         * @param state state
543         * @return total memory size occupied by channels
544         */
545        int channelSize(_State state) {
546            Iterator channelIterator = iterator();
547            int result = 0;
548            // iterate over channels in the list
549            while (channelIterator.hasNext()) {
550                _Channel channel = (_Channel) channelIterator.next();
551                // add up channel size
552                result += channel.channelSize(state);
553            }
554            return result;
555        }
556    }
557
558    /**
559     * A port of an actor, connected to a channel.
560     * A port as a rate determining the number of tokens produced/consumed in
561     * a firing of its actor.
562     * Negative rates represent input ports, positive rates output ports.
563     */
564    protected static class _Port {
565
566        /**
567         * Construct an instance of _Port with rate <i>rate</i> and for channel
568         * <i>channel</i>.
569         * @param rate port rate (negative for input port)
570         * @param channel channel to which it is bound
571         */
572        _Port(int rate, _Channel channel) {
573            _rate = rate;
574            _channel = channel;
575        }
576
577        /**
578         * Assign index to the port into the channel state vector
579         * only if it is an input port.
580         */
581        void assignIndex() {
582            if (_rate < 0) {
583                _portIndex = _channel.assignPortIndex();
584            }
585        }
586
587        /**
588         * test if the port is enabled, i.e. if the associated channel has enough
589         * tokens on this port to fire in state s
590         * @param state state
591         * @return true if it is enabled
592         */
593        boolean isEnabled(_State state) {
594            // an output port is always enabled
595            if (_rate >= 0) {
596                return true;
597            }
598            // otherwise check tokens, recall that rate is negative
599            return _channel.tokens(_portIndex, state) + _rate >= 0;
600        }
601
602        /**
603         * test if the port is enabled for exclusive firing, i.e. if the associated
604         * channel has enough tokens on this port to fire exclusively in state s
605         * @param state state
606         * @return true if it is enabled
607         */
608        boolean isExclusiveEnabled(_State state) {
609            // an output port is always enabled
610            if (_rate >= 0) {
611                return true;
612            }
613            // otherwise check tokens, recall that rate is negative
614            return _channel.exclusiveTokens(_portIndex, state) + _rate >= 0;
615        }
616
617        /**
618         * Fire the port by accounting the numbers of tokens.
619         * @param state state to use for firing
620         */
621        void fire(_State state) {
622            if (_rate > 0) {
623                // producing port
624                _channel.addTokens(state, _rate);
625            } else {
626                // consuming port
627                _channel.removeTokens(state, _portIndex, _rate);
628            }
629        }
630
631        /**
632         * The index for this port into the channel's state vector.
633         */
634        int _portIndex;
635
636        /**
637         * the port rate, negative if input port
638         */
639        int _rate;
640
641        /**
642         * The channel associated with the port.
643         */
644        _Channel _channel;
645    }
646
647    /**
648     * A list of ports, based on LinkedList.
649     */
650    @SuppressWarnings("serial")
651    protected static class _ListOfPorts extends LinkedList {
652    }
653
654    /**
655     * A model of an actor. Containing the firing profile, its count in the repetition
656     * vector and a number of ports.
657     */
658    protected static class _Actor {
659
660        /**
661         * Construct an instance of Actor, providing its name, repetition vector
662         * count and profile information.
663         * @param name name for the actor
664         * @param repetitionCount repetition vector entry of the actor
665         * @param sharedBuffersNeeded number of frame buffers needed for shared firing
666         * @param exclusiveBuffersNeeded number of frame buffers needed for exclusive firing
667         * @param sharedExecutionTimeNeeded execution time needed for share firing
668         * @param exclusiveExecutionTimeNeeded execution time needed for exclusive firing
669         */
670        protected _Actor(String name, int repetitionCount,
671                int sharedBuffersNeeded, int exclusiveBuffersNeeded,
672                int sharedExecutionTimeNeeded,
673                int exclusiveExecutionTimeNeeded) {
674            _name = name;
675            _repetitionCount = repetitionCount;
676            sharedBuffers = sharedBuffersNeeded;
677            exclusiveBuffers = exclusiveBuffersNeeded;
678            sharedExecutionTime = sharedExecutionTimeNeeded;
679            exclusiveExecutionTime = exclusiveExecutionTimeNeeded;
680            _ports = new _ListOfPorts();
681        }
682
683        /**
684         * The number of frame buffers the actor requires in a shared firing.
685         */
686        int sharedBuffers;
687
688        /**
689         * The number of frame buffers the actor requires in an exclusive firing.
690         */
691        int exclusiveBuffers;
692
693        /**
694         * Execution time (estimate) for the actor for a shared firing.
695         */
696        int sharedExecutionTime;
697
698        /**
699         * Execution time (estimate) for the actor for an exclusive firing.
700         */
701        int exclusiveExecutionTime;
702
703        /**
704         * Assign stateIndex to actor and its ports and returns the index for
705         * the next component.
706         * @param index index to assign to the actor
707         * @return index to assign to next actor
708         */
709        int assignStateIndex(int index) {
710            // iterate over ports to assign index to ports in channel state vector
711            Iterator portIterator = _ports.iterator();
712            while (portIterator.hasNext()) {
713                _Port port = (_Port) portIterator.next();
714                port.assignIndex();
715            }
716            // index for actor
717            _stateIndex = index;
718            return index + 1;
719        }
720
721        /**
722         * Test whether the actor is enabled for a shared firing in given state <i>state</i>.
723         * @param state state
724         * @return true if enabled
725         */
726        boolean isEnabled(_State state) {
727            // no more firings needed in iteration
728            if (state.actorContent[_stateIndex] == 0) {
729                return false;
730            }
731            // test if all ports are enabled
732            Iterator portIterator = _ports.iterator();
733            while (portIterator.hasNext()) {
734                _Port port = (_Port) portIterator.next();
735                if (!port.isEnabled(state)) {
736                    return false;
737                }
738            }
739            // all are enabled, go ahead
740            return true;
741        }
742
743        /**
744         * Test whether the actor is enabled for an exclusive firing in given state <i>state</i>.
745         * @param state state
746         * @return true if enabled
747         */
748        boolean isExclusiveEnabled(_State state) {
749            // no more firings needed in iteration
750            if (state.actorContent[_stateIndex] == 0) {
751                return false;
752            }
753            // test if all ports are enabled
754            Iterator portIterator = _ports.iterator();
755            while (portIterator.hasNext()) {
756                _Port port = (_Port) portIterator.next();
757                if (!port.isExclusiveEnabled(state)) {
758                    return false;
759                }
760            }
761            // all are enabled, go ahead
762            return true;
763        }
764
765        /**
766         * adapt state 'state' according to a shared firing. Assumes it is enabled.
767         * @param state state
768         */
769        void fire(_State state) {
770            // fire all ports
771            Iterator portIterator = _ports.iterator();
772            while (portIterator.hasNext()) {
773                _Port port = (_Port) portIterator.next();
774                port.fire(state);
775            }
776            // one less firing remaining in iteration
777            state.actorContent[_stateIndex]--;
778            // remember in the state which actor fired
779            state.firingActor = this;
780            // mark that the firing is shared, not exclusive
781            state.firingExclusive = false;
782        }
783
784        /**
785         * adapt state 'state' according to an exclusive firing. Assumes it is enabled.
786         * @param state state
787         */
788        void fireExclusive(_State state) {
789            // fire all ports
790            Iterator portIterator = _ports.iterator();
791            while (portIterator.hasNext()) {
792                _Port port = (_Port) portIterator.next();
793                port.fire(state);
794            }
795            // one less firing remaining in iteration
796            state.actorContent[_stateIndex]--;
797            // remember in the state which actor fired
798            state.firingActor = this;
799            // mark that the firing is shared, not exclusive
800            state.firingExclusive = true;
801        }
802
803        /**
804         * Add a port to the actor.
805         * @param port port to add
806         */
807        void addPort(_Port port) {
808            _ports.add(port);
809        }
810
811        /**
812         * Initialize state of to initial state of the network. Specifically, set
813         * the count for this actor to the number of firings in one iteration.
814         * @param state state to initialize
815         */
816        void setInitialState(_State state) {
817            state.actorContent[_stateIndex] = _repetitionCount;
818        }
819
820        /**
821         * index for the actor into the global state vector
822         */
823        int _stateIndex;
824
825        /**
826         * A list of ports of the actor, both input and output ports.
827         */
828        _ListOfPorts _ports;
829
830        /**
831         * The name of the actor.
832         */
833        String _name;
834
835        /**
836         * Count for the actor in the repetition vector of the graph.
837         */
838        int _repetitionCount;
839    }
840
841    /**
842     * A list of actors, derived from LinkedList.
843     */
844    @SuppressWarnings("serial")
845    protected static class _ListOfActors extends LinkedList {
846    }
847
848    /**
849     * State models a global state of the SDF graph and remembers the actor that was
850     * fired to reach it.
851     * It consists of two integer array containing the channel content and
852     * the actor states (remaining number of firings to complete an iteration)
853     * respectively.
854     * Moreover, it memorizes the firing to reach the state, which actor fired and
855     * whether the firing was exclusive. A state is typically first cloned from its
856     * predecessor state and then an actor firing is executed on it.
857     * It also maintains a link to its predecessor state. This way the path to reach
858     * this state can be reconstructed. It also maintain an optimization 'value'
859     * associated with the path leading to this state. This value is used for
860     * optimization.
861     */
862    protected static class _State {
863
864        /**
865         * Construct an instance of State, with a reference to a previous state.
866         * @param thePreviousState link to previous state
867         */
868        _State(_State thePreviousState) {
869            previousState = thePreviousState;
870        }
871
872        /**
873         * Create new state by cloning state 'state' and marking
874         * s as its predecessor state.
875         * @param state state to clone
876         * @return the new state
877         */
878        _State clone(_State state) {
879            _State result = new _State(state);
880            // copy global graph state
881            result.channelContent = channelContent.clone();
882            result.actorContent = actorContent.clone();
883            // copy value
884            result.value = value;
885            return result;
886        }
887
888        /**
889         * true if the firing to reach the state was exclusive.
890         */
891        boolean firingExclusive;
892
893        /**
894         * The actor that was fired to reach this state.
895         * remains nil for the initial state.
896         */
897        _Actor firingActor;
898
899        /**
900         * Link to the previous state.
901         */
902        _State previousState;
903
904        // actual state information
905        /**
906         * Array to store all channel content.
907         * Channels and input ports within those channels are given their unique
908         * index into this array.
909         */
910        int[] channelContent;
911
912        /**
913         * Array to store all actor content, remaining number of firings.
914         * Actors are given their unique index into this array.
915         */
916        int[] actorContent;
917
918        /**
919         * Value to be optimized, smaller is better.
920         */
921        int value;
922
923        /**
924         * Test whether this is a valid end state, i.e. whether all actors have
925         * completed their required number of firings.
926         * @return true is end state
927         */
928        boolean isEndState() {
929            // test all actors
930            for (int element : actorContent) {
931                if (element > 0) {
932                    return false;
933                }
934            }
935            return true;
936        }
937
938        /**
939         * Determine the number of remaining firings.
940         * @return number of remaining firings
941         */
942        int getFiringsToCompletion() {
943            int result = 0;
944            for (int element : actorContent) {
945                result += element;
946            }
947            return result;
948        }
949
950    }
951
952    /**
953     * A set of states, based on HashSet.
954     */
955    @SuppressWarnings("serial")
956    protected static class _SetOfStates extends HashSet {
957    }
958
959    /**
960     * An abstract super class for Comparators to maintain a sorted
961     * list of states.
962     */
963    @SuppressWarnings("serial")
964    protected static abstract class _StateComparator
965            implements Comparator, Serializable {
966    }
967
968    /**
969     * A Comparator to maintain a sorted list of states, sorted on their value.
970     */
971    @SuppressWarnings("serial")
972    protected static class _StateComparatorLowestValue
973            extends _StateComparator {
974
975        /**
976         * compare two states on their value. If values tie, then sort
977         * on arbitrary other criteria
978         * @param o1 first object to compare
979         * @param o2 second object to compare
980         * @return -1 if o1 &lt; o2, +1 if o1 &gt; o2 0 otherwise
981         */
982        @Override
983        public int compare(Object o1, Object o2) {
984            _State state1 = (_State) o1;
985            _State state2 = (_State) o2;
986            // sort on value
987            if (state1.value != state2.value) {
988                return state1.value - state2.value;
989            } else {
990                // value tie. compare channel state
991                for (int i = 0; i < state1.channelContent.length; i++) {
992                    if (state1.channelContent[i] != state2.channelContent[i]) {
993                        return state1.channelContent[i]
994                                - state2.channelContent[i];
995                    }
996                }
997                // still no difference, compare actor state
998                for (int i = 0; i < state1.actorContent.length; i++) {
999                    if (state1.actorContent[i] != state2.actorContent[i]) {
1000                        return state1.actorContent[i] - state2.actorContent[i];
1001                    }
1002                }
1003                // they are really equal
1004                return 0;
1005            }
1006        }
1007    }
1008
1009    /**
1010     * A Comparator to maintain a sorted list of states, sorted on their
1011     * progress to the final state.
1012     */
1013    @SuppressWarnings("serial")
1014    protected static class _StateComparatorMaximumProgress
1015            extends _StateComparator {
1016
1017        /**
1018         * Construct an instance of StateComparatorMaximumProgress. It creates
1019         * a secondary comparator based on StateComparatorLowestValue.
1020         */
1021        _StateComparatorMaximumProgress() {
1022            _backupComparator = new _StateComparatorLowestValue();
1023        }
1024
1025        /**
1026         * Compare the states based on smallest number of remaining firings.
1027         * @param o1 first object to compare
1028         * @param o2 second object to compare
1029         * @return -1 if o1 &lt; o2, +1 if o1 &gt; o2 0 otherwise
1030         */
1031        @Override
1032        public int compare(Object o1, Object o2) {
1033            _State state1 = (_State) o1;
1034            _State state2 = (_State) o2;
1035            int progress1 = state1.getFiringsToCompletion();
1036            int progress2 = state2.getFiringsToCompletion();
1037            if (progress1 != progress2) {
1038                // least number of firings first
1039                return progress1 - progress2;
1040            } else {
1041                // tie, invoke backup comparator
1042                return _backupComparator.compare(state1, state2);
1043            }
1044        }
1045
1046        /**
1047         * a secondary comparator to break a tie.
1048         */
1049        _StateComparator _backupComparator;
1050    }
1051
1052    /**
1053     * A sorted set of states. Internally using a TreeSet.
1054     */
1055    protected static class _SortedSetOfStates {
1056
1057        /**
1058         * Construct an instance of SortedSetOfStates. Creates the default
1059         * comparator and TreeSet. Default comparator sorts on lowest value.
1060         */
1061        _SortedSetOfStates() {
1062            _comparator = new _StateComparatorLowestValue();
1063            _treeSet = new TreeSet(_comparator);
1064        }
1065
1066        /**
1067         * Construct an instance with an explicitly specified comparator.
1068         * @param comparator comparator
1069         */
1070        _SortedSetOfStates(_StateComparator comparator) {
1071            _comparator = comparator;
1072            _treeSet = new TreeSet(_comparator);
1073        }
1074
1075        /**
1076         * Removes the first state from the sorted list.
1077         * @return state
1078         */
1079        _State removeFirstState() {
1080            _State state = (_State) _treeSet.first();
1081            _treeSet.remove(state);
1082            return state;
1083        }
1084
1085        /**
1086         * Adds a state to the sorted list.
1087         * @param state to add
1088         */
1089        void add(_State state) {
1090            _treeSet.add(state);
1091        }
1092
1093        /**
1094         * Test if list is empty.
1095         * @return true if empty
1096         */
1097        boolean isEmpty() {
1098            return _treeSet.isEmpty();
1099        }
1100
1101        /**
1102         * The comparator to use for sorting
1103         */
1104        _StateComparator _comparator;
1105
1106        /**
1107         * A tree set to store the sorted list.
1108         */
1109        TreeSet _treeSet;
1110    }
1111
1112    /**
1113     * A two-way hash map provides fast lookup in both directions
1114     * of a bijective function between objects.
1115     * Supports only adding.
1116     * (Didn't know whether Java provides a standard solution.)
1117     */
1118    protected static class _TwoWayHashMap {
1119
1120        /**
1121         * Construct an instance of two-way hash map.
1122         */
1123        _TwoWayHashMap() {
1124            _forwardMap = new HashMap();
1125            _backwardMap = new HashMap();
1126        }
1127
1128        /**
1129         * Put an association between objects A and B in the hash map.
1130         * @param A object A
1131         * @param B object B
1132         */
1133        void put(Object A, Object B) {
1134            _forwardMap.put(A, B);
1135            _backwardMap.put(B, A);
1136        }
1137
1138        /**
1139         * Forward lookup.
1140         * @param A lookup object associated with object A
1141         * @return associated object
1142         */
1143        Object getFW(Object A) {
1144            return _forwardMap.get(A);
1145        }
1146
1147        /**
1148         * Backward lookup.
1149         * @param B lookup object associated with object B
1150         * @return associated object
1151         */
1152        Object getBW(Object B) {
1153            return _backwardMap.get(B);
1154        }
1155
1156        /**
1157         * one-way hash map to make the forward association
1158         */
1159        HashMap _forwardMap;
1160
1161        /**
1162         * one-way hash map to make the backward association
1163         */
1164        HashMap _backwardMap;
1165
1166    }
1167
1168    ///////////////////////////////////////////////////////////////////
1169    ////                   private fields                                  ////
1170
1171    /**
1172     * Build the final schedule from the end state found
1173     * @param state optimal end state
1174     * @return schedule
1175     */
1176    private Schedule _buildSchedule(_State state) {
1177        // create a new schedule
1178        Schedule result = new Schedule();
1179        // reverse the order of the states, because they are linked from final
1180        // state to initial state
1181        LinkedList stateList = new LinkedList();
1182        _State currentState = state;
1183        while (currentState != null) {
1184            // test if it actually represents an actor firing, otherwise forget it
1185            if (currentState.firingActor != null) {
1186                stateList.addFirst(currentState);
1187            }
1188            currentState = currentState.previousState;
1189        }
1190
1191        // build the schedule
1192        Iterator stateListIterator = stateList.iterator();
1193        while (stateListIterator.hasNext()) {
1194            currentState = (_State) stateListIterator.next();
1195            // get the real actor from the model actor
1196            ptolemy.actor.Actor actor = (ptolemy.actor.Actor) _actorMap
1197                    .getFW(currentState.firingActor);
1198            // check if the actor implements the special BufferingProfile interface
1199            if (actor instanceof BufferingProfile) {
1200                // if yes, create a BufferingProfileFiring with the right parameters
1201                BufferingProfileFiring firing = new BufferingProfileFiring(
1202                        actor, currentState.firingExclusive);
1203                firing.setIterationCount(1);
1204                // add it to the schedule
1205                result.add(firing);
1206                // output the schedule to the debug listener
1207                _myScheduler.showDebug("Fire actor " + actor.getFullName()
1208                        + " exclusive: " + currentState.firingExclusive);
1209            } else {
1210                // if no, create a normal Firing with the right parameters
1211                Firing firing = new Firing(actor);
1212                firing.setIterationCount(1);
1213                // add it to the schedule
1214                result.add(firing);
1215                // output the schedule to the debug listener
1216                _myScheduler.showDebug("Fire actor " + actor.getFullName());
1217            }
1218        }
1219        return result;
1220    }
1221
1222    /**
1223     * Assign the state indices into state vector to actors and channels
1224     * (and recursively to the ports).
1225     */
1226    private void _setStateIndices() {
1227        int i = 0;
1228        Iterator actorIterator = _actors.iterator();
1229        while (actorIterator.hasNext()) {
1230            _Actor actor = (_Actor) actorIterator.next();
1231            i = actor.assignStateIndex(i);
1232        }
1233        _actorSize = i;
1234
1235        i = 0;
1236        Iterator channelIterator = _channels.iterator();
1237        while (channelIterator.hasNext()) {
1238            _Channel channel = (_Channel) channelIterator.next();
1239            i = channel.assignStateIndex(i);
1240        }
1241        _channelSize = i;
1242    }
1243
1244    /**
1245     * Create the initial state
1246     * @return initial state
1247     */
1248    private _State initialState() {
1249        _State result = new _State(null);
1250        // initialize state vectors
1251        result.channelContent = new int[_channelSize];
1252        result.actorContent = new int[_actorSize];
1253        // initialize actors
1254        Iterator actorIterator = _actors.iterator();
1255        while (actorIterator.hasNext()) {
1256            _Actor actor = (_Actor) actorIterator.next();
1257            actor.setInitialState(result);
1258        }
1259        // initialize channels
1260        Iterator channelIterator = _channels.iterator();
1261        while (channelIterator.hasNext()) {
1262            _Channel channel = (_Channel) channelIterator.next();
1263            channel.setInitialState(result);
1264        }
1265        return result;
1266    }
1267
1268    /**
1269     * list of actors in the model to optimize
1270     */
1271    private _ListOfActors _actors;
1272
1273    /**
1274     * state size occupied by channels
1275     */
1276    private int _channelSize;
1277
1278    /**
1279     * State size occupied by actors
1280     */
1281    private int _actorSize;
1282
1283    /**
1284     * a list of channels in the model
1285     */
1286    private _ListOfChannels _channels;
1287
1288    /**
1289     * The scheduler invoking the service of this object.
1290     */
1291    private OptimizingSDFScheduler _myScheduler;
1292
1293    /**
1294     * Two-way hash map associating actor models and their Ptolemy actors
1295     */
1296    private _TwoWayHashMap _actorMap;
1297
1298    /**
1299     * Two-way hash map associating channels with their producing IOPorts
1300     */
1301    private _TwoWayHashMap _channelMap;
1302
1303    /**
1304     * The optimization criterion to be used from the OptimizingSDFScheduler
1305     */
1306    private OptimizationCriteria _optimizationCriterion;
1307
1308}