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