ruby: Check MessageBuffer space in garnet NetworkInterface

Garnet's NetworkInterface does not consider the size of MessageBuffers when
ejecting a Message from the network. Add a size check for the MessageBuffer
and only enqueue if space is available. If space is not available, the
message if placed in a queue and the credit is held. A callback from the
MessageBuffer is implemented to wake the NetworkInterface. If there are
messages in the stalled queue, they are processed first, in a FIFO manner
and if succesfully ejected, the credit is finally sent back upstream. The
maximum size of the stall queue is equal to the number of valid VNETs
with MessageBuffers attached.

7 files changed, 173 insertions, 36 deletions

diff --git a/src/mem/ruby/network/MessageBuffer.cc b/src/mem/ruby/network/MessageBuffer.cc
index 573d8833a..67bc7f72d 100644
--- a/src/mem/ruby/network/MessageBuffer.cc
+++ b/src/mem/ruby/network/MessageBuffer.cc
@@ -60,6 +60,8 @@ MessageBuffer::MessageBuffer(const Params *p)
 
     m_buf_msgs = 0;
     m_stall_time = 0;
+
+    m_dequeue_callback = nullptr;
 }
 
 unsigned int
@@ -241,10 +243,27 @@ MessageBuffer::dequeue(Tick current_time, bool decrement_messages)
         m_buf_msgs--;
     }
 
+    // if a dequeue callback was requested, call it now
+    if (m_dequeue_callback) {
+        m_dequeue_callback();
+    }
+
     return delay;
 }
 
 void
+MessageBuffer::registerDequeueCallback(std::function<void()> callback)
+{
+    m_dequeue_callback = callback;
+}
+
+void
+MessageBuffer::unregisterDequeueCallback()
+{
+    m_dequeue_callback = nullptr;
+}
+
+void
 MessageBuffer::clear()
 {
     m_prio_heap.clear();
diff --git a/src/mem/ruby/network/MessageBuffer.hh b/src/mem/ruby/network/MessageBuffer.hh
index fc8feb03e..e6ec5ac4b 100644
--- a/src/mem/ruby/network/MessageBuffer.hh
+++ b/src/mem/ruby/network/MessageBuffer.hh
@@ -102,6 +102,9 @@ class MessageBuffer : public SimObject
     //! removes it from the queue and returns its total delay.
     Tick dequeue(Tick current_time, bool decrement_messages = true);
 
+    void registerDequeueCallback(std::function<void()> callback);
+    void unregisterDequeueCallback();
+
     void recycle(Tick current_time, Tick recycle_latency);
     bool isEmpty() const { return m_prio_heap.size() == 0; }
     bool isStallMapEmpty() { return m_stall_msg_map.size() == 0; }
@@ -133,6 +136,8 @@ class MessageBuffer : public SimObject
     Consumer* m_consumer;
     std::vector<MsgPtr> m_prio_heap;
 
+    std::function<void()> m_dequeue_callback;
+
     // use a std::map for the stalled messages as this container is
     // sorted and ensures a well-defined iteration order
     typedef std::map<Addr, std::list<MsgPtr> > StallMsgMapType;
diff --git a/src/mem/ruby/network/garnet2.0/NetworkInterface.cc b/src/mem/ruby/network/garnet2.0/NetworkInterface.cc
index fe9f1b87e..b3d89cab8 100644
--- a/src/mem/ruby/network/garnet2.0/NetworkInterface.cc
+++ b/src/mem/ruby/network/garnet2.0/NetworkInterface.cc
@@ -70,6 +70,8 @@ NetworkInterface::NetworkInterface(const Params *p)
     for (int i = 0; i < m_virtual_networks; i++) {
         m_vc_allocator[i] = 0;
     }
+
+    m_stall_count.resize(m_virtual_networks);
 }
 
 void
@@ -127,6 +129,41 @@ NetworkInterface::addNode(vector<MessageBuffer *>& in,
     }
 }
 
