gem5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
PerfectSwitch.cc
Go to the documentation of this file.
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 
30 
31 #include <algorithm>
32 
33 #include "base/cast.hh"
34 #include "base/random.hh"
35 #include "debug/RubyNetwork.hh"
40 
41 using namespace std;
42 
43 const int PRIORITY_SWITCH_LIMIT = 128;
44 
45 // Operator for helper class
46 bool
48 {
49  return (l1.m_value < l2.m_value);
50 }
51 
52 PerfectSwitch::PerfectSwitch(SwitchID sid, Switch *sw, uint32_t virt_nets)
53  : Consumer(sw), m_switch_id(sid), m_switch(sw)
54 {
57  m_virtual_networks = virt_nets;
58 }
59 
60 void
62 {
63  m_network_ptr = network_ptr;
64 
65  for (int i = 0;i < m_virtual_networks;++i) {
66  m_pending_message_count.push_back(0);
67  }
68 }
69 
70 void
72 {
73  NodeID port = m_in.size();
74  m_in.push_back(in);
75 
76  for (int i = 0; i < in.size(); ++i) {
77  if (in[i] != nullptr) {
78  in[i]->setConsumer(this);
79  in[i]->setIncomingLink(port);
80  in[i]->setVnet(i);
81  }
82  }
83 }
84 
85 void
87  const NetDest& routing_table_entry)
88 {
89  // Setup link order
90  LinkOrder l;
91  l.m_value = 0;
92  l.m_link = m_out.size();
93  m_link_order.push_back(l);
94 
95  // Add to routing table
96  m_out.push_back(out);
97  m_routing_table.push_back(routing_table_entry);
98 }
99 
101 {
102 }
103 
104 void
106 {
107  // This is for round-robin scheduling
108  int incoming = m_round_robin_start;
110  if (m_round_robin_start >= m_in.size()) {
112  }
113 
114  if (m_pending_message_count[vnet] > 0) {
115  // for all input ports, use round robin scheduling
116  for (int counter = 0; counter < m_in.size(); counter++) {
117  // Round robin scheduling
118  incoming++;
119  if (incoming >= m_in.size()) {
120  incoming = 0;
121  }
122 
123  // Is there a message waiting?
124  if (m_in[incoming].size() <= vnet) {
125  continue;
126  }
127 
128  MessageBuffer *buffer = m_in[incoming][vnet];
129  if (buffer == nullptr) {
130  continue;
131  }
132 
133  operateMessageBuffer(buffer, incoming, vnet);
134  }
135  }
136 }
137 
138 void
140  int vnet)
141 {
142  MsgPtr msg_ptr;
143  Message *net_msg_ptr = NULL;
144 
145  // temporary vectors to store the routing results
146  vector<LinkID> output_links;
147  vector<NetDest> output_link_destinations;
148  Tick current_time = m_switch->clockEdge();
149 
150  while (buffer->isReady(current_time)) {
151  DPRINTF(RubyNetwork, "incoming: %d\n", incoming);
152 
153  // Peek at message
154  msg_ptr = buffer->peekMsgPtr();
155  net_msg_ptr = msg_ptr.get();
156  DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr));
157 
158  output_links.clear();
159  output_link_destinations.clear();
160  NetDest msg_dsts = net_msg_ptr->getDestination();
161 
162  // Unfortunately, the token-protocol sends some
163  // zero-destination messages, so this assert isn't valid
164  // assert(msg_dsts.count() > 0);
165 
166  assert(m_link_order.size() == m_routing_table.size());
167  assert(m_link_order.size() == m_out.size());
168 
170  if (m_network_ptr->isVNetOrdered(vnet)) {
171  // Don't adaptively route
172  for (int out = 0; out < m_out.size(); out++) {
173  m_link_order[out].m_link = out;
174  m_link_order[out].m_value = 0;
175  }
176  } else {
177  // Find how clogged each link is
178  for (int out = 0; out < m_out.size(); out++) {
179  int out_queue_length = 0;
180  for (int v = 0; v < m_virtual_networks; v++) {
181  out_queue_length += m_out[out][v]->getSize(current_time);
182  }
183  int value =
184  (out_queue_length << 8) |
185  random_mt.random(0, 0xff);
186  m_link_order[out].m_link = out;
187  m_link_order[out].m_value = value;
188  }
189 
190  // Look at the most empty link first
191  sort(m_link_order.begin(), m_link_order.end());
192  }
193  }
194 
195  for (int i = 0; i < m_routing_table.size(); i++) {
196  // pick the next link to look at
197  int link = m_link_order[i].m_link;
198  NetDest dst = m_routing_table[link];
199  DPRINTF(RubyNetwork, "dst: %s\n", dst);
200 
201  if (!msg_dsts.intersectionIsNotEmpty(dst))
202  continue;
203 
204  // Remember what link we're using
205  output_links.push_back(link);
206 
207  // Need to remember which destinations need this message in
208  // another vector. This Set is the intersection of the
209  // routing_table entry and the current destination set. The
210  // intersection must not be empty, since we are inside "if"
211  output_link_destinations.push_back(msg_dsts.AND(dst));
212 
213  // Next, we update the msg_destination not to include
214  // those nodes that were already handled by this link
215  msg_dsts.removeNetDest(dst);
216  }
217 
218  assert(msg_dsts.count() == 0);
219 
220  // Check for resources - for all outgoing queues
221  bool enough = true;
222  for (int i = 0; i < output_links.size(); i++) {
223  int outgoing = output_links[i];
224 
225  if (!m_out[outgoing][vnet]->areNSlotsAvailable(1, current_time))
226  enough = false;
227 
228  DPRINTF(RubyNetwork, "Checking if node is blocked ..."
229  "outgoing: %d, vnet: %d, enough: %d\n",
230  outgoing, vnet, enough);
231  }
232 
233  // There were not enough resources
234  if (!enough) {
235  scheduleEvent(Cycles(1));
236  DPRINTF(RubyNetwork, "Can't deliver message since a node "
237  "is blocked\n");
238  DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr));
239  break; // go to next incoming port
240  }
241 
242  MsgPtr unmodified_msg_ptr;
243 
244  if (output_links.size() > 1) {
245  // If we are sending this message down more than one link
246  // (size>1), we need to make a copy of the message so each
247  // branch can have a different internal destination we need
248  // to create an unmodified MsgPtr because the MessageBuffer
249  // enqueue func will modify the message
250 
251  // This magic line creates a private copy of the message
252  unmodified_msg_ptr = msg_ptr->clone();
253  }
254 
255  // Dequeue msg
256  buffer->dequeue(current_time);
257  m_pending_message_count[vnet]--;
258 
259  // Enqueue it - for all outgoing queues
260  for (int i=0; i<output_links.size(); i++) {
261  int outgoing = output_links[i];
262 
263  if (i > 0) {
264  // create a private copy of the unmodified message
265  msg_ptr = unmodified_msg_ptr->clone();
266  }
267 
268  // Change the internal destination set of the message so it
269  // knows which destinations this link is responsible for.
270  net_msg_ptr = msg_ptr.get();
271  net_msg_ptr->getDestination() = output_link_destinations[i];
272 
273  // Enqeue msg
274  DPRINTF(RubyNetwork, "Enqueuing net msg from "
275  "inport[%d][%d] to outport [%d][%d].\n",
276  incoming, vnet, outgoing, vnet);
277 
278  m_out[outgoing][vnet]->enqueue(msg_ptr, current_time,
280  }
281  }
282 }
283 
284 void
286 {
287  // Give the highest numbered link priority most of the time
289  int highest_prio_vnet = m_virtual_networks-1;
290  int lowest_prio_vnet = 0;
291  int decrementer = 1;
292 
293  // invert priorities to avoid starvation seen in the component network
296  highest_prio_vnet = 0;
297  lowest_prio_vnet = m_virtual_networks-1;
298  decrementer = -1;
299  }
300 
301  // For all components incoming queues
302  for (int vnet = highest_prio_vnet;
303  (vnet * decrementer) >= (decrementer * lowest_prio_vnet);
304  vnet -= decrementer) {
305  operateVnet(vnet);
306  }
307 }
308 
309 void
311 {
312  m_pending_message_count[info]++;
313 }
314 
315 void
317 {
318 }
319 void
321 {
322 }
323 
324 
325 void
326 PerfectSwitch::print(std::ostream& out) const
327 {
328  out << "[PerfectSwitch " << m_switch_id << "]";
329 }
#define DPRINTF(x,...)
Definition: trace.hh:212
virtual const NetDest & getDestination() const
Definition: Message.hh:96
Bitfield< 28 > v
Definition: miscregs.hh:1366
Cycles is a wrapper class for representing cycle counts, i.e.
Definition: types.hh:83
std::shared_ptr< Message > MsgPtr
Definition: Message.hh:40
Bitfield< 7 > i
Definition: miscregs.hh:1378
uint32_t m_virtual_networks
void scheduleEvent(Cycles timeDelta)
Definition: Consumer.cc:34
Tick cyclesToTicks(Cycles c) const
bool getAdaptiveRouting()
bool intersectionIsNotEmpty(const NetDest &other_netDest) const
Definition: NetDest.cc:216
SimpleNetwork * m_network_ptr
std::vector< NetDest > m_routing_table
void storeEventInfo(int info)
bool isVNetOrdered(int vnet) const
Bitfield< 4 > l2
Definition: misc.hh:661
const int PRIORITY_SWITCH_LIMIT
int count() const
Definition: NetDest.cc:122
const SwitchID m_switch_id
std::enable_if< std::is_integral< T >::value, T >::type random()
Use the SFINAE idiom to choose an implementation based on whether the type is integral or floating po...
Definition: random.hh:83
Bitfield< 10 > sw
Definition: miscregs.hh:1559
Definition: Switch.hh:57
unsigned int NodeID
Definition: TypeDefines.hh:34
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...
const MsgPtr & peekMsgPtr() const
unsigned int SwitchID
Definition: TypeDefines.hh:35
uint64_t Tick
Tick count type.
Definition: types.hh:63
Tick dequeue(Tick current_time, bool decrement_messages=true)
Updates the delay cycles of the message at the head of the queue, removes it from the queue and retur...
std::vector< int > m_pending_message_count
Switch *const m_switch
std::vector< LinkOrder > m_link_order
void addOutPort(const std::vector< MessageBuffer * > &out, const NetDest &routing_table_entry)
void removeNetDest(const NetDest &netDest)
Definition: NetDest.cc:70
NetDest AND(const NetDest &andNetDest) const
Definition: NetDest.cc:204
std::vector< std::vector< MessageBuffer * > > m_in
void init(SimpleNetwork *)
std::vector< std::vector< MessageBuffer * > > m_out
bool isReady(Tick current_time) const
int size()
Definition: pagetable.hh:146
bool operator<(const LinkOrder &l1, const LinkOrder &l2)
Bitfield< 2 > l1
Definition: misc.hh:659
void print(std::ostream &out) const
Random random_mt
Definition: random.cc:100
void operateVnet(int vnet)
PerfectSwitch(SwitchID sid, Switch *, uint32_t)
Bitfield< 5 > l
void addInPort(const std::vector< MessageBuffer * > &in)
void operateMessageBuffer(MessageBuffer *b, int incoming, int vnet)

Generated on Fri Jun 9 2017 13:03:50 for gem5 by doxygen 1.8.6