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; --- 32 unchanged lines hidden (view full) --- 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 // Note that the python created links are bi-directional, but that the 60 // topology and networks utilize uni-directional links. Thus each 61 // BasicLink is converted to two calls to add link, on for each direction 62 for (vector<BasicExtLink*>::const_iterator i = ext_links.begin(); 63 i != ext_links.end(); ++i) { 64 BasicExtLink *ext_link = (*i); 65 AbstractController *abs_cntrl = ext_link->params()->ext_node; 66 BasicRouter *router = ext_link->params()->int_node; 67 |
68 int machine_base_idx = MachineType_base_number(abs_cntrl->getType()); 69 int ext_idx1 = machine_base_idx + abs_cntrl->getVersion(); 70 int ext_idx2 = ext_idx1 + m_nodes; 71 int int_idx = router->params()->router_id + 2*m_nodes; 72 73 // create the internal uni-directional links in both directions 74 // the first direction is marked: In 75 addLink(ext_idx1, int_idx, ext_link, LinkDirection_In); --- 29 unchanged lines hidden (view full) --- 105 for (LinkMap::const_iterator i = m_link_map.begin(); 106 i != m_link_map.end(); ++i) { 107 std::pair<SwitchID, SwitchID> src_dest = (*i).first; 108 max_switch_id = max(max_switch_id, src_dest.first); 109 max_switch_id = max(max_switch_id, src_dest.second); 110 } 111 112 // Initialize weight, latency, and inter switched vectors |
113 int num_switches = max_switch_id+1; |
114 Matrix topology_weights(num_switches, 115 vector<int>(num_switches, INFINITE_LATENCY)); 116 Matrix component_latencies(num_switches, 117 vector<int>(num_switches, -1)); 118 Matrix component_inter_switches(num_switches, 119 vector<int>(num_switches, 0)); |
120 |
121 // Set identity weights to zero 122 for (int i = 0; i < topology_weights.size(); i++) { 123 topology_weights[i][i] = 0; 124 } 125 126 // Fill in the topology weights and bandwidth multipliers 127 for (LinkMap::const_iterator i = m_link_map.begin(); 128 i != m_link_map.end(); ++i) { 129 std::pair<int, int> src_dest = (*i).first; 130 BasicLink* link = (*i).second.link; 131 int src = src_dest.first; 132 int dst = src_dest.second; |
133 component_latencies[src][dst] = link->m_latency; |
134 topology_weights[src][dst] = link->m_weight; 135 } 136 137 // Walk topology and hookup the links |
138 Matrix dist = shortest_path(topology_weights, component_latencies, 139 component_inter_switches); 140 |
141 for (int i = 0; i < topology_weights.size(); i++) { 142 for (int j = 0; j < topology_weights[i].size(); j++) { 143 int weight = topology_weights[i][j]; 144 if (weight > 0 && weight != INFINITE_LATENCY) { 145 NetDest destination_set = 146 shortest_path_to_node(i, j, topology_weights, dist); 147 makeLink(net, i, j, destination_set); 148 } --- 52 unchanged lines hidden (view full) --- 201 link_entry.link, link_entry.direction, 202 routing_table_entry); 203 } 204} 205 206// The following all-pairs shortest path algorithm is based on the 207// discussion from Cormen et al., Chapter 26.1. 208void |
209Topology::extend_shortest_path(Matrix ¤t_dist, Matrix &latencies, 210 Matrix &inter_switches) |
211{ 212 bool change = true; 213 int nodes = current_dist.size(); 214 215 while (change) { 216 change = false; 217 for (int i = 0; i < nodes; i++) { 218 for (int j = 0; j < nodes; j++) { --- 20 unchanged lines hidden (view full) --- 239 latencies[intermediate_switch][j]; 240 } 241 } 242 } 243 } 244} 245 246Matrix |
247Topology::shortest_path(const Matrix &weights, Matrix &latencies, 248 Matrix &inter_switches) |
249{ 250 Matrix dist = weights; 251 extend_shortest_path(dist, latencies, inter_switches); 252 return dist; 253} 254 255bool |
256Topology::link_is_shortest_path_to_node(SwitchID src, SwitchID next, 257 SwitchID final, const Matrix &weights, 258 const Matrix &dist) |
259{ 260 return weights[src][next] + dist[next][final] == dist[src][final]; 261} 262 263NetDest |
264Topology::shortest_path_to_node(SwitchID src, SwitchID next, 265 const Matrix &weights, const Matrix &dist) |
266{ 267 NetDest result; 268 int d = 0; 269 int machines; 270 int max_machines; 271 272 machines = MachineType_NUM; 273 max_machines = MachineType_base_number(MachineType_NUM); --- 25 unchanged lines hidden --- |