+void
+NetworkInterface::dequeueCallback()
+{
+    // An output MessageBuffer has dequeued something this cycle and there
+    // is now space to enqueue a stalled message. However, we cannot wake
+    // on the same cycle as the dequeue. Schedule a wake at the soonest
+    // possible time (next cycle).
+    scheduleEventAbsolute(clockEdge(Cycles(1)));
+}
+
+void
+NetworkInterface::incrementStats(flit *t_flit)
+{
+    int vnet = t_flit->get_vnet();
+
+    // Latency
+    m_net_ptr->increment_received_flits(vnet);
+    Cycles network_delay =
+        t_flit->get_dequeue_time() - t_flit->get_enqueue_time() - Cycles(1);
+    Cycles src_queueing_delay = t_flit->get_src_delay();
+    Cycles dest_queueing_delay = (curCycle() - t_flit->get_dequeue_time());
+    Cycles queueing_delay = src_queueing_delay + dest_queueing_delay;
+
+    m_net_ptr->increment_flit_network_latency(network_delay, vnet);
+    m_net_ptr->increment_flit_queueing_latency(queueing_delay, vnet);
+
+    if (t_flit->get_type() == TAIL_ || t_flit->get_type() == HEAD_TAIL_) {
+        m_net_ptr->increment_received_packets(vnet);
+        m_net_ptr->increment_packet_network_latency(network_delay, vnet);
+        m_net_ptr->increment_packet_queueing_latency(queueing_delay, vnet);
+    }
+
+    // Hops
+    m_net_ptr->increment_total_hops(t_flit->get_route().hops_traversed);
+}
 
 /*
  * The NI wakeup checks whether there are any ready messages in the protocol
@@ -166,48 +203,50 @@ NetworkInterface::wakeup()
     scheduleOutputLink();
     checkReschedule();
 
-    /*********** Check the incoming flit link **********/
+    // Check if there are flits stalling a virtual channel. Track if a
+    // message is enqueued to restrict ejection to one message per cycle.
+    bool messageEnqueuedThisCycle = checkStallQueue();
 
+    /*********** Check the incoming flit link **********/
     if (inNetLink->isReady(curCycle())) {
         flit *t_flit = inNetLink->consumeLink();
-        bool free_signal = false;
-        if (t_flit->get_type() == TAIL_ || t_flit->get_type() == HEAD_TAIL_) {
-            free_signal = true;
-
-            // enqueue into the protocol buffers
-            outNode_ptr[t_flit->get_vnet()]->enqueue(
-                t_flit->get_msg_ptr(), curTime, cyclesToTicks(Cycles(1)));
-        }
-        // Simply send a credit back since we are not buffering
-        // this flit in the NI
-        Credit *t_credit = new Credit(t_flit->get_vc(), free_signal,
-                                         curCycle());
-        outCreditQueue->insert(t_credit);
-        outCreditLink->
-            scheduleEventAbsolute(clockEdge(Cycles(1)));
-
         int vnet = t_flit->get_vnet();
+        t_flit->set_dequeue_time(curCycle());
 
-        // Update Stats
-
-        // Latency
-        m_net_ptr->increment_received_flits(vnet);
-        Cycles network_delay = curCycle() - t_flit->get_enqueue_time();
-        Cycles queueing_delay = t_flit->get_src_delay();
-
-        m_net_ptr->increment_flit_network_latency(network_delay, vnet);
-        m_net_ptr->increment_flit_queueing_latency(queueing_delay, vnet);
-
+        // If a tail flit is received, enqueue into the protocol buffers if
+        // space is available. Otherwise, exchange non-tail flits for credits.
         if (t_flit->get_type() == TAIL_ || t_flit->get_type() == HEAD_TAIL_) {
-            m_net_ptr->increment_received_packets(vnet);
-            m_net_ptr->increment_packet_network_latency(network_delay, vnet);
-            m_net_ptr->increment_packet_queueing_latency(queueing_delay, vnet);
-        }
-
-        // Hops
-        m_net_ptr->increment_total_hops(t_flit->get_route().hops_traversed);
+            if (!messageEnqueuedThisCycle &&
+                outNode_ptr[vnet]->areNSlotsAvailable(1, curTime)) {
+                // Space is available. Enqueue to protocol buffer.
+                outNode_ptr[vnet]->enqueue(t_flit->get_msg_ptr(), curTime,
+                                           cyclesToTicks(Cycles(1)));
+
+                // Simply send a credit back since we are not buffering
+                // this flit in the NI
+                sendCredit(t_flit, true);
+
+                // Update stats and delete flit pointer
+                incrementStats(t_flit);
+                delete t_flit;
+            } else {
+                // No space available- Place tail flit in stall queue and set
+                // up a callback for when protocol buffer is dequeued. Stat
+                // update and flit pointer deletion will occur upon unstall.
+                m_stall_queue.push_back(t_flit);
+                m_stall_count[vnet]++;
+
+                auto cb = std::bind(&NetworkInterface::dequeueCallback, this);
+                outNode_ptr[vnet]->registerDequeueCallback(cb);
+            }
+        } else {
+            // Non-tail flit. Send back a credit but not VC free signal.
+            sendCredit(t_flit, false);
 
-        delete t_flit;
+            // Update stats and delete flit pointer.
+            incrementStats(t_flit);
+            delete t_flit;
+        }
     }
 
     /****************** Check the incoming credit link *******/
