AbstractSimObject.h

Go to the documentation of this file.

#ifndef _ABS_SIMOBJECT_H_
#define _ABS_SIMOBJECT_H_



#include <vector>
#include <queue>
#include <algorithm>

#include <cassert>

#include "Galois/Graphs/Graph.h"

#include "comDefs.h"
#include "Event.h"


#include "SimObject.h"



class AbstractSimObject: public SimObject {
private:
  
  template <typename T, typename Cmp> 
  class CustomPriorityQueue {

    Cmp cmp;
    std::vector<T> vec;
    
  public:
    typedef std::vector<T> container_type;

    typedef typename container_type::value_type value_type;
    typedef typename container_type::reference reference;
    typedef typename container_type::const_reference const_reference;
    typedef typename container_type::size_type size_type;


    CustomPriorityQueue (const Cmp& cmp = Cmp(), const std::vector<T>& vec = std::vector<T>()) 
      : cmp(cmp), vec(vec) {
      std::make_heap ( this->vec.begin (), this->vec.end (), cmp);
    }

    template <typename Iter> 
    CustomPriorityQueue (Iter b, Iter e, const Cmp& cmp = Cmp ()) : cmp (cmp) {
      vec.insert (vec.end (), b, e);

      std::make_heap (vec.begin (), vec.end (), cmp);
    }

    CustomPriorityQueue (const CustomPriorityQueue& that): cmp(that.cmp), vec (that.vec) {
    }


    bool empty () const {
      return vec.empty ();
    }

    size_type size () const {
      return vec.size ();
    }

    const_reference top () const {
      return vec.front ();
    }

    void push (const value_type& x) {
      vec.push_back (x);
      std::push_heap (vec.begin (), vec.end (), cmp);
    }

    void pop () {
      std::pop_heap (vec.begin (), vec.end (), cmp);

      vec.pop_back ();
    }

    void reserve (size_type s) {
      assert (s > 0);
      vec.reserve (s);
    }

  };

public:
  static size_t NEVENTS_PER_ITER;


private:

  static const bool DEBUG = false;

  static const size_t PQ_OVER_RESERVE = 1024;

  // typedef std::priority_queue<EventTy, std::vector<EventTy>, EventRecvTimeLocalTieBrkCmp<EventTy> > PriorityQueue;
  typedef CustomPriorityQueue<EventTy, EventRecvTimeLocalTieBrkCmp<EventTy> > PriorityQueue;

  size_t id;

  size_t numInputs;

  size_t numOutputs;

  // std::vector<PriorityQueue> inputEvents;

  std::vector<SimTime> inputTimes;

  SimTime clock;

  PriorityQueue pendingEvents;

  bool active;


  size_t eventIdCntr;

  void init(size_t id, size_t numOutputs, size_t numInputs) {
    eventIdCntr = 0; 
    this->id = id;

    assert (numOutputs == 1);
    this->numOutputs = numOutputs;

    this->numInputs = numInputs;


    inputTimes.resize (numInputs);

    for (size_t i = 0; i < numInputs; ++i) {
      inputTimes[i] = SimTime(0);
    }

    pendingEvents = PriorityQueue();

    // reserving space upfront to avoid memory allocation due to doubling of the PriorityQueue etc
    pendingEvents.reserve (numInputs * NEVENTS_PER_ITER * PQ_OVER_RESERVE);

    clock = 0;

  }

  void deepCopy(const AbstractSimObject& that) {

    init(that.id, that.numOutputs, that.numInputs);

    for (size_t i = 0; i < numInputs; ++i) {
      this->inputTimes[i] = that.inputTimes[i];
    }

    PriorityQueue cpyQ(that.pendingEvents);
    while (!cpyQ.empty ()) {
      this->pendingEvents.push (cpyQ.top ());
      cpyQ.pop ();
    }

    // defensive
    this->clock = that.clock;
  }

  void updateClock() {
    SimTime min = INFINITY_SIM_TIME;
    for (size_t i = 0; i < numInputs; ++i) {
      if (this->inputTimes[i] < min) {
        min = this->inputTimes[i];
      }
    }

    this->clock = min;
  }


  // void sendEvent(size_t outIndex, SimObject target, Event<?> e) {
    // //TODO: not implemented yet
  // }






public:
  AbstractSimObject(size_t id, size_t numOutputs, size_t numInputs): SimObject() {
    assert (numOutputs == 1);
    init(id, numOutputs, numInputs);
  }

  AbstractSimObject (const AbstractSimObject& that): SimObject (that) {
    deepCopy (that);
  }

