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
49// Helper functions based on chapter 29 of Cormen et al.
50void extend_shortest_path(Matrix& current_dist, Matrix& latencies,
51 Matrix& inter_switches);
52Matrix shortest_path(const Matrix& weights, Matrix& latencies,
53 Matrix& inter_switches);
54bool link_is_shortest_path_to_node(SwitchID src, SwitchID next,
55 SwitchID final, const Matrix& weights, const Matrix& dist);
56NetDest shortest_path_to_node(SwitchID src, SwitchID next,
57 const Matrix& weights, const Matrix& dist);
58
59Topology::Topology(uint32_t num_routers, vector<BasicExtLink *> ext_links,
60 vector<BasicIntLink *> int_links)
61 : m_number_of_switches(num_routers)
62{
63
64 // initialize component latencies record
65 m_component_latencies.resize(0);
66 m_component_inter_switches.resize(0);
67
68 // Total nodes/controllers in network
69 // Must make sure this is called after the State Machine constructors
70 m_nodes = MachineType_base_number(MachineType_NUM);
71 assert(m_nodes > 1);
72
73 if (m_nodes != ext_links.size()) {
74 fatal("m_nodes (%d) != ext_links vector length (%d)\n",
75 m_nodes, ext_links.size());
76 }
77
78 // analyze both the internal and external links, create data structures
79 // Note that the python created links are bi-directional, but that the
80 // topology and networks utilize uni-directional links. Thus each
81 // BasicLink is converted to two calls to add link, on for each direction
82 for (vector<BasicExtLink*>::const_iterator i = ext_links.begin();
83 i != ext_links.end(); ++i) {
84 BasicExtLink *ext_link = (*i);
85 AbstractController *abs_cntrl = ext_link->params()->ext_node;
86 BasicRouter *router = ext_link->params()->int_node;
87
88 // Store the ExtLink pointers for later
89 m_ext_link_vector.push_back(ext_link);
90
91 int machine_base_idx = MachineType_base_number(abs_cntrl->getType());
92 int ext_idx1 = machine_base_idx + abs_cntrl->getVersion();
93 int ext_idx2 = ext_idx1 + m_nodes;
94 int int_idx = router->params()->router_id + 2*m_nodes;
95
96 // create the internal uni-directional links in both directions
97 // the first direction is marked: In
98 addLink(ext_idx1, int_idx, ext_link, LinkDirection_In);

--- 29 unchanged lines hidden (view full) ---

128 for (LinkMap::const_iterator i = m_link_map.begin();
129 i != m_link_map.end(); ++i) {
130 std::pair<SwitchID, SwitchID> src_dest = (*i).first;
131 max_switch_id = max(max_switch_id, src_dest.first);
132 max_switch_id = max(max_switch_id, src_dest.second);
133 }
134
135 // Initialize weight, latency, and inter switched vectors
136 Matrix topology_weights;
137 int num_switches = max_switch_id+1;
138 topology_weights.resize(num_switches);
139 m_component_latencies.resize(num_switches);
140 m_component_inter_switches.resize(num_switches);
141
142 for (int i = 0; i < topology_weights.size(); i++) {
143 topology_weights[i].resize(num_switches);
144 m_component_latencies[i].resize(num_switches);
145 m_component_inter_switches[i].resize(num_switches);
146
147 for (int j = 0; j < topology_weights[i].size(); j++) {
148 topology_weights[i][j] = INFINITE_LATENCY;
149
150 // initialize to invalid values
151 m_component_latencies[i][j] = -1;
152
153 // initially assume direct connections / no intermediate
154 // switches between components
155 m_component_inter_switches[i][j] = 0;
156 }
157 }
158
159 // Set identity weights to zero
160 for (int i = 0; i < topology_weights.size(); i++) {
161 topology_weights[i][i] = 0;
162 }
163
164 // Fill in the topology weights and bandwidth multipliers
165 for (LinkMap::const_iterator i = m_link_map.begin();
166 i != m_link_map.end(); ++i) {
167 std::pair<int, int> src_dest = (*i).first;
168 BasicLink* link = (*i).second.link;
169 int src = src_dest.first;
170 int dst = src_dest.second;
171 m_component_latencies[src][dst] = link->m_latency;
172 topology_weights[src][dst] = link->m_weight;
173 }
174
175 // Walk topology and hookup the links
176 Matrix dist = shortest_path(topology_weights, m_component_latencies,
177 m_component_inter_switches);
178 for (int i = 0; i < topology_weights.size(); i++) {
179 for (int j = 0; j < topology_weights[i].size(); j++) {
180 int weight = topology_weights[i][j];
181 if (weight > 0 && weight != INFINITE_LATENCY) {
182 NetDest destination_set =
183 shortest_path_to_node(i, j, topology_weights, dist);
184 makeLink(net, i, j, destination_set);
185 }

--- 52 unchanged lines hidden (view full) ---

238 link_entry.link, link_entry.direction,
239 routing_table_entry);
240 }
241}
242
243// The following all-pairs shortest path algorithm is based on the
244// discussion from Cormen et al., Chapter 26.1.
245void
246extend_shortest_path(Matrix& current_dist, Matrix& latencies,
247 Matrix& inter_switches)
248{
249 bool change = true;
250 int nodes = current_dist.size();
251
252 while (change) {
253 change = false;
254 for (int i = 0; i < nodes; i++) {
255 for (int j = 0; j < nodes; j++) {

--- 20 unchanged lines hidden (view full) ---

276 latencies[intermediate_switch][j];
277 }
278 }
279 }
280 }
281}
282
283Matrix
284shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches)
285{
286 Matrix dist = weights;
287 extend_shortest_path(dist, latencies, inter_switches);
288 return dist;
289}
290
291bool
292link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final,
293 const Matrix& weights, const Matrix& dist)
294{
295 return weights[src][next] + dist[next][final] == dist[src][final];
296}
297
298NetDest
299shortest_path_to_node(SwitchID src, SwitchID next, const Matrix& weights,
300 const Matrix& dist)
301{
302 NetDest result;
303 int d = 0;
304 int machines;
305 int max_machines;
306
307 machines = MachineType_NUM;
308 max_machines = MachineType_base_number(MachineType_NUM);

--- 25 unchanged lines hidden ---