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 <cassert>
41 #include <cstdlib>
42 #include <iostream>
43 #include <vector>
44 
45 namespace adevs
46 {
47 
55 template <class X, class T = double> class Simulator:
56  public AbstractSimulator<X,T>,
57  private Schedule<X,T>::ImminentVisitor
58 {
59  public:
67  AbstractSimulator<X,T>(),
68  Schedule<X,T>::ImminentVisitor(),
69  io_up_to_date(false)
70  {
71  schedule(model,adevs_zero<T>());
72  }
78  {
79  return sched.minPriority();
80  }
83  {
85  }
87  void execUntil(T tend)
88  {
89  while (nextEventTime() <= tend
90  && nextEventTime() < adevs_inf<T>()) {
91  execNextEvent();
92  }
93  }
99  void computeNextOutput();
111  void computeNextOutput(Bag<Event<X,T> >& input, T t);
123  void computeNextState(Bag<Event<X,T> >& input, T t);
131  void computeNextState();
137  ~Simulator();
142  void addModel(Atomic<X,T>* model)
143  {
144  schedule(model,adevs_zero<T>());
145  }
146  private:
147  // Bogus input bag for execNextEvent() method
148  Bag<Event<X,T> > bogus_input;
149  // The event schedule
150  #ifdef _OPENMP
151  MultiSchedule<X,T> sched;
152  #else
153  Schedule<X,T> sched;
154  #endif
155  // List of models that are imminent or activated by input
156  Bag<Atomic<X,T>*> activated;
157  // Mealy systems that we need to process
158  bool allow_mealy_input, io_up_to_date;
159  T io_time;
160  Bag<MealyAtomic<X,T>*> mealy;
161  // Pools of preallocated, commonly used objects
162  object_pool<Bag<X> > io_pool;
163  object_pool<Bag<Event<X,T> > > recv_pool;
164  // Sets for computing structure changes.
165  Bag<Devs<X,T>*> added;
166  Bag<Devs<X,T>*> removed;
167  Set<Devs<X,T>*> next;
168  Set<Devs<X,T>*> prev;
169  // Model transition functions are evaluated from the bottom up!
170  struct bottom_to_top_depth_compare
171  {
172  bool operator()(const Network<X,T>* m1, const Network<X,T>* m2) const
173  {
174  unsigned long int d1 = 0, d2 = 0;
175  // Compute depth of m1
176  const Network<X,T>* m = m1->getParent();
177  while (m != NULL)
178  {
179  d1++;
180  m = m->getParent();
181  }
182  // Compute depth of m2
183  m = m2->getParent();
184  while (m != NULL)
185  {
186  d2++;
187  m = m->getParent();
188  }
189  // Models at the same depth are sorted by name
190  if (d1 == d2) return m1 < m2;
191  // Otherwise, sort by depth
192  return d1 > d2;
193  }
194  };
195  struct top_to_bottom_depth_compare
196  {
197  bool operator()(const Devs<X,T>* m1, const Devs<X,T>* m2) const
198  {
199  unsigned long int d1 = 0, d2 = 0;
200  // Compute depth of m1
201  const Network<X,T>* m = m1->getParent();
202  while (m != NULL)
203  {
204  d1++;
205  m = m->getParent();
206  }
207  // Compute depth of m2
208  m = m2->getParent();
209  while (m != NULL)
210  {
211  d2++;
212  m = m->getParent();
213  }
214  // Models at the same depth are sorted by name
215  if (d1 == d2) return m1 < m2;
216  // Otherwise, sort by depth
217  return d1 < d2;
218  }
219  };
220  std::set<Network<X,T>*,bottom_to_top_depth_compare> model_func_eval_set;
221  std::set<Devs<X,T>*,top_to_bottom_depth_compare> sorted_removed;
226  void schedule(Devs<X,T>* model, T t);
228  void route(Network<X,T>* parent, Devs<X,T>* src, X& x);
234  void inject_event(Atomic<X,T>* model, X& value);
239  void unschedule_model(Devs<X,T>* model);
245  void clean_up(Devs<X,T>* model);
249  void getAllChildren(Network<X,T>* model, Set<Devs<X,T>*>& s);
253  void visit(Atomic<X,T>* model);
254 };
255 
256 template <class X, class T>
258 {
259  assert(model->y == NULL);
260  // Mealy models are processed after the Moore models
261  if (model->typeIsMealyAtomic() != NULL)
262  {
263  model->typeIsMealyAtomic()->imm = true;
264  assert(model->y == NULL);
265  // May be in the mealy list because of a route call
266  if (model->x == NULL)
267  mealy.insert(model->typeIsMealyAtomic());
268  return;
269  }
270  model->y = io_pool.make_obj();
271  // Put it in the active list if it is not already there
272  if (model->x == NULL)
273  activated.insert(model);
274  // Compute output functions and route the events. The bags of output
275  // are held for garbage collection at a later time.
276  model->output_func(*(model->y));
277  // Route each event in y
278  for (typename Bag<X>::iterator y_iter = model->y->begin();
279  y_iter != model->y->end(); y_iter++)
280  {
281  route(model->getParent(),model,*y_iter);
282  }
283 }
284 
285 template <class X, class T>
287 {
288  // Undo any prior output calculation at another time
289  if (io_up_to_date && !(io_time == t))
290  {
291  typename Bag<Atomic<X,T>*>::iterator iter;
292  for (iter = activated.begin(); iter != activated.end(); iter++)
293  {
294  clean_up(*iter);
295  }
296  activated.clear();
297  }
298  // Get the imminent Moore models from the schedule if we have not
299  // already done so.
300  allow_mealy_input = true;
301  if (t == sched.minPriority() && !io_up_to_date)
302  sched.visitImminent(this);
303  // Apply the injected inputs
304  for (typename Bag<Event<X,T> >::iterator iter = input.begin();
305  iter != input.end(); iter++)
306  {
307  Atomic<X,T>* amodel = (*iter).model->typeIsAtomic();
308  if (amodel != NULL)
309  {
310  inject_event(amodel,(*iter).value);
311  }
312  else
313  {
314  route((*iter).model->typeIsNetwork(),(*iter).model,(*iter).value);
315  }
316  }
317  // Only Moore models can influence Mealy models.
318  allow_mealy_input = false;
319  // Iterate over activated Mealy models to calculate their output
320  for (typename Bag<MealyAtomic<X,T>*>::iterator m_iter = mealy.begin();
321  m_iter != mealy.end(); m_iter++)
322  {
323  MealyAtomic<X,T> *model = *m_iter;
324  assert(model->y == NULL);
325  model->y = io_pool.make_obj();
326  // Put it in the active set if it is not already there
327  if (model->x == NULL)
328  activated.insert(model);
329  // Compute output functions and route the events. The bags of output
330  // are held for garbage collection at a later time.
331  if (model->imm) // These are the imminent Mealy models
332  {
333  if (model->x == NULL)
334  model->typeIsAtomic()->output_func(*(model->y));
335  else
336  model->output_func(*(model->x),*(model->y));
337  model->imm = false;
338  }
339  else
340  {
341  assert(model->x != NULL);
342  // These are the Mealy models activated by input
343  model->output_func(sched.minPriority()-model->tL,*(model->x),*(model->y));
344  }
345  }
346  // Translate Mealy output to inputs for Moore models. The route method
347  // will throw an exception if an event is sent to a Mealy model.
348  for (typename Bag<MealyAtomic<X,T>*>::iterator m_iter = mealy.begin();
349  m_iter != mealy.end(); m_iter++)
350  {
351  MealyAtomic<X,T> *model = *m_iter;
352  // Route each event in y
353  for (typename Bag<X>::iterator y_iter = model->y->begin();
354  y_iter != model->y->end(); y_iter++)
355  {
356  route(model->getParent(),model,*y_iter);
357  }
358  }
359  mealy.clear();
360  // Record the time of the input
361  io_up_to_date = true;
362  io_time = t;
363 
364 }
365 
366 template<class X, class T>
368 {
369  computeNextOutput(bogus_input,sched.minPriority());
370 }
371 
372 template <class X, class T>
374 {
375  computeNextOutput(input,t);
376  assert(io_time == t && io_up_to_date);
378 }
379 
380 template <class X, class T>
382 {
383  if (!io_up_to_date)
385  io_up_to_date = false;
386  T t = io_time, tQ = io_time + adevs_epsilon<T>();
387  /*
388  * Compute the states of atomic models. Store Network models that
389  * need to have their model transition function evaluated in a
390  * special container that will be used when the structure changes are
391  * computed.
392  */
393  #ifdef _OPENMP
394  #pragma omp parallel for
395  #endif
396  for (unsigned i = 0; i < activated.size(); i++)
397  {
398  Atomic<X,T>* model = activated[i];
399  // Internal event
400  if (model->x == NULL)
401  model->delta_int();
402  // Confluent event
403  else if (model->y != NULL)
404  model->delta_conf(*(model->x));
405  // External event
406  else
407  model->delta_ext(t-model->tL,*(model->x));
408  // Notify listeners
409  this->notify_state_listeners(model,tQ);
410  // Check for a model transition
411  if (model->model_transition() && model->getParent() != NULL)
412  {
413  #ifdef _OPENMP
414  #pragma omp critical
415  #endif
416  model_func_eval_set.insert(model->getParent());
417  }
418  // Adjust position in the schedule
419  schedule(model,tQ);
420  }
424  t = tQ;
431  if (model_func_eval_set.empty() == false)
432  {
433  while (!model_func_eval_set.empty())
434  {
435  Network<X,T>* network_model = *(model_func_eval_set.begin());
436  model_func_eval_set.erase(model_func_eval_set.begin());
437  getAllChildren(network_model,prev);
438  if (network_model->model_transition() &&
439  network_model->getParent() != NULL)
440  {
441  model_func_eval_set.insert(network_model->getParent());
442  }
443  getAllChildren(network_model,next);
444  }
445  // Find the set of models that were added.
446  set_assign_diff(added,next,prev);
447  // Find the set of models that were removed
448  set_assign_diff(removed,prev,next);
449  // Intersection of added and removed is always empty, so no need to look
450  // for models in both (an earlier version of the code did this).
451  next.clear();
452  prev.clear();
459  for (typename Bag<Devs<X,T>*>::iterator iter = added.begin();
460  iter != added.end(); iter++)
461  {
462  schedule(*iter,t);
463  }
464  // Done with the additions
465  added.clear();
466  // Remove the models that are in the removed set.
467  for (typename Bag<Devs<X,T>*>::iterator iter = removed.begin();
468  iter != removed.end(); iter++)
469  {
470  clean_up(*iter);
471  unschedule_model(*iter);
472  // Add to a sorted remove set for deletion
473  sorted_removed.insert(*iter);
474  }
475  // Done with the unsorted remove set
476  removed.clear();
477  // Delete the sorted removed models
478  while (!sorted_removed.empty())
479  {
480  // Get the model to erase
481  Devs<X,T>* model_to_remove = *(sorted_removed.begin());
482  // Remove the model
483  sorted_removed.erase(sorted_removed.begin());
488  if (model_to_remove->typeIsNetwork() != NULL)
489  {
490  getAllChildren(model_to_remove->typeIsNetwork(),prev);
491  typename Set<Devs<X,T>*>::iterator iter = prev.begin();
492  for (; iter != prev.end(); iter++)
493  sorted_removed.erase(*iter);
494  prev.clear();
495  }
496  // Delete the model and its children
497  delete model_to_remove;
498  }
499  // Removed sets should be empty now
500  assert(prev.empty());
501  assert(sorted_removed.empty());
502  } // End of the structure change
503  // Cleanup and reschedule models that changed state in this iteration
504  // and survived the structure change phase.
505  for (typename Bag<Atomic<X,T>*>::iterator iter = activated.begin();
506  iter != activated.end(); iter++)
507  {
508  clean_up(*iter);
509  }
510  // Empty the bags
511  activated.clear();
512 }
513 
514 template <class X, class T>
516 {
517  Atomic<X,T>* amodel = model->typeIsAtomic();
518  if (amodel != NULL)
519  {
520  if (amodel->x != NULL)
521  {
522  amodel->x->clear();
523  io_pool.destroy_obj(amodel->x);
524  amodel->x = NULL;
525  }
526  if (amodel->y != NULL)
527  {
528  amodel->gc_output(*(amodel->y));
529  amodel->y->clear();
530  io_pool.destroy_obj(amodel->y);
531  amodel->y = NULL;
532  }
533  if (amodel->typeIsMealyAtomic() != NULL)
534  {
535  amodel->typeIsMealyAtomic()->imm = false;
536  }
537  }
538  else
539  {
540  Set<Devs<X,T>*> components;
541  model->typeIsNetwork()->getComponents(components);
542  for (typename Set<Devs<X,T>*>::iterator iter = components.begin();
543  iter != components.end(); iter++)
544  {
545  clean_up(*iter);
546  }
547  }
548 }
549 
550 template <class X, class T>
552 {
553  if (model->typeIsAtomic() != NULL)
554  {
555  sched.schedule(model->typeIsAtomic(),adevs_inf<T>());
556  activated.erase(model->typeIsAtomic());
557  }
558  else
559  {
560  Set<Devs<X,T>*> components;
561  model->typeIsNetwork()->getComponents(components);
562  for (typename Set<Devs<X,T>*>::iterator iter = components.begin();
563  iter != components.end(); iter++)
564  {
565  unschedule_model(*iter);
566  }
567  }
568 }
569 
570 template <class X, class T>
571 void Simulator<X,T>::schedule(Devs<X,T>* model, T t)
572 {
573  Atomic<X,T>* a = model->typeIsAtomic();
574  if (a != NULL)
575  {
576  a->tL = t;
577  T dt = a->ta();
578  if (dt == adevs_inf<T>())
579  {
580  sched.schedule(a,adevs_inf<T>());
581  }
582  else
583  {
584  T tNext = a->tL+dt;
585  if (tNext < a->tL)
586  {
587  exception err("Negative time advance",a);
588  throw err;
589  }
590  sched.schedule(a,tNext);
591  }
592  }
593  else
594  {
595  Set<Devs<X,T>*> components;
596  model->typeIsNetwork()->getComponents(components);
597  typename Set<Devs<X,T>*>::iterator iter = components.begin();
598  for (; iter != components.end(); iter++)
599  {
600  schedule(*iter,t);
601  }
602  }
603 }
604 
605 template <class X, class T>
606 void Simulator<X,T>::inject_event(Atomic<X,T>* model, X& value)
607 {
608  // If this is a Mealy model, add it to the list of models that
609  // will need their input calculated
610  if (model->typeIsMealyAtomic())
611  {
612  if (allow_mealy_input)
613  {
614  assert(model->y == NULL);
615  // Add it to the list of its not already there
616  if (model->x == NULL && !model->typeIsMealyAtomic()->imm)
617  mealy.insert(model->typeIsMealyAtomic());
618  }
619  else
620  {
621  exception err("Mealy model coupled to a Mealy model",model);
622  throw err;
623  }
624  }
625  // Add the output to the model's bag of output to be processed
626  if (model->x == NULL)
627  {
628  if (model->y == NULL)
629  activated.insert(model);
630  model->x = io_pool.make_obj();
631  }
632  model->x->insert(value);
633 }
634 
635 template <class X, class T>
636 void Simulator<X,T>::route(Network<X,T>* parent, Devs<X,T>* src, X& x)
637 {
638  // Notify event listeners if this is an output event
639  if (parent != src)
640  this->notify_output_listeners(src,x,sched.minPriority());
641  // No one to do the routing, so return
642  if (parent == NULL) return;
643  // Compute the set of receivers for this value
644  Bag<Event<X,T> >* recvs = recv_pool.make_obj();
645  parent->route(x,src,*recvs);
646  // Deliver the event to each of its targets
647  Atomic<X,T>* amodel = NULL;
648  typename Bag<Event<X,T> >::iterator recv_iter = recvs->begin();
649  for (; recv_iter != recvs->end(); recv_iter++)
650  {
651  // Check for self-influencing error condition
652  if (src == (*recv_iter).model)
653  {
654  exception err("Model tried to influence self",src);
655  throw err;
656  }
661  amodel = (*recv_iter).model->typeIsAtomic();
662  if (amodel != NULL)
663  {
664  inject_event(amodel,(*recv_iter).value);
665  }
666  // if this is an external output from the parent model
667  else if ((*recv_iter).model == parent)
668  {
669  route(parent->getParent(),parent,(*recv_iter).value);
670  }
671  // otherwise it is an input to a coupled model
672  else
673  {
674  route((*recv_iter).model->typeIsNetwork(),
675  (*recv_iter).model,(*recv_iter).value);
676  }
677  }
678  recvs->clear();
679  recv_pool.destroy_obj(recvs);
680 }
681 
682 template <class X, class T>
684 {
685  Set<Devs<X,T>*> tmp;
686  // Get the component set
687  model->getComponents(tmp);
688  // Add all of the local level elements to s
689  s.insert(tmp.begin(),tmp.end());
690  // Find the components of type network and update s recursively
691  typename Set<Devs<X,T>*>::iterator iter;
692  for (iter = tmp.begin(); iter != tmp.end(); iter++)
693  {
694  if ((*iter)->typeIsNetwork() != NULL)
695  {
696  getAllChildren((*iter)->typeIsNetwork(),s);
697  }
698  }
699 }
700 
701 template <class X, class T>
703 {
704  // Clean up the models with stale IO
705  typename Bag<Atomic<X,T>*>::iterator iter;
706  for (iter = activated.begin(); iter != activated.end(); iter++)
707  {
708  clean_up(*iter);
709  }
710 }
711 
712 } // End of namespace
713 
714 #endif
Atomic< X, T > * typeIsAtomic()
Returns a pointer to this model.
Definition: adevs_models.h:210
Definition: adevs_models.h:51
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:82
void computeNextOutput()
Definition: adevs_simulator.h:367
Definition: adevs_models.h:46
Definition: adevs_models.h:50
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:142
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:80
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
virtual void output_func(Bag< X > &yb)=0
virtual Network< X, T > * typeIsNetwork()
Definition: adevs_models.h:76
virtual T ta()=0
Definition: adevs_fmi.h:57
virtual bool model_transition()
Definition: adevs_models.h:107
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
T nextEventTime()
Definition: adevs_simulator.h:77
void execUntil(T tend)
Execute until nextEventTime() > tend.
Definition: adevs_simulator.h:87
virtual Atomic< X, T > * typeIsAtomic()
Returns NULL if this is not an atomic model; returns itself otherwise.
Definition: adevs_models.h:78
~Simulator()
Definition: adevs_simulator.h:702
virtual void delta_ext(T e, const Bag< X > &xb)=0
Definition: adevs_models.h:59
virtual void delta_conf(const Bag< X > &xb)=0
Definition: adevs_models.h:117
void computeNextState()
Definition: adevs_simulator.h:381
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:66
const Network< X, T > * getParent() const
Definition: adevs_models.h:85
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