gem5  v22.1.0.0
RoutingUnit.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2008 Princeton University
3  * Copyright (c) 2016 Georgia Institute of Technology
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 
32 
33 #include "base/cast.hh"
34 #include "base/compiler.hh"
35 #include "debug/RubyNetwork.hh"
39 
40 namespace gem5
41 {
42 
43 namespace ruby
44 {
45 
46 namespace garnet
47 {
48 
50 {
51  m_router = router;
52  m_routing_table.clear();
53  m_weight_table.clear();
54 }
55 
56 void
58 {
59  if (routing_table_entry.size() > m_routing_table.size()) {
60  m_routing_table.resize(routing_table_entry.size());
61  }
62  for (int v = 0; v < routing_table_entry.size(); v++) {
63  m_routing_table[v].push_back(routing_table_entry[v]);
64  }
65 }
66 
67 void
68 RoutingUnit::addWeight(int link_weight)
69 {
70  m_weight_table.push_back(link_weight);
71 }
72 
73 bool
75 {
76  // If all vnets are supported, return true
77  if (sVnets.size() == 0) {
78  return true;
79  }
80 
81  // Find the vnet in the vector, return true
82  if (std::find(sVnets.begin(), sVnets.end(), vnet) != sVnets.end()) {
83  return true;
84  }
85 
86  // Not supported vnet
87  return false;
88 }
89 
90 /*
91  * This is the default routing algorithm in garnet.
92  * The routing table is populated during topology creation.
93  * Routes can be biased via weight assignments in the topology file.
94  * Correct weight assignments are critical to provide deadlock avoidance.
95  */
96 int
97 RoutingUnit::lookupRoutingTable(int vnet, NetDest msg_destination)
98 {
99  // First find all possible output link candidates
100  // For ordered vnet, just choose the first
101  // (to make sure different packets don't choose different routes)
102  // For unordered vnet, randomly choose any of the links
103  // To have a strict ordering between links, they should be given
104  // different weights in the topology file
105 
106  int output_link = -1;
107  int min_weight = INFINITE_;
108  std::vector<int> output_link_candidates;
109  int num_candidates = 0;
110 
111  // Identify the minimum weight among the candidate output links
112  for (int link = 0; link < m_routing_table[vnet].size(); link++) {
113  if (msg_destination.intersectionIsNotEmpty(
114  m_routing_table[vnet][link])) {
115 
116  if (m_weight_table[link] <= min_weight)
117  min_weight = m_weight_table[link];
118  }
119  }
120 
121  // Collect all candidate output links with this minimum weight
122  for (int link = 0; link < m_routing_table[vnet].size(); link++) {
123  if (msg_destination.intersectionIsNotEmpty(
124  m_routing_table[vnet][link])) {
125 
126  if (m_weight_table[link] == min_weight) {
127  num_candidates++;
128  output_link_candidates.push_back(link);
129  }
130  }
131  }
132 
133  if (output_link_candidates.size() == 0) {
134  fatal("Fatal Error:: No Route exists from this Router.");
135  exit(0);
136  }
137 
138  // Randomly select any candidate output link
139  int candidate = 0;
140  if (!(m_router->get_net_ptr())->isVNetOrdered(vnet))
141  candidate = rand() % num_candidates;
142 
143  output_link = output_link_candidates.at(candidate);
144  return output_link;
145 }
146 
147 
148 void
149 RoutingUnit::addInDirection(PortDirection inport_dirn, int inport_idx)
150 {
151  m_inports_dirn2idx[inport_dirn] = inport_idx;
152  m_inports_idx2dirn[inport_idx] = inport_dirn;
153 }
154 
155 void
156 RoutingUnit::addOutDirection(PortDirection outport_dirn, int outport_idx)
157 {
158  m_outports_dirn2idx[outport_dirn] = outport_idx;
159  m_outports_idx2dirn[outport_idx] = outport_dirn;
160 }
161 
162 // outportCompute() is called by the InputUnit
163 // It calls the routing table by default.
164 // A template for adaptive topology-specific routing algorithm
165 // implementations using port directions rather than a static routing
166 // table is provided here.
167 
168 int
170  PortDirection inport_dirn)
171 {
172  int outport = -1;
173 
174  if (route.dest_router == m_router->get_id()) {
175 
176  // Multiple NIs may be connected to this router,
177  // all with output port direction = "Local"
178  // Get exact outport id from table
179  outport = lookupRoutingTable(route.vnet, route.net_dest);
180  return outport;
181  }
182 
183  // Routing Algorithm set in GarnetNetwork.py
184  // Can be over-ridden from command line using --routing-algorithm = 1
185  RoutingAlgorithm routing_algorithm =
187 
188  switch (routing_algorithm) {
189  case TABLE_: outport =
190  lookupRoutingTable(route.vnet, route.net_dest); break;
191  case XY_: outport =
192  outportComputeXY(route, inport, inport_dirn); break;
193  // any custom algorithm
194  case CUSTOM_: outport =
195  outportComputeCustom(route, inport, inport_dirn); break;
196  default: outport =
197  lookupRoutingTable(route.vnet, route.net_dest); break;
198  }
199 
200  assert(outport != -1);
201  return outport;
202 }
203 
204 // XY routing implemented using port directions
205 // Only for reference purpose in a Mesh
206 // By default Garnet uses the routing table
207 int
209  int inport,
210  PortDirection inport_dirn)
211 {
212  PortDirection outport_dirn = "Unknown";
213 
214  [[maybe_unused]] int num_rows = m_router->get_net_ptr()->getNumRows();
215  int num_cols = m_router->get_net_ptr()->getNumCols();
216  assert(num_rows > 0 && num_cols > 0);
217 
218  int my_id = m_router->get_id();
219  int my_x = my_id % num_cols;
220  int my_y = my_id / num_cols;
221 
222  int dest_id = route.dest_router;
223  int dest_x = dest_id % num_cols;
224  int dest_y = dest_id / num_cols;
225 
226  int x_hops = abs(dest_x - my_x);
227  int y_hops = abs(dest_y - my_y);
228 
229  bool x_dirn = (dest_x >= my_x);
230  bool y_dirn = (dest_y >= my_y);
231 
232  // already checked that in outportCompute() function
233  assert(!(x_hops == 0 && y_hops == 0));
234 
235  if (x_hops > 0) {
236  if (x_dirn) {
237  assert(inport_dirn == "Local" || inport_dirn == "West");
238  outport_dirn = "East";
239  } else {
240  assert(inport_dirn == "Local" || inport_dirn == "East");
241  outport_dirn = "West";
242  }
243  } else if (y_hops > 0) {
244  if (y_dirn) {
245  // "Local" or "South" or "West" or "East"
246  assert(inport_dirn != "North");
247  outport_dirn = "North";
248  } else {
249  // "Local" or "North" or "West" or "East"
250  assert(inport_dirn != "South");
251  outport_dirn = "South";
252  }
253  } else {
254  // x_hops == 0 and y_hops == 0
255  // this is not possible
256  // already checked that in outportCompute() function
257  panic("x_hops == y_hops == 0");
258  }
259 
260  return m_outports_dirn2idx[outport_dirn];
261 }
262 
263 // Template for implementing custom routing algorithm
264 // using port directions. (Example adaptive)
265 int
267  int inport,
268  PortDirection inport_dirn)
269 {
270  panic("%s placeholder executed", __FUNCTION__);
271 }
272 
273 } // namespace garnet
274 } // namespace ruby
275 } // namespace gem5
#define INFINITE_
Definition: CommonTypes.hh:75
bool intersectionIsNotEmpty(const NetDest &other_netDest) const
Definition: NetDest.cc:222
GarnetNetwork * get_net_ptr()
Definition: Router.hh:98
void addOutDirection(PortDirection outport_dirn, int outport)
Definition: RoutingUnit.cc:156
int outportComputeCustom(RouteInfo route, int inport, PortDirection inport_dirn)
Definition: RoutingUnit.cc:266
int lookupRoutingTable(int vnet, NetDest net_dest)
Definition: RoutingUnit.cc:97
void addInDirection(PortDirection inport_dirn, int inport)
Definition: RoutingUnit.cc:149
std::vector< int > m_weight_table
Definition: RoutingUnit.hh:91
std::vector< std::vector< NetDest > > m_routing_table
Definition: RoutingUnit.hh:90
std::map< int, PortDirection > m_inports_idx2dirn
Definition: RoutingUnit.hh:95
int outportComputeXY(RouteInfo route, int inport, PortDirection inport_dirn)
Definition: RoutingUnit.cc:208
void addRoute(std::vector< NetDest > &routing_table_entry)
Definition: RoutingUnit.cc:57
std::map< int, PortDirection > m_outports_idx2dirn
Definition: RoutingUnit.hh:96
bool supportsVnet(int vnet, std::vector< int > sVnets)
Definition: RoutingUnit.cc:74
std::map< PortDirection, int > m_outports_dirn2idx
Definition: RoutingUnit.hh:97
void addWeight(int link_weight)
Definition: RoutingUnit.cc:68
std::map< PortDirection, int > m_inports_dirn2idx
Definition: RoutingUnit.hh:94
int outportCompute(RouteInfo route, int inport, PortDirection inport_dirn)
Definition: RoutingUnit.cc:169
STL vector class.
Definition: stl.hh:37
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:178
#define fatal(...)
This implements a cprintf based fatal() function.
Definition: logging.hh:190
Bitfield< 0 > v
Definition: pagetable.hh:65
Bitfield< 3 > exit
Definition: misc.hh:855
std::string PortDirection
Definition: TypeDefines.hh:44
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....

Generated on Wed Dec 21 2022 10:22:38 for gem5 by doxygen 1.9.1