diff options
Diffstat (limited to 'src/mem/ruby/eventqueue')
-rw-r--r-- | src/mem/ruby/eventqueue/EventQueue.cc | 120 | ||||
-rw-r--r-- | src/mem/ruby/eventqueue/EventQueue.hh | 118 | ||||
-rw-r--r-- | src/mem/ruby/eventqueue/EventQueueNode.cc | 47 | ||||
-rw-r--r-- | src/mem/ruby/eventqueue/EventQueueNode.hh | 98 | ||||
-rw-r--r-- | src/mem/ruby/eventqueue/EventQueue_tester.cc | 89 |
5 files changed, 472 insertions, 0 deletions
diff --git a/src/mem/ruby/eventqueue/EventQueue.cc b/src/mem/ruby/eventqueue/EventQueue.cc new file mode 100644 index 000000000..0eef53530 --- /dev/null +++ b/src/mem/ruby/eventqueue/EventQueue.cc @@ -0,0 +1,120 @@ + +/* + * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * $Id$ + */ + +#include "EventQueue.hh" +#include "RubyConfig.hh" +#include "Consumer.hh" +#include "Profiler.hh" +#include "System.hh" +#include "PrioHeap.hh" +#include "EventQueueNode.hh" + +// Class public method definitions + +EventQueue::EventQueue() +{ + m_prio_heap_ptr = NULL; + init(); +} + +EventQueue::~EventQueue() +{ + delete m_prio_heap_ptr; +} + +void EventQueue::init() +{ + m_globalTime = 1; + m_timeOfLastRecovery = 1; + m_prio_heap_ptr = new PrioHeap<EventQueueNode>; + m_prio_heap_ptr->init(); +} + +bool EventQueue::isEmpty() const +{ + return (m_prio_heap_ptr->size() == 0); +} + +void EventQueue::scheduleEventAbsolute(Consumer* consumer, Time timeAbs) +{ + // Check to see if this is a redundant wakeup + // Time time = timeDelta + m_globalTime; + ASSERT(consumer != NULL); + if (consumer->getLastScheduledWakeup() != timeAbs) { + // This wakeup is not redundant + EventQueueNode thisNode; + thisNode.m_consumer_ptr = consumer; + assert(timeAbs > m_globalTime); + thisNode.m_time = timeAbs; + m_prio_heap_ptr->insert(thisNode); + consumer->setLastScheduledWakeup(timeAbs); + } +} + +void EventQueue::triggerEvents(Time t) +{ + EventQueueNode thisNode; + + while(m_prio_heap_ptr->size() > 0 && m_prio_heap_ptr->peekMin().m_time <= t) { + m_globalTime = m_prio_heap_ptr->peekMin().m_time; + thisNode = m_prio_heap_ptr->extractMin(); + assert(thisNode.m_consumer_ptr != NULL); + DEBUG_EXPR(EVENTQUEUE_COMP,MedPrio,*(thisNode.m_consumer_ptr)); + DEBUG_EXPR(EVENTQUEUE_COMP,MedPrio,thisNode.m_time); + thisNode.m_consumer_ptr->triggerWakeup(); + } + m_globalTime = t; +} + +void EventQueue::triggerAllEvents() +{ + // FIXME - avoid repeated code + EventQueueNode thisNode; + + while(m_prio_heap_ptr->size() > 0) { + m_globalTime = m_prio_heap_ptr->peekMin().m_time; + thisNode = m_prio_heap_ptr->extractMin(); + assert(thisNode.m_consumer_ptr != NULL); + DEBUG_EXPR(EVENTQUEUE_COMP,MedPrio,*(thisNode.m_consumer_ptr)); + DEBUG_EXPR(EVENTQUEUE_COMP,MedPrio,thisNode.m_time); + thisNode.m_consumer_ptr->triggerWakeup(); + } +} + +// Class private method definitions + +void +EventQueue::print(ostream& out) const +{ + out << "[Event Queue: " << *m_prio_heap_ptr << "]"; +} diff --git a/src/mem/ruby/eventqueue/EventQueue.hh b/src/mem/ruby/eventqueue/EventQueue.hh new file mode 100644 index 000000000..476e0d24a --- /dev/null +++ b/src/mem/ruby/eventqueue/EventQueue.hh @@ -0,0 +1,118 @@ + +/* + * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * $Id$ + * + * Description: The EventQueue class implements an event queue which + * can be trigger events, allowing our simulation to be event driven. + * + * Currently, the only event we support is a Consumer being signaled + * by calling the consumer's wakeup() routine. Adding the event to + * the queue does not require a virtual function call, though calling + * wakeup() is a virtual function call. + * + * The method triggerEvents() is called with a global time. All + * events which are before or at this time are triggered in timestamp + * order. No ordering is enforced for events scheduled to occur at + * the same time. Events scheduled to wakeup the same consumer at the + * same time are combined into a single event. + * + * The method scheduleConsumerWakeup() is called with a global time + * and a consumer pointer. The event queue will call the wakeup() + * method of the consumer at the appropriate time. + * + * This implementation of EventQueue uses a dynamically sized array + * managed as a heap. The algorithms used has O(lg n) for insert and + * O(lg n) for extract minimum element. (Based on chapter 7 of Cormen, + * Leiserson, and Rivest.) The array is dynamically sized and is + * automatically doubled in size when necessary. + * + */ + +#ifndef EVENTQUEUE_H +#define EVENTQUEUE_H + +#include "Global.hh" +#include "Vector.hh" + +class Consumer; +template <class TYPE> class PrioHeap; +class EventQueueNode; + +class EventQueue { +public: + // Constructors + EventQueue(); + + // Destructor + ~EventQueue(); + + // Public Methods + + Time getTime() const { return m_globalTime; } + void scheduleEvent(Consumer* consumer, Time timeDelta) { scheduleEventAbsolute(consumer, timeDelta + m_globalTime); } + void scheduleEventAbsolute(Consumer* consumer, Time timeAbs); + void triggerEvents(Time t); // called to handle all events <= time t + void triggerAllEvents(); + void print(ostream& out) const; + bool isEmpty() const; + + Time getTimeOfLastRecovery() {return m_timeOfLastRecovery;} + void setTimeOfLastRecovery(Time t) {m_timeOfLastRecovery = t;} + + // Private Methods +private: + // Private copy constructor and assignment operator + void init(); + EventQueue(const EventQueue& obj); + EventQueue& operator=(const EventQueue& obj); + + // Data Members (m_ prefix) + PrioHeap<EventQueueNode>* m_prio_heap_ptr; + Time m_globalTime; + Time m_timeOfLastRecovery; +}; + +// Output operator declaration +inline extern +ostream& operator<<(ostream& out, const EventQueue& obj); + +// ******************* Definitions ******************* + +// Output operator definition +inline extern +ostream& operator<<(ostream& out, const EventQueue& obj) +{ + obj.print(out); + out << flush; + return out; +} + +#endif //EVENTQUEUE_H diff --git a/src/mem/ruby/eventqueue/EventQueueNode.cc b/src/mem/ruby/eventqueue/EventQueueNode.cc new file mode 100644 index 000000000..b0027506b --- /dev/null +++ b/src/mem/ruby/eventqueue/EventQueueNode.cc @@ -0,0 +1,47 @@ + +/* + * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * $Id$ + * + */ + +#include "EventQueueNode.hh" + +void EventQueueNode::print(ostream& out) const +{ + out << "["; + out << "Time=" << m_time; + if (m_consumer_ptr != NULL) { + out << " Consumer=" << m_consumer_ptr; + } else { + out << " Consumer=NULL"; + } + out << "]"; +} diff --git a/src/mem/ruby/eventqueue/EventQueueNode.hh b/src/mem/ruby/eventqueue/EventQueueNode.hh new file mode 100644 index 000000000..eff7ff37e --- /dev/null +++ b/src/mem/ruby/eventqueue/EventQueueNode.hh @@ -0,0 +1,98 @@ + +/* + * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * $Id$ + * + */ + +#ifndef EVENTQUEUENODE_H +#define EVENTQUEUENODE_H + +#include "Global.hh" +class Consumer; + +class EventQueueNode { +public: + // Constructors + EventQueueNode() { m_time = 0; m_consumer_ptr = NULL; } + + // Destructor + //~EventQueueNode(); + + // Public Methods + void print(ostream& out) const; + + // Assignment operator and copy constructor since the default + // constructors confuse purify when long longs are present. + EventQueueNode& operator=(const EventQueueNode& obj) { + m_time = obj.m_time; + m_consumer_ptr = obj.m_consumer_ptr; + return *this; + } + + EventQueueNode(const EventQueueNode& obj) { + m_time = obj.m_time; + m_consumer_ptr = obj.m_consumer_ptr; + } +private: + // Private Methods + + // Default copy constructor and assignment operator + // EventQueueNode(const EventQueueNode& obj); + + // Data Members (m_ prefix) +public: + Time m_time; + Consumer* m_consumer_ptr; +}; + +// Output operator declaration +ostream& operator<<(ostream& out, const EventQueueNode& obj); + +// ******************* Definitions ******************* + +inline extern bool node_less_then_eq(const EventQueueNode& n1, const EventQueueNode& n2); + +inline extern +bool node_less_then_eq(const EventQueueNode& n1, const EventQueueNode& n2) +{ + return (n1.m_time <= n2.m_time); +} + +// Output operator definition +extern inline +ostream& operator<<(ostream& out, const EventQueueNode& obj) +{ + obj.print(out); + out << flush; + return out; +} + +#endif //EVENTQUEUENODE_H diff --git a/src/mem/ruby/eventqueue/EventQueue_tester.cc b/src/mem/ruby/eventqueue/EventQueue_tester.cc new file mode 100644 index 000000000..5e54aa7e0 --- /dev/null +++ b/src/mem/ruby/eventqueue/EventQueue_tester.cc @@ -0,0 +1,89 @@ + +/* + * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * $Id$ + * + */ + +#include "EventQueue.hh" +#include "Consumer.hh" + +//static int global_counter = 0; + +class TestConsumer1 : public Consumer { +public: + TestConsumer1(int description) { m_description = description; } + ~TestConsumer1() { } + void wakeup() { cout << "Wakeup#1: " << m_description << endl; } + // void wakeup() { global_counter++; } + void print(ostream& out) const { out << "1:" << m_description << endl; } + +private: + int m_description; +}; + +class TestConsumer2 : public Consumer { +public: + TestConsumer2(int description) { m_description = description; } + ~TestConsumer2() { } + void wakeup() { cout << "Wakeup#2: " << m_description << endl; } + // void wakeup() { global_counter++; } + void print(ostream& out) const { out << "2:" << m_description << endl; } +private: + int m_description; +}; + +int main() +{ + EventQueue q; + const int SIZE = 200; + const int MAX_TIME = 10000; + int numbers[SIZE]; + Consumer* consumers[SIZE]; + + for (int i=0; i<SIZE; i++) { + numbers[i] = random() % MAX_TIME; + if (i%2 == 0) { + consumers[i] = new TestConsumer1(i); + } else { + consumers[i] = new TestConsumer2(i); + } + } + + for(int i=0; i<SIZE; i++) { + q.scheduleEvent(consumers[i], numbers[i]); + } + + q.triggerEvents(MAX_TIME); + + for (int i=0; i<SIZE; i++) { + delete consumers[i]; + } +} |