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