src/mem/ruby/network/garnet2.0/RoutingUnit.cc

   1 /*
   2  * Copyright (c) 2008 Princeton University
   3  * Copyright (c) 2016 Georgia Institute of Technology
   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 #include "mem/ruby/network/garnet2.0/RoutingUnit.hh"
  32
  33 #include "base/cast.hh"
  34 #include "debug/RubyNetwork.hh"
  35 #include "mem/ruby/network/garnet2.0/InputUnit.hh"
  36 #include "mem/ruby/network/garnet2.0/Router.hh"
  37 #include "mem/ruby/slicc_interface/Message.hh"
  38
  39 RoutingUnit::RoutingUnit(Router *router)
  40 {
  41     m_router = router;
  42     m_routing_table.clear();
  43     m_weight_table.clear();
  44 }
  45
  46 void
  47 RoutingUnit::addRoute(std::vector<NetDest>& routing_table_entry)
  48 {
  49     if (routing_table_entry.size() > m_routing_table.size()) {
  50         m_routing_table.resize(routing_table_entry.size());
  51     }
  52     for (int v = 0; v < routing_table_entry.size(); v++) {
  53         m_routing_table[v].push_back(routing_table_entry[v]);
  54     }
  55 }
  56
  57 void
  58 RoutingUnit::addWeight(int link_weight)
  59 {
  60     m_weight_table.push_back(link_weight);
  61 }
  62
  63 bool
  64 RoutingUnit::supportsVnet(int vnet, std::vector<int> sVnets)
  65 {
  66     // If all vnets are supported, return true
  67     if (sVnets.size() == 0) {
  68         return true;
  69     }
  70
  71     // Find the vnet in the vector, return true
  72     if (std::find(sVnets.begin(), sVnets.end(), vnet) != sVnets.end()) {
  73         return true;
  74     }
  75
  76     // Not supported vnet
  77     return false;
  78 }
  79
  80 /*
  81  * This is the default routing algorithm in garnet.
  82  * The routing table is populated during topology creation.
  83  * Routes can be biased via weight assignments in the topology file.
  84  * Correct weight assignments are critical to provide deadlock avoidance.
  85  */
  86 int
  87 RoutingUnit::lookupRoutingTable(int vnet, NetDest msg_destination)
  88 {
  89     // First find all possible output link candidates
  90     // For ordered vnet, just choose the first
  91     // (to make sure different packets don't choose different routes)
  92     // For unordered vnet, randomly choose any of the links
  93     // To have a strict ordering between links, they should be given
  94     // different weights in the topology file
  95
  96     int output_link = -1;
  97     int min_weight = INFINITE_;
  98     std::vector<int> output_link_candidates;
  99     int num_candidates = 0;
 100
 101     // Identify the minimum weight among the candidate output links
 102     for (int link = 0; link < m_routing_table[vnet].size(); link++) {
 103         if (msg_destination.intersectionIsNotEmpty(
 104             m_routing_table[vnet][link])) {
 105
 106         if (m_weight_table[link] <= min_weight)
 107             min_weight = m_weight_table[link];
 108         }
 109     }
 110
 111     // Collect all candidate output links with this minimum weight
 112     for (int link = 0; link < m_routing_table[vnet].size(); link++) {
 113         if (msg_destination.intersectionIsNotEmpty(
 114             m_routing_table[vnet][link])) {
 115
 116             if (m_weight_table[link] == min_weight) {
 117                 num_candidates++;
 118                 output_link_candidates.push_back(link);
 119             }
 120         }
 121     }
 122
 123     if (output_link_candidates.size() == 0) {
 124         fatal("Fatal Error:: No Route exists from this Router.");
 125         exit(0);
 126     }
 127
 128     // Randomly select any candidate output link
 129     int candidate = 0;
 130     if (!(m_router->get_net_ptr())->isVNetOrdered(vnet))
 131         candidate = rand() % num_candidates;
 132
 133     output_link = output_link_candidates.at(candidate);
 134     return output_link;
 135 }
 136
 137
 138 void
 139 RoutingUnit::addInDirection(PortDirection inport_dirn, int inport_idx)
 140 {
 141     m_inports_dirn2idx[inport_dirn] = inport_idx;
 142     m_inports_idx2dirn[inport_idx]  = inport_dirn;
 143 }
 144
 145 void
 146 RoutingUnit::addOutDirection(PortDirection outport_dirn, int outport_idx)
 147 {
 148     m_outports_dirn2idx[outport_dirn] = outport_idx;
 149     m_outports_idx2dirn[outport_idx]  = outport_dirn;
 150 }
 151
 152 // outportCompute() is called by the InputUnit
 153 // It calls the routing table by default.
 154 // A template for adaptive topology-specific routing algorithm
 155 // implementations using port directions rather than a static routing
 156 // table is provided here.
 157
 158 int
 159 RoutingUnit::outportCompute(RouteInfo route, int inport,
 160                             PortDirection inport_dirn)
 161 {
 162     int outport = -1;
 163
 164     if (route.dest_router == m_router->get_id()) {
 165
 166         // Multiple NIs may be connected to this router,
 167         // all with output port direction = "Local"
 168         // Get exact outport id from table
 169         outport = lookupRoutingTable(route.vnet, route.net_dest);
 170         return outport;
 171     }
 172
 173     // Routing Algorithm set in GarnetNetwork.py
 174     // Can be over-ridden from command line using --routing-algorithm = 1
 175     RoutingAlgorithm routing_algorithm =
 176         (RoutingAlgorithm) m_router->get_net_ptr()->getRoutingAlgorithm();
 177
 178     switch (routing_algorithm) {
 179         case TABLE_:  outport =
 180             lookupRoutingTable(route.vnet, route.net_dest); break;
 181         case XY_:     outport =
 182             outportComputeXY(route, inport, inport_dirn); break;
 183         // any custom algorithm
 184         case CUSTOM_: outport =
 185             outportComputeCustom(route, inport, inport_dirn); break;
 186         default: outport =
 187             lookupRoutingTable(route.vnet, route.net_dest); break;
 188     }
 189
 190     assert(outport != -1);
 191     return outport;
 192 }
 193
 194 // XY routing implemented using port directions
 195 // Only for reference purpose in a Mesh
 196 // By default Garnet uses the routing table
 197 int
 198 RoutingUnit::outportComputeXY(RouteInfo route,
 199                               int inport,
 200                               PortDirection inport_dirn)
 201 {
 202     PortDirection outport_dirn = "Unknown";
 203
 204     int M5_VAR_USED num_rows = m_router->get_net_ptr()->getNumRows();
 205     int num_cols = m_router->get_net_ptr()->getNumCols();
 206     assert(num_rows > 0 && num_cols > 0);
 207
 208     int my_id = m_router->get_id();
 209     int my_x = my_id % num_cols;
 210     int my_y = my_id / num_cols;
 211
 212     int dest_id = route.dest_router;
 213     int dest_x = dest_id % num_cols;
 214     int dest_y = dest_id / num_cols;
 215
 216     int x_hops = abs(dest_x - my_x);
 217     int y_hops = abs(dest_y - my_y);
 218
 219     bool x_dirn = (dest_x >= my_x);
 220     bool y_dirn = (dest_y >= my_y);
 221
 222     // already checked that in outportCompute() function
 223     assert(!(x_hops == 0 && y_hops == 0));
 224
 225     if (x_hops > 0) {
 226         if (x_dirn) {
 227             assert(inport_dirn == "Local" || inport_dirn == "West");
 228             outport_dirn = "East";
 229         } else {
 230             assert(inport_dirn == "Local" || inport_dirn == "East");
 231             outport_dirn = "West";
 232         }
 233     } else if (y_hops > 0) {
 234         if (y_dirn) {
 235             // "Local" or "South" or "West" or "East"
 236             assert(inport_dirn != "North");
 237             outport_dirn = "North";
 238         } else {
 239             // "Local" or "North" or "West" or "East"
 240             assert(inport_dirn != "South");
 241             outport_dirn = "South";
 242         }
 243     } else {
 244         // x_hops == 0 and y_hops == 0
 245         // this is not possible
 246         // already checked that in outportCompute() function
 247         panic("x_hops == y_hops == 0");
 248     }
 249
 250     return m_outports_dirn2idx[outport_dirn];
 251 }
 252
 253 // Template for implementing custom routing algorithm
 254 // using port directions. (Example adaptive)
 255 int
 256 RoutingUnit::outportComputeCustom(RouteInfo route,
 257                                  int inport,
 258                                  PortDirection inport_dirn)
 259 {
 260     panic("%s placeholder executed", __FUNCTION__);
 261 }