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