src/mem/ruby/buffers/MessageBuffer.cc

   1
   2 /*
   3  * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are
   8  * met: redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer;
  10  * redistributions in binary form must reproduce the above copyright
  11  * notice, this list of conditions and the following disclaimer in the
  12  * documentation and/or other materials provided with the distribution;
  13  * neither the name of the copyright holders nor the names of its
  14  * contributors may be used to endorse or promote products derived from
  15  * this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 /*
  31  * $Id$
  32  */
  33
  34 #include "mem/ruby/buffers/MessageBuffer.hh"
  35 #include "mem/ruby/config/RubyConfig.hh"
  36
  37 MessageBuffer::MessageBuffer()
  38 {
  39   m_msg_counter = 0;
  40   m_consumer_ptr = NULL;
  41   m_ordering_set = false;
  42   m_strict_fifo = true;
  43   m_size = 0;
  44   m_max_size = -1;
  45   m_last_arrival_time = 0;
  46   m_randomization = true;
  47   m_size_last_time_size_checked = 0;
  48   m_time_last_time_size_checked = 0;
  49   m_time_last_time_enqueue = 0;
  50   m_time_last_time_pop = 0;
  51   m_size_at_cycle_start = 0;
  52   m_msgs_this_cycle = 0;
  53   m_not_avail_count = 0;
  54   m_priority_rank = 0;
  55 }
  56
  57 MessageBuffer::MessageBuffer(const Chip* chip_ptr)  // The chip_ptr is ignored, but could be used for extra debugging
  58 {
  59   m_msg_counter = 0;
  60   m_consumer_ptr = NULL;
  61   m_ordering_set = false;
  62   m_strict_fifo = true;
  63   m_size = 0;
  64   m_max_size = -1;
  65   m_last_arrival_time = 0;
  66   m_randomization = true;
  67   m_size_last_time_size_checked = 0;
  68   m_time_last_time_size_checked = 0;
  69   m_time_last_time_enqueue = 0;
  70   m_time_last_time_pop = 0;
  71   m_size_at_cycle_start = 0;
  72   m_msgs_this_cycle = 0;
  73   m_not_avail_count = 0;
  74   m_priority_rank = 0;
  75 }
  76
  77 int MessageBuffer::getSize()
  78 {
  79   if(m_time_last_time_size_checked == g_eventQueue_ptr->getTime()){
  80     return m_size_last_time_size_checked;
  81   } else {
  82     m_time_last_time_size_checked = g_eventQueue_ptr->getTime();
  83     m_size_last_time_size_checked = m_size;
  84     return m_size;
  85   }
  86 }
  87
  88 bool MessageBuffer::areNSlotsAvailable(int n)
  89 {
  90
  91   // fast path when message buffers have infinite size
  92   if(m_max_size == -1) {
  93     return true;
  94   }
  95
  96   // determine my correct size for the current cycle
  97   // pop operations shouldn't effect the network's visible size until next cycle,
  98   // but enqueue operations effect the visible size immediately
  99   int current_size = max(m_size_at_cycle_start, m_size);
 100   if (m_time_last_time_pop < g_eventQueue_ptr->getTime()) {  // no pops this cycle - m_size is correct
 101     current_size = m_size;
 102   } else {
 103     if (m_time_last_time_enqueue < g_eventQueue_ptr->getTime()) {  // no enqueues this cycle - m_size_at_cycle_start is correct
 104       current_size = m_size_at_cycle_start;
 105     } else {  // both pops and enqueues occured this cycle - add new enqueued msgs to m_size_at_cycle_start
 106       current_size = m_size_at_cycle_start+m_msgs_this_cycle;
 107     }
 108   }
 109
 110   // now compare the new size with our max size
 111   if(current_size+n <= m_max_size){
 112     return true;
 113   } else {
 114     DEBUG_MSG(QUEUE_COMP,MedPrio,n);
 115     DEBUG_MSG(QUEUE_COMP,MedPrio,current_size);
 116     DEBUG_MSG(QUEUE_COMP,MedPrio,m_size);
 117     DEBUG_MSG(QUEUE_COMP,MedPrio,m_max_size);
 118     m_not_avail_count++;
 119     return false;
 120   }
 121 }
 122
 123 const MsgPtr MessageBuffer::getMsgPtrCopy() const
 124 {
 125   assert(isReady());
 126
 127   MsgPtr temp_msg;
 128   temp_msg = *(m_prio_heap.peekMin().m_msgptr.ref());
 129   assert(temp_msg.ref() != NULL);
 130   return temp_msg;
 131 }
 132
 133 const Message* MessageBuffer::peekAtHeadOfQueue() const
 134 {
 135   const Message* msg_ptr;
 136   DEBUG_NEWLINE(QUEUE_COMP,MedPrio);
 137
 138   DEBUG_MSG(QUEUE_COMP,MedPrio,"Peeking at head of queue " + m_name + " time: "
 139             + int_to_string(g_eventQueue_ptr->getTime()) + ".");
 140   assert(isReady());
 141
 142   msg_ptr = m_prio_heap.peekMin().m_msgptr.ref();
 143   assert(msg_ptr != NULL);
 144
 145   DEBUG_EXPR(QUEUE_COMP,MedPrio,*msg_ptr);
 146   DEBUG_NEWLINE(QUEUE_COMP,MedPrio);
 147   return msg_ptr;
 148 }
 149
 150 // FIXME - move me somewhere else
 151 int random_time()
 152 {
 153   int time = 1;
 154   time += random() & 0x3;  // [0...3]
 155   if ((random() & 0x7) == 0) {  // 1 in 8 chance
 156     time += 100 + (random() % 0xf); // 100 + [1...15]
 157   }
 158   return time;
 159 }
 160
 161 void MessageBuffer::enqueue(const MsgPtr& message, Time delta)
 162 {
 163   DEBUG_NEWLINE(QUEUE_COMP,HighPrio);
 164   DEBUG_MSG(QUEUE_COMP,HighPrio,"enqueue " + m_name + " time: "
 165             + int_to_string(g_eventQueue_ptr->getTime()) + ".");
 166   DEBUG_EXPR(QUEUE_COMP,MedPrio,message);
 167   DEBUG_NEWLINE(QUEUE_COMP,HighPrio);
 168
 169   m_msg_counter++;
 170   m_size++;
 171
 172   // record current time incase we have a pop that also adjusts my size
 173   if (m_time_last_time_enqueue < g_eventQueue_ptr->getTime()) {
 174     m_msgs_this_cycle = 0;  // first msg this cycle
 175     m_time_last_time_enqueue = g_eventQueue_ptr->getTime();
 176   }
 177   m_msgs_this_cycle++;
 178
 179   //  ASSERT(m_max_size == -1 || m_size <= m_max_size + 1);
 180   // the plus one is a kluge because of a SLICC issue
 181
 182   if (!m_ordering_set) {
 183     WARN_EXPR(*this);
 184     WARN_EXPR(m_name);
 185     ERROR_MSG("Ordering property of this queue has not been set");
 186   }
 187
 188   // Calculate the arrival time of the message, that is, the first
 189   // cycle the message can be dequeued.
 190   assert(delta>0);
 191   Time current_time = g_eventQueue_ptr->getTime();
 192   Time arrival_time = 0;
 193   if (!RANDOMIZATION || (m_randomization == false)) {
 194     // No randomization
 195     arrival_time = current_time + delta;
 196
 197   } else {
 198     // Randomization - ignore delta
 199     if (m_strict_fifo) {
 200       if (m_last_arrival_time < current_time) {
 201         m_last_arrival_time = current_time;
 202       }
 203       arrival_time = m_last_arrival_time + random_time();
 204     } else {
 205       arrival_time = current_time + random_time();
 206     }
 207   }
 208
 209   // Check the arrival time
 210   assert(arrival_time > current_time);
 211   if (m_strict_fifo) {
 212     if (arrival_time >= m_last_arrival_time) {
 213
 214     } else {
 215       WARN_EXPR(*this);
 216       WARN_EXPR(m_name);
 217       WARN_EXPR(current_time);
 218       WARN_EXPR(delta);
 219       WARN_EXPR(arrival_time);
 220       WARN_EXPR(m_last_arrival_time);
 221       ERROR_MSG("FIFO ordering violated");
 222     }
 223   }
 224   m_last_arrival_time = arrival_time;
 225
 226   // compute the delay cycles and set enqueue time
 227   Message* msg_ptr = NULL;
 228   msg_ptr = message.mod_ref();
 229   assert(msg_ptr != NULL);
 230   assert(g_eventQueue_ptr->getTime() >= msg_ptr->getLastEnqueueTime());  // ensure we aren't dequeued early
 231   msg_ptr->setDelayedCycles((g_eventQueue_ptr->getTime() - msg_ptr->getLastEnqueueTime())+msg_ptr->getDelayedCycles());
 232   msg_ptr->setLastEnqueueTime(arrival_time);
 233
 234   // Insert the message into the priority heap
 235   MessageBufferNode thisNode(arrival_time, m_msg_counter, message);
 236   m_prio_heap.insert(thisNode);
 237
 238   DEBUG_NEWLINE(QUEUE_COMP,HighPrio);
 239   DEBUG_MSG(QUEUE_COMP,HighPrio,"enqueue " + m_name
 240             + " with arrival_time " + int_to_string(arrival_time)
 241             + " cur_time: " + int_to_string(g_eventQueue_ptr->getTime()) + ".");
 242   DEBUG_EXPR(QUEUE_COMP,MedPrio,message);
 243   DEBUG_NEWLINE(QUEUE_COMP,HighPrio);
 244
 245   // Schedule the wakeup
 246   if (m_consumer_ptr != NULL) {
 247     g_eventQueue_ptr->scheduleEventAbsolute(m_consumer_ptr, arrival_time);
 248   } else {
 249     WARN_EXPR(*this);
 250     WARN_EXPR(m_name);
 251     ERROR_MSG("No consumer");
 252   }
 253 }
 254
 255 int MessageBuffer::dequeue_getDelayCycles(MsgPtr& message)
 256 {
 257   int delay_cycles = -1;  // null value
 258
 259   dequeue(message);
 260
 261   // get the delay cycles
 262   delay_cycles = setAndReturnDelayCycles(message);
 263
 264   assert(delay_cycles >= 0);
 265   return delay_cycles;
 266 }
 267
 268 void MessageBuffer::dequeue(MsgPtr& message)
 269 {
 270   DEBUG_MSG(QUEUE_COMP,MedPrio,"dequeue from " + m_name);
 271   message = m_prio_heap.peekMin().m_msgptr;
 272
 273   pop();
 274   DEBUG_EXPR(QUEUE_COMP,MedPrio,message);
 275 }
 276
 277 int MessageBuffer::dequeue_getDelayCycles()
 278 {
 279   int delay_cycles = -1;  // null value
 280
 281   // get MsgPtr of the message about to be dequeued
 282   MsgPtr message = m_prio_heap.peekMin().m_msgptr;
 283
 284   // get the delay cycles
 285   delay_cycles = setAndReturnDelayCycles(message);
 286
 287   dequeue();
 288
 289   assert(delay_cycles >= 0);
 290   return delay_cycles;
 291 }
 292
 293 void MessageBuffer::pop()
 294 {
 295   DEBUG_MSG(QUEUE_COMP,MedPrio,"pop from " + m_name);
 296   assert(isReady());
 297   Time ready_time = m_prio_heap.extractMin().m_time;
 298   // record previous size and time so the current buffer size isn't adjusted until next cycle
 299   if (m_time_last_time_pop < g_eventQueue_ptr->getTime()) {
 300     m_size_at_cycle_start = m_size;
 301     m_time_last_time_pop = g_eventQueue_ptr->getTime();
 302   }
 303   m_size--;
 304 }
 305
 306 void MessageBuffer::clear()
 307 {
 308   while(m_prio_heap.size() > 0){
 309     m_prio_heap.extractMin();
 310   }
 311
 312   ASSERT(m_prio_heap.size() == 0);
 313
 314   m_msg_counter = 0;
 315   m_size = 0;
 316   m_time_last_time_enqueue = 0;
 317   m_time_last_time_pop = 0;
 318   m_size_at_cycle_start = 0;
 319   m_msgs_this_cycle = 0;
 320 }
 321
 322 void MessageBuffer::recycle()
 323 {
 324   //  const int RECYCLE_LATENCY = 3;
 325   DEBUG_MSG(QUEUE_COMP,MedPrio,"recycling " + m_name);
 326   assert(isReady());
 327   MessageBufferNode node = m_prio_heap.extractMin();
 328   node.m_time = g_eventQueue_ptr->getTime() + RECYCLE_LATENCY;
 329   m_prio_heap.insert(node);
 330   g_eventQueue_ptr->scheduleEventAbsolute(m_consumer_ptr, g_eventQueue_ptr->getTime() + RECYCLE_LATENCY);
 331 }
 332
 333 int MessageBuffer::setAndReturnDelayCycles(MsgPtr& message)
 334 {
 335   int delay_cycles = -1;  // null value
 336
 337   // get the delay cycles of the message at the top of the queue
 338   Message* msg_ptr = message.ref();
 339
 340   // this function should only be called on dequeue
 341   // ensure the msg hasn't been enqueued
 342   assert(msg_ptr->getLastEnqueueTime() <= g_eventQueue_ptr->getTime());
 343   msg_ptr->setDelayedCycles((g_eventQueue_ptr->getTime() - msg_ptr->getLastEnqueueTime())+msg_ptr->getDelayedCycles());
 344   delay_cycles = msg_ptr->getDelayedCycles();
 345
 346   assert(delay_cycles >= 0);
 347   return delay_cycles;
 348 }
 349
 350 void MessageBuffer::print(ostream& out) const
 351 {
 352   out << "[MessageBuffer: ";
 353   if (m_consumer_ptr != NULL) {
 354     out << " consumer-yes ";
 355   }
 356   out << m_prio_heap << "] " << m_name << endl;
 357 }
 358
 359 void MessageBuffer::printStats(ostream& out)
 360 {
 361   out << "MessageBuffer: " << m_name << " stats - msgs:" << m_msg_counter << " full:" << m_not_avail_count << endl;
 362 }
 363