@@ -220,8 +259,68 @@ NetworkInterface::wakeup()
         }
         delete t_credit;
     }
+
+
+    // It is possible to enqueue multiple outgoing credit flits if a message
+    // was unstalled in the same cycle as a new message arrives. In this
+    // case, we should schedule another wakeup to ensure the credit is sent
+    // back.
+    if (outCreditQueue->getSize() > 0) {
+        outCreditLink->scheduleEventAbsolute(clockEdge(Cycles(1)));
+    }
+}
+
+void
+NetworkInterface::sendCredit(flit *t_flit, bool is_free)
+{
+    Credit *credit_flit = new Credit(t_flit->get_vc(), is_free, curCycle());
+    outCreditQueue->insert(credit_flit);
 }
 
+bool
+NetworkInterface::checkStallQueue()
+{
+    bool messageEnqueuedThisCycle = false;
+    Tick curTime = clockEdge();
+
+    if (!m_stall_queue.empty()) {
+        for (auto stallIter = m_stall_queue.begin();
+             stallIter != m_stall_queue.end(); ) {
+            flit *stallFlit = *stallIter;
+            int vnet = stallFlit->get_vnet();
+
+            // If we can now eject to the protocol buffer, send back credits
+            if (outNode_ptr[vnet]->areNSlotsAvailable(1, curTime)) {
+                outNode_ptr[vnet]->enqueue(stallFlit->get_msg_ptr(), curTime,
+                                           cyclesToTicks(Cycles(1)));
+
+                // Send back a credit with free signal now that the VC is no
+                // longer stalled.
+                sendCredit(stallFlit, true);
+
+                // Update Stats
+                incrementStats(stallFlit);
+
+                // Flit can now safely be deleted and removed from stall queue
+                delete stallFlit;
+                m_stall_queue.erase(stallIter);
+                m_stall_count[vnet]--;
+
+                // If there are no more stalled messages for this vnet, the
+                // callback on it's MessageBuffer is not needed.
+                if (m_stall_count[vnet] == 0)
+                    outNode_ptr[vnet]->unregisterDequeueCallback();
+
+                messageEnqueuedThisCycle = true;
+                break;
+            } else {
+                ++stallIter;
+            }
+        }
+    }
+
+    return messageEnqueuedThisCycle;
+}
 
 // Embed the protocol message into flits
 bool
diff --git a/src/mem/ruby/network/garnet2.0/NetworkInterface.hh b/src/mem/ruby/network/garnet2.0/NetworkInterface.hh
index f1d1fd505..2dfb2d287 100644
--- a/src/mem/ruby/network/garnet2.0/NetworkInterface.hh
+++ b/src/mem/ruby/network/garnet2.0/NetworkInterface.hh
@@ -62,6 +62,7 @@ class NetworkInterface : public ClockedObject, public Consumer
     void addOutPort(NetworkLink *out_link, CreditLink *credit_link,
         SwitchID router_id);
 
