diff options
23 files changed, 120 insertions, 370 deletions
diff --git a/src/mem/gems_common/PrioHeap.hh b/src/mem/gems_common/PrioHeap.hh deleted file mode 100644 index 266d35e6a..000000000 --- a/src/mem/gems_common/PrioHeap.hh +++ /dev/null @@ -1,251 +0,0 @@ -/* - * Copyright (c) 1999-2005 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. - */ - -#ifndef PRIOHEAP_H -#define PRIOHEAP_H - -#include <cassert> -#include <iostream> -#include <vector> - -typedef unsigned int HeapIndex; - -template <class TYPE> -class PrioHeap { -public: - // Constructors - PrioHeap() { init(); } - - // Destructor - //~PrioHeap(); - - // Public Methods - void init() { m_current_size = 0; } - int size() const { return m_current_size; } - void insert(const TYPE& key); - const TYPE& peekMin() const; - const TYPE& peekElement(int index) const; - TYPE extractMin(); - void print(std::ostream& out) const; -private: - // Private Methods - bool verifyHeap() const; - bool verifyHeap(HeapIndex index) const; - void heapify(); - - // Private copy constructor and assignment operator - PrioHeap(const PrioHeap& obj); - PrioHeap<TYPE>& operator=(const PrioHeap& obj); - - // Data Members (m_ prefix) - std::vector<TYPE> m_heap; - HeapIndex m_current_size; -}; - -// Output operator declaration -template <class TYPE> -std::ostream& operator<<(std::ostream& out, const PrioHeap<TYPE>& obj); - -// ******************* Helper Functions ******************* -inline -HeapIndex get_parent(HeapIndex i) -{ - // return (i/2); - return (i>>1); -} - -inline -HeapIndex get_right(HeapIndex i) -{ - // return (2*i) + 1; - return (i<<1) | 1; -} - -inline -HeapIndex get_left(HeapIndex i) -{ - // return (2*i); - return (i<<1); -} - -template <class TYPE> -void prio_heap_swap(TYPE& n1, TYPE& n2) -{ - TYPE temp = n1; - n1 = n2; - n2 = temp; -} - -// ******************* Definitions ******************* - -template <class TYPE> -void PrioHeap<TYPE>::insert(const TYPE& key) -{ - int i; - // grow the vector size - m_current_size++; - m_heap.resize(m_current_size+1); - - if(m_current_size == 1){ // HACK: need to initialize index 0 to avoid purify UMCs - m_heap[0] = key; - } - - i = m_current_size; - while ((i > 1) && (node_less_then_eq(key, m_heap[get_parent(i)]))) { - m_heap[i] = m_heap[get_parent(i)]; - i = get_parent(i); - } - m_heap[i] = key; - // assert(verifyHeap()); -} - -template <class TYPE> -const TYPE& PrioHeap<TYPE>::peekMin() const -{ - assert(size() > 0); - return m_heap[1]; // 1, not 0, is the first element -} - -template <class TYPE> -const TYPE& PrioHeap<TYPE>::peekElement(int index) const -{ - assert(size() > 0); - return m_heap[index]; -} - -template <class TYPE> -TYPE PrioHeap<TYPE>::extractMin() -{ - // TYPE temp; - assert(size() > 0); - TYPE temp = m_heap[1]; // 1, not 0, is the first element - m_heap[1] = m_heap[m_current_size]; - m_current_size--; - heapify(); - return temp; -} - -template <class TYPE> -bool PrioHeap<TYPE>::verifyHeap() const -{ - return verifyHeap(1); -} - -template <class TYPE> -bool PrioHeap<TYPE>::verifyHeap(HeapIndex index) const -{ - // Recursively verify that each node is <= its parent - if(index > m_current_size) { - return true; - } else if (index == 1) { - return - verifyHeap(get_right(index)) && - verifyHeap(get_left(index)); - } else if (node_less_then_eq(m_heap[get_parent(index)], m_heap[index])) { - return - verifyHeap(get_right(index)) && - verifyHeap(get_left(index)); - } else { - // Heap property violation - return false; - } -} - -template <class TYPE> -void PrioHeap<TYPE>::heapify() -{ - HeapIndex current_node = 1; - HeapIndex left, right, smallest; - // HeapIndex size = m_current_size; - - while(true) { - left = get_left(current_node); - right = get_right(current_node); - - // Find the smallest of the current node and children - if (left <= m_current_size && node_less_then_eq(m_heap[left], m_heap[current_node])) { - smallest = left; - } else { - smallest = current_node; - } - - if (right <= m_current_size && node_less_then_eq(m_heap[right], m_heap[smallest])) { - smallest = right; - } - - // Check to see if we are done - if (smallest == current_node) { - // We are done - break; - } else { - // Not done, heapify on the smallest child - prio_heap_swap(m_heap[current_node], m_heap[smallest]); - current_node = smallest; - } - } - // assert(verifyHeap()); -} - -template <class TYPE> -void PrioHeap<TYPE>::print(std::ostream& out) const -{ - std::vector<TYPE> copyHeap(m_heap); - - // sort copyHeap (inefficient, but will not be done often) - - for(HeapIndex i=0;i<m_current_size; i++){ - for(HeapIndex j=0; j< m_current_size; j++){ - if(copyHeap[i].m_time < copyHeap[j].m_time){ - prio_heap_swap(copyHeap[i], copyHeap[j]); - } - } - } - - out << "[PrioHeap: "; - - for(HeapIndex i=1; i<= m_current_size; i++){ - out << copyHeap[i]; - - if(i != m_current_size-1){ - out << ","; - } - out << " "; - } - out << "]"; -} - -// Output operator definition -template <class TYPE> -std::ostream& operator<<(std::ostream& out, const PrioHeap<TYPE>& obj) -{ - obj.print(out); - out << std::flush; - return out; -} - -#endif //PRIOHEAP_H diff --git a/src/mem/ruby/buffers/MessageBuffer.cc b/src/mem/ruby/buffers/MessageBuffer.cc index 26d187305..9cd1dd47b 100644 --- a/src/mem/ruby/buffers/MessageBuffer.cc +++ b/src/mem/ruby/buffers/MessageBuffer.cc @@ -27,10 +27,12 @@ */ #include "base/cprintf.hh" +#include "base/stl_helpers.hh" #include "mem/ruby/buffers/MessageBuffer.hh" #include "mem/ruby/system/System.hh" using namespace std; +using m5::stl_helpers::operator<<; MessageBuffer::MessageBuffer(const string &name) { @@ -111,7 +113,7 @@ MessageBuffer::getMsgPtrCopy() const { assert(isReady()); - return m_prio_heap.peekMin().m_msgptr->clone(); + return m_prio_heap.front().m_msgptr->clone(); } const Message* @@ -124,7 +126,7 @@ MessageBuffer::peekAtHeadOfQueue() const m_name, g_eventQueue_ptr->getTime())); assert(isReady()); - const Message* msg_ptr = m_prio_heap.peekMin().m_msgptr.get(); + const Message* msg_ptr = m_prio_heap.front().m_msgptr.get(); assert(msg_ptr); DEBUG_EXPR(QUEUE_COMP, MedPrio, *msg_ptr); @@ -223,7 +225,9 @@ MessageBuffer::enqueue(MsgPtr message, Time delta) // Insert the message into the priority heap MessageBufferNode thisNode(arrival_time, m_msg_counter, message); - m_prio_heap.insert(thisNode); + m_prio_heap.push_back(thisNode); + push_heap(m_prio_heap.begin(), m_prio_heap.end(), + greater<MessageBufferNode>()); DEBUG_NEWLINE(QUEUE_COMP, HighPrio); DEBUG_MSG(QUEUE_COMP, HighPrio, @@ -260,7 +264,7 @@ void MessageBuffer::dequeue(MsgPtr& message) { DEBUG_MSG(QUEUE_COMP, MedPrio, "dequeue from " + m_name); - message = m_prio_heap.peekMin().m_msgptr; + message = m_prio_heap.front().m_msgptr; pop(); DEBUG_EXPR(QUEUE_COMP, MedPrio, message); @@ -272,7 +276,7 @@ MessageBuffer::dequeue_getDelayCycles() int delay_cycles = -1; // null value // get MsgPtr of the message about to be dequeued - MsgPtr message = m_prio_heap.peekMin().m_msgptr; + MsgPtr message = m_prio_heap.front().m_msgptr; // get the delay cycles delay_cycles = setAndReturnDelayCycles(message); @@ -288,7 +292,10 @@ MessageBuffer::pop() { DEBUG_MSG(QUEUE_COMP, MedPrio, "pop from " + m_name); assert(isReady()); - m_prio_heap.extractMin(); + pop_heap(m_prio_heap.begin(), m_prio_heap.end(), + greater<MessageBufferNode>()); + m_prio_heap.pop_back(); + // record previous size and time so the current buffer size isn't // adjusted until next cycle if (m_time_last_time_pop < g_eventQueue_ptr->getTime()) { @@ -301,11 +308,7 @@ MessageBuffer::pop() void MessageBuffer::clear() { - while(m_prio_heap.size() > 0){ - m_prio_heap.extractMin(); - } - - ASSERT(m_prio_heap.size() == 0); + m_prio_heap.clear(); m_msg_counter = 0; m_size = 0; @@ -320,9 +323,13 @@ MessageBuffer::recycle() { DEBUG_MSG(QUEUE_COMP, MedPrio, "recycling " + m_name); assert(isReady()); - MessageBufferNode node = m_prio_heap.extractMin(); + MessageBufferNode node = m_prio_heap.front(); + pop_heap(m_prio_heap.begin(), m_prio_heap.end(), + greater<MessageBufferNode>()); node.m_time = g_eventQueue_ptr->getTime() + m_recycle_latency; - m_prio_heap.insert(node); + m_prio_heap.back() = node; + push_heap(m_prio_heap.begin(), m_prio_heap.end(), + greater<MessageBufferNode>()); g_eventQueue_ptr->scheduleEventAbsolute(m_consumer_ptr, g_eventQueue_ptr->getTime() + m_recycle_latency); } @@ -353,7 +360,10 @@ MessageBuffer::print(ostream& out) const if (m_consumer_ptr != NULL) { out << " consumer-yes "; } - out << m_prio_heap << "] " << m_name << endl; + + vector<MessageBufferNode> copy(m_prio_heap); + sort_heap(copy.begin(), copy.end(), greater<MessageBufferNode>()); + out << copy << "] " << m_name << endl; } void diff --git a/src/mem/ruby/buffers/MessageBuffer.hh b/src/mem/ruby/buffers/MessageBuffer.hh index 12799c871..9315eaec0 100644 --- a/src/mem/ruby/buffers/MessageBuffer.hh +++ b/src/mem/ruby/buffers/MessageBuffer.hh @@ -34,10 +34,12 @@ #ifndef __MEM_RUBY_BUFFERS_MESSAGEBUFFER_HH__ #define __MEM_RUBY_BUFFERS_MESSAGEBUFFER_HH__ +#include <algorithm> +#include <functional> #include <iostream> +#include <vector> #include <string> -#include "mem/gems_common/PrioHeap.hh" #include "mem/ruby/buffers/MessageBufferNode.hh" #include "mem/ruby/common/Consumer.hh" #include "mem/ruby/common/Global.hh" @@ -61,13 +63,16 @@ class MessageBuffer isReady() const { return ((m_prio_heap.size() > 0) && - (m_prio_heap.peekMin().m_time <= g_eventQueue_ptr->getTime())); + (m_prio_heap.front().m_time <= g_eventQueue_ptr->getTime())); } void delayHead() { - MessageBufferNode node = m_prio_heap.extractMin(); + MessageBufferNode node = m_prio_heap.front(); + std::pop_heap(m_prio_heap.begin(), m_prio_heap.end(), + std::greater<MessageBufferNode>()); + m_prio_heap.pop_back(); enqueue(node.m_msgptr, 1); } @@ -93,13 +98,13 @@ class MessageBuffer peekMsgPtr() const { assert(isReady()); - return m_prio_heap.peekMin().m_msgptr; + return m_prio_heap.front().m_msgptr; } const MsgPtr& peekMsgPtrEvenIfNotReady() const { - return m_prio_heap.peekMin().m_msgptr; + return m_prio_heap.front().m_msgptr; } void enqueue(MsgPtr message) { enqueue(message, 1); } @@ -144,7 +149,7 @@ class MessageBuffer // Data Members (m_ prefix) Consumer* m_consumer_ptr; // Consumer to signal a wakeup(), can be NULL - PrioHeap<MessageBufferNode> m_prio_heap; + std::vector<MessageBufferNode> m_prio_heap; std::string m_name; int m_max_size; diff --git a/src/mem/ruby/buffers/MessageBufferNode.hh b/src/mem/ruby/buffers/MessageBufferNode.hh index 9ead9b9aa..078da47c4 100644 --- a/src/mem/ruby/buffers/MessageBufferNode.hh +++ b/src/mem/ruby/buffers/MessageBufferNode.hh @@ -59,13 +59,13 @@ class MessageBufferNode }; inline bool -node_less_then_eq(const MessageBufferNode& n1, const MessageBufferNode& n2) +operator>(const MessageBufferNode& n1, const MessageBufferNode& n2) { if (n1.m_time == n2.m_time) { assert(n1.m_msg_counter != n2.m_msg_counter); - return (n1.m_msg_counter <= n2.m_msg_counter); + return n1.m_msg_counter > n2.m_msg_counter; } else { - return (n1.m_time <= n2.m_time); + return n1.m_time > n2.m_time; } } diff --git a/src/mem/ruby/eventqueue/RubyEventQueue.hh b/src/mem/ruby/eventqueue/RubyEventQueue.hh index 4a0fb9ceb..6fa8b0ac3 100644 --- a/src/mem/ruby/eventqueue/RubyEventQueue.hh +++ b/src/mem/ruby/eventqueue/RubyEventQueue.hh @@ -63,7 +63,6 @@ #include "sim/eventq.hh" class Consumer; -template <class TYPE> class PrioHeap; class RubyEventQueueNode; class RubyEventQueue : public EventManager diff --git a/src/mem/ruby/network/garnet/fixed-pipeline/NetworkLink_d.hh b/src/mem/ruby/network/garnet/fixed-pipeline/NetworkLink_d.hh index 29699562d..39fdd3c6f 100644 --- a/src/mem/ruby/network/garnet/fixed-pipeline/NetworkLink_d.hh +++ b/src/mem/ruby/network/garnet/fixed-pipeline/NetworkLink_d.hh @@ -37,7 +37,6 @@ #include "mem/ruby/network/garnet/NetworkHeader.hh" #include "mem/ruby/common/Consumer.hh" #include "mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.hh" -#include "mem/gems_common/PrioHeap.hh" #include "mem/ruby/network/orion/power_bus.hh" class GarnetNetwork_d; diff --git a/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.cc b/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.cc index 38510c758..5387604d4 100644 --- a/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.cc +++ b/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.cc @@ -49,7 +49,7 @@ bool flitBuffer_d::isReady() { if(m_buffer.size() != 0 ) { - flit_d *t_flit = m_buffer.peekMin(); + flit_d *t_flit = peekTopFlit(); if(t_flit->get_time() <= g_eventQueue_ptr->getTime()) return true; } @@ -60,7 +60,7 @@ bool flitBuffer_d::isReadyForNext() { if(m_buffer.size() != 0 ) { - flit_d *t_flit = m_buffer.peekMin(); + flit_d *t_flit = peekTopFlit(); if(t_flit->get_time() <= (g_eventQueue_ptr->getTime() + 1)) return true; } diff --git a/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.hh b/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.hh index 976fa4053..8aa869f82 100644 --- a/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.hh +++ b/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.hh @@ -31,10 +31,11 @@ #ifndef FLIT_BUFFER_D_H #define FLIT_BUFFER_D_H +#include <algorithm> #include <iostream> +#include <vector> #include "mem/ruby/network/garnet/NetworkHeader.hh" -#include "mem/gems_common/PrioHeap.hh" #include "mem/ruby/network/garnet/fixed-pipeline/flit_d.hh" class flitBuffer_d { @@ -51,19 +52,23 @@ public: inline flit_d* getTopFlit() { - return m_buffer.extractMin(); + flit_d *f = m_buffer.front(); + std::pop_heap(m_buffer.begin(), m_buffer.end(), flit_d::greater); + m_buffer.pop_back(); + return f; } inline flit_d* peekTopFlit() { - return m_buffer.peekMin(); + return m_buffer.front(); } inline void insert(flit_d *flt) { - m_buffer.insert(flt); + m_buffer.push_back(flt); + std::push_heap(m_buffer.begin(), m_buffer.end(), flit_d::greater); } /**********Data Members*********/ private: - PrioHeap <flit_d *> m_buffer; + std::vector<flit_d *> m_buffer; int size, max_size; }; diff --git a/src/mem/ruby/network/garnet/fixed-pipeline/flit_d.hh b/src/mem/ruby/network/garnet/fixed-pipeline/flit_d.hh index 39bbe011d..ec2774a94 100644 --- a/src/mem/ruby/network/garnet/fixed-pipeline/flit_d.hh +++ b/src/mem/ruby/network/garnet/fixed-pipeline/flit_d.hh @@ -115,6 +115,16 @@ public: return src_delay; } + static bool + greater(flit_d* n1, flit_d* n2) + { + if (n1->get_time() == n2->get_time()) { + //ASSERT(n1->flit_id != n2->flit_id); + return (n1->get_id() > n2->get_id()); + } else { + return (n1->get_time() > n2->get_time()); + } + } private: /************Data Members*************/ @@ -132,19 +142,6 @@ private: }; -inline extern bool node_less_then_eq(flit_d* n1, flit_d* n2); - -inline extern -bool node_less_then_eq(flit_d* n1, flit_d* n2) -{ - if (n1->get_time() == n2->get_time()) { -// ASSERT(n1->flit_id != n2->flit_id); - return (n1->get_id() <= n2->get_id()); - } else { - return (n1->get_time() <= n2->get_time()); - } -} - inline std::ostream& operator<<(std::ostream& out, const flit_d& obj) { diff --git a/src/mem/ruby/network/garnet/flexible-pipeline/NetworkLink.hh b/src/mem/ruby/network/garnet/flexible-pipeline/NetworkLink.hh index c23d55b48..9f1311dce 100644 --- a/src/mem/ruby/network/garnet/flexible-pipeline/NetworkLink.hh +++ b/src/mem/ruby/network/garnet/flexible-pipeline/NetworkLink.hh @@ -37,7 +37,6 @@ #include "mem/ruby/network/garnet/NetworkHeader.hh" #include "mem/ruby/network/garnet/flexible-pipeline/FlexibleConsumer.hh" #include "mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh" -#include "mem/gems_common/PrioHeap.hh" #include "mem/ruby/common/NetDest.hh" class GarnetNetwork; diff --git a/src/mem/ruby/network/garnet/flexible-pipeline/Router.hh b/src/mem/ruby/network/garnet/flexible-pipeline/Router.hh index b6ebb601f..16b19204a 100644 --- a/src/mem/ruby/network/garnet/flexible-pipeline/Router.hh +++ b/src/mem/ruby/network/garnet/flexible-pipeline/Router.hh @@ -37,7 +37,6 @@ #include "mem/ruby/network/garnet/NetworkHeader.hh" #include "mem/ruby/network/garnet/flexible-pipeline/GarnetNetwork.hh" #include "mem/ruby/network/garnet/flexible-pipeline/FlexibleConsumer.hh" -#include "mem/gems_common/PrioHeap.hh" #include "mem/ruby/network/garnet/flexible-pipeline/NetworkLink.hh" #include "mem/ruby/common/NetDest.hh" #include "mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh" diff --git a/src/mem/ruby/network/garnet/flexible-pipeline/flit.hh b/src/mem/ruby/network/garnet/flexible-pipeline/flit.hh index 1cc8806e9..5aa01c5e7 100644 --- a/src/mem/ruby/network/garnet/flexible-pipeline/flit.hh +++ b/src/mem/ruby/network/garnet/flexible-pipeline/flit.hh @@ -52,6 +52,16 @@ public: flit_type get_type(); void print(std::ostream& out) const; + static bool + greater(flit* n1, flit* n2) + { + if (n1->get_time() == n2->get_time()) + //ASSERT(n1->flit_id != n2->flit_id); + return (n1->get_id() > n2->get_id()); + else + return (n1->get_time() > n2->get_time()); + } + private: /************Data Members*************/ int m_id; @@ -64,19 +74,6 @@ private: }; -inline extern bool node_less_then_eq(flit* n1, flit* n2); - -inline extern -bool node_less_then_eq(flit* n1, flit* n2) -{ - if (n1->get_time() == n2->get_time()) { -// ASSERT(n1->flit_id != n2->flit_id); - return (n1->get_id() <= n2->get_id()); - } else { - return (n1->get_time() <= n2->get_time()); - } -} - inline std::ostream& operator<<(std::ostream& out, const flit& obj) { diff --git a/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.cc b/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.cc index 7f41d6f8c..82eb08902 100644 --- a/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.cc +++ b/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.cc @@ -28,8 +28,12 @@ * Authors: Niket Agarwal */ +#include <algorithm> + #include "mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh" +using namespace std; + flitBuffer::flitBuffer() { max_size = INFINITE_; @@ -49,7 +53,7 @@ bool flitBuffer::isReady() { if(m_buffer.size() != 0 ) { - flit *t_flit = m_buffer.peekMin(); + flit *t_flit = m_buffer.front(); if(t_flit->get_time() <= g_eventQueue_ptr->getTime()) return true; } @@ -60,7 +64,7 @@ bool flitBuffer::isReadyForNext() { if(m_buffer.size() != 0 ) { - flit *t_flit = m_buffer.peekMin(); + flit *t_flit = m_buffer.front(); if(t_flit->get_time() <= (g_eventQueue_ptr->getTime() + 1)) return true; } @@ -79,17 +83,21 @@ void flitBuffer::setMaxSize(int maximum) flit* flitBuffer:: getTopFlit() { - return m_buffer.extractMin(); + flit *f = m_buffer.front(); + pop_heap(m_buffer.begin(), m_buffer.end(), flit::greater); + m_buffer.pop_back(); + return f; } flit* flitBuffer::peekTopFlit() { - return m_buffer.peekMin(); + return m_buffer.front(); } void flitBuffer::insert(flit *flt) { - m_buffer.insert(flt); + m_buffer.push_back(flt); + push_heap(m_buffer.begin(), m_buffer.end(), flit::greater); } void flitBuffer::print(std::ostream& out) const diff --git a/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh b/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh index 646cd99c7..a5ec25590 100644 --- a/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh +++ b/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh @@ -32,9 +32,9 @@ #define FLIT_BUFFER_H #include <iostream> +#include <vector> #include "mem/ruby/network/garnet/NetworkHeader.hh" -#include "mem/gems_common/PrioHeap.hh" #include "mem/ruby/network/garnet/flexible-pipeline/flit.hh" class flitBuffer { @@ -54,7 +54,7 @@ public: /**********Data Members*********/ private: - PrioHeap <flit *> m_buffer; + std::vector<flit *> m_buffer; int size, max_size; }; diff --git a/src/mem/ruby/profiler/AccessTraceForAddress.hh b/src/mem/ruby/profiler/AccessTraceForAddress.hh index a707cd4df..b950f2be2 100644 --- a/src/mem/ruby/profiler/AccessTraceForAddress.hh +++ b/src/mem/ruby/profiler/AccessTraceForAddress.hh @@ -60,6 +60,13 @@ class AccessTraceForAddress void print(std::ostream& out) const; + static inline bool + less_equal(const AccessTraceForAddress* n1, + const AccessTraceForAddress* n2) + { + return n1->getTotal() <= n2->getTotal(); + } + private: Address m_addr; uint64 m_loads; @@ -72,13 +79,6 @@ class AccessTraceForAddress Histogram* m_histogram_ptr; }; -inline bool -node_less_then_eq(const AccessTraceForAddress* n1, - const AccessTraceForAddress* n2) -{ - return n1->getTotal() > n2->getTotal(); -} - inline std::ostream& operator<<(std::ostream& out, const AccessTraceForAddress& obj) { diff --git a/src/mem/ruby/profiler/AddressProfiler.cc b/src/mem/ruby/profiler/AddressProfiler.cc index 4274569ad..5c1b7352c 100644 --- a/src/mem/ruby/profiler/AddressProfiler.cc +++ b/src/mem/ruby/profiler/AddressProfiler.cc @@ -29,7 +29,6 @@ #include <vector> #include "base/stl_helpers.hh" -#include "mem/gems_common/PrioHeap.hh" #include "mem/protocol/CacheMsg.hh" #include "mem/ruby/profiler/AddressProfiler.hh" #include "mem/ruby/profiler/Profiler.hh" @@ -70,15 +69,16 @@ printSorted(ostream& out, int num_of_sequencers, const AddressMap &record_map, const int records_printed = 100; uint64 misses = 0; - PrioHeap<const AccessTraceForAddress*> heap; + std::vector<const AccessTraceForAddress *> sorted; AddressMap::const_iterator i = record_map.begin(); AddressMap::const_iterator end = record_map.end(); for (; i != end; ++i) { const AccessTraceForAddress* record = &i->second; misses += record->getTotal(); - heap.insert(record); + sorted.push_back(record); } + sort(sorted.begin(), sorted.end(), AccessTraceForAddress::less_equal); out << "Total_entries_" << description << ": " << record_map.size() << endl; @@ -106,8 +106,9 @@ printSorted(ostream& out, int num_of_sequencers, const AddressMap &record_map, } int counter = 0; - while (heap.size() > 0 && counter < records_printed) { - const AccessTraceForAddress* record = heap.extractMin(); + int max = sorted.size(); + while (counter < max && counter < records_printed) { + const AccessTraceForAddress* record = sorted[counter]; double percent = 100.0 * (record->getTotal() / double(misses)); out << description << " | " << percent << " % " << *record << endl; all_records.add(record->getTotal()); @@ -117,8 +118,8 @@ printSorted(ostream& out, int num_of_sequencers, const AddressMap &record_map, m_touched_weighted_vec[record->getTouchedBy()] += record->getTotal(); } - while (heap.size() > 0) { - const AccessTraceForAddress* record = heap.extractMin(); + while (counter < max) { + const AccessTraceForAddress* record = sorted[counter]; all_records.add(record->getTotal()); remaining_records.add(record->getTotal()); all_records_log.add(record->getTotal()); diff --git a/src/mem/ruby/profiler/CacheProfiler.cc b/src/mem/ruby/profiler/CacheProfiler.cc index 8ba64add9..006617190 100644 --- a/src/mem/ruby/profiler/CacheProfiler.cc +++ b/src/mem/ruby/profiler/CacheProfiler.cc @@ -26,7 +26,6 @@ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -#include "mem/gems_common/PrioHeap.hh" #include "mem/ruby/profiler/CacheProfiler.hh" #include "mem/ruby/profiler/Profiler.hh" #include "mem/ruby/system/System.hh" diff --git a/src/mem/ruby/profiler/Profiler.cc b/src/mem/ruby/profiler/Profiler.cc index 33d490a85..2b844ef9d 100644 --- a/src/mem/ruby/profiler/Profiler.cc +++ b/src/mem/ruby/profiler/Profiler.cc @@ -50,7 +50,6 @@ #include "base/stl_helpers.hh" #include "base/str.hh" -#include "mem/gems_common/PrioHeap.hh" #include "mem/protocol/CacheMsg.hh" #include "mem/protocol/MachineType.hh" #include "mem/protocol/Protocol.hh" diff --git a/src/mem/ruby/recorder/CacheRecorder.cc b/src/mem/ruby/recorder/CacheRecorder.cc index 32db211b6..1d08eef12 100644 --- a/src/mem/ruby/recorder/CacheRecorder.cc +++ b/src/mem/ruby/recorder/CacheRecorder.cc @@ -26,31 +26,21 @@ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ +#include <algorithm> + #include "gzstream.hh" -#include "mem/gems_common/PrioHeap.hh" #include "mem/ruby/eventqueue/RubyEventQueue.hh" #include "mem/ruby/recorder/CacheRecorder.hh" -#include "mem/ruby/recorder/TraceRecord.hh" using namespace std; -CacheRecorder::CacheRecorder() -{ - m_records_ptr = new PrioHeap<TraceRecord>; -} - -CacheRecorder::~CacheRecorder() -{ - delete m_records_ptr; -} - void CacheRecorder::addRecord(Sequencer* sequencer, const Address& data_addr, const Address& pc_addr, RubyRequestType type, Time time) { - m_records_ptr-> - insert(TraceRecord(sequencer, data_addr, pc_addr, type, time)); + TraceRecord rec(sequencer, data_addr, pc_addr, type, time); + m_records.push_back(rec); } int @@ -62,13 +52,15 @@ CacheRecorder::dumpRecords(string filename) return 0; } - int counter = 0; - while (m_records_ptr->size() != 0) { - TraceRecord record = m_records_ptr->extractMin(); - record.output(out); - counter++; - } - return counter; + std::sort(m_records.begin(), m_records.end(), greater<TraceRecord>()); + + int size = m_records.size(); + for (int i = 0; i < size; ++i) + m_records[i].output(out); + + m_records.clear(); + + return size; } void diff --git a/src/mem/ruby/recorder/CacheRecorder.hh b/src/mem/ruby/recorder/CacheRecorder.hh index 18c246c9f..14066c387 100644 --- a/src/mem/ruby/recorder/CacheRecorder.hh +++ b/src/mem/ruby/recorder/CacheRecorder.hh @@ -36,13 +36,14 @@ #include <iostream> #include <string> +#include <vector> #include "mem/protocol/CacheRequestType.hh" #include "mem/ruby/common/Global.hh" #include "mem/ruby/libruby_internal.hh" #include "mem/ruby/system/NodeID.hh" +#include "mem/ruby/recorder/TraceRecord.hh" -template <class TYPE> class PrioHeap; class Address; class TraceRecord; class Sequencer; @@ -50,9 +51,6 @@ class Sequencer; class CacheRecorder { public: - CacheRecorder(); - ~CacheRecorder(); - void addRecord(Sequencer* sequencer, const Address& data_addr, const Address& pc_addr, RubyRequestType type, Time time); int dumpRecords(std::string filename); @@ -64,7 +62,7 @@ class CacheRecorder CacheRecorder(const CacheRecorder& obj); CacheRecorder& operator=(const CacheRecorder& obj); - PrioHeap<TraceRecord>* m_records_ptr; + std::vector<TraceRecord> m_records; }; inline std::ostream& diff --git a/src/mem/ruby/recorder/TraceRecord.hh b/src/mem/ruby/recorder/TraceRecord.hh index 98e78b20e..ed066debb 100644 --- a/src/mem/ruby/recorder/TraceRecord.hh +++ b/src/mem/ruby/recorder/TraceRecord.hh @@ -60,12 +60,6 @@ class TraceRecord TraceRecord(const TraceRecord& obj); TraceRecord& operator=(const TraceRecord& obj); - bool - node_less_then_eq(const TraceRecord& rec) const - { - return this->m_time <= rec.m_time; - } - void issueRequest() const; void print(std::ostream& out) const; @@ -73,6 +67,8 @@ class TraceRecord bool input(std::istream& in); private: + friend bool operator>(const TraceRecord& n1, const TraceRecord& n2); + Sequencer* m_sequencer_ptr; Time m_time; Address m_data_address; @@ -81,9 +77,9 @@ class TraceRecord }; inline bool -node_less_then_eq(const TraceRecord& n1, const TraceRecord& n2) +operator>(const TraceRecord& n1, const TraceRecord& n2) { - return n1.node_less_then_eq(n2); + return n1.m_time > n2.m_time; } inline std::ostream& diff --git a/src/mem/ruby/recorder/Tracer.cc b/src/mem/ruby/recorder/Tracer.cc index 23dafdb6c..bff59a832 100644 --- a/src/mem/ruby/recorder/Tracer.cc +++ b/src/mem/ruby/recorder/Tracer.cc @@ -27,7 +27,6 @@ */ #include "base/cprintf.hh" -#include "mem/gems_common/PrioHeap.hh" #include "mem/ruby/eventqueue/RubyEventQueue.hh" #include "mem/ruby/recorder/TraceRecord.hh" #include "mem/ruby/recorder/Tracer.hh" diff --git a/src/mem/ruby/recorder/Tracer.hh b/src/mem/ruby/recorder/Tracer.hh index d468b4920..4b81d6121 100644 --- a/src/mem/ruby/recorder/Tracer.hh +++ b/src/mem/ruby/recorder/Tracer.hh @@ -46,7 +46,6 @@ #include "params/RubyTracer.hh" #include "sim/sim_object.hh" -template <class TYPE> class PrioHeap; class Address; class TraceRecord; class Sequencer; |