Topology.cc revision 6881
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::printConfig(ostream& out) const 242{ 243 if (m_print_config == false) return; 244 245 assert(m_component_latencies.size() > 0); 246 247 out << "--- Begin Topology Print ---" << endl; 248 out << endl; 249 out << "Topology print ONLY indicates the _NETWORK_ latency between two machines" << endl; 250 out << "It does NOT include the latency within the machines" << endl; 251 out << endl; 252 for (int m=0; m<MachineType_NUM; m++) { 253 for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 254 MachineID cur_mach = {(MachineType)m, i}; 255 out << cur_mach << " Network Latencies" << endl; 256 for (int n=0; n<MachineType_NUM; n++) { 257 for (int j=0; j<MachineType_base_count((MachineType)n); j++) { 258 MachineID dest_mach = {(MachineType)n, j}; 259 if (cur_mach != dest_mach) { 260 int link_latency = m_component_latencies[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 261 int intermediate_switches = m_component_inter_switches[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 262 out << " " << cur_mach << " -> " << dest_mach << " net_lat: " 263 << link_latency+intermediate_switches << endl; // NOTE switches are assumed to have single cycle latency 264 } 265 } 266 } 267 out << endl; 268 } 269 } 270 271 out << "--- End Topology Print ---" << endl; 272} 273 274/**************************************************************************/ 275 276// The following all-pairs shortest path algorithm is based on the 277// discussion from Cormen et al., Chapter 26.1. 278 279static void extend_shortest_path(Matrix& current_dist, Matrix& latencies, Matrix& inter_switches) 280{ 281 bool change = true; 282 int nodes = current_dist.size(); 283 284 while (change) { 285 change = false; 286 for (int i=0; i<nodes; i++) { 287 for (int j=0; j<nodes; j++) { 288 int minimum = current_dist[i][j]; 289 int previous_minimum = minimum; 290 int intermediate_switch = -1; 291 for (int k=0; k<nodes; k++) { 292 minimum = min(minimum, current_dist[i][k] + current_dist[k][j]); 293 if (previous_minimum != minimum) { 294 intermediate_switch = k; 295 inter_switches[i][j] = inter_switches[i][k] + inter_switches[k][j] + 1; 296 } 297 previous_minimum = minimum; 298 } 299 if (current_dist[i][j] != minimum) { 300 change = true; 301 current_dist[i][j] = minimum; 302 assert(intermediate_switch >= 0); 303 assert(intermediate_switch < latencies[i].size()); 304 latencies[i][j] = latencies[i][intermediate_switch] + latencies[intermediate_switch][j]; 305 } 306 } 307 } 308 } 309} 310 311static Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches) 312{ 313 Matrix dist = weights; 314 extend_shortest_path(dist, latencies, inter_switches); 315 return dist; 316} 317 318static bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, 319 const Matrix& weights, const Matrix& dist) 320{ 321 return (weights[src][next] + dist[next][final] == dist[src][final]); 322} 323 324static NetDest shortest_path_to_node(SwitchID src, SwitchID next, 325 const Matrix& weights, const Matrix& dist) 326{ 327 NetDest result; 328 int d = 0; 329 int machines; 330 int max_machines; 331 332 machines = MachineType_NUM; 333 max_machines = MachineType_base_number(MachineType_NUM); 334 335 for (int m=0; m<machines; m++) { 336 for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 337 // we use "d+max_machines" below since the "destination" switches for the machines are numbered 338 // [MachineType_base_number(MachineType_NUM)...2*MachineType_base_number(MachineType_NUM)-1] 339 // for the component network 340 if (link_is_shortest_path_to_node(src, next, 341 d+max_machines, 342 weights, dist)) { 343 MachineID mach = {(MachineType)m, i}; 344 result.add(mach); 345 } 346 d++; 347 } 348 } 349 350 DEBUG_MSG(NETWORK_COMP, MedPrio, "returning shortest path"); 351 DEBUG_EXPR(NETWORK_COMP, MedPrio, (src-(2*max_machines))); 352 DEBUG_EXPR(NETWORK_COMP, MedPrio, (next-(2*max_machines))); 353 DEBUG_EXPR(NETWORK_COMP, MedPrio, src); 354 DEBUG_EXPR(NETWORK_COMP, MedPrio, next); 355 DEBUG_EXPR(NETWORK_COMP, MedPrio, result); 356 DEBUG_NEWLINE(NETWORK_COMP, MedPrio); 357 358 return result; 359} 360 361Topology * 362TopologyParams::create() 363{ 364 return new Topology(this); 365} 366 367Link * 368LinkParams::create() 369{ 370 return new Link(this); 371} 372 373ExtLink * 374ExtLinkParams::create() 375{ 376 return new ExtLink(this); 377} 378 379IntLink * 380IntLinkParams::create() 381{ 382 return new IntLink(this); 383} 384