Topology.cc revision 11664
12137SN/A/* 25268Sksewell@umich.edu * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 35254Sksewell@umich.edu * All rights reserved. 45254Sksewell@umich.edu * 52137SN/A * Redistribution and use in source and binary forms, with or without 65254Sksewell@umich.edu * modification, are permitted provided that the following conditions are 75254Sksewell@umich.edu * met: redistributions of source code must retain the above copyright 85254Sksewell@umich.edu * notice, this list of conditions and the following disclaimer; 95254Sksewell@umich.edu * redistributions in binary form must reproduce the above copyright 105254Sksewell@umich.edu * notice, this list of conditions and the following disclaimer in the 115254Sksewell@umich.edu * documentation and/or other materials provided with the distribution; 125254Sksewell@umich.edu * neither the name of the copyright holders nor the names of its 135254Sksewell@umich.edu * contributors may be used to endorse or promote products derived from 145254Sksewell@umich.edu * this software without specific prior written permission. 155254Sksewell@umich.edu * 162137SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 175254Sksewell@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 185254Sksewell@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 195254Sksewell@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 205254Sksewell@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 215254Sksewell@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 225254Sksewell@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 235254Sksewell@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 245254Sksewell@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 255254Sksewell@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 265254Sksewell@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 275254Sksewell@umich.edu */ 282665Ssaidi@eecs.umich.edu 295268Sksewell@umich.edu#include <cassert> 305268Sksewell@umich.edu 312137SN/A#include "base/trace.hh" 322137SN/A#include "debug/RubyNetwork.hh" 332597SN/A#include "mem/ruby/common/NetDest.hh" 342597SN/A#include "mem/ruby/network/BasicLink.hh" 352137SN/A#include "mem/ruby/network/Topology.hh" 362137SN/A#include "mem/ruby/slicc_interface/AbstractController.hh" 372137SN/A 382680Sktlim@umich.eduusing namespace std; 392137SN/A 402137SN/Aconst int INFINITE_LATENCY = 10000; // Yes, this is a big hack 412137SN/A 424661Sksewell@umich.edu// Note: In this file, we use the first 2*m_nodes SwitchIDs to 432137SN/A// represent the input and output endpoint links. These really are 444661Sksewell@umich.edu// not 'switches', as they will not have a Switch object allocated for 452137SN/A// them. The first m_nodes SwitchIDs are the links into the network, 462137SN/A// the second m_nodes set of SwitchIDs represent the the output queues 472137SN/A// of the network. 482137SN/A 492137SN/ATopology::Topology(uint32_t num_routers, 502137SN/A const vector<BasicExtLink *> &ext_links, 513114Sgblack@eecs.umich.edu const vector<BasicIntLink *> &int_links) 522680Sktlim@umich.edu : m_nodes(ext_links.size()), m_number_of_switches(num_routers), 532137SN/A m_ext_link_vector(ext_links), m_int_link_vector(int_links) 542680Sktlim@umich.edu{ 552137SN/A // Total nodes/controllers in network 562137SN/A assert(m_nodes > 1); 574661Sksewell@umich.edu 582137SN/A // analyze both the internal and external links, create data structures. 592137SN/A // The python created external links are bi-directional, 602137SN/A // and the python created internal links are uni-directional. 612137SN/A // The networks and topology utilize uni-directional links. 622680Sktlim@umich.edu // Thus each external link is converted to two calls to addLink, 632137SN/A // one for each direction. 642137SN/A // 652137SN/A // External Links 662484SN/A for (vector<BasicExtLink*>::const_iterator i = ext_links.begin(); 672137SN/A i != ext_links.end(); ++i) { 682137SN/A BasicExtLink *ext_link = (*i); 692137SN/A AbstractController *abs_cntrl = ext_link->params()->ext_node; 703114Sgblack@eecs.umich.edu BasicRouter *router = ext_link->params()->int_node; 712680Sktlim@umich.edu 722137SN/A int machine_base_idx = MachineType_base_number(abs_cntrl->getType()); 732680Sktlim@umich.edu int ext_idx1 = machine_base_idx + abs_cntrl->getVersion(); 742680Sktlim@umich.edu int ext_idx2 = ext_idx1 + m_nodes; 752137SN/A int int_idx = router->params()->router_id + 2*m_nodes; 762137SN/A 772137SN/A // create the internal uni-directional links in both directions 782137SN/A // ext to int 792680Sktlim@umich.edu addLink(ext_idx1, int_idx, ext_link); 802137SN/A // int to ext 812137SN/A addLink(int_idx, ext_idx2, ext_link); 822680Sktlim@umich.edu } 832137SN/A 842137SN/A // Internal Links 852137SN/A for (vector<BasicIntLink*>::const_iterator i = int_links.begin(); 862137SN/A i != int_links.end(); ++i) { 872484SN/A BasicIntLink *int_link = (*i); 882137SN/A BasicRouter *router_src = int_link->params()->src_node; 892137SN/A BasicRouter *router_dst = int_link->params()->dst_node; 902137SN/A 912137SN/A PortDirection src_outport = int_link->params()->src_outport; 922137SN/A PortDirection dst_inport = int_link->params()->dst_inport; 932137SN/A 942137SN/A // Store the IntLink pointers for later 952484SN/A m_int_link_vector.push_back(int_link); 962137SN/A 973114Sgblack@eecs.umich.edu int src = router_src->params()->router_id + 2*m_nodes; 982680Sktlim@umich.edu int dst = router_dst->params()->router_id + 2*m_nodes; 992137SN/A 1002680Sktlim@umich.edu // create the internal uni-directional link from src to dst 1012680Sktlim@umich.edu addLink(src, dst, int_link, src_outport, dst_inport); 1022137SN/A } 1032137SN/A} 1042137SN/A 1052137SN/Avoid 1062680Sktlim@umich.eduTopology::createLinks(Network *net) 1072137SN/A{ 1082680Sktlim@umich.edu // Find maximum switchID 1092484SN/A SwitchID max_switch_id = 0; 1102137SN/A for (LinkMap::const_iterator i = m_link_map.begin(); 1112137SN/A i != m_link_map.end(); ++i) { 1122137SN/A std::pair<SwitchID, SwitchID> src_dest = (*i).first; 1132137SN/A max_switch_id = max(max_switch_id, src_dest.first); 1142137SN/A max_switch_id = max(max_switch_id, src_dest.second); 1152484SN/A } 1162137SN/A 1172137SN/A // Initialize weight, latency, and inter switched vectors 1182137SN/A int num_switches = max_switch_id+1; 1192137SN/A Matrix topology_weights(num_switches, 1202137SN/A vector<int>(num_switches, INFINITE_LATENCY)); 1212137SN/A Matrix component_latencies(num_switches, 1222137SN/A vector<int>(num_switches, -1)); 1232137SN/A Matrix component_inter_switches(num_switches, 1242484SN/A vector<int>(num_switches, 0)); 1252137SN/A 1262137SN/A // Set identity weights to zero 1272137SN/A for (int i = 0; i < topology_weights.size(); i++) { 1282137SN/A topology_weights[i][i] = 0; 1292553SN/A } 1302137SN/A 1312484SN/A // Fill in the topology weights and bandwidth multipliers 1322484SN/A for (LinkMap::const_iterator i = m_link_map.begin(); 1332137SN/A i != m_link_map.end(); ++i) { 1342137SN/A std::pair<int, int> src_dest = (*i).first; 1352484SN/A BasicLink* link = (*i).second.link; 1362137SN/A int src = src_dest.first; 1372484SN/A int dst = src_dest.second; 1382137SN/A component_latencies[src][dst] = link->m_latency; 1392553SN/A topology_weights[src][dst] = link->m_weight; 1402484SN/A } 1412686Sksewell@umich.edu 1422484SN/A // Walk topology and hookup the links 1432137SN/A Matrix dist = shortest_path(topology_weights, component_latencies, 1442484SN/A component_inter_switches); 1452484SN/A 1462137SN/A for (int i = 0; i < topology_weights.size(); i++) { 1472137SN/A for (int j = 0; j < topology_weights[i].size(); j++) { 1482484SN/A int weight = topology_weights[i][j]; 1492484SN/A if (weight > 0 && weight != INFINITE_LATENCY) { 1502484SN/A NetDest destination_set = 1512484SN/A shortest_path_to_node(i, j, topology_weights, dist); 1522484SN/A makeLink(net, i, j, destination_set); 1532484SN/A } 1542484SN/A } 1552484SN/A } 1562484SN/A} 1572137SN/A 1582484SN/Avoid 1592484SN/ATopology::addLink(SwitchID src, SwitchID dest, BasicLink* link, 1602137SN/A PortDirection src_outport_dirn, 1614661Sksewell@umich.edu PortDirection dst_inport_dirn) 1622484SN/A{ 1632484SN/A assert(src <= m_number_of_switches+m_nodes+m_nodes); 1642484SN/A assert(dest <= m_number_of_switches+m_nodes+m_nodes); 1652137SN/A 1664661Sksewell@umich.edu std::pair<int, int> src_dest_pair; 1672484SN/A LinkEntry link_entry; 1682484SN/A 1692686Sksewell@umich.edu src_dest_pair.first = src; 1702491SN/A src_dest_pair.second = dest; 1712484SN/A link_entry.link = link; 1722484SN/A link_entry.src_outport_dirn = src_outport_dirn; 1732491SN/A link_entry.dst_inport_dirn = dst_inport_dirn; 1742491SN/A m_link_map[src_dest_pair] = link_entry; 1752137SN/A} 1762484SN/A 1772484SN/Avoid 1784661Sksewell@umich.eduTopology::makeLink(Network *net, SwitchID src, SwitchID dest, 1792686Sksewell@umich.edu const NetDest& routing_table_entry) 1802484SN/A{ 1812484SN/A // Make sure we're not trying to connect two end-point nodes 1822484SN/A // directly together 1832484SN/A assert(src >= 2 * m_nodes || dest >= 2 * m_nodes); 1842137SN/A 1852137SN/A std::pair<int, int> src_dest; 1862484SN/A LinkEntry link_entry; 1872484SN/A 1882484SN/A if (src < m_nodes) { 1892484SN/A src_dest.first = src; 1902484SN/A src_dest.second = dest; 1912495SN/A link_entry = m_link_map[src_dest]; 1922495SN/A net->makeExtInLink(src, dest - (2 * m_nodes), link_entry.link, 1932484SN/A routing_table_entry); 1942484SN/A } else if (dest < 2*m_nodes) { 1952495SN/A assert(dest >= m_nodes); 1962484SN/A NodeID node = dest - m_nodes; 1972495SN/A src_dest.first = src; 1982484SN/A src_dest.second = dest; 1994661Sksewell@umich.edu link_entry = m_link_map[src_dest]; 2004661Sksewell@umich.edu net->makeExtOutLink(src - (2 * m_nodes), node, link_entry.link, 2014661Sksewell@umich.edu routing_table_entry); 2022484SN/A } else { 2032484SN/A assert((src >= 2 * m_nodes) && (dest >= 2 * m_nodes)); 2042484SN/A src_dest.first = src; 2052484SN/A src_dest.second = dest; 2062484SN/A link_entry = m_link_map[src_dest]; 2072484SN/A net->makeInternalLink(src - (2 * m_nodes), dest - (2 * m_nodes), 2082484SN/A link_entry.link, 2092484SN/A routing_table_entry, 2102484SN/A link_entry.src_outport_dirn, 2112484SN/A link_entry.dst_inport_dirn); 2122484SN/A } 2132484SN/A} 2142553SN/A 2152495SN/A// The following all-pairs shortest path algorithm is based on the 2162686Sksewell@umich.edu// discussion from Cormen et al., Chapter 26.1. 2172686Sksewell@umich.eduvoid 2184661Sksewell@umich.eduTopology::extend_shortest_path(Matrix ¤t_dist, Matrix &latencies, 2194661Sksewell@umich.edu Matrix &inter_switches) 2202484SN/A{ 2212484SN/A bool change = true; 2222484SN/A int nodes = current_dist.size(); 2232484SN/A 2242484SN/A while (change) { 2252484SN/A change = false; 2262484SN/A for (int i = 0; i < nodes; i++) { 2272484SN/A for (int j = 0; j < nodes; j++) { 2282484SN/A int minimum = current_dist[i][j]; 2292484SN/A int previous_minimum = minimum; 2302553SN/A int intermediate_switch = -1; 2312484SN/A for (int k = 0; k < nodes; k++) { 2322553SN/A minimum = min(minimum, 2332484SN/A current_dist[i][k] + current_dist[k][j]); 2342484SN/A if (previous_minimum != minimum) { 2352484SN/A intermediate_switch = k; 2362484SN/A inter_switches[i][j] = 2372484SN/A inter_switches[i][k] + 2382484SN/A inter_switches[k][j] + 1; 2392484SN/A } 2402484SN/A previous_minimum = minimum; 2412484SN/A } 2422484SN/A if (current_dist[i][j] != minimum) { 2432484SN/A change = true; 2444661Sksewell@umich.edu current_dist[i][j] = minimum; 2452484SN/A assert(intermediate_switch >= 0); 2462492SN/A assert(intermediate_switch < latencies[i].size()); 2472491SN/A latencies[i][j] = latencies[i][intermediate_switch] + 2482491SN/A latencies[intermediate_switch][j]; 2492495SN/A } 2502484SN/A } 2512484SN/A } 2522484SN/A } 2532484SN/A} 2542484SN/A 2552484SN/AMatrix 2562484SN/ATopology::shortest_path(const Matrix &weights, Matrix &latencies, 2572484SN/A Matrix &inter_switches) 2582484SN/A{ 2592484SN/A Matrix dist = weights; 2602484SN/A extend_shortest_path(dist, latencies, inter_switches); 2612484SN/A return dist; 2622484SN/A} 2632484SN/A 2642484SN/Abool 2652484SN/ATopology::link_is_shortest_path_to_node(SwitchID src, SwitchID next, 2662484SN/A SwitchID final, const Matrix &weights, 2672484SN/A const Matrix &dist) 2682686Sksewell@umich.edu{ 2692484SN/A return weights[src][next] + dist[next][final] == dist[src][final]; 2702553SN/A} 2712484SN/A 2722484SN/ANetDest 2732484SN/ATopology::shortest_path_to_node(SwitchID src, SwitchID next, 2742484SN/A const Matrix &weights, const Matrix &dist) 2752484SN/A{ 2762484SN/A NetDest result; 2774661Sksewell@umich.edu int d = 0; 2782484SN/A int machines; 2792484SN/A int max_machines; 2802484SN/A 2812484SN/A machines = MachineType_NUM; 2822484SN/A max_machines = MachineType_base_number(MachineType_NUM); 2832484SN/A 2842484SN/A for (int m = 0; m < machines; m++) { 2852484SN/A for (NodeID i = 0; i < MachineType_base_count((MachineType)m); i++) { 2862484SN/A // we use "d+max_machines" below since the "destination" 2872484SN/A // switches for the machines are numbered 2882484SN/A // [MachineType_base_number(MachineType_NUM)... 2892484SN/A // 2*MachineType_base_number(MachineType_NUM)-1] for the 2902484SN/A // component network 2912484SN/A if (link_is_shortest_path_to_node(src, next, d + max_machines, 2922484SN/A weights, dist)) { 2932484SN/A MachineID mach = {(MachineType)m, i}; 2942484SN/A result.add(mach); 2952484SN/A } 2962484SN/A d++; 2972484SN/A } 2982484SN/A } 2992484SN/A 3002484SN/A DPRINTF(RubyNetwork, "Returning shortest path\n" 3012484SN/A "(src-(2*max_machines)): %d, (next-(2*max_machines)): %d, " 3022484SN/A "src: %d, next: %d, result: %s\n", 3032484SN/A (src-(2*max_machines)), (next-(2*max_machines)), 3042484SN/A src, next, result); 3052484SN/A 3062137SN/A return result; 3072484SN/A} 3082484SN/A