Topology.cc revision 11793
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;
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.
15 *
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.
27 */
28
29#include "mem/ruby/network/Topology.hh"
30
31#include <cassert>
32
33#include "base/trace.hh"
34#include "debug/RubyNetwork.hh"
35#include "mem/ruby/common/NetDest.hh"
36#include "mem/ruby/network/BasicLink.hh"
37#include "mem/ruby/network/Network.hh"
38#include "mem/ruby/slicc_interface/AbstractController.hh"
39
40using namespace std;
41
42const int INFINITE_LATENCY = 10000; // Yes, this is a big hack
43
44// Note: In this file, we use the first 2*m_nodes SwitchIDs to
45// represent the input and output endpoint links.  These really are
46// not 'switches', as they will not have a Switch object allocated for
47// them. The first m_nodes SwitchIDs are the links into the network,
48// the second m_nodes set of SwitchIDs represent the the output queues
49// of the network.
50
51Topology::Topology(uint32_t num_routers,
52                   const vector<BasicExtLink *> &ext_links,
53                   const vector<BasicIntLink *> &int_links)
54    : m_nodes(ext_links.size()), m_number_of_switches(num_routers),
55      m_ext_link_vector(ext_links), m_int_link_vector(int_links)
56{
57    // Total nodes/controllers in network
58    assert(m_nodes > 1);
59
60    // analyze both the internal and external links, create data structures.
61    // The python created external links are bi-directional,
62    // and the python created internal links are uni-directional.
63    // The networks and topology utilize uni-directional links.
64    // Thus each external link is converted to two calls to addLink,
65    // one for each direction.
66    //
67    // External Links
68    for (vector<BasicExtLink*>::const_iterator i = ext_links.begin();
69         i != ext_links.end(); ++i) {
70        BasicExtLink *ext_link = (*i);
71        AbstractController *abs_cntrl = ext_link->params()->ext_node;
72        BasicRouter *router = ext_link->params()->int_node;
73
74        int machine_base_idx = MachineType_base_number(abs_cntrl->getType());
75        int ext_idx1 = machine_base_idx + abs_cntrl->getVersion();
76        int ext_idx2 = ext_idx1 + m_nodes;
77        int int_idx = router->params()->router_id + 2*m_nodes;
78
79        // create the internal uni-directional links in both directions
80        // ext to int
81        addLink(ext_idx1, int_idx, ext_link);
82        // int to ext
83        addLink(int_idx, ext_idx2, ext_link);
84    }
85
86    // Internal Links
87    for (vector<BasicIntLink*>::const_iterator i = int_links.begin();
88         i != int_links.end(); ++i) {
89        BasicIntLink *int_link = (*i);
90        BasicRouter *router_src = int_link->params()->src_node;
91        BasicRouter *router_dst = int_link->params()->dst_node;
92
93        PortDirection src_outport = int_link->params()->src_outport;
94        PortDirection dst_inport = int_link->params()->dst_inport;
95
96        // Store the IntLink pointers for later
97        m_int_link_vector.push_back(int_link);
98
99        int src = router_src->params()->router_id + 2*m_nodes;
100        int dst = router_dst->params()->router_id + 2*m_nodes;
101
102        // create the internal uni-directional link from src to dst
103        addLink(src, dst, int_link, src_outport, dst_inport);
104    }
105}
106
107void
108Topology::createLinks(Network *net)
109{
110    // Find maximum switchID
111    SwitchID max_switch_id = 0;
112    for (LinkMap::const_iterator i = m_link_map.begin();
113         i != m_link_map.end(); ++i) {
114        std::pair<SwitchID, SwitchID> src_dest = (*i).first;
115        max_switch_id = max(max_switch_id, src_dest.first);
116        max_switch_id = max(max_switch_id, src_dest.second);
117    }
118
119    // Initialize weight, latency, and inter switched vectors
120    int num_switches = max_switch_id+1;
121    Matrix topology_weights(num_switches,
122            vector<int>(num_switches, INFINITE_LATENCY));
123    Matrix component_latencies(num_switches,
124            vector<int>(num_switches, -1));
125    Matrix component_inter_switches(num_switches,
126            vector<int>(num_switches, 0));
127
128    // Set identity weights to zero
129    for (int i = 0; i < topology_weights.size(); i++) {
130        topology_weights[i][i] = 0;
131    }
132
133    // Fill in the topology weights and bandwidth multipliers
134    for (LinkMap::const_iterator i = m_link_map.begin();
135         i != m_link_map.end(); ++i) {
136        std::pair<int, int> src_dest = (*i).first;
137        BasicLink* link = (*i).second.link;
138        int src = src_dest.first;
139        int dst = src_dest.second;
140        component_latencies[src][dst] = link->m_latency;
141        topology_weights[src][dst] = link->m_weight;
142    }
143
144    // Walk topology and hookup the links
145    Matrix dist = shortest_path(topology_weights, component_latencies,
146                                component_inter_switches);
147
148    for (int i = 0; i < topology_weights.size(); i++) {
149        for (int j = 0; j < topology_weights[i].size(); j++) {
150            int weight = topology_weights[i][j];
151            if (weight > 0 && weight != INFINITE_LATENCY) {
152                NetDest destination_set =
153                        shortest_path_to_node(i, j, topology_weights, dist);
154                makeLink(net, i, j, destination_set);
155            }
156        }
157    }
158}
159
160void
161Topology::addLink(SwitchID src, SwitchID dest, BasicLink* link,
162                  PortDirection src_outport_dirn,
163                  PortDirection dst_inport_dirn)
164{
165    assert(src <= m_number_of_switches+m_nodes+m_nodes);
166    assert(dest <= m_number_of_switches+m_nodes+m_nodes);
167
168    std::pair<int, int> src_dest_pair;
169    LinkEntry link_entry;
170
171    src_dest_pair.first = src;
172    src_dest_pair.second = dest;
173    link_entry.link = link;
174    link_entry.src_outport_dirn = src_outport_dirn;
175    link_entry.dst_inport_dirn  = dst_inport_dirn;
176    m_link_map[src_dest_pair] = link_entry;
177}
178
179void
180Topology::makeLink(Network *net, SwitchID src, SwitchID dest,
181                   const NetDest& routing_table_entry)
182{
183    // Make sure we're not trying to connect two end-point nodes
184    // directly together
185    assert(src >= 2 * m_nodes || dest >= 2 * m_nodes);
186
187    std::pair<int, int> src_dest;
188    LinkEntry link_entry;
189
190    if (src < m_nodes) {
191        src_dest.first = src;
192        src_dest.second = dest;
193        link_entry = m_link_map[src_dest];
194        net->makeExtInLink(src, dest - (2 * m_nodes), link_entry.link,
195                        routing_table_entry);
196    } else if (dest < 2*m_nodes) {
197        assert(dest >= m_nodes);
198        NodeID node = dest - m_nodes;
199        src_dest.first = src;
200        src_dest.second = dest;
201        link_entry = m_link_map[src_dest];
202        net->makeExtOutLink(src - (2 * m_nodes), node, link_entry.link,
203                         routing_table_entry);
204    } else {
205        assert((src >= 2 * m_nodes) && (dest >= 2 * m_nodes));
206        src_dest.first = src;
207        src_dest.second = dest;
208        link_entry = m_link_map[src_dest];
209        net->makeInternalLink(src - (2 * m_nodes), dest - (2 * m_nodes),
210                              link_entry.link,
211                              routing_table_entry,
212                              link_entry.src_outport_dirn,
213                              link_entry.dst_inport_dirn);
214    }
215}
216
217// The following all-pairs shortest path algorithm is based on the
218// discussion from Cormen et al., Chapter 26.1.
219void
220Topology::extend_shortest_path(Matrix &current_dist, Matrix &latencies,
221    Matrix &inter_switches)
222{
223    bool change = true;
224    int nodes = current_dist.size();
225
226    while (change) {
227        change = false;
228        for (int i = 0; i < nodes; i++) {
229            for (int j = 0; j < nodes; j++) {
230                int minimum = current_dist[i][j];
231                int previous_minimum = minimum;
232                int intermediate_switch = -1;
233                for (int k = 0; k < nodes; k++) {
234                    minimum = min(minimum,
235                        current_dist[i][k] + current_dist[k][j]);
236                    if (previous_minimum != minimum) {
237                        intermediate_switch = k;
238                        inter_switches[i][j] =
239                            inter_switches[i][k] +
240                            inter_switches[k][j] + 1;
241                    }
242                    previous_minimum = minimum;
243                }
244                if (current_dist[i][j] != minimum) {
245                    change = true;
246                    current_dist[i][j] = minimum;
247                    assert(intermediate_switch >= 0);
248                    assert(intermediate_switch < latencies[i].size());
249                    latencies[i][j] = latencies[i][intermediate_switch] +
250                        latencies[intermediate_switch][j];
251                }
252            }
253        }
254    }
255}
256
257Matrix
258Topology::shortest_path(const Matrix &weights, Matrix &latencies,
259                        Matrix &inter_switches)
260{
261    Matrix dist = weights;
262    extend_shortest_path(dist, latencies, inter_switches);
263    return dist;
264}
265
266bool
267Topology::link_is_shortest_path_to_node(SwitchID src, SwitchID next,
268                                        SwitchID final, const Matrix &weights,
269                                        const Matrix &dist)
270{
271    return weights[src][next] + dist[next][final] == dist[src][final];
272}
273
274NetDest
275Topology::shortest_path_to_node(SwitchID src, SwitchID next,
276                                const Matrix &weights, const Matrix &dist)
277{
278    NetDest result;
279    int d = 0;
280    int machines;
281    int max_machines;
282
283    machines = MachineType_NUM;
284    max_machines = MachineType_base_number(MachineType_NUM);
285
286    for (int m = 0; m < machines; m++) {
287        for (NodeID i = 0; i < MachineType_base_count((MachineType)m); i++) {
288            // we use "d+max_machines" below since the "destination"
289            // switches for the machines are numbered
290            // [MachineType_base_number(MachineType_NUM)...
291            //  2*MachineType_base_number(MachineType_NUM)-1] for the
292            // component network
293            if (link_is_shortest_path_to_node(src, next, d + max_machines,
294                    weights, dist)) {
295                MachineID mach = {(MachineType)m, i};
296                result.add(mach);
297            }
298            d++;
299        }
300    }
301
302    DPRINTF(RubyNetwork, "Returning shortest path\n"
303            "(src-(2*max_machines)): %d, (next-(2*max_machines)): %d, "
304            "src: %d, next: %d, result: %s\n",
305            (src-(2*max_machines)), (next-(2*max_machines)),
306            src, next, result);
307
308    return result;
309}
310