adevs
adevs_simulator.h
1 
31 #ifndef __adevs_simulator_h_
32 #define __adevs_simulator_h_
33 #include "adevs_abstract_simulator.h"
34 #include "adevs_models.h"
35 #include "adevs_event_listener.h"
36 #include "adevs_sched.h"
37 #include "adevs_bag.h"
38 #include "adevs_set.h"
39 #include "object_pool.h"
40 #include "adevs_lp.h"
41 #include <cassert>
42 #include <cstdlib>
43 #include <iostream>
44 #include <vector>
45 
46 namespace adevs
47 {
48 
56 template <class X, class T = double> class Simulator:
57  public AbstractSimulator<X,T>,
58  private Schedule<X,T>::ImminentVisitor
59 {
60  public:
68  AbstractSimulator<X,T>(),
69  Schedule<X,T>::ImminentVisitor(),
70  lps(NULL),
71  io_up_to_date(false)
72  {
73  schedule(model,adevs_zero<T>());
74  }
80  {
81  return sched.minPriority();
82  }
85  {
87  }
89  void execUntil(T tend)
90  {
91  while (nextEventTime() <= tend
92  && nextEventTime() < adevs_inf<T>()) {
93  execNextEvent();
94  }
95  }
101  void computeNextOutput();
113  void computeNextOutput(Bag<Event<X,T> >& input, T t);
125  void computeNextState(Bag<Event<X,T> >& input, T t);
133  void computeNextState();
139  ~Simulator();
144  void addModel(Atomic<X,T>* model)
145  {
146  schedule(model,adevs_zero<T>());
147  }
152  Simulator(LogicalProcess<X,T>* lp);
166  void beginLookahead();
171  void endLookahead();
178  void lookNextEvent();
179  private:
180  typedef enum { OUTPUT_OK, OUTPUT_NOT_OK, RESTORING_OUTPUT } OutputStatus;
181  // Structure to support parallel computing by a logical process
182  struct lp_support
183  {
184  // The processor that this simulator works for
185  LogicalProcess<X,T>* lp;
186  bool look_ahead, stop_forced;
187  OutputStatus out_flag;
188  Bag<Atomic<X,T>*> to_restore;
189  };
190  // This is NULL if the simulator is not supporting a logical process
191  lp_support* lps;
192  // Bogus input bag for execNextEvent() method
193  Bag<Event<X,T> > bogus_input;
194  // The event schedule
195  Schedule<X,T> sched;
196  // List of models that are imminent or activated by input
197  Bag<Atomic<X,T>*> activated;
198  // Mealy systems that we need to process
199  bool allow_mealy_input, io_up_to_date;
200  T io_time;
201  Bag<MealyAtomic<X,T>*> mealy;
202  // Pools of preallocated, commonly used objects
203  object_pool<Bag<X> > io_pool;
204  object_pool<Bag<Event<X,T> > > recv_pool;
205  // Sets for computing structure changes.
206  Bag<Devs<X,T>*> added;
207  Bag<Devs<X,T>*> removed;
208  Set<Devs<X,T>*> next;
209  Set<Devs<X,T>*> prev;
210  // Model transition functions are evaluated from the bottom up!
211  struct bottom_to_top_depth_compare
212  {
213  bool operator()(const Network<X,T>* m1, const Network<X,T>* m2) const
214  {
215  unsigned long int d1 = 0, d2 = 0;
216  // Compute depth of m1
217  const Network<X,T>* m = m1->getParent();
218  while (m != NULL)
219  {
220  d1++;
221  m = m->getParent();
222  }
223  // Compute depth of m2
224  m = m2->getParent();
225  while (m != NULL)
226  {
227  d2++;
228  m = m->getParent();
229  }
230  // Models at the same depth are sorted by name
231  if (d1 == d2) return m1 < m2;
232  // Otherwise, sort by depth
233  return d1 > d2;
234  }
235  };
236  struct top_to_bottom_depth_compare
237  {
238  bool operator()(const Devs<X,T>* m1, const Devs<X,T>* m2) const
239  {
240  unsigned long int d1 = 0, d2 = 0;
241  // Compute depth of m1
242  const Network<X,T>* m = m1->getParent();
243  while (m != NULL)
244  {
245  d1++;
246  m = m->getParent();
247  }
248  // Compute depth of m2
249  m = m2->getParent();
250  while (m != NULL)
251  {
252  d2++;
253  m = m->getParent();
254  }
255  // Models at the same depth are sorted by name
256  if (d1 == d2) return m1 < m2;
257  // Otherwise, sort by depth
258  return d1 < d2;
259  }
260  };
261  std::set<Network<X,T>*,bottom_to_top_depth_compare> model_func_eval_set;
262  std::set<Devs<X,T>*,top_to_bottom_depth_compare> sorted_removed;
267  void schedule(Devs<X,T>* model, T t);
269  void route(Network<X,T>* parent, Devs<X,T>* src, X& x);
275  void inject_event(Atomic<X,T>* model, X& value);
280  void unschedule_model(Devs<X,T>* model);
286  void clean_up(Devs<X,T>* model);
293  void exec_event(Atomic<X,T>* model, T t);
297  void getAllChildren(Network<X,T>* model, Set<Devs<X,T>*>& s);
303  bool manage_lookahead_data(Atomic<X,T>* model);
307  void visit(Atomic<X,T>* model);
308 };
309 
310 template <class X, class T>
312 {
313  assert(model->y == NULL);
314  // Mealy models are processed after the Moore models
315  if (model->typeIsMealyAtomic() != NULL)
316  {
317  model->typeIsMealyAtomic()->imm = true;
318  assert(model->y == NULL);
319  // May be in the mealy list because of a route call
320  if (model->x == NULL)
321  mealy.insert(model->typeIsMealyAtomic());
322  return;
323  }
324  model->y = io_pool.make_obj();
325  // Put it in the active list if it is not already there
326  if (model->x == NULL)
327  activated.insert(model);
328  // Compute output functions and route the events. The bags of output
329  // are held for garbage collection at a later time.
330  model->output_func(*(model->y));
331  // Route each event in y
332  for (typename Bag<X>::iterator y_iter = model->y->begin();
333  y_iter != model->y->end(); y_iter++)
334  {
335  route(model->getParent(),model,*y_iter);
336  }
337 }
338 
339 template <class X, class T>
341 {
342  // Undo any prior output calculation at another time
343  if (io_up_to_date && !(io_time == t))
344  {
345  typename Bag<Atomic<X,T>*>::iterator iter;
346  for (iter = activated.begin(); iter != activated.end(); iter++)
347  {
348  clean_up(*iter);
349  }
350  activated.clear();
351  }
352  // Get the imminent Moore models from the schedule if we have not
353  // already done so.
354  allow_mealy_input = true;
355  if (t == sched.minPriority() && !io_up_to_date)
356  sched.visitImminent(this);
357  // Apply the injected inputs
358  for (typename Bag<Event<X,T> >::iterator iter = input.begin();
359  iter != input.end(); iter++)
360  {
361  Atomic<X,T>* amodel = (*iter).model->typeIsAtomic();
362  if (amodel != NULL)
363  {
364  inject_event(amodel,(*iter).value);
365  }
366  else
367  {
368  route((*iter).model->typeIsNetwork(),(*iter).model,(*iter).value);
369  }
370  }
371  // Only Moore models can influence Mealy models.
372  allow_mealy_input = false;
373  // Iterate over activated Mealy models to calculate their output
374  for (typename Bag<MealyAtomic<X,T>*>::iterator m_iter = mealy.begin();
375  m_iter != mealy.end(); m_iter++)
376  {
377  MealyAtomic<X,T> *model = *m_iter;
378  assert(model->y == NULL);
379  model->y = io_pool.make_obj();
380  // Put it in the active set if it is not already there
381  if (model->x == NULL)
382  activated.insert(model);
383  // Compute output functions and route the events. The bags of output
384  // are held for garbage collection at a later time.
385  if (model->imm) // These are the imminent Mealy models
386  {
387  if (model->x == NULL)
388  model->typeIsAtomic()->output_func(*(model->y));
389  else
390  model->output_func(*(model->x),*(model->y));
391  model->imm = false;
392  }
393  else
394  {
395  assert(model->x != NULL);
396  // These are the Mealy models activated by input
397  model->output_func(sched.minPriority()-model->tL,*(model->x),*(model->y));
398  }
399  }
400  // Translate Mealy output to inputs for Moore models. The route method
401  // will throw an exception if an event is sent to a Mealy model.
402  for (typename Bag<MealyAtomic<X,T>*>::iterator m_iter = mealy.begin();
403  m_iter != mealy.end(); m_iter++)
404  {
405  MealyAtomic<X,T> *model = *m_iter;
406  // Route each event in y
407  for (typename Bag<X>::iterator y_iter = model->y->begin();
408  y_iter != model->y->end(); y_iter++)
409  {
410  route(model->getParent(),model,*y_iter);
411  }
412  }
413  mealy.clear();
414  // Record the time of the input
415  io_up_to_date = true;
416  io_time = t;
417 
418 }
419 
420 template<class X, class T>
422 {
423  computeNextOutput(bogus_input,sched.minPriority());
424 }
425 
426 template <class X, class T>
428 {
429  computeNextOutput(input,t);
430  assert(io_time == t && io_up_to_date);
432 }
433 
434 template <class X, class T>
436 {
437  if (!io_up_to_date)
439  io_up_to_date = false;
440  T t = io_time;
441  /*
442  * Compute the states of atomic models. Store Network models that
443  * need to have their model transition function evaluated in a
444  * special container that will be used when the structure changes are
445  * computed (see exec_event(.)).
446  */
447  for (typename Bag<Atomic<X,T>*>::iterator iter = activated.begin();
448  iter != activated.end(); iter++)
449  {
450  exec_event(*iter,t);
451  }
455  t = t + adevs_epsilon<T>();
462  if (model_func_eval_set.empty() == false)
463  {
464  while (!model_func_eval_set.empty())
465  {
466  Network<X,T>* network_model = *(model_func_eval_set.begin());
467  model_func_eval_set.erase(model_func_eval_set.begin());
468  getAllChildren(network_model,prev);
469  if (network_model->model_transition() &&
470  network_model->getParent() != NULL)
471  {
472  model_func_eval_set.insert(network_model->getParent());
473  }
474  getAllChildren(network_model,next);
475  }
476  // Find the set of models that were added.
477  set_assign_diff(added,next,prev);
478  // Find the set of models that were removed
479  set_assign_diff(removed,prev,next);
480  // Intersection of added and removed is always empty, so no need to look
481  // for models in both (an earlier version of the code did this).
482  next.clear();
483  prev.clear();
490  for (typename Bag<Devs<X,T>*>::iterator iter = added.begin();
491  iter != added.end(); iter++)
492  {
493  schedule(*iter,t);
494  }
495  // Done with the additions
496  added.clear();
497  // Remove the models that are in the removed set.
498  for (typename Bag<Devs<X,T>*>::iterator iter = removed.begin();
499  iter != removed.end(); iter++)
500  {
501  clean_up(*iter);
502  unschedule_model(*iter);
503  // Add to a sorted remove set for deletion
504  sorted_removed.insert(*iter);
505  }
506  // Done with the unsorted remove set
507  removed.clear();
508  // Delete the sorted removed models
509  while (!sorted_removed.empty())
510  {
511  // Get the model to erase
512  Devs<X,T>* model_to_remove = *(sorted_removed.begin());
513  // Remove the model
514  sorted_removed.erase(sorted_removed.begin());
519  if (model_to_remove->typeIsNetwork() != NULL)
520  {
521  getAllChildren(model_to_remove->typeIsNetwork(),prev);
522  typename Set<Devs<X,T>*>::iterator iter = prev.begin();
523  for (; iter != prev.end(); iter++)
524  sorted_removed.erase(*iter);
525  prev.clear();
526  }
527  // Delete the model and its children
528  delete model_to_remove;
529  }
530  // Removed sets should be empty now
531  assert(prev.empty());
532  assert(sorted_removed.empty());
533  } // End of the structure change
534  // Cleanup and reschedule models that changed state in this iteration
535  // and survived the structure change phase.
536  for (typename Bag<Atomic<X,T>*>::iterator iter = activated.begin();
537  iter != activated.end(); iter++)
538  {
539  clean_up(*iter);
540  schedule(*iter,t);
541  }
542  // Empty the bags
543  activated.clear();
544  // If we are looking ahead, throw an exception if a stop was forced
545  if (lps != NULL && lps->stop_forced)
546  {
548  throw err;
549  }
550 }
551 
552 template <class X, class T>
554 {
555  Atomic<X,T>* amodel = model->typeIsAtomic();
556  if (amodel != NULL)
557  {
558  if (amodel->x != NULL)
559  {
560  amodel->x->clear();
561  io_pool.destroy_obj(amodel->x);
562  amodel->x = NULL;
563  }
564  if (amodel->y != NULL)
565  {
566  amodel->gc_output(*(amodel->y));
567  amodel->y->clear();
568  io_pool.destroy_obj(amodel->y);
569  amodel->y = NULL;
570  }
571  if (amodel->typeIsMealyAtomic() != NULL)
572  {
573  amodel->typeIsMealyAtomic()->imm = false;
574  }
575  }
576  else
577  {
578  Set<Devs<X,T>*> components;
579  model->typeIsNetwork()->getComponents(components);
580  for (typename Set<Devs<X,T>*>::iterator iter = components.begin();
581  iter != components.end(); iter++)
582  {
583  clean_up(*iter);
584  }
585  }
586 }
587 
588 template <class X, class T>
590 {
591  if (model->typeIsAtomic() != NULL)
592  {
593  sched.schedule(model->typeIsAtomic(),adevs_inf<T>());
594  activated.erase(model->typeIsAtomic());
595  }
596  else
597  {
598  Set<Devs<X,T>*> components;
599  model->typeIsNetwork()->getComponents(components);
600  for (typename Set<Devs<X,T>*>::iterator iter = components.begin();
601  iter != components.end(); iter++)
602  {
603  unschedule_model(*iter);
604  }
605  }
606 }
607 
608 template <class X, class T>
609 void Simulator<X,T>::schedule(Devs<X,T>* model, T t)
610 {
611  Atomic<X,T>* a = model->typeIsAtomic();
612  if (a != NULL)
613  {
614  a->tL = t;
615  T dt = a->ta();
616  if (dt == adevs_inf<T>())
617  {
618  sched.schedule(a,adevs_inf<T>());
619  }
620  else
621  {
622  T tNext = a->tL+dt;
623  if (tNext < a->tL)
624  {
625  exception err("Negative time advance",a);
626  throw err;
627  }
628  sched.schedule(a,tNext);
629  }
630  }
631  else
632  {
633  Set<Devs<X,T>*> components;
634  model->typeIsNetwork()->getComponents(components);
635  typename Set<Devs<X,T>*>::iterator iter = components.begin();
636  for (; iter != components.end(); iter++)
637  {
638  schedule(*iter,t);
639  }
640  }
641 }
642 
643 template <class X, class T>
644 void Simulator<X,T>::inject_event(Atomic<X,T>* model, X& value)
645 {
646  // If this is a Mealy model, add it to the list of models that
647  // will need their input calculated
648  if (model->typeIsMealyAtomic())
649  {
650  if (allow_mealy_input)
651  {
652  assert(model->y == NULL);
653  // Add it to the list of its not already there
654  if (model->x == NULL && !model->typeIsMealyAtomic()->imm)
655  mealy.insert(model->typeIsMealyAtomic());
656  }
657  else
658  {
659  exception err("Mealy model coupled to a Mealy model",model);
660  throw err;
661  }
662  }
663  // Add the output to the model's bag of output to be processed
664  if (model->x == NULL)
665  {
666  if (model->y == NULL)
667  activated.insert(model);
668  model->x = io_pool.make_obj();
669  }
670  model->x->insert(value);
671 }
672 
673 template <class X, class T>
674 void Simulator<X,T>::route(Network<X,T>* parent, Devs<X,T>* src, X& x)
675 {
676  // Notify event listeners if this is an output event
677  if (parent != src && (lps == NULL || lps->out_flag != RESTORING_OUTPUT))
678  this->notify_output_listeners(src,x,sched.minPriority());
679  // No one to do the routing, so return
680  if (parent == NULL) return;
681  // Compute the set of receivers for this value
682  Bag<Event<X,T> >* recvs = recv_pool.make_obj();
683  parent->route(x,src,*recvs);
684  // Deliver the event to each of its targets
685  Atomic<X,T>* amodel = NULL;
686  typename Bag<Event<X,T> >::iterator recv_iter = recvs->begin();
687  for (; recv_iter != recvs->end(); recv_iter++)
688  {
689  // Check for self-influencing error condition
690  if (src == (*recv_iter).model)
691  {
692  exception err("Model tried to influence self",src);
693  throw err;
694  }
699  amodel = (*recv_iter).model->typeIsAtomic();
700  if (amodel != NULL)
701  {
702  // Inject it only if it is assigned to our processor
703  if (lps == NULL || amodel->getProc() == lps->lp->getID())
704  inject_event(amodel,(*recv_iter).value);
705  // Otherwise tell the lp about it
706  else if (lps->out_flag != RESTORING_OUTPUT)
707  lps->lp->notifyInput(amodel,(*recv_iter).value);
708  }
709  // if this is an external output from the parent model
710  else if ((*recv_iter).model == parent)
711  {
712  route(parent->getParent(),parent,(*recv_iter).value);
713  }
714  // otherwise it is an input to a coupled model
715  else
716  {
717  route((*recv_iter).model->typeIsNetwork(),
718  (*recv_iter).model,(*recv_iter).value);
719  }
720  }
721  recvs->clear();
722  recv_pool.destroy_obj(recvs);
723 }
724 
725 template <class X, class T>
726 void Simulator<X,T>::exec_event(Atomic<X,T>* model, T t)
727 {
728  if (!manage_lookahead_data(model)) return;
729  // Internal event
730  if (model->x == NULL)
731  model->delta_int();
732  // Confluent event
733  else if (model->y != NULL)
734  model->delta_conf(*(model->x));
735  // External event
736  else
737  model->delta_ext(t-model->tL,*(model->x));
738  // Notify any listeners of the new state at t+eps
739  this->notify_state_listeners(model,t+adevs_epsilon<T>());
740  // Check for a model transition
741  if (model->model_transition() && model->getParent() != NULL)
742  {
743  model_func_eval_set.insert(model->getParent());
744  }
745 }
746 
747 template <class X, class T>
749 {
750  Set<Devs<X,T>*> tmp;
751  // Get the component set
752  model->getComponents(tmp);
753  // Add all of the local level elements to s
754  s.insert(tmp.begin(),tmp.end());
755  // Find the components of type network and update s recursively
756  typename Set<Devs<X,T>*>::iterator iter;
757  for (iter = tmp.begin(); iter != tmp.end(); iter++)
758  {
759  if ((*iter)->typeIsNetwork() != NULL)
760  {
761  getAllChildren((*iter)->typeIsNetwork(),s);
762  }
763  }
764 }
765 
766 template <class X, class T>
768 {
769  // Clean up the models with stale IO
770  typename Bag<Atomic<X,T>*>::iterator iter;
771  for (iter = activated.begin(); iter != activated.end(); iter++)
772  {
773  clean_up(*iter);
774  }
775 }
776 
777 template <class X, class T>
778 Simulator<X,T>::Simulator(LogicalProcess<X,T>* lp):
779  AbstractSimulator<X,T>()
780 {
781  io_up_to_date = false;
782  io_time = adevs_zero<T>();
783  lps = new lp_support;
784  lps->lp = lp;
785  lps->look_ahead = false;
786  lps->stop_forced = false;
787  lps->out_flag = OUTPUT_OK;
788 }
789 
790 template <class X, class T>
792 {
793  if (lps == NULL)
794  {
795  adevs::exception err("tried to lookahead without lp support");
796  throw err;
797  }
798  lps->look_ahead = true;
799  if (!activated.empty())
800  lps->out_flag = OUTPUT_NOT_OK;
801 }
802 
803 template <class X, class T>
805 {
806  execNextEvent();
807 }
808 
809 template <class X, class T>
811 {
812  if (lps == NULL) return;
813  typename Bag<Atomic<X,T>*>::iterator iter = lps->to_restore.begin();
814  for (; iter != lps->to_restore.end(); iter++)
815  {
816  (*iter)->endLookahead();
817  schedule(*iter,(*iter)->tL_cp);
818  (*iter)->tL_cp = adevs_sentinel<T>();
819  assert((*iter)->x == NULL);
820  assert((*iter)->y == NULL);
821  }
822  lps->to_restore.clear();
823  assert(activated.empty());
824  if (lps->out_flag == OUTPUT_NOT_OK)
825  {
826  lps->out_flag = RESTORING_OUTPUT;
828  lps->out_flag = OUTPUT_OK;
829  }
830  lps->look_ahead = false;
831  lps->stop_forced = false;
832 }
833 
834 template <class X, class T>
836 {
837  if (lps == NULL) return true;
838  if (lps->look_ahead && model->tL_cp < adevs_zero<T>())
839  {
840  lps->to_restore.insert(model);
841  model->tL_cp = model->tL;
842  try
843  {
844  model->beginLookahead();
845  }
847  {
848  lps->stop_forced = true;
849  }
850  }
851  return !(lps->stop_forced);
852 }
853 
854 } // End of namespace
855 
856 #endif
Atomic< X, T > * typeIsAtomic()
Returns a pointer to this model.
Definition: adevs_models.h:258
Definition: adevs_models.h:50
virtual void output_func(T e, const Bag< X > &xb, Bag< X > &yb)=0
virtual void route(const X &value, Devs< X, T > *model, Bag< Event< X, T > > &r)=0
Definition: adevs_abstract_simulator.h:45
Definition: adevs_set.h:42
void execNextEvent()
Execute the simulation cycle at time nextEventTime()
Definition: adevs_simulator.h:84
void beginLookahead()
Definition: adevs_simulator.h:791
void lookNextEvent()
Definition: adevs_simulator.h:804
void computeNextOutput()
Definition: adevs_simulator.h:421
Definition: adevs_models.h:46
void clear()
Remove all of the elements from the bag.
Definition: adevs_bag.h:144
virtual void gc_output(Bag< X > &g)=0
void notify_output_listeners(Devs< X, T > *model, const X &value, T t)
Notify listeners of an output event.
Definition: adevs_abstract_simulator.h:79
void addModel(Atomic< X, T > *model)
Definition: adevs_simulator.h:144
int getProc()
Definition: adevs_models.h:133
virtual void delta_int()=0
Internal transition function.
iterator begin() const
Get an iterator pointing to the first element in the bag.
Definition: adevs_bag.h:128
virtual void getComponents(Set< Devs< X, T > * > &c)=0
Definition: adevs_exception.h:43
virtual MealyAtomic< X, T > * typeIsMealyAtomic()
Returns NULL if this is not a mealy atomic model; returns itself otherwise.
Definition: adevs_models.h:86
Definition: adevs_models.h:49
iterator end() const
Get an iterator to the end of the bag (i.e., just after the last element)
Definition: adevs_bag.h:130
Definition: adevs_exception.h:80
virtual void output_func(Bag< X > &yb)=0
virtual Network< X, T > * typeIsNetwork()
Definition: adevs_models.h:82
virtual T ta()=0
Definition: adevs_fmi.h:56
virtual bool model_transition()
Definition: adevs_models.h:113
void set_assign_diff(Bag< T > &result, const Set< T > &A, const Set< T > &B)
Set difference operator. Returns the set A-B.
Definition: adevs_set.h:48
virtual void beginLookahead()
Definition: adevs_models.h:243
T nextEventTime()
Definition: adevs_simulator.h:79
void execUntil(T tend)
Execute until nextEventTime() > tend.
Definition: adevs_simulator.h:89
virtual Atomic< X, T > * typeIsAtomic()
Returns NULL if this is not an atomic model; returns itself otherwise.
Definition: adevs_models.h:84
~Simulator()
Definition: adevs_simulator.h:767
virtual void delta_ext(T e, const Bag< X > &xb)=0
Definition: adevs_models.h:64
virtual void delta_conf(const Bag< X > &xb)=0
Definition: adevs_models.h:145
void computeNextState()
Definition: adevs_simulator.h:435
void endLookahead()
Definition: adevs_simulator.h:810
void insert(const T &t)
Put t into the bag.
Definition: adevs_bag.h:153
Definition: adevs_models.h:47
Simulator(Devs< X, T > *model)
Definition: adevs_simulator.h:67
Definition: adevs_exception.h:99
const Network< X, T > * getParent() const
Definition: adevs_models.h:91
void notify_state_listeners(Atomic< X, T > *model, T t)
Notify listeners of a state change.
Definition: adevs_abstract_simulator.h:90
Definition: adevs_models.h:48
Definition: adevs_bag.h:45