Topology.cc revision 6881
1
2/*
3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
8 * met: redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer;
10 * redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution;
13 * neither the name of the copyright holders nor the names of its
14 * contributors may be used to endorse or promote products derived from
15 * this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30/*
31 * Topology.cc
32 *
33 * Description: See Topology.hh
34 *
35 * $Id$
36 *
37 * */
38
39#include "mem/ruby/network/simple/Topology.hh"
40#include "mem/ruby/common/NetDest.hh"
41#include "mem/ruby/network/Network.hh"
42#include "mem/ruby/slicc_interface/AbstractController.hh"
43#include "mem/protocol/TopologyType.hh"
44#include "mem/gems_common/util.hh"
45#include "mem/protocol/MachineType.hh"
46#include "mem/protocol/Protocol.hh"
47#include "mem/ruby/system/System.hh"
48#include <string>
49
50static const int INFINITE_LATENCY = 10000; // Yes, this is a big hack
51static const int DEFAULT_BW_MULTIPLIER = 1;  // Just to be consistent with above :)
52
53// Note: In this file, we use the first 2*m_nodes SwitchIDs to
54// represent the input and output endpoint links.  These really are
55// not 'switches', as they will not have a Switch object allocated for
56// them. The first m_nodes SwitchIDs are the links into the network,
57// the second m_nodes set of SwitchIDs represent the the output queues
58// of the network.
59
60// Helper functions based on chapter 29 of Cormen et al.
61static void extend_shortest_path(Matrix& current_dist, Matrix& latencies, Matrix& inter_switches);
62static Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches);
63static bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, const Matrix& weights, const Matrix& dist);
64static NetDest shortest_path_to_node(SwitchID src, SwitchID next, const Matrix& weights, const Matrix& dist);
65
66Topology::Topology(const Params *p)
67    : SimObject(p)
68{
69    m_print_config = p->print_config;
70    m_number_of_switches = p->num_int_nodes;
71    // initialize component latencies record
72    m_component_latencies.setSize(0);
73    m_component_inter_switches.setSize(0);
74
75    //
76    // Total nodes/controllers in network
77    // Must make sure this is called after the State Machine constructors
78    //
79    m_nodes = MachineType_base_number(MachineType_NUM);
80    assert(m_nodes > 1);
81
82    if (m_nodes != params()->ext_links.size()) {
83        fatal("m_nodes (%d) != ext_links vector length (%d)\n",
84              m_nodes != params()->ext_links.size());
85    }
86
87    //
88    // First create the links between the endpoints (i.e. controllers) and the
89    // network.
90    //
91  for (vector<ExtLink*>::const_iterator i = params()->ext_links.begin();
92       i != params()->ext_links.end(); ++i)
93  {
94      const ExtLinkParams *p = (*i)->params();
95      AbstractController *c = p->ext_node;
96
97      // Store the controller pointers for later
98      m_controller_vector.insertAtBottom(c);
99
100      int ext_idx1 =
101          MachineType_base_number(c->getMachineType()) + c->getVersion();
102      int ext_idx2 = ext_idx1 + m_nodes;
103      int int_idx = p->int_node + 2*m_nodes;
104
105      // create the links in both directions
106      addLink(ext_idx1, int_idx, p->latency, p->bw_multiplier, p->weight);
107      addLink(int_idx, ext_idx2, p->latency, p->bw_multiplier, p->weight);
108  }
109
110  for (vector<IntLink*>::const_iterator i = params()->int_links.begin();
111       i != params()->int_links.end(); ++i)
112  {
113      const IntLinkParams *p = (*i)->params();
114      int a = p->node_a + 2*m_nodes;
115      int b = p->node_b + 2*m_nodes;
116
117      // create the links in both directions
118      addLink(a, b, p->latency, p->bw_multiplier, p->weight);
119      addLink(b, a, p->latency, p->bw_multiplier, p->weight);
120  }
121}
122
123
124void Topology::initNetworkPtr(Network* net_ptr)
125{
126    for (int cntrl = 0; cntrl < m_controller_vector.size(); cntrl++)
127    {
128        m_controller_vector[cntrl]->initNetworkPtr(net_ptr);
129    }
130}
131
132
133void Topology::createLinks(Network *net, bool isReconfiguration)
134{
135  // Find maximum switchID
136
137  SwitchID max_switch_id = 0;
138  for (int i=0; i<m_links_src_vector.size(); i++) {
139    max_switch_id = max(max_switch_id, m_links_src_vector[i]);
140    max_switch_id = max(max_switch_id, m_links_dest_vector[i]);
141  }
142
143  // Initialize weight vector
144  Matrix topology_weights;
145  Matrix topology_latency;
146  Matrix topology_bw_multis;
147  int num_switches = max_switch_id+1;
148  topology_weights.setSize(num_switches);
149  topology_latency.setSize(num_switches);
150  topology_bw_multis.setSize(num_switches);
151  m_component_latencies.setSize(num_switches);  // FIXME setting the size of a member variable here is a HACK!
152  m_component_inter_switches.setSize(num_switches);  // FIXME setting the size of a member variable here is a HACK!
153  for(int i=0; i<topology_weights.size(); i++) {
154    topology_weights[i].setSize(num_switches);
155    topology_latency[i].setSize(num_switches);
156    topology_bw_multis[i].setSize(num_switches);
157    m_component_latencies[i].setSize(num_switches);
158    m_component_inter_switches[i].setSize(num_switches);  // FIXME setting the size of a member variable here is a HACK!
159    for(int j=0; j<topology_weights[i].size(); j++) {
160      topology_weights[i][j] = INFINITE_LATENCY;
161      topology_latency[i][j] = -1;  // initialize to an invalid value
162      topology_bw_multis[i][j] = -1;  // initialize to an invalid value
163      m_component_latencies[i][j] = -1; // initialize to an invalid value
164      m_component_inter_switches[i][j] = 0;  // initially assume direct connections / no intermediate switches between components
165    }
166  }
167
168  // Set identity weights to zero
169  for(int i=0; i<topology_weights.size(); i++) {
170    topology_weights[i][i] = 0;
171  }
172
173  // Fill in the topology weights and bandwidth multipliers
174  for (int i=0; i<m_links_src_vector.size(); i++) {
175    topology_weights[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_weight_vector[i];
176    topology_latency[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i];
177    m_component_latencies[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i];  // initialize to latency vector
178    topology_bw_multis[m_links_src_vector[i]][m_links_dest_vector[i]] = m_bw_multiplier_vector[i];
179  }
180
181  // Walk topology and hookup the links
182  Matrix dist = shortest_path(topology_weights, m_component_latencies, m_component_inter_switches);
183  for(int i=0; i<topology_weights.size(); i++) {
184    for(int j=0; j<topology_weights[i].size(); j++) {
185      int weight = topology_weights[i][j];
186      int bw_multiplier = topology_bw_multis[i][j];
187      int latency = topology_latency[i][j];
188      if (weight > 0 && weight != INFINITE_LATENCY) {
189        NetDest destination_set = shortest_path_to_node(i, j, topology_weights, dist);
190        assert(latency != -1);
191        makeLink(net, i, j, destination_set, latency, weight, bw_multiplier, isReconfiguration);
192      }
193    }
194  }
195}
196
197SwitchID Topology::newSwitchID()
198{
199  m_number_of_switches++;
200  return m_number_of_switches-1+m_nodes+m_nodes;
201}
202
203void Topology::addLink(SwitchID src, SwitchID dest, int link_latency)
204{
205  addLink(src, dest, link_latency, DEFAULT_BW_MULTIPLIER, link_latency);
206}
207
208void Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier)
209{
210  addLink(src, dest, link_latency, bw_multiplier, link_latency);
211}
212
213void Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier, int link_weight)
214{
215  ASSERT(src <= m_number_of_switches+m_nodes+m_nodes);
216  ASSERT(dest <= m_number_of_switches+m_nodes+m_nodes);
217  m_links_src_vector.insertAtBottom(src);
218  m_links_dest_vector.insertAtBottom(dest);
219  m_links_latency_vector.insertAtBottom(link_latency);
220  m_links_weight_vector.insertAtBottom(link_weight);
221  m_bw_multiplier_vector.insertAtBottom(bw_multiplier);
222}
223
224void Topology::makeLink(Network *net, SwitchID src, SwitchID dest, const NetDest& routing_table_entry, int link_latency, int link_weight, int bw_multiplier, bool isReconfiguration)
225{
226  // Make sure we're not trying to connect two end-point nodes directly together
227  assert((src >= 2*m_nodes) || (dest >= 2*m_nodes));
228
229  if (src < m_nodes) {
230    net->makeInLink(src, dest-(2*m_nodes), routing_table_entry, link_latency, bw_multiplier, isReconfiguration);
231  } else if (dest < 2*m_nodes) {
232    assert(dest >= m_nodes);
233    NodeID node = dest-m_nodes;
234    net->makeOutLink(src-(2*m_nodes), node, routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration);
235  } else {
236    assert((src >= 2*m_nodes) && (dest >= 2*m_nodes));
237    net->makeInternalLink(src-(2*m_nodes), dest-(2*m_nodes), routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration);
238  }
239}
240
241void Topology::printConfig(ostream& out) const
242{
243  if (m_print_config == false) return;
244
245  assert(m_component_latencies.size() > 0);
246
247  out << "--- Begin Topology Print ---" << endl;
248  out << endl;
249  out << "Topology print ONLY indicates the _NETWORK_ latency between two machines" << endl;
250  out << "It does NOT include the latency within the machines" << endl;
251  out << endl;
252  for (int m=0; m<MachineType_NUM; m++) {
253    for (int i=0; i<MachineType_base_count((MachineType)m); i++) {
254      MachineID cur_mach = {(MachineType)m, i};
255      out << cur_mach << " Network Latencies" << endl;
256      for (int n=0; n<MachineType_NUM; n++) {
257        for (int j=0; j<MachineType_base_count((MachineType)n); j++) {
258          MachineID dest_mach = {(MachineType)n, j};
259          if (cur_mach != dest_mach) {
260            int link_latency = m_component_latencies[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j];
261            int intermediate_switches = m_component_inter_switches[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j];
262            out << "  " << cur_mach << " -> " << dest_mach << " net_lat: "
263                << link_latency+intermediate_switches << endl;  // NOTE switches are assumed to have single cycle latency
264          }
265        }
266      }
267      out << endl;
268    }
269  }
270
271  out << "--- End Topology Print ---" << endl;
272}
273
274/**************************************************************************/
275
276// The following all-pairs shortest path algorithm is based on the
277// discussion from Cormen et al., Chapter 26.1.
278
279static void extend_shortest_path(Matrix& current_dist, Matrix& latencies, Matrix& inter_switches)
280{
281  bool change = true;
282  int nodes = current_dist.size();
283
284  while (change) {
285    change = false;
286    for (int i=0; i<nodes; i++) {
287      for (int j=0; j<nodes; j++) {
288        int minimum = current_dist[i][j];
289        int previous_minimum = minimum;
290        int intermediate_switch = -1;
291        for (int k=0; k<nodes; k++) {
292          minimum = min(minimum, current_dist[i][k] + current_dist[k][j]);
293          if (previous_minimum != minimum) {
294            intermediate_switch = k;
295            inter_switches[i][j] = inter_switches[i][k] + inter_switches[k][j] + 1;
296          }
297          previous_minimum = minimum;
298        }
299        if (current_dist[i][j] != minimum) {
300          change = true;
301          current_dist[i][j] = minimum;
302          assert(intermediate_switch >= 0);
303          assert(intermediate_switch < latencies[i].size());
304          latencies[i][j] = latencies[i][intermediate_switch] + latencies[intermediate_switch][j];
305        }
306      }
307    }
308  }
309}
310
311static Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches)
312{
313  Matrix dist = weights;
314  extend_shortest_path(dist, latencies, inter_switches);
315  return dist;
316}
317
318static bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final,
319                                          const Matrix& weights, const Matrix& dist)
320{
321  return (weights[src][next] + dist[next][final] == dist[src][final]);
322}
323
324static NetDest shortest_path_to_node(SwitchID src, SwitchID next,
325                                     const Matrix& weights, const Matrix& dist)
326{
327  NetDest result;
328  int d = 0;
329  int machines;
330  int max_machines;
331
332  machines = MachineType_NUM;
333  max_machines = MachineType_base_number(MachineType_NUM);
334
335  for (int m=0; m<machines; m++) {
336    for (int i=0; i<MachineType_base_count((MachineType)m); i++) {
337      // we use "d+max_machines" below since the "destination" switches for the machines are numbered
338      // [MachineType_base_number(MachineType_NUM)...2*MachineType_base_number(MachineType_NUM)-1]
339      // for the component network
340      if (link_is_shortest_path_to_node(src, next,
341                                        d+max_machines,
342                                        weights, dist)) {
343        MachineID mach = {(MachineType)m, i};
344        result.add(mach);
345      }
346      d++;
347    }
348  }
349
350  DEBUG_MSG(NETWORK_COMP, MedPrio, "returning shortest path");
351  DEBUG_EXPR(NETWORK_COMP, MedPrio, (src-(2*max_machines)));
352  DEBUG_EXPR(NETWORK_COMP, MedPrio, (next-(2*max_machines)));
353  DEBUG_EXPR(NETWORK_COMP, MedPrio, src);
354  DEBUG_EXPR(NETWORK_COMP, MedPrio, next);
355  DEBUG_EXPR(NETWORK_COMP, MedPrio, result);
356  DEBUG_NEWLINE(NETWORK_COMP, MedPrio);
357
358  return result;
359}
360
361Topology *
362TopologyParams::create()
363{
364    return new Topology(this);
365}
366
367Link *
368LinkParams::create()
369{
370    return new Link(this);
371}
372
373ExtLink *
374ExtLinkParams::create()
375{
376    return new ExtLink(this);
377}
378
379IntLink *
380IntLinkParams::create()
381{
382    return new IntLink(this);
383}
384