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