Topology.cc revision 9109
17860SN/A/* 27860SN/A * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 37860SN/A * All rights reserved. 48825Snilay@cs.wisc.edu * 57935SN/A * Redistribution and use in source and binary forms, with or without 67935SN/A * modification, are permitted provided that the following conditions are 77935SN/A * met: redistributions of source code must retain the above copyright 87860SN/A * notice, this list of conditions and the following disclaimer; 97860SN/A * redistributions in binary form must reproduce the above copyright 107860SN/A * notice, this list of conditions and the following disclaimer in the 117860SN/A * documentation and/or other materials provided with the distribution; 128825Snilay@cs.wisc.edu * neither the name of the copyright holders nor the names of its 138825Snilay@cs.wisc.edu * contributors may be used to endorse or promote products derived from 148825Snilay@cs.wisc.edu * this software without specific prior written permission. 158825Snilay@cs.wisc.edu * 167860SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 178464SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 188721SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 198825Snilay@cs.wisc.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 208825Snilay@cs.wisc.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 217935SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 227935SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 237935SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 247935SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 257935SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 267935SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 277935SN/A */ 288893Ssaidi@eecs.umich.edu 297860SN/A#include <cassert> 307860SN/A 317860SN/A#include "debug/RubyNetwork.hh" 328825Snilay@cs.wisc.edu#include "mem/protocol/MachineType.hh" 337860SN/A#include "mem/protocol/TopologyType.hh" 347860SN/A#include "mem/ruby/common/NetDest.hh" 357860SN/A#include "mem/ruby/network/BasicLink.hh" 367860SN/A#include "mem/ruby/network/BasicRouter.hh" 378210SN/A#include "mem/ruby/network/Network.hh" 388210SN/A#include "mem/ruby/network/Topology.hh" 397860SN/A#include "mem/ruby/slicc_interface/AbstractController.hh" 407860SN/A 417860SN/Ausing namespace std; 427860SN/A 437860SN/Aconst int INFINITE_LATENCY = 10000; // Yes, this is a big hack 447860SN/A 457860SN/Aclass BasicRouter; 467860SN/A 477860SN/A// Note: In this file, we use the first 2*m_nodes SwitchIDs to 487860SN/A// represent the input and output endpoint links. These really are 497860SN/A// not 'switches', as they will not have a Switch object allocated for 507860SN/A// them. The first m_nodes SwitchIDs are the links into the network, 517860SN/A// the second m_nodes set of SwitchIDs represent the the output queues 527860SN/A// of the network. 537860SN/A 547860SN/A// Helper functions based on chapter 29 of Cormen et al. 557860SN/Avoid extend_shortest_path(Matrix& current_dist, Matrix& latencies, 567860SN/A Matrix& inter_switches); 577860SN/AMatrix shortest_path(const Matrix& weights, Matrix& latencies, 587860SN/A Matrix& inter_switches); 597860SN/Abool link_is_shortest_path_to_node(SwitchID src, SwitchID next, 607860SN/A SwitchID final, const Matrix& weights, const Matrix& dist); 618825Snilay@cs.wisc.eduNetDest shortest_path_to_node(SwitchID src, SwitchID next, 627860SN/A const Matrix& weights, const Matrix& dist); 637860SN/A 647860SN/ATopology::Topology(const Params *p) 657860SN/A : SimObject(p) 667860SN/A{ 677860SN/A m_print_config = p->print_config; 687860SN/A m_number_of_switches = p->routers.size(); 697860SN/A 707860SN/A // initialize component latencies record 717860SN/A m_component_latencies.resize(0); 727860SN/A m_component_inter_switches.resize(0); 737860SN/A 747860SN/A // Total nodes/controllers in network 757860SN/A // Must make sure this is called after the State Machine constructors 767860SN/A m_nodes = MachineType_base_number(MachineType_NUM); 777860SN/A assert(m_nodes > 1); 787860SN/A 798825Snilay@cs.wisc.edu if (m_nodes != params()->ext_links.size() && 807860SN/A m_nodes != params()->ext_links.size()) { 817860SN/A fatal("m_nodes (%d) != ext_links vector length (%d)\n", 827860SN/A m_nodes, params()->ext_links.size()); 837860SN/A } 847860SN/A 857860SN/A // analyze both the internal and external links, create data structures 867860SN/A // Note that the python created links are bi-directional, but that the 877860SN/A // topology and networks utilize uni-directional links. Thus each 887860SN/A // BasicLink is converted to two calls to add link, on for each direction 897860SN/A for (vector<BasicExtLink*>::const_iterator i = params()->ext_links.begin(); 907860SN/A i != params()->ext_links.end(); ++i) { 918825Snilay@cs.wisc.edu BasicExtLink *ext_link = (*i); 927860SN/A AbstractController *abs_cntrl = ext_link->params()->ext_node; 937860SN/A BasicRouter *router = ext_link->params()->int_node; 947860SN/A 957860SN/A // Store the controller and ExtLink pointers for later 967860SN/A m_controller_vector.push_back(abs_cntrl); 977860SN/A m_ext_link_vector.push_back(ext_link); 987860SN/A 997860SN/A int ext_idx1 = abs_cntrl->params()->cntrl_id; 1008825Snilay@cs.wisc.edu int ext_idx2 = ext_idx1 + m_nodes; 1017860SN/A int int_idx = router->params()->router_id + 2*m_nodes; 1027860SN/A 1037860SN/A // create the internal uni-directional links in both directions 1047860SN/A // the first direction is marked: In 1057860SN/A addLink(ext_idx1, int_idx, ext_link, LinkDirection_In); 1067860SN/A // the first direction is marked: Out 1077860SN/A addLink(int_idx, ext_idx2, ext_link, LinkDirection_Out); 1087860SN/A } 1097860SN/A 1107860SN/A for (vector<BasicIntLink*>::const_iterator i = params()->int_links.begin(); 1117860SN/A i != params()->int_links.end(); ++i) { 1127860SN/A BasicIntLink *int_link = (*i); 1137860SN/A BasicRouter *router_a = int_link->params()->node_a; 1147860SN/A BasicRouter *router_b = int_link->params()->node_b; 1157860SN/A 1167860SN/A // Store the IntLink pointers for later 1178521SN/A m_int_link_vector.push_back(int_link); 1187860SN/A 1197860SN/A int a = router_a->params()->router_id + 2*m_nodes; 1207860SN/A int b = router_b->params()->router_id + 2*m_nodes; 1217860SN/A 1227860SN/A // create the internal uni-directional links in both directions 1237860SN/A // the first direction is marked: In 1247860SN/A addLink(a, b, int_link, LinkDirection_In); 1257860SN/A // the second direction is marked: Out 1267860SN/A addLink(b, a, int_link, LinkDirection_Out); 1277860SN/A } 1287860SN/A} 1298893Ssaidi@eecs.umich.edu 1307860SN/Avoid 1317860SN/ATopology::init() 1327860SN/A{ 1337860SN/A} 1348150SN/A 1357860SN/A 1367860SN/Avoid 1377860SN/ATopology::initNetworkPtr(Network* net_ptr) 1387860SN/A{ 1398835SAli.Saidi@ARM.com for (vector<BasicExtLink*>::const_iterator i = params()->ext_links.begin(); 1407860SN/A i != params()->ext_links.end(); ++i) { 1417860SN/A BasicExtLink *ext_link = (*i); 1427860SN/A AbstractController *abs_cntrl = ext_link->params()->ext_node; 1437860SN/A abs_cntrl->initNetworkPtr(net_ptr); 1448835SAli.Saidi@ARM.com } 1457860SN/A} 1467860SN/A 1477860SN/Avoid 1487860SN/ATopology::createLinks(Network *net, bool isReconfiguration) 1497860SN/A{ 1508893Ssaidi@eecs.umich.edu // Find maximum switchID 1517860SN/A SwitchID max_switch_id = 0; 1527860SN/A for (LinkMap::const_iterator i = m_link_map.begin(); 1537860SN/A i != m_link_map.end(); ++i) { 1548825Snilay@cs.wisc.edu std::pair<int, int> src_dest = (*i).first; 1557860SN/A max_switch_id = max(max_switch_id, src_dest.first); 1568825Snilay@cs.wisc.edu max_switch_id = max(max_switch_id, src_dest.second); 1578825Snilay@cs.wisc.edu } 1588825Snilay@cs.wisc.edu 1598825Snilay@cs.wisc.edu // Initialize weight, latency, and inter switched vectors 1608825Snilay@cs.wisc.edu Matrix topology_weights; 1618825Snilay@cs.wisc.edu int num_switches = max_switch_id+1; 1628825Snilay@cs.wisc.edu topology_weights.resize(num_switches); 1638893Ssaidi@eecs.umich.edu m_component_latencies.resize(num_switches); 1647860SN/A m_component_inter_switches.resize(num_switches); 1657860SN/A 1667860SN/A for (int i = 0; i < topology_weights.size(); i++) { 1677860SN/A topology_weights[i].resize(num_switches); 1687860SN/A m_component_latencies[i].resize(num_switches); 1697860SN/A m_component_inter_switches[i].resize(num_switches); 1707860SN/A 1717860SN/A for (int j = 0; j < topology_weights[i].size(); j++) { 1727860SN/A topology_weights[i][j] = INFINITE_LATENCY; 1737860SN/A 1747860SN/A // initialize to invalid values 1757860SN/A m_component_latencies[i][j] = -1; 1767860SN/A 1777860SN/A // initially assume direct connections / no intermediate 1787860SN/A // switches between components 1797860SN/A m_component_inter_switches[i][j] = 0; 1807860SN/A } 1817860SN/A } 1827860SN/A 1837860SN/A // Set identity weights to zero 1847860SN/A for (int i = 0; i < topology_weights.size(); i++) { 1857860SN/A topology_weights[i][i] = 0; 1867860SN/A } 1877860SN/A 1887860SN/A // Fill in the topology weights and bandwidth multipliers 1897860SN/A for (LinkMap::const_iterator i = m_link_map.begin(); 1907860SN/A i != m_link_map.end(); ++i) { 1917860SN/A std::pair<int, int> src_dest = (*i).first; 1927860SN/A BasicLink* link = (*i).second.link; 1937860SN/A int src = src_dest.first; 1947860SN/A int dst = src_dest.second; 1957860SN/A m_component_latencies[src][dst] = link->m_latency; 1967860SN/A topology_weights[src][dst] = link->m_weight; 1977860SN/A } 1987860SN/A 1997860SN/A // Walk topology and hookup the links 2007860SN/A Matrix dist = shortest_path(topology_weights, m_component_latencies, 2017860SN/A m_component_inter_switches); 2027860SN/A for (int i = 0; i < topology_weights.size(); i++) { 2037860SN/A for (int j = 0; j < topology_weights[i].size(); j++) { 2047860SN/A int weight = topology_weights[i][j]; 2057860SN/A if (weight > 0 && weight != INFINITE_LATENCY) { 2067860SN/A NetDest destination_set = shortest_path_to_node(i, j, 2077860SN/A topology_weights, dist); 2087860SN/A makeLink(net, i, j, destination_set, isReconfiguration); 2097860SN/A } 2107860SN/A } 2117860SN/A } 2127860SN/A} 2137860SN/A 2147860SN/Avoid 2157860SN/ATopology::addLink(SwitchID src, SwitchID dest, BasicLink* link, 2167860SN/A LinkDirection dir) 2177860SN/A{ 2187860SN/A assert(src <= m_number_of_switches+m_nodes+m_nodes); 2197860SN/A assert(dest <= m_number_of_switches+m_nodes+m_nodes); 2207860SN/A 2217860SN/A std::pair<int, int> src_dest_pair; 2227860SN/A LinkEntry link_entry; 2237860SN/A 2247860SN/A src_dest_pair.first = src; 2257860SN/A src_dest_pair.second = dest; 2267860SN/A link_entry.direction = dir; 2277860SN/A link_entry.link = link; 2287860SN/A m_link_map[src_dest_pair] = link_entry; 2297860SN/A} 2307860SN/A 2317860SN/Avoid 2327860SN/ATopology::makeLink(Network *net, SwitchID src, SwitchID dest, 2337860SN/A const NetDest& routing_table_entry, bool isReconfiguration) 2347860SN/A{ 2357860SN/A // Make sure we're not trying to connect two end-point nodes 2367860SN/A // directly together 2377860SN/A assert(src >= 2 * m_nodes || dest >= 2 * m_nodes); 2387860SN/A 2397860SN/A std::pair<int, int> src_dest; 2407860SN/A LinkEntry link_entry; 2417860SN/A 2427860SN/A if (src < m_nodes) { 2437860SN/A src_dest.first = src; 2447860SN/A src_dest.second = dest; 2457860SN/A link_entry = m_link_map[src_dest]; 2467860SN/A net->makeInLink(src, dest - (2 * m_nodes), link_entry.link, 2477860SN/A link_entry.direction, 2487860SN/A routing_table_entry, 2497860SN/A isReconfiguration); 2507860SN/A } else if (dest < 2*m_nodes) { 2517860SN/A assert(dest >= m_nodes); 2527860SN/A NodeID node = dest - m_nodes; 2537860SN/A src_dest.first = src; 2547860SN/A src_dest.second = dest; 2557860SN/A link_entry = m_link_map[src_dest]; 2567860SN/A net->makeOutLink(src - (2 * m_nodes), node, link_entry.link, 2577860SN/A link_entry.direction, 2587860SN/A routing_table_entry, 2597860SN/A isReconfiguration); 2607860SN/A } else { 2617860SN/A assert((src >= 2 * m_nodes) && (dest >= 2 * m_nodes)); 2627860SN/A src_dest.first = src; 2637860SN/A src_dest.second = dest; 2647860SN/A link_entry = m_link_map[src_dest]; 2657860SN/A net->makeInternalLink(src - (2 * m_nodes), dest - (2 * m_nodes), 2667860SN/A link_entry.link, link_entry.direction, 2677860SN/A routing_table_entry, isReconfiguration); 2687860SN/A } 2697860SN/A} 2707860SN/A 2717860SN/Avoid 2727860SN/ATopology::printStats(std::ostream& out) const 2737860SN/A{ 2747860SN/A for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 2757860SN/A m_controller_vector[cntrl]->printStats(out); 2767860SN/A } 2777860SN/A} 2787860SN/A 2797860SN/Avoid 2807860SN/ATopology::clearStats() 2817860SN/A{ 2827860SN/A for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 2837860SN/A m_controller_vector[cntrl]->clearStats(); 2847860SN/A } 2857860SN/A} 2867860SN/A 2877860SN/Avoid 2887860SN/ATopology::printConfig(std::ostream& out) const 2897860SN/A{ 2907860SN/A if (m_print_config == false) 2917860SN/A return; 2927860SN/A 2937860SN/A assert(m_component_latencies.size() > 0); 2947860SN/A 2957860SN/A out << "--- Begin Topology Print ---" << endl 2967860SN/A << endl 2977860SN/A << "Topology print ONLY indicates the _NETWORK_ latency between two " 2987860SN/A << "machines" << endl 2997860SN/A << "It does NOT include the latency within the machines" << endl 3007860SN/A << endl; 3017860SN/A 3027860SN/A for (int m = 0; m < MachineType_NUM; m++) { 3037860SN/A int i_end = MachineType_base_count((MachineType)m); 3047860SN/A for (int i = 0; i < i_end; i++) { 3057860SN/A MachineID cur_mach = {(MachineType)m, i}; 3067860SN/A out << cur_mach << " Network Latencies" << endl; 3077860SN/A for (int n = 0; n < MachineType_NUM; n++) { 3087860SN/A int j_end = MachineType_base_count((MachineType)n); 3097860SN/A for (int j = 0; j < j_end; j++) { 3107860SN/A MachineID dest_mach = {(MachineType)n, j}; 3117860SN/A if (cur_mach == dest_mach) 3127860SN/A continue; 3137860SN/A 3147860SN/A int src = MachineType_base_number((MachineType)m) + i; 3157860SN/A int dst = MachineType_base_number(MachineType_NUM) + 3167860SN/A MachineType_base_number((MachineType)n) + j; 3177860SN/A int link_latency = m_component_latencies[src][dst]; 3187860SN/A int intermediate_switches = 3197860SN/A m_component_inter_switches[src][dst]; 3207860SN/A 3217860SN/A // NOTE switches are assumed to have single 3227860SN/A // cycle latency 3237860SN/A out << " " << cur_mach << " -> " << dest_mach 3247860SN/A << " net_lat: " 3257860SN/A << link_latency + intermediate_switches << endl; 3267860SN/A } 3277860SN/A } 3287860SN/A out << endl; 3297860SN/A } 3307860SN/A } 3317860SN/A 3327860SN/A out << "--- End Topology Print ---" << endl; 3337860SN/A} 3347860SN/A 3357860SN/A// The following all-pairs shortest path algorithm is based on the 3367860SN/A// discussion from Cormen et al., Chapter 26.1. 3377860SN/Avoid 3387860SN/Aextend_shortest_path(Matrix& current_dist, Matrix& latencies, 3397860SN/A Matrix& inter_switches) 3407860SN/A{ 3417860SN/A bool change = true; 3427860SN/A int nodes = current_dist.size(); 3437860SN/A 3447860SN/A while (change) { 3457860SN/A change = false; 3467860SN/A for (int i = 0; i < nodes; i++) { 3477860SN/A for (int j = 0; j < nodes; j++) { 3487860SN/A int minimum = current_dist[i][j]; 3497860SN/A int previous_minimum = minimum; 3507860SN/A int intermediate_switch = -1; 3517860SN/A for (int k = 0; k < nodes; k++) { 3527860SN/A minimum = min(minimum, 3537860SN/A current_dist[i][k] + current_dist[k][j]); 3547860SN/A if (previous_minimum != minimum) { 3557860SN/A intermediate_switch = k; 3567860SN/A inter_switches[i][j] = 3577860SN/A inter_switches[i][k] + 3587860SN/A inter_switches[k][j] + 1; 3597860SN/A } 3607860SN/A previous_minimum = minimum; 3617860SN/A } 3627860SN/A if (current_dist[i][j] != minimum) { 3637860SN/A change = true; 3647860SN/A current_dist[i][j] = minimum; 3657860SN/A assert(intermediate_switch >= 0); 3667860SN/A assert(intermediate_switch < latencies[i].size()); 3677860SN/A latencies[i][j] = latencies[i][intermediate_switch] + 3687860SN/A latencies[intermediate_switch][j]; 3697860SN/A } 3707860SN/A } 3717860SN/A } 3727860SN/A } 3737860SN/A} 3747860SN/A 3757860SN/AMatrix 3767860SN/Ashortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches) 3777860SN/A{ 3787860SN/A Matrix dist = weights; 3797860SN/A extend_shortest_path(dist, latencies, inter_switches); 3807860SN/A return dist; 3817860SN/A} 3827860SN/A 3837860SN/Abool 3847860SN/Alink_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, 3857860SN/A const Matrix& weights, const Matrix& dist) 3867860SN/A{ 3877860SN/A return weights[src][next] + dist[next][final] == dist[src][final]; 3887860SN/A} 3897860SN/A 3907860SN/ANetDest 3917860SN/Ashortest_path_to_node(SwitchID src, SwitchID next, const Matrix& weights, 3927860SN/A const Matrix& dist) 3937860SN/A{ 3947860SN/A NetDest result; 3957860SN/A int d = 0; 3967860SN/A int machines; 3977860SN/A int max_machines; 3987860SN/A 3997860SN/A machines = MachineType_NUM; 4007860SN/A max_machines = MachineType_base_number(MachineType_NUM); 4017860SN/A 4027860SN/A for (int m = 0; m < machines; m++) { 4037860SN/A for (int i = 0; i < MachineType_base_count((MachineType)m); i++) { 4047860SN/A // we use "d+max_machines" below since the "destination" 4057860SN/A // switches for the machines are numbered 4067860SN/A // [MachineType_base_number(MachineType_NUM)... 4077860SN/A // 2*MachineType_base_number(MachineType_NUM)-1] for the 4087860SN/A // component network 4097860SN/A if (link_is_shortest_path_to_node(src, next, d + max_machines, 4107860SN/A weights, dist)) { 4117860SN/A MachineID mach = {(MachineType)m, i}; 4127860SN/A result.add(mach); 4137860SN/A } 4147860SN/A d++; 4157860SN/A } 4167860SN/A } 4177860SN/A 4187860SN/A DPRINTF(RubyNetwork, "Returning shortest path\n" 4197860SN/A "(src-(2*max_machines)): %d, (next-(2*max_machines)): %d, " 4207860SN/A "src: %d, next: %d, result: %s\n", 4217860SN/A (src-(2*max_machines)), (next-(2*max_machines)), 4227860SN/A src, next, result); 4237860SN/A 4247860SN/A return result; 4257860SN/A} 4267860SN/A 4277860SN/ATopology * 4287860SN/ATopologyParams::create() 4297860SN/A{ 4308893Ssaidi@eecs.umich.edu return new Topology(this); 4317860SN/A} 4327860SN/A 4337860SN/A