Topology.cc revision 6895
1955SN/A 2955SN/A/* 31762SN/A * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 4955SN/A * All rights reserved. 5955SN/A * 6955SN/A * Redistribution and use in source and binary forms, with or without 7955SN/A * modification, are permitted provided that the following conditions are 8955SN/A * met: redistributions of source code must retain the above copyright 9955SN/A * notice, this list of conditions and the following disclaimer; 10955SN/A * redistributions in binary form must reproduce the above copyright 11955SN/A * notice, this list of conditions and the following disclaimer in the 12955SN/A * documentation and/or other materials provided with the distribution; 13955SN/A * neither the name of the copyright holders nor the names of its 14955SN/A * contributors may be used to endorse or promote products derived from 15955SN/A * this software without specific prior written permission. 16955SN/A * 17955SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 18955SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 19955SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 20955SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 21955SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22955SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23955SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24955SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25955SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26955SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27955SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 282665Ssaidi@eecs.umich.edu */ 292665Ssaidi@eecs.umich.edu 30955SN/A/* 31955SN/A * Topology.cc 32955SN/A * 33955SN/A * Description: See Topology.hh 34955SN/A * 352632Sstever@eecs.umich.edu * $Id$ 362632Sstever@eecs.umich.edu * 372632Sstever@eecs.umich.edu * */ 382632Sstever@eecs.umich.edu 39955SN/A#include "mem/ruby/network/simple/Topology.hh" 402632Sstever@eecs.umich.edu#include "mem/ruby/common/NetDest.hh" 412632Sstever@eecs.umich.edu#include "mem/ruby/network/Network.hh" 422761Sstever@eecs.umich.edu#include "mem/ruby/slicc_interface/AbstractController.hh" 432632Sstever@eecs.umich.edu#include "mem/protocol/TopologyType.hh" 442632Sstever@eecs.umich.edu#include "mem/gems_common/util.hh" 452632Sstever@eecs.umich.edu#include "mem/protocol/MachineType.hh" 462761Sstever@eecs.umich.edu#include "mem/protocol/Protocol.hh" 472761Sstever@eecs.umich.edu#include "mem/ruby/system/System.hh" 482761Sstever@eecs.umich.edu#include <string> 492632Sstever@eecs.umich.edu 502632Sstever@eecs.umich.edustatic const int INFINITE_LATENCY = 10000; // Yes, this is a big hack 512761Sstever@eecs.umich.edustatic const int DEFAULT_BW_MULTIPLIER = 1; // Just to be consistent with above :) 522761Sstever@eecs.umich.edu 532761Sstever@eecs.umich.edu// Note: In this file, we use the first 2*m_nodes SwitchIDs to 542761Sstever@eecs.umich.edu// represent the input and output endpoint links. These really are 552761Sstever@eecs.umich.edu// not 'switches', as they will not have a Switch object allocated for 562632Sstever@eecs.umich.edu// them. The first m_nodes SwitchIDs are the links into the network, 572632Sstever@eecs.umich.edu// the second m_nodes set of SwitchIDs represent the the output queues 582632Sstever@eecs.umich.edu// of the network. 592632Sstever@eecs.umich.edu 602632Sstever@eecs.umich.edu// Helper functions based on chapter 29 of Cormen et al. 612632Sstever@eecs.umich.edustatic void extend_shortest_path(Matrix& current_dist, Matrix& latencies, Matrix& inter_switches); 622632Sstever@eecs.umich.edustatic Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches); 63955SN/Astatic bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, const Matrix& weights, const Matrix& dist); 64955SN/Astatic NetDest shortest_path_to_node(SwitchID src, SwitchID next, const Matrix& weights, const Matrix& dist); 65955SN/A 66955SN/ATopology::Topology(const Params *p) 67955SN/A : SimObject(p) 685396Ssaidi@eecs.umich.edu{ 694202Sbinkertn@umich.edu m_print_config = p->print_config; 705342Sstever@gmail.com m_number_of_switches = p->num_int_nodes; 71955SN/A // initialize component latencies record 725273Sstever@gmail.com m_component_latencies.setSize(0); 735273Sstever@gmail.com m_component_inter_switches.setSize(0); 742656Sstever@eecs.umich.edu 752656Sstever@eecs.umich.edu // 762656Sstever@eecs.umich.edu // Total nodes/controllers in network 772656Sstever@eecs.umich.edu // Must make sure this is called after the State Machine constructors 782656Sstever@eecs.umich.edu // 792656Sstever@eecs.umich.edu m_nodes = MachineType_base_number(MachineType_NUM); 802656Sstever@eecs.umich.edu assert(m_nodes > 1); 812653Sstever@eecs.umich.edu 825227Ssaidi@eecs.umich.edu if (m_nodes != params()->ext_links.size()) { 835227Ssaidi@eecs.umich.edu fatal("m_nodes (%d) != ext_links vector length (%d)\n", 845227Ssaidi@eecs.umich.edu m_nodes != params()->ext_links.size()); 855227Ssaidi@eecs.umich.edu } 865396Ssaidi@eecs.umich.edu 875396Ssaidi@eecs.umich.edu // 885396Ssaidi@eecs.umich.edu // First create the links between the endpoints (i.e. controllers) and the 895396Ssaidi@eecs.umich.edu // network. 905396Ssaidi@eecs.umich.edu // 915396Ssaidi@eecs.umich.edu for (vector<ExtLink*>::const_iterator i = params()->ext_links.begin(); 925396Ssaidi@eecs.umich.edu i != params()->ext_links.end(); ++i) 935396Ssaidi@eecs.umich.edu { 945396Ssaidi@eecs.umich.edu const ExtLinkParams *p = (*i)->params(); 955396Ssaidi@eecs.umich.edu AbstractController *c = p->ext_node; 965396Ssaidi@eecs.umich.edu 975396Ssaidi@eecs.umich.edu // Store the controller pointers for later 985396Ssaidi@eecs.umich.edu m_controller_vector.insertAtBottom(c); 995396Ssaidi@eecs.umich.edu 1005396Ssaidi@eecs.umich.edu int ext_idx1 = 1015396Ssaidi@eecs.umich.edu MachineType_base_number(c->getMachineType()) + c->getVersion(); 1025396Ssaidi@eecs.umich.edu int ext_idx2 = ext_idx1 + m_nodes; 1035396Ssaidi@eecs.umich.edu int int_idx = p->int_node + 2*m_nodes; 1045396Ssaidi@eecs.umich.edu 1055396Ssaidi@eecs.umich.edu // create the links in both directions 1065396Ssaidi@eecs.umich.edu addLink(ext_idx1, int_idx, p->latency, p->bw_multiplier, p->weight); 1075396Ssaidi@eecs.umich.edu addLink(int_idx, ext_idx2, p->latency, p->bw_multiplier, p->weight); 1085396Ssaidi@eecs.umich.edu } 1095396Ssaidi@eecs.umich.edu 1105396Ssaidi@eecs.umich.edu for (vector<IntLink*>::const_iterator i = params()->int_links.begin(); 1115396Ssaidi@eecs.umich.edu i != params()->int_links.end(); ++i) 1125396Ssaidi@eecs.umich.edu { 1135396Ssaidi@eecs.umich.edu const IntLinkParams *p = (*i)->params(); 1145396Ssaidi@eecs.umich.edu int a = p->node_a + 2*m_nodes; 1155396Ssaidi@eecs.umich.edu int b = p->node_b + 2*m_nodes; 1165396Ssaidi@eecs.umich.edu 1175396Ssaidi@eecs.umich.edu // create the links in both directions 1185396Ssaidi@eecs.umich.edu addLink(a, b, p->latency, p->bw_multiplier, p->weight); 1195396Ssaidi@eecs.umich.edu addLink(b, a, p->latency, p->bw_multiplier, p->weight); 1205396Ssaidi@eecs.umich.edu } 1215396Ssaidi@eecs.umich.edu} 1225396Ssaidi@eecs.umich.edu 1235396Ssaidi@eecs.umich.edu 1245396Ssaidi@eecs.umich.eduvoid Topology::initNetworkPtr(Network* net_ptr) 1255396Ssaidi@eecs.umich.edu{ 1265396Ssaidi@eecs.umich.edu for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) 1275396Ssaidi@eecs.umich.edu { 1285396Ssaidi@eecs.umich.edu m_controller_vector[cntrl]->initNetworkPtr(net_ptr); 1295396Ssaidi@eecs.umich.edu } 1305396Ssaidi@eecs.umich.edu} 1315396Ssaidi@eecs.umich.edu 1325396Ssaidi@eecs.umich.edu 1335396Ssaidi@eecs.umich.eduvoid Topology::createLinks(Network *net, bool isReconfiguration) 1345396Ssaidi@eecs.umich.edu{ 1355396Ssaidi@eecs.umich.edu // Find maximum switchID 1365396Ssaidi@eecs.umich.edu 1375396Ssaidi@eecs.umich.edu SwitchID max_switch_id = 0; 1385396Ssaidi@eecs.umich.edu for (int i=0; i<m_links_src_vector.size(); i++) { 1395396Ssaidi@eecs.umich.edu max_switch_id = max(max_switch_id, m_links_src_vector[i]); 1405396Ssaidi@eecs.umich.edu max_switch_id = max(max_switch_id, m_links_dest_vector[i]); 1415396Ssaidi@eecs.umich.edu } 1425396Ssaidi@eecs.umich.edu 1435396Ssaidi@eecs.umich.edu // Initialize weight vector 1445396Ssaidi@eecs.umich.edu Matrix topology_weights; 1455396Ssaidi@eecs.umich.edu Matrix topology_latency; 1465396Ssaidi@eecs.umich.edu Matrix topology_bw_multis; 1475396Ssaidi@eecs.umich.edu int num_switches = max_switch_id+1; 1485396Ssaidi@eecs.umich.edu topology_weights.setSize(num_switches); 1495396Ssaidi@eecs.umich.edu topology_latency.setSize(num_switches); 1504781Snate@binkert.org topology_bw_multis.setSize(num_switches); 1511852SN/A m_component_latencies.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 152955SN/A m_component_inter_switches.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 153955SN/A for(int i=0; i<topology_weights.size(); i++) { 154955SN/A topology_weights[i].setSize(num_switches); 1553717Sstever@eecs.umich.edu topology_latency[i].setSize(num_switches); 1563716Sstever@eecs.umich.edu topology_bw_multis[i].setSize(num_switches); 157955SN/A m_component_latencies[i].setSize(num_switches); 1581533SN/A m_component_inter_switches[i].setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 1593716Sstever@eecs.umich.edu for(int j=0; j<topology_weights[i].size(); j++) { 1601533SN/A topology_weights[i][j] = INFINITE_LATENCY; 1614678Snate@binkert.org topology_latency[i][j] = -1; // initialize to an invalid value 1624678Snate@binkert.org topology_bw_multis[i][j] = -1; // initialize to an invalid value 1634678Snate@binkert.org m_component_latencies[i][j] = -1; // initialize to an invalid value 1644678Snate@binkert.org m_component_inter_switches[i][j] = 0; // initially assume direct connections / no intermediate switches between components 1654678Snate@binkert.org } 1664678Snate@binkert.org } 1674678Snate@binkert.org 1684678Snate@binkert.org // Set identity weights to zero 1694678Snate@binkert.org for(int i=0; i<topology_weights.size(); i++) { 1704678Snate@binkert.org topology_weights[i][i] = 0; 1714678Snate@binkert.org } 1724678Snate@binkert.org 1734678Snate@binkert.org // Fill in the topology weights and bandwidth multipliers 1744678Snate@binkert.org for (int i=0; i<m_links_src_vector.size(); i++) { 1754678Snate@binkert.org topology_weights[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_weight_vector[i]; 1764678Snate@binkert.org topology_latency[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; 1774678Snate@binkert.org m_component_latencies[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; // initialize to latency vector 1784678Snate@binkert.org topology_bw_multis[m_links_src_vector[i]][m_links_dest_vector[i]] = m_bw_multiplier_vector[i]; 1794678Snate@binkert.org } 1804678Snate@binkert.org 1814678Snate@binkert.org // Walk topology and hookup the links 1824973Ssaidi@eecs.umich.edu Matrix dist = shortest_path(topology_weights, m_component_latencies, m_component_inter_switches); 1834678Snate@binkert.org for(int i=0; i<topology_weights.size(); i++) { 1844678Snate@binkert.org for(int j=0; j<topology_weights[i].size(); j++) { 1854678Snate@binkert.org int weight = topology_weights[i][j]; 1864678Snate@binkert.org int bw_multiplier = topology_bw_multis[i][j]; 1874678Snate@binkert.org int latency = topology_latency[i][j]; 1884678Snate@binkert.org if (weight > 0 && weight != INFINITE_LATENCY) { 189955SN/A NetDest destination_set = shortest_path_to_node(i, j, topology_weights, dist); 190955SN/A assert(latency != -1); 1912632Sstever@eecs.umich.edu makeLink(net, i, j, destination_set, latency, weight, bw_multiplier, isReconfiguration); 1922632Sstever@eecs.umich.edu } 193955SN/A } 194955SN/A } 195955SN/A} 196955SN/A 1972632Sstever@eecs.umich.eduSwitchID Topology::newSwitchID() 198955SN/A{ 1992632Sstever@eecs.umich.edu m_number_of_switches++; 2002632Sstever@eecs.umich.edu return m_number_of_switches-1+m_nodes+m_nodes; 2012632Sstever@eecs.umich.edu} 2022632Sstever@eecs.umich.edu 2032632Sstever@eecs.umich.eduvoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency) 2042632Sstever@eecs.umich.edu{ 2052632Sstever@eecs.umich.edu addLink(src, dest, link_latency, DEFAULT_BW_MULTIPLIER, link_latency); 2062632Sstever@eecs.umich.edu} 2072632Sstever@eecs.umich.edu 2082632Sstever@eecs.umich.eduvoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier) 2092632Sstever@eecs.umich.edu{ 2102632Sstever@eecs.umich.edu addLink(src, dest, link_latency, bw_multiplier, link_latency); 2112632Sstever@eecs.umich.edu} 2123718Sstever@eecs.umich.edu 2133718Sstever@eecs.umich.eduvoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier, int link_weight) 2143718Sstever@eecs.umich.edu{ 2153718Sstever@eecs.umich.edu ASSERT(src <= m_number_of_switches+m_nodes+m_nodes); 2163718Sstever@eecs.umich.edu ASSERT(dest <= m_number_of_switches+m_nodes+m_nodes); 2173718Sstever@eecs.umich.edu m_links_src_vector.insertAtBottom(src); 2183718Sstever@eecs.umich.edu m_links_dest_vector.insertAtBottom(dest); 2193718Sstever@eecs.umich.edu m_links_latency_vector.insertAtBottom(link_latency); 2203718Sstever@eecs.umich.edu m_links_weight_vector.insertAtBottom(link_weight); 2213718Sstever@eecs.umich.edu m_bw_multiplier_vector.insertAtBottom(bw_multiplier); 2223718Sstever@eecs.umich.edu} 2233718Sstever@eecs.umich.edu 2243718Sstever@eecs.umich.eduvoid Topology::makeLink(Network *net, SwitchID src, SwitchID dest, const NetDest& routing_table_entry, int link_latency, int link_weight, int bw_multiplier, bool isReconfiguration) 2252634Sstever@eecs.umich.edu{ 2262634Sstever@eecs.umich.edu // Make sure we're not trying to connect two end-point nodes directly together 2272632Sstever@eecs.umich.edu assert((src >= 2*m_nodes) || (dest >= 2*m_nodes)); 2282638Sstever@eecs.umich.edu 2292632Sstever@eecs.umich.edu if (src < m_nodes) { 2302632Sstever@eecs.umich.edu net->makeInLink(src, dest-(2*m_nodes), routing_table_entry, link_latency, bw_multiplier, isReconfiguration); 2312632Sstever@eecs.umich.edu } else if (dest < 2*m_nodes) { 2322632Sstever@eecs.umich.edu assert(dest >= m_nodes); 2332632Sstever@eecs.umich.edu NodeID node = dest-m_nodes; 2342632Sstever@eecs.umich.edu net->makeOutLink(src-(2*m_nodes), node, routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 2351858SN/A } else { 2363716Sstever@eecs.umich.edu assert((src >= 2*m_nodes) && (dest >= 2*m_nodes)); 2372638Sstever@eecs.umich.edu net->makeInternalLink(src-(2*m_nodes), dest-(2*m_nodes), routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 2382638Sstever@eecs.umich.edu } 2392638Sstever@eecs.umich.edu} 2402638Sstever@eecs.umich.edu 2412638Sstever@eecs.umich.eduvoid Topology::printStats(ostream& out) const 2422638Sstever@eecs.umich.edu{ 2432638Sstever@eecs.umich.edu for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 2443716Sstever@eecs.umich.edu m_controller_vector[cntrl]->printStats(out); 2452634Sstever@eecs.umich.edu } 2462634Sstever@eecs.umich.edu} 247955SN/A 2485341Sstever@gmail.comvoid Topology::clearStats() 2495341Sstever@gmail.com{ 2505341Sstever@gmail.com for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 2515341Sstever@gmail.com m_controller_vector[cntrl]->clearStats(); 252955SN/A } 253955SN/A} 254955SN/A 255955SN/Avoid Topology::printConfig(ostream& out) const 256955SN/A{ 257955SN/A if (m_print_config == false) return; 258955SN/A 2591858SN/A assert(m_component_latencies.size() > 0); 2601858SN/A 2612632Sstever@eecs.umich.edu out << "--- Begin Topology Print ---" << endl; 262955SN/A out << endl; 2634494Ssaidi@eecs.umich.edu out << "Topology print ONLY indicates the _NETWORK_ latency between two machines" << endl; 2644494Ssaidi@eecs.umich.edu out << "It does NOT include the latency within the machines" << endl; 2653716Sstever@eecs.umich.edu out << endl; 2661105SN/A for (int m=0; m<MachineType_NUM; m++) { 2672667Sstever@eecs.umich.edu for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 2682667Sstever@eecs.umich.edu MachineID cur_mach = {(MachineType)m, i}; 2692667Sstever@eecs.umich.edu out << cur_mach << " Network Latencies" << endl; 2702667Sstever@eecs.umich.edu for (int n=0; n<MachineType_NUM; n++) { 2712667Sstever@eecs.umich.edu for (int j=0; j<MachineType_base_count((MachineType)n); j++) { 2722667Sstever@eecs.umich.edu MachineID dest_mach = {(MachineType)n, j}; 2731869SN/A if (cur_mach != dest_mach) { 2741869SN/A int link_latency = m_component_latencies[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 2751869SN/A int intermediate_switches = m_component_inter_switches[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 2761869SN/A out << " " << cur_mach << " -> " << dest_mach << " net_lat: " 2771869SN/A << link_latency+intermediate_switches << endl; // NOTE switches are assumed to have single cycle latency 2781065SN/A } 2795341Sstever@gmail.com } 2805341Sstever@gmail.com } 2815341Sstever@gmail.com out << endl; 2825341Sstever@gmail.com } 2835341Sstever@gmail.com } 2845341Sstever@gmail.com 2855341Sstever@gmail.com out << "--- End Topology Print ---" << endl; 2865341Sstever@gmail.com} 2875341Sstever@gmail.com 2885341Sstever@gmail.com/**************************************************************************/ 2895341Sstever@gmail.com 2905341Sstever@gmail.com// The following all-pairs shortest path algorithm is based on the 2915341Sstever@gmail.com// discussion from Cormen et al., Chapter 26.1. 2925341Sstever@gmail.com 2935341Sstever@gmail.comstatic void extend_shortest_path(Matrix& current_dist, Matrix& latencies, Matrix& inter_switches) 2945341Sstever@gmail.com{ 2955341Sstever@gmail.com bool change = true; 2965341Sstever@gmail.com int nodes = current_dist.size(); 2975341Sstever@gmail.com 2985341Sstever@gmail.com while (change) { 2995341Sstever@gmail.com change = false; 3005341Sstever@gmail.com for (int i=0; i<nodes; i++) { 3015341Sstever@gmail.com for (int j=0; j<nodes; j++) { 3025341Sstever@gmail.com int minimum = current_dist[i][j]; 3035341Sstever@gmail.com int previous_minimum = minimum; 3045341Sstever@gmail.com int intermediate_switch = -1; 3055341Sstever@gmail.com for (int k=0; k<nodes; k++) { 3065341Sstever@gmail.com minimum = min(minimum, current_dist[i][k] + current_dist[k][j]); 3075341Sstever@gmail.com if (previous_minimum != minimum) { 3085341Sstever@gmail.com intermediate_switch = k; 3095341Sstever@gmail.com inter_switches[i][j] = inter_switches[i][k] + inter_switches[k][j] + 1; 3105341Sstever@gmail.com } 3115341Sstever@gmail.com previous_minimum = minimum; 3125341Sstever@gmail.com } 3135341Sstever@gmail.com if (current_dist[i][j] != minimum) { 3145341Sstever@gmail.com change = true; 3155341Sstever@gmail.com current_dist[i][j] = minimum; 3165341Sstever@gmail.com assert(intermediate_switch >= 0); 3175341Sstever@gmail.com assert(intermediate_switch < latencies[i].size()); 3185341Sstever@gmail.com latencies[i][j] = latencies[i][intermediate_switch] + latencies[intermediate_switch][j]; 3195341Sstever@gmail.com } 3205341Sstever@gmail.com } 3215341Sstever@gmail.com } 3225341Sstever@gmail.com } 3235341Sstever@gmail.com} 3245341Sstever@gmail.com 3255341Sstever@gmail.comstatic Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches) 3265341Sstever@gmail.com{ 3275341Sstever@gmail.com Matrix dist = weights; 3285344Sstever@gmail.com extend_shortest_path(dist, latencies, inter_switches); 3295341Sstever@gmail.com return dist; 3305341Sstever@gmail.com} 3315341Sstever@gmail.com 3325341Sstever@gmail.comstatic bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, 3335341Sstever@gmail.com const Matrix& weights, const Matrix& dist) 3342632Sstever@eecs.umich.edu{ 3355199Sstever@gmail.com return (weights[src][next] + dist[next][final] == dist[src][final]); 3363918Ssaidi@eecs.umich.edu} 3373918Ssaidi@eecs.umich.edu 3383940Ssaidi@eecs.umich.edustatic NetDest shortest_path_to_node(SwitchID src, SwitchID next, 3394781Snate@binkert.org const Matrix& weights, const Matrix& dist) 3404781Snate@binkert.org{ 3413918Ssaidi@eecs.umich.edu NetDest result; 3424781Snate@binkert.org int d = 0; 3434781Snate@binkert.org int machines; 3443918Ssaidi@eecs.umich.edu int max_machines; 3454781Snate@binkert.org 3464781Snate@binkert.org machines = MachineType_NUM; 3473940Ssaidi@eecs.umich.edu max_machines = MachineType_base_number(MachineType_NUM); 3483942Ssaidi@eecs.umich.edu 3493940Ssaidi@eecs.umich.edu for (int m=0; m<machines; m++) { 3503918Ssaidi@eecs.umich.edu for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 3513918Ssaidi@eecs.umich.edu // we use "d+max_machines" below since the "destination" switches for the machines are numbered 352955SN/A // [MachineType_base_number(MachineType_NUM)...2*MachineType_base_number(MachineType_NUM)-1] 3531858SN/A // for the component network 3543918Ssaidi@eecs.umich.edu if (link_is_shortest_path_to_node(src, next, 3553918Ssaidi@eecs.umich.edu d+max_machines, 3563918Ssaidi@eecs.umich.edu weights, dist)) { 3573918Ssaidi@eecs.umich.edu MachineID mach = {(MachineType)m, i}; 3583940Ssaidi@eecs.umich.edu result.add(mach); 3593940Ssaidi@eecs.umich.edu } 3603918Ssaidi@eecs.umich.edu d++; 3613918Ssaidi@eecs.umich.edu } 3623918Ssaidi@eecs.umich.edu } 3633918Ssaidi@eecs.umich.edu 3643918Ssaidi@eecs.umich.edu DEBUG_MSG(NETWORK_COMP, MedPrio, "returning shortest path"); 3653918Ssaidi@eecs.umich.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, (src-(2*max_machines))); 3663918Ssaidi@eecs.umich.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, (next-(2*max_machines))); 3673918Ssaidi@eecs.umich.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, src); 3683918Ssaidi@eecs.umich.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, next); 3693940Ssaidi@eecs.umich.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, result); 3703918Ssaidi@eecs.umich.edu DEBUG_NEWLINE(NETWORK_COMP, MedPrio); 3713918Ssaidi@eecs.umich.edu 3721851SN/A return result; 3731851SN/A} 3741858SN/A 3755200Sstever@gmail.comTopology * 376955SN/ATopologyParams::create() 3773053Sstever@eecs.umich.edu{ 3783053Sstever@eecs.umich.edu return new Topology(this); 3793053Sstever@eecs.umich.edu} 3803053Sstever@eecs.umich.edu 3813053Sstever@eecs.umich.eduLink * 3823053Sstever@eecs.umich.eduLinkParams::create() 3833053Sstever@eecs.umich.edu{ 3843053Sstever@eecs.umich.edu return new Link(this); 3853053Sstever@eecs.umich.edu} 3864742Sstever@eecs.umich.edu 3874742Sstever@eecs.umich.eduExtLink * 3883053Sstever@eecs.umich.eduExtLinkParams::create() 3893053Sstever@eecs.umich.edu{ 3903053Sstever@eecs.umich.edu return new ExtLink(this); 3913053Sstever@eecs.umich.edu} 3923053Sstever@eecs.umich.edu 3933053Sstever@eecs.umich.eduIntLink * 3943053Sstever@eecs.umich.eduIntLinkParams::create() 3953053Sstever@eecs.umich.edu{ 3963053Sstever@eecs.umich.edu return new IntLink(this); 3972667Sstever@eecs.umich.edu} 3984554Sbinkertn@umich.edu