PerfectSwitch.cc (7002:48a19d52d939) PerfectSwitch.cc (7054:7d6862b80049)
1
2/*
3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
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;

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

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
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
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"
40#include "mem/ruby/network/simple/PerfectSwitch.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"
42#include "mem/ruby/profiler/Profiler.hh"
34#include "mem/ruby/profiler/Profiler.hh"
35#include "mem/ruby/slicc_interface/NetworkMessage.hh"
43#include "mem/ruby/system/System.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"
48
49const int PRIORITY_SWITCH_LIMIT = 128;
50
51// Operator for helper class
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);
54}
55
56PerfectSwitch::PerfectSwitch(SwitchID sid, SimpleNetwork* network_ptr)
57{
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;
63}
64
54}
55
65void PerfectSwitch::addInPort(const Vector<MessageBuffer*>& in)
56void
57PerfectSwitch::addInPort(const Vector<MessageBuffer*>& in)
66{
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 }
75}
76
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)
78{
74{
79 assert(out.size() == m_virtual_networks);
75 assert(out.size() == m_virtual_networks);
80
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);
86
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);
91}
92
86}
87
93void PerfectSwitch::clearRoutingTables()
88void
89PerfectSwitch::clearRoutingTables()
94{
90{
95 m_routing_table.clear();
91 m_routing_table.clear();
96}
97
92}
93
98void PerfectSwitch::clearBuffers()
94void
95PerfectSwitch::clearBuffers()
99{
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 }
103 }
101 }
104 }
105
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 }
109 }
107 }
110 }
111}
112
108}
109
113void PerfectSwitch::reconfigureOutPort(const NetDest& routing_table_entry)
110void
111PerfectSwitch::reconfigureOutPort(const NetDest& routing_table_entry)
114{
112{
115 m_routing_table.insertAtBottom(routing_table_entry);
113 m_routing_table.insertAtBottom(routing_table_entry);
116}
117
118PerfectSwitch::~PerfectSwitch()
119{
120}
121
114}
115
116PerfectSwitch::~PerfectSwitch()
117{
118}
119
122void PerfectSwitch::wakeup()
120void
121PerfectSwitch::wakeup()
123{
122{
123 DEBUG_EXPR(NETWORK_COMP, MedPrio, m_switch_id);
124
124
125 DEBUG_EXPR(NETWORK_COMP, MedPrio, m_switch_id);
125 MsgPtr msg_ptr;
126
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;
128
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 }
135
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
146 // For all components incoming queues
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) {
152
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 }
155
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
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
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);
168
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);
170
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();
175
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);
179
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());
183
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 }
186
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 }
209
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);
213
217
214 DEBUG_EXPR(NETWORK_COMP, MedPrio, m_routing_table[link]);
218 if (!msg_dsts.intersectionIsNotEmpty(dst))
219 continue;
215
220
216 if (msg_destinations.intersectionIsNotEmpty(m_routing_table[link])) {
221 // Remember what link we're using
222 output_links.insertAtBottom(link);
217
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));
220
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 }
226
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);
232
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 }
235
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 }
246
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;
254
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
256
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 }
265
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];
269
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 }
273
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];
278
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);
287
302
288 m_out[outgoing][vnet]->enqueue(msg_ptr);
289 }
303 m_out[outgoing][vnet]->enqueue(msg_ptr);
304 }
290
305
291 // Dequeue msg
292 m_in[incoming][vnet]->pop();
293 }
306 // Dequeue msg
307 m_in[incoming][vnet]->pop();
308 }
309 }
294 }
310 }
295 }
296}
297
311}
312
298void PerfectSwitch::printStats(std::ostream& out) const
313void
314PerfectSwitch::printStats(std::ostream& out) const
299{
315{
300 out << "PerfectSwitch printStats" << endl;
316 out << "PerfectSwitch printStats" << endl;
301}
302
317}
318
303void PerfectSwitch::clearStats()
319void
320PerfectSwitch::clearStats()
304{
305}
306
321{
322}
323
307void PerfectSwitch::printConfig(std::ostream& out) const
324void
325PerfectSwitch::printConfig(std::ostream& out) const
308{
309}
310
326{
327}
328
311void PerfectSwitch::print(std::ostream& out) const
329void
330PerfectSwitch::print(std::ostream& out) const
312{
331{
313 out << "[PerfectSwitch " << m_switch_id << "]";
332 out << "[PerfectSwitch " << m_switch_id << "]";
314}
315
333}
334