RoutingUnit.cc revision 11667
14403Srdreslin@umich.edu/* 21693Sstever@eecs.umich.edu * Copyright (c) 2008 Princeton University 31693Sstever@eecs.umich.edu * Copyright (c) 2016 Georgia Institute of Technology 41693Sstever@eecs.umich.edu * All rights reserved. 51693Sstever@eecs.umich.edu * 61693Sstever@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 71693Sstever@eecs.umich.edu * modification, are permitted provided that the following conditions are 81693Sstever@eecs.umich.edu * met: redistributions of source code must retain the above copyright 91693Sstever@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 101693Sstever@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 111693Sstever@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 121693Sstever@eecs.umich.edu * documentation and/or other materials provided with the distribution; 131693Sstever@eecs.umich.edu * neither the name of the copyright holders nor the names of its 141693Sstever@eecs.umich.edu * contributors may be used to endorse or promote products derived from 151693Sstever@eecs.umich.edu * this software without specific prior written permission. 161693Sstever@eecs.umich.edu * 171693Sstever@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 181693Sstever@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 191693Sstever@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 201693Sstever@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 211693Sstever@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 221693Sstever@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 231693Sstever@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 241693Sstever@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 251693Sstever@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 261693Sstever@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 271693Sstever@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 281693Sstever@eecs.umich.edu * 293358Srdreslin@umich.edu * Authors: Niket Agarwal 303358Srdreslin@umich.edu * Tushar Krishna 311516SN/A */ 326654Snate@binkert.org 336654Snate@binkert.org 346654Snate@binkert.org#include "mem/ruby/network/garnet2.0/RoutingUnit.hh" 356654Snate@binkert.org 363358Srdreslin@umich.edu#include "base/cast.hh" 373358Srdreslin@umich.edu#include "mem/ruby/network/garnet2.0/InputUnit.hh" 386654Snate@binkert.org#include "mem/ruby/network/garnet2.0/Router.hh" 396654Snate@binkert.org#include "mem/ruby/slicc_interface/Message.hh" 401516SN/A 413358Srdreslin@umich.eduRoutingUnit::RoutingUnit(Router *router) 423358Srdreslin@umich.edu{ 433358Srdreslin@umich.edu m_router = router; 443358Srdreslin@umich.edu m_routing_table.clear(); 453358Srdreslin@umich.edu m_weight_table.clear(); 463358Srdreslin@umich.edu} 473358Srdreslin@umich.edu 483358Srdreslin@umich.eduvoid 493358Srdreslin@umich.eduRoutingUnit::addRoute(const NetDest& routing_table_entry) 503358Srdreslin@umich.edu{ 513358Srdreslin@umich.edu m_routing_table.push_back(routing_table_entry); 523358Srdreslin@umich.edu} 533360Srdreslin@umich.edu 543358Srdreslin@umich.eduvoid 553360Srdreslin@umich.eduRoutingUnit::addWeight(int link_weight) 563360Srdreslin@umich.edu{ 573360Srdreslin@umich.edu m_weight_table.push_back(link_weight); 585255Ssaidi@eecs.umich.edu} 593360Srdreslin@umich.edu 603360Srdreslin@umich.edu/* 613360Srdreslin@umich.edu * This is the default routing algorithm in garnet. 625255Ssaidi@eecs.umich.edu * The routing table is populated during topology creation. 633358Srdreslin@umich.edu * Routes can be biased via weight assignments in the topology file. 644403Srdreslin@umich.edu * Correct weight assignments are critical to provide deadlock avoidance. 653360Srdreslin@umich.edu */ 663358Srdreslin@umich.edu 673358Srdreslin@umich.eduint 683358Srdreslin@umich.eduRoutingUnit::lookupRoutingTable(int vnet, NetDest msg_destination) 693358Srdreslin@umich.edu{ 703358Srdreslin@umich.edu // First find all possible output link candidates 713358Srdreslin@umich.edu // For ordered vnet, just choose the first 723358Srdreslin@umich.edu // (to make sure different packets don't choose different routes) 733358Srdreslin@umich.edu // For unordered vnet, randomly choose any of the links 743358Srdreslin@umich.edu // To have a strict ordering between links, they should be given 753360Srdreslin@umich.edu // different weights in the topology file 763360Srdreslin@umich.edu 773360Srdreslin@umich.edu int output_link = -1; 783360Srdreslin@umich.edu int min_weight = INFINITE_; 793358Srdreslin@umich.edu std::vector<int> output_link_candidates; 803358Srdreslin@umich.edu int num_candidates = 0; 813358Srdreslin@umich.edu 823358Srdreslin@umich.edu // Identify the minimum weight among the candidate output links 834403Srdreslin@umich.edu for (int link = 0; link < m_routing_table.size(); link++) { 844403Srdreslin@umich.edu if (msg_destination.intersectionIsNotEmpty(m_routing_table[link])) { 855256Ssaidi@eecs.umich.edu 865255Ssaidi@eecs.umich.edu if (m_weight_table[link] <= min_weight) 873358Srdreslin@umich.edu min_weight = m_weight_table[link]; 883358Srdreslin@umich.edu } 894403Srdreslin@umich.edu } 904403Srdreslin@umich.edu 915255Ssaidi@eecs.umich.edu // Collect all candidate output links with this minimum weight 923358Srdreslin@umich.edu for (int link = 0; link < m_routing_table.size(); link++) { 933358Srdreslin@umich.edu if (msg_destination.intersectionIsNotEmpty(m_routing_table[link])) { 944403Srdreslin@umich.edu 955255Ssaidi@eecs.umich.edu if (m_weight_table[link] == min_weight) { 964403Srdreslin@umich.edu 973358Srdreslin@umich.edu num_candidates++; 983358Srdreslin@umich.edu output_link_candidates.push_back(link); 994403Srdreslin@umich.edu } 1005255Ssaidi@eecs.umich.edu } 1014403Srdreslin@umich.edu } 1023358Srdreslin@umich.edu 1033358Srdreslin@umich.edu if (output_link_candidates.size() == 0) { 1044403Srdreslin@umich.edu fatal("Fatal Error:: No Route exists from this Router."); 1055255Ssaidi@eecs.umich.edu exit(0); 1064403Srdreslin@umich.edu } 1073358Srdreslin@umich.edu 1083358Srdreslin@umich.edu // Randomly select any candidate output link 1094403Srdreslin@umich.edu int candidate = 0; 1105255Ssaidi@eecs.umich.edu if (!(m_router->get_net_ptr())->isVNetOrdered(vnet)) 1114403Srdreslin@umich.edu candidate = rand() % num_candidates; 1124403Srdreslin@umich.edu 1133358Srdreslin@umich.edu output_link = output_link_candidates.at(candidate); 1143358Srdreslin@umich.edu return output_link; 1154403Srdreslin@umich.edu} 1165255Ssaidi@eecs.umich.edu 1174403Srdreslin@umich.edu 1184403Srdreslin@umich.eduvoid 1194403Srdreslin@umich.eduRoutingUnit::addInDirection(PortDirection inport_dirn, int inport_idx) 1203360Srdreslin@umich.edu{ 1214403Srdreslin@umich.edu m_inports_dirn2idx[inport_dirn] = inport_idx; 1223358Srdreslin@umich.edu m_inports_idx2dirn[inport_idx] = inport_dirn; 1233358Srdreslin@umich.edu} 1244403Srdreslin@umich.edu 1255255Ssaidi@eecs.umich.eduvoid 1264403Srdreslin@umich.eduRoutingUnit::addOutDirection(PortDirection outport_dirn, int outport_idx) 1273358Srdreslin@umich.edu{ 1283358Srdreslin@umich.edu m_outports_dirn2idx[outport_dirn] = outport_idx; 1294403Srdreslin@umich.edu m_outports_idx2dirn[outport_idx] = outport_dirn; 1305255Ssaidi@eecs.umich.edu} 1314403Srdreslin@umich.edu 1323358Srdreslin@umich.edu// outportCompute() is called by the InputUnit 1333358Srdreslin@umich.edu// It calls the routing table by default. 1344403Srdreslin@umich.edu// A template for adaptive topology-specific routing algorithm 1355256Ssaidi@eecs.umich.edu// implementations using port directions rather than a static routing 1365255Ssaidi@eecs.umich.edu// table is provided here. 1374403Srdreslin@umich.edu 1383358Srdreslin@umich.eduint 1393358Srdreslin@umich.eduRoutingUnit::outportCompute(RouteInfo route, int inport, 1404403Srdreslin@umich.edu PortDirection inport_dirn) 1415255Ssaidi@eecs.umich.edu{ 1424403Srdreslin@umich.edu int outport = -1; 1434403Srdreslin@umich.edu 1444403Srdreslin@umich.edu if (route.dest_router == m_router->get_id()) { 1453360Srdreslin@umich.edu 1464403Srdreslin@umich.edu // Multiple NIs may be connected to this router, 1473358Srdreslin@umich.edu // all with output port direction = "Local" 1483358Srdreslin@umich.edu // Get exact outport id from table 1494403Srdreslin@umich.edu outport = lookupRoutingTable(route.vnet, route.net_dest); 1505255Ssaidi@eecs.umich.edu return outport; 1514403Srdreslin@umich.edu } 1524403Srdreslin@umich.edu 1534403Srdreslin@umich.edu // Routing Algorithm set in GarnetNetwork.py 1543360Srdreslin@umich.edu // Can be over-ridden from command line using --routing-algorithm = 1 1554403Srdreslin@umich.edu RoutingAlgorithm routing_algorithm = 1563358Srdreslin@umich.edu (RoutingAlgorithm) m_router->get_net_ptr()->getRoutingAlgorithm(); 1573358Srdreslin@umich.edu 1583358Srdreslin@umich.edu switch (routing_algorithm) { 1593358Srdreslin@umich.edu case TABLE_: outport = 1603358Srdreslin@umich.edu lookupRoutingTable(route.vnet, route.net_dest); break; 1613358Srdreslin@umich.edu case XY_: outport = 1623358Srdreslin@umich.edu outportComputeXY(route, inport, inport_dirn); break; 1633358Srdreslin@umich.edu // any custom algorithm 1643358Srdreslin@umich.edu case CUSTOM_: outport = 1653358Srdreslin@umich.edu outportComputeCustom(route, inport, inport_dirn); break; 1663358Srdreslin@umich.edu default: outport = 1673358Srdreslin@umich.edu lookupRoutingTable(route.vnet, route.net_dest); break; 1683358Srdreslin@umich.edu } 1693358Srdreslin@umich.edu 1703358Srdreslin@umich.edu assert(outport != -1); 1713358Srdreslin@umich.edu return outport; 1723358Srdreslin@umich.edu} 1733358Srdreslin@umich.edu 1743358Srdreslin@umich.edu// XY routing implemented using port directions 1753358Srdreslin@umich.edu// Only for reference purpose in a Mesh 1763358Srdreslin@umich.edu// By default Garnet uses the routing table 1773358Srdreslin@umich.eduint 1783358Srdreslin@umich.eduRoutingUnit::outportComputeXY(RouteInfo route, 1793358Srdreslin@umich.edu int inport, 1803358Srdreslin@umich.edu PortDirection inport_dirn) 1813358Srdreslin@umich.edu{ 1823358Srdreslin@umich.edu PortDirection outport_dirn = "Unknown"; 1833358Srdreslin@umich.edu 1843358Srdreslin@umich.edu int M5_VAR_USED num_rows = m_router->get_net_ptr()->getNumRows(); 1853358Srdreslin@umich.edu int num_cols = m_router->get_net_ptr()->getNumCols(); 1863358Srdreslin@umich.edu assert(num_rows > 0 && num_cols > 0); 1873358Srdreslin@umich.edu 1883358Srdreslin@umich.edu int my_id = m_router->get_id(); 1893358Srdreslin@umich.edu int my_x = my_id % num_cols; 1901516SN/A int my_y = my_id / num_cols; 1913358Srdreslin@umich.edu 1923358Srdreslin@umich.edu int dest_id = route.dest_router; 1933358Srdreslin@umich.edu int dest_x = dest_id % num_cols; 1941516SN/A int dest_y = dest_id / num_cols; 1953358Srdreslin@umich.edu 1963358Srdreslin@umich.edu int x_hops = abs(dest_x - my_x); 1973358Srdreslin@umich.edu int y_hops = abs(dest_y - my_y); 1988931Sandreas.hansson@arm.com 19910720Sandreas.hansson@arm.com bool x_dirn = (dest_x >= my_x); 2009790Sakash.bagdia@arm.com bool y_dirn = (dest_y >= my_y); 2011516SN/A 20210720Sandreas.hansson@arm.com // already checked that in outportCompute() function 2033358Srdreslin@umich.edu assert(!(x_hops == 0 && y_hops == 0)); 2043358Srdreslin@umich.edu 2053358Srdreslin@umich.edu if (x_hops > 0) { 2063358Srdreslin@umich.edu if (x_dirn) { 2073358Srdreslin@umich.edu assert(inport_dirn == "Local" || inport_dirn == "West"); 2083358Srdreslin@umich.edu outport_dirn = "East"; 2098847Sandreas.hansson@arm.com } else { 2108847Sandreas.hansson@arm.com assert(inport_dirn == "Local" || inport_dirn == "East"); 2118847Sandreas.hansson@arm.com outport_dirn = "West"; 2128847Sandreas.hansson@arm.com } 2133358Srdreslin@umich.edu } else if (y_hops > 0) { 2143358Srdreslin@umich.edu if (y_dirn) { 2153358Srdreslin@umich.edu // "Local" or "South" or "West" or "East" 2163358Srdreslin@umich.edu assert(inport_dirn != "North"); 2173358Srdreslin@umich.edu outport_dirn = "North"; 2183358Srdreslin@umich.edu } else { 2193358Srdreslin@umich.edu // "Local" or "North" or "West" or "East" 2203358Srdreslin@umich.edu assert(inport_dirn != "South"); 2217876Sgblack@eecs.umich.edu outport_dirn = "South"; 2223358Srdreslin@umich.edu } 2233358Srdreslin@umich.edu } else { 2243358Srdreslin@umich.edu // x_hops == 0 and y_hops == 0 2253358Srdreslin@umich.edu // this is not possible 2263358Srdreslin@umich.edu // already checked that in outportCompute() function 2273358Srdreslin@umich.edu assert(0); 2288801Sgblack@eecs.umich.edu } 2293358Srdreslin@umich.edu 2303358Srdreslin@umich.edu return m_outports_dirn2idx[outport_dirn]; 2313358Srdreslin@umich.edu} 2323358Srdreslin@umich.edu 2333358Srdreslin@umich.edu// Template for implementing custom routing algorithm 2343358Srdreslin@umich.edu// using port directions. (Example adaptive) 2353358Srdreslin@umich.eduint 2363358Srdreslin@umich.eduRoutingUnit::outportComputeCustom(RouteInfo route, 2373358Srdreslin@umich.edu int inport, 2383358Srdreslin@umich.edu PortDirection inport_dirn) 2393358Srdreslin@umich.edu{ 2403358Srdreslin@umich.edu assert(0); 2413358Srdreslin@umich.edu return -1; 2423358Srdreslin@umich.edu} 2433358Srdreslin@umich.edu