Topology.cc revision 7454
1/* 2 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29#include "mem/protocol/MachineType.hh" 30#include "mem/protocol/Protocol.hh" 31#include "mem/protocol/TopologyType.hh" 32#include "mem/ruby/common/NetDest.hh" 33#include "mem/ruby/network/Network.hh" 34#include "mem/ruby/network/simple/Topology.hh" 35#include "mem/ruby/slicc_interface/AbstractController.hh" 36#include "mem/ruby/system/System.hh" 37 38using namespace std; 39 40const int INFINITE_LATENCY = 10000; // Yes, this is a big hack 41const int DEFAULT_BW_MULTIPLIER = 1; // Just to be consistent with above :) 42 43// Note: In this file, we use the first 2*m_nodes SwitchIDs to 44// represent the input and output endpoint links. These really are 45// not 'switches', as they will not have a Switch object allocated for 46// them. The first m_nodes SwitchIDs are the links into the network, 47// the second m_nodes set of SwitchIDs represent the the output queues 48// of the network. 49 50// Helper functions based on chapter 29 of Cormen et al. 51void extend_shortest_path(Matrix& current_dist, Matrix& latencies, 52 Matrix& inter_switches); 53Matrix shortest_path(const Matrix& weights, Matrix& latencies, 54 Matrix& inter_switches); 55bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, 56 SwitchID final, const Matrix& weights, const Matrix& dist); 57NetDest shortest_path_to_node(SwitchID src, SwitchID next, 58 const Matrix& weights, const Matrix& dist); 59 60Topology::Topology(const Params *p) 61 : SimObject(p) 62{ 63 m_print_config = p->print_config; 64 m_number_of_switches = p->num_int_nodes; 65 // initialize component latencies record 66 m_component_latencies.resize(0); 67 m_component_inter_switches.resize(0); 68 69 // Total nodes/controllers in network 70 // Must make sure this is called after the State Machine constructors 71 m_nodes = MachineType_base_number(MachineType_NUM); 72 assert(m_nodes > 1); 73 74 if (m_nodes != params()->ext_links.size() && 75 m_nodes != params()->ext_links.size()) { 76 fatal("m_nodes (%d) != ext_links vector length (%d)\n", 77 m_nodes != params()->ext_links.size()); 78 } 79 80 // First create the links between the endpoints (i.e. controllers) 81 // and the network. 82 for (vector<ExtLink*>::const_iterator i = params()->ext_links.begin(); 83 i != params()->ext_links.end(); ++i) { 84 const ExtLinkParams *p = (*i)->params(); 85 AbstractController *c = p->ext_node; 86 87 // Store the controller pointers for later 88 m_controller_vector.push_back(c); 89 90 int ext_idx1 = 91 MachineType_base_number(c->getMachineType()) + c->getVersion(); 92 int ext_idx2 = ext_idx1 + m_nodes; 93 int int_idx = p->int_node + 2*m_nodes; 94 95 // create the links in both directions 96 addLink(ext_idx1, int_idx, p->latency, p->bw_multiplier, p->weight); 97 addLink(int_idx, ext_idx2, p->latency, p->bw_multiplier, p->weight); 98 } 99 100 for (vector<IntLink*>::const_iterator i = params()->int_links.begin(); 101 i != params()->int_links.end(); ++i) { 102 const IntLinkParams *p = (*i)->params(); 103 int a = p->node_a + 2*m_nodes; 104 int b = p->node_b + 2*m_nodes; 105 106 // create the links in both directions 107 addLink(a, b, p->latency, p->bw_multiplier, p->weight); 108 addLink(b, a, p->latency, p->bw_multiplier, p->weight); 109 } 110} 111 112 113void 114Topology::initNetworkPtr(Network* net_ptr) 115{ 116 for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 117 m_controller_vector[cntrl]->initNetworkPtr(net_ptr); 118 } 119} 120 121void 122Topology::createLinks(Network *net, bool isReconfiguration) 123{ 124 // Find maximum switchID 125 SwitchID max_switch_id = 0; 126 for (int i = 0; i < m_links_src_vector.size(); i++) { 127 max_switch_id = max(max_switch_id, m_links_src_vector[i]); 128 max_switch_id = max(max_switch_id, m_links_dest_vector[i]); 129 } 130 131 // Initialize weight vector 132 Matrix topology_weights; 133 Matrix topology_latency; 134 Matrix topology_bw_multis; 135 int num_switches = max_switch_id+1; 136 topology_weights.resize(num_switches); 137 topology_latency.resize(num_switches); 138 topology_bw_multis.resize(num_switches); 139 140 // FIXME setting the size of a member variable here is a HACK! 141 m_component_latencies.resize(num_switches); 142 143 // FIXME setting the size of a member variable here is a HACK! 144 m_component_inter_switches.resize(num_switches); 145 146 for (int i = 0; i < topology_weights.size(); i++) { 147 topology_weights[i].resize(num_switches); 148 topology_latency[i].resize(num_switches); 149 topology_bw_multis[i].resize(num_switches); 150 m_component_latencies[i].resize(num_switches); 151 152 // FIXME setting the size of a member variable here is a HACK! 153 m_component_inter_switches[i].resize(num_switches); 154 155 for (int j = 0; j < topology_weights[i].size(); j++) { 156 topology_weights[i][j] = INFINITE_LATENCY; 157 158 // initialize to invalid values 159 topology_latency[i][j] = -1; 160 topology_bw_multis[i][j] = -1; 161 m_component_latencies[i][j] = -1; 162 163 // initially assume direct connections / no intermediate 164 // switches between components 165 m_component_inter_switches[i][j] = 0; 166 } 167 } 168 169 // Set identity weights to zero 170 for (int i = 0; i < topology_weights.size(); i++) { 171 topology_weights[i][i] = 0; 172 } 173 174 // Fill in the topology weights and bandwidth multipliers 175 for (int i = 0; i < m_links_src_vector.size(); i++) { 176 int src = m_links_src_vector[i]; 177 int dst = m_links_dest_vector[i]; 178 topology_weights[src][dst] = m_links_weight_vector[i]; 179 topology_latency[src][dst] = m_links_latency_vector[i]; 180 m_component_latencies[src][dst] = m_links_latency_vector[i]; 181 topology_bw_multis[src][dst] = m_bw_multiplier_vector[i]; 182 } 183 184 // Walk topology and hookup the links 185 Matrix dist = shortest_path(topology_weights, m_component_latencies, 186 m_component_inter_switches); 187 for (int i = 0; i < topology_weights.size(); i++) { 188 for (int j = 0; j < topology_weights[i].size(); j++) { 189 int weight = topology_weights[i][j]; 190 int bw_multiplier = topology_bw_multis[i][j]; 191 int latency = topology_latency[i][j]; 192 if (weight > 0 && weight != INFINITE_LATENCY) { 193 NetDest destination_set = shortest_path_to_node(i, j, 194 topology_weights, dist); 195 assert(latency != -1); 196 makeLink(net, i, j, destination_set, latency, weight, 197 bw_multiplier, isReconfiguration); 198 } 199 } 200 } 201} 202 203SwitchID 204Topology::newSwitchID() 205{ 206 m_number_of_switches++; 207 return m_number_of_switches-1+m_nodes+m_nodes; 208} 209 210void 211Topology::addLink(SwitchID src, SwitchID dest, int link_latency) 212{ 213 addLink(src, dest, link_latency, DEFAULT_BW_MULTIPLIER, link_latency); 214} 215 216void 217Topology::addLink(SwitchID src, SwitchID dest, int link_latency, 218 int bw_multiplier) 219{ 220 addLink(src, dest, link_latency, bw_multiplier, link_latency); 221} 222 223void 224Topology::addLink(SwitchID src, SwitchID dest, int link_latency, 225 int bw_multiplier, int link_weight) 226{ 227 ASSERT(src <= m_number_of_switches+m_nodes+m_nodes); 228 ASSERT(dest <= m_number_of_switches+m_nodes+m_nodes); 229 m_links_src_vector.push_back(src); 230 m_links_dest_vector.push_back(dest); 231 m_links_latency_vector.push_back(link_latency); 232 m_links_weight_vector.push_back(link_weight); 233 m_bw_multiplier_vector.push_back(bw_multiplier); 234} 235 236void 237Topology::makeLink(Network *net, SwitchID src, SwitchID dest, 238 const NetDest& routing_table_entry, int link_latency, int link_weight, 239 int bw_multiplier, bool isReconfiguration) 240{ 241 // Make sure we're not trying to connect two end-point nodes 242 // directly together 243 assert(src >= 2 * m_nodes || dest >= 2 * m_nodes); 244 245 if (src < m_nodes) { 246 net->makeInLink(src, dest-(2*m_nodes), routing_table_entry, 247 link_latency, bw_multiplier, isReconfiguration); 248 } else if (dest < 2*m_nodes) { 249 assert(dest >= m_nodes); 250 NodeID node = dest-m_nodes; 251 net->makeOutLink(src-(2*m_nodes), node, routing_table_entry, 252 link_latency, link_weight, bw_multiplier, isReconfiguration); 253 } else { 254 assert((src >= 2*m_nodes) && (dest >= 2*m_nodes)); 255 net->makeInternalLink(src-(2*m_nodes), dest-(2*m_nodes), 256 routing_table_entry, link_latency, link_weight, bw_multiplier, 257 isReconfiguration); 258 } 259} 260 261void 262Topology::printStats(std::ostream& out) const 263{ 264 for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 265 m_controller_vector[cntrl]->printStats(out); 266 } 267} 268 269void 270Topology::clearStats() 271{ 272 for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 273 m_controller_vector[cntrl]->clearStats(); 274 } 275} 276 277void 278Topology::printConfig(std::ostream& out) const 279{ 280 if (m_print_config == false) 281 return; 282 283 assert(m_component_latencies.size() > 0); 284 285 out << "--- Begin Topology Print ---" << endl 286 << endl 287 << "Topology print ONLY indicates the _NETWORK_ latency between two " 288 << "machines" << endl 289 << "It does NOT include the latency within the machines" << endl 290 << endl; 291 292 for (int m = 0; m < MachineType_NUM; m++) { 293 int i_end = MachineType_base_count((MachineType)m); 294 for (int i = 0; i < i_end; i++) { 295 MachineID cur_mach = {(MachineType)m, i}; 296 out << cur_mach << " Network Latencies" << endl; 297 for (int n = 0; n < MachineType_NUM; n++) { 298 int j_end = MachineType_base_count((MachineType)n); 299 for (int j = 0; j < j_end; j++) { 300 MachineID dest_mach = {(MachineType)n, j}; 301 if (cur_mach == dest_mach) 302 continue; 303 304 int src = MachineType_base_number((MachineType)m) + i; 305 int dst = MachineType_base_number(MachineType_NUM) + 306 MachineType_base_number((MachineType)n) + j; 307 int link_latency = m_component_latencies[src][dst]; 308 int intermediate_switches = 309 m_component_inter_switches[src][dst]; 310 311 // NOTE switches are assumed to have single 312 // cycle latency 313 out << " " << cur_mach << " -> " << dest_mach 314 << " net_lat: " 315 << link_latency + intermediate_switches << endl; 316 } 317 } 318 out << endl; 319 } 320 } 321 322 out << "--- End Topology Print ---" << endl; 323} 324 325// The following all-pairs shortest path algorithm is based on the 326// discussion from Cormen et al., Chapter 26.1. 327void 328extend_shortest_path(Matrix& current_dist, Matrix& latencies, 329 Matrix& inter_switches) 330{ 331 bool change = true; 332 int nodes = current_dist.size(); 333 334 while (change) { 335 change = false; 336 for (int i = 0; i < nodes; i++) { 337 for (int j = 0; j < nodes; j++) { 338 int minimum = current_dist[i][j]; 339 int previous_minimum = minimum; 340 int intermediate_switch = -1; 341 for (int k = 0; k < nodes; k++) { 342 minimum = min(minimum, 343 current_dist[i][k] + current_dist[k][j]); 344 if (previous_minimum != minimum) { 345 intermediate_switch = k; 346 inter_switches[i][j] = 347 inter_switches[i][k] + 348 inter_switches[k][j] + 1; 349 } 350 previous_minimum = minimum; 351 } 352 if (current_dist[i][j] != minimum) { 353 change = true; 354 current_dist[i][j] = minimum; 355 assert(intermediate_switch >= 0); 356 assert(intermediate_switch < latencies[i].size()); 357 latencies[i][j] = latencies[i][intermediate_switch] + 358 latencies[intermediate_switch][j]; 359 } 360 } 361 } 362 } 363} 364 365Matrix 366shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches) 367{ 368 Matrix dist = weights; 369 extend_shortest_path(dist, latencies, inter_switches); 370 return dist; 371} 372 373bool 374link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, 375 const Matrix& weights, const Matrix& dist) 376{ 377 return weights[src][next] + dist[next][final] == dist[src][final]; 378} 379 380NetDest 381shortest_path_to_node(SwitchID src, SwitchID next, const Matrix& weights, 382 const Matrix& dist) 383{ 384 NetDest result; 385 int d = 0; 386 int machines; 387 int max_machines; 388 389 machines = MachineType_NUM; 390 max_machines = MachineType_base_number(MachineType_NUM); 391 392 for (int m = 0; m < machines; m++) { 393 for (int i = 0; i < MachineType_base_count((MachineType)m); i++) { 394 // we use "d+max_machines" below since the "destination" 395 // switches for the machines are numbered 396 // [MachineType_base_number(MachineType_NUM)... 397 // 2*MachineType_base_number(MachineType_NUM)-1] for the 398 // component network 399 if (link_is_shortest_path_to_node(src, next, d + max_machines, 400 weights, dist)) { 401 MachineID mach = {(MachineType)m, i}; 402 result.add(mach); 403 } 404 d++; 405 } 406 } 407 408 DEBUG_MSG(NETWORK_COMP, MedPrio, "returning shortest path"); 409 DEBUG_EXPR(NETWORK_COMP, MedPrio, (src-(2*max_machines))); 410 DEBUG_EXPR(NETWORK_COMP, MedPrio, (next-(2*max_machines))); 411 DEBUG_EXPR(NETWORK_COMP, MedPrio, src); 412 DEBUG_EXPR(NETWORK_COMP, MedPrio, next); 413 DEBUG_EXPR(NETWORK_COMP, MedPrio, result); 414 DEBUG_NEWLINE(NETWORK_COMP, MedPrio); 415 416 return result; 417} 418 419Topology * 420TopologyParams::create() 421{ 422 return new Topology(this); 423} 424 425Link * 426LinkParams::create() 427{ 428 return new Link(this); 429} 430 431ExtLink * 432ExtLinkParams::create() 433{ 434 return new ExtLink(this); 435} 436 437IntLink * 438IntLinkParams::create() 439{ 440 return new IntLink(this); 441} 442