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