Topology.cc revision 6895
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/ruby/slicc_interface/AbstractController.hh" 43#include "mem/protocol/TopologyType.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 void extend_shortest_path(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 Params *p) 67 : SimObject(p) 68{ 69 m_print_config = p->print_config; 70 m_number_of_switches = p->num_int_nodes; 71 // initialize component latencies record 72 m_component_latencies.setSize(0); 73 m_component_inter_switches.setSize(0); 74 75 // 76 // Total nodes/controllers in network 77 // Must make sure this is called after the State Machine constructors 78 // 79 m_nodes = MachineType_base_number(MachineType_NUM); 80 assert(m_nodes > 1); 81 82 if (m_nodes != params()->ext_links.size()) { 83 fatal("m_nodes (%d) != ext_links vector length (%d)\n", 84 m_nodes != params()->ext_links.size()); 85 } 86 87 // 88 // First create the links between the endpoints (i.e. controllers) and the 89 // network. 90 // 91 for (vector<ExtLink*>::const_iterator i = params()->ext_links.begin(); 92 i != params()->ext_links.end(); ++i) 93 { 94 const ExtLinkParams *p = (*i)->params(); 95 AbstractController *c = p->ext_node; 96 97 // Store the controller pointers for later 98 m_controller_vector.insertAtBottom(c); 99 100 int ext_idx1 = 101 MachineType_base_number(c->getMachineType()) + c->getVersion(); 102 int ext_idx2 = ext_idx1 + m_nodes; 103 int int_idx = p->int_node + 2*m_nodes; 104 105 // create the links in both directions 106 addLink(ext_idx1, int_idx, p->latency, p->bw_multiplier, p->weight); 107 addLink(int_idx, ext_idx2, p->latency, p->bw_multiplier, p->weight); 108 } 109 110 for (vector<IntLink*>::const_iterator i = params()->int_links.begin(); 111 i != params()->int_links.end(); ++i) 112 { 113 const IntLinkParams *p = (*i)->params(); 114 int a = p->node_a + 2*m_nodes; 115 int b = p->node_b + 2*m_nodes; 116 117 // create the links in both directions 118 addLink(a, b, p->latency, p->bw_multiplier, p->weight); 119 addLink(b, a, p->latency, p->bw_multiplier, p->weight); 120 } 121} 122 123 124void Topology::initNetworkPtr(Network* net_ptr) 125{ 126 for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) 127 { 128 m_controller_vector[cntrl]->initNetworkPtr(net_ptr); 129 } 130} 131 132 133void Topology::createLinks(Network *net, bool isReconfiguration) 134{ 135 // Find maximum switchID 136 137 SwitchID max_switch_id = 0; 138 for (int i=0; i<m_links_src_vector.size(); i++) { 139 max_switch_id = max(max_switch_id, m_links_src_vector[i]); 140 max_switch_id = max(max_switch_id, m_links_dest_vector[i]); 141 } 142 143 // Initialize weight vector 144 Matrix topology_weights; 145 Matrix topology_latency; 146 Matrix topology_bw_multis; 147 int num_switches = max_switch_id+1; 148 topology_weights.setSize(num_switches); 149 topology_latency.setSize(num_switches); 150 topology_bw_multis.setSize(num_switches); 151 m_component_latencies.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 152 m_component_inter_switches.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 153 for(int i=0; i<topology_weights.size(); i++) { 154 topology_weights[i].setSize(num_switches); 155 topology_latency[i].setSize(num_switches); 156 topology_bw_multis[i].setSize(num_switches); 157 m_component_latencies[i].setSize(num_switches); 158 m_component_inter_switches[i].setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 159 for(int j=0; j<topology_weights[i].size(); j++) { 160 topology_weights[i][j] = INFINITE_LATENCY; 161 topology_latency[i][j] = -1; // initialize to an invalid value 162 topology_bw_multis[i][j] = -1; // initialize to an invalid value 163 m_component_latencies[i][j] = -1; // initialize to an invalid value 164 m_component_inter_switches[i][j] = 0; // initially assume direct connections / no intermediate switches between components 165 } 166 } 167 168 // Set identity weights to zero 169 for(int i=0; i<topology_weights.size(); i++) { 170 topology_weights[i][i] = 0; 171 } 172 173 // Fill in the topology weights and bandwidth multipliers 174 for (int i=0; i<m_links_src_vector.size(); i++) { 175 topology_weights[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_weight_vector[i]; 176 topology_latency[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; 177 m_component_latencies[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; // initialize to latency vector 178 topology_bw_multis[m_links_src_vector[i]][m_links_dest_vector[i]] = m_bw_multiplier_vector[i]; 179 } 180 181 // Walk topology and hookup the links 182 Matrix dist = shortest_path(topology_weights, m_component_latencies, m_component_inter_switches); 183 for(int i=0; i<topology_weights.size(); i++) { 184 for(int j=0; j<topology_weights[i].size(); j++) { 185 int weight = topology_weights[i][j]; 186 int bw_multiplier = topology_bw_multis[i][j]; 187 int latency = topology_latency[i][j]; 188 if (weight > 0 && weight != INFINITE_LATENCY) { 189 NetDest destination_set = shortest_path_to_node(i, j, topology_weights, dist); 190 assert(latency != -1); 191 makeLink(net, i, j, destination_set, latency, weight, bw_multiplier, isReconfiguration); 192 } 193 } 194 } 195} 196 197SwitchID Topology::newSwitchID() 198{ 199 m_number_of_switches++; 200 return m_number_of_switches-1+m_nodes+m_nodes; 201} 202 203void Topology::addLink(SwitchID src, SwitchID dest, int link_latency) 204{ 205 addLink(src, dest, link_latency, DEFAULT_BW_MULTIPLIER, link_latency); 206} 207 208void Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier) 209{ 210 addLink(src, dest, link_latency, bw_multiplier, link_latency); 211} 212 213void Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier, int link_weight) 214{ 215 ASSERT(src <= m_number_of_switches+m_nodes+m_nodes); 216 ASSERT(dest <= m_number_of_switches+m_nodes+m_nodes); 217 m_links_src_vector.insertAtBottom(src); 218 m_links_dest_vector.insertAtBottom(dest); 219 m_links_latency_vector.insertAtBottom(link_latency); 220 m_links_weight_vector.insertAtBottom(link_weight); 221 m_bw_multiplier_vector.insertAtBottom(bw_multiplier); 222} 223 224void Topology::makeLink(Network *net, SwitchID src, SwitchID dest, const NetDest& routing_table_entry, int link_latency, int link_weight, int bw_multiplier, bool isReconfiguration) 225{ 226 // Make sure we're not trying to connect two end-point nodes directly together 227 assert((src >= 2*m_nodes) || (dest >= 2*m_nodes)); 228 229 if (src < m_nodes) { 230 net->makeInLink(src, dest-(2*m_nodes), routing_table_entry, link_latency, bw_multiplier, isReconfiguration); 231 } else if (dest < 2*m_nodes) { 232 assert(dest >= m_nodes); 233 NodeID node = dest-m_nodes; 234 net->makeOutLink(src-(2*m_nodes), node, routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 235 } else { 236 assert((src >= 2*m_nodes) && (dest >= 2*m_nodes)); 237 net->makeInternalLink(src-(2*m_nodes), dest-(2*m_nodes), routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 238 } 239} 240 241void Topology::printStats(ostream& out) const 242{ 243 for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 244 m_controller_vector[cntrl]->printStats(out); 245 } 246} 247 248void Topology::clearStats() 249{ 250 for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++) { 251 m_controller_vector[cntrl]->clearStats(); 252 } 253} 254 255void Topology::printConfig(ostream& out) const 256{ 257 if (m_print_config == false) return; 258 259 assert(m_component_latencies.size() > 0); 260 261 out << "--- Begin Topology Print ---" << endl; 262 out << endl; 263 out << "Topology print ONLY indicates the _NETWORK_ latency between two machines" << endl; 264 out << "It does NOT include the latency within the machines" << endl; 265 out << endl; 266 for (int m=0; m<MachineType_NUM; m++) { 267 for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 268 MachineID cur_mach = {(MachineType)m, i}; 269 out << cur_mach << " Network Latencies" << endl; 270 for (int n=0; n<MachineType_NUM; n++) { 271 for (int j=0; j<MachineType_base_count((MachineType)n); j++) { 272 MachineID dest_mach = {(MachineType)n, j}; 273 if (cur_mach != dest_mach) { 274 int link_latency = m_component_latencies[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 275 int intermediate_switches = m_component_inter_switches[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 276 out << " " << cur_mach << " -> " << dest_mach << " net_lat: " 277 << link_latency+intermediate_switches << endl; // NOTE switches are assumed to have single cycle latency 278 } 279 } 280 } 281 out << endl; 282 } 283 } 284 285 out << "--- End Topology Print ---" << endl; 286} 287 288/**************************************************************************/ 289 290// The following all-pairs shortest path algorithm is based on the 291// discussion from Cormen et al., Chapter 26.1. 292 293static void extend_shortest_path(Matrix& current_dist, Matrix& latencies, Matrix& inter_switches) 294{ 295 bool change = true; 296 int nodes = current_dist.size(); 297 298 while (change) { 299 change = false; 300 for (int i=0; i<nodes; i++) { 301 for (int j=0; j<nodes; j++) { 302 int minimum = current_dist[i][j]; 303 int previous_minimum = minimum; 304 int intermediate_switch = -1; 305 for (int k=0; k<nodes; k++) { 306 minimum = min(minimum, current_dist[i][k] + current_dist[k][j]); 307 if (previous_minimum != minimum) { 308 intermediate_switch = k; 309 inter_switches[i][j] = inter_switches[i][k] + inter_switches[k][j] + 1; 310 } 311 previous_minimum = minimum; 312 } 313 if (current_dist[i][j] != minimum) { 314 change = true; 315 current_dist[i][j] = minimum; 316 assert(intermediate_switch >= 0); 317 assert(intermediate_switch < latencies[i].size()); 318 latencies[i][j] = latencies[i][intermediate_switch] + latencies[intermediate_switch][j]; 319 } 320 } 321 } 322 } 323} 324 325static Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches) 326{ 327 Matrix dist = weights; 328 extend_shortest_path(dist, latencies, inter_switches); 329 return dist; 330} 331 332static bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, 333 const Matrix& weights, const Matrix& dist) 334{ 335 return (weights[src][next] + dist[next][final] == dist[src][final]); 336} 337 338static NetDest shortest_path_to_node(SwitchID src, SwitchID next, 339 const Matrix& weights, const Matrix& dist) 340{ 341 NetDest result; 342 int d = 0; 343 int machines; 344 int max_machines; 345 346 machines = MachineType_NUM; 347 max_machines = MachineType_base_number(MachineType_NUM); 348 349 for (int m=0; m<machines; m++) { 350 for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 351 // we use "d+max_machines" below since the "destination" switches for the machines are numbered 352 // [MachineType_base_number(MachineType_NUM)...2*MachineType_base_number(MachineType_NUM)-1] 353 // for the component network 354 if (link_is_shortest_path_to_node(src, next, 355 d+max_machines, 356 weights, dist)) { 357 MachineID mach = {(MachineType)m, i}; 358 result.add(mach); 359 } 360 d++; 361 } 362 } 363 364 DEBUG_MSG(NETWORK_COMP, MedPrio, "returning shortest path"); 365 DEBUG_EXPR(NETWORK_COMP, MedPrio, (src-(2*max_machines))); 366 DEBUG_EXPR(NETWORK_COMP, MedPrio, (next-(2*max_machines))); 367 DEBUG_EXPR(NETWORK_COMP, MedPrio, src); 368 DEBUG_EXPR(NETWORK_COMP, MedPrio, next); 369 DEBUG_EXPR(NETWORK_COMP, MedPrio, result); 370 DEBUG_NEWLINE(NETWORK_COMP, MedPrio); 371 372 return result; 373} 374 375Topology * 376TopologyParams::create() 377{ 378 return new Topology(this); 379} 380 381Link * 382LinkParams::create() 383{ 384 return new Link(this); 385} 386 387ExtLink * 388ExtLinkParams::create() 389{ 390 return new ExtLink(this); 391} 392 393IntLink * 394IntLinkParams::create() 395{ 396 return new IntLink(this); 397} 398