src/mem/ruby/network/garnet/flexible-pipeline/Router.cc

   1 /*
   2  * Copyright (c) 2008 Princeton University
   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  * Authors: Niket Agarwal
  29  */
  30
  31 #include "base/cast.hh"
  32 #include "base/stl_helpers.hh"
  33 #include "debug/RubyNetwork.hh"
  34 #include "mem/ruby/network/garnet/flexible-pipeline/InVcState.hh"
  35 #include "mem/ruby/network/garnet/flexible-pipeline/OutVcState.hh"
  36 #include "mem/ruby/network/garnet/flexible-pipeline/Router.hh"
  37 #include "mem/ruby/network/garnet/flexible-pipeline/VCarbiter.hh"
  38 #include "mem/ruby/slicc_interface/NetworkMessage.hh"
  39
  40 using namespace std;
  41 using m5::stl_helpers::deletePointers;
  42
  43 Router::Router(const Params *p)
  44     : BasicRouter(p), FlexibleConsumer(this)
  45 {
  46     m_id = p->router_id;
  47     m_virtual_networks = p->virt_nets;
  48     m_vc_per_vnet = p->vcs_per_vnet;
  49     m_round_robin_inport = 0;
  50     m_round_robin_start = 0;
  51     m_num_vcs = m_vc_per_vnet * m_virtual_networks;
  52     m_vc_arbiter = new VCarbiter(this);
  53 }
  54
  55 Router::~Router()
  56 {
  57     for (int i = 0; i < m_in_link.size(); i++) {
  58         deletePointers(m_in_vc_state[i]);
  59     }
  60     for (int i = 0; i < m_out_link.size(); i++) {
  61         deletePointers(m_out_vc_state[i]);
  62         deletePointers(m_router_buffers[i]);
  63     }
  64     deletePointers(m_out_src_queue);
  65     delete m_vc_arbiter;
  66 }
  67
  68 void
  69 Router::addInPort(NetworkLink *in_link)
  70 {
  71     int port = m_in_link.size();
  72     vector<InVcState *> in_vc_vector;
  73     for (int i = 0; i < m_num_vcs; i++) {
  74         in_vc_vector.push_back(new InVcState(i));
  75         in_vc_vector[i]->setState(IDLE_, g_system_ptr->getTime());
  76     }
  77     m_in_vc_state.push_back(in_vc_vector);
  78     m_in_link.push_back(in_link);
  79     in_link->setLinkConsumer(this);
  80     in_link->setInPort(port);
  81
  82     int start = 0;
  83     m_round_robin_invc.push_back(start);
  84 }
  85
  86 void
  87 Router::addOutPort(NetworkLink *out_link, const NetDest& routing_table_entry,
  88                    int link_weight)
  89 {
  90     int port = m_out_link.size();
  91     out_link->setOutPort(port);
  92     int start = 0;
  93     m_vc_round_robin.push_back(start);
  94
  95     m_out_src_queue.push_back(new flitBuffer());
  96
  97     m_out_link.push_back(out_link);
  98     m_routing_table.push_back(routing_table_entry);
  99     out_link->setSourceQueue(m_out_src_queue[port]);
 100     out_link->setSource(this);
 101
 102     vector<flitBuffer *> intermediateQueues;
 103     for (int i = 0; i < m_num_vcs; i++) {
 104         int buffer_size = m_net_ptr->getBufferSize();
 105         if (buffer_size > 0) // finite size
 106             intermediateQueues.push_back(new flitBuffer(buffer_size));
 107         else // infinite size
 108             intermediateQueues.push_back(new flitBuffer());
 109     }
 110     m_router_buffers.push_back(intermediateQueues);
 111
 112     vector<OutVcState *> out_vc_vector;
 113     for (int i = 0; i < m_num_vcs; i++) {
 114         out_vc_vector.push_back(new OutVcState(i));
 115         out_vc_vector[i]->setState(IDLE_, g_system_ptr->getTime());
 116     }
 117     m_out_vc_state.push_back(out_vc_vector);
 118     m_link_weights.push_back(link_weight);
 119 }
 120
 121 bool
 122 Router::isBufferNotFull(int vc, int inport)
 123 {
 124     int outport = m_in_vc_state[inport][vc]->get_outport();
 125     int outvc = m_in_vc_state[inport][vc]->get_outvc();
 126
 127     return (!m_router_buffers[outport][outvc]->isFull());
 128 }
 129
 130 // A request for an output vc has been placed by an upstream Router/NI.
 131 // This has to be updated and arbitration performed
 132 void
 133 Router::request_vc(int in_vc, int in_port, NetDest destination,
 134                    Time request_time)
 135 {
 136     assert(m_in_vc_state[in_port][in_vc]->isInState(IDLE_, request_time));
 137
 138     int outport = getRoute(destination);
 139     m_in_vc_state[in_port][in_vc]->setRoute(outport);
 140     m_in_vc_state[in_port][in_vc]->setState(VC_AB_, request_time);
 141     assert(request_time >= g_system_ptr->getTime());
 142     if (request_time > g_system_ptr->getTime())
 143         m_vc_arbiter->scheduleEventAbsolute(request_time);
 144     else
 145         vc_arbitrate();
 146 }
 147
 148 void
 149 Router::vc_arbitrate()
 150 {
 151     int inport = m_round_robin_inport;
 152     m_round_robin_inport++;
 153     if (m_round_robin_inport == m_in_link.size())
 154         m_round_robin_inport = 0;
 155
 156     for (int port_iter = 0; port_iter < m_in_link.size(); port_iter++) {
 157         inport++;
 158         if (inport >= m_in_link.size())
 159             inport = 0;
 160         int invc = m_round_robin_invc[inport];
 161
 162         int next_round_robin_invc = invc;
 163         do {
 164             next_round_robin_invc++;
 165
 166             if (next_round_robin_invc >= m_num_vcs)
 167                 next_round_robin_invc = 0;
 168
 169         } while (!(m_net_ptr->validVirtualNetwork(
 170                    get_vnet(next_round_robin_invc))));
 171
 172         m_round_robin_invc[inport] = next_round_robin_invc;
 173
 174         for (int vc_iter = 0; vc_iter < m_num_vcs; vc_iter++) {
 175             invc++;
 176             if (invc >= m_num_vcs)
 177                 invc = 0;
 178
 179             if (!(m_net_ptr->validVirtualNetwork(get_vnet(invc))))
 180                 continue;
 181
 182             InVcState *in_vc_state = m_in_vc_state[inport][invc];
 183
 184             if (in_vc_state->isInState(VC_AB_, g_system_ptr->getTime())) {
 185                 int outport = in_vc_state->get_outport();
 186                 vector<int> valid_vcs = get_valid_vcs(invc);
 187                 for (int valid_vc_iter = 0; valid_vc_iter < valid_vcs.size();
 188                         valid_vc_iter++) {
 189                     if (m_out_vc_state[outport][valid_vcs[valid_vc_iter]]
 190                             ->isInState(IDLE_, g_system_ptr->getTime())) {
 191
 192                         in_vc_state->grant_vc(valid_vcs[valid_vc_iter],
 193                                 g_system_ptr->getTime());
 194
 195                         m_in_link[inport]->grant_vc_link(invc,
 196                                 g_system_ptr->getTime());
 197
 198                         m_out_vc_state[outport][valid_vcs[valid_vc_iter]]
 199                             ->setState(VC_AB_, g_system_ptr->getTime());
 200                         break;
 201                     }
 202                 }
 203             }
 204         }
 205     }
 206 }
 207
 208 vector<int>
 209 Router::get_valid_vcs(int invc)
 210 {
 211     vector<int> vc_list;
 212
 213     for (int vnet = 0; vnet < m_virtual_networks; vnet++) {
 214         if (invc >= (vnet*m_vc_per_vnet) && invc < ((vnet+1)*m_vc_per_vnet)) {
 215             int base = vnet*m_vc_per_vnet;
 216             int vc_per_vnet;
 217             if (m_net_ptr->isVNetOrdered(vnet))
 218                 vc_per_vnet = 1;
 219             else
 220                 vc_per_vnet = m_vc_per_vnet;
 221
 222             for (int offset = 0; offset < vc_per_vnet; offset++) {
 223                 vc_list.push_back(base+offset);
 224             }
 225             break;
 226         }
 227     }
 228     return vc_list;
 229 }
 230
 231 void
 232 Router::grant_vc(int out_port, int vc, Time grant_time)
 233 {
 234     assert(m_out_vc_state[out_port][vc]->isInState(VC_AB_, grant_time));
 235     m_out_vc_state[out_port][vc]->grant_vc(grant_time);
 236     scheduleEvent(1);
 237 }
 238
 239 void
 240 Router::release_vc(int out_port, int vc, Time release_time)
 241 {
 242     assert(m_out_vc_state[out_port][vc]->isInState(ACTIVE_, release_time));
 243     m_out_vc_state[out_port][vc]->setState(IDLE_, release_time);
 244     scheduleEvent(1);
 245 }
 246
 247 // This function calculated the output port for a particular destination.
 248 int
 249 Router::getRoute(NetDest destination)
 250 {
 251     int output_link = -1;
 252     int min_weight = INFINITE_;
 253     for (int link = 0; link < m_routing_table.size(); link++) {
 254         if (destination.intersectionIsNotEmpty(m_routing_table[link])) {
 255             if ((m_link_weights[link] >= min_weight))
 256                 continue;
 257             output_link = link;
 258             min_weight = m_link_weights[link];
 259         }
 260     }
 261     return output_link;
 262 }
 263
 264 void
 265 Router::routeCompute(flit *m_flit, int inport)
 266 {
 267     int invc = m_flit->get_vc();
 268     int outport = m_in_vc_state[inport][invc]->get_outport();
 269     int outvc = m_in_vc_state[inport][invc]->get_outvc();
 270
 271     assert(m_net_ptr->getNumPipeStages() >= 1);
 272
 273     // Subtract 1 as 1 cycle will be consumed in scheduling the output link
 274     m_flit->set_time(g_system_ptr->getTime() +
 275                      (m_net_ptr->getNumPipeStages() - 1));
 276     m_flit->set_vc(outvc);
 277     m_router_buffers[outport][outvc]->insert(m_flit);
 278
 279     if (m_net_ptr->getNumPipeStages() > 1)
 280         scheduleEvent(m_net_ptr->getNumPipeStages() - 1 );
 281     if ((m_flit->get_type() == HEAD_) || (m_flit->get_type() == HEAD_TAIL_)) {
 282         NetworkMessage *nm =
 283             safe_cast<NetworkMessage*>(m_flit->get_msg_ptr().get());
 284         NetDest destination = nm->getInternalDestination();
 285
 286         if (m_net_ptr->getNumPipeStages() > 1) {
 287             m_out_vc_state[outport][outvc]->setState(VC_AB_,
 288                 g_system_ptr->getTime() + 1);
 289
 290             m_out_link[outport]->request_vc_link(outvc, destination,
 291                 g_system_ptr->getTime() + 1);
 292         } else {
 293             m_out_vc_state[outport][outvc]->setState(VC_AB_,
 294                 g_system_ptr->getTime());
 295
 296             m_out_link[outport]->request_vc_link(outvc, destination,
 297                 g_system_ptr->getTime());
 298         }
 299     }
 300     if ((m_flit->get_type() == TAIL_) || (m_flit->get_type() == HEAD_TAIL_)) {
 301         m_in_vc_state[inport][invc]->setState(IDLE_,
 302             g_system_ptr->getTime() + 1);
 303
 304         m_in_link[inport]->release_vc_link(invc,
 305             g_system_ptr->getTime() + 1);
 306     }
 307 }
 308
 309 void
 310 Router::wakeup()
 311 {
 312     flit *t_flit;
 313
 314     // This is for round-robin scheduling of incoming ports
 315     int incoming_port = m_round_robin_start;
 316     m_round_robin_start++;
 317     if (m_round_robin_start >= m_in_link.size()) {
 318         m_round_robin_start = 0;
 319     }
 320
 321     for (int port = 0; port < m_in_link.size(); port++) {
 322         // Round robin scheduling
 323         incoming_port++;
 324         if (incoming_port >= m_in_link.size())
 325             incoming_port = 0;
 326
 327         // checking the incoming link
 328         if (m_in_link[incoming_port]->isReady()) {
 329             DPRINTF(RubyNetwork, "m_id: %d, Time: %lld\n",
 330                     m_id, g_system_ptr->getTime());
 331             t_flit = m_in_link[incoming_port]->peekLink();
 332             routeCompute(t_flit, incoming_port);
 333             m_in_link[incoming_port]->consumeLink();
 334         }
 335     }
 336     scheduleOutputLinks();
 337     checkReschedule(); // This is for flits lying in the router buffers
 338     vc_arbitrate();
 339     check_arbiter_reschedule();
 340 }
 341
 342 void
 343 Router::scheduleOutputLinks()
 344 {
 345     for (int port = 0; port < m_out_link.size(); port++) {
 346         int vc_tolookat = m_vc_round_robin[port];
 347
 348         int next_round_robin_vc_tolookat = vc_tolookat;
 349         do {
 350             next_round_robin_vc_tolookat++;
 351
 352             if (next_round_robin_vc_tolookat == m_num_vcs)
 353                 next_round_robin_vc_tolookat = 0;
 354         } while (!(m_net_ptr->validVirtualNetwork(
 355                    get_vnet(next_round_robin_vc_tolookat))));
 356
 357         m_vc_round_robin[port] = next_round_robin_vc_tolookat;
 358
 359         for (int i = 0; i < m_num_vcs; i++) {
 360             vc_tolookat++;
 361             if (vc_tolookat == m_num_vcs)
 362                 vc_tolookat = 0;
 363
 364             if (m_router_buffers[port][vc_tolookat]->isReady()) {
 365
 366                 // models buffer backpressure
 367                 if (m_out_vc_state[port][vc_tolookat]->isInState(ACTIVE_,
 368                    g_system_ptr->getTime()) &&
 369                    m_out_link[port]->isBufferNotFull_link(vc_tolookat)) {
 370
 371                     flit *t_flit =
 372                         m_router_buffers[port][vc_tolookat]->getTopFlit();
 373                     t_flit->set_time(g_system_ptr->getTime() + 1 );
 374                     m_out_src_queue[port]->insert(t_flit);
 375                     m_out_link[port]->scheduleEvent(1);
 376                     break; // done for this port
 377                 }
 378             }
 379         }
 380     }
 381 }
 382
 383 int
 384 Router::get_vnet(int vc)
 385 {
 386     int vnet = vc/m_vc_per_vnet;
 387     assert(vnet < m_virtual_networks);
 388     return vnet;
 389 }
 390
 391 void
 392 Router::checkReschedule()
 393 {
 394     for (int port = 0; port < m_out_link.size(); port++) {
 395         for (int vc = 0; vc < m_num_vcs; vc++) {
 396             if (m_router_buffers[port][vc]->isReadyForNext()) {
 397                 scheduleEvent(1);
 398                 return;
 399             }
 400         }
 401     }
 402 }
 403
 404 void
 405 Router::check_arbiter_reschedule()
 406 {
 407     for (int port = 0; port < m_in_link.size(); port++) {
 408         for (int vc = 0; vc < m_num_vcs; vc++) {
 409             if (m_in_vc_state[port][vc]->isInState(VC_AB_,
 410                g_system_ptr->getTime() + 1)) {
 411
 412                 m_vc_arbiter->scheduleEvent(1);
 413                 return;
 414             }
 415         }
 416     }
 417 }
 418
 419 void
 420 Router::print(ostream& out) const
 421 {
 422     out << "[Router]";
 423 }
 424
 425 Router *
 426 GarnetRouterParams::create()
 427 {
 428     return new Router(this);
 429 }