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;

--- 12 unchanged lines hidden (view full) ---

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
29#include "mem/gems_common/util.hh"
30#include "mem/protocol/Protocol.hh"
31#include "mem/ruby/buffers/MessageBuffer.hh"
32#include "mem/ruby/network/simple/PerfectSwitch.hh"
33#include "mem/ruby/network/simple/SimpleNetwork.hh"
34#include "mem/ruby/profiler/Profiler.hh"
35#include "mem/ruby/slicc_interface/NetworkMessage.hh"
36#include "mem/ruby/system/System.hh"
37
38const int PRIORITY_SWITCH_LIMIT = 128;
39
40// Operator for helper class
41bool
42operator<(const LinkOrder& l1, const LinkOrder& l2)
43{
44 return (l1.m_value < l2.m_value);
45}
46
47PerfectSwitch::PerfectSwitch(SwitchID sid, SimpleNetwork* network_ptr)
48{
49 m_virtual_networks = network_ptr->getNumberOfVirtualNetworks();
50 m_switch_id = sid;
51 m_round_robin_start = 0;
52 m_network_ptr = network_ptr;
53 m_wakeups_wo_switch = 0;
54}
55
56void
57PerfectSwitch::addInPort(const Vector<MessageBuffer*>& in)
58{
59 assert(in.size() == m_virtual_networks);
60 NodeID port = m_in.size();
61 m_in.insertAtBottom(in);
62 for (int j = 0; j < m_virtual_networks; j++) {
63 m_in[port][j]->setConsumer(this);
64 string desc = csprintf("[Queue from port %s %s %s to PerfectSwitch]",
65 NodeIDToString(m_switch_id), NodeIDToString(port),
66 NodeIDToString(j));
67 m_in[port][j]->setDescription(desc);
68 }
69}
70
71void
72PerfectSwitch::addOutPort(const Vector<MessageBuffer*>& out,
73 const NetDest& routing_table_entry)
74{
75 assert(out.size() == m_virtual_networks);
76
77 // Setup link order
78 LinkOrder l;
79 l.m_value = 0;
80 l.m_link = m_out.size();
81 m_link_order.insertAtBottom(l);
82
83 // Add to routing table
84 m_out.insertAtBottom(out);
85 m_routing_table.insertAtBottom(routing_table_entry);
86}
87
88void
89PerfectSwitch::clearRoutingTables()
90{
91 m_routing_table.clear();
92}
93
94void
95PerfectSwitch::clearBuffers()
96{
97 for (int i = 0; i < m_in.size(); i++){
98 for(int vnet = 0; vnet < m_virtual_networks; vnet++) {
99 m_in[i][vnet]->clear();
100 }
101 }
102
103 for (int i = 0; i < m_out.size(); i++){
104 for(int vnet = 0; vnet < m_virtual_networks; vnet++) {
105 m_out[i][vnet]->clear();
106 }
107 }
108}
109
110void
111PerfectSwitch::reconfigureOutPort(const NetDest& routing_table_entry)
112{
113 m_routing_table.insertAtBottom(routing_table_entry);
114}
115
116PerfectSwitch::~PerfectSwitch()
117{
118}
119
120void
121PerfectSwitch::wakeup()
122{
123 DEBUG_EXPR(NETWORK_COMP, MedPrio, m_switch_id);
124
125 MsgPtr msg_ptr;
126
127 // Give the highest numbered link priority most of the time
128 m_wakeups_wo_switch++;
129 int highest_prio_vnet = m_virtual_networks-1;
130 int lowest_prio_vnet = 0;
131 int decrementer = 1;
132 NetworkMessage* net_msg_ptr = NULL;
133
134 // invert priorities to avoid starvation seen in the component network
135 if (m_wakeups_wo_switch > PRIORITY_SWITCH_LIMIT) {
136 m_wakeups_wo_switch = 0;
137 highest_prio_vnet = 0;
138 lowest_prio_vnet = m_virtual_networks-1;
139 decrementer = -1;
140 }
141
142 // For all components incoming queues
143 for (int vnet = highest_prio_vnet;
144 (vnet * decrementer) >= (decrementer * lowest_prio_vnet);
145 vnet -= decrementer) {
146
147 // This is for round-robin scheduling
148 int incoming = m_round_robin_start;
149 m_round_robin_start++;
150 if (m_round_robin_start >= m_in.size()) {
151 m_round_robin_start = 0;
152 }
153
154 // for all input ports, use round robin scheduling
155 for (int counter = 0; counter < m_in.size(); counter++) {
156 // Round robin scheduling
157 incoming++;
158 if (incoming >= m_in.size()) {
159 incoming = 0;
160 }
161
162 // temporary vectors to store the routing results
163 Vector<LinkID> output_links;
164 Vector<NetDest> output_link_destinations;
165
166 // Is there a message waiting?
167 while (m_in[incoming][vnet]->isReady()) {
168 DEBUG_EXPR(NETWORK_COMP, MedPrio, incoming);
169
170 // Peek at message
171 msg_ptr = m_in[incoming][vnet]->peekMsgPtr();
172 net_msg_ptr = dynamic_cast<NetworkMessage*>(msg_ptr.ref());
173 DEBUG_EXPR(NETWORK_COMP, MedPrio, *net_msg_ptr);
174
175 output_links.clear();
176 output_link_destinations.clear();
177 NetDest msg_dsts =
178 net_msg_ptr->getInternalDestination();
179
180 // Unfortunately, the token-protocol sends some
181 // zero-destination messages, so this assert isn't valid
182 // assert(msg_dsts.count() > 0);
183
184 assert(m_link_order.size() == m_routing_table.size());
185 assert(m_link_order.size() == m_out.size());
186
187 if (m_network_ptr->getAdaptiveRouting()) {
188 if (m_network_ptr->isVNetOrdered(vnet)) {
189 // Don't adaptively route
190 for (int out = 0; out < m_out.size(); out++) {
191 m_link_order[out].m_link = out;
192 m_link_order[out].m_value = 0;
193 }
194 } else {
195 // Find how clogged each link is
196 for (int out = 0; out < m_out.size(); out++) {
197 int out_queue_length = 0;
198 for (int v = 0; v < m_virtual_networks; v++) {
199 out_queue_length += m_out[out][v]->getSize();
200 }
201 int value =
202 (out_queue_length << 8) | (random() & 0xff);
203 m_link_order[out].m_link = out;
204 m_link_order[out].m_value = value;
205 }
206
207 // Look at the most empty link first
208 m_link_order.sortVector();
209 }
210 }
211
212 for (int i = 0; i < m_routing_table.size(); i++) {
213 // pick the next link to look at
214 int link = m_link_order[i].m_link;
215 NetDest dst = m_routing_table[link];
216 DEBUG_EXPR(NETWORK_COMP, MedPrio, dst);
217
218 if (!msg_dsts.intersectionIsNotEmpty(dst))
219 continue;
220
221 // Remember what link we're using
222 output_links.insertAtBottom(link);
223
224 // Need to remember which destinations need this
225 // message in another vector. This Set is the
226 // intersection of the routing_table entry and the
227 // current destination set. The intersection must
228 // not be empty, since we are inside "if"
229 output_link_destinations.insertAtBottom(msg_dsts.AND(dst));
230
231 // Next, we update the msg_destination not to
232 // include those nodes that were already handled
233 // by this link
234 msg_dsts.removeNetDest(dst);
235 }
236
237 assert(msg_dsts.count() == 0);
238 //assert(output_links.size() > 0);
239
240 // Check for resources - for all outgoing queues
241 bool enough = true;
242 for (int i = 0; i < output_links.size(); i++) {
243 int outgoing = output_links[i];
244 if (!m_out[outgoing][vnet]->areNSlotsAvailable(1))
245 enough = false;
246 DEBUG_MSG(NETWORK_COMP, HighPrio,
247 "checking if node is blocked");
248 DEBUG_EXPR(NETWORK_COMP, HighPrio, outgoing);
249 DEBUG_EXPR(NETWORK_COMP, HighPrio, vnet);
250 DEBUG_EXPR(NETWORK_COMP, HighPrio, enough);
251 }
252
253 // There were not enough resources
254 if (!enough) {
255 g_eventQueue_ptr->scheduleEvent(this, 1);
256 DEBUG_MSG(NETWORK_COMP, HighPrio,
257 "Can't deliver message since a node is blocked");
258 DEBUG_EXPR(NETWORK_COMP, HighPrio, *net_msg_ptr);
259 break; // go to next incoming port
260 }
261
262 MsgPtr unmodified_msg_ptr;
263
264 if (output_links.size() > 1) {
265 // If we are sending this message down more than
266 // one link (size>1), we need to make a copy of
267 // the message so each branch can have a different
268 // internal destination we need to create an
269 // unmodified MsgPtr because the MessageBuffer
270 // enqueue func will modify the message
271
272 // This magic line creates a private copy of the
273 // message
274 unmodified_msg_ptr = *(msg_ptr.ref());
275 }
276
277 // Enqueue it - for all outgoing queues
278 for (int i=0; i<output_links.size(); i++) {
279 int outgoing = output_links[i];
280
281 if (i > 0) {
282 // create a private copy of the unmodified
283 // message
284 msg_ptr = *(unmodified_msg_ptr.ref());
285 }
286
287 // Change the internal destination set of the
288 // message so it knows which destinations this
289 // link is responsible for.
290 net_msg_ptr = safe_cast<NetworkMessage*>(msg_ptr.ref());
291 net_msg_ptr->getInternalDestination() =
292 output_link_destinations[i];
293
294 // Enqeue msg
295 DEBUG_NEWLINE(NETWORK_COMP,HighPrio);
296 DEBUG_MSG(NETWORK_COMP, HighPrio,
297 csprintf("switch: %d enqueuing net msg from "
298 "inport[%d][%d] to outport [%d][%d] time: %d.",
299 m_switch_id, incoming, vnet, outgoing, vnet,
300 g_eventQueue_ptr->getTime()));
301 DEBUG_NEWLINE(NETWORK_COMP,HighPrio);
302
303 m_out[outgoing][vnet]->enqueue(msg_ptr);
304 }
305
306 // Dequeue msg
307 m_in[incoming][vnet]->pop();
308 }
309 }
310 }
311}
312
313void
314PerfectSwitch::printStats(std::ostream& out) const
315{
316 out << "PerfectSwitch printStats" << endl;
317}
318
319void
320PerfectSwitch::clearStats()
321{
322}
323
324void
325PerfectSwitch::printConfig(std::ostream& out) const
326{
327}
328
329void
330PerfectSwitch::print(std::ostream& out) const
331{
332 out << "[PerfectSwitch " << m_switch_id << "]";
333}
334