adevs
/home/rotten/adevs-2.6/include/adevs_simulator.h
00001 /***************
00002 Copyright (C) 2000-2010 by James Nutaro
00003 
00004 This library is free software; you can redistribute it and/or
00005 modify it under the terms of the GNU Lesser General Public
00006 License as published by the Free Software Foundation; either
00007 version 2 of the License, or (at your option) any later version.
00008 
00009 This library is distributed in the hope that it will be useful,
00010 but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012 Lesser General Public License for more details.
00013 
00014 You should have received a copy of the GNU Lesser General Public
00015 License along with this library; if not, write to the Free Software
00016 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00017 
00018 Bugs, comments, and questions can be sent to nutaro@gmail.com
00019 ***************/
00020 #ifndef __adevs_simulator_h_
00021 #define __adevs_simulator_h_
00022 #include "adevs_abstract_simulator.h"
00023 #include "adevs_models.h"
00024 #include "adevs_event_listener.h"
00025 #include "adevs_sched.h"
00026 #include "adevs_bag.h"
00027 #include "adevs_set.h"
00028 #include "object_pool.h"
00029 #include "adevs_lp.h"
00030 #include <cassert>
00031 #include <cstdlib>
00032 #include <iostream>
00033 #include <vector>
00034 
00035 namespace adevs
00036 {
00037 
00044 template <class X, class T = double> class Simulator:
00045         public AbstractSimulator<X,T>
00046 {
00047         public:
00054                 Simulator(Devs<X,T>* model):
00055                         AbstractSimulator<X,T>(),lps(NULL)
00056                 {
00057                         schedule(model,adevs_zero<T>());
00058                 }
00063                 T nextEventTime()
00064                 {
00065                         return sched.minPriority();
00066                 }
00068                 void execNextEvent()
00069                 {
00070                         computeNextOutput();
00071                         computeNextState(bogus_input,sched.minPriority());
00072                 }
00074                 void execUntil(T tend)
00075                 {
00076                         while (nextEventTime() <= tend 
00077                    && nextEventTime() < adevs_inf<T>()) {
00078                                 execNextEvent();
00079             }
00080                 }
00086                 void computeNextOutput();
00095                 void computeNextState(Bag<Event<X,T> >& input, T t);
00101                 ~Simulator();
00106                 void addModel(Atomic<X,T>* model) 
00107                 {
00108                         schedule(model,adevs_zero<T>());
00109                 }
00114                 Simulator(LogicalProcess<X,T>* lp);
00126                 void beginLookahead();
00131                 void endLookahead();
00138                 void lookNextEvent();
00139         private:
00140                 typedef enum { OUTPUT_OK, OUTPUT_NOT_OK, RESTORING_OUTPUT } OutputStatus;
00141                 // Structure to support parallel computing by a logical process
00142                 struct lp_support
00143                 {
00144                         // The processor that this simulator works for
00145                         LogicalProcess<X,T>* lp;
00146                         bool look_ahead, stop_forced;
00147                         OutputStatus out_flag;
00148                         Bag<Atomic<X,T>*> to_restore;
00149                 };
00150                 // This is NULL if the simulator is not supporting a logical process
00151                 lp_support* lps;
00152                 // Bogus input bag for execNextEvent() method
00153                 Bag<Event<X,T> > bogus_input;
00154                 // The event schedule
00155                 Schedule<X,T> sched;
00156                 // List of imminent models
00157                 Bag<Atomic<X,T>*> imm;
00158                 // List of models activated by input
00159                 Bag<Atomic<X,T>*> activated;
00160                 // Pools of preallocated, commonly used objects
00161                 object_pool<Bag<X> > io_pool;
00162                 object_pool<Bag<Event<X,T> > > recv_pool;
00163                 // Sets for computing structure changes.
00164                 Bag<Devs<X,T>*> added;
00165                 Bag<Devs<X,T>*> removed;
00166                 Set<Devs<X,T>*> next;
00167                 Set<Devs<X,T>*> prev;
00168                 // Model transition functions are evaluated from the bottom up!
00169                 struct bottom_to_top_depth_compare
00170                 {
00171                         bool operator()(const Network<X,T>* m1, const Network<X,T>* m2) const
00172                         {
00173                                 unsigned long int d1 = 0, d2 = 0;
00174                                 // Compute depth of m1
00175                                 const Network<X,T>* m = m1->getParent();
00176                                 while (m != NULL) 
00177                                 {
00178                                         d1++;
00179                                         m = m->getParent();
00180                                 }
00181                                 // Compute depth of m2
00182                                 m = m2->getParent();
00183                                 while (m != NULL)
00184                                 {
00185                                         d2++;
00186                                         m = m->getParent();
00187                                 }
00188                                 // Models at the same depth are sorted by name
00189                                 if (d1 == d2) return m1 < m2;
00190                                 // Otherwise, sort by depth
00191                                 return d1 > d2;
00192                         }
00193                 };
00194                 struct top_to_bottom_depth_compare
00195                 {
00196                         bool operator()(const Devs<X,T>* m1, const Devs<X,T>* m2) const
00197                         {
00198                                 unsigned long int d1 = 0, d2 = 0;
00199                                 // Compute depth of m1
00200                                 const Network<X,T>* m = m1->getParent();
00201                                 while (m != NULL) 
00202                                 {
00203                                         d1++;
00204                                         m = m->getParent();
00205                                 }
00206                                 // Compute depth of m2
00207                                 m = m2->getParent();
00208                                 while (m != NULL)
00209                                 {
00210                                         d2++;
00211                                         m = m->getParent();
00212                                 }
00213                                 // Models at the same depth are sorted by name
00214                                 if (d1 == d2) return m1 < m2;
00215                                 // Otherwise, sort by depth
00216                                 return d1 < d2;
00217                         }
00218                 };
00219                 std::set<Network<X,T>*,bottom_to_top_depth_compare> model_func_eval_set;
00220                 std::set<Devs<X,T>*,top_to_bottom_depth_compare> sorted_removed;
00225                 void schedule(Devs<X,T>* model, T t);
00227                 void route(Network<X,T>* parent, Devs<X,T>* src, X& x);
00233                 void inject_event(Atomic<X,T>* model, X& value);
00238                 void unschedule_model(Devs<X,T>* model);
00244                 void clean_up(Devs<X,T>* model);
00251                 void exec_event(Atomic<X,T>* model, bool internal, T t);
00255                 void getAllChildren(Network<X,T>* model, Set<Devs<X,T>*>& s);
00261                 bool manage_lookahead_data(Atomic<X,T>* model);
00262 };
00263 
00264 template <class X, class T>
00265 void Simulator<X,T>::computeNextOutput()
00266 {
00267         // If the imminent set is up to date, then just return
00268         if (imm.empty() == false) return;
00269         // Get the imminent models from the schedule. This sets the active flags.
00270         sched.getImminent(imm);
00271         // Compute output functions and route the events. The bags of output
00272         // are held for garbage collection at a later time.
00273         for (typename Bag<Atomic<X,T>*>::iterator imm_iter = imm.begin(); 
00274                 imm_iter != imm.end(); imm_iter++)
00275         {
00276                 Atomic<X,T>* model = *imm_iter;
00277                 // If the output for this model has already been computed, then skip it
00278                 if (model->y == NULL)
00279                 {
00280                         model->y = io_pool.make_obj();
00281                         model->output_func(*(model->y));
00282                         // Route each event in y
00283                         for (typename Bag<X>::iterator y_iter = model->y->begin(); 
00284                         y_iter != model->y->end(); y_iter++)
00285                         {
00286                                 route(model->getParent(),model,*y_iter);
00287                         }
00288                 }
00289         }
00290 }
00291 
00292 template <class X, class T>
00293 void Simulator<X,T>::computeNextState(Bag<Event<X,T> >& input, T t)
00294 {
00295         // Clean up if there was a previous IO calculation
00296         if (t < sched.minPriority())
00297         {
00298                 typename Bag<Atomic<X,T>*>::iterator iter;
00299                 for (iter = activated.begin(); iter != activated.end(); iter++)
00300                 {
00301                         clean_up(*iter);
00302                 }
00303                 activated.clear();
00304                 for (iter = imm.begin(); iter != imm.end(); iter++)
00305                 {
00306                         clean_up(*iter);
00307                 }
00308                 imm.clear();
00309         }
00310         // Otherwise, if the internal IO needs to be computed, do it
00311         else if (t == sched.minPriority() && imm.empty())
00312         {
00313                 computeNextOutput();
00314         }
00315         // Apply the injected inputs
00316         for (typename Bag<Event<X,T> >::iterator iter = input.begin(); 
00317         iter != input.end(); iter++)
00318         {
00319                 Atomic<X,T>* amodel = (*iter).model->typeIsAtomic();
00320                 if (amodel != NULL)
00321                 {
00322                         inject_event(amodel,(*iter).value);
00323                 }
00324                 else
00325                 {
00326                         route((*iter).model->typeIsNetwork(),(*iter).model,(*iter).value);
00327                 }
00328         }
00329         /*
00330         Compute the states of atomic models.  Store Network models that 
00331         need to have their model transition function evaluated in a
00332         special container that will be used when the structure changes are
00333         computed (see exec_event(.)).
00334         */
00335         for (typename Bag<Atomic<X,T>*>::iterator iter = imm.begin(); 
00336         iter != imm.end(); iter++)
00337         {
00338                 exec_event(*iter,true,t); // Internal and confluent transitions
00339         }
00340         for (typename Bag<Atomic<X,T>*>::iterator iter = activated.begin(); 
00341         iter != activated.end(); iter++)
00342         {
00343                 exec_event(*iter,false,t); // External transitions
00344         }
00351         if (model_func_eval_set.empty() == false)
00352         {
00353                 while (!model_func_eval_set.empty())
00354                 {
00355                         Network<X,T>* network_model = *(model_func_eval_set.begin());
00356                         getAllChildren(network_model,prev);
00357                         if (network_model->model_transition() &&
00358                                         network_model->getParent() != NULL)
00359                         {
00360                                 model_func_eval_set.insert(network_model->getParent());
00361                         }
00362                         getAllChildren(network_model,next);
00363                         model_func_eval_set.erase(network_model);
00364                 }
00365                 // Find the set of models that were added.
00366                 set_assign_diff(added,next,prev);
00367                 // Find the set of models that were removed
00368                 set_assign_diff(removed,prev,next);
00369                 // Intersection of added and removed is always empty, so no need to look
00370                 // for models in both (an earlier version of the code did this).
00371                 next.clear();
00372                 prev.clear();
00379                 for (typename Bag<Devs<X,T>*>::iterator iter = added.begin(); 
00380                         iter != added.end(); iter++)
00381                 {
00382                         schedule(*iter,t);
00383                 }
00384                 // Done with the additions
00385                 added.clear();
00386                 // Remove the models that are in the removed set.
00387                 for (typename Bag<Devs<X,T>*>::iterator iter = removed.begin(); 
00388                         iter != removed.end(); iter++)
00389                 {
00390                         clean_up(*iter);
00391                         unschedule_model(*iter);
00392                         // Add to a sorted remove set for deletion
00393                         sorted_removed.insert(*iter); 
00394                 }
00395                 // Done with the unsorted remove set
00396                 removed.clear();
00397                 // Delete the sorted removed models
00398                 while (!sorted_removed.empty())
00399                 {
00400                         // Get the model to erase
00401                         Devs<X,T>* model_to_remove = *(sorted_removed.begin());
00406                         if (model_to_remove->typeIsNetwork() != NULL)
00407                         {
00408                                 getAllChildren(model_to_remove->typeIsNetwork(),prev);
00409                                 for (typename Set<Devs<X,T>*>::iterator iter = prev.begin(); 
00410                                         iter != prev.end(); iter++)
00411                                 {
00412                                         sorted_removed.erase(*iter);
00413                                 }
00414                                 prev.clear();
00415                         }
00416                         // Remove the model
00417                         sorted_removed.erase(sorted_removed.begin());
00418                         // Delete the model and its children
00419                         delete model_to_remove;
00420                 }
00421                 // Removed sets should be empty now
00422                 assert(prev.empty());
00423                 assert(sorted_removed.empty());
00424         } // End of the structure change
00425         // Cleanup and reschedule models that changed state in this iteration
00426         // and survived the structure change phase.
00427         for (typename Bag<Atomic<X,T>*>::iterator iter = imm.begin(); 
00428                 iter != imm.end(); iter++) // Schedule the imminents
00429         {
00430                 clean_up(*iter);
00431                 schedule(*iter,t);
00432         }
00433         // Schedule the activated
00434         for (typename Bag<Atomic<X,T>*>::iterator iter = activated.begin(); 
00435                 iter != activated.end(); iter++)
00436         {
00437                 clean_up(*iter);
00438                 schedule(*iter,t);
00439         }
00440         // Empty the bags
00441         imm.clear();
00442         activated.clear();
00443         // If we are looking ahead, throw an exception if a stop was forced
00444         if (lps != NULL && lps->stop_forced)
00445         {
00446                 lookahead_impossible_exception err;
00447                 throw err;
00448         }
00449 }
00450 
00451 template <class X, class T>
00452 void Simulator<X,T>::clean_up(Devs<X,T>* model)
00453 {
00454         Atomic<X,T>* amodel = model->typeIsAtomic();
00455         if (amodel != NULL)
00456         {
00457                 amodel->active = false;
00458                 if (amodel->x != NULL)
00459                 {
00460                         amodel->x->clear();
00461                         io_pool.destroy_obj(amodel->x);
00462                         amodel->x = NULL;
00463                 }
00464                 if (amodel->y != NULL)
00465                 {
00466                         amodel->gc_output(*(amodel->y));
00467                         amodel->y->clear();
00468                         io_pool.destroy_obj(amodel->y);
00469                         amodel->y = NULL;
00470                 }
00471         }
00472         else
00473         {
00474                 Set<Devs<X,T>*> components;
00475                 model->typeIsNetwork()->getComponents(components);
00476                 for (typename Set<Devs<X,T>*>::iterator iter = components.begin();
00477                 iter != components.end(); iter++)
00478                 {
00479                         clean_up(*iter);
00480                 }
00481         }
00482 }
00483 
00484 template <class X, class T>
00485 void Simulator<X,T>::unschedule_model(Devs<X,T>* model)
00486 {
00487         if (model->typeIsAtomic() != NULL)
00488         {
00489                 sched.schedule(model->typeIsAtomic(),adevs_inf<T>());
00490                 imm.erase(model->typeIsAtomic());
00491                 activated.erase(model->typeIsAtomic());
00492         }
00493         else
00494         {
00495                 Set<Devs<X,T>*> components;
00496                 model->typeIsNetwork()->getComponents(components);
00497                 for (typename Set<Devs<X,T>*>::iterator iter = components.begin();
00498                 iter != components.end(); iter++)
00499                 {
00500                         unschedule_model(*iter);
00501                 }
00502         }
00503 }
00504 
00505 template <class X, class T>
00506 void Simulator<X,T>::schedule(Devs<X,T>* model, T t)
00507 {
00508         Atomic<X,T>* a = model->typeIsAtomic();
00509         if (a != NULL)
00510         {
00511                 a->tL = t;
00512                 T dt = a->ta();
00513                 if (dt < adevs_zero<T>())
00514                 {
00515                         exception err("Negative time advance",a);
00516                         throw err;
00517                 }
00518                 if (dt == adevs_inf<T>())
00519                         sched.schedule(a,adevs_inf<T>());
00520                 else
00521                         sched.schedule(a,t+dt);
00522         }
00523         else
00524         {
00525                 Set<Devs<X,T>*> components;
00526                 model->typeIsNetwork()->getComponents(components);
00527                 typename Set<Devs<X,T>*>::iterator iter = components.begin();
00528                 for (; iter != components.end(); iter++)
00529                 {
00530                         schedule(*iter,t);
00531                 }
00532         }
00533 }
00534 
00535 template <class X, class T>
00536 void Simulator<X,T>::inject_event(Atomic<X,T>* model, X& value)
00537 {
00538         if (model->active == false)
00539         {
00540                 model->active = true;
00541                 activated.insert(model);
00542         }
00543         if (model->x == NULL)
00544         {
00545                 model->x = io_pool.make_obj();
00546         }
00547         model->x->insert(value);
00548 }
00549 
00550 template <class X, class T>
00551 void Simulator<X,T>::route(Network<X,T>* parent, Devs<X,T>* src, X& x)
00552 {
00553         // Notify event listeners if this is an output event
00554         if (parent != src && (lps == NULL || lps->out_flag != RESTORING_OUTPUT))
00555                 this->notify_output_listeners(src,x,sched.minPriority());
00556         // No one to do the routing, so return
00557         if (parent == NULL) return;
00558         // Compute the set of receivers for this value
00559         Bag<Event<X,T> >* recvs = recv_pool.make_obj();
00560         parent->route(x,src,*recvs);
00561         // Deliver the event to each of its targets
00562         Atomic<X,T>* amodel = NULL;
00563         typename Bag<Event<X,T> >::iterator recv_iter = recvs->begin();
00564         for (; recv_iter != recvs->end(); recv_iter++)
00565         {
00566                 // Check for self-influencing error condition
00567                 if (src == (*recv_iter).model)
00568                 {
00569                         exception err("Model tried to influence self",src);
00570                         throw err;
00571                 }
00576                 amodel = (*recv_iter).model->typeIsAtomic();
00577                 if (amodel != NULL)
00578                 {
00579                         // Inject it only if it is assigned to our processor
00580                         if (lps == NULL || amodel->getProc() == lps->lp->getID())
00581                                 inject_event(amodel,(*recv_iter).value);
00582                         // Otherwise tell the lp about it
00583                         else if (lps->out_flag != RESTORING_OUTPUT)
00584                                 lps->lp->notifyInput(amodel,(*recv_iter).value);
00585                 }
00586                 // if this is an external output from the parent model
00587                 else if ((*recv_iter).model == parent)
00588                 {
00589                         route(parent->getParent(),parent,(*recv_iter).value);
00590                 }
00591                 // otherwise it is an input to a coupled model
00592                 else
00593                 {
00594                         route((*recv_iter).model->typeIsNetwork(),
00595                         (*recv_iter).model,(*recv_iter).value);
00596                 }
00597         }
00598         recvs->clear();
00599         recv_pool.destroy_obj(recvs);
00600 }
00601 
00602 template <class X, class T>
00603 void Simulator<X,T>::exec_event(Atomic<X,T>* model, bool internal, T t)
00604 {
00605         if (!manage_lookahead_data(model)) return;
00606         // Compute the state change
00607         if (model->x == NULL)
00608         {
00609                 model->delta_int();
00610         }
00611         else if (internal)
00612         {
00613                 model->delta_conf(*(model->x));
00614         }
00615         else
00616         {
00617                 model->delta_ext(t-model->tL,*(model->x));
00618         }
00619         // Notify any listeners
00620         notify_state_listeners(model,t);
00621         // Check for a model transition
00622         if (model->model_transition() && model->getParent() != NULL)
00623         {
00624                 model_func_eval_set.insert(model->getParent());
00625         }
00626 }
00627 
00628 template <class X, class T>
00629 void Simulator<X,T>::getAllChildren(Network<X,T>* model, Set<Devs<X,T>*>& s)
00630 {
00631         Set<Devs<X,T>*> tmp;
00632         // Get the component set
00633         model->getComponents(tmp);
00634         // Find the components of type network and update s recursively
00635         typename Set<Devs<X,T>*>::iterator iter;
00636         for (iter = tmp.begin(); iter != tmp.end(); iter++)
00637         {
00638                 if ((*iter)->typeIsNetwork() != NULL)
00639                 {
00640                         getAllChildren((*iter)->typeIsNetwork(),s);
00641                 }
00642         }
00643         // Add all of the local level elements to s
00644         for (iter = tmp.begin(); iter != tmp.end(); iter++)
00645         {
00646                 s.insert(*iter);
00647         }
00648 }
00649 
00650 template <class X, class T>
00651 Simulator<X,T>::~Simulator()
00652 {
00653         // Clean up the models with stale IO
00654         typename Bag<Atomic<X,T>*>::iterator imm_iter;
00655         for (imm_iter = imm.begin(); imm_iter != imm.end(); imm_iter++)
00656         {
00657                 clean_up(*imm_iter);
00658         }
00659         for (imm_iter = activated.begin(); imm_iter != activated.end(); imm_iter++)
00660         {
00661                 clean_up(*imm_iter);
00662         }
00663 }
00664 
00665 template <class X, class T>
00666 Simulator<X,T>::Simulator(LogicalProcess<X,T>* lp):
00667         AbstractSimulator<X,T>()
00668 {
00669         lps = new lp_support;
00670         lps->lp = lp;
00671         lps->look_ahead = false;
00672         lps->stop_forced = false;
00673         lps->out_flag = OUTPUT_OK;
00674 }
00675 
00676 template <class X, class T>
00677 void Simulator<X,T>::beginLookahead()
00678 {
00679         if (lps == NULL)
00680         {
00681                 adevs::exception err("tried to lookahead without lp support");
00682                 throw err;
00683         }
00684         lps->look_ahead = true;
00685         if (!imm.empty())
00686                 lps->out_flag = OUTPUT_NOT_OK; 
00687 }
00688 
00689 template <class X, class T>
00690 void Simulator<X,T>::lookNextEvent()
00691 {
00692         execNextEvent();
00693 }
00694 
00695 template <class X, class T>
00696 void Simulator<X,T>::endLookahead()
00697 {
00698         if (lps == NULL) return;
00699         typename Bag<Atomic<X,T>*>::iterator iter = lps->to_restore.begin();
00700         for (; iter != lps->to_restore.end(); iter++)
00701         {
00702                 (*iter)->endLookahead();
00703                 schedule(*iter,(*iter)->tL_cp);
00704                 (*iter)->tL_cp = adevs_sentinel<T>();
00705                 assert((*iter)->x == NULL);
00706                 assert((*iter)->y == NULL);
00707         }
00708         lps->to_restore.clear();
00709         assert(imm.empty());
00710         if (lps->out_flag == OUTPUT_NOT_OK)
00711         {
00712                 lps->out_flag = RESTORING_OUTPUT;
00713                 computeNextOutput();
00714                 lps->out_flag = OUTPUT_OK;
00715         }
00716         lps->look_ahead = false;
00717         lps->stop_forced = false;
00718 }
00719 
00720 template <class X, class T>
00721 bool Simulator<X,T>::manage_lookahead_data(Atomic<X,T>* model)
00722 {
00723         if (lps == NULL) return true;
00724         if (lps->look_ahead && model->tL_cp < adevs_zero<T>())
00725         {
00726                 lps->to_restore.insert(model);
00727                 model->tL_cp = model->tL;
00728                 try
00729                 {
00730                         model->beginLookahead();
00731                 }
00732                 catch(method_not_supported_exception err)
00733                 {
00734                         lps->stop_forced = true;
00735                 }
00736         }
00737         return !(lps->stop_forced);
00738 }
00739 
00740 } // End of namespace
00741 
00742 #endif