Topology.cc revision 7780
14484Sbinkertn@umich.edu/* 24484Sbinkertn@umich.edu * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 34484Sbinkertn@umich.edu * All rights reserved. 44484Sbinkertn@umich.edu * 54484Sbinkertn@umich.edu * Redistribution and use in source and binary forms, with or without 64484Sbinkertn@umich.edu * modification, are permitted provided that the following conditions are 74484Sbinkertn@umich.edu * met: redistributions of source code must retain the above copyright 84484Sbinkertn@umich.edu * notice, this list of conditions and the following disclaimer; 94484Sbinkertn@umich.edu * redistributions in binary form must reproduce the above copyright 104484Sbinkertn@umich.edu * notice, this list of conditions and the following disclaimer in the 114484Sbinkertn@umich.edu * documentation and/or other materials provided with the distribution; 124484Sbinkertn@umich.edu * neither the name of the copyright holders nor the names of its 134484Sbinkertn@umich.edu * contributors may be used to endorse or promote products derived from 144484Sbinkertn@umich.edu * this software without specific prior written permission. 154484Sbinkertn@umich.edu * 164484Sbinkertn@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 174484Sbinkertn@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 184484Sbinkertn@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 194484Sbinkertn@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 204484Sbinkertn@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 214484Sbinkertn@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 224484Sbinkertn@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 234484Sbinkertn@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 244484Sbinkertn@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 254484Sbinkertn@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 264484Sbinkertn@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 274484Sbinkertn@umich.edu */ 284484Sbinkertn@umich.edu 294484Sbinkertn@umich.edu#include "mem/protocol/MachineType.hh" 304484Sbinkertn@umich.edu#include "mem/protocol/Protocol.hh" 314484Sbinkertn@umich.edu#include "mem/protocol/TopologyType.hh" 324484Sbinkertn@umich.edu#include "mem/ruby/common/NetDest.hh" 334484Sbinkertn@umich.edu#include "mem/ruby/network/Network.hh" 344484Sbinkertn@umich.edu#include "mem/ruby/network/simple/Topology.hh" 354484Sbinkertn@umich.edu#include "mem/ruby/slicc_interface/AbstractController.hh" 364484Sbinkertn@umich.edu#include "mem/ruby/system/System.hh" 374484Sbinkertn@umich.edu 384484Sbinkertn@umich.eduusing namespace std; 394484Sbinkertn@umich.edu 404484Sbinkertn@umich.educonst int INFINITE_LATENCY = 10000; // Yes, this is a big hack 414484Sbinkertn@umich.educonst int DEFAULT_BW_MULTIPLIER = 1; // Just to be consistent with above :) 424484Sbinkertn@umich.edu 434484Sbinkertn@umich.edu// Note: In this file, we use the first 2*m_nodes SwitchIDs to 444484Sbinkertn@umich.edu// represent the input and output endpoint links. These really are 454484Sbinkertn@umich.edu// not 'switches', as they will not have a Switch object allocated for 464484Sbinkertn@umich.edu// them. The first m_nodes SwitchIDs are the links into the network, 474484Sbinkertn@umich.edu// the second m_nodes set of SwitchIDs represent the the output queues 484484Sbinkertn@umich.edu// of the network. 494484Sbinkertn@umich.edu 504484Sbinkertn@umich.edu// Helper functions based on chapter 29 of Cormen et al. 514484Sbinkertn@umich.eduvoid extend_shortest_path(Matrix& current_dist, Matrix& latencies, 524484Sbinkertn@umich.edu Matrix& inter_switches); 534484Sbinkertn@umich.eduMatrix shortest_path(const Matrix& weights, Matrix& latencies, 544484Sbinkertn@umich.edu Matrix& inter_switches); 554484Sbinkertn@umich.edubool link_is_shortest_path_to_node(SwitchID src, SwitchID next, 564484Sbinkertn@umich.edu SwitchID final, const Matrix& weights, const Matrix& dist); 574484Sbinkertn@umich.eduNetDest shortest_path_to_node(SwitchID src, SwitchID next, 584484Sbinkertn@umich.edu const Matrix& weights, const Matrix& dist); 594484Sbinkertn@umich.edu 604484Sbinkertn@umich.eduTopology::Topology(const Params *p) 614484Sbinkertn@umich.edu : SimObject(p) 624484Sbinkertn@umich.edu{ 634484Sbinkertn@umich.edu m_print_config = p->print_config; 644484Sbinkertn@umich.edu m_number_of_switches = p->num_int_nodes; 654484Sbinkertn@umich.edu // initialize component latencies record 664484Sbinkertn@umich.edu m_component_latencies.resize(0); 674484Sbinkertn@umich.edu m_component_inter_switches.resize(0); 684484Sbinkertn@umich.edu 694484Sbinkertn@umich.edu // Total nodes/controllers in network 704484Sbinkertn@umich.edu // Must make sure this is called after the State Machine constructors 714484Sbinkertn@umich.edu m_nodes = MachineType_base_number(MachineType_NUM); 724484Sbinkertn@umich.edu assert(m_nodes > 1); 734484Sbinkertn@umich.edu 744484Sbinkertn@umich.edu if (m_nodes != params()->ext_links.size() && 754484Sbinkertn@umich.edu m_nodes != params()->ext_links.size()) { 764484Sbinkertn@umich.edu fatal("m_nodes (%d) != ext_links vector length (%d)\n", 774484Sbinkertn@umich.edu m_nodes != params()->ext_links.size()); 784484Sbinkertn@umich.edu } 794484Sbinkertn@umich.edu 804484Sbinkertn@umich.edu // First create the links between the endpoints (i.e. controllers) 814484Sbinkertn@umich.edu // and the network. 824484Sbinkertn@umich.edu for (vector<ExtLink*>::const_iterator i = params()->ext_links.begin(); 834484Sbinkertn@umich.edu i != params()->ext_links.end(); ++i) { 844484Sbinkertn@umich.edu const ExtLinkParams *p = (*i)->params(); 854484Sbinkertn@umich.edu AbstractController *c = p->ext_node; 864484Sbinkertn@umich.edu 874484Sbinkertn@umich.edu // Store the controller pointers for later 884484Sbinkertn@umich.edu m_controller_vector.push_back(c); 894484Sbinkertn@umich.edu 904484Sbinkertn@umich.edu int ext_idx1 = 914484Sbinkertn@umich.edu MachineType_base_number(c->getMachineType()) + c->getVersion(); 924484Sbinkertn@umich.edu int ext_idx2 = ext_idx1 + m_nodes; 934484Sbinkertn@umich.edu int int_idx = p->int_node + 2*m_nodes; 944484Sbinkertn@umich.edu 954484Sbinkertn@umich.edu // create the links in both directions 964484Sbinkertn@umich.edu addLink(ext_idx1, int_idx, p->latency, p->bw_multiplier, p->weight); 974484Sbinkertn@umich.edu addLink(int_idx, ext_idx2, p->latency, p->bw_multiplier, p->weight); 984484Sbinkertn@umich.edu } 994484Sbinkertn@umich.edu 1004484Sbinkertn@umich.edu for (vector<IntLink*>::const_iterator i = params()->int_links.begin(); 1014484Sbinkertn@umich.edu i != params()->int_links.end(); ++i) { 1024484Sbinkertn@umich.edu const IntLinkParams *p = (*i)->params(); 1034484Sbinkertn@umich.edu int a = p->node_a + 2*m_nodes; 1044484Sbinkertn@umich.edu int b = p->node_b + 2*m_nodes; 1054484Sbinkertn@umich.edu 1064484Sbinkertn@umich.edu // create the links in both directions 1074484Sbinkertn@umich.edu addLink(a, b, p->latency, p->bw_multiplier, p->weight); 1084484Sbinkertn@umich.edu addLink(b, a, p->latency, p->bw_multiplier, p->weight); 1094484Sbinkertn@umich.edu } 1104484Sbinkertn@umich.edu} 1114484Sbinkertn@umich.edu 1124484Sbinkertn@umich.edu 1134484Sbinkertn@umich.eduvoid 1144484Sbinkertn@umich.eduTopology::initNetworkPtr(Network* net_ptr) 1154484Sbinkertn@umich.edu{ 1164484Sbinkertn@umich.edu for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 1174484Sbinkertn@umich.edu m_controller_vector[cntrl]->initNetworkPtr(net_ptr); 1184484Sbinkertn@umich.edu } 1194484Sbinkertn@umich.edu} 1204484Sbinkertn@umich.edu 1214484Sbinkertn@umich.eduvoid 1224484Sbinkertn@umich.eduTopology::createLinks(Network *net, bool isReconfiguration) 1234484Sbinkertn@umich.edu{ 1244484Sbinkertn@umich.edu // Find maximum switchID 1254484Sbinkertn@umich.edu SwitchID max_switch_id = 0; 1264484Sbinkertn@umich.edu for (int i = 0; i < m_links_src_vector.size(); i++) { 1274484Sbinkertn@umich.edu max_switch_id = max(max_switch_id, m_links_src_vector[i]); 1284484Sbinkertn@umich.edu max_switch_id = max(max_switch_id, m_links_dest_vector[i]); 1294484Sbinkertn@umich.edu } 1304484Sbinkertn@umich.edu 1314484Sbinkertn@umich.edu // Initialize weight vector 1324484Sbinkertn@umich.edu Matrix topology_weights; 1334484Sbinkertn@umich.edu Matrix topology_latency; 1344484Sbinkertn@umich.edu Matrix topology_bw_multis; 1354484Sbinkertn@umich.edu int num_switches = max_switch_id+1; 1364484Sbinkertn@umich.edu topology_weights.resize(num_switches); 1374484Sbinkertn@umich.edu topology_latency.resize(num_switches); 1384484Sbinkertn@umich.edu topology_bw_multis.resize(num_switches); 1394484Sbinkertn@umich.edu 1404484Sbinkertn@umich.edu // FIXME setting the size of a member variable here is a HACK! 1414484Sbinkertn@umich.edu 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 DPRINTF(RubyNetwork, "Returning shortest path\n" 409 "(src-(2*max_machines)): %d, (next-(2*max_machines)): %d, " 410 "src: %d, next: %d, result: %s\n", 411 (src-(2*max_machines)), (next-(2*max_machines)), 412 src, next, result); 413 414 return result; 415} 416 417Topology * 418TopologyParams::create() 419{ 420 return new Topology(this); 421} 422 423Link * 424LinkParams::create() 425{ 426 return new Link(this); 427} 428 429ExtLink * 430ExtLinkParams::create() 431{ 432 return new ExtLink(this); 433} 434 435IntLink * 436IntLinkParams::create() 437{ 438 return new IntLink(this); 439} 440