+    void dequeueCallback();
     void wakeup();
     void addNode(std::vector<MessageBuffer *> &inNode,
                  std::vector<MessageBuffer *> &outNode);
@@ -90,6 +91,10 @@ class NetworkInterface : public ClockedObject, public Consumer
     CreditLink *inCreditLink;
     CreditLink *outCreditLink;
 
+    // Queue for stalled flits
+    std::deque<flit *> m_stall_queue;
+    std::vector<int> m_stall_count;
+
     // Input Flit Buffers
     // The flit buffers which will serve the Consumer
     std::vector<flitBuffer *>  m_ni_out_vcs;
@@ -102,10 +107,15 @@ class NetworkInterface : public ClockedObject, public Consumer
     // When a vc stays busy for a long time, it indicates a deadlock
     std::vector<int> vc_busy_counter;
 
+    bool checkStallQueue();
     bool flitisizeMessage(MsgPtr msg_ptr, int vnet);
     int calculateVC(int vnet);
+
     void scheduleOutputLink();
     void checkReschedule();
+    void sendCredit(flit *t_flit, bool is_free);
+
+    void incrementStats(flit *t_flit);
 };
 
 #endif // __MEM_RUBY_NETWORK_GARNET_NETWORK_INTERFACE_HH__
diff --git a/src/mem/ruby/network/garnet2.0/flit.cc b/src/mem/ruby/network/garnet2.0/flit.cc
index e507ea442..60f1082f0 100644
--- a/src/mem/ruby/network/garnet2.0/flit.cc
+++ b/src/mem/ruby/network/garnet2.0/flit.cc
@@ -40,6 +40,7 @@ flit::flit(int id, int  vc, int vnet, RouteInfo route, int size,
     m_size = size;
     m_msg_ptr = msg_ptr;
     m_enqueue_time = curTime;
+    m_dequeue_time = curTime;
     m_time = curTime;
     m_id = id;
     m_vnet = vnet;
diff --git a/src/mem/ruby/network/garnet2.0/flit.hh b/src/mem/ruby/network/garnet2.0/flit.hh
index 3e30ec98c..419450b1c 100644
--- a/src/mem/ruby/network/garnet2.0/flit.hh
+++ b/src/mem/ruby/network/garnet2.0/flit.hh
@@ -51,6 +51,7 @@ class flit
     int get_outport() {return m_outport; }
     int get_size() { return m_size; }
     Cycles get_enqueue_time() { return m_enqueue_time; }
+    Cycles get_dequeue_time() { return m_dequeue_time; }
     int get_id() { return m_id; }
     Cycles get_time() { return m_time; }
     int get_vnet() { return m_vnet; }
@@ -66,6 +67,7 @@ class flit
     void set_vc(int vc) { m_vc = vc; }
     void set_route(RouteInfo route) { m_route = route; }
     void set_src_delay(Cycles delay) { src_delay = delay; }
+    void set_dequeue_time(Cycles time) { m_dequeue_time = time; }
 
     void increment_hops() { m_route.hops_traversed++; }
     void print(std::ostream& out) const;
@@ -103,7 +105,7 @@ class flit
     int m_vc;
     RouteInfo m_route;
     int m_size;
-    Cycles m_enqueue_time, m_time;
+    Cycles m_enqueue_time, m_dequeue_time, m_time;
     flit_type m_type;
     MsgPtr m_msg_ptr;
     int m_outport;
diff --git a/src/mem/ruby/network/garnet2.0/flitBuffer.hh b/src/mem/ruby/network/garnet2.0/flitBuffer.hh
index eb6ad6167..d98fe8b4f 100644
--- a/src/mem/ruby/network/garnet2.0/flitBuffer.hh
+++ b/src/mem/ruby/network/garnet2.0/flitBuffer.hh
@@ -52,6 +52,7 @@ class flitBuffer
     void print(std::ostream& out) const;
     bool isFull();
     void setMaxSize(int maximum);
+    int getSize() const { return m_buffer.size(); }
 
     flit *
     getTopFlit()