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