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 "base/trace.hh"
32 #include "debug/RubyNetwork.hh"
33 #include "mem/ruby/common/NetDest.hh"
34 #include "mem/ruby/network/BasicLink.hh"
35 #include "mem/ruby/network/Topology.hh"
36 #include "mem/ruby/slicc_interface/AbstractController.hh"
40 const int INFINITE_LATENCY
= 10000; // Yes, this is a big hack
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
49 // Helper functions based on chapter 29 of Cormen et al.
50 void extend_shortest_path(Matrix
& current_dist
, Matrix
& latencies
,
51 Matrix
& inter_switches
);
52 Matrix
shortest_path(const Matrix
& weights
, Matrix
& latencies
,
53 Matrix
& inter_switches
);
54 bool link_is_shortest_path_to_node(SwitchID src
, SwitchID next
,
55 SwitchID final
, const Matrix
& weights
, const Matrix
& dist
);
56 NetDest
shortest_path_to_node(SwitchID src
, SwitchID next
,
57 const Matrix
& weights
, const Matrix
& dist
);
59 Topology::Topology(uint32_t num_routers
, vector
<BasicExtLink
*> ext_links
,
60 vector
<BasicIntLink
*> int_links
)
61 : m_number_of_switches(num_routers
)
64 // initialize component latencies record
65 m_component_latencies
.resize(0);
66 m_component_inter_switches
.resize(0);
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
);
73 if (m_nodes
!= ext_links
.size()) {
74 fatal("m_nodes (%d) != ext_links vector length (%d)\n",
75 m_nodes
, ext_links
.size());
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
;
88 // Store the ExtLink pointers for later
89 m_ext_link_vector
.push_back(ext_link
);
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
;
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
);
99 // the first direction is marked: Out
100 addLink(int_idx
, ext_idx2
, ext_link
, LinkDirection_Out
);
103 for (vector
<BasicIntLink
*>::const_iterator i
= int_links
.begin();
104 i
!= int_links
.end(); ++i
) {
105 BasicIntLink
*int_link
= (*i
);
106 BasicRouter
*router_a
= int_link
->params()->node_a
;
107 BasicRouter
*router_b
= int_link
->params()->node_b
;
109 // Store the IntLink pointers for later
110 m_int_link_vector
.push_back(int_link
);
112 int a
= router_a
->params()->router_id
+ 2*m_nodes
;
113 int b
= router_b
->params()->router_id
+ 2*m_nodes
;
115 // create the internal uni-directional links in both directions
116 // the first direction is marked: In
117 addLink(a
, b
, int_link
, LinkDirection_In
);
118 // the second direction is marked: Out
119 addLink(b
, a
, int_link
, LinkDirection_Out
);
124 Topology::createLinks(Network
*net
)
126 // Find maximum switchID
127 SwitchID max_switch_id
= 0;
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
);
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
);
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
);
147 for (int j
= 0; j
< topology_weights
[i
].size(); j
++) {
148 topology_weights
[i
][j
] = INFINITE_LATENCY
;
150 // initialize to invalid values
151 m_component_latencies
[i
][j
] = -1;
153 // initially assume direct connections / no intermediate
154 // switches between components
155 m_component_inter_switches
[i
][j
] = 0;
159 // Set identity weights to zero
160 for (int i
= 0; i
< topology_weights
.size(); i
++) {
161 topology_weights
[i
][i
] = 0;
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
;
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
);
191 Topology::addLink(SwitchID src
, SwitchID dest
, BasicLink
* link
,
194 assert(src
<= m_number_of_switches
+m_nodes
+m_nodes
);
195 assert(dest
<= m_number_of_switches
+m_nodes
+m_nodes
);
197 std::pair
<int, int> src_dest_pair
;
198 LinkEntry link_entry
;
200 src_dest_pair
.first
= src
;
201 src_dest_pair
.second
= dest
;
202 link_entry
.direction
= dir
;
203 link_entry
.link
= link
;
204 m_link_map
[src_dest_pair
] = link_entry
;
208 Topology::makeLink(Network
*net
, SwitchID src
, SwitchID dest
,
209 const NetDest
& routing_table_entry
)
211 // Make sure we're not trying to connect two end-point nodes
213 assert(src
>= 2 * m_nodes
|| dest
>= 2 * m_nodes
);
215 std::pair
<int, int> src_dest
;
216 LinkEntry link_entry
;
219 src_dest
.first
= src
;
220 src_dest
.second
= dest
;
221 link_entry
= m_link_map
[src_dest
];
222 net
->makeInLink(src
, dest
- (2 * m_nodes
), link_entry
.link
,
223 link_entry
.direction
, routing_table_entry
);
224 } else if (dest
< 2*m_nodes
) {
225 assert(dest
>= m_nodes
);
226 NodeID node
= dest
- m_nodes
;
227 src_dest
.first
= src
;
228 src_dest
.second
= dest
;
229 link_entry
= m_link_map
[src_dest
];
230 net
->makeOutLink(src
- (2 * m_nodes
), node
, link_entry
.link
,
231 link_entry
.direction
, routing_table_entry
);
233 assert((src
>= 2 * m_nodes
) && (dest
>= 2 * m_nodes
));
234 src_dest
.first
= src
;
235 src_dest
.second
= dest
;
236 link_entry
= m_link_map
[src_dest
];
237 net
->makeInternalLink(src
- (2 * m_nodes
), dest
- (2 * m_nodes
),
238 link_entry
.link
, link_entry
.direction
,
239 routing_table_entry
);
243 // The following all-pairs shortest path algorithm is based on the
244 // discussion from Cormen et al., Chapter 26.1.
246 extend_shortest_path(Matrix
& current_dist
, Matrix
& latencies
,
247 Matrix
& inter_switches
)
250 int nodes
= current_dist
.size();
254 for (int i
= 0; i
< nodes
; i
++) {
255 for (int j
= 0; j
< nodes
; j
++) {
256 int minimum
= current_dist
[i
][j
];
257 int previous_minimum
= minimum
;
258 int intermediate_switch
= -1;
259 for (int k
= 0; k
< nodes
; k
++) {
260 minimum
= min(minimum
,
261 current_dist
[i
][k
] + current_dist
[k
][j
]);
262 if (previous_minimum
!= minimum
) {
263 intermediate_switch
= k
;
264 inter_switches
[i
][j
] =
265 inter_switches
[i
][k
] +
266 inter_switches
[k
][j
] + 1;
268 previous_minimum
= minimum
;
270 if (current_dist
[i
][j
] != minimum
) {
272 current_dist
[i
][j
] = minimum
;
273 assert(intermediate_switch
>= 0);
274 assert(intermediate_switch
< latencies
[i
].size());
275 latencies
[i
][j
] = latencies
[i
][intermediate_switch
] +
276 latencies
[intermediate_switch
][j
];
284 shortest_path(const Matrix
& weights
, Matrix
& latencies
, Matrix
& inter_switches
)
286 Matrix dist
= weights
;
287 extend_shortest_path(dist
, latencies
, inter_switches
);
292 link_is_shortest_path_to_node(SwitchID src
, SwitchID next
, SwitchID final
,
293 const Matrix
& weights
, const Matrix
& dist
)
295 return weights
[src
][next
] + dist
[next
][final
] == dist
[src
][final
];
299 shortest_path_to_node(SwitchID src
, SwitchID next
, const Matrix
& weights
,
307 machines
= MachineType_NUM
;
308 max_machines
= MachineType_base_number(MachineType_NUM
);
310 for (int m
= 0; m
< machines
; m
++) {
311 for (NodeID i
= 0; i
< MachineType_base_count((MachineType
)m
); i
++) {
312 // we use "d+max_machines" below since the "destination"
313 // switches for the machines are numbered
314 // [MachineType_base_number(MachineType_NUM)...
315 // 2*MachineType_base_number(MachineType_NUM)-1] for the
317 if (link_is_shortest_path_to_node(src
, next
, d
+ max_machines
,
319 MachineID mach
= {(MachineType
)m
, i
};
326 DPRINTF(RubyNetwork
, "Returning shortest path\n"
327 "(src-(2*max_machines)): %d, (next-(2*max_machines)): %d, "
328 "src: %d, next: %d, result: %s\n",
329 (src
-(2*max_machines
)), (next
-(2*max_machines
)),