adevs
|
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