Topology.cc revision 11793:ef606668d247
14826Ssaidi@eecs.umich.edu/* 24826Ssaidi@eecs.umich.edu * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 34826Ssaidi@eecs.umich.edu * All rights reserved. 44826Ssaidi@eecs.umich.edu * 54826Ssaidi@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 64826Ssaidi@eecs.umich.edu * modification, are permitted provided that the following conditions are 74826Ssaidi@eecs.umich.edu * met: redistributions of source code must retain the above copyright 84826Ssaidi@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 94826Ssaidi@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 104826Ssaidi@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 114826Ssaidi@eecs.umich.edu * documentation and/or other materials provided with the distribution; 124826Ssaidi@eecs.umich.edu * neither the name of the copyright holders nor the names of its 134826Ssaidi@eecs.umich.edu * contributors may be used to endorse or promote products derived from 144826Ssaidi@eecs.umich.edu * this software without specific prior written permission. 154826Ssaidi@eecs.umich.edu * 164826Ssaidi@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 174826Ssaidi@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 184826Ssaidi@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 194826Ssaidi@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 204826Ssaidi@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 214826Ssaidi@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 224826Ssaidi@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 234826Ssaidi@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 244826Ssaidi@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 254826Ssaidi@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 264826Ssaidi@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 274826Ssaidi@eecs.umich.edu */ 284826Ssaidi@eecs.umich.edu 294826Ssaidi@eecs.umich.edu#include "mem/ruby/network/Topology.hh" 304826Ssaidi@eecs.umich.edu 314826Ssaidi@eecs.umich.edu#include <cassert> 324826Ssaidi@eecs.umich.edu 334826Ssaidi@eecs.umich.edu#include "base/trace.hh" 348706Sandreas.hansson@arm.com#include "debug/RubyNetwork.hh" 358780Sgblack@eecs.umich.edu#include "mem/ruby/common/NetDest.hh" 364826Ssaidi@eecs.umich.edu#include "mem/ruby/network/BasicLink.hh" 375569Snate@binkert.org#include "mem/ruby/network/Network.hh" 384826Ssaidi@eecs.umich.edu#include "mem/ruby/slicc_interface/AbstractController.hh" 395569Snate@binkert.org 407707Sgblack@eecs.umich.eduusing namespace std; 414826Ssaidi@eecs.umich.edu 428806Sgblack@eecs.umich.educonst int INFINITE_LATENCY = 10000; // Yes, this is a big hack 438780Sgblack@eecs.umich.edu 448780Sgblack@eecs.umich.edu// Note: In this file, we use the first 2*m_nodes SwitchIDs to 454826Ssaidi@eecs.umich.edu// represent the input and output endpoint links. These really are 468806Sgblack@eecs.umich.edu// not 'switches', as they will not have a Switch object allocated for 478806Sgblack@eecs.umich.edu// them. The first m_nodes SwitchIDs are the links into the network, 488806Sgblack@eecs.umich.edu// the second m_nodes set of SwitchIDs represent the the output queues 498806Sgblack@eecs.umich.edu// of the network. 508806Sgblack@eecs.umich.edu 518806Sgblack@eecs.umich.eduTopology::Topology(uint32_t num_routers, 528806Sgblack@eecs.umich.edu const vector<BasicExtLink *> &ext_links, 538806Sgblack@eecs.umich.edu const vector<BasicIntLink *> &int_links) 548806Sgblack@eecs.umich.edu : m_nodes(ext_links.size()), m_number_of_switches(num_routers), 558852Sandreas.hansson@arm.com m_ext_link_vector(ext_links), m_int_link_vector(int_links) 568852Sandreas.hansson@arm.com{ 578852Sandreas.hansson@arm.com // Total nodes/controllers in network 588852Sandreas.hansson@arm.com assert(m_nodes > 1); 598806Sgblack@eecs.umich.edu 608806Sgblack@eecs.umich.edu // analyze both the internal and external links, create data structures. 614826Ssaidi@eecs.umich.edu // The python created external links are bi-directional, 624826Ssaidi@eecs.umich.edu // and the python created internal links are uni-directional. 636329Sgblack@eecs.umich.edu // The networks and topology utilize uni-directional links. 646329Sgblack@eecs.umich.edu // Thus each external link is converted to two calls to addLink, 656329Sgblack@eecs.umich.edu // one for each direction. 666329Sgblack@eecs.umich.edu // 676329Sgblack@eecs.umich.edu // External Links 686329Sgblack@eecs.umich.edu for (vector<BasicExtLink*>::const_iterator i = ext_links.begin(); 696329Sgblack@eecs.umich.edu i != ext_links.end(); ++i) { 706329Sgblack@eecs.umich.edu BasicExtLink *ext_link = (*i); 716329Sgblack@eecs.umich.edu AbstractController *abs_cntrl = ext_link->params()->ext_node; 726329Sgblack@eecs.umich.edu BasicRouter *router = ext_link->params()->int_node; 736329Sgblack@eecs.umich.edu 746329Sgblack@eecs.umich.edu int machine_base_idx = MachineType_base_number(abs_cntrl->getType()); 756329Sgblack@eecs.umich.edu int ext_idx1 = machine_base_idx + abs_cntrl->getVersion(); 766329Sgblack@eecs.umich.edu int ext_idx2 = ext_idx1 + m_nodes; 776329Sgblack@eecs.umich.edu int int_idx = router->params()->router_id + 2*m_nodes; 787720Sgblack@eecs.umich.edu 796329Sgblack@eecs.umich.edu // create the internal uni-directional links in both directions 806329Sgblack@eecs.umich.edu // ext to int 816329Sgblack@eecs.umich.edu addLink(ext_idx1, int_idx, ext_link); 826329Sgblack@eecs.umich.edu // int to ext 836329Sgblack@eecs.umich.edu addLink(int_idx, ext_idx2, ext_link); 846329Sgblack@eecs.umich.edu } 856329Sgblack@eecs.umich.edu 866329Sgblack@eecs.umich.edu // Internal Links 876329Sgblack@eecs.umich.edu for (vector<BasicIntLink*>::const_iterator i = int_links.begin(); 886329Sgblack@eecs.umich.edu i != int_links.end(); ++i) { 896329Sgblack@eecs.umich.edu BasicIntLink *int_link = (*i); 906329Sgblack@eecs.umich.edu BasicRouter *router_src = int_link->params()->src_node; 916329Sgblack@eecs.umich.edu BasicRouter *router_dst = int_link->params()->dst_node; 926329Sgblack@eecs.umich.edu 936329Sgblack@eecs.umich.edu PortDirection src_outport = int_link->params()->src_outport; 946329Sgblack@eecs.umich.edu PortDirection dst_inport = int_link->params()->dst_inport; 956329Sgblack@eecs.umich.edu 967693SAli.Saidi@ARM.com // Store the IntLink pointers for later 977693SAli.Saidi@ARM.com m_int_link_vector.push_back(int_link); 987693SAli.Saidi@ARM.com 997720Sgblack@eecs.umich.edu int src = router_src->params()->router_id + 2*m_nodes; 1007720Sgblack@eecs.umich.edu int dst = router_dst->params()->router_id + 2*m_nodes; 1017720Sgblack@eecs.umich.edu 1027693SAli.Saidi@ARM.com // create the internal uni-directional link from src to dst 1037693SAli.Saidi@ARM.com addLink(src, dst, int_link, src_outport, dst_inport); 1047693SAli.Saidi@ARM.com } 1054826Ssaidi@eecs.umich.edu} 1064826Ssaidi@eecs.umich.edu 107void 108Topology::createLinks(Network *net) 109{ 110 // Find maximum switchID 111 SwitchID max_switch_id = 0; 112 for (LinkMap::const_iterator i = m_link_map.begin(); 113 i != m_link_map.end(); ++i) { 114 std::pair<SwitchID, SwitchID> src_dest = (*i).first; 115 max_switch_id = max(max_switch_id, src_dest.first); 116 max_switch_id = max(max_switch_id, src_dest.second); 117 } 118 119 // Initialize weight, latency, and inter switched vectors 120 int num_switches = max_switch_id+1; 121 Matrix topology_weights(num_switches, 122 vector<int>(num_switches, INFINITE_LATENCY)); 123 Matrix component_latencies(num_switches, 124 vector<int>(num_switches, -1)); 125 Matrix component_inter_switches(num_switches, 126 vector<int>(num_switches, 0)); 127 128 // Set identity weights to zero 129 for (int i = 0; i < topology_weights.size(); i++) { 130 topology_weights[i][i] = 0; 131 } 132 133 // Fill in the topology weights and bandwidth multipliers 134 for (LinkMap::const_iterator i = m_link_map.begin(); 135 i != m_link_map.end(); ++i) { 136 std::pair<int, int> src_dest = (*i).first; 137 BasicLink* link = (*i).second.link; 138 int src = src_dest.first; 139 int dst = src_dest.second; 140 component_latencies[src][dst] = link->m_latency; 141 topology_weights[src][dst] = link->m_weight; 142 } 143 144 // Walk topology and hookup the links 145 Matrix dist = shortest_path(topology_weights, component_latencies, 146 component_inter_switches); 147 148 for (int i = 0; i < topology_weights.size(); i++) { 149 for (int j = 0; j < topology_weights[i].size(); j++) { 150 int weight = topology_weights[i][j]; 151 if (weight > 0 && weight != INFINITE_LATENCY) { 152 NetDest destination_set = 153 shortest_path_to_node(i, j, topology_weights, dist); 154 makeLink(net, i, j, destination_set); 155 } 156 } 157 } 158} 159 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