Topology.cc revision 11664
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 <cassert> 30 31#include "base/trace.hh" 32#include "debug/RubyNetwork.hh" 33#include "mem/ruby/common/NetDest.hh" 34#include "mem/ruby/network/BasicLink.hh" 35#include "mem/ruby/network/Topology.hh" 36#include "mem/ruby/slicc_interface/AbstractController.hh" 37 38using namespace std; 39 40const int INFINITE_LATENCY = 10000; // Yes, this is a big hack 41 42// Note: In this file, we use the first 2*m_nodes SwitchIDs to 43// represent the input and output endpoint links. These really are 44// not 'switches', as they will not have a Switch object allocated for 45// them. The first m_nodes SwitchIDs are the links into the network, 46// the second m_nodes set of SwitchIDs represent the the output queues 47// of the network. 48 49Topology::Topology(uint32_t num_routers, 50 const vector<BasicExtLink *> &ext_links, 51 const vector<BasicIntLink *> &int_links) 52 : m_nodes(ext_links.size()), m_number_of_switches(num_routers), 53 m_ext_link_vector(ext_links), m_int_link_vector(int_links) 54{ 55 // Total nodes/controllers in network 56 assert(m_nodes > 1); 57 58 // analyze both the internal and external links, create data structures. 59 // The python created external links are bi-directional, 60 // and the python created internal links are uni-directional. 61 // The networks and topology utilize uni-directional links. 62 // Thus each external link is converted to two calls to addLink, 63 // one for each direction. 64 // 65 // External Links 66 for (vector<BasicExtLink*>::const_iterator i = ext_links.begin(); 67 i != ext_links.end(); ++i) { 68 BasicExtLink *ext_link = (*i); 69 AbstractController *abs_cntrl = ext_link->params()->ext_node; 70 BasicRouter *router = ext_link->params()->int_node; 71 72 int machine_base_idx = MachineType_base_number(abs_cntrl->getType()); 73 int ext_idx1 = machine_base_idx + abs_cntrl->getVersion(); 74 int ext_idx2 = ext_idx1 + m_nodes; 75 int int_idx = router->params()->router_id + 2*m_nodes; 76 77 // create the internal uni-directional links in both directions 78 // ext to int 79 addLink(ext_idx1, int_idx, ext_link); 80 // int to ext 81 addLink(int_idx, ext_idx2, ext_link); 82 } 83 84 // Internal Links 85 for (vector<BasicIntLink*>::const_iterator i = int_links.begin(); 86 i != int_links.end(); ++i) { 87 BasicIntLink *int_link = (*i); 88 BasicRouter *router_src = int_link->params()->src_node; 89 BasicRouter *router_dst = int_link->params()->dst_node; 90 91 PortDirection src_outport = int_link->params()->src_outport; 92 PortDirection dst_inport = int_link->params()->dst_inport; 93 94 // Store the IntLink pointers for later 95 m_int_link_vector.push_back(int_link); 96 97 int src = router_src->params()->router_id + 2*m_nodes; 98 int dst = router_dst->params()->router_id + 2*m_nodes; 99 100 // create the internal uni-directional link from src to dst 101 addLink(src, dst, int_link, src_outport, dst_inport); 102 } 103} 104 105void 106Topology::createLinks(Network *net) 107{ 108 // Find maximum switchID 109 SwitchID max_switch_id = 0; 110 for (LinkMap::const_iterator i = m_link_map.begin(); 111 i != m_link_map.end(); ++i) { 112 std::pair<SwitchID, SwitchID> src_dest = (*i).first; 113 max_switch_id = max(max_switch_id, src_dest.first); 114 max_switch_id = max(max_switch_id, src_dest.second); 115 } 116 117 // Initialize weight, latency, and inter switched vectors 118 int num_switches = max_switch_id+1; 119 Matrix topology_weights(num_switches, 120 vector<int>(num_switches, INFINITE_LATENCY)); 121 Matrix component_latencies(num_switches, 122 vector<int>(num_switches, -1)); 123 Matrix component_inter_switches(num_switches, 124 vector<int>(num_switches, 0)); 125 126 // Set identity weights to zero 127 for (int i = 0; i < topology_weights.size(); i++) { 128 topology_weights[i][i] = 0; 129 } 130 131 // Fill in the topology weights and bandwidth multipliers 132 for (LinkMap::const_iterator i = m_link_map.begin(); 133 i != m_link_map.end(); ++i) { 134 std::pair<int, int> src_dest = (*i).first; 135 BasicLink* link = (*i).second.link; 136 int src = src_dest.first; 137 int dst = src_dest.second; 138 component_latencies[src][dst] = link->m_latency; 139 topology_weights[src][dst] = link->m_weight; 140 } 141 142 // Walk topology and hookup the links 143 Matrix dist = shortest_path(topology_weights, component_latencies, 144 component_inter_switches); 145 146 for (int i = 0; i < topology_weights.size(); i++) { 147 for (int j = 0; j < topology_weights[i].size(); j++) { 148 int weight = topology_weights[i][j]; 149 if (weight > 0 && weight != INFINITE_LATENCY) { 150 NetDest destination_set = 151 shortest_path_to_node(i, j, topology_weights, dist); 152 makeLink(net, i, j, destination_set); 153 } 154 } 155 } 156} 157 158void 159Topology::addLink(SwitchID src, SwitchID dest, BasicLink* link, 160 PortDirection src_outport_dirn, 161 PortDirection dst_inport_dirn) 162{ 163 assert(src <= m_number_of_switches+m_nodes+m_nodes); 164 assert(dest <= m_number_of_switches+m_nodes+m_nodes); 165 166 std::pair<int, int> src_dest_pair; 167 LinkEntry link_entry; 168 169 src_dest_pair.first = src; 170 src_dest_pair.second = dest; 171 link_entry.link = link; 172 link_entry.src_outport_dirn = src_outport_dirn; 173 link_entry.dst_inport_dirn = dst_inport_dirn; 174 m_link_map[src_dest_pair] = link_entry; 175} 176 177void 178Topology::makeLink(Network *net, SwitchID src, SwitchID dest, 179 const NetDest& routing_table_entry) 180{ 181 // Make sure we're not trying to connect two end-point nodes 182 // directly together 183 assert(src >= 2 * m_nodes || dest >= 2 * m_nodes); 184 185 std::pair<int, int> src_dest; 186 LinkEntry link_entry; 187 188 if (src < m_nodes) { 189 src_dest.first = src; 190 src_dest.second = dest; 191 link_entry = m_link_map[src_dest]; 192 net->makeExtInLink(src, dest - (2 * m_nodes), link_entry.link, 193 routing_table_entry); 194 } else if (dest < 2*m_nodes) { 195 assert(dest >= m_nodes); 196 NodeID node = dest - m_nodes; 197 src_dest.first = src; 198 src_dest.second = dest; 199 link_entry = m_link_map[src_dest]; 200 net->makeExtOutLink(src - (2 * m_nodes), node, link_entry.link, 201 routing_table_entry); 202 } else { 203 assert((src >= 2 * m_nodes) && (dest >= 2 * m_nodes)); 204 src_dest.first = src; 205 src_dest.second = dest; 206 link_entry = m_link_map[src_dest]; 207 net->makeInternalLink(src - (2 * m_nodes), dest - (2 * m_nodes), 208 link_entry.link, 209 routing_table_entry, 210 link_entry.src_outport_dirn, 211 link_entry.dst_inport_dirn); 212 } 213} 214 215// The following all-pairs shortest path algorithm is based on the 216// discussion from Cormen et al., Chapter 26.1. 217void 218Topology::extend_shortest_path(Matrix ¤t_dist, Matrix &latencies, 219 Matrix &inter_switches) 220{ 221 bool change = true; 222 int nodes = current_dist.size(); 223 224 while (change) { 225 change = false; 226 for (int i = 0; i < nodes; i++) { 227 for (int j = 0; j < nodes; j++) { 228 int minimum = current_dist[i][j]; 229 int previous_minimum = minimum; 230 int intermediate_switch = -1; 231 for (int k = 0; k < nodes; k++) { 232 minimum = min(minimum, 233 current_dist[i][k] + current_dist[k][j]); 234 if (previous_minimum != minimum) { 235 intermediate_switch = k; 236 inter_switches[i][j] = 237 inter_switches[i][k] + 238 inter_switches[k][j] + 1; 239 } 240 previous_minimum = minimum; 241 } 242 if (current_dist[i][j] != minimum) { 243 change = true; 244 current_dist[i][j] = minimum; 245 assert(intermediate_switch >= 0); 246 assert(intermediate_switch < latencies[i].size()); 247 latencies[i][j] = latencies[i][intermediate_switch] + 248 latencies[intermediate_switch][j]; 249 } 250 } 251 } 252 } 253} 254 255Matrix 256Topology::shortest_path(const Matrix &weights, Matrix &latencies, 257 Matrix &inter_switches) 258{ 259 Matrix dist = weights; 260 extend_shortest_path(dist, latencies, inter_switches); 261 return dist; 262} 263 264bool 265Topology::link_is_shortest_path_to_node(SwitchID src, SwitchID next, 266 SwitchID final, const Matrix &weights, 267 const Matrix &dist) 268{ 269 return weights[src][next] + dist[next][final] == dist[src][final]; 270} 271 272NetDest 273Topology::shortest_path_to_node(SwitchID src, SwitchID next, 274 const Matrix &weights, const Matrix &dist) 275{ 276 NetDest result; 277 int d = 0; 278 int machines; 279 int max_machines; 280 281 machines = MachineType_NUM; 282 max_machines = MachineType_base_number(MachineType_NUM); 283 284 for (int m = 0; m < machines; m++) { 285 for (NodeID i = 0; i < MachineType_base_count((MachineType)m); i++) { 286 // we use "d+max_machines" below since the "destination" 287 // switches for the machines are numbered 288 // [MachineType_base_number(MachineType_NUM)... 289 // 2*MachineType_base_number(MachineType_NUM)-1] for the 290 // component network 291 if (link_is_shortest_path_to_node(src, next, d + max_machines, 292 weights, dist)) { 293 MachineID mach = {(MachineType)m, i}; 294 result.add(mach); 295 } 296 d++; 297 } 298 } 299 300 DPRINTF(RubyNetwork, "Returning shortest path\n" 301 "(src-(2*max_machines)): %d, (next-(2*max_machines)): %d, " 302 "src: %d, next: %d, result: %s\n", 303 (src-(2*max_machines)), (next-(2*max_machines)), 304 src, next, result); 305 306 return result; 307} 308