  virtual ~AbstractSimObject () {}
  virtual AbstractSimObject* clone() const = 0;

   EventTy makeEvent(SimObject* sendObj, SimObject* recvObj, const EventTy::Type& type, const LogicUpdate&  act
      , const SimTime& sendTime, SimTime delay = MIN_DELAY) {

    assert (sendObj == this);

    if (delay <= 0) {
      delay = MIN_DELAY;
    }

    SimTime recvTime;
    if (sendTime == INFINITY_SIM_TIME) {
      recvTime = INFINITY_SIM_TIME;
    } else {
      recvTime = sendTime + delay;
    }
    return  EventTy((eventIdCntr++), sendObj, recvObj, act, type, sendTime, recvTime);
  }


  void recvEvent(size_t inputIndex, const EventTy& e) {

    assert (inputIndex >= 0 && inputIndex < numInputs);

    this->pendingEvents.push (e);

    if (this->inputTimes[inputIndex] < e.getRecvTime()) {
      this->inputTimes[inputIndex] = e.getRecvTime();
    }
  }

  virtual void execEvent(Graph& graph, GNode& myNode, const EventTy& e) = 0;

  size_t simulate(Graph& graph, GNode& myNode) {
    assert (isActive ());

    updateClock();// update the clock, 

    size_t retVal = 0;

    while ((!pendingEvents.empty())
        && (pendingEvents.top ().getRecvTime () <= this->clock)
        && (retVal < NEVENTS_PER_ITER)) {

      EventTy e = pendingEvents.top ();
      pendingEvents.pop ();

      //DEBUG
      if (!pendingEvents.empty ()) {
        const EventTy& curr = e;
        const EventTy& next = (pendingEvents.top ());

        // assert (EventRecvTimeLocalTieBrkCmp<EventTy> ().compare (prev, curr) < 0);
        if (EventRecvTimeLocalTieBrkCmp<EventTy> ().compare (curr, next) >= 0) {
          std::cerr << "EventRecvTimeLocalTieBrkCmp ().compare (curr, next) >= 0" << std::endl;
          std::cerr << "curr = " << curr.detailedString () << std::endl << "next = " << next.detailedString () << std::endl;
        }
      }


      assert (graph.getData(myNode, Galois::NONE) == this); // should already own a lock
      assert (e.getRecvObj () == this);

      execEvent(graph, myNode, e);

      ++retVal;
    }

    return (retVal);
  }




  bool isActive() const {
    return active;
  }

  void updateActive() {

    bool allEmpty = pendingEvents.empty ();

    bool isWaiting = false; // is Waiting on an input event

    if (allEmpty) {
      // pendingEvents is empty, but how do we know whether this is the beginning of simulation
      // or the end. In the beginning we are waiting on input events with empty queue in the
      // end we're not.
      // we are not waiting only if the time stamp of latest event is >= INFINITY_SIM_TIME
      for (size_t i = 0; i < numInputs; ++i) {
        if (inputTimes[i] <  INFINITY_SIM_TIME) {
          isWaiting = true;
          break;
        }
      }

    } else {
      // still some pending events to process
      // what we need to determine now is whether we can process the pending events safely
      // which can be determined by checking pendingEvents.top () against inputTimes[i] for input i
      // because if inputTimes[i] < pendingEvents.top () then we cannot safely process any
      // pendingEvents because there's a possibility of receiving more events on input i which have
      // a time stamp less that pendingEvents.top ()


      const SimTime& top = pendingEvents.top ().getRecvTime ();
      for (size_t i = 0; i < numInputs; ++i) {
        if (inputTimes[i] < top) {
          isWaiting = true;
          break;
        }
      }
    }


    active = !allEmpty && !isWaiting;
  }


  virtual size_t numPendingEvents () const { 
    return pendingEvents.size ();
  }

  virtual const std::string toString() const {
    std::ostringstream ss;
    ss << "SimObject-" << id << " ";
    if (DEBUG) {
      for (size_t i = 0; i < numInputs; ++i) {
        ss << ", inputTimes[" << i << "] = " << inputTimes[i];
      }
      ss << std::endl;

      ss << ", active = " << active << ", clock = " << clock << ", pendingEvents.size() = " << pendingEvents.size ()
          << ", pendingEvent.top () = " << pendingEvents.top ().toString () << std::endl;


    }

    return ss.str ();
  }

  size_t getId() const { return id; }

}; // end class


size_t AbstractSimObject::NEVENTS_PER_ITER = 1024;
#endif 

---