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
29#include "mem/ruby/network/simple/PerfectSwitch.hh"
30
31#include <algorithm>
32
33#include "base/cast.hh"
34#include "base/random.hh"
35#include "debug/RubyNetwork.hh"
36#include "mem/ruby/network/MessageBuffer.hh"
37#include "mem/ruby/network/simple/SimpleNetwork.hh"
38#include "mem/ruby/network/simple/Switch.hh"
39#include "mem/ruby/slicc_interface/Message.hh"
40
41using namespace std;
42
43const int PRIORITY_SWITCH_LIMIT = 128;
44
45// Operator for helper class
46bool
47operator<(const LinkOrder& l1, const LinkOrder& l2)
48{
49    return (l1.m_value < l2.m_value);
50}
51
52PerfectSwitch::PerfectSwitch(SwitchID sid, Switch *sw, uint32_t virt_nets)
53    : Consumer(sw), m_switch_id(sid), m_switch(sw)
54{
55    m_round_robin_start = 0;
56    m_wakeups_wo_switch = 0;
57    m_virtual_networks = virt_nets;
58}
59
60void
61PerfectSwitch::init(SimpleNetwork *network_ptr)
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
70void
71PerfectSwitch::addInPort(const vector<MessageBuffer*>& in)
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
85void
86PerfectSwitch::addOutPort(const vector<MessageBuffer*>& out,
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
100PerfectSwitch::~PerfectSwitch()
101{
102}
103
104void
105PerfectSwitch::operateVnet(int vnet)
106{
107    // This is for round-robin scheduling
108    int incoming = m_round_robin_start;
109    m_round_robin_start++;
110    if (m_round_robin_start >= m_in.size()) {
111        m_round_robin_start = 0;
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
138void
139PerfectSwitch::operateMessageBuffer(MessageBuffer *buffer, int incoming,
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
169        if (m_network_ptr->getAdaptiveRouting()) {
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,
279                                           m_switch->cyclesToTicks(Cycles(1)));
280        }
281    }
282}
283
284void
285PerfectSwitch::wakeup()
286{
287    // Give the highest numbered link priority most of the time
288    m_wakeups_wo_switch++;
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
294    if (m_wakeups_wo_switch > PRIORITY_SWITCH_LIMIT) {
295        m_wakeups_wo_switch = 0;
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
309void
310PerfectSwitch::storeEventInfo(int info)
311{
312    m_pending_message_count[info]++;
313}
314
315void
316PerfectSwitch::clearStats()
317{
318}
319void
320PerfectSwitch::collateStats()
321{
322}
323
324
325void
326PerfectSwitch::print(std::ostream& out) const
327{
328    out << "[PerfectSwitch " << m_switch_id << "]";
329}
330