111666Stushar@ece.gatech.edu/* 211666Stushar@ece.gatech.edu * Copyright (c) 2008 Princeton University 311666Stushar@ece.gatech.edu * Copyright (c) 2016 Georgia Institute of Technology 411666Stushar@ece.gatech.edu * All rights reserved. 511666Stushar@ece.gatech.edu * 611666Stushar@ece.gatech.edu * Redistribution and use in source and binary forms, with or without 711666Stushar@ece.gatech.edu * modification, are permitted provided that the following conditions are 811666Stushar@ece.gatech.edu * met: redistributions of source code must retain the above copyright 911666Stushar@ece.gatech.edu * notice, this list of conditions and the following disclaimer; 1011666Stushar@ece.gatech.edu * redistributions in binary form must reproduce the above copyright 1111666Stushar@ece.gatech.edu * notice, this list of conditions and the following disclaimer in the 1211666Stushar@ece.gatech.edu * documentation and/or other materials provided with the distribution; 1311666Stushar@ece.gatech.edu * neither the name of the copyright holders nor the names of its 1411666Stushar@ece.gatech.edu * contributors may be used to endorse or promote products derived from 1511666Stushar@ece.gatech.edu * this software without specific prior written permission. 1611666Stushar@ece.gatech.edu * 1711666Stushar@ece.gatech.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1811666Stushar@ece.gatech.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1911666Stushar@ece.gatech.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2011666Stushar@ece.gatech.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2111666Stushar@ece.gatech.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2211666Stushar@ece.gatech.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2311666Stushar@ece.gatech.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2411666Stushar@ece.gatech.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2511666Stushar@ece.gatech.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2611666Stushar@ece.gatech.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2711666Stushar@ece.gatech.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2811666Stushar@ece.gatech.edu * 2911666Stushar@ece.gatech.edu * Authors: Niket Agarwal 3011666Stushar@ece.gatech.edu * Tushar Krishna 3111666Stushar@ece.gatech.edu */ 3211666Stushar@ece.gatech.edu 3311666Stushar@ece.gatech.edu 3411666Stushar@ece.gatech.edu#include "mem/ruby/network/garnet2.0/RoutingUnit.hh" 3511666Stushar@ece.gatech.edu 3611666Stushar@ece.gatech.edu#include "base/cast.hh" 3713449Sgabeblack@google.com#include "base/logging.hh" 3811666Stushar@ece.gatech.edu#include "mem/ruby/network/garnet2.0/InputUnit.hh" 3911666Stushar@ece.gatech.edu#include "mem/ruby/network/garnet2.0/Router.hh" 4011666Stushar@ece.gatech.edu#include "mem/ruby/slicc_interface/Message.hh" 4111666Stushar@ece.gatech.edu 4211666Stushar@ece.gatech.eduRoutingUnit::RoutingUnit(Router *router) 4311666Stushar@ece.gatech.edu{ 4411666Stushar@ece.gatech.edu m_router = router; 4511666Stushar@ece.gatech.edu m_routing_table.clear(); 4611666Stushar@ece.gatech.edu m_weight_table.clear(); 4711666Stushar@ece.gatech.edu} 4811666Stushar@ece.gatech.edu 4911666Stushar@ece.gatech.eduvoid 5011666Stushar@ece.gatech.eduRoutingUnit::addRoute(const NetDest& routing_table_entry) 5111666Stushar@ece.gatech.edu{ 5211666Stushar@ece.gatech.edu m_routing_table.push_back(routing_table_entry); 5311666Stushar@ece.gatech.edu} 5411666Stushar@ece.gatech.edu 5511666Stushar@ece.gatech.eduvoid 5611666Stushar@ece.gatech.eduRoutingUnit::addWeight(int link_weight) 5711666Stushar@ece.gatech.edu{ 5811666Stushar@ece.gatech.edu m_weight_table.push_back(link_weight); 5911666Stushar@ece.gatech.edu} 6011666Stushar@ece.gatech.edu 6111666Stushar@ece.gatech.edu/* 6211666Stushar@ece.gatech.edu * This is the default routing algorithm in garnet. 6311666Stushar@ece.gatech.edu * The routing table is populated during topology creation. 6411666Stushar@ece.gatech.edu * Routes can be biased via weight assignments in the topology file. 6511666Stushar@ece.gatech.edu * Correct weight assignments are critical to provide deadlock avoidance. 6611666Stushar@ece.gatech.edu */ 6711666Stushar@ece.gatech.edu 6811666Stushar@ece.gatech.eduint 6911666Stushar@ece.gatech.eduRoutingUnit::lookupRoutingTable(int vnet, NetDest msg_destination) 7011666Stushar@ece.gatech.edu{ 7111666Stushar@ece.gatech.edu // First find all possible output link candidates 7211666Stushar@ece.gatech.edu // For ordered vnet, just choose the first 7311666Stushar@ece.gatech.edu // (to make sure different packets don't choose different routes) 7411666Stushar@ece.gatech.edu // For unordered vnet, randomly choose any of the links 7511666Stushar@ece.gatech.edu // To have a strict ordering between links, they should be given 7611666Stushar@ece.gatech.edu // different weights in the topology file 7711666Stushar@ece.gatech.edu 7811666Stushar@ece.gatech.edu int output_link = -1; 7911666Stushar@ece.gatech.edu int min_weight = INFINITE_; 8011666Stushar@ece.gatech.edu std::vector<int> output_link_candidates; 8111666Stushar@ece.gatech.edu int num_candidates = 0; 8211666Stushar@ece.gatech.edu 8311666Stushar@ece.gatech.edu // Identify the minimum weight among the candidate output links 8411666Stushar@ece.gatech.edu for (int link = 0; link < m_routing_table.size(); link++) { 8511666Stushar@ece.gatech.edu if (msg_destination.intersectionIsNotEmpty(m_routing_table[link])) { 8611666Stushar@ece.gatech.edu 8711666Stushar@ece.gatech.edu if (m_weight_table[link] <= min_weight) 8811666Stushar@ece.gatech.edu min_weight = m_weight_table[link]; 8911666Stushar@ece.gatech.edu } 9011666Stushar@ece.gatech.edu } 9111666Stushar@ece.gatech.edu 9211666Stushar@ece.gatech.edu // Collect all candidate output links with this minimum weight 9311666Stushar@ece.gatech.edu for (int link = 0; link < m_routing_table.size(); link++) { 9411666Stushar@ece.gatech.edu if (msg_destination.intersectionIsNotEmpty(m_routing_table[link])) { 9511666Stushar@ece.gatech.edu 9611666Stushar@ece.gatech.edu if (m_weight_table[link] == min_weight) { 9711666Stushar@ece.gatech.edu 9811666Stushar@ece.gatech.edu num_candidates++; 9911666Stushar@ece.gatech.edu output_link_candidates.push_back(link); 10011666Stushar@ece.gatech.edu } 10111666Stushar@ece.gatech.edu } 10211666Stushar@ece.gatech.edu } 10311666Stushar@ece.gatech.edu 10411666Stushar@ece.gatech.edu if (output_link_candidates.size() == 0) { 10511666Stushar@ece.gatech.edu fatal("Fatal Error:: No Route exists from this Router."); 10611666Stushar@ece.gatech.edu exit(0); 10711666Stushar@ece.gatech.edu } 10811666Stushar@ece.gatech.edu 10911666Stushar@ece.gatech.edu // Randomly select any candidate output link 11011666Stushar@ece.gatech.edu int candidate = 0; 11111666Stushar@ece.gatech.edu if (!(m_router->get_net_ptr())->isVNetOrdered(vnet)) 11211666Stushar@ece.gatech.edu candidate = rand() % num_candidates; 11311666Stushar@ece.gatech.edu 11411666Stushar@ece.gatech.edu output_link = output_link_candidates.at(candidate); 11511666Stushar@ece.gatech.edu return output_link; 11611666Stushar@ece.gatech.edu} 11711666Stushar@ece.gatech.edu 11811666Stushar@ece.gatech.edu 11911666Stushar@ece.gatech.eduvoid 12011666Stushar@ece.gatech.eduRoutingUnit::addInDirection(PortDirection inport_dirn, int inport_idx) 12111666Stushar@ece.gatech.edu{ 12211666Stushar@ece.gatech.edu m_inports_dirn2idx[inport_dirn] = inport_idx; 12311666Stushar@ece.gatech.edu m_inports_idx2dirn[inport_idx] = inport_dirn; 12411666Stushar@ece.gatech.edu} 12511666Stushar@ece.gatech.edu 12611666Stushar@ece.gatech.eduvoid 12711666Stushar@ece.gatech.eduRoutingUnit::addOutDirection(PortDirection outport_dirn, int outport_idx) 12811666Stushar@ece.gatech.edu{ 12911666Stushar@ece.gatech.edu m_outports_dirn2idx[outport_dirn] = outport_idx; 13011666Stushar@ece.gatech.edu m_outports_idx2dirn[outport_idx] = outport_dirn; 13111666Stushar@ece.gatech.edu} 13211666Stushar@ece.gatech.edu 13311666Stushar@ece.gatech.edu// outportCompute() is called by the InputUnit 13411666Stushar@ece.gatech.edu// It calls the routing table by default. 13511666Stushar@ece.gatech.edu// A template for adaptive topology-specific routing algorithm 13611666Stushar@ece.gatech.edu// implementations using port directions rather than a static routing 13711666Stushar@ece.gatech.edu// table is provided here. 13811666Stushar@ece.gatech.edu 13911666Stushar@ece.gatech.eduint 14011666Stushar@ece.gatech.eduRoutingUnit::outportCompute(RouteInfo route, int inport, 14111666Stushar@ece.gatech.edu PortDirection inport_dirn) 14211666Stushar@ece.gatech.edu{ 14311666Stushar@ece.gatech.edu int outport = -1; 14411666Stushar@ece.gatech.edu 14511666Stushar@ece.gatech.edu if (route.dest_router == m_router->get_id()) { 14611666Stushar@ece.gatech.edu 14711666Stushar@ece.gatech.edu // Multiple NIs may be connected to this router, 14811666Stushar@ece.gatech.edu // all with output port direction = "Local" 14911666Stushar@ece.gatech.edu // Get exact outport id from table 15011666Stushar@ece.gatech.edu outport = lookupRoutingTable(route.vnet, route.net_dest); 15111666Stushar@ece.gatech.edu return outport; 15211666Stushar@ece.gatech.edu } 15311666Stushar@ece.gatech.edu 15411666Stushar@ece.gatech.edu // Routing Algorithm set in GarnetNetwork.py 15511666Stushar@ece.gatech.edu // Can be over-ridden from command line using --routing-algorithm = 1 15611666Stushar@ece.gatech.edu RoutingAlgorithm routing_algorithm = 15711666Stushar@ece.gatech.edu (RoutingAlgorithm) m_router->get_net_ptr()->getRoutingAlgorithm(); 15811666Stushar@ece.gatech.edu 15911666Stushar@ece.gatech.edu switch (routing_algorithm) { 16011666Stushar@ece.gatech.edu case TABLE_: outport = 16111666Stushar@ece.gatech.edu lookupRoutingTable(route.vnet, route.net_dest); break; 16211666Stushar@ece.gatech.edu case XY_: outport = 16311666Stushar@ece.gatech.edu outportComputeXY(route, inport, inport_dirn); break; 16411666Stushar@ece.gatech.edu // any custom algorithm 16511666Stushar@ece.gatech.edu case CUSTOM_: outport = 16611666Stushar@ece.gatech.edu outportComputeCustom(route, inport, inport_dirn); break; 16711666Stushar@ece.gatech.edu default: outport = 16811666Stushar@ece.gatech.edu lookupRoutingTable(route.vnet, route.net_dest); break; 16911666Stushar@ece.gatech.edu } 17011666Stushar@ece.gatech.edu 17111666Stushar@ece.gatech.edu assert(outport != -1); 17211666Stushar@ece.gatech.edu return outport; 17311666Stushar@ece.gatech.edu} 17411666Stushar@ece.gatech.edu 17511666Stushar@ece.gatech.edu// XY routing implemented using port directions 17611666Stushar@ece.gatech.edu// Only for reference purpose in a Mesh 17711666Stushar@ece.gatech.edu// By default Garnet uses the routing table 17811666Stushar@ece.gatech.eduint 17911666Stushar@ece.gatech.eduRoutingUnit::outportComputeXY(RouteInfo route, 18011666Stushar@ece.gatech.edu int inport, 18111666Stushar@ece.gatech.edu PortDirection inport_dirn) 18211666Stushar@ece.gatech.edu{ 18311666Stushar@ece.gatech.edu PortDirection outport_dirn = "Unknown"; 18411666Stushar@ece.gatech.edu 18511667Stushar@ece.gatech.edu int M5_VAR_USED num_rows = m_router->get_net_ptr()->getNumRows(); 18611666Stushar@ece.gatech.edu int num_cols = m_router->get_net_ptr()->getNumCols(); 18711666Stushar@ece.gatech.edu assert(num_rows > 0 && num_cols > 0); 18811666Stushar@ece.gatech.edu 18911666Stushar@ece.gatech.edu int my_id = m_router->get_id(); 19011666Stushar@ece.gatech.edu int my_x = my_id % num_cols; 19111666Stushar@ece.gatech.edu int my_y = my_id / num_cols; 19211666Stushar@ece.gatech.edu 19311666Stushar@ece.gatech.edu int dest_id = route.dest_router; 19411666Stushar@ece.gatech.edu int dest_x = dest_id % num_cols; 19511666Stushar@ece.gatech.edu int dest_y = dest_id / num_cols; 19611666Stushar@ece.gatech.edu 19711666Stushar@ece.gatech.edu int x_hops = abs(dest_x - my_x); 19811666Stushar@ece.gatech.edu int y_hops = abs(dest_y - my_y); 19911666Stushar@ece.gatech.edu 20011666Stushar@ece.gatech.edu bool x_dirn = (dest_x >= my_x); 20111666Stushar@ece.gatech.edu bool y_dirn = (dest_y >= my_y); 20211666Stushar@ece.gatech.edu 20311666Stushar@ece.gatech.edu // already checked that in outportCompute() function 20411666Stushar@ece.gatech.edu assert(!(x_hops == 0 && y_hops == 0)); 20511666Stushar@ece.gatech.edu 20611666Stushar@ece.gatech.edu if (x_hops > 0) { 20711666Stushar@ece.gatech.edu if (x_dirn) { 20811666Stushar@ece.gatech.edu assert(inport_dirn == "Local" || inport_dirn == "West"); 20911666Stushar@ece.gatech.edu outport_dirn = "East"; 21011666Stushar@ece.gatech.edu } else { 21111666Stushar@ece.gatech.edu assert(inport_dirn == "Local" || inport_dirn == "East"); 21211666Stushar@ece.gatech.edu outport_dirn = "West"; 21311666Stushar@ece.gatech.edu } 21411666Stushar@ece.gatech.edu } else if (y_hops > 0) { 21511666Stushar@ece.gatech.edu if (y_dirn) { 21611666Stushar@ece.gatech.edu // "Local" or "South" or "West" or "East" 21711666Stushar@ece.gatech.edu assert(inport_dirn != "North"); 21811666Stushar@ece.gatech.edu outport_dirn = "North"; 21911666Stushar@ece.gatech.edu } else { 22011666Stushar@ece.gatech.edu // "Local" or "North" or "West" or "East" 22111666Stushar@ece.gatech.edu assert(inport_dirn != "South"); 22211666Stushar@ece.gatech.edu outport_dirn = "South"; 22311666Stushar@ece.gatech.edu } 22411666Stushar@ece.gatech.edu } else { 22511666Stushar@ece.gatech.edu // x_hops == 0 and y_hops == 0 22611666Stushar@ece.gatech.edu // this is not possible 22711666Stushar@ece.gatech.edu // already checked that in outportCompute() function 22813449Sgabeblack@google.com panic("x_hops == y_hops == 0"); 22911666Stushar@ece.gatech.edu } 23011666Stushar@ece.gatech.edu 23111666Stushar@ece.gatech.edu return m_outports_dirn2idx[outport_dirn]; 23211666Stushar@ece.gatech.edu} 23311666Stushar@ece.gatech.edu 23411666Stushar@ece.gatech.edu// Template for implementing custom routing algorithm 23511666Stushar@ece.gatech.edu// using port directions. (Example adaptive) 23611666Stushar@ece.gatech.eduint 23711666Stushar@ece.gatech.eduRoutingUnit::outportComputeCustom(RouteInfo route, 23811666Stushar@ece.gatech.edu int inport, 23911666Stushar@ece.gatech.edu PortDirection inport_dirn) 24011666Stushar@ece.gatech.edu{ 24113449Sgabeblack@google.com panic("%s placeholder executed", __FUNCTION__); 24211666Stushar@ece.gatech.edu} 243