16145Snate@binkert.org/* 26145Snate@binkert.org * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 36145Snate@binkert.org * All rights reserved. 46145Snate@binkert.org * 56145Snate@binkert.org * Redistribution and use in source and binary forms, with or without 66145Snate@binkert.org * modification, are permitted provided that the following conditions are 76145Snate@binkert.org * met: redistributions of source code must retain the above copyright 86145Snate@binkert.org * notice, this list of conditions and the following disclaimer; 96145Snate@binkert.org * redistributions in binary form must reproduce the above copyright 106145Snate@binkert.org * notice, this list of conditions and the following disclaimer in the 116145Snate@binkert.org * documentation and/or other materials provided with the distribution; 126145Snate@binkert.org * neither the name of the copyright holders nor the names of its 136145Snate@binkert.org * contributors may be used to endorse or promote products derived from 146145Snate@binkert.org * this software without specific prior written permission. 156145Snate@binkert.org * 166145Snate@binkert.org * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 176145Snate@binkert.org * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 186145Snate@binkert.org * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 196145Snate@binkert.org * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 206145Snate@binkert.org * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 216145Snate@binkert.org * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 226145Snate@binkert.org * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 236145Snate@binkert.org * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 246145Snate@binkert.org * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 256145Snate@binkert.org * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 266145Snate@binkert.org * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 276145Snate@binkert.org */ 286145Snate@binkert.org 2911793Sbrandon.potter@amd.com#include "mem/ruby/network/simple/PerfectSwitch.hh" 3011793Sbrandon.potter@amd.com 317454Snate@binkert.org#include <algorithm> 327454Snate@binkert.org 338645Snilay@cs.wisc.edu#include "base/cast.hh" 3410348Sandreas.hansson@arm.com#include "base/random.hh" 358232Snate@binkert.org#include "debug/RubyNetwork.hh" 3610301Snilay@cs.wisc.edu#include "mem/ruby/network/MessageBuffer.hh" 377054Snate@binkert.org#include "mem/ruby/network/simple/SimpleNetwork.hh" 389274Snilay@cs.wisc.edu#include "mem/ruby/network/simple/Switch.hh" 3910895Snilay@cs.wisc.edu#include "mem/ruby/slicc_interface/Message.hh" 406145Snate@binkert.org 417055Snate@binkert.orgusing namespace std; 427055Snate@binkert.org 436145Snate@binkert.orgconst int PRIORITY_SWITCH_LIMIT = 128; 446145Snate@binkert.org 456145Snate@binkert.org// Operator for helper class 467054Snate@binkert.orgbool 477054Snate@binkert.orgoperator<(const LinkOrder& l1, const LinkOrder& l2) 487054Snate@binkert.org{ 497054Snate@binkert.org return (l1.m_value < l2.m_value); 506145Snate@binkert.org} 516145Snate@binkert.org 529274Snilay@cs.wisc.eduPerfectSwitch::PerfectSwitch(SwitchID sid, Switch *sw, uint32_t virt_nets) 5311092Snilay@cs.wisc.edu : Consumer(sw), m_switch_id(sid), m_switch(sw) 546145Snate@binkert.org{ 557054Snate@binkert.org m_round_robin_start = 0; 569274Snilay@cs.wisc.edu m_wakeups_wo_switch = 0; 579274Snilay@cs.wisc.edu m_virtual_networks = virt_nets; 589274Snilay@cs.wisc.edu} 599274Snilay@cs.wisc.edu 609274Snilay@cs.wisc.eduvoid 619274Snilay@cs.wisc.eduPerfectSwitch::init(SimpleNetwork *network_ptr) 629274Snilay@cs.wisc.edu{ 637054Snate@binkert.org m_network_ptr = network_ptr; 647973Snilay@cs.wisc.edu 6511321Ssteve.reinhardt@amd.com for (int i = 0;i < m_virtual_networks;++i) { 667973Snilay@cs.wisc.edu m_pending_message_count.push_back(0); 677973Snilay@cs.wisc.edu } 686145Snate@binkert.org} 696145Snate@binkert.org 707054Snate@binkert.orgvoid 7110370Snilay@cs.wisc.eduPerfectSwitch::addInPort(const vector<MessageBuffer*>& in) 726145Snate@binkert.org{ 737054Snate@binkert.org NodeID port = m_in.size(); 747454Snate@binkert.org m_in.push_back(in); 757973Snilay@cs.wisc.edu 7610370Snilay@cs.wisc.edu for (int i = 0; i < in.size(); ++i) { 7710370Snilay@cs.wisc.edu if (in[i] != nullptr) { 7810370Snilay@cs.wisc.edu in[i]->setConsumer(this); 7910370Snilay@cs.wisc.edu in[i]->setIncomingLink(port); 8010370Snilay@cs.wisc.edu in[i]->setVnet(i); 8110370Snilay@cs.wisc.edu } 827054Snate@binkert.org } 836145Snate@binkert.org} 846145Snate@binkert.org 857054Snate@binkert.orgvoid 8610370Snilay@cs.wisc.eduPerfectSwitch::addOutPort(const vector<MessageBuffer*>& out, 8710370Snilay@cs.wisc.edu const NetDest& routing_table_entry) 886145Snate@binkert.org{ 897054Snate@binkert.org // Setup link order 907054Snate@binkert.org LinkOrder l; 917054Snate@binkert.org l.m_value = 0; 927054Snate@binkert.org l.m_link = m_out.size(); 937454Snate@binkert.org m_link_order.push_back(l); 946145Snate@binkert.org 957054Snate@binkert.org // Add to routing table 967454Snate@binkert.org m_out.push_back(out); 977454Snate@binkert.org m_routing_table.push_back(routing_table_entry); 986145Snate@binkert.org} 996145Snate@binkert.org 1006145Snate@binkert.orgPerfectSwitch::~PerfectSwitch() 1016145Snate@binkert.org{ 1026145Snate@binkert.org} 1036145Snate@binkert.org 1047054Snate@binkert.orgvoid 10510312Snilay@cs.wisc.eduPerfectSwitch::operateVnet(int vnet) 10610312Snilay@cs.wisc.edu{ 10710312Snilay@cs.wisc.edu // This is for round-robin scheduling 10810312Snilay@cs.wisc.edu int incoming = m_round_robin_start; 10910312Snilay@cs.wisc.edu m_round_robin_start++; 11010312Snilay@cs.wisc.edu if (m_round_robin_start >= m_in.size()) { 11110312Snilay@cs.wisc.edu m_round_robin_start = 0; 11210312Snilay@cs.wisc.edu } 11310312Snilay@cs.wisc.edu 11411321Ssteve.reinhardt@amd.com if (m_pending_message_count[vnet] > 0) { 11510312Snilay@cs.wisc.edu // for all input ports, use round robin scheduling 11610312Snilay@cs.wisc.edu for (int counter = 0; counter < m_in.size(); counter++) { 11710312Snilay@cs.wisc.edu // Round robin scheduling 11810312Snilay@cs.wisc.edu incoming++; 11910312Snilay@cs.wisc.edu if (incoming >= m_in.size()) { 12010312Snilay@cs.wisc.edu incoming = 0; 12110312Snilay@cs.wisc.edu } 12210312Snilay@cs.wisc.edu 12310312Snilay@cs.wisc.edu // Is there a message waiting? 12410370Snilay@cs.wisc.edu if (m_in[incoming].size() <= vnet) { 12510312Snilay@cs.wisc.edu continue; 12610370Snilay@cs.wisc.edu } 12710370Snilay@cs.wisc.edu 12810370Snilay@cs.wisc.edu MessageBuffer *buffer = m_in[incoming][vnet]; 12910370Snilay@cs.wisc.edu if (buffer == nullptr) { 13010370Snilay@cs.wisc.edu continue; 13110370Snilay@cs.wisc.edu } 13210312Snilay@cs.wisc.edu 13311093Snilay@cs.wisc.edu operateMessageBuffer(buffer, incoming, vnet); 13411093Snilay@cs.wisc.edu } 13511093Snilay@cs.wisc.edu } 13611093Snilay@cs.wisc.edu} 13710312Snilay@cs.wisc.edu 13811093Snilay@cs.wisc.eduvoid 13911093Snilay@cs.wisc.eduPerfectSwitch::operateMessageBuffer(MessageBuffer *buffer, int incoming, 14011093Snilay@cs.wisc.edu int vnet) 14111093Snilay@cs.wisc.edu{ 14211093Snilay@cs.wisc.edu MsgPtr msg_ptr; 14311093Snilay@cs.wisc.edu Message *net_msg_ptr = NULL; 14410312Snilay@cs.wisc.edu 14511093Snilay@cs.wisc.edu // temporary vectors to store the routing results 14611093Snilay@cs.wisc.edu vector<LinkID> output_links; 14711093Snilay@cs.wisc.edu vector<NetDest> output_link_destinations; 14811111Snilay@cs.wisc.edu Tick current_time = m_switch->clockEdge(); 14910312Snilay@cs.wisc.edu 15011111Snilay@cs.wisc.edu while (buffer->isReady(current_time)) { 15111093Snilay@cs.wisc.edu DPRINTF(RubyNetwork, "incoming: %d\n", incoming); 15210312Snilay@cs.wisc.edu 15311093Snilay@cs.wisc.edu // Peek at message 15411093Snilay@cs.wisc.edu msg_ptr = buffer->peekMsgPtr(); 15511093Snilay@cs.wisc.edu net_msg_ptr = msg_ptr.get(); 15611093Snilay@cs.wisc.edu DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr)); 15710312Snilay@cs.wisc.edu 15811093Snilay@cs.wisc.edu output_links.clear(); 15911093Snilay@cs.wisc.edu output_link_destinations.clear(); 16011093Snilay@cs.wisc.edu NetDest msg_dsts = net_msg_ptr->getDestination(); 16110312Snilay@cs.wisc.edu 16211093Snilay@cs.wisc.edu // Unfortunately, the token-protocol sends some 16311093Snilay@cs.wisc.edu // zero-destination messages, so this assert isn't valid 16411093Snilay@cs.wisc.edu // assert(msg_dsts.count() > 0); 16511093Snilay@cs.wisc.edu 16611093Snilay@cs.wisc.edu assert(m_link_order.size() == m_routing_table.size()); 16711093Snilay@cs.wisc.edu assert(m_link_order.size() == m_out.size()); 16811093Snilay@cs.wisc.edu 16911093Snilay@cs.wisc.edu if (m_network_ptr->getAdaptiveRouting()) { 17011093Snilay@cs.wisc.edu if (m_network_ptr->isVNetOrdered(vnet)) { 17111093Snilay@cs.wisc.edu // Don't adaptively route 17211093Snilay@cs.wisc.edu for (int out = 0; out < m_out.size(); out++) { 17311093Snilay@cs.wisc.edu m_link_order[out].m_link = out; 17411093Snilay@cs.wisc.edu m_link_order[out].m_value = 0; 17511093Snilay@cs.wisc.edu } 17611093Snilay@cs.wisc.edu } else { 17711093Snilay@cs.wisc.edu // Find how clogged each link is 17811093Snilay@cs.wisc.edu for (int out = 0; out < m_out.size(); out++) { 17911093Snilay@cs.wisc.edu int out_queue_length = 0; 18011093Snilay@cs.wisc.edu for (int v = 0; v < m_virtual_networks; v++) { 18111111Snilay@cs.wisc.edu out_queue_length += m_out[out][v]->getSize(current_time); 18210312Snilay@cs.wisc.edu } 18311093Snilay@cs.wisc.edu int value = 18411093Snilay@cs.wisc.edu (out_queue_length << 8) | 18511093Snilay@cs.wisc.edu random_mt.random(0, 0xff); 18611093Snilay@cs.wisc.edu m_link_order[out].m_link = out; 18711093Snilay@cs.wisc.edu m_link_order[out].m_value = value; 18810312Snilay@cs.wisc.edu } 18910312Snilay@cs.wisc.edu 19011093Snilay@cs.wisc.edu // Look at the most empty link first 19111093Snilay@cs.wisc.edu sort(m_link_order.begin(), m_link_order.end()); 19211093Snilay@cs.wisc.edu } 19311093Snilay@cs.wisc.edu } 19411049Snilay@cs.wisc.edu 19511093Snilay@cs.wisc.edu for (int i = 0; i < m_routing_table.size(); i++) { 19611093Snilay@cs.wisc.edu // pick the next link to look at 19711093Snilay@cs.wisc.edu int link = m_link_order[i].m_link; 19811093Snilay@cs.wisc.edu NetDest dst = m_routing_table[link]; 19911093Snilay@cs.wisc.edu DPRINTF(RubyNetwork, "dst: %s\n", dst); 20011049Snilay@cs.wisc.edu 20111093Snilay@cs.wisc.edu if (!msg_dsts.intersectionIsNotEmpty(dst)) 20211093Snilay@cs.wisc.edu continue; 20311049Snilay@cs.wisc.edu 20411093Snilay@cs.wisc.edu // Remember what link we're using 20511093Snilay@cs.wisc.edu output_links.push_back(link); 20611049Snilay@cs.wisc.edu 20711093Snilay@cs.wisc.edu // Need to remember which destinations need this message in 20811093Snilay@cs.wisc.edu // another vector. This Set is the intersection of the 20911093Snilay@cs.wisc.edu // routing_table entry and the current destination set. The 21011093Snilay@cs.wisc.edu // intersection must not be empty, since we are inside "if" 21111093Snilay@cs.wisc.edu output_link_destinations.push_back(msg_dsts.AND(dst)); 21211049Snilay@cs.wisc.edu 21311093Snilay@cs.wisc.edu // Next, we update the msg_destination not to include 21411093Snilay@cs.wisc.edu // those nodes that were already handled by this link 21511093Snilay@cs.wisc.edu msg_dsts.removeNetDest(dst); 21611093Snilay@cs.wisc.edu } 21711049Snilay@cs.wisc.edu 21811093Snilay@cs.wisc.edu assert(msg_dsts.count() == 0); 21911049Snilay@cs.wisc.edu 22011093Snilay@cs.wisc.edu // Check for resources - for all outgoing queues 22111093Snilay@cs.wisc.edu bool enough = true; 22211093Snilay@cs.wisc.edu for (int i = 0; i < output_links.size(); i++) { 22311093Snilay@cs.wisc.edu int outgoing = output_links[i]; 22411049Snilay@cs.wisc.edu 22511111Snilay@cs.wisc.edu if (!m_out[outgoing][vnet]->areNSlotsAvailable(1, current_time)) 22611093Snilay@cs.wisc.edu enough = false; 22711049Snilay@cs.wisc.edu 22811093Snilay@cs.wisc.edu DPRINTF(RubyNetwork, "Checking if node is blocked ..." 22911093Snilay@cs.wisc.edu "outgoing: %d, vnet: %d, enough: %d\n", 23011093Snilay@cs.wisc.edu outgoing, vnet, enough); 23111093Snilay@cs.wisc.edu } 23211049Snilay@cs.wisc.edu 23311093Snilay@cs.wisc.edu // There were not enough resources 23411093Snilay@cs.wisc.edu if (!enough) { 23511093Snilay@cs.wisc.edu scheduleEvent(Cycles(1)); 23611093Snilay@cs.wisc.edu DPRINTF(RubyNetwork, "Can't deliver message since a node " 23711093Snilay@cs.wisc.edu "is blocked\n"); 23811093Snilay@cs.wisc.edu DPRINTF(RubyNetwork, "Message: %s\n", (*net_msg_ptr)); 23911093Snilay@cs.wisc.edu break; // go to next incoming port 24011093Snilay@cs.wisc.edu } 24111049Snilay@cs.wisc.edu 24211093Snilay@cs.wisc.edu MsgPtr unmodified_msg_ptr; 24311049Snilay@cs.wisc.edu 24411093Snilay@cs.wisc.edu if (output_links.size() > 1) { 24511093Snilay@cs.wisc.edu // If we are sending this message down more than one link 24611093Snilay@cs.wisc.edu // (size>1), we need to make a copy of the message so each 24711093Snilay@cs.wisc.edu // branch can have a different internal destination we need 24811093Snilay@cs.wisc.edu // to create an unmodified MsgPtr because the MessageBuffer 24911093Snilay@cs.wisc.edu // enqueue func will modify the message 25011049Snilay@cs.wisc.edu 25111093Snilay@cs.wisc.edu // This magic line creates a private copy of the message 25211093Snilay@cs.wisc.edu unmodified_msg_ptr = msg_ptr->clone(); 25311093Snilay@cs.wisc.edu } 25411049Snilay@cs.wisc.edu 25511093Snilay@cs.wisc.edu // Dequeue msg 25611111Snilay@cs.wisc.edu buffer->dequeue(current_time); 25711093Snilay@cs.wisc.edu m_pending_message_count[vnet]--; 25811049Snilay@cs.wisc.edu 25911093Snilay@cs.wisc.edu // Enqueue it - for all outgoing queues 26011093Snilay@cs.wisc.edu for (int i=0; i<output_links.size(); i++) { 26111093Snilay@cs.wisc.edu int outgoing = output_links[i]; 26211049Snilay@cs.wisc.edu 26311093Snilay@cs.wisc.edu if (i > 0) { 26411093Snilay@cs.wisc.edu // create a private copy of the unmodified message 26511093Snilay@cs.wisc.edu msg_ptr = unmodified_msg_ptr->clone(); 26611093Snilay@cs.wisc.edu } 26711049Snilay@cs.wisc.edu 26811093Snilay@cs.wisc.edu // Change the internal destination set of the message so it 26911093Snilay@cs.wisc.edu // knows which destinations this link is responsible for. 27011093Snilay@cs.wisc.edu net_msg_ptr = msg_ptr.get(); 27111093Snilay@cs.wisc.edu net_msg_ptr->getDestination() = output_link_destinations[i]; 27211049Snilay@cs.wisc.edu 27311093Snilay@cs.wisc.edu // Enqeue msg 27411093Snilay@cs.wisc.edu DPRINTF(RubyNetwork, "Enqueuing net msg from " 27511093Snilay@cs.wisc.edu "inport[%d][%d] to outport [%d][%d].\n", 27611093Snilay@cs.wisc.edu incoming, vnet, outgoing, vnet); 27711093Snilay@cs.wisc.edu 27811111Snilay@cs.wisc.edu m_out[outgoing][vnet]->enqueue(msg_ptr, current_time, 27911111Snilay@cs.wisc.edu m_switch->cyclesToTicks(Cycles(1))); 28011035Snilay@cs.wisc.edu } 28110312Snilay@cs.wisc.edu } 28210312Snilay@cs.wisc.edu} 28310312Snilay@cs.wisc.edu 28410312Snilay@cs.wisc.eduvoid 2857054Snate@binkert.orgPerfectSwitch::wakeup() 2866145Snate@binkert.org{ 2877054Snate@binkert.org // Give the highest numbered link priority most of the time 2887054Snate@binkert.org m_wakeups_wo_switch++; 2897054Snate@binkert.org int highest_prio_vnet = m_virtual_networks-1; 2907054Snate@binkert.org int lowest_prio_vnet = 0; 2917054Snate@binkert.org int decrementer = 1; 2926145Snate@binkert.org 2937054Snate@binkert.org // invert priorities to avoid starvation seen in the component network 2947054Snate@binkert.org if (m_wakeups_wo_switch > PRIORITY_SWITCH_LIMIT) { 2957054Snate@binkert.org m_wakeups_wo_switch = 0; 2967054Snate@binkert.org highest_prio_vnet = 0; 2977054Snate@binkert.org lowest_prio_vnet = m_virtual_networks-1; 2987054Snate@binkert.org decrementer = -1; 2997054Snate@binkert.org } 3006145Snate@binkert.org 3016145Snate@binkert.org // For all components incoming queues 3027054Snate@binkert.org for (int vnet = highest_prio_vnet; 3037054Snate@binkert.org (vnet * decrementer) >= (decrementer * lowest_prio_vnet); 3047054Snate@binkert.org vnet -= decrementer) { 30510312Snilay@cs.wisc.edu operateVnet(vnet); 3066145Snate@binkert.org } 3076145Snate@binkert.org} 3086145Snate@binkert.org 3097054Snate@binkert.orgvoid 3107973Snilay@cs.wisc.eduPerfectSwitch::storeEventInfo(int info) 3117973Snilay@cs.wisc.edu{ 3127973Snilay@cs.wisc.edu m_pending_message_count[info]++; 3137973Snilay@cs.wisc.edu} 3147973Snilay@cs.wisc.edu 3157973Snilay@cs.wisc.eduvoid 3167054Snate@binkert.orgPerfectSwitch::clearStats() 3176145Snate@binkert.org{ 3186145Snate@binkert.org} 3199863Snilay@cs.wisc.eduvoid 3209863Snilay@cs.wisc.eduPerfectSwitch::collateStats() 3219863Snilay@cs.wisc.edu{ 3229863Snilay@cs.wisc.edu} 3239863Snilay@cs.wisc.edu 3246145Snate@binkert.org 3257054Snate@binkert.orgvoid 3267054Snate@binkert.orgPerfectSwitch::print(std::ostream& out) const 3276145Snate@binkert.org{ 3287054Snate@binkert.org out << "[PerfectSwitch " << m_switch_id << "]"; 3296145Snate@binkert.org} 330