2 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
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;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #include "debug/RubyNetwork.hh"
32 #include "mem/protocol/MachineType.hh"
33 #include "mem/protocol/Protocol.hh"
34 #include "mem/protocol/TopologyType.hh"
35 #include "mem/ruby/common/NetDest.hh"
36 #include "mem/ruby/network/BasicLink.hh"
37 #include "mem/ruby/network/BasicRouter.hh"
38 #include "mem/ruby/network/Network.hh"
39 #include "mem/ruby/network/Topology.hh"
40 #include "mem/ruby/slicc_interface/AbstractController.hh"
41 #include "mem/ruby/system/System.hh"
45 const int INFINITE_LATENCY
= 10000; // Yes, this is a big hack
49 // Note: In this file, we use the first 2*m_nodes SwitchIDs to
50 // represent the input and output endpoint links. These really are
51 // not 'switches', as they will not have a Switch object allocated for
52 // them. The first m_nodes SwitchIDs are the links into the network,
53 // the second m_nodes set of SwitchIDs represent the the output queues
56 // Helper functions based on chapter 29 of Cormen et al.
57 void extend_shortest_path(Matrix
& current_dist
, Matrix
& latencies
,
58 Matrix
& inter_switches
);
59 Matrix
shortest_path(const Matrix
& weights
, Matrix
& latencies
,
60 Matrix
& inter_switches
);
61 bool link_is_shortest_path_to_node(SwitchID src
, SwitchID next
,
62 SwitchID final
, const Matrix
& weights
, const Matrix
& dist
);
63 NetDest
shortest_path_to_node(SwitchID src
, SwitchID next
,
64 const Matrix
& weights
, const Matrix
& dist
);
66 Topology::Topology(const Params
*p
)
69 m_print_config
= p
->print_config
;
70 m_number_of_switches
= p
->routers
.size();
72 // initialize component latencies record
73 m_component_latencies
.resize(0);
74 m_component_inter_switches
.resize(0);
76 // Total nodes/controllers in network
77 // Must make sure this is called after the State Machine constructors
78 m_nodes
= MachineType_base_number(MachineType_NUM
);
81 if (m_nodes
!= params()->ext_links
.size() &&
82 m_nodes
!= params()->ext_links
.size()) {
83 fatal("m_nodes (%d) != ext_links vector length (%d)\n",
84 m_nodes
!= params()->ext_links
.size());
87 // analyze both the internal and external links, create data structures
88 // Note that the python created links are bi-directional, but that the
89 // topology and networks utilize uni-directional links. Thus each
90 // BasicLink is converted to two calls to add link, on for each direction
91 for (vector
<BasicExtLink
*>::const_iterator i
= params()->ext_links
.begin();
92 i
!= params()->ext_links
.end(); ++i
) {
93 BasicExtLink
*ext_link
= (*i
);
94 AbstractController
*abs_cntrl
= ext_link
->params()->ext_node
;
95 BasicRouter
*router
= ext_link
->params()->int_node
;
97 // Store the controller and ExtLink pointers for later
98 m_controller_vector
.push_back(abs_cntrl
);
99 m_ext_link_vector
.push_back(ext_link
);
101 int ext_idx1
= abs_cntrl
->params()->cntrl_id
;
102 int ext_idx2
= ext_idx1
+ m_nodes
;
103 int int_idx
= router
->params()->router_id
+ 2*m_nodes
;
105 // create the internal uni-directional links in both directions
106 // the first direction is marked: In
107 addLink(ext_idx1
, int_idx
, ext_link
, LinkDirection_In
);
108 // the first direction is marked: Out
109 addLink(int_idx
, ext_idx2
, ext_link
, LinkDirection_Out
);
112 for (vector
<BasicIntLink
*>::const_iterator i
= params()->int_links
.begin();
113 i
!= params()->int_links
.end(); ++i
) {
114 BasicIntLink
*int_link
= (*i
);
115 BasicRouter
*router_a
= int_link
->params()->node_a
;
116 BasicRouter
*router_b
= int_link
->params()->node_b
;
118 // Store the IntLink pointers for later
119 m_int_link_vector
.push_back(int_link
);
121 int a
= router_a
->params()->router_id
+ 2*m_nodes
;
122 int b
= router_b
->params()->router_id
+ 2*m_nodes
;
124 // create the internal uni-directional links in both directions
125 // the first direction is marked: In
126 addLink(a
, b
, int_link
, LinkDirection_In
);
127 // the second direction is marked: Out
128 addLink(b
, a
, int_link
, LinkDirection_Out
);
139 Topology::initNetworkPtr(Network
* net_ptr
)
141 for (vector
<BasicExtLink
*>::const_iterator i
= params()->ext_links
.begin();
142 i
!= params()->ext_links
.end(); ++i
) {
143 BasicExtLink
*ext_link
= (*i
);
144 AbstractController
*abs_cntrl
= ext_link
->params()->ext_node
;
145 abs_cntrl
->initNetworkPtr(net_ptr
);
150 Topology::createLinks(Network
*net
, bool isReconfiguration
)
152 // Find maximum switchID
153 SwitchID max_switch_id
= 0;
154 for (LinkMap::const_iterator i
= m_link_map
.begin();
155 i
!= m_link_map
.end(); ++i
) {
156 std::pair
<int, int> src_dest
= (*i
).first
;
157 max_switch_id
= max(max_switch_id
, src_dest
.first
);
158 max_switch_id
= max(max_switch_id
, src_dest
.second
);
161 // Initialize weight, latency, and inter switched vectors
162 Matrix topology_weights
;
163 int num_switches
= max_switch_id
+1;
164 topology_weights
.resize(num_switches
);
165 m_component_latencies
.resize(num_switches
);
166 m_component_inter_switches
.resize(num_switches
);
168 for (int i
= 0; i
< topology_weights
.size(); i
++) {
169 topology_weights
[i
].resize(num_switches
);
170 m_component_latencies
[i
].resize(num_switches
);
171 m_component_inter_switches
[i
].resize(num_switches
);
173 for (int j
= 0; j
< topology_weights
[i
].size(); j
++) {
174 topology_weights
[i
][j
] = INFINITE_LATENCY
;
176 // initialize to invalid values
177 m_component_latencies
[i
][j
] = -1;
179 // initially assume direct connections / no intermediate
180 // switches between components
181 m_component_inter_switches
[i
][j
] = 0;
185 // Set identity weights to zero
186 for (int i
= 0; i
< topology_weights
.size(); i
++) {
187 topology_weights
[i
][i
] = 0;
190 // Fill in the topology weights and bandwidth multipliers
191 for (LinkMap::const_iterator i
= m_link_map
.begin();
192 i
!= m_link_map
.end(); ++i
) {
193 std::pair
<int, int> src_dest
= (*i
).first
;
194 BasicLink
* link
= (*i
).second
.link
;
195 int src
= src_dest
.first
;
196 int dst
= src_dest
.second
;
197 m_component_latencies
[src
][dst
] = link
->m_latency
;
198 topology_weights
[src
][dst
] = link
->m_weight
;
201 // Walk topology and hookup the links
202 Matrix dist
= shortest_path(topology_weights
, m_component_latencies
,
203 m_component_inter_switches
);
204 for (int i
= 0; i
< topology_weights
.size(); i
++) {
205 for (int j
= 0; j
< topology_weights
[i
].size(); j
++) {
206 int weight
= topology_weights
[i
][j
];
207 if (weight
> 0 && weight
!= INFINITE_LATENCY
) {
208 NetDest destination_set
= shortest_path_to_node(i
, j
,
209 topology_weights
, dist
);
210 makeLink(net
, i
, j
, destination_set
, isReconfiguration
);
217 Topology::addLink(SwitchID src
, SwitchID dest
, BasicLink
* link
,
220 assert(src
<= m_number_of_switches
+m_nodes
+m_nodes
);
221 assert(dest
<= m_number_of_switches
+m_nodes
+m_nodes
);
223 std::pair
<int, int> src_dest_pair
;
224 LinkEntry link_entry
;
226 src_dest_pair
.first
= src
;
227 src_dest_pair
.second
= dest
;
228 link_entry
.direction
= dir
;
229 link_entry
.link
= link
;
230 m_link_map
[src_dest_pair
] = link_entry
;
234 Topology::makeLink(Network
*net
, SwitchID src
, SwitchID dest
,
235 const NetDest
& routing_table_entry
, bool isReconfiguration
)
237 // Make sure we're not trying to connect two end-point nodes
239 assert(src
>= 2 * m_nodes
|| dest
>= 2 * m_nodes
);
241 std::pair
<int, int> src_dest
;
242 LinkEntry link_entry
;
245 src_dest
.first
= src
;
246 src_dest
.second
= dest
;
247 link_entry
= m_link_map
[src_dest
];
248 net
->makeInLink(src
, dest
- (2 * m_nodes
), link_entry
.link
,
249 link_entry
.direction
,
252 } else if (dest
< 2*m_nodes
) {
253 assert(dest
>= m_nodes
);
254 NodeID node
= dest
- m_nodes
;
255 src_dest
.first
= src
;
256 src_dest
.second
= dest
;
257 link_entry
= m_link_map
[src_dest
];
258 net
->makeOutLink(src
- (2 * m_nodes
), node
, link_entry
.link
,
259 link_entry
.direction
,
263 assert((src
>= 2 * m_nodes
) && (dest
>= 2 * m_nodes
));
264 src_dest
.first
= src
;
265 src_dest
.second
= dest
;
266 link_entry
= m_link_map
[src_dest
];
267 net
->makeInternalLink(src
- (2 * m_nodes
), dest
- (2 * m_nodes
),
268 link_entry
.link
, link_entry
.direction
,
269 routing_table_entry
, isReconfiguration
);
274 Topology::printStats(std::ostream
& out
) const
276 for (int cntrl
= 0; cntrl
< m_controller_vector
.size(); cntrl
++) {
277 m_controller_vector
[cntrl
]->printStats(out
);
282 Topology::clearStats()
284 for (int cntrl
= 0; cntrl
< m_controller_vector
.size(); cntrl
++) {
285 m_controller_vector
[cntrl
]->clearStats();
290 Topology::printConfig(std::ostream
& out
) const
292 if (m_print_config
== false)
295 assert(m_component_latencies
.size() > 0);
297 out
<< "--- Begin Topology Print ---" << endl
299 << "Topology print ONLY indicates the _NETWORK_ latency between two "
300 << "machines" << endl
301 << "It does NOT include the latency within the machines" << endl
304 for (int m
= 0; m
< MachineType_NUM
; m
++) {
305 int i_end
= MachineType_base_count((MachineType
)m
);
306 for (int i
= 0; i
< i_end
; i
++) {
307 MachineID cur_mach
= {(MachineType
)m
, i
};
308 out
<< cur_mach
<< " Network Latencies" << endl
;
309 for (int n
= 0; n
< MachineType_NUM
; n
++) {
310 int j_end
= MachineType_base_count((MachineType
)n
);
311 for (int j
= 0; j
< j_end
; j
++) {
312 MachineID dest_mach
= {(MachineType
)n
, j
};
313 if (cur_mach
== dest_mach
)
316 int src
= MachineType_base_number((MachineType
)m
) + i
;
317 int dst
= MachineType_base_number(MachineType_NUM
) +
318 MachineType_base_number((MachineType
)n
) + j
;
319 int link_latency
= m_component_latencies
[src
][dst
];
320 int intermediate_switches
=
321 m_component_inter_switches
[src
][dst
];
323 // NOTE switches are assumed to have single
325 out
<< " " << cur_mach
<< " -> " << dest_mach
327 << link_latency
+ intermediate_switches
<< endl
;
334 out
<< "--- End Topology Print ---" << endl
;
337 // The following all-pairs shortest path algorithm is based on the
338 // discussion from Cormen et al., Chapter 26.1.
340 extend_shortest_path(Matrix
& current_dist
, Matrix
& latencies
,
341 Matrix
& inter_switches
)
344 int nodes
= current_dist
.size();
348 for (int i
= 0; i
< nodes
; i
++) {
349 for (int j
= 0; j
< nodes
; j
++) {
350 int minimum
= current_dist
[i
][j
];
351 int previous_minimum
= minimum
;
352 int intermediate_switch
= -1;
353 for (int k
= 0; k
< nodes
; k
++) {
354 minimum
= min(minimum
,
355 current_dist
[i
][k
] + current_dist
[k
][j
]);
356 if (previous_minimum
!= minimum
) {
357 intermediate_switch
= k
;
358 inter_switches
[i
][j
] =
359 inter_switches
[i
][k
] +
360 inter_switches
[k
][j
] + 1;
362 previous_minimum
= minimum
;
364 if (current_dist
[i
][j
] != minimum
) {
366 current_dist
[i
][j
] = minimum
;
367 assert(intermediate_switch
>= 0);
368 assert(intermediate_switch
< latencies
[i
].size());
369 latencies
[i
][j
] = latencies
[i
][intermediate_switch
] +
370 latencies
[intermediate_switch
][j
];
378 shortest_path(const Matrix
& weights
, Matrix
& latencies
, Matrix
& inter_switches
)
380 Matrix dist
= weights
;
381 extend_shortest_path(dist
, latencies
, inter_switches
);
386 link_is_shortest_path_to_node(SwitchID src
, SwitchID next
, SwitchID final
,
387 const Matrix
& weights
, const Matrix
& dist
)
389 return weights
[src
][next
] + dist
[next
][final
] == dist
[src
][final
];
393 shortest_path_to_node(SwitchID src
, SwitchID next
, const Matrix
& weights
,
401 machines
= MachineType_NUM
;
402 max_machines
= MachineType_base_number(MachineType_NUM
);
404 for (int m
= 0; m
< machines
; m
++) {
405 for (int i
= 0; i
< MachineType_base_count((MachineType
)m
); i
++) {
406 // we use "d+max_machines" below since the "destination"
407 // switches for the machines are numbered
408 // [MachineType_base_number(MachineType_NUM)...
409 // 2*MachineType_base_number(MachineType_NUM)-1] for the
411 if (link_is_shortest_path_to_node(src
, next
, d
+ max_machines
,
413 MachineID mach
= {(MachineType
)m
, i
};
420 DPRINTF(RubyNetwork
, "Returning shortest path\n"
421 "(src-(2*max_machines)): %d, (next-(2*max_machines)): %d, "
422 "src: %d, next: %d, result: %s\n",
423 (src
-(2*max_machines
)), (next
-(2*max_machines
)),
430 TopologyParams::create()
432 return new Topology(this);