Topology.cc (10086:bd1089db3a88) Topology.cc (11096:efaacec43726)
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
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)
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)
62{
54{
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
55 // 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
56 assert(m_nodes > 1);
57
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
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
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
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
136 Matrix topology_weights;
137 int num_switches = max_switch_id+1;
113 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);
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));
141
120
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;
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;
171 m_component_latencies[src][dst] = link->m_latency;
133 component_latencies[src][dst] = link->m_latency;
172 topology_weights[src][dst] = link->m_weight;
173 }
174
175 // Walk topology and hookup the links
134 topology_weights[src][dst] = link->m_weight;
135 }
136
137 // Walk topology and hookup the links
176 Matrix dist = shortest_path(topology_weights, m_component_latencies,
177 m_component_inter_switches);
138 Matrix dist = shortest_path(topology_weights, component_latencies,
139 component_inter_switches);
140
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
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
246extend_shortest_path(Matrix& current_dist, Matrix& latencies,
247 Matrix& inter_switches)
209Topology::extend_shortest_path(Matrix &current_dist, Matrix &latencies,
210 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
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
284shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches)
247Topology::shortest_path(const Matrix &weights, Matrix &latencies,
248 Matrix &inter_switches)
285{
286 Matrix dist = weights;
287 extend_shortest_path(dist, latencies, inter_switches);
288 return dist;
289}
290
291bool
249{
250 Matrix dist = weights;
251 extend_shortest_path(dist, latencies, inter_switches);
252 return dist;
253}
254
255bool
292link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final,
293 const Matrix& weights, const Matrix& dist)
256Topology::link_is_shortest_path_to_node(SwitchID src, SwitchID next,
257 SwitchID final, const Matrix &weights,
258 const Matrix &dist)
294{
295 return weights[src][next] + dist[next][final] == dist[src][final];
296}
297
298NetDest
259{
260 return weights[src][next] + dist[next][final] == dist[src][final];
261}
262
263NetDest
299shortest_path_to_node(SwitchID src, SwitchID next, const Matrix& weights,
300 const Matrix& dist)
264Topology::shortest_path_to_node(SwitchID src, SwitchID next,
265 const Matrix &weights, 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 --- 		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 ---