RoutingUnit.cc revision 11666
16657Snate@binkert.org/* 26657Snate@binkert.org * Copyright (c) 2008 Princeton University 36657Snate@binkert.org * Copyright (c) 2016 Georgia Institute of Technology 46657Snate@binkert.org * All rights reserved. 56657Snate@binkert.org * 66657Snate@binkert.org * Redistribution and use in source and binary forms, with or without 76657Snate@binkert.org * modification, are permitted provided that the following conditions are 86657Snate@binkert.org * met: redistributions of source code must retain the above copyright 96657Snate@binkert.org * notice, this list of conditions and the following disclaimer; 106657Snate@binkert.org * redistributions in binary form must reproduce the above copyright 116657Snate@binkert.org * notice, this list of conditions and the following disclaimer in the 126657Snate@binkert.org * documentation and/or other materials provided with the distribution; 136657Snate@binkert.org * neither the name of the copyright holders nor the names of its 146657Snate@binkert.org * contributors may be used to endorse or promote products derived from 156657Snate@binkert.org * this software without specific prior written permission. 166657Snate@binkert.org * 176657Snate@binkert.org * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 186657Snate@binkert.org * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 196657Snate@binkert.org * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 206657Snate@binkert.org * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 216657Snate@binkert.org * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 226657Snate@binkert.org * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 236657Snate@binkert.org * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 246657Snate@binkert.org * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 256657Snate@binkert.org * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 266657Snate@binkert.org * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 276657Snate@binkert.org * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 286999Snate@binkert.org * 296657Snate@binkert.org * Authors: Niket Agarwal 306657Snate@binkert.org * Tushar Krishna 316657Snate@binkert.org */ 326657Snate@binkert.org 338189SLisa.Hsu@amd.com 346657Snate@binkert.org#include "mem/ruby/network/garnet2.0/RoutingUnit.hh" 356882SBrad.Beckmann@amd.com 367055Snate@binkert.org#include "base/cast.hh" 376882SBrad.Beckmann@amd.com#include "mem/ruby/network/garnet2.0/InputUnit.hh" 386882SBrad.Beckmann@amd.com#include "mem/ruby/network/garnet2.0/Router.hh" 398191SLisa.Hsu@amd.com#include "mem/ruby/slicc_interface/Message.hh" 406882SBrad.Beckmann@amd.com 416882SBrad.Beckmann@amd.comRoutingUnit::RoutingUnit(Router *router) 429102SNuwan.Jayasena@amd.com{ 436888SBrad.Beckmann@amd.com m_router = router; 446882SBrad.Beckmann@amd.com m_routing_table.clear(); 456882SBrad.Beckmann@amd.com m_weight_table.clear(); 466657Snate@binkert.org} 476657Snate@binkert.org 486657Snate@binkert.orgvoid 496657Snate@binkert.orgRoutingUnit::addRoute(const NetDest& routing_table_entry) 506657Snate@binkert.org{ 517839Snilay@cs.wisc.edu m_routing_table.push_back(routing_table_entry); 526657Snate@binkert.org} 536882SBrad.Beckmann@amd.com 546882SBrad.Beckmann@amd.comvoid 556882SBrad.Beckmann@amd.comRoutingUnit::addWeight(int link_weight) 566882SBrad.Beckmann@amd.com{ 576882SBrad.Beckmann@amd.com m_weight_table.push_back(link_weight); 586882SBrad.Beckmann@amd.com} 596657Snate@binkert.org 606657Snate@binkert.org/* 616657Snate@binkert.org * This is the default routing algorithm in garnet. 626657Snate@binkert.org * The routing table is populated during topology creation. 636657Snate@binkert.org * Routes can be biased via weight assignments in the topology file. 646657Snate@binkert.org * Correct weight assignments are critical to provide deadlock avoidance. 656657Snate@binkert.org */ 666657Snate@binkert.org 676657Snate@binkert.orgint 687839Snilay@cs.wisc.eduRoutingUnit::lookupRoutingTable(int vnet, NetDest msg_destination) 697839Snilay@cs.wisc.edu{ 706657Snate@binkert.org // First find all possible output link candidates 716657Snate@binkert.org // For ordered vnet, just choose the first 726657Snate@binkert.org // (to make sure different packets don't choose different routes) 736657Snate@binkert.org // For unordered vnet, randomly choose any of the links 746657Snate@binkert.org // To have a strict ordering between links, they should be given 756657Snate@binkert.org // different weights in the topology file 766657Snate@binkert.org 776657Snate@binkert.org int output_link = -1; 786657Snate@binkert.org int min_weight = INFINITE_; 796657Snate@binkert.org std::vector<int> output_link_candidates; 806657Snate@binkert.org int num_candidates = 0; 816657Snate@binkert.org 826657Snate@binkert.org // Identify the minimum weight among the candidate output links 836657Snate@binkert.org for (int link = 0; link < m_routing_table.size(); link++) { 846657Snate@binkert.org if (msg_destination.intersectionIsNotEmpty(m_routing_table[link])) { 856657Snate@binkert.org 866657Snate@binkert.org if (m_weight_table[link] <= min_weight) 876657Snate@binkert.org min_weight = m_weight_table[link]; 886657Snate@binkert.org } 896657Snate@binkert.org } 906779SBrad.Beckmann@amd.com 916657Snate@binkert.org // Collect all candidate output links with this minimum weight 926657Snate@binkert.org for (int link = 0; link < m_routing_table.size(); link++) { 936657Snate@binkert.org if (msg_destination.intersectionIsNotEmpty(m_routing_table[link])) { 946657Snate@binkert.org 956657Snate@binkert.org if (m_weight_table[link] == min_weight) { 966657Snate@binkert.org 976657Snate@binkert.org num_candidates++; 986657Snate@binkert.org output_link_candidates.push_back(link); 996657Snate@binkert.org } 1006657Snate@binkert.org } 1016657Snate@binkert.org } 1026657Snate@binkert.org 1036657Snate@binkert.org if (output_link_candidates.size() == 0) { 1046657Snate@binkert.org fatal("Fatal Error:: No Route exists from this Router."); 1056657Snate@binkert.org exit(0); 1066657Snate@binkert.org } 1076657Snate@binkert.org 1086657Snate@binkert.org // Randomly select any candidate output link 1096657Snate@binkert.org int candidate = 0; 1106657Snate@binkert.org if (!(m_router->get_net_ptr())->isVNetOrdered(vnet)) 1116657Snate@binkert.org candidate = rand() % num_candidates; 1126657Snate@binkert.org 1136657Snate@binkert.org output_link = output_link_candidates.at(candidate); 1146657Snate@binkert.org return output_link; 1157839Snilay@cs.wisc.edu} 1167839Snilay@cs.wisc.edu 1177839Snilay@cs.wisc.edu 1187839Snilay@cs.wisc.eduvoid 1197839Snilay@cs.wisc.eduRoutingUnit::addInDirection(PortDirection inport_dirn, int inport_idx) 1207839Snilay@cs.wisc.edu{ 1217839Snilay@cs.wisc.edu m_inports_dirn2idx[inport_dirn] = inport_idx; 1227839Snilay@cs.wisc.edu m_inports_idx2dirn[inport_idx] = inport_dirn; 1237839Snilay@cs.wisc.edu} 1247839Snilay@cs.wisc.edu 1257839Snilay@cs.wisc.eduvoid 1267839Snilay@cs.wisc.eduRoutingUnit::addOutDirection(PortDirection outport_dirn, int outport_idx) 1277839Snilay@cs.wisc.edu{ 1287839Snilay@cs.wisc.edu m_outports_dirn2idx[outport_dirn] = outport_idx; 1297839Snilay@cs.wisc.edu m_outports_idx2dirn[outport_idx] = outport_dirn; 1306657Snate@binkert.org} 1316657Snate@binkert.org 1326657Snate@binkert.org// outportCompute() is called by the InputUnit 1336657Snate@binkert.org// It calls the routing table by default. 1346657Snate@binkert.org// A template for adaptive topology-specific routing algorithm 1356657Snate@binkert.org// implementations using port directions rather than a static routing 1366657Snate@binkert.org// table is provided here. 1376657Snate@binkert.org 1386657Snate@binkert.orgint 1396657Snate@binkert.orgRoutingUnit::outportCompute(RouteInfo route, int inport, 1406657Snate@binkert.org PortDirection inport_dirn) 1416657Snate@binkert.org{ 1426657Snate@binkert.org int outport = -1; 1436657Snate@binkert.org 1446657Snate@binkert.org if (route.dest_router == m_router->get_id()) { 1456657Snate@binkert.org 1466657Snate@binkert.org // Multiple NIs may be connected to this router, 1476657Snate@binkert.org // all with output port direction = "Local" 1486657Snate@binkert.org // Get exact outport id from table 1496657Snate@binkert.org outport = lookupRoutingTable(route.vnet, route.net_dest); 1506657Snate@binkert.org return outport; 1516657Snate@binkert.org } 1526657Snate@binkert.org 1536657Snate@binkert.org // Routing Algorithm set in GarnetNetwork.py 1546657Snate@binkert.org // Can be over-ridden from command line using --routing-algorithm = 1 1556657Snate@binkert.org RoutingAlgorithm routing_algorithm = 1566657Snate@binkert.org (RoutingAlgorithm) m_router->get_net_ptr()->getRoutingAlgorithm(); 1576657Snate@binkert.org 1586657Snate@binkert.org switch (routing_algorithm) { 1596657Snate@binkert.org case TABLE_: outport = 1606657Snate@binkert.org lookupRoutingTable(route.vnet, route.net_dest); break; 1616877Ssteve.reinhardt@amd.com case XY_: outport = 1626657Snate@binkert.org outportComputeXY(route, inport, inport_dirn); break; 1636657Snate@binkert.org // any custom algorithm 1646657Snate@binkert.org case CUSTOM_: outport = 1656657Snate@binkert.org outportComputeCustom(route, inport, inport_dirn); break; 1666657Snate@binkert.org default: outport = 1676657Snate@binkert.org lookupRoutingTable(route.vnet, route.net_dest); break; 1687542SBrad.Beckmann@amd.com } 1697542SBrad.Beckmann@amd.com 1706657Snate@binkert.org assert(outport != -1); 1716877Ssteve.reinhardt@amd.com return outport; 1726999Snate@binkert.org} 1736877Ssteve.reinhardt@amd.com 1746877Ssteve.reinhardt@amd.com// XY routing implemented using port directions 1756877Ssteve.reinhardt@amd.com// Only for reference purpose in a Mesh 1766877Ssteve.reinhardt@amd.com// By default Garnet uses the routing table 1776877Ssteve.reinhardt@amd.comint 1786877Ssteve.reinhardt@amd.comRoutingUnit::outportComputeXY(RouteInfo route, 1796877Ssteve.reinhardt@amd.com int inport, 1806877Ssteve.reinhardt@amd.com PortDirection inport_dirn) 1816877Ssteve.reinhardt@amd.com{ 1826877Ssteve.reinhardt@amd.com PortDirection outport_dirn = "Unknown"; 1836877Ssteve.reinhardt@amd.com 1846877Ssteve.reinhardt@amd.com int num_rows = m_router->get_net_ptr()->getNumRows(); 1856877Ssteve.reinhardt@amd.com int num_cols = m_router->get_net_ptr()->getNumCols(); 1866877Ssteve.reinhardt@amd.com assert(num_rows > 0 && num_cols > 0); 1876877Ssteve.reinhardt@amd.com 1886877Ssteve.reinhardt@amd.com int my_id = m_router->get_id(); 1896882SBrad.Beckmann@amd.com int my_x = my_id % num_cols; 1906882SBrad.Beckmann@amd.com int my_y = my_id / num_cols; 1916882SBrad.Beckmann@amd.com 1926882SBrad.Beckmann@amd.com int dest_id = route.dest_router; 1936882SBrad.Beckmann@amd.com int dest_x = dest_id % num_cols; 1946882SBrad.Beckmann@amd.com int dest_y = dest_id / num_cols; 1956882SBrad.Beckmann@amd.com 1966877Ssteve.reinhardt@amd.com int x_hops = abs(dest_x - my_x); 1976877Ssteve.reinhardt@amd.com int y_hops = abs(dest_y - my_y); 1986877Ssteve.reinhardt@amd.com 1996877Ssteve.reinhardt@amd.com bool x_dirn = (dest_x >= my_x); 2006657Snate@binkert.org bool y_dirn = (dest_y >= my_y); 2016657Snate@binkert.org 2026999Snate@binkert.org // already checked that in outportCompute() function 2036657Snate@binkert.org assert(!(x_hops == 0 && y_hops == 0)); 2046657Snate@binkert.org 2056657Snate@binkert.org if (x_hops > 0) { 2066657Snate@binkert.org if (x_dirn) { 2076657Snate@binkert.org assert(inport_dirn == "Local" || inport_dirn == "West"); 2086657Snate@binkert.org outport_dirn = "East"; 2097007Snate@binkert.org } else { 2106657Snate@binkert.org assert(inport_dirn == "Local" || inport_dirn == "East"); 2116657Snate@binkert.org outport_dirn = "West"; 2126657Snate@binkert.org } 2136657Snate@binkert.org } else if (y_hops > 0) { 2146657Snate@binkert.org if (y_dirn) { 2157007Snate@binkert.org // "Local" or "South" or "West" or "East" 2167007Snate@binkert.org assert(inport_dirn != "North"); 2176657Snate@binkert.org outport_dirn = "North"; 2187002Snate@binkert.org } else { 2197002Snate@binkert.org // "Local" or "North" or "West" or "East" 2207002Snate@binkert.org assert(inport_dirn != "South"); 2217002Snate@binkert.org outport_dirn = "South"; 2228229Snate@binkert.org } 2238229Snate@binkert.org } else { 2246657Snate@binkert.org // x_hops == 0 and y_hops == 0 2256657Snate@binkert.org // this is not possible 2268229Snate@binkert.org // already checked that in outportCompute() function 2278229Snate@binkert.org assert(0); 2288229Snate@binkert.org } 2298229Snate@binkert.org 2306657Snate@binkert.org return m_outports_dirn2idx[outport_dirn]; 2316657Snate@binkert.org} 2326657Snate@binkert.org 2336657Snate@binkert.org// Template for implementing custom routing algorithm 2346793SBrad.Beckmann@amd.com// using port directions. (Example adaptive) 2356657Snate@binkert.orgint 2366657Snate@binkert.orgRoutingUnit::outportComputeCustom(RouteInfo route, 2376657Snate@binkert.org int inport, 2386657Snate@binkert.org PortDirection inport_dirn) 2396657Snate@binkert.org{ 2407002Snate@binkert.org assert(0); 2416657Snate@binkert.org} 2427007Snate@binkert.org