gem5  v21.1.0.2
SwitchAllocator.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2020 Inria
3  * Copyright (c) 2016 Georgia Institute of Technology
4  * Copyright (c) 2008 Princeton University
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions are
9  * met: redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer;
11  * redistributions in binary form must reproduce the above copyright
12  * notice, this list of conditions and the following disclaimer in the
13  * documentation and/or other materials provided with the distribution;
14  * neither the name of the copyright holders nor the names of its
15  * contributors may be used to endorse or promote products derived from
16  * this software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  */
30 
31 
33 
34 #include "debug/RubyNetwork.hh"
39 
40 namespace gem5
41 {
42 
43 namespace ruby
44 {
45 
46 namespace garnet
47 {
48 
50  : Consumer(router)
51 {
52  m_router = router;
55 
58 }
59 
60 void
62 {
69 
70  for (int i = 0; i < m_num_inports; i++) {
71  m_round_robin_invc[i] = 0;
72  m_port_requests[i] = -1;
73  m_vc_winners[i] = -1;
74  }
75 
76  for (int i = 0; i < m_num_outports; i++) {
78  }
79 }
80 
81 /*
82  * The wakeup function of the SwitchAllocator performs a 2-stage
83  * seperable switch allocation. At the end of the 2nd stage, a free
84  * output VC is assigned to the winning flits of each output port.
85  * There is no separate VCAllocator stage like the one in garnet1.0.
86  * At the end of this function, the router is rescheduled to wakeup
87  * next cycle for peforming SA for any flits ready next cycle.
88  */
89 
90 void
92 {
93  arbitrate_inports(); // First stage of allocation
94  arbitrate_outports(); // Second stage of allocation
95 
98 }
99 
100 /*
101  * SA-I (or SA-i) loops through all input VCs at every input port,
102  * and selects one in a round robin manner.
103  * - For HEAD/HEAD_TAIL flits only selects an input VC whose output port
104  * has at least one free output VC.
105  * - For BODY/TAIL flits, only selects an input VC that has credits
106  * in its output VC.
107  * Places a request for the output port from this input VC.
108  */
109 
110 void
112 {
113  // Select a VC from each input in a round robin manner
114  // Independent arbiter at each input port
115  for (int inport = 0; inport < m_num_inports; inport++) {
116  int invc = m_round_robin_invc[inport];
117 
118  for (int invc_iter = 0; invc_iter < m_num_vcs; invc_iter++) {
119  auto input_unit = m_router->getInputUnit(inport);
120 
121  if (input_unit->need_stage(invc, SA_, curTick())) {
122  // This flit is in SA stage
123 
124  int outport = input_unit->get_outport(invc);
125  int outvc = input_unit->get_outvc(invc);
126 
127  // check if the flit in this InputVC is allowed to be sent
128  // send_allowed conditions described in that function.
129  bool make_request =
130  send_allowed(inport, invc, outport, outvc);
131 
132  if (make_request) {
134  m_port_requests[inport] = outport;
135  m_vc_winners[inport] = invc;
136 
137  break; // got one vc winner for this port
138  }
139  }
140 
141  invc++;
142  if (invc >= m_num_vcs)
143  invc = 0;
144  }
145  }
146 }
147 
148 /*
149  * SA-II (or SA-o) loops through all output ports,
150  * and selects one input VC (that placed a request during SA-I)
151  * as the winner for this output port in a round robin manner.
152  * - For HEAD/HEAD_TAIL flits, performs simplified outvc allocation.
153  * (i.e., select a free VC from the output port).
154  * - For BODY/TAIL flits, decrement a credit in the output vc.
155  * The winning flit is read out from the input VC and sent to the
156  * CrossbarSwitch.
157  * An increment_credit signal is sent from the InputUnit
158  * to the upstream router. For HEAD_TAIL/TAIL flits, is_free_signal in the
159  * credit is set to true.
160  */
161 
162 void
164 {
165  // Now there are a set of input vc requests for output vcs.
166  // Again do round robin arbitration on these requests
167  // Independent arbiter at each output port
168  for (int outport = 0; outport < m_num_outports; outport++) {
169  int inport = m_round_robin_inport[outport];
170 
171  for (int inport_iter = 0; inport_iter < m_num_inports;
172  inport_iter++) {
173 
174  // inport has a request this cycle for outport
175  if (m_port_requests[inport] == outport) {
176  auto output_unit = m_router->getOutputUnit(outport);
177  auto input_unit = m_router->getInputUnit(inport);
178 
179  // grant this outport to this inport
180  int invc = m_vc_winners[inport];
181 
182  int outvc = input_unit->get_outvc(invc);
183  if (outvc == -1) {
184  // VC Allocation - select any free VC from outport
185  outvc = vc_allocate(outport, inport, invc);
186  }
187 
188  // remove flit from Input VC
189  flit *t_flit = input_unit->getTopFlit(invc);
190 
191  DPRINTF(RubyNetwork, "SwitchAllocator at Router %d "
192  "granted outvc %d at outport %d "
193  "to invc %d at inport %d to flit %s at "
194  "cycle: %lld\n",
195  m_router->get_id(), outvc,
197  output_unit->get_direction()),
198  invc,
200  input_unit->get_direction()),
201  *t_flit,
202  m_router->curCycle());
203 
204 
205  // Update outport field in the flit since this is
206  // used by CrossbarSwitch code to send it out of
207  // correct outport.
208  // Note: post route compute in InputUnit,
209  // outport is updated in VC, but not in flit
210  t_flit->set_outport(outport);
211 
212  // set outvc (i.e., invc for next hop) in flit
213  // (This was updated in VC by vc_allocate, but not in flit)
214  t_flit->set_vc(outvc);
215 
216  // decrement credit in outvc
217  output_unit->decrement_credit(outvc);
218 
219  // flit ready for Switch Traversal
220  t_flit->advance_stage(ST_, curTick());
221  m_router->grant_switch(inport, t_flit);
223 
224  if ((t_flit->get_type() == TAIL_) ||
225  t_flit->get_type() == HEAD_TAIL_) {
226 
227  // This Input VC should now be empty
228  assert(!(input_unit->isReady(invc, curTick())));
229 
230  // Free this VC
231  input_unit->set_vc_idle(invc, curTick());
232 
233  // Send a credit back
234  // along with the information that this VC is now idle
235  input_unit->increment_credit(invc, true, curTick());
236  } else {
237  // Send a credit back
238  // but do not indicate that the VC is idle
239  input_unit->increment_credit(invc, false, curTick());
240  }
241 
242  // remove this request
243  m_port_requests[inport] = -1;
244 
245  // Update Round Robin pointer
246  m_round_robin_inport[outport] = inport + 1;
247  if (m_round_robin_inport[outport] >= m_num_inports)
248  m_round_robin_inport[outport] = 0;
249 
250  // Update Round Robin pointer to the next VC
251  // We do it here to keep it fair.
252  // Only the VC which got switch traversal
253  // is updated.
254  m_round_robin_invc[inport] = invc + 1;
255  if (m_round_robin_invc[inport] >= m_num_vcs)
256  m_round_robin_invc[inport] = 0;
257 
258 
259  break; // got a input winner for this outport
260  }
261 
262  inport++;
263  if (inport >= m_num_inports)
264  inport = 0;
265  }
266  }
267 }
268 
269 /*
270  * A flit can be sent only if
271  * (1) there is at least one free output VC at the
272  * output port (for HEAD/HEAD_TAIL),
273  * or
274  * (2) if there is at least one credit (i.e., buffer slot)
275  * within the VC for BODY/TAIL flits of multi-flit packets.
276  * and
277  * (3) pt-to-pt ordering is not violated in ordered vnets, i.e.,
278  * there should be no other flit in this input port
279  * within an ordered vnet
280  * that arrived before this flit and is requesting the same output port.
281  */
282 
283 bool
284 SwitchAllocator::send_allowed(int inport, int invc, int outport, int outvc)
285 {
286  // Check if outvc needed
287  // Check if credit needed (for multi-flit packet)
288  // Check if ordering violated (in ordered vnet)
289 
290  int vnet = get_vnet(invc);
291  bool has_outvc = (outvc != -1);
292  bool has_credit = false;
293 
294  auto output_unit = m_router->getOutputUnit(outport);
295  if (!has_outvc) {
296 
297  // needs outvc
298  // this is only true for HEAD and HEAD_TAIL flits.
299 
300  if (output_unit->has_free_vc(vnet)) {
301 
302  has_outvc = true;
303 
304  // each VC has at least one buffer,
305  // so no need for additional credit check
306  has_credit = true;
307  }
308  } else {
309  has_credit = output_unit->has_credit(outvc);
310  }
311 
312  // cannot send if no outvc or no credit.
313  if (!has_outvc || !has_credit)
314  return false;
315 
316 
317  // protocol ordering check
318  if ((m_router->get_net_ptr())->isVNetOrdered(vnet)) {
319  auto input_unit = m_router->getInputUnit(inport);
320 
321  // enqueue time of this flit
322  Tick t_enqueue_time = input_unit->get_enqueue_time(invc);
323 
324  // check if any other flit is ready for SA and for same output port
325  // and was enqueued before this flit
326  int vc_base = vnet*m_vc_per_vnet;
327  for (int vc_offset = 0; vc_offset < m_vc_per_vnet; vc_offset++) {
328  int temp_vc = vc_base + vc_offset;
329  if (input_unit->need_stage(temp_vc, SA_, curTick()) &&
330  (input_unit->get_outport(temp_vc) == outport) &&
331  (input_unit->get_enqueue_time(temp_vc) < t_enqueue_time)) {
332  return false;
333  }
334  }
335  }
336 
337  return true;
338 }
339 
340 // Assign a free VC to the winner of the output port.
341 int
342 SwitchAllocator::vc_allocate(int outport, int inport, int invc)
343 {
344  // Select a free VC from the output port
345  int outvc =
346  m_router->getOutputUnit(outport)->select_free_vc(get_vnet(invc));
347 
348  // has to get a valid VC since it checked before performing SA
349  assert(outvc != -1);
350  m_router->getInputUnit(inport)->grant_outvc(invc, outvc);
351  return outvc;
352 }
353 
354 // Wakeup the router next cycle to perform SA again
355 // if there are flits ready.
356 void
358 {
359  Tick nextCycle = m_router->clockEdge(Cycles(1));
360 
361  if (m_router->alreadyScheduled(nextCycle)) {
362  return;
363  }
364 
365  for (int i = 0; i < m_num_inports; i++) {
366  for (int j = 0; j < m_num_vcs; j++) {
367  if (m_router->getInputUnit(i)->need_stage(j, SA_, nextCycle)) {
369  return;
370  }
371  }
372  }
373 }
374 
375 int
377 {
378  int vnet = invc/m_vc_per_vnet;
379  assert(vnet < m_router->get_num_vnets());
380  return vnet;
381 }
382 
383 
384 // Clear the request vector within the allocator at end of SA-II.
385 // Was populated by SA-I.
386 void
388 {
389  std::fill(m_port_requests.begin(), m_port_requests.end(), -1);
390 }
391 
392 void
394 {
397 }
398 
399 } // namespace garnet
400 } // namespace ruby
401 } // namespace gem5
gem5::ruby::garnet::SwitchAllocator::SwitchAllocator
SwitchAllocator(Router *router)
Definition: SwitchAllocator.cc:49
gem5::curTick
Tick curTick()
The universal simulation clock.
Definition: cur_tick.hh:46
gem5::ruby::garnet::SwitchAllocator::vc_allocate
int vc_allocate(int outport, int inport, int invc)
Definition: SwitchAllocator.cc:342
gem5::ruby::garnet::Router::getInputUnit
InputUnit * getInputUnit(unsigned port)
Definition: Router.hh:101
gem5::ruby::garnet::flit
Definition: flit.hh:50
gem5::MipsISA::fill
fill
Definition: pra_constants.hh:57
gem5::ruby::garnet::SwitchAllocator::m_num_vcs
int m_num_vcs
Definition: SwitchAllocator.hh:84
gem5::ruby::garnet::SwitchAllocator::m_input_arbiter_activity
double m_input_arbiter_activity
Definition: SwitchAllocator.hh:86
gem5::ruby::garnet::Router::get_net_ptr
GarnetNetwork * get_net_ptr()
Definition: Router.hh:98
gem5::ruby::garnet::flit::set_vc
void set_vc(int vc)
Definition: flit.hh:75
gem5::Clocked::curCycle
Cycles curCycle() const
Determine the current cycle, corresponding to a tick aligned to a clock edge.
Definition: clocked_object.hh:195
gem5::ruby::garnet::InputUnit::get_outport
int get_outport(int invc)
Definition: InputUnit.hh:91
gem5::ruby::garnet::HEAD_TAIL_
@ HEAD_TAIL_
Definition: CommonTypes.hh:47
gem5::ruby::garnet::SwitchAllocator::m_num_outports
int m_num_outports
Definition: SwitchAllocator.hh:83
gem5::ruby::garnet::SA_
@ SA_
Definition: CommonTypes.hh:51
gem5::ruby::garnet::SwitchAllocator::get_vnet
int get_vnet(int invc)
Definition: SwitchAllocator.cc:376
gem5::ruby::garnet::SwitchAllocator::m_num_inports
int m_num_inports
Definition: SwitchAllocator.hh:83
gem5::ruby::garnet::SwitchAllocator::m_port_requests
std::vector< int > m_port_requests
Definition: SwitchAllocator.hh:91
InputUnit.hh
gem5::ruby::garnet::Router
Definition: Router.hh:66
gem5::ruby::garnet::Router::get_num_outports
int get_num_outports()
Definition: Router.hh:90
gem5::ruby::garnet::SwitchAllocator::send_allowed
bool send_allowed(int inport, int invc, int outport, int outvc)
Definition: SwitchAllocator.cc:284
gem5::ruby::garnet::SwitchAllocator::m_vc_per_vnet
int m_vc_per_vnet
Definition: SwitchAllocator.hh:84
gem5::ruby::garnet::SwitchAllocator::resetStats
void resetStats()
Definition: SwitchAllocator.cc:393
GarnetNetwork.hh
gem5::ruby::Consumer
Definition: Consumer.hh:61
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:66
gem5::ruby::garnet::Router::get_num_vcs
uint32_t get_num_vcs()
Definition: Router.hh:86
gem5::Cycles
Cycles is a wrapper class for representing cycle counts, i.e.
Definition: types.hh:78
gem5::ArmISA::j
Bitfield< 24 > j
Definition: misc_types.hh:57
DPRINTF
#define DPRINTF(x,...)
Definition: trace.hh:186
gem5::ruby::garnet::OutputUnit::has_credit
bool has_credit(int out_vc)
Definition: OutputUnit.cc:89
gem5::Tick
uint64_t Tick
Tick count type.
Definition: types.hh:58
gem5::ruby::garnet::Router::grant_switch
void grant_switch(int inport, flit *t_flit)
Definition: Router.cc:168
gem5::ruby::garnet::SwitchAllocator::arbitrate_inports
void arbitrate_inports()
Definition: SwitchAllocator.cc:111
gem5::ruby::garnet::SwitchAllocator::check_for_wakeup
void check_for_wakeup()
Definition: SwitchAllocator.cc:357
gem5::ruby::garnet::SwitchAllocator::m_vc_winners
std::vector< int > m_vc_winners
Definition: SwitchAllocator.hh:92
SwitchAllocator.hh
gem5::ruby::garnet::ST_
@ ST_
Definition: CommonTypes.hh:51
gem5::ruby::garnet::SwitchAllocator::m_round_robin_inport
std::vector< int > m_round_robin_inport
Definition: SwitchAllocator.hh:90
gem5::Clocked::clockEdge
Tick clockEdge(Cycles cycles=Cycles(0)) const
Determine the tick when a cycle begins, by default the current one, but the argument also enables the...
Definition: clocked_object.hh:177
gem5::ruby::garnet::SwitchAllocator::m_router
Router * m_router
Definition: SwitchAllocator.hh:88
gem5::ruby::garnet::InputUnit::get_enqueue_time
Tick get_enqueue_time(int invc)
Definition: InputUnit.hh:103
OutputUnit.hh
gem5::ruby::garnet::flit::advance_stage
void advance_stage(flit_stage t_stage, Tick newTime)
Definition: flit.hh:92
gem5::ruby::garnet::SwitchAllocator::init
void init()
Definition: SwitchAllocator.cc:61
gem5::ruby::garnet::flit::set_outport
void set_outport(int port)
Definition: flit.hh:73
gem5::ruby::garnet::Router::get_num_inports
int get_num_inports()
Definition: Router.hh:89
gem5::ruby::garnet::Router::get_vc_per_vnet
uint32_t get_vc_per_vnet()
Definition: Router.hh:88
gem5::ruby::garnet::TAIL_
@ TAIL_
Definition: CommonTypes.hh:47
gem5::ruby::garnet::InputUnit::grant_outvc
void grant_outvc(int vc, int outvc)
Definition: InputUnit.hh:85
gem5::ruby::garnet::Router::getPortDirectionName
std::string getPortDirectionName(PortDirection direction)
Definition: Router.cc:181
gem5::ruby::garnet::Router::schedule_wakeup
void schedule_wakeup(Cycles time)
Definition: Router.cc:174
gem5::ruby::garnet::flit::get_type
flit_type get_type()
Definition: flit.hh:69
gem5::ruby::garnet::Router::get_id
int get_id()
Definition: Router.hh:91
gem5::ruby::garnet::SwitchAllocator::arbitrate_outports
void arbitrate_outports()
Definition: SwitchAllocator.cc:163
gem5::ruby::garnet::Router::getOutputUnit
OutputUnit * getOutputUnit(unsigned port)
Definition: Router.hh:108
gem5::ruby::garnet::SwitchAllocator::wakeup
void wakeup()
Definition: SwitchAllocator.cc:91
gem5::ruby::garnet::SwitchAllocator::m_round_robin_invc
std::vector< int > m_round_robin_invc
Definition: SwitchAllocator.hh:89
gem5::ruby::garnet::SwitchAllocator::clear_request_vector
void clear_request_vector()
Definition: SwitchAllocator.cc:387
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::ruby::garnet::OutputUnit::select_free_vc
int select_free_vc(int vnet)
Definition: OutputUnit.cc:111
gem5::ruby::garnet::SwitchAllocator::m_output_arbiter_activity
double m_output_arbiter_activity
Definition: SwitchAllocator.hh:86
gem5::ruby::garnet::InputUnit::need_stage
bool need_stage(int vc, flit_stage stage, Tick time)
Definition: InputUnit.hh:123
gem5::ruby::Consumer::alreadyScheduled
bool alreadyScheduled(Tick time)
Definition: Consumer.hh:75
Router.hh

Generated on Tue Sep 21 2021 12:25:41 for gem5 by doxygen 1.8.17