src/mem/ruby/network/simple/PerfectSwitch.cc

   1 /*
   2  * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include "mem/ruby/network/simple/PerfectSwitch.hh"
  30
  31 #include <algorithm>
  32
  33 #include "base/cast.hh"
  34 #include "base/cprintf.hh"
  35 #include "base/random.hh"
  36 #include "debug/RubyNetwork.hh"
  37 #include "mem/ruby/network/MessageBuffer.hh"
  38 #include "mem/ruby/network/simple/SimpleNetwork.hh"
  39 #include "mem/ruby/network/simple/Switch.hh"
  40 #include "mem/ruby/slicc_interface/Message.hh"
  41
  42 const int PRIORITY_SWITCH_LIMIT = 128;
  43
  44 // Operator for helper class
  45 bool
  46 operator<(const LinkOrder& l1, const LinkOrder& l2)
  47 {
  48     return (l1.m_value < l2.m_value);
  49 }
  50
  51 PerfectSwitch::PerfectSwitch(SwitchID sid, Switch *sw, uint32_t virt_nets)
  52     : Consumer(sw), m_switch_id(sid), m_switch(sw)
  53 {
  54     m_round_robin_start = 0;
  55     m_wakeups_wo_switch = 0;
  56     m_virtual_networks = virt_nets;
  57 }
  58
  59 void
  60 PerfectSwitch::init(SimpleNetwork *network_ptr)
  61 {
  62     m_network_ptr = network_ptr;
  63
  64     for (int i = 0;i < m_virtual_networks;++i) {
  65         m_pending_message_count.push_back(0);
  66     }
  67 }
  68
  69 void
  70 PerfectSwitch::addInPort(const std::vector<MessageBuffer*>& in)
  71 {
  72     NodeID port = m_in.size();
  73     m_in.push_back(in);
  74
  75     for (int i = 0; i < in.size(); ++i) {
  76         if (in[i] != nullptr) {
  77             in[i]->setConsumer(this);
  78             in[i]->setIncomingLink(port);
  79             in[i]->setVnet(i);
  80         }
  81     }
  82 }
  83
  84 void
  85 PerfectSwitch::addOutPort(const std::vector<MessageBuffer*>& out,
  86                           const NetDest& routing_table_entry)
  87 {
  88     // Setup link order
  89     LinkOrder l;
  90     l.m_value = 0;
  91     l.m_link = m_out.size();
  92     m_link_order.push_back(l);
  93
  94     // Add to routing table
  95     m_out.push_back(out);
  96     m_routing_table.push_back(routing_table_entry);
  97 }
  98
  99 PerfectSwitch::~PerfectSwitch()
 100 {
 101 }
 102
 103 void
 104 PerfectSwitch::operateVnet(int vnet)
 105 {
 106     // This is for round-robin scheduling
 107     int incoming = m_round_robin_start;
 108     m_round_robin_start++;
 109     if (m_round_robin_start >= m_in.size()) {
 110         m_round_robin_start = 0;
 111     }
 112
 113     if (m_pending_message_count[vnet] > 0) {
 114         // for all input ports, use round robin scheduling
 115         for (int counter = 0; counter < m_in.size(); counter++) {
 116             // Round robin scheduling
 117             incoming++;
 118             if (incoming >= m_in.size()) {
 119                 incoming = 0;
 120             }
 121
 122             // Is there a message waiting?
 123             if (m_in[incoming].size() <= vnet) {
 124                 continue;
 125             }
 126
 127             MessageBuffer *buffer = m_in[incoming][vnet];
 128             if (buffer == nullptr) {
 129                 continue;
 130             }
 131
 132             operateMessageBuffer(buffer, incoming, vnet);
 133         }
 134     }
 135 }
 136
 137 void
 138 PerfectSwitch::operateMessageBuffer(MessageBuffer *buffer, int incoming,
 139                                     int vnet)
 140 {
 141     MsgPtr msg_ptr;
 142     Message *net_msg_ptr = NULL;
 143
 144     // temporary vectors to store the routing results
 145     std::vector<LinkID> output_links;
 146     std::vector<NetDest> output_link_destinations;
 147     Tick current_time = m_switch->clockEdge();
 148
 149     while (buffer->isReady(current_time)) {
 150         DPRINTF(RubyNetwork, "incoming: %d\n", incoming);
 151
 152         // Peek at message
 153         msg_ptr = buffer->peekMsgPtr();
 154         net_msg_ptr = msg_ptr.get();
 155         DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr));
 156
 157         output_links.clear();
 158         output_link_destinations.clear();
 159         NetDest msg_dsts = net_msg_ptr->getDestination();
 160
 161         // Unfortunately, the token-protocol sends some
 162         // zero-destination messages, so this assert isn't valid
 163         // assert(msg_dsts.count() > 0);
 164
 165         assert(m_link_order.size() == m_routing_table.size());
 166         assert(m_link_order.size() == m_out.size());
 167
 168         if (m_network_ptr->getAdaptiveRouting()) {
 169             if (m_network_ptr->isVNetOrdered(vnet)) {
 170                 // Don't adaptively route
 171                 for (int out = 0; out < m_out.size(); out++) {
 172                     m_link_order[out].m_link = out;
 173                     m_link_order[out].m_value = 0;
 174                 }
 175             } else {
 176                 // Find how clogged each link is
 177                 for (int out = 0; out < m_out.size(); out++) {
 178                     int out_queue_length = 0;
 179                     for (int v = 0; v < m_virtual_networks; v++) {
 180                         out_queue_length += m_out[out][v]->getSize(current_time);
 181                     }
 182                     int value =
 183                         (out_queue_length << 8) |
 184                         random_mt.random(0, 0xff);
 185                     m_link_order[out].m_link = out;
 186                     m_link_order[out].m_value = value;
 187                 }
 188
 189                 // Look at the most empty link first
 190                 sort(m_link_order.begin(), m_link_order.end());
 191             }
 192         }
 193
 194         for (int i = 0; i < m_routing_table.size(); i++) {
 195             // pick the next link to look at
 196             int link = m_link_order[i].m_link;
 197             NetDest dst = m_routing_table[link];
 198             DPRINTF(RubyNetwork, "dst: %s\n", dst);
 199
 200             if (!msg_dsts.intersectionIsNotEmpty(dst))
 201                 continue;
 202
 203             // Remember what link we're using
 204             output_links.push_back(link);
 205
 206             // Need to remember which destinations need this message in
 207             // another vector.  This Set is the intersection of the
 208             // routing_table entry and the current destination set.  The
 209             // intersection must not be empty, since we are inside "if"
 210             output_link_destinations.push_back(msg_dsts.AND(dst));
 211
 212             // Next, we update the msg_destination not to include
 213             // those nodes that were already handled by this link
 214             msg_dsts.removeNetDest(dst);
 215         }
 216
 217         assert(msg_dsts.count() == 0);
 218
 219         // Check for resources - for all outgoing queues
 220         bool enough = true;
 221         for (int i = 0; i < output_links.size(); i++) {
 222             int outgoing = output_links[i];
 223
 224             if (!m_out[outgoing][vnet]->areNSlotsAvailable(1, current_time))
 225                 enough = false;
 226
 227             DPRINTF(RubyNetwork, "Checking if node is blocked ..."
 228                     "outgoing: %d, vnet: %d, enough: %d\n",
 229                     outgoing, vnet, enough);
 230         }
 231
 232         // There were not enough resources
 233         if (!enough) {
 234             scheduleEvent(Cycles(1));
 235             DPRINTF(RubyNetwork, "Can't deliver message since a node "
 236                     "is blocked\n");
 237             DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr));
 238             break; // go to next incoming port
 239         }
 240
 241         MsgPtr unmodified_msg_ptr;
 242
 243         if (output_links.size() > 1) {
 244             // If we are sending this message down more than one link
 245             // (size>1), we need to make a copy of the message so each
 246             // branch can have a different internal destination we need
 247             // to create an unmodified MsgPtr because the MessageBuffer
 248             // enqueue func will modify the message
 249
 250             // This magic line creates a private copy of the message
 251             unmodified_msg_ptr = msg_ptr->clone();
 252         }
 253
 254         // Dequeue msg
 255         buffer->dequeue(current_time);
 256         m_pending_message_count[vnet]--;
 257
 258         // Enqueue it - for all outgoing queues
 259         for (int i=0; i<output_links.size(); i++) {
 260             int outgoing = output_links[i];
 261
 262             if (i > 0) {
 263                 // create a private copy of the unmodified message
 264                 msg_ptr = unmodified_msg_ptr->clone();
 265             }
 266
 267             // Change the internal destination set of the message so it
 268             // knows which destinations this link is responsible for.
 269             net_msg_ptr = msg_ptr.get();
 270             net_msg_ptr->getDestination() = output_link_destinations[i];
 271
 272             // Enqeue msg
 273             DPRINTF(RubyNetwork, "Enqueuing net msg from "
 274                     "inport[%d][%d] to outport [%d][%d].\n",
 275                     incoming, vnet, outgoing, vnet);
 276
 277             m_out[outgoing][vnet]->enqueue(msg_ptr, current_time,
 278                                            m_switch->cyclesToTicks(Cycles(1)));
 279         }
 280     }
 281 }
 282
 283 void
 284 PerfectSwitch::wakeup()
 285 {
 286     // Give the highest numbered link priority most of the time
 287     m_wakeups_wo_switch++;
 288     int highest_prio_vnet = m_virtual_networks-1;
 289     int lowest_prio_vnet = 0;
 290     int decrementer = 1;
 291
 292     // invert priorities to avoid starvation seen in the component network
 293     if (m_wakeups_wo_switch > PRIORITY_SWITCH_LIMIT) {
 294         m_wakeups_wo_switch = 0;
 295         highest_prio_vnet = 0;
 296         lowest_prio_vnet = m_virtual_networks-1;
 297         decrementer = -1;
 298     }
 299
 300     // For all components incoming queues
 301     for (int vnet = highest_prio_vnet;
 302          (vnet * decrementer) >= (decrementer * lowest_prio_vnet);
 303          vnet -= decrementer) {
 304         operateVnet(vnet);
 305     }
 306 }
 307
 308 void
 309 PerfectSwitch::storeEventInfo(int info)
 310 {
 311     m_pending_message_count[info]++;
 312 }
 313
 314 void
 315 PerfectSwitch::clearStats()
 316 {
 317 }
 318 void
 319 PerfectSwitch::collateStats()
 320 {
 321 }
 322
 323
 324 void
 325 PerfectSwitch::print(std::ostream& out) const
 326 {
 327     out << "[PerfectSwitch " << m_switch_id << "]";
 328 }