From dbe8892b761067c5c1e828f889a513ea085b044f Mon Sep 17 00:00:00 2001 From: Tushar Krishna Date: Thu, 6 Oct 2016 14:35:22 -0400 Subject: ruby: garnet2.0 Revamped version of garnet with more optimized single-cycle routers, more configurability, and cleaner code. --- src/mem/ruby/network/garnet2.0/RoutingUnit.cc | 241 ++++++++++++++++++++++++++ 1 file changed, 241 insertions(+) create mode 100644 src/mem/ruby/network/garnet2.0/RoutingUnit.cc (limited to 'src/mem/ruby/network/garnet2.0/RoutingUnit.cc') diff --git a/src/mem/ruby/network/garnet2.0/RoutingUnit.cc b/src/mem/ruby/network/garnet2.0/RoutingUnit.cc new file mode 100644 index 000000000..aa5ff53c1 --- /dev/null +++ b/src/mem/ruby/network/garnet2.0/RoutingUnit.cc @@ -0,0 +1,241 @@ +/* + * Copyright (c) 2008 Princeton University + * Copyright (c) 2016 Georgia Institute of Technology + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Authors: Niket Agarwal + * Tushar Krishna + */ + + +#include "mem/ruby/network/garnet2.0/RoutingUnit.hh" + +#include "base/cast.hh" +#include "mem/ruby/network/garnet2.0/InputUnit.hh" +#include "mem/ruby/network/garnet2.0/Router.hh" +#include "mem/ruby/slicc_interface/Message.hh" + +RoutingUnit::RoutingUnit(Router *router) +{ + m_router = router; + m_routing_table.clear(); + m_weight_table.clear(); +} + +void +RoutingUnit::addRoute(const NetDest& routing_table_entry) +{ + m_routing_table.push_back(routing_table_entry); +} + +void +RoutingUnit::addWeight(int link_weight) +{ + m_weight_table.push_back(link_weight); +} + +/* + * This is the default routing algorithm in garnet. + * The routing table is populated during topology creation. + * Routes can be biased via weight assignments in the topology file. + * Correct weight assignments are critical to provide deadlock avoidance. + */ + +int +RoutingUnit::lookupRoutingTable(int vnet, NetDest msg_destination) +{ + // First find all possible output link candidates + // For ordered vnet, just choose the first + // (to make sure different packets don't choose different routes) + // For unordered vnet, randomly choose any of the links + // To have a strict ordering between links, they should be given + // different weights in the topology file + + int output_link = -1; + int min_weight = INFINITE_; + std::vector output_link_candidates; + int num_candidates = 0; + + // Identify the minimum weight among the candidate output links + for (int link = 0; link < m_routing_table.size(); link++) { + if (msg_destination.intersectionIsNotEmpty(m_routing_table[link])) { + + if (m_weight_table[link] <= min_weight) + min_weight = m_weight_table[link]; + } + } + + // Collect all candidate output links with this minimum weight + for (int link = 0; link < m_routing_table.size(); link++) { + if (msg_destination.intersectionIsNotEmpty(m_routing_table[link])) { + + if (m_weight_table[link] == min_weight) { + + num_candidates++; + output_link_candidates.push_back(link); + } + } + } + + if (output_link_candidates.size() == 0) { + fatal("Fatal Error:: No Route exists from this Router."); + exit(0); + } + + // Randomly select any candidate output link + int candidate = 0; + if (!(m_router->get_net_ptr())->isVNetOrdered(vnet)) + candidate = rand() % num_candidates; + + output_link = output_link_candidates.at(candidate); + return output_link; +} + + +void +RoutingUnit::addInDirection(PortDirection inport_dirn, int inport_idx) +{ + m_inports_dirn2idx[inport_dirn] = inport_idx; + m_inports_idx2dirn[inport_idx] = inport_dirn; +} + +void +RoutingUnit::addOutDirection(PortDirection outport_dirn, int outport_idx) +{ + m_outports_dirn2idx[outport_dirn] = outport_idx; + m_outports_idx2dirn[outport_idx] = outport_dirn; +} + +// outportCompute() is called by the InputUnit +// It calls the routing table by default. +// A template for adaptive topology-specific routing algorithm +// implementations using port directions rather than a static routing +// table is provided here. + +int +RoutingUnit::outportCompute(RouteInfo route, int inport, + PortDirection inport_dirn) +{ + int outport = -1; + + if (route.dest_router == m_router->get_id()) { + + // Multiple NIs may be connected to this router, + // all with output port direction = "Local" + // Get exact outport id from table + outport = lookupRoutingTable(route.vnet, route.net_dest); + return outport; + } + + // Routing Algorithm set in GarnetNetwork.py + // Can be over-ridden from command line using --routing-algorithm = 1 + RoutingAlgorithm routing_algorithm = + (RoutingAlgorithm) m_router->get_net_ptr()->getRoutingAlgorithm(); + + switch (routing_algorithm) { + case TABLE_: outport = + lookupRoutingTable(route.vnet, route.net_dest); break; + case XY_: outport = + outportComputeXY(route, inport, inport_dirn); break; + // any custom algorithm + case CUSTOM_: outport = + outportComputeCustom(route, inport, inport_dirn); break; + default: outport = + lookupRoutingTable(route.vnet, route.net_dest); break; + } + + assert(outport != -1); + return outport; +} + +// XY routing implemented using port directions +// Only for reference purpose in a Mesh +// By default Garnet uses the routing table +int +RoutingUnit::outportComputeXY(RouteInfo route, + int inport, + PortDirection inport_dirn) +{ + PortDirection outport_dirn = "Unknown"; + + int num_rows = m_router->get_net_ptr()->getNumRows(); + int num_cols = m_router->get_net_ptr()->getNumCols(); + assert(num_rows > 0 && num_cols > 0); + + int my_id = m_router->get_id(); + int my_x = my_id % num_cols; + int my_y = my_id / num_cols; + + int dest_id = route.dest_router; + int dest_x = dest_id % num_cols; + int dest_y = dest_id / num_cols; + + int x_hops = abs(dest_x - my_x); + int y_hops = abs(dest_y - my_y); + + bool x_dirn = (dest_x >= my_x); + bool y_dirn = (dest_y >= my_y); + + // already checked that in outportCompute() function + assert(!(x_hops == 0 && y_hops == 0)); + + if (x_hops > 0) { + if (x_dirn) { + assert(inport_dirn == "Local" || inport_dirn == "West"); + outport_dirn = "East"; + } else { + assert(inport_dirn == "Local" || inport_dirn == "East"); + outport_dirn = "West"; + } + } else if (y_hops > 0) { + if (y_dirn) { + // "Local" or "South" or "West" or "East" + assert(inport_dirn != "North"); + outport_dirn = "North"; + } else { + // "Local" or "North" or "West" or "East" + assert(inport_dirn != "South"); + outport_dirn = "South"; + } + } else { + // x_hops == 0 and y_hops == 0 + // this is not possible + // already checked that in outportCompute() function + assert(0); + } + + return m_outports_dirn2idx[outport_dirn]; +} + +// Template for implementing custom routing algorithm +// using port directions. (Example adaptive) +int +RoutingUnit::outportComputeCustom(RouteInfo route, + int inport, + PortDirection inport_dirn) +{ + assert(0); +} -- cgit v1.2.3