Topology.cc revision 11793
17375Sgblack@eecs.umich.edu/* 27375Sgblack@eecs.umich.edu * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 37375Sgblack@eecs.umich.edu * All rights reserved. 47375Sgblack@eecs.umich.edu * 57375Sgblack@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 67375Sgblack@eecs.umich.edu * modification, are permitted provided that the following conditions are 77375Sgblack@eecs.umich.edu * met: redistributions of source code must retain the above copyright 87375Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 97375Sgblack@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 107375Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 117375Sgblack@eecs.umich.edu * documentation and/or other materials provided with the distribution; 127375Sgblack@eecs.umich.edu * neither the name of the copyright holders nor the names of its 137375Sgblack@eecs.umich.edu * contributors may be used to endorse or promote products derived from 147375Sgblack@eecs.umich.edu * this software without specific prior written permission. 157375Sgblack@eecs.umich.edu * 167375Sgblack@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 177375Sgblack@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 187375Sgblack@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 197375Sgblack@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 207375Sgblack@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 217375Sgblack@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 227375Sgblack@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 237375Sgblack@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 247375Sgblack@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 257375Sgblack@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 267375Sgblack@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 277375Sgblack@eecs.umich.edu */ 287375Sgblack@eecs.umich.edu 297375Sgblack@eecs.umich.edu#include "mem/ruby/network/Topology.hh" 307375Sgblack@eecs.umich.edu 317375Sgblack@eecs.umich.edu#include <cassert> 327375Sgblack@eecs.umich.edu 337375Sgblack@eecs.umich.edu#include "base/trace.hh" 347375Sgblack@eecs.umich.edu#include "debug/RubyNetwork.hh" 357375Sgblack@eecs.umich.edu#include "mem/ruby/common/NetDest.hh" 367375Sgblack@eecs.umich.edu#include "mem/ruby/network/BasicLink.hh" 377375Sgblack@eecs.umich.edu#include "mem/ruby/network/Network.hh" 387375Sgblack@eecs.umich.edu#include "mem/ruby/slicc_interface/AbstractController.hh" 397375Sgblack@eecs.umich.edu 407640Sgblack@eecs.umich.eduusing namespace std; 417640Sgblack@eecs.umich.edu 427640Sgblack@eecs.umich.educonst int INFINITE_LATENCY = 10000; // Yes, this is a big hack 437640Sgblack@eecs.umich.edu 447640Sgblack@eecs.umich.edu// Note: In this file, we use the first 2*m_nodes SwitchIDs to 457640Sgblack@eecs.umich.edu// represent the input and output endpoint links. These really are 467644Sali.saidi@arm.com// not 'switches', as they will not have a Switch object allocated for 477640Sgblack@eecs.umich.edu// them. The first m_nodes SwitchIDs are the links into the network, 487644Sali.saidi@arm.com// the second m_nodes set of SwitchIDs represent the the output queues 497644Sali.saidi@arm.com// of the network. 507644Sali.saidi@arm.com 517644Sali.saidi@arm.comTopology::Topology(uint32_t num_routers, 527644Sali.saidi@arm.com const vector<BasicExtLink *> &ext_links, 537644Sali.saidi@arm.com const vector<BasicIntLink *> &int_links) 547644Sali.saidi@arm.com : m_nodes(ext_links.size()), m_number_of_switches(num_routers), 557644Sali.saidi@arm.com m_ext_link_vector(ext_links), m_int_link_vector(int_links) 567644Sali.saidi@arm.com{ 577644Sali.saidi@arm.com // Total nodes/controllers in network 587644Sali.saidi@arm.com assert(m_nodes > 1); 597644Sali.saidi@arm.com 607644Sali.saidi@arm.com // analyze both the internal and external links, create data structures. 617644Sali.saidi@arm.com // The python created external links are bi-directional, 627644Sali.saidi@arm.com // and the python created internal links are uni-directional. 637644Sali.saidi@arm.com // The networks and topology utilize uni-directional links. 647640Sgblack@eecs.umich.edu // Thus each external link is converted to two calls to addLink, 657640Sgblack@eecs.umich.edu // one for each direction. 667640Sgblack@eecs.umich.edu // 677396Sgblack@eecs.umich.edu // External Links 687375Sgblack@eecs.umich.edu for (vector<BasicExtLink*>::const_iterator i = ext_links.begin(); 697375Sgblack@eecs.umich.edu i != ext_links.end(); ++i) { 707396Sgblack@eecs.umich.edu BasicExtLink *ext_link = (*i); 717396Sgblack@eecs.umich.edu AbstractController *abs_cntrl = ext_link->params()->ext_node; 727396Sgblack@eecs.umich.edu BasicRouter *router = ext_link->params()->int_node; 737396Sgblack@eecs.umich.edu 747396Sgblack@eecs.umich.edu int machine_base_idx = MachineType_base_number(abs_cntrl->getType()); 757396Sgblack@eecs.umich.edu int ext_idx1 = machine_base_idx + abs_cntrl->getVersion(); 767375Sgblack@eecs.umich.edu int ext_idx2 = ext_idx1 + m_nodes; 777375Sgblack@eecs.umich.edu int int_idx = router->params()->router_id + 2*m_nodes; 787375Sgblack@eecs.umich.edu 797396Sgblack@eecs.umich.edu // create the internal uni-directional links in both directions 807375Sgblack@eecs.umich.edu // ext to int 817375Sgblack@eecs.umich.edu addLink(ext_idx1, int_idx, ext_link); 827375Sgblack@eecs.umich.edu // int to ext 837375Sgblack@eecs.umich.edu addLink(int_idx, ext_idx2, ext_link); 847375Sgblack@eecs.umich.edu } 857375Sgblack@eecs.umich.edu 867375Sgblack@eecs.umich.edu // Internal Links 877375Sgblack@eecs.umich.edu for (vector<BasicIntLink*>::const_iterator i = int_links.begin(); 887375Sgblack@eecs.umich.edu i != int_links.end(); ++i) { 897375Sgblack@eecs.umich.edu BasicIntLink *int_link = (*i); 907396Sgblack@eecs.umich.edu BasicRouter *router_src = int_link->params()->src_node; 917375Sgblack@eecs.umich.edu BasicRouter *router_dst = int_link->params()->dst_node; 927375Sgblack@eecs.umich.edu 937396Sgblack@eecs.umich.edu PortDirection src_outport = int_link->params()->src_outport; 947396Sgblack@eecs.umich.edu PortDirection dst_inport = int_link->params()->dst_inport; 957396Sgblack@eecs.umich.edu 967396Sgblack@eecs.umich.edu // Store the IntLink pointers for later 977396Sgblack@eecs.umich.edu m_int_link_vector.push_back(int_link); 987375Sgblack@eecs.umich.edu 997375Sgblack@eecs.umich.edu int src = router_src->params()->router_id + 2*m_nodes; 1007375Sgblack@eecs.umich.edu int dst = router_dst->params()->router_id + 2*m_nodes; 1017396Sgblack@eecs.umich.edu 1027375Sgblack@eecs.umich.edu // create the internal uni-directional link from src to dst 1037375Sgblack@eecs.umich.edu addLink(src, dst, int_link, src_outport, dst_inport); 1047375Sgblack@eecs.umich.edu } 1057375Sgblack@eecs.umich.edu} 1067375Sgblack@eecs.umich.edu 1077375Sgblack@eecs.umich.eduvoid 1087375Sgblack@eecs.umich.eduTopology::createLinks(Network *net) 1097375Sgblack@eecs.umich.edu{ 1107375Sgblack@eecs.umich.edu // Find maximum switchID 1117396Sgblack@eecs.umich.edu SwitchID max_switch_id = 0; 1127375Sgblack@eecs.umich.edu for (LinkMap::const_iterator i = m_link_map.begin(); 1137375Sgblack@eecs.umich.edu i != m_link_map.end(); ++i) { 1147396Sgblack@eecs.umich.edu std::pair<SwitchID, SwitchID> src_dest = (*i).first; 1157396Sgblack@eecs.umich.edu max_switch_id = max(max_switch_id, src_dest.first); 1167396Sgblack@eecs.umich.edu max_switch_id = max(max_switch_id, src_dest.second); 1177396Sgblack@eecs.umich.edu } 1187396Sgblack@eecs.umich.edu 1197396Sgblack@eecs.umich.edu // Initialize weight, latency, and inter switched vectors 1207375Sgblack@eecs.umich.edu int num_switches = max_switch_id+1; 1217375Sgblack@eecs.umich.edu Matrix topology_weights(num_switches, 1227375Sgblack@eecs.umich.edu vector<int>(num_switches, INFINITE_LATENCY)); 1237396Sgblack@eecs.umich.edu Matrix component_latencies(num_switches, 1247375Sgblack@eecs.umich.edu vector<int>(num_switches, -1)); 1257375Sgblack@eecs.umich.edu Matrix component_inter_switches(num_switches, 1267375Sgblack@eecs.umich.edu vector<int>(num_switches, 0)); 1277375Sgblack@eecs.umich.edu 1287375Sgblack@eecs.umich.edu // Set identity weights to zero 1297375Sgblack@eecs.umich.edu for (int i = 0; i < topology_weights.size(); i++) { 1307375Sgblack@eecs.umich.edu topology_weights[i][i] = 0; 1317375Sgblack@eecs.umich.edu } 1327375Sgblack@eecs.umich.edu 1337375Sgblack@eecs.umich.edu // Fill in the topology weights and bandwidth multipliers 1347375Sgblack@eecs.umich.edu for (LinkMap::const_iterator i = m_link_map.begin(); 1357375Sgblack@eecs.umich.edu i != m_link_map.end(); ++i) { 1367396Sgblack@eecs.umich.edu std::pair<int, int> src_dest = (*i).first; 1377375Sgblack@eecs.umich.edu BasicLink* link = (*i).second.link; 1387375Sgblack@eecs.umich.edu int src = src_dest.first; 1397396Sgblack@eecs.umich.edu int dst = src_dest.second; 1407396Sgblack@eecs.umich.edu component_latencies[src][dst] = link->m_latency; 1417396Sgblack@eecs.umich.edu topology_weights[src][dst] = link->m_weight; 1427396Sgblack@eecs.umich.edu } 1437396Sgblack@eecs.umich.edu 1447396Sgblack@eecs.umich.edu // Walk topology and hookup the links 1457375Sgblack@eecs.umich.edu Matrix dist = shortest_path(topology_weights, component_latencies, 1467375Sgblack@eecs.umich.edu component_inter_switches); 1477375Sgblack@eecs.umich.edu 1487396Sgblack@eecs.umich.edu for (int i = 0; i < topology_weights.size(); i++) { 1497375Sgblack@eecs.umich.edu for (int j = 0; j < topology_weights[i].size(); j++) { 1507375Sgblack@eecs.umich.edu int weight = topology_weights[i][j]; 1517375Sgblack@eecs.umich.edu if (weight > 0 && weight != INFINITE_LATENCY) { 1527375Sgblack@eecs.umich.edu NetDest destination_set = 1537375Sgblack@eecs.umich.edu shortest_path_to_node(i, j, topology_weights, dist); 1547375Sgblack@eecs.umich.edu makeLink(net, i, j, destination_set); 1557375Sgblack@eecs.umich.edu } 1567375Sgblack@eecs.umich.edu } 1577375Sgblack@eecs.umich.edu } 1587375Sgblack@eecs.umich.edu} 1597375Sgblack@eecs.umich.edu 160void 161Topology::addLink(SwitchID src, SwitchID dest, BasicLink* link, 162 PortDirection src_outport_dirn, 163 PortDirection dst_inport_dirn) 164{ 165 assert(src <= m_number_of_switches+m_nodes+m_nodes); 166 assert(dest <= m_number_of_switches+m_nodes+m_nodes); 167 168 std::pair<int, int> src_dest_pair; 169 LinkEntry link_entry; 170 171 src_dest_pair.first = src; 172 src_dest_pair.second = dest; 173 link_entry.link = link; 174 link_entry.src_outport_dirn = src_outport_dirn; 175 link_entry.dst_inport_dirn = dst_inport_dirn; 176 m_link_map[src_dest_pair] = link_entry; 177} 178 179void 180Topology::makeLink(Network *net, SwitchID src, SwitchID dest, 181 const NetDest& routing_table_entry) 182{ 183 // Make sure we're not trying to connect two end-point nodes 184 // directly together 185 assert(src >= 2 * m_nodes || dest >= 2 * m_nodes); 186 187 std::pair<int, int> src_dest; 188 LinkEntry link_entry; 189 190 if (src < m_nodes) { 191 src_dest.first = src; 192 src_dest.second = dest; 193 link_entry = m_link_map[src_dest]; 194 net->makeExtInLink(src, dest - (2 * m_nodes), link_entry.link, 195 routing_table_entry); 196 } else if (dest < 2*m_nodes) { 197 assert(dest >= m_nodes); 198 NodeID node = dest - m_nodes; 199 src_dest.first = src; 200 src_dest.second = dest; 201 link_entry = m_link_map[src_dest]; 202 net->makeExtOutLink(src - (2 * m_nodes), node, link_entry.link, 203 routing_table_entry); 204 } else { 205 assert((src >= 2 * m_nodes) && (dest >= 2 * m_nodes)); 206 src_dest.first = src; 207 src_dest.second = dest; 208 link_entry = m_link_map[src_dest]; 209 net->makeInternalLink(src - (2 * m_nodes), dest - (2 * m_nodes), 210 link_entry.link, 211 routing_table_entry, 212 link_entry.src_outport_dirn, 213 link_entry.dst_inport_dirn); 214 } 215} 216 217// The following all-pairs shortest path algorithm is based on the 218// discussion from Cormen et al., Chapter 26.1. 219void 220Topology::extend_shortest_path(Matrix ¤t_dist, Matrix &latencies, 221 Matrix &inter_switches) 222{ 223 bool change = true; 224 int nodes = current_dist.size(); 225 226 while (change) { 227 change = false; 228 for (int i = 0; i < nodes; i++) { 229 for (int j = 0; j < nodes; j++) { 230 int minimum = current_dist[i][j]; 231 int previous_minimum = minimum; 232 int intermediate_switch = -1; 233 for (int k = 0; k < nodes; k++) { 234 minimum = min(minimum, 235 current_dist[i][k] + current_dist[k][j]); 236 if (previous_minimum != minimum) { 237 intermediate_switch = k; 238 inter_switches[i][j] = 239 inter_switches[i][k] + 240 inter_switches[k][j] + 1; 241 } 242 previous_minimum = minimum; 243 } 244 if (current_dist[i][j] != minimum) { 245 change = true; 246 current_dist[i][j] = minimum; 247 assert(intermediate_switch >= 0); 248 assert(intermediate_switch < latencies[i].size()); 249 latencies[i][j] = latencies[i][intermediate_switch] + 250 latencies[intermediate_switch][j]; 251 } 252 } 253 } 254 } 255} 256 257Matrix 258Topology::shortest_path(const Matrix &weights, Matrix &latencies, 259 Matrix &inter_switches) 260{ 261 Matrix dist = weights; 262 extend_shortest_path(dist, latencies, inter_switches); 263 return dist; 264} 265 266bool 267Topology::link_is_shortest_path_to_node(SwitchID src, SwitchID next, 268 SwitchID final, const Matrix &weights, 269 const Matrix &dist) 270{ 271 return weights[src][next] + dist[next][final] == dist[src][final]; 272} 273 274NetDest 275Topology::shortest_path_to_node(SwitchID src, SwitchID next, 276 const Matrix &weights, const Matrix &dist) 277{ 278 NetDest result; 279 int d = 0; 280 int machines; 281 int max_machines; 282 283 machines = MachineType_NUM; 284 max_machines = MachineType_base_number(MachineType_NUM); 285 286 for (int m = 0; m < machines; m++) { 287 for (NodeID i = 0; i < MachineType_base_count((MachineType)m); i++) { 288 // we use "d+max_machines" below since the "destination" 289 // switches for the machines are numbered 290 // [MachineType_base_number(MachineType_NUM)... 291 // 2*MachineType_base_number(MachineType_NUM)-1] for the 292 // component network 293 if (link_is_shortest_path_to_node(src, next, d + max_machines, 294 weights, dist)) { 295 MachineID mach = {(MachineType)m, i}; 296 result.add(mach); 297 } 298 d++; 299 } 300 } 301 302 DPRINTF(RubyNetwork, "Returning shortest path\n" 303 "(src-(2*max_machines)): %d, (next-(2*max_machines)): %d, " 304 "src: %d, next: %d, result: %s\n", 305 (src-(2*max_machines)), (next-(2*max_machines)), 306 src, next, result); 307 308 return result; 309} 310