Topology.cc revision 11320
15081Sgblack@eecs.umich.edu/* 25081Sgblack@eecs.umich.edu * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 35081Sgblack@eecs.umich.edu * All rights reserved. 45081Sgblack@eecs.umich.edu * 55081Sgblack@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 65081Sgblack@eecs.umich.edu * modification, are permitted provided that the following conditions are 75081Sgblack@eecs.umich.edu * met: redistributions of source code must retain the above copyright 85081Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 95081Sgblack@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 105081Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 115081Sgblack@eecs.umich.edu * documentation and/or other materials provided with the distribution; 125081Sgblack@eecs.umich.edu * neither the name of the copyright holders nor the names of its 135081Sgblack@eecs.umich.edu * contributors may be used to endorse or promote products derived from 145081Sgblack@eecs.umich.edu * this software without specific prior written permission. 155081Sgblack@eecs.umich.edu * 165081Sgblack@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 175081Sgblack@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 185081Sgblack@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 195081Sgblack@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 205081Sgblack@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 215081Sgblack@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 225081Sgblack@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 235081Sgblack@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 245081Sgblack@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 255081Sgblack@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 265081Sgblack@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 275081Sgblack@eecs.umich.edu */ 285081Sgblack@eecs.umich.edu 295081Sgblack@eecs.umich.edu#include <cassert> 305081Sgblack@eecs.umich.edu 315081Sgblack@eecs.umich.edu#include "base/trace.hh" 325081Sgblack@eecs.umich.edu#include "debug/RubyNetwork.hh" 335081Sgblack@eecs.umich.edu#include "mem/ruby/common/NetDest.hh" 345081Sgblack@eecs.umich.edu#include "mem/ruby/network/BasicLink.hh" 355081Sgblack@eecs.umich.edu#include "mem/ruby/network/Topology.hh" 365081Sgblack@eecs.umich.edu#include "mem/ruby/slicc_interface/AbstractController.hh" 375081Sgblack@eecs.umich.edu 385081Sgblack@eecs.umich.eduusing namespace std; 395081Sgblack@eecs.umich.edu 405081Sgblack@eecs.umich.educonst int INFINITE_LATENCY = 10000; // Yes, this is a big hack 415081Sgblack@eecs.umich.edu 425081Sgblack@eecs.umich.edu// Note: In this file, we use the first 2*m_nodes SwitchIDs to 435081Sgblack@eecs.umich.edu// represent the input and output endpoint links. These really are 445081Sgblack@eecs.umich.edu// not 'switches', as they will not have a Switch object allocated for 455081Sgblack@eecs.umich.edu// them. The first m_nodes SwitchIDs are the links into the network, 465081Sgblack@eecs.umich.edu// the second m_nodes set of SwitchIDs represent the the output queues 475081Sgblack@eecs.umich.edu// of the network. 485081Sgblack@eecs.umich.edu 495081Sgblack@eecs.umich.eduTopology::Topology(uint32_t num_routers, 505081Sgblack@eecs.umich.edu const vector<BasicExtLink *> &ext_links, 515081Sgblack@eecs.umich.edu const vector<BasicIntLink *> &int_links) 525081Sgblack@eecs.umich.edu : m_nodes(ext_links.size()), m_number_of_switches(num_routers), 535081Sgblack@eecs.umich.edu m_ext_link_vector(ext_links), m_int_link_vector(int_links) 545081Sgblack@eecs.umich.edu{ 555081Sgblack@eecs.umich.edu // Total nodes/controllers in network 565081Sgblack@eecs.umich.edu assert(m_nodes > 1); 575081Sgblack@eecs.umich.edu 585081Sgblack@eecs.umich.edu // analyze both the internal and external links, create data structures 595081Sgblack@eecs.umich.edu // Note that the python created links are bi-directional, but that the 605081Sgblack@eecs.umich.edu // topology and networks utilize uni-directional links. Thus each 615081Sgblack@eecs.umich.edu // BasicLink is converted to two calls to add link, on for each direction 625081Sgblack@eecs.umich.edu for (vector<BasicExtLink*>::const_iterator i = ext_links.begin(); 635081Sgblack@eecs.umich.edu i != ext_links.end(); ++i) { 645081Sgblack@eecs.umich.edu BasicExtLink *ext_link = (*i); 655081Sgblack@eecs.umich.edu AbstractController *abs_cntrl = ext_link->params()->ext_node; 665081Sgblack@eecs.umich.edu BasicRouter *router = ext_link->params()->int_node; 675081Sgblack@eecs.umich.edu 685081Sgblack@eecs.umich.edu int machine_base_idx = MachineType_base_number(abs_cntrl->getType()); 695081Sgblack@eecs.umich.edu int ext_idx1 = machine_base_idx + abs_cntrl->getVersion(); 705081Sgblack@eecs.umich.edu int ext_idx2 = ext_idx1 + m_nodes; 715119Sgblack@eecs.umich.edu int int_idx = router->params()->router_id + 2*m_nodes; 725081Sgblack@eecs.umich.edu 735081Sgblack@eecs.umich.edu // create the internal uni-directional links in both directions 745081Sgblack@eecs.umich.edu // the first direction is marked: In 755081Sgblack@eecs.umich.edu addLink(ext_idx1, int_idx, ext_link, LinkDirection_In); 765081Sgblack@eecs.umich.edu // the first direction is marked: Out 775081Sgblack@eecs.umich.edu addLink(int_idx, ext_idx2, ext_link, LinkDirection_Out); 785081Sgblack@eecs.umich.edu } 795081Sgblack@eecs.umich.edu 805119Sgblack@eecs.umich.edu for (vector<BasicIntLink*>::const_iterator i = int_links.begin(); 815081Sgblack@eecs.umich.edu i != int_links.end(); ++i) { 825081Sgblack@eecs.umich.edu BasicIntLink *int_link = (*i); 835081Sgblack@eecs.umich.edu BasicRouter *router_a = int_link->params()->node_a; 845081Sgblack@eecs.umich.edu BasicRouter *router_b = int_link->params()->node_b; 856081Sgblack@eecs.umich.edu 866081Sgblack@eecs.umich.edu // Store the IntLink pointers for later 876081Sgblack@eecs.umich.edu m_int_link_vector.push_back(int_link); 886081Sgblack@eecs.umich.edu 896081Sgblack@eecs.umich.edu int a = router_a->params()->router_id + 2*m_nodes; 906081Sgblack@eecs.umich.edu int b = router_b->params()->router_id + 2*m_nodes; 916081Sgblack@eecs.umich.edu 926081Sgblack@eecs.umich.edu // create the internal uni-directional links in both directions 936081Sgblack@eecs.umich.edu // the first direction is marked: In 946081Sgblack@eecs.umich.edu addLink(a, b, int_link, LinkDirection_In); 956081Sgblack@eecs.umich.edu // the second direction is marked: Out 966081Sgblack@eecs.umich.edu addLink(b, a, int_link, LinkDirection_Out); 976081Sgblack@eecs.umich.edu } 986081Sgblack@eecs.umich.edu} 996081Sgblack@eecs.umich.edu 1006081Sgblack@eecs.umich.eduvoid 1016081Sgblack@eecs.umich.eduTopology::createLinks(Network *net) 1025081Sgblack@eecs.umich.edu{ 1035081Sgblack@eecs.umich.edu // Find maximum switchID 1045119Sgblack@eecs.umich.edu SwitchID max_switch_id = 0; 1055081Sgblack@eecs.umich.edu for (LinkMap::const_iterator i = m_link_map.begin(); 1065081Sgblack@eecs.umich.edu i != m_link_map.end(); ++i) { 1075081Sgblack@eecs.umich.edu std::pair<SwitchID, SwitchID> src_dest = (*i).first; 1085081Sgblack@eecs.umich.edu max_switch_id = max(max_switch_id, src_dest.first); 1095081Sgblack@eecs.umich.edu max_switch_id = max(max_switch_id, src_dest.second); 1105081Sgblack@eecs.umich.edu } 1115081Sgblack@eecs.umich.edu 1125119Sgblack@eecs.umich.edu // Initialize weight, latency, and inter switched vectors 1135081Sgblack@eecs.umich.edu int num_switches = max_switch_id+1; 1145081Sgblack@eecs.umich.edu Matrix topology_weights(num_switches, 1155081Sgblack@eecs.umich.edu vector<int>(num_switches, INFINITE_LATENCY)); 1165081Sgblack@eecs.umich.edu Matrix component_latencies(num_switches, 1176081Sgblack@eecs.umich.edu vector<int>(num_switches, -1)); 1186081Sgblack@eecs.umich.edu Matrix component_inter_switches(num_switches, 1196081Sgblack@eecs.umich.edu vector<int>(num_switches, 0)); 1206081Sgblack@eecs.umich.edu 1216081Sgblack@eecs.umich.edu // Set identity weights to zero 1226081Sgblack@eecs.umich.edu for (int i = 0; i < topology_weights.size(); i++) { 1236081Sgblack@eecs.umich.edu topology_weights[i][i] = 0; 1246081Sgblack@eecs.umich.edu } 1256081Sgblack@eecs.umich.edu 1266081Sgblack@eecs.umich.edu // Fill in the topology weights and bandwidth multipliers 1276081Sgblack@eecs.umich.edu for (LinkMap::const_iterator i = m_link_map.begin(); 1286081Sgblack@eecs.umich.edu i != m_link_map.end(); ++i) { 1296081Sgblack@eecs.umich.edu std::pair<int, int> src_dest = (*i).first; 1306081Sgblack@eecs.umich.edu BasicLink* link = (*i).second.link; 1316081Sgblack@eecs.umich.edu int src = src_dest.first; 1325081Sgblack@eecs.umich.edu int dst = src_dest.second; 1335081Sgblack@eecs.umich.edu component_latencies[src][dst] = link->m_latency; 1345081Sgblack@eecs.umich.edu topology_weights[src][dst] = link->m_weight; 1355081Sgblack@eecs.umich.edu } 1365081Sgblack@eecs.umich.edu 1375081Sgblack@eecs.umich.edu // Walk topology and hookup the links 1385081Sgblack@eecs.umich.edu Matrix dist = shortest_path(topology_weights, component_latencies, 1395081Sgblack@eecs.umich.edu component_inter_switches); 1405081Sgblack@eecs.umich.edu 1415081Sgblack@eecs.umich.edu for (int i = 0; i < topology_weights.size(); i++) { 1425081Sgblack@eecs.umich.edu for (int j = 0; j < topology_weights[i].size(); j++) { 1435081Sgblack@eecs.umich.edu int weight = topology_weights[i][j]; 1445081Sgblack@eecs.umich.edu if (weight > 0 && weight != INFINITE_LATENCY) { 1455081Sgblack@eecs.umich.edu NetDest destination_set = 1465081Sgblack@eecs.umich.edu shortest_path_to_node(i, j, topology_weights, dist); 1475081Sgblack@eecs.umich.edu makeLink(net, i, j, destination_set); 1485081Sgblack@eecs.umich.edu } 1495081Sgblack@eecs.umich.edu } 1505081Sgblack@eecs.umich.edu } 1515081Sgblack@eecs.umich.edu} 1525081Sgblack@eecs.umich.edu 1535081Sgblack@eecs.umich.eduvoid 1545081Sgblack@eecs.umich.eduTopology::addLink(SwitchID src, SwitchID dest, BasicLink* link, 1555081Sgblack@eecs.umich.edu LinkDirection dir) 1565081Sgblack@eecs.umich.edu{ 1575081Sgblack@eecs.umich.edu assert(src <= m_number_of_switches+m_nodes+m_nodes); 1585081Sgblack@eecs.umich.edu assert(dest <= m_number_of_switches+m_nodes+m_nodes); 1595081Sgblack@eecs.umich.edu 1605081Sgblack@eecs.umich.edu std::pair<int, int> src_dest_pair; 1615081Sgblack@eecs.umich.edu LinkEntry link_entry; 1625081Sgblack@eecs.umich.edu 1635081Sgblack@eecs.umich.edu src_dest_pair.first = src; 1645081Sgblack@eecs.umich.edu src_dest_pair.second = dest; 1655081Sgblack@eecs.umich.edu link_entry.direction = dir; 1665081Sgblack@eecs.umich.edu link_entry.link = link; 1675081Sgblack@eecs.umich.edu m_link_map[src_dest_pair] = link_entry; 1685081Sgblack@eecs.umich.edu} 1695081Sgblack@eecs.umich.edu 1705081Sgblack@eecs.umich.eduvoid 1715081Sgblack@eecs.umich.eduTopology::makeLink(Network *net, SwitchID src, SwitchID dest, 1725119Sgblack@eecs.umich.edu const NetDest& routing_table_entry) 1735081Sgblack@eecs.umich.edu{ 1745081Sgblack@eecs.umich.edu // Make sure we're not trying to connect two end-point nodes 1755081Sgblack@eecs.umich.edu // directly together 1765081Sgblack@eecs.umich.edu assert(src >= 2 * m_nodes || dest >= 2 * m_nodes); 1775081Sgblack@eecs.umich.edu 1785081Sgblack@eecs.umich.edu std::pair<int, int> src_dest; 1795081Sgblack@eecs.umich.edu LinkEntry link_entry; 1805081Sgblack@eecs.umich.edu 1815119Sgblack@eecs.umich.edu if (src < m_nodes) { 1825081Sgblack@eecs.umich.edu src_dest.first = src; 1835081Sgblack@eecs.umich.edu src_dest.second = dest; 1845081Sgblack@eecs.umich.edu link_entry = m_link_map[src_dest]; 1855081Sgblack@eecs.umich.edu net->makeInLink(src, dest - (2 * m_nodes), link_entry.link, 1866086Sgblack@eecs.umich.edu link_entry.direction, routing_table_entry); 1876086Sgblack@eecs.umich.edu } else if (dest < 2*m_nodes) { 1886086Sgblack@eecs.umich.edu assert(dest >= m_nodes); 1896086Sgblack@eecs.umich.edu NodeID node = dest - m_nodes; 1906086Sgblack@eecs.umich.edu src_dest.first = src; 1916086Sgblack@eecs.umich.edu src_dest.second = dest; 1926086Sgblack@eecs.umich.edu link_entry = m_link_map[src_dest]; 1936086Sgblack@eecs.umich.edu net->makeOutLink(src - (2 * m_nodes), node, link_entry.link, 1946086Sgblack@eecs.umich.edu link_entry.direction, routing_table_entry); 1956086Sgblack@eecs.umich.edu } else { 1966086Sgblack@eecs.umich.edu assert((src >= 2 * m_nodes) && (dest >= 2 * m_nodes)); 1976086Sgblack@eecs.umich.edu src_dest.first = src; 1986086Sgblack@eecs.umich.edu src_dest.second = dest; 1996086Sgblack@eecs.umich.edu link_entry = m_link_map[src_dest]; 2006086Sgblack@eecs.umich.edu net->makeInternalLink(src - (2 * m_nodes), dest - (2 * m_nodes), 2016086Sgblack@eecs.umich.edu link_entry.link, link_entry.direction, 2026086Sgblack@eecs.umich.edu routing_table_entry); 2035081Sgblack@eecs.umich.edu } 2045081Sgblack@eecs.umich.edu} 2055119Sgblack@eecs.umich.edu 2065081Sgblack@eecs.umich.edu// The following all-pairs shortest path algorithm is based on the 2075081Sgblack@eecs.umich.edu// discussion from Cormen et al., Chapter 26.1. 2085081Sgblack@eecs.umich.eduvoid 2095081Sgblack@eecs.umich.eduTopology::extend_shortest_path(Matrix ¤t_dist, Matrix &latencies, 2105081Sgblack@eecs.umich.edu Matrix &inter_switches) 2115081Sgblack@eecs.umich.edu{ 2125081Sgblack@eecs.umich.edu bool change = true; 2135119Sgblack@eecs.umich.edu int nodes = current_dist.size(); 2145081Sgblack@eecs.umich.edu 2155081Sgblack@eecs.umich.edu while (change) { 2165081Sgblack@eecs.umich.edu change = false; 2175081Sgblack@eecs.umich.edu for (int i = 0; i < nodes; i++) { 2186086Sgblack@eecs.umich.edu for (int j = 0; j < nodes; j++) { 2196086Sgblack@eecs.umich.edu int minimum = current_dist[i][j]; 2206086Sgblack@eecs.umich.edu int previous_minimum = minimum; 2216086Sgblack@eecs.umich.edu int intermediate_switch = -1; 2226086Sgblack@eecs.umich.edu for (int k = 0; k < nodes; k++) { 2236086Sgblack@eecs.umich.edu minimum = min(minimum, 2246086Sgblack@eecs.umich.edu current_dist[i][k] + current_dist[k][j]); 2256086Sgblack@eecs.umich.edu if (previous_minimum != minimum) { 2266086Sgblack@eecs.umich.edu intermediate_switch = k; 2276086Sgblack@eecs.umich.edu inter_switches[i][j] = 2286086Sgblack@eecs.umich.edu inter_switches[i][k] + 2296086Sgblack@eecs.umich.edu inter_switches[k][j] + 1; 2306086Sgblack@eecs.umich.edu } 2316086Sgblack@eecs.umich.edu previous_minimum = minimum; 2326086Sgblack@eecs.umich.edu } 2335081Sgblack@eecs.umich.edu if (current_dist[i][j] != minimum) { 2345081Sgblack@eecs.umich.edu change = true; 2355081Sgblack@eecs.umich.edu current_dist[i][j] = minimum; 2365081Sgblack@eecs.umich.edu assert(intermediate_switch >= 0); 2375081Sgblack@eecs.umich.edu assert(intermediate_switch < latencies[i].size()); 2385081Sgblack@eecs.umich.edu latencies[i][j] = latencies[i][intermediate_switch] + 2395081Sgblack@eecs.umich.edu latencies[intermediate_switch][j]; 2405081Sgblack@eecs.umich.edu } 2415081Sgblack@eecs.umich.edu } 2425081Sgblack@eecs.umich.edu } 2435081Sgblack@eecs.umich.edu } 2445081Sgblack@eecs.umich.edu} 2455081Sgblack@eecs.umich.edu 2465081Sgblack@eecs.umich.eduMatrix 2475119Sgblack@eecs.umich.eduTopology::shortest_path(const Matrix &weights, Matrix &latencies, 2485081Sgblack@eecs.umich.edu Matrix &inter_switches) 2495081Sgblack@eecs.umich.edu{ 2505081Sgblack@eecs.umich.edu Matrix dist = weights; 2515081Sgblack@eecs.umich.edu extend_shortest_path(dist, latencies, inter_switches); 2525081Sgblack@eecs.umich.edu return dist; 2535081Sgblack@eecs.umich.edu} 2545081Sgblack@eecs.umich.edu 2555081Sgblack@eecs.umich.edubool 2565119Sgblack@eecs.umich.eduTopology::link_is_shortest_path_to_node(SwitchID src, SwitchID next, 2575081Sgblack@eecs.umich.edu SwitchID final, const Matrix &weights, 2585081Sgblack@eecs.umich.edu const Matrix &dist) 2595081Sgblack@eecs.umich.edu{ 2605081Sgblack@eecs.umich.edu return weights[src][next] + dist[next][final] == dist[src][final]; 2616083Sgblack@eecs.umich.edu} 2626083Sgblack@eecs.umich.edu 2636083Sgblack@eecs.umich.eduNetDest 2646083Sgblack@eecs.umich.eduTopology::shortest_path_to_node(SwitchID src, SwitchID next, 2656083Sgblack@eecs.umich.edu const Matrix &weights, const Matrix &dist) 2666083Sgblack@eecs.umich.edu{ 2676083Sgblack@eecs.umich.edu NetDest result; 2686083Sgblack@eecs.umich.edu int d = 0; 2696083Sgblack@eecs.umich.edu int machines; 2706083Sgblack@eecs.umich.edu int max_machines; 2716083Sgblack@eecs.umich.edu 2726083Sgblack@eecs.umich.edu machines = MachineType_NUM; 2736083Sgblack@eecs.umich.edu max_machines = MachineType_base_number(MachineType_NUM); 2746083Sgblack@eecs.umich.edu 2756083Sgblack@eecs.umich.edu for (int m = 0; m < machines; m++) { 2766083Sgblack@eecs.umich.edu for (NodeID i = 0; i < MachineType_base_count((MachineType)m); i++) { 2776083Sgblack@eecs.umich.edu // we use "d+max_machines" below since the "destination" 2785081Sgblack@eecs.umich.edu // switches for the machines are numbered 2795081Sgblack@eecs.umich.edu // [MachineType_base_number(MachineType_NUM)... 2805119Sgblack@eecs.umich.edu // 2*MachineType_base_number(MachineType_NUM)-1] for the 2815081Sgblack@eecs.umich.edu // component network 2825081Sgblack@eecs.umich.edu if (link_is_shortest_path_to_node(src, next, d + max_machines, 2835081Sgblack@eecs.umich.edu weights, dist)) { 2845081Sgblack@eecs.umich.edu MachineID mach = {(MachineType)m, i}; 2855081Sgblack@eecs.umich.edu result.add(mach); 2865081Sgblack@eecs.umich.edu } 2875081Sgblack@eecs.umich.edu d++; 2885119Sgblack@eecs.umich.edu } 2895081Sgblack@eecs.umich.edu } 2905081Sgblack@eecs.umich.edu 2915081Sgblack@eecs.umich.edu DPRINTF(RubyNetwork, "Returning shortest path\n" 2925081Sgblack@eecs.umich.edu "(src-(2*max_machines)): %d, (next-(2*max_machines)): %d, " 2936083Sgblack@eecs.umich.edu "src: %d, next: %d, result: %s\n", 2946083Sgblack@eecs.umich.edu (src-(2*max_machines)), (next-(2*max_machines)), 2956083Sgblack@eecs.umich.edu src, next, result); 2966083Sgblack@eecs.umich.edu 2976083Sgblack@eecs.umich.edu return result; 2986083Sgblack@eecs.umich.edu} 2996083Sgblack@eecs.umich.edu