Topology.cc revision 6285
1 2/* 3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are 8 * met: redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer; 10 * redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution; 13 * neither the name of the copyright holders nor the names of its 14 * contributors may be used to endorse or promote products derived from 15 * this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30/* 31 * Topology.cc 32 * 33 * Description: See Topology.hh 34 * 35 * $Id$ 36 * 37 * */ 38 39#include "mem/ruby/network/simple/Topology.hh" 40#include "mem/ruby/common/NetDest.hh" 41#include "mem/ruby/network/Network.hh" 42#include "mem/protocol/TopologyType.hh" 43//#include "mem/ruby/config/RubyConfig.hh" 44#include "mem/gems_common/util.hh" 45#include "mem/protocol/MachineType.hh" 46#include "mem/protocol/Protocol.hh" 47#include "mem/ruby/system/System.hh" 48#include <string> 49 50static const int INFINITE_LATENCY = 10000; // Yes, this is a big hack 51static const int DEFAULT_BW_MULTIPLIER = 1; // Just to be consistent with above :) 52 53// Note: In this file, we use the first 2*m_nodes SwitchIDs to 54// represent the input and output endpoint links. These really are 55// not 'switches', as they will not have a Switch object allocated for 56// them. The first m_nodes SwitchIDs are the links into the network, 57// the second m_nodes set of SwitchIDs represent the the output queues 58// of the network. 59 60// Helper functions based on chapter 29 of Cormen et al. 61static Matrix extend_shortest_path(const Matrix& current_dist, Matrix& latencies, Matrix& inter_switches); 62static Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches); 63static bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, const Matrix& weights, const Matrix& dist); 64static NetDest shortest_path_to_node(SwitchID src, SwitchID next, const Matrix& weights, const Matrix& dist); 65 66Topology::Topology(const string & name) 67 : m_name(name) 68{ 69 m_network_ptr = NULL; 70 m_nodes = MachineType_base_number(MachineType_NUM); 71 m_number_of_switches = 0; 72} 73 74void Topology::init(const vector<string> & argv) 75{ 76 for (size_t i=0; i<argv.size(); i+=2) { 77 if (argv[i] == "network") 78 m_network_ptr = RubySystem::getNetwork(); 79 else if (argv[i] == "connections") 80 m_connections = argv[i+1]; 81 else if (argv[i] == "print_config") { 82 m_print_config = string_to_bool(argv[i+1]); 83 cerr << "print config: " << m_print_config << endl; 84 } 85 } 86 assert(m_network_ptr != NULL); 87} 88 89void Topology::makeTopology() 90{ 91 /* 92 if (m_nodes == 1) { 93 SwitchID id = newSwitchID(); 94 addLink(0, id, m_network_ptr->getOffChipLinkLatency()); 95 addLink(id, 1, m_network_ptr->getOffChipLinkLatency()); 96 return; 97 } 98 */ 99 assert(m_nodes > 1); 100 101 Vector< Vector < SwitchID > > nodePairs; // node pairs extracted from the file 102 Vector<int> latencies; // link latencies for each link extracted 103 Vector<int> bw_multis; // bw multipliers for each link extracted 104 Vector<int> weights; // link weights used to enfore e-cube deadlock free routing 105 Vector< SwitchID > int_network_switches; // internal switches extracted from the file 106 Vector<bool> endpointConnectionExist; // used to ensure all endpoints are connected to the network 107 108 endpointConnectionExist.setSize(m_nodes); 109 110 // initialize endpoint check vector 111 for (int k = 0; k < endpointConnectionExist.size(); k++) { 112 endpointConnectionExist[k] = false; 113 } 114 115 stringstream networkFile( m_connections ); 116 117 string line = ""; 118 119 while (!networkFile.eof()) { 120 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