Topology.cc revision 11663
110037SARM gem5 Developers/* 210037SARM gem5 Developers * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 310037SARM gem5 Developers * All rights reserved. 410037SARM gem5 Developers * 510037SARM gem5 Developers * Redistribution and use in source and binary forms, with or without 610037SARM gem5 Developers * modification, are permitted provided that the following conditions are 710037SARM gem5 Developers * met: redistributions of source code must retain the above copyright 810037SARM gem5 Developers * notice, this list of conditions and the following disclaimer; 910037SARM gem5 Developers * redistributions in binary form must reproduce the above copyright 1010037SARM gem5 Developers * notice, this list of conditions and the following disclaimer in the 1110037SARM gem5 Developers * documentation and/or other materials provided with the distribution; 1210037SARM gem5 Developers * neither the name of the copyright holders nor the names of its 1310037SARM gem5 Developers * contributors may be used to endorse or promote products derived from 1410037SARM gem5 Developers * this software without specific prior written permission. 1510037SARM gem5 Developers * 1610037SARM gem5 Developers * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1710037SARM gem5 Developers * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1810037SARM gem5 Developers * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1910037SARM gem5 Developers * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2010037SARM gem5 Developers * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2110037SARM gem5 Developers * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2210037SARM gem5 Developers * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2310037SARM gem5 Developers * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2410037SARM gem5 Developers * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2510037SARM gem5 Developers * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2610037SARM gem5 Developers * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2710037SARM gem5 Developers */ 2810037SARM gem5 Developers 2910037SARM gem5 Developers#include <cassert> 3010037SARM gem5 Developers 3110037SARM gem5 Developers#include "base/trace.hh" 3210037SARM gem5 Developers#include "debug/RubyNetwork.hh" 3310037SARM gem5 Developers#include "mem/ruby/common/NetDest.hh" 3410037SARM gem5 Developers#include "mem/ruby/network/BasicLink.hh" 3510037SARM gem5 Developers#include "mem/ruby/network/Topology.hh" 3610037SARM gem5 Developers#include "mem/ruby/slicc_interface/AbstractController.hh" 3710037SARM gem5 Developers 3810037SARM gem5 Developersusing namespace std; 3910037SARM gem5 Developers 4011793Sbrandon.potter@amd.comconst int INFINITE_LATENCY = 10000; // Yes, this is a big hack 4111793Sbrandon.potter@amd.com 4210037SARM gem5 Developers// Note: In this file, we use the first 2*m_nodes SwitchIDs to 4310037SARM gem5 Developers// represent the input and output endpoint links. These really are 4410037SARM gem5 Developers// not 'switches', as they will not have a Switch object allocated for 4510037SARM gem5 Developers// them. The first m_nodes SwitchIDs are the links into the network, 4610037SARM gem5 Developers// the second m_nodes set of SwitchIDs represent the the output queues 4710037SARM gem5 Developers// of the network. 4810037SARM gem5 Developers 4910037SARM gem5 DevelopersTopology::Topology(uint32_t num_routers, 5010037SARM gem5 Developers const vector<BasicExtLink *> &ext_links, 5110037SARM gem5 Developers const vector<BasicIntLink *> &int_links) 5210037SARM gem5 Developers : m_nodes(ext_links.size()), m_number_of_switches(num_routers), 5310037SARM gem5 Developers m_ext_link_vector(ext_links), m_int_link_vector(int_links) 5410037SARM gem5 Developers{ 5510037SARM gem5 Developers // Total nodes/controllers in network 5610037SARM gem5 Developers assert(m_nodes > 1); 5710037SARM gem5 Developers 5810037SARM gem5 Developers // analyze both the internal and external links, create data structures. 5910037SARM gem5 Developers // The python created external links are bi-directional, 6010037SARM gem5 Developers // and the python created internal links are uni-directional. 6110037SARM gem5 Developers // The networks and topology utilize uni-directional links. 6210037SARM gem5 Developers // Thus each external link is converted to two calls to addLink, 6312092Sspwilson2@wisc.edu // one for each direction. 6412092Sspwilson2@wisc.edu // 6512092Sspwilson2@wisc.edu // External Links 6612092Sspwilson2@wisc.edu for (vector<BasicExtLink*>::const_iterator i = ext_links.begin(); 6712092Sspwilson2@wisc.edu i != ext_links.end(); ++i) { 6812092Sspwilson2@wisc.edu BasicExtLink *ext_link = (*i); 6910037SARM gem5 Developers AbstractController *abs_cntrl = ext_link->params()->ext_node; 7010037SARM gem5 Developers BasicRouter *router = ext_link->params()->int_node; 7110037SARM gem5 Developers 7210037SARM gem5 Developers int machine_base_idx = MachineType_base_number(abs_cntrl->getType()); 7310037SARM gem5 Developers int ext_idx1 = machine_base_idx + abs_cntrl->getVersion(); 7410037SARM gem5 Developers int ext_idx2 = ext_idx1 + m_nodes; 7510037SARM gem5 Developers int int_idx = router->params()->router_id + 2*m_nodes; 7610037SARM gem5 Developers 7710037SARM gem5 Developers // create the internal uni-directional links in both directions 7810037SARM gem5 Developers // ext to int 7910037SARM gem5 Developers addLink(ext_idx1, int_idx, ext_link); 8010037SARM gem5 Developers // int to ext 8110037SARM gem5 Developers addLink(int_idx, ext_idx2, ext_link); 8210037SARM gem5 Developers } 8310037SARM gem5 Developers 8410037SARM gem5 Developers // Internal Links 8510037SARM gem5 Developers for (vector<BasicIntLink*>::const_iterator i = int_links.begin(); 8610037SARM gem5 Developers i != int_links.end(); ++i) { 8710037SARM gem5 Developers BasicIntLink *int_link = (*i); 8810037SARM gem5 Developers BasicRouter *router_src = int_link->params()->src_node; 8910037SARM gem5 Developers BasicRouter *router_dst = int_link->params()->dst_node; 9010037SARM gem5 Developers 9110037SARM gem5 Developers // Store the IntLink pointers for later 9210037SARM gem5 Developers m_int_link_vector.push_back(int_link); 9310037SARM gem5 Developers 9410037SARM gem5 Developers int src = router_src->params()->router_id + 2*m_nodes; 9510037SARM gem5 Developers int dst = router_dst->params()->router_id + 2*m_nodes; 9610037SARM gem5 Developers 9710037SARM gem5 Developers // create the internal uni-directional link from src to dst 9810037SARM gem5 Developers addLink(src, dst, int_link); 9910037SARM gem5 Developers } 10011005Sandreas.sandberg@arm.com} 10110037SARM gem5 Developers 10210037SARM gem5 Developersvoid 10310037SARM gem5 DevelopersTopology::createLinks(Network *net) 10410037SARM gem5 Developers{ 10510037SARM gem5 Developers // Find maximum switchID 10610037SARM gem5 Developers SwitchID max_switch_id = 0; 10710037SARM gem5 Developers for (LinkMap::const_iterator i = m_link_map.begin(); 10810037SARM gem5 Developers i != m_link_map.end(); ++i) { 10910037SARM gem5 Developers std::pair<SwitchID, SwitchID> src_dest = (*i).first; 11010037SARM gem5 Developers max_switch_id = max(max_switch_id, src_dest.first); 11110037SARM gem5 Developers max_switch_id = max(max_switch_id, src_dest.second); 11210037SARM gem5 Developers } 11310037SARM gem5 Developers 11410037SARM gem5 Developers // Initialize weight, latency, and inter switched vectors 11510037SARM gem5 Developers int num_switches = max_switch_id+1; 11610037SARM gem5 Developers Matrix topology_weights(num_switches, 11710037SARM gem5 Developers vector<int>(num_switches, INFINITE_LATENCY)); 11810037SARM gem5 Developers Matrix component_latencies(num_switches, 11910037SARM gem5 Developers vector<int>(num_switches, -1)); 12010037SARM gem5 Developers Matrix component_inter_switches(num_switches, 12110037SARM gem5 Developers vector<int>(num_switches, 0)); 12210037SARM gem5 Developers 12310037SARM gem5 Developers // Set identity weights to zero 12410037SARM gem5 Developers for (int i = 0; i < topology_weights.size(); i++) { 12510037SARM gem5 Developers topology_weights[i][i] = 0; 12610037SARM gem5 Developers } 12710037SARM gem5 Developers 12810037SARM gem5 Developers // Fill in the topology weights and bandwidth multipliers 12910037SARM gem5 Developers for (LinkMap::const_iterator i = m_link_map.begin(); 13010037SARM gem5 Developers i != m_link_map.end(); ++i) { 13110037SARM gem5 Developers std::pair<int, int> src_dest = (*i).first; 13210037SARM gem5 Developers BasicLink* link = (*i).second.link; 13310037SARM gem5 Developers int src = src_dest.first; 13410037SARM gem5 Developers int dst = src_dest.second; 13510037SARM gem5 Developers component_latencies[src][dst] = link->m_latency; 13610037SARM gem5 Developers topology_weights[src][dst] = link->m_weight; 13710037SARM gem5 Developers } 13810037SARM gem5 Developers 13910037SARM gem5 Developers // Walk topology and hookup the links 14010037SARM gem5 Developers Matrix dist = shortest_path(topology_weights, component_latencies, 14110037SARM gem5 Developers component_inter_switches); 14210037SARM gem5 Developers 14310037SARM gem5 Developers for (int i = 0; i < topology_weights.size(); i++) { 14411005Sandreas.sandberg@arm.com for (int j = 0; j < topology_weights[i].size(); j++) { 14510037SARM gem5 Developers int weight = topology_weights[i][j]; 14610037SARM gem5 Developers if (weight > 0 && weight != INFINITE_LATENCY) { 14710037SARM gem5 Developers NetDest destination_set = 14810037SARM gem5 Developers shortest_path_to_node(i, j, topology_weights, dist); 14910037SARM gem5 Developers makeLink(net, i, j, destination_set); 15010037SARM gem5 Developers } 15110037SARM gem5 Developers } 15210037SARM gem5 Developers } 15310037SARM gem5 Developers} 15410037SARM gem5 Developers 15510037SARM gem5 Developersvoid 15610037SARM gem5 DevelopersTopology::addLink(SwitchID src, SwitchID dest, BasicLink* link) 15710037SARM gem5 Developers{ 15810037SARM gem5 Developers assert(src <= m_number_of_switches+m_nodes+m_nodes); 15910037SARM gem5 Developers assert(dest <= m_number_of_switches+m_nodes+m_nodes); 16010037SARM gem5 Developers 16110037SARM gem5 Developers std::pair<int, int> src_dest_pair; 16210037SARM gem5 Developers LinkEntry link_entry; 16310037SARM gem5 Developers 16410037SARM gem5 Developers src_dest_pair.first = src; 16510037SARM gem5 Developers src_dest_pair.second = dest; 16610037SARM gem5 Developers link_entry.link = link; 16710037SARM gem5 Developers m_link_map[src_dest_pair] = link_entry; 16810037SARM gem5 Developers} 16910037SARM gem5 Developers 17010037SARM gem5 Developersvoid 17110037SARM gem5 DevelopersTopology::makeLink(Network *net, SwitchID src, SwitchID dest, 17210037SARM gem5 Developers const NetDest& routing_table_entry) 17310037SARM gem5 Developers{ 17410037SARM gem5 Developers // Make sure we're not trying to connect two end-point nodes 17510037SARM gem5 Developers // directly together 17610037SARM gem5 Developers assert(src >= 2 * m_nodes || dest >= 2 * m_nodes); 17710037SARM gem5 Developers 17810037SARM gem5 Developers std::pair<int, int> src_dest; 17910037SARM gem5 Developers LinkEntry link_entry; 18010037SARM gem5 Developers 18110037SARM gem5 Developers if (src < m_nodes) { 18210037SARM gem5 Developers src_dest.first = src; 18310037SARM gem5 Developers src_dest.second = dest; 18410037SARM gem5 Developers link_entry = m_link_map[src_dest]; 18510037SARM gem5 Developers net->makeExtInLink(src, dest - (2 * m_nodes), link_entry.link, 18610037SARM gem5 Developers routing_table_entry); 18710037SARM gem5 Developers } else if (dest < 2*m_nodes) { 18810037SARM gem5 Developers assert(dest >= m_nodes); 18910037SARM gem5 Developers NodeID node = dest - m_nodes; 19010037SARM gem5 Developers src_dest.first = src; 19110037SARM gem5 Developers src_dest.second = dest; 19210037SARM gem5 Developers link_entry = m_link_map[src_dest]; 19310037SARM gem5 Developers net->makeExtOutLink(src - (2 * m_nodes), node, link_entry.link, 19410037SARM gem5 Developers routing_table_entry); 19510037SARM gem5 Developers } else { 19610037SARM gem5 Developers assert((src >= 2 * m_nodes) && (dest >= 2 * m_nodes)); 19710037SARM gem5 Developers src_dest.first = src; 19810037SARM gem5 Developers src_dest.second = dest; 19910037SARM gem5 Developers link_entry = m_link_map[src_dest]; 20010037SARM gem5 Developers net->makeInternalLink(src - (2 * m_nodes), dest - (2 * m_nodes), 20110037SARM gem5 Developers link_entry.link, 20210037SARM gem5 Developers routing_table_entry); 20310037SARM gem5 Developers } 20410037SARM gem5 Developers} 20510037SARM gem5 Developers 20610037SARM gem5 Developers// The following all-pairs shortest path algorithm is based on the 20710037SARM gem5 Developers// discussion from Cormen et al., Chapter 26.1. 20810037SARM gem5 Developersvoid 20910037SARM gem5 DevelopersTopology::extend_shortest_path(Matrix ¤t_dist, Matrix &latencies, 21010037SARM gem5 Developers Matrix &inter_switches) 21110037SARM gem5 Developers{ 21210037SARM gem5 Developers bool change = true; 21310037SARM gem5 Developers int nodes = current_dist.size(); 21410037SARM gem5 Developers 21510037SARM gem5 Developers while (change) { 21610037SARM gem5 Developers change = false; 21710037SARM gem5 Developers for (int i = 0; i < nodes; i++) { 21810037SARM gem5 Developers for (int j = 0; j < nodes; j++) { 21910037SARM gem5 Developers int minimum = current_dist[i][j]; 22010037SARM gem5 Developers int previous_minimum = minimum; 22110037SARM gem5 Developers int intermediate_switch = -1; 22210037SARM gem5 Developers for (int k = 0; k < nodes; k++) { 22310037SARM gem5 Developers minimum = min(minimum, 22410037SARM gem5 Developers current_dist[i][k] + current_dist[k][j]); 22510037SARM gem5 Developers if (previous_minimum != minimum) { 22610037SARM gem5 Developers intermediate_switch = k; 22710037SARM gem5 Developers inter_switches[i][j] = 22810037SARM gem5 Developers inter_switches[i][k] + 22910037SARM gem5 Developers inter_switches[k][j] + 1; 23010037SARM gem5 Developers } 23110037SARM gem5 Developers previous_minimum = minimum; 23210037SARM gem5 Developers } 23310037SARM gem5 Developers if (current_dist[i][j] != minimum) { 23410037SARM gem5 Developers change = true; 23510037SARM gem5 Developers current_dist[i][j] = minimum; 23610037SARM gem5 Developers assert(intermediate_switch >= 0); 23710037SARM gem5 Developers assert(intermediate_switch < latencies[i].size()); 23811005Sandreas.sandberg@arm.com latencies[i][j] = latencies[i][intermediate_switch] + 23910037SARM gem5 Developers latencies[intermediate_switch][j]; 24010037SARM gem5 Developers } 24110037SARM gem5 Developers } 24210037SARM gem5 Developers } 24310037SARM gem5 Developers } 24410037SARM gem5 Developers} 24510037SARM gem5 Developers 24610037SARM gem5 DevelopersMatrix 24710037SARM gem5 DevelopersTopology::shortest_path(const Matrix &weights, Matrix &latencies, 24810037SARM gem5 Developers Matrix &inter_switches) 24910037SARM gem5 Developers{ 25010037SARM gem5 Developers Matrix dist = weights; 25110037SARM gem5 Developers extend_shortest_path(dist, latencies, inter_switches); 25210037SARM gem5 Developers return dist; 25310037SARM gem5 Developers} 25410037SARM gem5 Developers 25510037SARM gem5 Developersbool 25610037SARM gem5 DevelopersTopology::link_is_shortest_path_to_node(SwitchID src, SwitchID next, 25710037SARM gem5 Developers SwitchID final, const Matrix &weights, 25810037SARM gem5 Developers const Matrix &dist) 25910037SARM gem5 Developers{ 26010037SARM gem5 Developers return weights[src][next] + dist[next][final] == dist[src][final]; 26110037SARM gem5 Developers} 26210037SARM gem5 Developers 26310037SARM gem5 DevelopersNetDest 26410037SARM gem5 DevelopersTopology::shortest_path_to_node(SwitchID src, SwitchID next, 26510037SARM gem5 Developers const Matrix &weights, const Matrix &dist) 26610037SARM gem5 Developers{ 26710037SARM gem5 Developers NetDest result; 26810037SARM gem5 Developers int d = 0; 26910037SARM gem5 Developers int machines; 27010037SARM gem5 Developers int max_machines; 27110037SARM gem5 Developers 27210037SARM gem5 Developers machines = MachineType_NUM; 27310037SARM gem5 Developers max_machines = MachineType_base_number(MachineType_NUM); 27410037SARM gem5 Developers 27510037SARM gem5 Developers for (int m = 0; m < machines; m++) { 27610037SARM gem5 Developers for (NodeID i = 0; i < MachineType_base_count((MachineType)m); i++) { 27710037SARM gem5 Developers // we use "d+max_machines" below since the "destination" 27810037SARM gem5 Developers // switches for the machines are numbered 27910037SARM gem5 Developers // [MachineType_base_number(MachineType_NUM)... 28010037SARM gem5 Developers // 2*MachineType_base_number(MachineType_NUM)-1] for the 28110037SARM gem5 Developers // component network 28210037SARM gem5 Developers if (link_is_shortest_path_to_node(src, next, d + max_machines, 28310037SARM gem5 Developers weights, dist)) { 28410037SARM gem5 Developers MachineID mach = {(MachineType)m, i}; 28511005Sandreas.sandberg@arm.com result.add(mach); 28610037SARM gem5 Developers } 28710037SARM gem5 Developers d++; 28810037SARM gem5 Developers } 28910037SARM gem5 Developers } 29010037SARM gem5 Developers 29110037SARM gem5 Developers DPRINTF(RubyNetwork, "Returning shortest path\n" 29210037SARM gem5 Developers "(src-(2*max_machines)): %d, (next-(2*max_machines)): %d, " 29310037SARM gem5 Developers "src: %d, next: %d, result: %s\n", 29410037SARM gem5 Developers (src-(2*max_machines)), (next-(2*max_machines)), 29510037SARM gem5 Developers src, next, result); 29610037SARM gem5 Developers 29710037SARM gem5 Developers return result; 29810037SARM gem5 Developers} 29910037SARM gem5 Developers