Topology.cc revision 6285
12810Srdreslin@umich.edu 211051Sandreas.hansson@arm.com/* 311051Sandreas.hansson@arm.com * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 411051Sandreas.hansson@arm.com * All rights reserved. 511051Sandreas.hansson@arm.com * 611051Sandreas.hansson@arm.com * Redistribution and use in source and binary forms, with or without 711051Sandreas.hansson@arm.com * modification, are permitted provided that the following conditions are 811051Sandreas.hansson@arm.com * met: redistributions of source code must retain the above copyright 911051Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer; 1011051Sandreas.hansson@arm.com * redistributions in binary form must reproduce the above copyright 1111051Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer in the 1211051Sandreas.hansson@arm.com * documentation and/or other materials provided with the distribution; 1311051Sandreas.hansson@arm.com * neither the name of the copyright holders nor the names of its 1411051Sandreas.hansson@arm.com * contributors may be used to endorse or promote products derived from 1511051Sandreas.hansson@arm.com * this software without specific prior written permission. 162810Srdreslin@umich.edu * 172810Srdreslin@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 182810Srdreslin@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 192810Srdreslin@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 202810Srdreslin@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 212810Srdreslin@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 222810Srdreslin@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 232810Srdreslin@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 242810Srdreslin@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 252810Srdreslin@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 262810Srdreslin@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 272810Srdreslin@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 282810Srdreslin@umich.edu */ 292810Srdreslin@umich.edu 302810Srdreslin@umich.edu/* 312810Srdreslin@umich.edu * Topology.cc 322810Srdreslin@umich.edu * 332810Srdreslin@umich.edu * Description: See Topology.hh 342810Srdreslin@umich.edu * 352810Srdreslin@umich.edu * $Id$ 362810Srdreslin@umich.edu * 372810Srdreslin@umich.edu * */ 382810Srdreslin@umich.edu 392810Srdreslin@umich.edu#include "mem/ruby/network/simple/Topology.hh" 402810Srdreslin@umich.edu#include "mem/ruby/common/NetDest.hh" 412810Srdreslin@umich.edu#include "mem/ruby/network/Network.hh" 4211051Sandreas.hansson@arm.com#include "mem/protocol/TopologyType.hh" 4311051Sandreas.hansson@arm.com//#include "mem/ruby/config/RubyConfig.hh" 442810Srdreslin@umich.edu#include "mem/gems_common/util.hh" 4511051Sandreas.hansson@arm.com#include "mem/protocol/MachineType.hh" 4611051Sandreas.hansson@arm.com#include "mem/protocol/Protocol.hh" 472810Srdreslin@umich.edu#include "mem/ruby/system/System.hh" 482810Srdreslin@umich.edu#include <string> 492810Srdreslin@umich.edu 502810Srdreslin@umich.edustatic const int INFINITE_LATENCY = 10000; // Yes, this is a big hack 5111051Sandreas.hansson@arm.comstatic const int DEFAULT_BW_MULTIPLIER = 1; // Just to be consistent with above :) 522810Srdreslin@umich.edu 532810Srdreslin@umich.edu// Note: In this file, we use the first 2*m_nodes SwitchIDs to 5411051Sandreas.hansson@arm.com// represent the input and output endpoint links. These really are 552810Srdreslin@umich.edu// not 'switches', as they will not have a Switch object allocated for 5611051Sandreas.hansson@arm.com// them. The first m_nodes SwitchIDs are the links into the network, 5711051Sandreas.hansson@arm.com// the second m_nodes set of SwitchIDs represent the the output queues 5811051Sandreas.hansson@arm.com// of the network. 5911051Sandreas.hansson@arm.com 6011051Sandreas.hansson@arm.com// Helper functions based on chapter 29 of Cormen et al. 6111051Sandreas.hansson@arm.comstatic Matrix extend_shortest_path(const Matrix& current_dist, Matrix& latencies, Matrix& inter_switches); 6211051Sandreas.hansson@arm.comstatic Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches); 6311051Sandreas.hansson@arm.comstatic bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, const Matrix& weights, const Matrix& dist); 6411051Sandreas.hansson@arm.comstatic NetDest shortest_path_to_node(SwitchID src, SwitchID next, const Matrix& weights, const Matrix& dist); 6511051Sandreas.hansson@arm.com 6611053Sandreas.hansson@arm.comTopology::Topology(const string & name) 6711053Sandreas.hansson@arm.com : m_name(name) 6811051Sandreas.hansson@arm.com{ 6911051Sandreas.hansson@arm.com m_network_ptr = NULL; 7011051Sandreas.hansson@arm.com m_nodes = MachineType_base_number(MachineType_NUM); 7111197Sandreas.hansson@arm.com m_number_of_switches = 0; 7211197Sandreas.hansson@arm.com} 7311199Sandreas.hansson@arm.com 7411197Sandreas.hansson@arm.comvoid Topology::init(const vector<string> & argv) 7511197Sandreas.hansson@arm.com{ 7611197Sandreas.hansson@arm.com for (size_t i=0; i<argv.size(); i+=2) { 7711051Sandreas.hansson@arm.com if (argv[i] == "network") 7811051Sandreas.hansson@arm.com m_network_ptr = RubySystem::getNetwork(); 7911051Sandreas.hansson@arm.com else if (argv[i] == "connections") 8011051Sandreas.hansson@arm.com m_connections = argv[i+1]; 8111051Sandreas.hansson@arm.com else if (argv[i] == "print_config") { 8211051Sandreas.hansson@arm.com m_print_config = string_to_bool(argv[i+1]); 8311051Sandreas.hansson@arm.com cerr << "print config: " << m_print_config << endl; 8411051Sandreas.hansson@arm.com } 8511051Sandreas.hansson@arm.com } 8611051Sandreas.hansson@arm.com assert(m_network_ptr != NULL); 8711051Sandreas.hansson@arm.com} 8811051Sandreas.hansson@arm.com 8911051Sandreas.hansson@arm.comvoid Topology::makeTopology() 9011051Sandreas.hansson@arm.com{ 9111051Sandreas.hansson@arm.com /* 9211051Sandreas.hansson@arm.com if (m_nodes == 1) { 9311051Sandreas.hansson@arm.com SwitchID id = newSwitchID(); 9411051Sandreas.hansson@arm.com addLink(0, id, m_network_ptr->getOffChipLinkLatency()); 9511051Sandreas.hansson@arm.com addLink(id, 1, m_network_ptr->getOffChipLinkLatency()); 9611051Sandreas.hansson@arm.com return; 9711051Sandreas.hansson@arm.com } 9811051Sandreas.hansson@arm.com */ 9911051Sandreas.hansson@arm.com assert(m_nodes > 1); 10011051Sandreas.hansson@arm.com 10111051Sandreas.hansson@arm.com Vector< Vector < SwitchID > > nodePairs; // node pairs extracted from the file 10211051Sandreas.hansson@arm.com Vector<int> latencies; // link latencies for each link extracted 10311051Sandreas.hansson@arm.com Vector<int> bw_multis; // bw multipliers for each link extracted 10411051Sandreas.hansson@arm.com Vector<int> weights; // link weights used to enfore e-cube deadlock free routing 10511051Sandreas.hansson@arm.com Vector< SwitchID > int_network_switches; // internal switches extracted from the file 10611051Sandreas.hansson@arm.com Vector<bool> endpointConnectionExist; // used to ensure all endpoints are connected to the network 10711051Sandreas.hansson@arm.com 10811051Sandreas.hansson@arm.com endpointConnectionExist.setSize(m_nodes); 10911051Sandreas.hansson@arm.com 11011051Sandreas.hansson@arm.com // initialize endpoint check vector 11111051Sandreas.hansson@arm.com for (int k = 0; k < endpointConnectionExist.size(); k++) { 11211051Sandreas.hansson@arm.com endpointConnectionExist[k] = false; 11311051Sandreas.hansson@arm.com } 11411051Sandreas.hansson@arm.com 11511051Sandreas.hansson@arm.com stringstream networkFile( m_connections ); 11611051Sandreas.hansson@arm.com 11711051Sandreas.hansson@arm.com string line = ""; 11811051Sandreas.hansson@arm.com 11911051Sandreas.hansson@arm.com while (!networkFile.eof()) { 12011051Sandreas.hansson@arm.com 12111051Sandreas.hansson@arm.com Vector < SwitchID > nodes; 12211051Sandreas.hansson@arm.com nodes.setSize(2); 12311051Sandreas.hansson@arm.com int latency = -1; // null latency 12411051Sandreas.hansson@arm.com int weight = -1; // null weight 12511051Sandreas.hansson@arm.com int bw_multiplier = DEFAULT_BW_MULTIPLIER; // default multiplier incase the network file doesn't define it 12611051Sandreas.hansson@arm.com int i = 0; // node pair index 12711051Sandreas.hansson@arm.com int varsFound = 0; // number of varsFound on the line 12811051Sandreas.hansson@arm.com int internalNodes = 0; // used to determine if the link is between 2 internal nodes 12911051Sandreas.hansson@arm.com std::getline(networkFile, line, '\n'); 13011051Sandreas.hansson@arm.com string varStr = string_split(line, ' '); 13111051Sandreas.hansson@arm.com 13211051Sandreas.hansson@arm.com // parse the current line in the file 13311051Sandreas.hansson@arm.com while (varStr != "") { 13411051Sandreas.hansson@arm.com string label = string_split(varStr, ':'); 13511051Sandreas.hansson@arm.com 13611051Sandreas.hansson@arm.com // valid node labels 13711051Sandreas.hansson@arm.com if (label == "ext_node" || label == "int_node") { 13811051Sandreas.hansson@arm.com ASSERT(i < 2); // one link between 2 switches per line 13911051Sandreas.hansson@arm.com varsFound++; 14011051Sandreas.hansson@arm.com bool isNewIntSwitch = true; 14111051Sandreas.hansson@arm.com if (label == "ext_node") { // input link to node 14211051Sandreas.hansson@arm.com MachineType machine = string_to_MachineType(string_split(varStr, ':')); 14311051Sandreas.hansson@arm.com string nodeStr = string_split(varStr, ':'); 14411051Sandreas.hansson@arm.com nodes[i] = MachineType_base_number(machine) 14511051Sandreas.hansson@arm.com + atoi(nodeStr.c_str()); 14611051Sandreas.hansson@arm.com 14711051Sandreas.hansson@arm.com // in nodes should be numbered 0 to m_nodes-1 14811051Sandreas.hansson@arm.com ASSERT(nodes[i] >= 0 && nodes[i] < m_nodes); 14911051Sandreas.hansson@arm.com isNewIntSwitch = false; 15011051Sandreas.hansson@arm.com endpointConnectionExist[nodes[i]] = true; 15111051Sandreas.hansson@arm.com } 15211051Sandreas.hansson@arm.com if (label == "int_node") { // interior node 15311051Sandreas.hansson@arm.com nodes[i] = atoi((string_split(varStr, ':')).c_str())+m_nodes*2; 15411051Sandreas.hansson@arm.com // in nodes should be numbered >= m_nodes*2 15511051Sandreas.hansson@arm.com ASSERT(nodes[i] >= m_nodes*2); 15611051Sandreas.hansson@arm.com for (int k = 0; k < int_network_switches.size(); k++) { 15711051Sandreas.hansson@arm.com if (int_network_switches[k] == nodes[i]) { 15811051Sandreas.hansson@arm.com isNewIntSwitch = false; 15911051Sandreas.hansson@arm.com } 16011051Sandreas.hansson@arm.com } 16111051Sandreas.hansson@arm.com if (isNewIntSwitch) { // if internal switch 16211051Sandreas.hansson@arm.com m_number_of_switches++; 16311051Sandreas.hansson@arm.com int_network_switches.insertAtBottom(nodes[i]); 16411051Sandreas.hansson@arm.com } 16511051Sandreas.hansson@arm.com internalNodes++; 16611051Sandreas.hansson@arm.com } 16711051Sandreas.hansson@arm.com i++; 16811051Sandreas.hansson@arm.com } else if (label == "link_latency") { 16911051Sandreas.hansson@arm.com latency = atoi((string_split(varStr, ':')).c_str()); 17011051Sandreas.hansson@arm.com varsFound++; 17111051Sandreas.hansson@arm.com } else if (label == "bw_multiplier") { // not necessary, defaults to DEFAULT_BW_MULTIPLIER 17211051Sandreas.hansson@arm.com bw_multiplier = atoi((string_split(varStr, ':')).c_str()); 17311051Sandreas.hansson@arm.com } else if (label == "link_weight") { // not necessary, defaults to link_latency 17411051Sandreas.hansson@arm.com weight = atoi((string_split(varStr, ':')).c_str()); 17511051Sandreas.hansson@arm.com } else { 17611051Sandreas.hansson@arm.com cerr << "Error: Unexpected Identifier: " << label << endl; 17711051Sandreas.hansson@arm.com exit(1); 17811051Sandreas.hansson@arm.com } 17911051Sandreas.hansson@arm.com varStr = string_split(line, ' '); 18011051Sandreas.hansson@arm.com } 18111051Sandreas.hansson@arm.com if (varsFound == 3) { // all three necessary link variables where found so add the link 18211051Sandreas.hansson@arm.com nodePairs.insertAtBottom(nodes); 18311051Sandreas.hansson@arm.com latencies.insertAtBottom(latency); 18411051Sandreas.hansson@arm.com if (weight != -1) { 18511051Sandreas.hansson@arm.com weights.insertAtBottom(weight); 18611051Sandreas.hansson@arm.com } else { 18711051Sandreas.hansson@arm.com weights.insertAtBottom(latency); 18811051Sandreas.hansson@arm.com } 18911051Sandreas.hansson@arm.com bw_multis.insertAtBottom(bw_multiplier); 19011051Sandreas.hansson@arm.com Vector < SwitchID > otherDirectionNodes; 19111051Sandreas.hansson@arm.com otherDirectionNodes.setSize(2); 19211051Sandreas.hansson@arm.com otherDirectionNodes[0] = nodes[1]; 19311051Sandreas.hansson@arm.com if (internalNodes == 2) { // this is an internal link 19411051Sandreas.hansson@arm.com otherDirectionNodes[1] = nodes[0]; 19511051Sandreas.hansson@arm.com } else { 19611051Sandreas.hansson@arm.com otherDirectionNodes[1] = nodes[0]+m_nodes; 19711051Sandreas.hansson@arm.com } 19811051Sandreas.hansson@arm.com nodePairs.insertAtBottom(otherDirectionNodes); 19911051Sandreas.hansson@arm.com latencies.insertAtBottom(latency); 20011051Sandreas.hansson@arm.com if (weight != -1) { 20111051Sandreas.hansson@arm.com weights.insertAtBottom(weight); 20211051Sandreas.hansson@arm.com } else { 20311051Sandreas.hansson@arm.com weights.insertAtBottom(latency); 20411051Sandreas.hansson@arm.com } 20511051Sandreas.hansson@arm.com bw_multis.insertAtBottom(bw_multiplier); 20611197Sandreas.hansson@arm.com } else { 20711197Sandreas.hansson@arm.com if (varsFound != 0) { // if this is not a valid link, then no vars should have been found 20811197Sandreas.hansson@arm.com cerr << "Error in line: " << line << endl; 20911197Sandreas.hansson@arm.com exit(1); 21011051Sandreas.hansson@arm.com } 21111051Sandreas.hansson@arm.com } 21211051Sandreas.hansson@arm.com } // end of file 21311051Sandreas.hansson@arm.com 21411051Sandreas.hansson@arm.com // makes sure all enpoints are connected in the soon to be created network 21511051Sandreas.hansson@arm.com for (int k = 0; k < endpointConnectionExist.size(); k++) { 21611051Sandreas.hansson@arm.com if (endpointConnectionExist[k] == false) { 21711051Sandreas.hansson@arm.com cerr << "Error: Unconnected Endpoint: " << k << endl; 21811051Sandreas.hansson@arm.com exit(1); 21911051Sandreas.hansson@arm.com } 22011051Sandreas.hansson@arm.com } 22111051Sandreas.hansson@arm.com 22211051Sandreas.hansson@arm.com ASSERT(nodePairs.size() == latencies.size() && latencies.size() == bw_multis.size() && latencies.size() == weights.size()) 22311051Sandreas.hansson@arm.com for (int k = 0; k < nodePairs.size(); k++) { 22411051Sandreas.hansson@arm.com ASSERT(nodePairs[k].size() == 2); 22511051Sandreas.hansson@arm.com addLink(nodePairs[k][0], nodePairs[k][1], latencies[k], bw_multis[k], weights[k]); 22611051Sandreas.hansson@arm.com } 22711051Sandreas.hansson@arm.com 22811197Sandreas.hansson@arm.com // initialize component latencies record 22911197Sandreas.hansson@arm.com m_component_latencies.setSize(0); 23011051Sandreas.hansson@arm.com m_component_inter_switches.setSize(0); 23111197Sandreas.hansson@arm.com} 23211197Sandreas.hansson@arm.com 23311197Sandreas.hansson@arm.com 23411197Sandreas.hansson@arm.comvoid Topology::createLinks(bool isReconfiguration) 23511197Sandreas.hansson@arm.com{ 23611197Sandreas.hansson@arm.com // Find maximum switchID 23711197Sandreas.hansson@arm.com 23811197Sandreas.hansson@arm.com SwitchID max_switch_id = 0; 23911197Sandreas.hansson@arm.com for (int i=0; i<m_links_src_vector.size(); i++) { 24011197Sandreas.hansson@arm.com max_switch_id = max(max_switch_id, m_links_src_vector[i]); 24111197Sandreas.hansson@arm.com max_switch_id = max(max_switch_id, m_links_dest_vector[i]); 24211197Sandreas.hansson@arm.com } 24311197Sandreas.hansson@arm.com 24411197Sandreas.hansson@arm.com // Initialize weight vector 24511051Sandreas.hansson@arm.com Matrix topology_weights; 24611197Sandreas.hansson@arm.com Matrix topology_latency; 24711197Sandreas.hansson@arm.com Matrix topology_bw_multis; 24811197Sandreas.hansson@arm.com int num_switches = max_switch_id+1; 24911197Sandreas.hansson@arm.com topology_weights.setSize(num_switches); 25011197Sandreas.hansson@arm.com topology_latency.setSize(num_switches); 25111197Sandreas.hansson@arm.com topology_bw_multis.setSize(num_switches); 25211051Sandreas.hansson@arm.com m_component_latencies.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 25311051Sandreas.hansson@arm.com m_component_inter_switches.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 25411051Sandreas.hansson@arm.com for(int i=0; i<topology_weights.size(); i++) { 25511051Sandreas.hansson@arm.com topology_weights[i].setSize(num_switches); 25611051Sandreas.hansson@arm.com topology_latency[i].setSize(num_switches); 25711051Sandreas.hansson@arm.com topology_bw_multis[i].setSize(num_switches); 25811051Sandreas.hansson@arm.com m_component_latencies[i].setSize(num_switches); 25911051Sandreas.hansson@arm.com m_component_inter_switches[i].setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 26011051Sandreas.hansson@arm.com for(int j=0; j<topology_weights[i].size(); j++) { 26111051Sandreas.hansson@arm.com topology_weights[i][j] = INFINITE_LATENCY; 26211051Sandreas.hansson@arm.com topology_latency[i][j] = -1; // initialize to an invalid value 26311051Sandreas.hansson@arm.com topology_bw_multis[i][j] = -1; // initialize to an invalid value 26411051Sandreas.hansson@arm.com m_component_latencies[i][j] = -1; // initialize to an invalid value 26511051Sandreas.hansson@arm.com m_component_inter_switches[i][j] = 0; // initially assume direct connections / no intermediate switches between components 26611051Sandreas.hansson@arm.com } 26711051Sandreas.hansson@arm.com } 26811051Sandreas.hansson@arm.com 26911051Sandreas.hansson@arm.com // Set identity weights to zero 27011197Sandreas.hansson@arm.com for(int i=0; i<topology_weights.size(); i++) { 27111197Sandreas.hansson@arm.com topology_weights[i][i] = 0; 27211197Sandreas.hansson@arm.com } 27311197Sandreas.hansson@arm.com 27411051Sandreas.hansson@arm.com // Fill in the topology weights and bandwidth multipliers 27511051Sandreas.hansson@arm.com for (int i=0; i<m_links_src_vector.size(); i++) { 27611051Sandreas.hansson@arm.com topology_weights[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_weight_vector[i]; 27711051Sandreas.hansson@arm.com topology_latency[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; 27811051Sandreas.hansson@arm.com m_component_latencies[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; // initialize to latency vector 27911051Sandreas.hansson@arm.com topology_bw_multis[m_links_src_vector[i]][m_links_dest_vector[i]] = m_bw_multiplier_vector[i]; 28011051Sandreas.hansson@arm.com } 28111051Sandreas.hansson@arm.com 28211051Sandreas.hansson@arm.com // Walk topology and hookup the links 28311051Sandreas.hansson@arm.com Matrix dist = shortest_path(topology_weights, m_component_latencies, m_component_inter_switches); 28411051Sandreas.hansson@arm.com for(int i=0; i<topology_weights.size(); i++) { 28511051Sandreas.hansson@arm.com for(int j=0; j<topology_weights[i].size(); j++) { 28611051Sandreas.hansson@arm.com int weight = topology_weights[i][j]; 28711051Sandreas.hansson@arm.com int bw_multiplier = topology_bw_multis[i][j]; 28811051Sandreas.hansson@arm.com int latency = topology_latency[i][j]; 28911051Sandreas.hansson@arm.com if (weight > 0 && weight != INFINITE_LATENCY) { 29011051Sandreas.hansson@arm.com NetDest destination_set = shortest_path_to_node(i, j, topology_weights, dist); 29111051Sandreas.hansson@arm.com assert(latency != -1); 29211051Sandreas.hansson@arm.com makeLink(i, j, destination_set, latency, weight, bw_multiplier, isReconfiguration); 29311051Sandreas.hansson@arm.com } 29411051Sandreas.hansson@arm.com } 29511051Sandreas.hansson@arm.com } 29611051Sandreas.hansson@arm.com} 29711051Sandreas.hansson@arm.com/* 29811051Sandreas.hansson@arm.comvoid Topology::makeSwitchesPerChip(Vector< Vector < SwitchID > > &nodePairs, Vector<int> &latencies, Vector<int> &bw_multis, int numberOfChipSwitches) 29911051Sandreas.hansson@arm.com{ 30011051Sandreas.hansson@arm.com 30111051Sandreas.hansson@arm.com Vector < SwitchID > nodes; // temporary buffer 30211051Sandreas.hansson@arm.com nodes.setSize(2); 30311051Sandreas.hansson@arm.com 30411051Sandreas.hansson@arm.com Vector<bool> endpointConnectionExist; // used to ensure all endpoints are connected to the network 30511051Sandreas.hansson@arm.com endpointConnectionExist.setSize(m_nodes); 30611051Sandreas.hansson@arm.com // initialize endpoint check vector 30711051Sandreas.hansson@arm.com for (int k = 0; k < endpointConnectionExist.size(); k++) { 30811051Sandreas.hansson@arm.com endpointConnectionExist[k] = false; 30911051Sandreas.hansson@arm.com } 31011051Sandreas.hansson@arm.com 31111051Sandreas.hansson@arm.com Vector<int> componentCount; 31211051Sandreas.hansson@arm.com componentCount.setSize(MachineType_NUM); 31311051Sandreas.hansson@arm.com for (MachineType mType = MachineType_FIRST; mType < MachineType_NUM; ++mType) { 31411051Sandreas.hansson@arm.com componentCount[mType] = 0; 31511051Sandreas.hansson@arm.com } 31611051Sandreas.hansson@arm.com 31711051Sandreas.hansson@arm.com // components to/from network links 31811051Sandreas.hansson@arm.com // TODO: drh5: bring back chips!!! 31911051Sandreas.hansson@arm.com for (int chip = 0; chip < RubyConfig::getNumberOfChips(); chip++) { 32011051Sandreas.hansson@arm.com for (MachineType mType = MachineType_FIRST; mType < MachineType_NUM; ++mType) { 32111199Sandreas.hansson@arm.com for (int component = 0; component < MachineType_base_count(mType); component++) { 32211051Sandreas.hansson@arm.com 32311051Sandreas.hansson@arm.com int latency = -1; 32411051Sandreas.hansson@arm.com int bw_multiplier = -1; // internal link bw multiplier of the global bandwidth 32511051Sandreas.hansson@arm.com if (mType != MachineType_Directory) { 32611051Sandreas.hansson@arm.com latency = RubyConfig::getOnChipLinkLatency(); // internal link latency 32711051Sandreas.hansson@arm.com bw_multiplier = 10; // internal link bw multiplier of the global bandwidth 32811051Sandreas.hansson@arm.com } else { 32911051Sandreas.hansson@arm.com latency = RubyConfig::getNetworkLinkLatency(); // local memory latency 33011051Sandreas.hansson@arm.com bw_multiplier = 1; // local memory link bw multiplier of the global bandwidth 33111051Sandreas.hansson@arm.com } 33211051Sandreas.hansson@arm.com nodes[0] = MachineType_base_number(mType)+componentCount[mType]; 33311051Sandreas.hansson@arm.com nodes[1] = chip+m_nodes*2; // this is the chip's internal switch id # 33411051Sandreas.hansson@arm.com 33511051Sandreas.hansson@arm.com // insert link 33611051Sandreas.hansson@arm.com nodePairs.insertAtBottom(nodes); 33711051Sandreas.hansson@arm.com latencies.insertAtBottom(latency); 33811051Sandreas.hansson@arm.com bw_multis.insertAtBottom(bw_multiplier); 33911051Sandreas.hansson@arm.com //bw_multis.insertAtBottom(componentCount[mType]+MachineType_base_number((MachineType)mType)); 34011051Sandreas.hansson@arm.com 34111051Sandreas.hansson@arm.com // opposite direction link 34211051Sandreas.hansson@arm.com Vector < SwitchID > otherDirectionNodes; 34311051Sandreas.hansson@arm.com otherDirectionNodes.setSize(2); 34411051Sandreas.hansson@arm.com otherDirectionNodes[0] = nodes[1]; 34511051Sandreas.hansson@arm.com otherDirectionNodes[1] = nodes[0]+m_nodes; 34611051Sandreas.hansson@arm.com nodePairs.insertAtBottom(otherDirectionNodes); 34711199Sandreas.hansson@arm.com latencies.insertAtBottom(latency); 34811051Sandreas.hansson@arm.com bw_multis.insertAtBottom(bw_multiplier); 34911051Sandreas.hansson@arm.com 35011051Sandreas.hansson@arm.com assert(!endpointConnectionExist[nodes[0]]); 35111051Sandreas.hansson@arm.com endpointConnectionExist[nodes[0]] = true; 35211051Sandreas.hansson@arm.com componentCount[mType]++; 35311051Sandreas.hansson@arm.com } 35411051Sandreas.hansson@arm.com } 35511051Sandreas.hansson@arm.com } 35611051Sandreas.hansson@arm.com 35711051Sandreas.hansson@arm.com // make sure all enpoints are connected in the soon to be created network 35811051Sandreas.hansson@arm.com for (int k = 0; k < endpointConnectionExist.size(); k++) { 35911051Sandreas.hansson@arm.com if (endpointConnectionExist[k] == false) { 36011199Sandreas.hansson@arm.com cerr << "Error: Unconnected Endpoint: " << k << endl; 36111199Sandreas.hansson@arm.com exit(1); 36211199Sandreas.hansson@arm.com } 36311199Sandreas.hansson@arm.com } 36411199Sandreas.hansson@arm.com 36511199Sandreas.hansson@arm.com // secondary check to ensure we saw the correct machine counts 36611199Sandreas.hansson@arm.com for (MachineType mType = MachineType_FIRST; mType < MachineType_NUM; ++mType) { 36711199Sandreas.hansson@arm.com assert(componentCount[mType] == MachineType_base_count((MachineType)mType)); 36811199Sandreas.hansson@arm.com } 36911199Sandreas.hansson@arm.com 37011199Sandreas.hansson@arm.com} 37111199Sandreas.hansson@arm.com*/ 37211199Sandreas.hansson@arm.com 37311199Sandreas.hansson@arm.com 37411199Sandreas.hansson@arm.comSwitchID Topology::newSwitchID() 37511199Sandreas.hansson@arm.com{ 37611199Sandreas.hansson@arm.com m_number_of_switches++; 37711199Sandreas.hansson@arm.com return m_number_of_switches-1+m_nodes+m_nodes; 37811199Sandreas.hansson@arm.com} 37911199Sandreas.hansson@arm.com 38011199Sandreas.hansson@arm.comvoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency) 38111199Sandreas.hansson@arm.com{ 38211199Sandreas.hansson@arm.com addLink(src, dest, link_latency, DEFAULT_BW_MULTIPLIER, link_latency); 38311199Sandreas.hansson@arm.com} 38411051Sandreas.hansson@arm.com 38511051Sandreas.hansson@arm.comvoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier) 38611051Sandreas.hansson@arm.com{ 38711051Sandreas.hansson@arm.com addLink(src, dest, link_latency, bw_multiplier, link_latency); 38811051Sandreas.hansson@arm.com} 38911199Sandreas.hansson@arm.com 39011051Sandreas.hansson@arm.comvoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier, int link_weight) 39111199Sandreas.hansson@arm.com{ 39211199Sandreas.hansson@arm.com ASSERT(src <= m_number_of_switches+m_nodes+m_nodes); 39311199Sandreas.hansson@arm.com ASSERT(dest <= m_number_of_switches+m_nodes+m_nodes); 39411199Sandreas.hansson@arm.com m_links_src_vector.insertAtBottom(src); 39511199Sandreas.hansson@arm.com m_links_dest_vector.insertAtBottom(dest); 39611199Sandreas.hansson@arm.com m_links_latency_vector.insertAtBottom(link_latency); 39711199Sandreas.hansson@arm.com m_links_weight_vector.insertAtBottom(link_weight); 39811199Sandreas.hansson@arm.com m_bw_multiplier_vector.insertAtBottom(bw_multiplier); 39911199Sandreas.hansson@arm.com} 40011199Sandreas.hansson@arm.com 40111199Sandreas.hansson@arm.comvoid Topology::makeLink(SwitchID src, SwitchID dest, const NetDest& routing_table_entry, int link_latency, int link_weight, int bw_multiplier, bool isReconfiguration) 40211199Sandreas.hansson@arm.com{ 40311051Sandreas.hansson@arm.com // Make sure we're not trying to connect two end-point nodes directly together 40411051Sandreas.hansson@arm.com assert((src >= 2*m_nodes) || (dest >= 2*m_nodes)); 40511051Sandreas.hansson@arm.com 40611051Sandreas.hansson@arm.com if (src < m_nodes) { 40711051Sandreas.hansson@arm.com m_network_ptr->makeInLink(src, dest-(2*m_nodes), routing_table_entry, link_latency, bw_multiplier, isReconfiguration); 40811051Sandreas.hansson@arm.com } else if (dest < 2*m_nodes) { 40911051Sandreas.hansson@arm.com assert(dest >= m_nodes); 41011051Sandreas.hansson@arm.com NodeID node = dest-m_nodes; 41111051Sandreas.hansson@arm.com m_network_ptr->makeOutLink(src-(2*m_nodes), node, routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 41211051Sandreas.hansson@arm.com } else { 41311051Sandreas.hansson@arm.com assert((src >= 2*m_nodes) && (dest >= 2*m_nodes)); 41411051Sandreas.hansson@arm.com m_network_ptr->makeInternalLink(src-(2*m_nodes), dest-(2*m_nodes), routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 41511051Sandreas.hansson@arm.com } 41611051Sandreas.hansson@arm.com} 41711051Sandreas.hansson@arm.com 41811199Sandreas.hansson@arm.comvoid Topology::printConfig(ostream& out) const 41911199Sandreas.hansson@arm.com{ 42011199Sandreas.hansson@arm.com if (m_print_config == false) return; 42111199Sandreas.hansson@arm.com 42211199Sandreas.hansson@arm.com assert(m_component_latencies.size() > 0); 42311051Sandreas.hansson@arm.com 42411051Sandreas.hansson@arm.com out << "--- Begin Topology Print ---" << endl; 42511051Sandreas.hansson@arm.com out << endl; 42611051Sandreas.hansson@arm.com out << "Topology print ONLY indicates the _NETWORK_ latency between two machines" << endl; 42711051Sandreas.hansson@arm.com out << "It does NOT include the latency within the machines" << endl; 42811051Sandreas.hansson@arm.com out << endl; 42911051Sandreas.hansson@arm.com for (int m=0; m<MachineType_NUM; m++) { 43011051Sandreas.hansson@arm.com for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 43111051Sandreas.hansson@arm.com MachineID cur_mach = {(MachineType)m, i}; 43211051Sandreas.hansson@arm.com out << cur_mach << " Network Latencies" << endl; 43311051Sandreas.hansson@arm.com for (int n=0; n<MachineType_NUM; n++) { 43411051Sandreas.hansson@arm.com for (int j=0; j<MachineType_base_count((MachineType)n); j++) { 43511051Sandreas.hansson@arm.com MachineID dest_mach = {(MachineType)n, j}; 43611051Sandreas.hansson@arm.com if (cur_mach != dest_mach) { 43711051Sandreas.hansson@arm.com int link_latency = m_component_latencies[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 43811051Sandreas.hansson@arm.com int intermediate_switches = m_component_inter_switches[MachineType_base_number((MachineType)m)+i][MachineType_base_number(MachineType_NUM)+MachineType_base_number((MachineType)n)+j]; 43911051Sandreas.hansson@arm.com out << " " << cur_mach << " -> " << dest_mach << " net_lat: " 44011051Sandreas.hansson@arm.com << link_latency+intermediate_switches << endl; // NOTE switches are assumed to have single cycle latency 44111051Sandreas.hansson@arm.com } 44211051Sandreas.hansson@arm.com } 44311051Sandreas.hansson@arm.com } 44411051Sandreas.hansson@arm.com out << endl; 44511051Sandreas.hansson@arm.com } 44611051Sandreas.hansson@arm.com } 44711051Sandreas.hansson@arm.com 44811051Sandreas.hansson@arm.com out << "--- End Topology Print ---" << endl; 44911051Sandreas.hansson@arm.com} 45011051Sandreas.hansson@arm.com 45111051Sandreas.hansson@arm.com/**************************************************************************/ 45211051Sandreas.hansson@arm.com 45311051Sandreas.hansson@arm.com// The following all-pairs shortest path algorithm is based on the 45411051Sandreas.hansson@arm.com// discussion from Cormen et al., Chapter 26.1. 45511051Sandreas.hansson@arm.com 45611051Sandreas.hansson@arm.comstatic void extend_shortest_path(Matrix& current_dist, Matrix& latencies, Matrix& inter_switches) 45711051Sandreas.hansson@arm.com{ 45811051Sandreas.hansson@arm.com bool change = true; 45911051Sandreas.hansson@arm.com int nodes = current_dist.size(); 46011051Sandreas.hansson@arm.com 46111051Sandreas.hansson@arm.com while (change) { 46211051Sandreas.hansson@arm.com change = false; 46311051Sandreas.hansson@arm.com for (int i=0; i<nodes; i++) { 46411051Sandreas.hansson@arm.com for (int j=0; j<nodes; j++) { 46511051Sandreas.hansson@arm.com int minimum = current_dist[i][j]; 46611051Sandreas.hansson@arm.com int previous_minimum = minimum; 46711051Sandreas.hansson@arm.com int intermediate_switch = -1; 46811051Sandreas.hansson@arm.com for (int k=0; k<nodes; k++) { 46911051Sandreas.hansson@arm.com minimum = min(minimum, current_dist[i][k] + current_dist[k][j]); 47011051Sandreas.hansson@arm.com if (previous_minimum != minimum) { 47111051Sandreas.hansson@arm.com intermediate_switch = k; 47211051Sandreas.hansson@arm.com inter_switches[i][j] = inter_switches[i][k] + inter_switches[k][j] + 1; 47311051Sandreas.hansson@arm.com } 47411051Sandreas.hansson@arm.com previous_minimum = minimum; 47511051Sandreas.hansson@arm.com } 47611051Sandreas.hansson@arm.com if (current_dist[i][j] != minimum) { 47711051Sandreas.hansson@arm.com change = true; 47811051Sandreas.hansson@arm.com current_dist[i][j] = minimum; 47911051Sandreas.hansson@arm.com assert(intermediate_switch >= 0); 48011051Sandreas.hansson@arm.com assert(intermediate_switch < latencies[i].size()); 48111051Sandreas.hansson@arm.com latencies[i][j] = latencies[i][intermediate_switch] + latencies[intermediate_switch][j]; 48211051Sandreas.hansson@arm.com } 48311051Sandreas.hansson@arm.com } 48411051Sandreas.hansson@arm.com } 48511051Sandreas.hansson@arm.com } 48611051Sandreas.hansson@arm.com} 48711051Sandreas.hansson@arm.com 48811051Sandreas.hansson@arm.comstatic Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches) 48911051Sandreas.hansson@arm.com{ 49011051Sandreas.hansson@arm.com Matrix dist = weights; 49111051Sandreas.hansson@arm.com extend_shortest_path(dist, latencies, inter_switches); 49211051Sandreas.hansson@arm.com return dist; 49311051Sandreas.hansson@arm.com} 49411199Sandreas.hansson@arm.com 49511199Sandreas.hansson@arm.comstatic bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, 49611199Sandreas.hansson@arm.com const Matrix& weights, const Matrix& dist) 49711199Sandreas.hansson@arm.com{ 49811199Sandreas.hansson@arm.com return (weights[src][next] + dist[next][final] == dist[src][final]); 49911051Sandreas.hansson@arm.com} 50011199Sandreas.hansson@arm.com 50111051Sandreas.hansson@arm.comstatic NetDest shortest_path_to_node(SwitchID src, SwitchID next, 50211051Sandreas.hansson@arm.com const Matrix& weights, const Matrix& dist) 50311051Sandreas.hansson@arm.com{ 50411051Sandreas.hansson@arm.com NetDest result; 50511051Sandreas.hansson@arm.com int d = 0; 50611051Sandreas.hansson@arm.com int machines; 50711051Sandreas.hansson@arm.com int max_machines; 50811051Sandreas.hansson@arm.com 50911051Sandreas.hansson@arm.com machines = MachineType_NUM; 51011051Sandreas.hansson@arm.com max_machines = MachineType_base_number(MachineType_NUM); 51111051Sandreas.hansson@arm.com 51211051Sandreas.hansson@arm.com for (int m=0; m<machines; m++) { 51311051Sandreas.hansson@arm.com for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 51411051Sandreas.hansson@arm.com // we use "d+max_machines" below since the "destination" switches for the machines are numbered 51511051Sandreas.hansson@arm.com // [MachineType_base_number(MachineType_NUM)...2*MachineType_base_number(MachineType_NUM)-1] 51611051Sandreas.hansson@arm.com // for the component network 51711051Sandreas.hansson@arm.com if (link_is_shortest_path_to_node(src, next, 51811130Sali.jafri@arm.com d+max_machines, 51911130Sali.jafri@arm.com weights, dist)) { 52011130Sali.jafri@arm.com MachineID mach = {(MachineType)m, i}; 52111130Sali.jafri@arm.com result.add(mach); 52211130Sali.jafri@arm.com } 52311130Sali.jafri@arm.com d++; 52411130Sali.jafri@arm.com } 52511130Sali.jafri@arm.com } 52611130Sali.jafri@arm.com 52711199Sandreas.hansson@arm.com DEBUG_MSG(NETWORK_COMP, MedPrio, "returning shortest path"); 52811130Sali.jafri@arm.com DEBUG_EXPR(NETWORK_COMP, MedPrio, (src-(2*max_machines))); 52911130Sali.jafri@arm.com DEBUG_EXPR(NETWORK_COMP, MedPrio, (next-(2*max_machines))); 53011130Sali.jafri@arm.com DEBUG_EXPR(NETWORK_COMP, MedPrio, src); 53111130Sali.jafri@arm.com DEBUG_EXPR(NETWORK_COMP, MedPrio, next); 53211130Sali.jafri@arm.com DEBUG_EXPR(NETWORK_COMP, MedPrio, result); 53311130Sali.jafri@arm.com DEBUG_NEWLINE(NETWORK_COMP, MedPrio); 53411130Sali.jafri@arm.com 53511130Sali.jafri@arm.com return result; 53611130Sali.jafri@arm.com} 53711130Sali.jafri@arm.com 53811130Sali.jafri@arm.com