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/protocol/MachineType.hh"
34 #include "mem/ruby/common/NetDest.hh"
35 #include "mem/ruby/network/BasicLink.hh"
36 #include "mem/ruby/network/Topology.hh"
37 #include "mem/ruby/slicc_interface/AbstractController.hh"
41 const int INFINITE_LATENCY
= 10000; // Yes, this is a big hack
43 // Note: In this file, we use the first 2*m_nodes SwitchIDs to
44 // represent the input and output endpoint links. These really are
45 // not 'switches', as they will not have a Switch object allocated for
46 // them. The first m_nodes SwitchIDs are the links into the network,
47 // the second m_nodes set of SwitchIDs represent the the output queues
50 // Helper functions based on chapter 29 of Cormen et al.
51 void extend_shortest_path(Matrix
& current_dist
, Matrix
& latencies
,
52 Matrix
& inter_switches
);
53 Matrix
shortest_path(const Matrix
& weights
, Matrix
& latencies
,
54 Matrix
& inter_switches
);
55 bool link_is_shortest_path_to_node(SwitchID src
, SwitchID next
,
56 SwitchID final
, const Matrix
& weights
, const Matrix
& dist
);
57 NetDest
shortest_path_to_node(SwitchID src
, SwitchID next
,
58 const Matrix
& weights
, const Matrix
& dist
);
60 Topology::Topology(uint32_t num_routers
, vector
<BasicExtLink
*> ext_links
,
61 vector
<BasicIntLink
*> int_links
)
62 : m_number_of_switches(num_routers
)
65 // initialize component latencies record
66 m_component_latencies
.resize(0);
67 m_component_inter_switches
.resize(0);
69 // Total nodes/controllers in network
70 // Must make sure this is called after the State Machine constructors
71 m_nodes
= MachineType_base_number(MachineType_NUM
);
74 if (m_nodes
!= ext_links
.size()) {
75 fatal("m_nodes (%d) != ext_links vector length (%d)\n",
76 m_nodes
, ext_links
.size());
79 // analyze both the internal and external links, create data structures
80 // Note that the python created links are bi-directional, but that the
81 // topology and networks utilize uni-directional links. Thus each
82 // BasicLink is converted to two calls to add link, on for each direction
83 for (vector
<BasicExtLink
*>::const_iterator i
= ext_links
.begin();
84 i
!= ext_links
.end(); ++i
) {
85 BasicExtLink
*ext_link
= (*i
);
86 AbstractController
*abs_cntrl
= ext_link
->params()->ext_node
;
87 BasicRouter
*router
= ext_link
->params()->int_node
;
89 // Store the ExtLink pointers for later
90 m_ext_link_vector
.push_back(ext_link
);
92 int ext_idx1
= abs_cntrl
->params()->cntrl_id
;
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
, bool isReconfiguration
)
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
<int, int> 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
= shortest_path_to_node(i
, j
,
183 topology_weights
, dist
);
184 makeLink(net
, i
, j
, destination_set
, isReconfiguration
);
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
, bool isReconfiguration
)
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
,
226 } else if (dest
< 2*m_nodes
) {
227 assert(dest
>= m_nodes
);
228 NodeID node
= dest
- m_nodes
;
229 src_dest
.first
= src
;
230 src_dest
.second
= dest
;
231 link_entry
= m_link_map
[src_dest
];
232 net
->makeOutLink(src
- (2 * m_nodes
), node
, link_entry
.link
,
233 link_entry
.direction
,
237 assert((src
>= 2 * m_nodes
) && (dest
>= 2 * m_nodes
));
238 src_dest
.first
= src
;
239 src_dest
.second
= dest
;
240 link_entry
= m_link_map
[src_dest
];
241 net
->makeInternalLink(src
- (2 * m_nodes
), dest
- (2 * m_nodes
),
242 link_entry
.link
, link_entry
.direction
,
243 routing_table_entry
, isReconfiguration
);
247 // The following all-pairs shortest path algorithm is based on the
248 // discussion from Cormen et al., Chapter 26.1.
250 extend_shortest_path(Matrix
& current_dist
, Matrix
& latencies
,
251 Matrix
& inter_switches
)
254 int nodes
= current_dist
.size();
258 for (int i
= 0; i
< nodes
; i
++) {
259 for (int j
= 0; j
< nodes
; j
++) {
260 int minimum
= current_dist
[i
][j
];
261 int previous_minimum
= minimum
;
262 int intermediate_switch
= -1;
263 for (int k
= 0; k
< nodes
; k
++) {
264 minimum
= min(minimum
,
265 current_dist
[i
][k
] + current_dist
[k
][j
]);
266 if (previous_minimum
!= minimum
) {
267 intermediate_switch
= k
;
268 inter_switches
[i
][j
] =
269 inter_switches
[i
][k
] +
270 inter_switches
[k
][j
] + 1;
272 previous_minimum
= minimum
;
274 if (current_dist
[i
][j
] != minimum
) {
276 current_dist
[i
][j
] = minimum
;
277 assert(intermediate_switch
>= 0);
278 assert(intermediate_switch
< latencies
[i
].size());
279 latencies
[i
][j
] = latencies
[i
][intermediate_switch
] +
280 latencies
[intermediate_switch
][j
];
288 shortest_path(const Matrix
& weights
, Matrix
& latencies
, Matrix
& inter_switches
)
290 Matrix dist
= weights
;
291 extend_shortest_path(dist
, latencies
, inter_switches
);
296 link_is_shortest_path_to_node(SwitchID src
, SwitchID next
, SwitchID final
,
297 const Matrix
& weights
, const Matrix
& dist
)
299 return weights
[src
][next
] + dist
[next
][final
] == dist
[src
][final
];
303 shortest_path_to_node(SwitchID src
, SwitchID next
, const Matrix
& weights
,
311 machines
= MachineType_NUM
;
312 max_machines
= MachineType_base_number(MachineType_NUM
);
314 for (int m
= 0; m
< machines
; m
++) {
315 for (int i
= 0; i
< MachineType_base_count((MachineType
)m
); i
++) {
316 // we use "d+max_machines" below since the "destination"
317 // switches for the machines are numbered
318 // [MachineType_base_number(MachineType_NUM)...
319 // 2*MachineType_base_number(MachineType_NUM)-1] for the
321 if (link_is_shortest_path_to_node(src
, next
, d
+ max_machines
,
323 MachineID mach
= {(MachineType
)m
, i
};
330 DPRINTF(RubyNetwork
, "Returning shortest path\n"
331 "(src-(2*max_machines)): %d, (next-(2*max_machines)): %d, "
332 "src: %d, next: %d, result: %s\n",
333 (src
-(2*max_machines
)), (next
-(2*max_machines
)),