Topology.cc revision 6285
16145Snate@binkert.org 26145Snate@binkert.org/* 36145Snate@binkert.org * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 46145Snate@binkert.org * All rights reserved. 56145Snate@binkert.org * 66145Snate@binkert.org * Redistribution and use in source and binary forms, with or without 76145Snate@binkert.org * modification, are permitted provided that the following conditions are 86145Snate@binkert.org * met: redistributions of source code must retain the above copyright 96145Snate@binkert.org * notice, this list of conditions and the following disclaimer; 106145Snate@binkert.org * redistributions in binary form must reproduce the above copyright 116145Snate@binkert.org * notice, this list of conditions and the following disclaimer in the 126145Snate@binkert.org * documentation and/or other materials provided with the distribution; 136145Snate@binkert.org * neither the name of the copyright holders nor the names of its 146145Snate@binkert.org * contributors may be used to endorse or promote products derived from 156145Snate@binkert.org * this software without specific prior written permission. 166145Snate@binkert.org * 176145Snate@binkert.org * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 186145Snate@binkert.org * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 196145Snate@binkert.org * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 206145Snate@binkert.org * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 216145Snate@binkert.org * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 226145Snate@binkert.org * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 236145Snate@binkert.org * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 246145Snate@binkert.org * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 256145Snate@binkert.org * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 266145Snate@binkert.org * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 276145Snate@binkert.org * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 286145Snate@binkert.org */ 297054Snate@binkert.org 307054Snate@binkert.org/* 316145Snate@binkert.org * Topology.cc 327055Snate@binkert.org * 337454Snate@binkert.org * Description: See Topology.hh 347055Snate@binkert.org * 356154Snate@binkert.org * $Id$ 366154Snate@binkert.org * 376154Snate@binkert.org * */ 387054Snate@binkert.org 396876Ssteve.reinhardt@amd.com#include "mem/ruby/network/simple/Topology.hh" 406145Snate@binkert.org#include "mem/ruby/common/NetDest.hh" 416145Snate@binkert.org#include "mem/ruby/network/Network.hh" 426145Snate@binkert.org#include "mem/protocol/TopologyType.hh" 436145Snate@binkert.org//#include "mem/ruby/config/RubyConfig.hh" 446145Snate@binkert.org#include "mem/gems_common/util.hh" 456145Snate@binkert.org#include "mem/protocol/MachineType.hh" 466145Snate@binkert.org#include "mem/protocol/Protocol.hh" 477054Snate@binkert.org#include "mem/ruby/system/System.hh" 487054Snate@binkert.org#include <string> 497054Snate@binkert.org 506876Ssteve.reinhardt@amd.comstatic const int INFINITE_LATENCY = 10000; // Yes, this is a big hack 516876Ssteve.reinhardt@amd.comstatic const int DEFAULT_BW_MULTIPLIER = 1; // Just to be consistent with above :) 527054Snate@binkert.org 536145Snate@binkert.org// Note: In this file, we use the first 2*m_nodes SwitchIDs to 547054Snate@binkert.org// represent the input and output endpoint links. These really are 556145Snate@binkert.org// not 'switches', as they will not have a Switch object allocated for 567055Snate@binkert.org// them. The first m_nodes SwitchIDs are the links into the network, 577054Snate@binkert.org// the second m_nodes set of SwitchIDs represent the the output queues 587055Snate@binkert.org// of the network. 596285Snate@binkert.org 607054Snate@binkert.org// Helper functions based on chapter 29 of Cormen et al. 616145Snate@binkert.orgstatic Matrix extend_shortest_path(const Matrix& current_dist, Matrix& latencies, Matrix& inter_switches); 627054Snate@binkert.orgstatic Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches); 637054Snate@binkert.orgstatic bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, const Matrix& weights, const Matrix& dist); 647054Snate@binkert.orgstatic NetDest shortest_path_to_node(SwitchID src, SwitchID next, const Matrix& weights, const Matrix& dist); 657454Snate@binkert.org 666145Snate@binkert.orgTopology::Topology(const string & name) 677054Snate@binkert.org : m_name(name) 687054Snate@binkert.org{ 696145Snate@binkert.org m_network_ptr = NULL; 707054Snate@binkert.org m_nodes = MachineType_base_number(MachineType_NUM); 716145Snate@binkert.org m_number_of_switches = 0; 727054Snate@binkert.org} 738257SBrad.Beckmann@amd.com 748257SBrad.Beckmann@amd.comvoid Topology::init(const vector<string> & argv) 758257SBrad.Beckmann@amd.com{ 768257SBrad.Beckmann@amd.com for (size_t i=0; i<argv.size(); i+=2) { 778257SBrad.Beckmann@amd.com if (argv[i] == "network") 788257SBrad.Beckmann@amd.com m_network_ptr = RubySystem::getNetwork(); 798257SBrad.Beckmann@amd.com else if (argv[i] == "connections") 808257SBrad.Beckmann@amd.com m_connections = argv[i+1]; 818257SBrad.Beckmann@amd.com else if (argv[i] == "print_config") { 828257SBrad.Beckmann@amd.com m_print_config = string_to_bool(argv[i+1]); 838257SBrad.Beckmann@amd.com cerr << "print config: " << m_print_config << endl; 848257SBrad.Beckmann@amd.com } 856145Snate@binkert.org } 867055Snate@binkert.org assert(m_network_ptr != NULL); 876145Snate@binkert.org} 887054Snate@binkert.org 897054Snate@binkert.orgvoid Topology::makeTopology() 907054Snate@binkert.org{ 917054Snate@binkert.org /* 927054Snate@binkert.org if (m_nodes == 1) { 937054Snate@binkert.org SwitchID id = newSwitchID(); 947054Snate@binkert.org addLink(0, id, m_network_ptr->getOffChipLinkLatency()); 957054Snate@binkert.org addLink(id, 1, m_network_ptr->getOffChipLinkLatency()); 966145Snate@binkert.org return; 977054Snate@binkert.org } 987054Snate@binkert.org */ 997054Snate@binkert.org assert(m_nodes > 1); 1006145Snate@binkert.org 1017054Snate@binkert.org Vector< Vector < SwitchID > > nodePairs; // node pairs extracted from the file 1027454Snate@binkert.org Vector<int> latencies; // link latencies for each link extracted 1037454Snate@binkert.org Vector<int> bw_multis; // bw multipliers for each link extracted 1046145Snate@binkert.org Vector<int> weights; // link weights used to enfore e-cube deadlock free routing 1057454Snate@binkert.org Vector< SwitchID > int_network_switches; // internal switches extracted from the file 1067454Snate@binkert.org Vector<bool> endpointConnectionExist; // used to ensure all endpoints are connected to the network 1077454Snate@binkert.org 1087454Snate@binkert.org endpointConnectionExist.setSize(m_nodes); 1097454Snate@binkert.org 1106145Snate@binkert.org // initialize endpoint check vector 1116145Snate@binkert.org for (int k = 0; k < endpointConnectionExist.size(); k++) { 1127055Snate@binkert.org endpointConnectionExist[k] = false; 1137055Snate@binkert.org } 1146145Snate@binkert.org 1157054Snate@binkert.org stringstream networkFile( m_connections ); 1167055Snate@binkert.org 1177054Snate@binkert.org string line = ""; 1186145Snate@binkert.org 1196145Snate@binkert.org while (!networkFile.eof()) { 1207054Snate@binkert.org 121 Vector < SwitchID > nodes; 122 nodes.setSize(2); 123 int latency = -1; // null latency 124 int weight = -1; // null weight 125 int bw_multiplier = DEFAULT_BW_MULTIPLIER; // default multiplier incase the network file doesn't define it 126 int i = 0; // node pair index 127 int varsFound = 0; // number of varsFound on the line 128 int internalNodes = 0; // used to determine if the link is between 2 internal nodes 129 std::getline(networkFile, line, '\n'); 130 string varStr = string_split(line, ' '); 131 132 // parse the current line in the file 133 while (varStr != "") { 134 string label = string_split(varStr, ':'); 135 136 // valid node labels 137 if (label == "ext_node" || label == "int_node") { 138 ASSERT(i < 2); // one link between 2 switches per line 139 varsFound++; 140 bool isNewIntSwitch = true; 141 if (label == "ext_node") { // input link to node 142 MachineType machine = string_to_MachineType(string_split(varStr, ':')); 143 string nodeStr = string_split(varStr, ':'); 144 nodes[i] = MachineType_base_number(machine) 145 + atoi(nodeStr.c_str()); 146 147 // in nodes should be numbered 0 to m_nodes-1 148 ASSERT(nodes[i] >= 0 && nodes[i] < m_nodes); 149 isNewIntSwitch = false; 150 endpointConnectionExist[nodes[i]] = true; 151 } 152 if (label == "int_node") { // interior node 153 nodes[i] = atoi((string_split(varStr, ':')).c_str())+m_nodes*2; 154 // in nodes should be numbered >= m_nodes*2 155 ASSERT(nodes[i] >= m_nodes*2); 156 for (int k = 0; k < int_network_switches.size(); k++) { 157 if (int_network_switches[k] == nodes[i]) { 158 isNewIntSwitch = false; 159 } 160 } 161 if (isNewIntSwitch) { // if internal switch 162 m_number_of_switches++; 163 int_network_switches.insertAtBottom(nodes[i]); 164 } 165 internalNodes++; 166 } 167 i++; 168 } else if (label == "link_latency") { 169 latency = atoi((string_split(varStr, ':')).c_str()); 170 varsFound++; 171 } else if (label == "bw_multiplier") { // not necessary, defaults to DEFAULT_BW_MULTIPLIER 172 bw_multiplier = atoi((string_split(varStr, ':')).c_str()); 173 } else if (label == "link_weight") { // not necessary, defaults to link_latency 174 weight = atoi((string_split(varStr, ':')).c_str()); 175 } else { 176 cerr << "Error: Unexpected Identifier: " << label << endl; 177 exit(1); 178 } 179 varStr = string_split(line, ' '); 180 } 181 if (varsFound == 3) { // all three necessary link variables where found so add the link 182 nodePairs.insertAtBottom(nodes); 183 latencies.insertAtBottom(latency); 184 if (weight != -1) { 185 weights.insertAtBottom(weight); 186 } else { 187 weights.insertAtBottom(latency); 188 } 189 bw_multis.insertAtBottom(bw_multiplier); 190 Vector < SwitchID > otherDirectionNodes; 191 otherDirectionNodes.setSize(2); 192 otherDirectionNodes[0] = nodes[1]; 193 if (internalNodes == 2) { // this is an internal link 194 otherDirectionNodes[1] = nodes[0]; 195 } else { 196 otherDirectionNodes[1] = nodes[0]+m_nodes; 197 } 198 nodePairs.insertAtBottom(otherDirectionNodes); 199 latencies.insertAtBottom(latency); 200 if (weight != -1) { 201 weights.insertAtBottom(weight); 202 } else { 203 weights.insertAtBottom(latency); 204 } 205 bw_multis.insertAtBottom(bw_multiplier); 206 } else { 207 if (varsFound != 0) { // if this is not a valid link, then no vars should have been found 208 cerr << "Error in line: " << line << endl; 209 exit(1); 210 } 211 } 212 } // end of file 213 214 // makes sure all enpoints are connected in the soon to be created network 215 for (int k = 0; k < endpointConnectionExist.size(); k++) { 216 if (endpointConnectionExist[k] == false) { 217 cerr << "Error: Unconnected Endpoint: " << k << endl; 218 exit(1); 219 } 220 } 221 222 ASSERT(nodePairs.size() == latencies.size() && latencies.size() == bw_multis.size() && latencies.size() == weights.size()) 223 for (int k = 0; k < nodePairs.size(); k++) { 224 ASSERT(nodePairs[k].size() == 2); 225 addLink(nodePairs[k][0], nodePairs[k][1], latencies[k], bw_multis[k], weights[k]); 226 } 227 228 // initialize component latencies record 229 m_component_latencies.setSize(0); 230 m_component_inter_switches.setSize(0); 231} 232 233 234void Topology::createLinks(bool isReconfiguration) 235{ 236 // Find maximum switchID 237 238 SwitchID max_switch_id = 0; 239 for (int i=0; i<m_links_src_vector.size(); i++) { 240 max_switch_id = max(max_switch_id, m_links_src_vector[i]); 241 max_switch_id = max(max_switch_id, m_links_dest_vector[i]); 242 } 243 244 // Initialize weight vector 245 Matrix topology_weights; 246 Matrix topology_latency; 247 Matrix topology_bw_multis; 248 int num_switches = max_switch_id+1; 249 topology_weights.setSize(num_switches); 250 topology_latency.setSize(num_switches); 251 topology_bw_multis.setSize(num_switches); 252 m_component_latencies.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 253 m_component_inter_switches.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 254 for(int i=0; i<topology_weights.size(); i++) { 255 topology_weights[i].setSize(num_switches); 256 topology_latency[i].setSize(num_switches); 257 topology_bw_multis[i].setSize(num_switches); 258 m_component_latencies[i].setSize(num_switches); 259 m_component_inter_switches[i].setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 260 for(int j=0; j<topology_weights[i].size(); j++) { 261 topology_weights[i][j] = INFINITE_LATENCY; 262 topology_latency[i][j] = -1; // initialize to an invalid value 263 topology_bw_multis[i][j] = -1; // initialize to an invalid value 264 m_component_latencies[i][j] = -1; // initialize to an invalid value 265 m_component_inter_switches[i][j] = 0; // initially assume direct connections / no intermediate switches between components 266 } 267 } 268 269 // Set identity weights to zero 270 for(int i=0; i<topology_weights.size(); i++) { 271 topology_weights[i][i] = 0; 272 } 273 274 // Fill in the topology weights and bandwidth multipliers 275 for (int i=0; i<m_links_src_vector.size(); i++) { 276 topology_weights[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_weight_vector[i]; 277 topology_latency[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; 278 m_component_latencies[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; // initialize to latency vector 279 topology_bw_multis[m_links_src_vector[i]][m_links_dest_vector[i]] = m_bw_multiplier_vector[i]; 280 } 281 282 // Walk topology and hookup the links 283 Matrix dist = shortest_path(topology_weights, m_component_latencies, m_component_inter_switches); 284 for(int i=0; i<topology_weights.size(); i++) { 285 for(int j=0; j<topology_weights[i].size(); j++) { 286 int weight = topology_weights[i][j]; 287 int bw_multiplier = topology_bw_multis[i][j]; 288 int latency = topology_latency[i][j]; 289 if (weight > 0 && weight != INFINITE_LATENCY) { 290 NetDest destination_set = shortest_path_to_node(i, j, topology_weights, dist); 291 assert(latency != -1); 292 makeLink(i, j, destination_set, latency, weight, bw_multiplier, isReconfiguration); 293 } 294 } 295 } 296} 297/* 298void Topology::makeSwitchesPerChip(Vector< Vector < SwitchID > > &nodePairs, Vector<int> &latencies, Vector<int> &bw_multis, int numberOfChipSwitches) 299{ 300 301 Vector < SwitchID > nodes; // temporary buffer 302 nodes.setSize(2); 303 304 Vector<bool> endpointConnectionExist; // used to ensure all endpoints are connected to the network 305 endpointConnectionExist.setSize(m_nodes); 306 // initialize endpoint check vector 307 for (int k = 0; k < endpointConnectionExist.size(); k++) { 308 endpointConnectionExist[k] = false; 309 } 310 311 Vector<int> componentCount; 312 componentCount.setSize(MachineType_NUM); 313 for (MachineType mType = MachineType_FIRST; mType < MachineType_NUM; ++mType) { 314 componentCount[mType] = 0; 315 } 316 317 // components to/from network links 318 // TODO: drh5: bring back chips!!! 319 for (int chip = 0; chip < RubyConfig::getNumberOfChips(); chip++) { 320 for (MachineType mType = MachineType_FIRST; mType < MachineType_NUM; ++mType) { 321 for (int component = 0; component < MachineType_base_count(mType); component++) { 322 323 int latency = -1; 324 int bw_multiplier = -1; // internal link bw multiplier of the global bandwidth 325 if (mType != MachineType_Directory) { 326 latency = RubyConfig::getOnChipLinkLatency(); // internal link latency 327 bw_multiplier = 10; // internal link bw multiplier of the global bandwidth 328 } else { 329 latency = RubyConfig::getNetworkLinkLatency(); // local memory latency 330 bw_multiplier = 1; // local memory link bw multiplier of the global bandwidth 331 } 332 nodes[0] = MachineType_base_number(mType)+componentCount[mType]; 333 nodes[1] = chip+m_nodes*2; // this is the chip's internal switch id # 334 335 // insert link 336 nodePairs.insertAtBottom(nodes); 337 latencies.insertAtBottom(latency); 338 bw_multis.insertAtBottom(bw_multiplier); 339 //bw_multis.insertAtBottom(componentCount[mType]+MachineType_base_number((MachineType)mType)); 340 341 // opposite direction link 342 Vector < SwitchID > otherDirectionNodes; 343 otherDirectionNodes.setSize(2); 344 otherDirectionNodes[0] = nodes[1]; 345 otherDirectionNodes[1] = nodes[0]+m_nodes; 346 nodePairs.insertAtBottom(otherDirectionNodes); 347 latencies.insertAtBottom(latency); 348 bw_multis.insertAtBottom(bw_multiplier); 349 350 assert(!endpointConnectionExist[nodes[0]]); 351 endpointConnectionExist[nodes[0]] = true; 352 componentCount[mType]++; 353 } 354 } 355 } 356 357 // make sure all enpoints are connected in the soon to be created network 358 for (int k = 0; k < endpointConnectionExist.size(); k++) { 359 if (endpointConnectionExist[k] == false) { 360 cerr << "Error: Unconnected Endpoint: " << k << endl; 361 exit(1); 362 } 363 } 364 365 // secondary check to ensure we saw the correct machine counts 366 for (MachineType mType = MachineType_FIRST; mType < MachineType_NUM; ++mType) { 367 assert(componentCount[mType] == MachineType_base_count((MachineType)mType)); 368 } 369 370} 371*/ 372 373 374SwitchID Topology::newSwitchID() 375{ 376 m_number_of_switches++; 377 return m_number_of_switches-1+m_nodes+m_nodes; 378} 379 380void Topology::addLink(SwitchID src, SwitchID dest, int link_latency) 381{ 382 addLink(src, dest, link_latency, DEFAULT_BW_MULTIPLIER, link_latency); 383} 384 385void Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier) 386{ 387 addLink(src, dest, link_latency, bw_multiplier, link_latency); 388} 389 390void Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier, int link_weight) 391{ 392 ASSERT(src <= m_number_of_switches+m_nodes+m_nodes); 393 ASSERT(dest <= m_number_of_switches+m_nodes+m_nodes); 394 m_links_src_vector.insertAtBottom(src); 395 m_links_dest_vector.insertAtBottom(dest); 396 m_links_latency_vector.insertAtBottom(link_latency); 397 m_links_weight_vector.insertAtBottom(link_weight); 398 m_bw_multiplier_vector.insertAtBottom(bw_multiplier); 399} 400 401void Topology::makeLink(SwitchID src, SwitchID dest, const NetDest& routing_table_entry, int link_latency, int link_weight, int bw_multiplier, bool isReconfiguration) 402{ 403 // Make sure we're not trying to connect two end-point nodes directly together 404 assert((src >= 2*m_nodes) || (dest >= 2*m_nodes)); 405 406 if (src < m_nodes) { 407 m_network_ptr->makeInLink(src, dest-(2*m_nodes), routing_table_entry, link_latency, bw_multiplier, isReconfiguration); 408 } else if (dest < 2*m_nodes) { 409 assert(dest >= m_nodes); 410 NodeID node = dest-m_nodes; 411 m_network_ptr->makeOutLink(src-(2*m_nodes), node, routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 412 } else { 413 assert((src >= 2*m_nodes) && (dest >= 2*m_nodes)); 414 m_network_ptr->makeInternalLink(src-(2*m_nodes), dest-(2*m_nodes), routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 415 } 416} 417 418void Topology::printConfig(ostream& out) const 419{ 420 if (m_print_config == false) return; 421 422 assert(m_component_latencies.size() > 0); 423 424 out << "--- Begin Topology Print ---" << endl; 425 out << endl; 426 out << "Topology print ONLY indicates the _NETWORK_ latency between two machines" << endl; 427 out << "It does NOT include the latency within the machines" << endl; 428 out << endl; 429 for (int m=0; m<MachineType_NUM; m++) { 430 for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 431 MachineID cur_mach = {(MachineType)m, i}; 432 out << cur_mach << " Network Latencies" << endl; 433 for (int n=0; n<MachineType_NUM; n++) { 434 for (int j=0; j<MachineType_base_count((MachineType)n); j++) { 435 MachineID dest_mach = {(MachineType)n, j}; 436 if (cur_mach != dest_mach) { 437 int link_latency = m_component_latencies[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 438 int intermediate_switches = m_component_inter_switches[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 439 out << " " << cur_mach << " -> " << dest_mach << " net_lat: " 440 << link_latency+intermediate_switches << endl; // NOTE switches are assumed to have single cycle latency 441 } 442 } 443 } 444 out << endl; 445 } 446 } 447 448 out << "--- End Topology Print ---" << endl; 449} 450 451/**************************************************************************/ 452 453// The following all-pairs shortest path algorithm is based on the 454// discussion from Cormen et al., Chapter 26.1. 455 456static void extend_shortest_path(Matrix& current_dist, Matrix& latencies, Matrix& inter_switches) 457{ 458 bool change = true; 459 int nodes = current_dist.size(); 460 461 while (change) { 462 change = false; 463 for (int i=0; i<nodes; i++) { 464 for (int j=0; j<nodes; j++) { 465 int minimum = current_dist[i][j]; 466 int previous_minimum = minimum; 467 int intermediate_switch = -1; 468 for (int k=0; k<nodes; k++) { 469 minimum = min(minimum, current_dist[i][k] + current_dist[k][j]); 470 if (previous_minimum != minimum) { 471 intermediate_switch = k; 472 inter_switches[i][j] = inter_switches[i][k] + inter_switches[k][j] + 1; 473 } 474 previous_minimum = minimum; 475 } 476 if (current_dist[i][j] != minimum) { 477 change = true; 478 current_dist[i][j] = minimum; 479 assert(intermediate_switch >= 0); 480 assert(intermediate_switch < latencies[i].size()); 481 latencies[i][j] = latencies[i][intermediate_switch] + latencies[intermediate_switch][j]; 482 } 483 } 484 } 485 } 486} 487 488static Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches) 489{ 490 Matrix dist = weights; 491 extend_shortest_path(dist, latencies, inter_switches); 492 return dist; 493} 494 495static bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, 496 const Matrix& weights, const Matrix& dist) 497{ 498 return (weights[src][next] + dist[next][final] == dist[src][final]); 499} 500 501static NetDest shortest_path_to_node(SwitchID src, SwitchID next, 502 const Matrix& weights, const Matrix& dist) 503{ 504 NetDest result; 505 int d = 0; 506 int machines; 507 int max_machines; 508 509 machines = MachineType_NUM; 510 max_machines = MachineType_base_number(MachineType_NUM); 511 512 for (int m=0; m<machines; m++) { 513 for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 514 // we use "d+max_machines" below since the "destination" switches for the machines are numbered 515 // [MachineType_base_number(MachineType_NUM)...2*MachineType_base_number(MachineType_NUM)-1] 516 // for the component network 517 if (link_is_shortest_path_to_node(src, next, 518 d+max_machines, 519 weights, dist)) { 520 MachineID mach = {(MachineType)m, i}; 521 result.add(mach); 522 } 523 d++; 524 } 525 } 526 527 DEBUG_MSG(NETWORK_COMP, MedPrio, "returning shortest path"); 528 DEBUG_EXPR(NETWORK_COMP, MedPrio, (src-(2*max_machines))); 529 DEBUG_EXPR(NETWORK_COMP, MedPrio, (next-(2*max_machines))); 530 DEBUG_EXPR(NETWORK_COMP, MedPrio, src); 531 DEBUG_EXPR(NETWORK_COMP, MedPrio, next); 532 DEBUG_EXPR(NETWORK_COMP, MedPrio, result); 533 DEBUG_NEWLINE(NETWORK_COMP, MedPrio); 534 535 return result; 536} 537 538