Topology.cc revision 6895
12810Srdreslin@umich.edu 212500Snikos.nikoleris@arm.com/* 311051Sandreas.hansson@arm.com * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 411051Sandreas.hansson@arm.com * All rights reserved. 511051Sandreas.hansson@arm.com * 611051Sandreas.hansson@arm.com * Redistribution and use in source and binary forms, with or without 711051Sandreas.hansson@arm.com * modification, are permitted provided that the following conditions are 811051Sandreas.hansson@arm.com * met: redistributions of source code must retain the above copyright 911051Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer; 1011051Sandreas.hansson@arm.com * redistributions in binary form must reproduce the above copyright 1111051Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer in the 1211051Sandreas.hansson@arm.com * documentation and/or other materials provided with the distribution; 1311051Sandreas.hansson@arm.com * neither the name of the copyright holders nor the names of its 1411051Sandreas.hansson@arm.com * contributors may be used to endorse or promote products derived from 1511051Sandreas.hansson@arm.com * this software without specific prior written permission. 162810Srdreslin@umich.edu * 172810Srdreslin@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 182810Srdreslin@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 192810Srdreslin@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 202810Srdreslin@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 212810Srdreslin@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 222810Srdreslin@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 232810Srdreslin@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 242810Srdreslin@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 252810Srdreslin@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 262810Srdreslin@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 272810Srdreslin@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 282810Srdreslin@umich.edu */ 292810Srdreslin@umich.edu 302810Srdreslin@umich.edu/* 312810Srdreslin@umich.edu * Topology.cc 322810Srdreslin@umich.edu * 332810Srdreslin@umich.edu * Description: See Topology.hh 342810Srdreslin@umich.edu * 352810Srdreslin@umich.edu * $Id$ 362810Srdreslin@umich.edu * 372810Srdreslin@umich.edu * */ 382810Srdreslin@umich.edu 392810Srdreslin@umich.edu#include "mem/ruby/network/simple/Topology.hh" 402810Srdreslin@umich.edu#include "mem/ruby/common/NetDest.hh" 412810Srdreslin@umich.edu#include "mem/ruby/network/Network.hh" 4211051Sandreas.hansson@arm.com#include "mem/ruby/slicc_interface/AbstractController.hh" 4311051Sandreas.hansson@arm.com#include "mem/protocol/TopologyType.hh" 442810Srdreslin@umich.edu#include "mem/gems_common/util.hh" 4511051Sandreas.hansson@arm.com#include "mem/protocol/MachineType.hh" 4611051Sandreas.hansson@arm.com#include "mem/protocol/Protocol.hh" 4712349Snikos.nikoleris@arm.com#include "mem/ruby/system/System.hh" 482810Srdreslin@umich.edu#include <string> 492810Srdreslin@umich.edu 502810Srdreslin@umich.edustatic const int INFINITE_LATENCY = 10000; // Yes, this is a big hack 512810Srdreslin@umich.edustatic const int DEFAULT_BW_MULTIPLIER = 1; // Just to be consistent with above :) 5211051Sandreas.hansson@arm.com 532810Srdreslin@umich.edu// Note: In this file, we use the first 2*m_nodes SwitchIDs to 542810Srdreslin@umich.edu// represent the input and output endpoint links. These really are 5511051Sandreas.hansson@arm.com// not 'switches', as they will not have a Switch object allocated for 562810Srdreslin@umich.edu// them. The first m_nodes SwitchIDs are the links into the network, 5712724Snikos.nikoleris@arm.com// the second m_nodes set of SwitchIDs represent the the output queues 5812724Snikos.nikoleris@arm.com// of the network. 5912724Snikos.nikoleris@arm.com 6012334Sgabeblack@google.com// Helper functions based on chapter 29 of Cormen et al. 6112724Snikos.nikoleris@arm.comstatic void extend_shortest_path(Matrix& current_dist, Matrix& latencies, Matrix& inter_switches); 6211051Sandreas.hansson@arm.comstatic Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches); 6311051Sandreas.hansson@arm.comstatic bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, const Matrix& weights, const Matrix& dist); 6411051Sandreas.hansson@arm.comstatic NetDest shortest_path_to_node(SwitchID src, SwitchID next, const Matrix& weights, const Matrix& dist); 6511288Ssteve.reinhardt@amd.com 6612724Snikos.nikoleris@arm.comTopology::Topology(const Params *p) 6711051Sandreas.hansson@arm.com : SimObject(p) 6811051Sandreas.hansson@arm.com{ 6912724Snikos.nikoleris@arm.com m_print_config = p->print_config; 7012724Snikos.nikoleris@arm.com m_number_of_switches = p->num_int_nodes; 7112724Snikos.nikoleris@arm.com // initialize component latencies record 7212724Snikos.nikoleris@arm.com m_component_latencies.setSize(0); 7311051Sandreas.hansson@arm.com m_component_inter_switches.setSize(0); 7411053Sandreas.hansson@arm.com 7511053Sandreas.hansson@arm.com // 7612724Snikos.nikoleris@arm.com // Total nodes/controllers in network 7711051Sandreas.hansson@arm.com // Must make sure this is called after the State Machine constructors 7811051Sandreas.hansson@arm.com // 7911051Sandreas.hansson@arm.com m_nodes = MachineType_base_number(MachineType_NUM); 8011051Sandreas.hansson@arm.com assert(m_nodes > 1); 8111601Sandreas.hansson@arm.com 8211601Sandreas.hansson@arm.com if (m_nodes != params()->ext_links.size()) { 8311051Sandreas.hansson@arm.com fatal("m_nodes (%d) != ext_links vector length (%d)\n", 8412724Snikos.nikoleris@arm.com m_nodes != params()->ext_links.size()); 8511051Sandreas.hansson@arm.com } 8612724Snikos.nikoleris@arm.com 8711600Sandreas.hansson@arm.com // 8811600Sandreas.hansson@arm.com // First create the links between the endpoints (i.e. controllers) and the 8911051Sandreas.hansson@arm.com // network. 9011051Sandreas.hansson@arm.com // 9111051Sandreas.hansson@arm.com for (vector<ExtLink*>::const_iterator i = params()->ext_links.begin(); 9211284Sandreas.hansson@arm.com i != params()->ext_links.end(); ++i) 9311051Sandreas.hansson@arm.com { 9411051Sandreas.hansson@arm.com const ExtLinkParams *p = (*i)->params(); 9511051Sandreas.hansson@arm.com AbstractController *c = p->ext_node; 9611602Sandreas.hansson@arm.com 9711051Sandreas.hansson@arm.com // Store the controller pointers for later 9811051Sandreas.hansson@arm.com m_controller_vector.insertAtBottom(c); 9911284Sandreas.hansson@arm.com 10011051Sandreas.hansson@arm.com int ext_idx1 = 10111284Sandreas.hansson@arm.com MachineType_base_number(c->getMachineType()) + c->getVersion(); 10211602Sandreas.hansson@arm.com int ext_idx2 = ext_idx1 + m_nodes; 10311051Sandreas.hansson@arm.com int int_idx = p->int_node + 2*m_nodes; 10411051Sandreas.hansson@arm.com 10511284Sandreas.hansson@arm.com // create the links in both directions 10611051Sandreas.hansson@arm.com addLink(ext_idx1, int_idx, p->latency, p->bw_multiplier, p->weight); 10711284Sandreas.hansson@arm.com addLink(int_idx, ext_idx2, p->latency, p->bw_multiplier, p->weight); 10811284Sandreas.hansson@arm.com } 10911284Sandreas.hansson@arm.com 11011051Sandreas.hansson@arm.com for (vector<IntLink*>::const_iterator i = params()->int_links.begin(); 11111051Sandreas.hansson@arm.com i != params()->int_links.end(); ++i) 11211051Sandreas.hansson@arm.com { 11311284Sandreas.hansson@arm.com const IntLinkParams *p = (*i)->params(); 11411284Sandreas.hansson@arm.com int a = p->node_a + 2*m_nodes; 11511284Sandreas.hansson@arm.com int b = p->node_b + 2*m_nodes; 11611284Sandreas.hansson@arm.com 11711051Sandreas.hansson@arm.com // create the links in both directions 11811051Sandreas.hansson@arm.com addLink(a, b, p->latency, p->bw_multiplier, p->weight); 11911051Sandreas.hansson@arm.com addLink(b, a, p->latency, p->bw_multiplier, p->weight); 12011284Sandreas.hansson@arm.com } 12111284Sandreas.hansson@arm.com} 12211284Sandreas.hansson@arm.com 12311197Sandreas.hansson@arm.com 12411601Sandreas.hansson@arm.comvoid Topology::initNetworkPtr(Network* net_ptr) 12511601Sandreas.hansson@arm.com{ 12611601Sandreas.hansson@arm.com for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) 12711601Sandreas.hansson@arm.com { 12811601Sandreas.hansson@arm.com m_controller_vector[cntrl]->initNetworkPtr(net_ptr); 12911601Sandreas.hansson@arm.com } 13011601Sandreas.hansson@arm.com} 13111601Sandreas.hansson@arm.com 13211197Sandreas.hansson@arm.com 13311601Sandreas.hansson@arm.comvoid Topology::createLinks(Network *net, bool isReconfiguration) 13411601Sandreas.hansson@arm.com{ 13511601Sandreas.hansson@arm.com // Find maximum switchID 13611601Sandreas.hansson@arm.com 13711601Sandreas.hansson@arm.com SwitchID max_switch_id = 0; 13811601Sandreas.hansson@arm.com for (int i=0; i<m_links_src_vector.size(); i++) { 13911601Sandreas.hansson@arm.com max_switch_id = max(max_switch_id, m_links_src_vector[i]); 14011051Sandreas.hansson@arm.com max_switch_id = max(max_switch_id, m_links_dest_vector[i]); 14111051Sandreas.hansson@arm.com } 14211051Sandreas.hansson@arm.com 14311051Sandreas.hansson@arm.com // Initialize weight vector 14411051Sandreas.hansson@arm.com Matrix topology_weights; 14511284Sandreas.hansson@arm.com Matrix topology_latency; 14611284Sandreas.hansson@arm.com Matrix topology_bw_multis; 14711051Sandreas.hansson@arm.com int num_switches = max_switch_id+1; 14811051Sandreas.hansson@arm.com topology_weights.setSize(num_switches); 14911051Sandreas.hansson@arm.com topology_latency.setSize(num_switches); 15011051Sandreas.hansson@arm.com topology_bw_multis.setSize(num_switches); 15111284Sandreas.hansson@arm.com m_component_latencies.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 15211051Sandreas.hansson@arm.com m_component_inter_switches.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 15311051Sandreas.hansson@arm.com for(int i=0; i<topology_weights.size(); i++) { 15411051Sandreas.hansson@arm.com topology_weights[i].setSize(num_switches); 15511051Sandreas.hansson@arm.com topology_latency[i].setSize(num_switches); 15611051Sandreas.hansson@arm.com topology_bw_multis[i].setSize(num_switches); 15711051Sandreas.hansson@arm.com m_component_latencies[i].setSize(num_switches); 15811051Sandreas.hansson@arm.com m_component_inter_switches[i].setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 15911051Sandreas.hansson@arm.com for(int j=0; j<topology_weights[i].size(); j++) { 16011051Sandreas.hansson@arm.com topology_weights[i][j] = INFINITE_LATENCY; 16111051Sandreas.hansson@arm.com topology_latency[i][j] = -1; // initialize to an invalid value 16211051Sandreas.hansson@arm.com topology_bw_multis[i][j] = -1; // initialize to an invalid value 16311051Sandreas.hansson@arm.com m_component_latencies[i][j] = -1; // initialize to an invalid value 16411051Sandreas.hansson@arm.com m_component_inter_switches[i][j] = 0; // initially assume direct connections / no intermediate switches between components 16511051Sandreas.hansson@arm.com } 16611051Sandreas.hansson@arm.com } 16711051Sandreas.hansson@arm.com 16811051Sandreas.hansson@arm.com // Set identity weights to zero 16912724Snikos.nikoleris@arm.com for(int i=0; i<topology_weights.size(); i++) { 17012724Snikos.nikoleris@arm.com topology_weights[i][i] = 0; 17112724Snikos.nikoleris@arm.com } 17212724Snikos.nikoleris@arm.com 17312724Snikos.nikoleris@arm.com // Fill in the topology weights and bandwidth multipliers 17412724Snikos.nikoleris@arm.com for (int i=0; i<m_links_src_vector.size(); i++) { 17512724Snikos.nikoleris@arm.com topology_weights[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_weight_vector[i]; 17611051Sandreas.hansson@arm.com topology_latency[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; 17711051Sandreas.hansson@arm.com m_component_latencies[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; // initialize to latency vector 17811051Sandreas.hansson@arm.com topology_bw_multis[m_links_src_vector[i]][m_links_dest_vector[i]] = m_bw_multiplier_vector[i]; 17911051Sandreas.hansson@arm.com } 18012723Snikos.nikoleris@arm.com 18111051Sandreas.hansson@arm.com // Walk topology and hookup the links 18211051Sandreas.hansson@arm.com Matrix dist = shortest_path(topology_weights, m_component_latencies, m_component_inter_switches); 18311484Snikos.nikoleris@arm.com for(int i=0; i<topology_weights.size(); i++) { 18411051Sandreas.hansson@arm.com for(int j=0; j<topology_weights[i].size(); j++) { 18511051Sandreas.hansson@arm.com int weight = topology_weights[i][j]; 18611051Sandreas.hansson@arm.com int bw_multiplier = topology_bw_multis[i][j]; 18711051Sandreas.hansson@arm.com int latency = topology_latency[i][j]; 18811051Sandreas.hansson@arm.com if (weight > 0 && weight != INFINITE_LATENCY) { 18912724Snikos.nikoleris@arm.com NetDest destination_set = shortest_path_to_node(i, j, topology_weights, dist); 19011601Sandreas.hansson@arm.com assert(latency != -1); 19111601Sandreas.hansson@arm.com makeLink(net, i, j, destination_set, latency, weight, bw_multiplier, isReconfiguration); 19211601Sandreas.hansson@arm.com } 19311051Sandreas.hansson@arm.com } 19411051Sandreas.hansson@arm.com } 19511051Sandreas.hansson@arm.com} 19611051Sandreas.hansson@arm.com 19711051Sandreas.hansson@arm.comSwitchID Topology::newSwitchID() 19812345Snikos.nikoleris@arm.com{ 19912345Snikos.nikoleris@arm.com m_number_of_switches++; 20012345Snikos.nikoleris@arm.com return m_number_of_switches-1+m_nodes+m_nodes; 20112345Snikos.nikoleris@arm.com} 20211051Sandreas.hansson@arm.com 20311051Sandreas.hansson@arm.comvoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency) 20411051Sandreas.hansson@arm.com{ 20511051Sandreas.hansson@arm.com addLink(src, dest, link_latency, DEFAULT_BW_MULTIPLIER, link_latency); 20611051Sandreas.hansson@arm.com} 20711051Sandreas.hansson@arm.com 20811051Sandreas.hansson@arm.comvoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier) 20911199Sandreas.hansson@arm.com{ 21011199Sandreas.hansson@arm.com addLink(src, dest, link_latency, bw_multiplier, link_latency); 21111199Sandreas.hansson@arm.com} 21211199Sandreas.hansson@arm.com 21311199Sandreas.hansson@arm.comvoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier, int link_weight) 21411051Sandreas.hansson@arm.com{ 21512345Snikos.nikoleris@arm.com ASSERT(src <= m_number_of_switches+m_nodes+m_nodes); 21612345Snikos.nikoleris@arm.com ASSERT(dest <= m_number_of_switches+m_nodes+m_nodes); 21711051Sandreas.hansson@arm.com m_links_src_vector.insertAtBottom(src); 21811051Sandreas.hansson@arm.com m_links_dest_vector.insertAtBottom(dest); 21911051Sandreas.hansson@arm.com m_links_latency_vector.insertAtBottom(link_latency); 22011051Sandreas.hansson@arm.com m_links_weight_vector.insertAtBottom(link_weight); 22111051Sandreas.hansson@arm.com m_bw_multiplier_vector.insertAtBottom(bw_multiplier); 22211051Sandreas.hansson@arm.com} 22311051Sandreas.hansson@arm.com 22411051Sandreas.hansson@arm.comvoid Topology::makeLink(Network *net, SwitchID src, SwitchID dest, const NetDest& routing_table_entry, int link_latency, int link_weight, int bw_multiplier, bool isReconfiguration) 22511051Sandreas.hansson@arm.com{ 22611051Sandreas.hansson@arm.com // Make sure we're not trying to connect two end-point nodes directly together 22711051Sandreas.hansson@arm.com assert((src >= 2*m_nodes) || (dest >= 2*m_nodes)); 22811051Sandreas.hansson@arm.com 22911051Sandreas.hansson@arm.com if (src < m_nodes) { 23011051Sandreas.hansson@arm.com net->makeInLink(src, dest-(2*m_nodes), routing_table_entry, link_latency, bw_multiplier, isReconfiguration); 23111051Sandreas.hansson@arm.com } else if (dest < 2*m_nodes) { 23211051Sandreas.hansson@arm.com assert(dest >= m_nodes); 23311051Sandreas.hansson@arm.com NodeID node = dest-m_nodes; 23411130Sali.jafri@arm.com net->makeOutLink(src-(2*m_nodes), node, routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 23511130Sali.jafri@arm.com } else { 23611130Sali.jafri@arm.com assert((src >= 2*m_nodes) && (dest >= 2*m_nodes)); 23711130Sali.jafri@arm.com net->makeInternalLink(src-(2*m_nodes), dest-(2*m_nodes), routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 23811130Sali.jafri@arm.com } 23911130Sali.jafri@arm.com} 24011130Sali.jafri@arm.com 24111130Sali.jafri@arm.comvoid Topology::printStats(ostream& out) const 24211130Sali.jafri@arm.com{ 24312345Snikos.nikoleris@arm.com for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 24412345Snikos.nikoleris@arm.com m_controller_vector[cntrl]->printStats(out); 24511130Sali.jafri@arm.com } 24611130Sali.jafri@arm.com} 24711130Sali.jafri@arm.com 24811130Sali.jafri@arm.comvoid Topology::clearStats() 24911130Sali.jafri@arm.com{ 25011130Sali.jafri@arm.com for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 25112724Snikos.nikoleris@arm.com m_controller_vector[cntrl]->clearStats(); 25211130Sali.jafri@arm.com } 25311130Sali.jafri@arm.com} 25411130Sali.jafri@arm.com 25511130Sali.jafri@arm.comvoid Topology::printConfig(ostream& out) const 25611130Sali.jafri@arm.com{ 25711130Sali.jafri@arm.com if (m_print_config == false) return; 25812724Snikos.nikoleris@arm.com 25911130Sali.jafri@arm.com assert(m_component_latencies.size() > 0); 26011130Sali.jafri@arm.com 26111130Sali.jafri@arm.com out << "--- Begin Topology Print ---" << endl; 26211130Sali.jafri@arm.com out << endl; 26311130Sali.jafri@arm.com out << "Topology print ONLY indicates the _NETWORK_ latency between two machines" << endl; 26411130Sali.jafri@arm.com out << "It does NOT include the latency within the machines" << endl; 26511130Sali.jafri@arm.com out << endl; 26611130Sali.jafri@arm.com for (int m=0; m<MachineType_NUM; m++) { 26711130Sali.jafri@arm.com for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 26811051Sandreas.hansson@arm.com MachineID cur_mach = {(MachineType)m, i}; 26911051Sandreas.hansson@arm.com out << cur_mach << " Network Latencies" << endl; 27011051Sandreas.hansson@arm.com for (int n=0; n<MachineType_NUM; n++) { 27111051Sandreas.hansson@arm.com for (int j=0; j<MachineType_base_count((MachineType)n); j++) { 27211744Snikos.nikoleris@arm.com MachineID dest_mach = {(MachineType)n, j}; 27311051Sandreas.hansson@arm.com if (cur_mach != dest_mach) { 27411276Sandreas.hansson@arm.com int link_latency = m_component_latencies[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 27511276Sandreas.hansson@arm.com int intermediate_switches = m_component_inter_switches[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 27611276Sandreas.hansson@arm.com out << " " << cur_mach << " -> " << dest_mach << " net_lat: " 27711276Sandreas.hansson@arm.com << link_latency+intermediate_switches << endl; // NOTE switches are assumed to have single cycle latency 27811276Sandreas.hansson@arm.com } 27911276Sandreas.hansson@arm.com } 28011276Sandreas.hansson@arm.com } 28111276Sandreas.hansson@arm.com out << endl; 28211276Sandreas.hansson@arm.com } 28311051Sandreas.hansson@arm.com } 28411276Sandreas.hansson@arm.com 28511276Sandreas.hansson@arm.com out << "--- End Topology Print ---" << endl; 28611276Sandreas.hansson@arm.com} 28711276Sandreas.hansson@arm.com 28811276Sandreas.hansson@arm.com/**************************************************************************/ 28911051Sandreas.hansson@arm.com 29011051Sandreas.hansson@arm.com// The following all-pairs shortest path algorithm is based on the 29111051Sandreas.hansson@arm.com// discussion from Cormen et al., Chapter 26.1. 29211051Sandreas.hansson@arm.com 29311051Sandreas.hansson@arm.comstatic void extend_shortest_path(Matrix& current_dist, Matrix& latencies, Matrix& inter_switches) 29411051Sandreas.hansson@arm.com{ 29511051Sandreas.hansson@arm.com bool change = true; 29611051Sandreas.hansson@arm.com int nodes = current_dist.size(); 29711051Sandreas.hansson@arm.com 29811051Sandreas.hansson@arm.com while (change) { 29911051Sandreas.hansson@arm.com change = false; 30012724Snikos.nikoleris@arm.com for (int i=0; i<nodes; i++) { 30111051Sandreas.hansson@arm.com for (int j=0; j<nodes; j++) { 30211051Sandreas.hansson@arm.com int minimum = current_dist[i][j]; 30311051Sandreas.hansson@arm.com int previous_minimum = minimum; 30411051Sandreas.hansson@arm.com int intermediate_switch = -1; 30511051Sandreas.hansson@arm.com for (int k=0; k<nodes; k++) { 30611051Sandreas.hansson@arm.com minimum = min(minimum, current_dist[i][k] + current_dist[k][j]); 30711051Sandreas.hansson@arm.com if (previous_minimum != minimum) { 30811051Sandreas.hansson@arm.com intermediate_switch = k; 30911051Sandreas.hansson@arm.com inter_switches[i][j] = inter_switches[i][k] + inter_switches[k][j] + 1; 31011051Sandreas.hansson@arm.com } 31111051Sandreas.hansson@arm.com previous_minimum = minimum; 31211051Sandreas.hansson@arm.com } 31311051Sandreas.hansson@arm.com if (current_dist[i][j] != minimum) { 31412630Snikos.nikoleris@arm.com change = true; 31512720Snikos.nikoleris@arm.com current_dist[i][j] = minimum; 31612720Snikos.nikoleris@arm.com assert(intermediate_switch >= 0); 31712720Snikos.nikoleris@arm.com assert(intermediate_switch < latencies[i].size()); 31812720Snikos.nikoleris@arm.com latencies[i][j] = latencies[i][intermediate_switch] + latencies[intermediate_switch][j]; 31912720Snikos.nikoleris@arm.com } 32012720Snikos.nikoleris@arm.com } 32112720Snikos.nikoleris@arm.com } 32212724Snikos.nikoleris@arm.com } 32312720Snikos.nikoleris@arm.com} 32412720Snikos.nikoleris@arm.com 32512720Snikos.nikoleris@arm.comstatic Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches) 32612720Snikos.nikoleris@arm.com{ 32712720Snikos.nikoleris@arm.com Matrix dist = weights; 32812720Snikos.nikoleris@arm.com extend_shortest_path(dist, latencies, inter_switches); 32912724Snikos.nikoleris@arm.com return dist; 33012724Snikos.nikoleris@arm.com} 33112724Snikos.nikoleris@arm.com 33212724Snikos.nikoleris@arm.comstatic bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, 33312724Snikos.nikoleris@arm.com const Matrix& weights, const Matrix& dist) 33412724Snikos.nikoleris@arm.com{ 33512724Snikos.nikoleris@arm.com return (weights[src][next] + dist[next][final] == dist[src][final]); 33612724Snikos.nikoleris@arm.com} 33712724Snikos.nikoleris@arm.com 33812724Snikos.nikoleris@arm.comstatic NetDest shortest_path_to_node(SwitchID src, SwitchID next, 33912724Snikos.nikoleris@arm.com const Matrix& weights, const Matrix& dist) 34012724Snikos.nikoleris@arm.com{ 34112724Snikos.nikoleris@arm.com NetDest result; 34212724Snikos.nikoleris@arm.com int d = 0; 34312724Snikos.nikoleris@arm.com int machines; 34412724Snikos.nikoleris@arm.com int max_machines; 34512724Snikos.nikoleris@arm.com 34612724Snikos.nikoleris@arm.com machines = MachineType_NUM; 34712724Snikos.nikoleris@arm.com max_machines = MachineType_base_number(MachineType_NUM); 34812724Snikos.nikoleris@arm.com 34912724Snikos.nikoleris@arm.com for (int m=0; m<machines; m++) { 35012724Snikos.nikoleris@arm.com for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 35112724Snikos.nikoleris@arm.com // we use "d+max_machines" below since the "destination" switches for the machines are numbered 35212724Snikos.nikoleris@arm.com // [MachineType_base_number(MachineType_NUM)...2*MachineType_base_number(MachineType_NUM)-1] 35312724Snikos.nikoleris@arm.com // for the component network 35412720Snikos.nikoleris@arm.com if (link_is_shortest_path_to_node(src, next, 35512720Snikos.nikoleris@arm.com d+max_machines, 35612724Snikos.nikoleris@arm.com weights, dist)) { 35712720Snikos.nikoleris@arm.com MachineID mach = {(MachineType)m, i}; 35812720Snikos.nikoleris@arm.com result.add(mach); 35912720Snikos.nikoleris@arm.com } 36012720Snikos.nikoleris@arm.com d++; 36112720Snikos.nikoleris@arm.com } 36212720Snikos.nikoleris@arm.com } 36312720Snikos.nikoleris@arm.com 36412720Snikos.nikoleris@arm.com DEBUG_MSG(NETWORK_COMP, MedPrio, "returning shortest path"); 36512720Snikos.nikoleris@arm.com DEBUG_EXPR(NETWORK_COMP, MedPrio, (src-(2*max_machines))); 36612720Snikos.nikoleris@arm.com DEBUG_EXPR(NETWORK_COMP, MedPrio, (next-(2*max_machines))); 36712720Snikos.nikoleris@arm.com DEBUG_EXPR(NETWORK_COMP, MedPrio, src); 36812720Snikos.nikoleris@arm.com DEBUG_EXPR(NETWORK_COMP, MedPrio, next); 36912720Snikos.nikoleris@arm.com DEBUG_EXPR(NETWORK_COMP, MedPrio, result); 37012720Snikos.nikoleris@arm.com DEBUG_NEWLINE(NETWORK_COMP, MedPrio); 37112720Snikos.nikoleris@arm.com 37212720Snikos.nikoleris@arm.com return result; 37312720Snikos.nikoleris@arm.com} 37412720Snikos.nikoleris@arm.com 37512720Snikos.nikoleris@arm.comTopology * 37612720Snikos.nikoleris@arm.comTopologyParams::create() 37712720Snikos.nikoleris@arm.com{ 37812720Snikos.nikoleris@arm.com return new Topology(this); 37912720Snikos.nikoleris@arm.com} 38012749Sgiacomo.travaglini@arm.com 38112749Sgiacomo.travaglini@arm.comLink * 38212749Sgiacomo.travaglini@arm.comLinkParams::create() 38312749Sgiacomo.travaglini@arm.com{ 38412720Snikos.nikoleris@arm.com return new Link(this); 38512720Snikos.nikoleris@arm.com} 38612720Snikos.nikoleris@arm.com 38712720Snikos.nikoleris@arm.comExtLink * 38812720Snikos.nikoleris@arm.comExtLinkParams::create() 38912720Snikos.nikoleris@arm.com{ 39012720Snikos.nikoleris@arm.com return new ExtLink(this); 39112720Snikos.nikoleris@arm.com} 39212720Snikos.nikoleris@arm.com 39312720Snikos.nikoleris@arm.comIntLink * 39412724Snikos.nikoleris@arm.comIntLinkParams::create() 39512720Snikos.nikoleris@arm.com{ 39612720Snikos.nikoleris@arm.com return new IntLink(this); 39712720Snikos.nikoleris@arm.com} 39812720Snikos.nikoleris@arm.com