Topology.cc revision 6145
18528SN/A 28528SN/A/* 38528SN/A * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 49988Snilay@cs.wisc.edu * All rights reserved. 58835SAli.Saidi@ARM.com * 69988Snilay@cs.wisc.edu * Redistribution and use in source and binary forms, with or without 78528SN/A * modification, are permitted provided that the following conditions are 88528SN/A * met: redistributions of source code must retain the above copyright 98528SN/A * notice, this list of conditions and the following disclaimer; 108528SN/A * redistributions in binary form must reproduce the above copyright 118528SN/A * notice, this list of conditions and the following disclaimer in the 128528SN/A * documentation and/or other materials provided with the distribution; 1310315Snilay@cs.wisc.edu * neither the name of the copyright holders nor the names of its 1410513SAli.Saidi@ARM.com * contributors may be used to endorse or promote products derived from 1511957Sgabeblack@google.com * this software without specific prior written permission. 1610513SAli.Saidi@ARM.com * 179885Sstever@gmail.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 189885Sstever@gmail.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1911570SCurtis.Dunham@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2011957Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 219055Ssaidi@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 229449SAli.Saidi@ARM.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 239988Snilay@cs.wisc.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2411312Santhony.gutierrez@amd.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2510513SAli.Saidi@ARM.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2610513SAli.Saidi@ARM.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2710038SAli.Saidi@ARM.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2811515Sandreas.sandberg@arm.com */ 2910038SAli.Saidi@ARM.com 3010038SAli.Saidi@ARM.com/* 3110038SAli.Saidi@ARM.com * Topology.C 328528SN/A * 3311957Sgabeblack@google.com * Description: See Topology.h 3410315Snilay@cs.wisc.edu * 358528SN/A * $Id$ 3610513SAli.Saidi@ARM.com * 3710513SAli.Saidi@ARM.com * */ 388528SN/A 3911680SCurtis.Dunham@arm.com#include "Topology.hh" 4010636Snilay@cs.wisc.edu#include "NetDest.hh" 4110736Snilay@cs.wisc.edu#include "Network.hh" 429079SAli.Saidi@ARM.com#include "TopologyType.hh" 4311219Snilay@cs.wisc.edu#include "RubyConfig.hh" 448721SN/A#include "util.hh" 4511570SCurtis.Dunham@arm.com#include "MachineType.hh" 4611570SCurtis.Dunham@arm.com#include "Protocol.hh" 4711570SCurtis.Dunham@arm.com#include <string> 489885Sstever@gmail.com 499885Sstever@gmail.comstatic const int INFINITE_LATENCY = 10000; // Yes, this is a big hack 5010038SAli.Saidi@ARM.comstatic const int DEFAULT_BW_MULTIPLIER = 1; // Just to be consistent with above :) 5111570SCurtis.Dunham@arm.com 5211957Sgabeblack@google.com// Note: In this file, we use the first 2*m_nodes SwitchIDs to 5310038SAli.Saidi@ARM.com// represent the input and output endpoint links. These really are 548528SN/A// not 'switches', as they will not have a Switch object allocated for 5511440SCurtis.Dunham@arm.com// them. The first m_nodes SwitchIDs are the links into the network, 5611440SCurtis.Dunham@arm.com// the second m_nodes set of SwitchIDs represent the the output queues 578528SN/A// of the network. 588528SN/A 598528SN/A// Helper functions based on chapter 29 of Cormen et al. 608528SN/Astatic Matrix extend_shortest_path(const Matrix& current_dist, Matrix& latencies, Matrix& inter_switches); 618528SN/Astatic Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches); 628528SN/Astatic bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, const Matrix& weights, const Matrix& dist); 638528SN/Astatic NetDest shortest_path_to_node(SwitchID src, SwitchID next, const Matrix& weights, const Matrix& dist); 6410513SAli.Saidi@ARM.com 658528SN/A 668528SN/ATopology::Topology(Network* network_ptr, int number_of_nodes) 678528SN/A{ 689885Sstever@gmail.com m_network_ptr = network_ptr; 6911570SCurtis.Dunham@arm.com m_nodes = number_of_nodes; 708528SN/A m_number_of_switches = 0; 719988Snilay@cs.wisc.edu init(); 7211570SCurtis.Dunham@arm.com} 7311570SCurtis.Dunham@arm.com 7411570SCurtis.Dunham@arm.comvoid Topology::init() 7511570SCurtis.Dunham@arm.com{ 7611680SCurtis.Dunham@arm.com if (m_nodes == 1) { 778721SN/A SwitchID id = newSwitchID(); 788721SN/A addLink(0, id, NETWORK_LINK_LATENCY); 798891SAli.Saidi@ARM.com addLink(id, 1, NETWORK_LINK_LATENCY); 808891SAli.Saidi@ARM.com return; 818528SN/A } 828528SN/A 838528SN/A // topology-specific set-up 848528SN/A TopologyType topology = string_to_TopologyType(g_NETWORK_TOPOLOGY); 858528SN/A switch (topology) { 868528SN/A case TopologyType_TORUS_2D: 879988Snilay@cs.wisc.edu make2DTorus(); 888528SN/A break; 898528SN/A case TopologyType_HIERARCHICAL_SWITCH: 908528SN/A makeHierarchicalSwitch(FAN_OUT_DEGREE); 918528SN/A break; 928528SN/A case TopologyType_CROSSBAR: 938528SN/A makeHierarchicalSwitch(1024); 949988Snilay@cs.wisc.edu break; 958528SN/A case TopologyType_PT_TO_PT: 968528SN/A makePtToPt(); 978528SN/A break; 988528SN/A case TopologyType_FILE_SPECIFIED: 998528SN/A makeFileSpecified(); 1008528SN/A break; 1019988Snilay@cs.wisc.edu default: 10211957Sgabeblack@google.com ERROR_MSG("Unexpected typology type") 1038528SN/A } 1048528SN/A 1059885Sstever@gmail.com // initialize component latencies record 1069885Sstever@gmail.com m_component_latencies.setSize(0); 1079885Sstever@gmail.com m_component_inter_switches.setSize(0); 10810315Snilay@cs.wisc.edu} 1099988Snilay@cs.wisc.edu 11010315Snilay@cs.wisc.eduvoid Topology::makeSwitchesPerChip(Vector< Vector < SwitchID > > &nodePairs, Vector<int> &latencies, Vector<int> &bw_multis, int numberOfChipSwitches) 1119885Sstever@gmail.com{ 1129885Sstever@gmail.com 1138528SN/A Vector < SwitchID > nodes; // temporary buffer 1148528SN/A nodes.setSize(2); 11510451Snilay@cs.wisc.edu 11610315Snilay@cs.wisc.edu Vector<bool> endpointConnectionExist; // used to ensure all endpoints are connected to the network 1178528SN/A endpointConnectionExist.setSize(m_nodes); 1189885Sstever@gmail.com // initialize endpoint check vector 1198528SN/A for (int k = 0; k < endpointConnectionExist.size(); k++) { 12011570SCurtis.Dunham@arm.com endpointConnectionExist[k] = false; 1218528SN/A } 1228528SN/A 1238528SN/A Vector<int> componentCount; 12410038SAli.Saidi@ARM.com componentCount.setSize(MachineType_NUM); 1258528SN/A for (MachineType mType = MachineType_FIRST; mType < MachineType_NUM; ++mType) { 1269988Snilay@cs.wisc.edu componentCount[mType] = 0; 1278528SN/A } 1288528SN/A 1298528SN/A // components to/from network links 1309449SAli.Saidi@ARM.com for (int chip = 0; chip < RubyConfig::numberOfChips(); chip++) { 13110038SAli.Saidi@ARM.com for (MachineType mType = MachineType_FIRST; mType < MachineType_NUM; ++mType) { 1328528SN/A for (int component = 0; component < MachineType_chip_count(mType, chip); component++) { 1338528SN/A 1348528SN/A int latency = -1; 1358528SN/A int bw_multiplier = -1; // internal link bw multiplier of the global bandwidth 1368528SN/A if (mType != MachineType_Directory) { 1378528SN/A latency = ON_CHIP_LINK_LATENCY; // internal link latency 13811570SCurtis.Dunham@arm.com bw_multiplier = 10; // internal link bw multiplier of the global bandwidth 13911570SCurtis.Dunham@arm.com } else { 14011570SCurtis.Dunham@arm.com latency = NETWORK_LINK_LATENCY; // local memory latency 14111570SCurtis.Dunham@arm.com bw_multiplier = 1; // local memory link bw multiplier of the global bandwidth 1428528SN/A } 1438528SN/A nodes[0] = MachineType_base_number(mType)+componentCount[mType]; 1449885Sstever@gmail.com nodes[1] = chip+m_nodes*2; // this is the chip's internal switch id # 14510315Snilay@cs.wisc.edu 1469449SAli.Saidi@ARM.com // insert link 14711957Sgabeblack@google.com nodePairs.insertAtBottom(nodes); 1488528SN/A latencies.insertAtBottom(latency); 1498528SN/A //bw_multis.insertAtBottom(bw_multiplier); 1508835SAli.Saidi@ARM.com bw_multis.insertAtBottom(componentCount[mType]+MachineType_base_number((MachineType)mType)); 1518528SN/A 1528528SN/A // opposite direction link 1538528SN/A Vector < SwitchID > otherDirectionNodes; 1548528SN/A otherDirectionNodes.setSize(2); 15511103Snilay@cs.wisc.edu otherDirectionNodes[0] = nodes[1]; 1569885Sstever@gmail.com otherDirectionNodes[1] = nodes[0]+m_nodes; 15711680SCurtis.Dunham@arm.com nodePairs.insertAtBottom(otherDirectionNodes); 15810451Snilay@cs.wisc.edu latencies.insertAtBottom(latency); 1599885Sstever@gmail.com bw_multis.insertAtBottom(bw_multiplier); 16011219Snilay@cs.wisc.edu 16111731Sjason@lowepower.com assert(!endpointConnectionExist[nodes[0]]); 16211570SCurtis.Dunham@arm.com endpointConnectionExist[nodes[0]] = true; 16310636Snilay@cs.wisc.edu componentCount[mType]++; 1649988Snilay@cs.wisc.edu } 16511014Sandreas.sandberg@arm.com } 1668528SN/A } 16710451Snilay@cs.wisc.edu 16811570SCurtis.Dunham@arm.com // make sure all enpoints are connected in the soon to be created network 16911570SCurtis.Dunham@arm.com for (int k = 0; k < endpointConnectionExist.size(); k++) { 17011570SCurtis.Dunham@arm.com if (endpointConnectionExist[k] == false) { 17111570SCurtis.Dunham@arm.com cerr << "Error: Unconnected Endpoint: " << k << endl; 1728528SN/A exit(1); 1738835SAli.Saidi@ARM.com } 1749449SAli.Saidi@ARM.com } 17510036SAli.Saidi@ARM.com 1768528SN/A // secondary check to ensure we saw the correct machine counts 1778835SAli.Saidi@ARM.com for (MachineType mType = MachineType_FIRST; mType < MachineType_NUM; ++mType) { 17811731Sjason@lowepower.com assert(componentCount[mType] == MachineType_base_count((MachineType)mType)); 1799885Sstever@gmail.com } 18010451Snilay@cs.wisc.edu 18110451Snilay@cs.wisc.edu} 18211219Snilay@cs.wisc.edu 1838528SN/A// 2D torus topology 18410451Snilay@cs.wisc.edu 1858528SN/Avoid Topology::make2DTorus() 1869885Sstever@gmail.com{ 1879885Sstever@gmail.com Vector< Vector < SwitchID > > nodePairs; // node pairs extracted from the file 18810451Snilay@cs.wisc.edu Vector<int> latencies; // link latencies for each link extracted 1899885Sstever@gmail.com Vector<int> bw_multis; // bw multipliers for each link extracted 1909885Sstever@gmail.com 19111731Sjason@lowepower.com Vector < SwitchID > nodes; // temporary buffer 19211570SCurtis.Dunham@arm.com nodes.setSize(2); 1939988Snilay@cs.wisc.edu 19411570SCurtis.Dunham@arm.com // number of inter-chip switches 19511570SCurtis.Dunham@arm.com int numberOfTorusSwitches = m_nodes/MachineType_base_level(MachineType_NUM); 19611570SCurtis.Dunham@arm.com // one switch per machine node grouping 19711570SCurtis.Dunham@arm.com Vector<SwitchID> torusSwitches; 19810036SAli.Saidi@ARM.com for(int i=0; i<numberOfTorusSwitches; i++){ 1999885Sstever@gmail.com SwitchID new_switch = newSwitchID(); 20011731Sjason@lowepower.com torusSwitches.insertAtBottom(new_switch); 2019885Sstever@gmail.com } 20210038SAli.Saidi@ARM.com 20310038SAli.Saidi@ARM.com makeSwitchesPerChip(nodePairs, latencies, bw_multis, numberOfTorusSwitches); 20410038SAli.Saidi@ARM.com 20510038SAli.Saidi@ARM.com int lengthOfSide = (int)sqrt((double)numberOfTorusSwitches); 20610038SAli.Saidi@ARM.com 20710736Snilay@cs.wisc.edu // Now connect the inter-chip torus links 20810038SAli.Saidi@ARM.com 20910038SAli.Saidi@ARM.com int latency = NETWORK_LINK_LATENCY; // external link latency 21010038SAli.Saidi@ARM.com int bw_multiplier = 1; // external link bw multiplier of the global bandwidth 21110038SAli.Saidi@ARM.com 21210038SAli.Saidi@ARM.com for(int i=0; i<numberOfTorusSwitches; i++){ 21310038SAli.Saidi@ARM.com nodes[0] = torusSwitches[i]; // current switch 21410038SAli.Saidi@ARM.com 21510038SAli.Saidi@ARM.com // left 21610038SAli.Saidi@ARM.com if(nodes[0]%lengthOfSide == 0){ // determine left neighbor 21710038SAli.Saidi@ARM.com nodes[1] = nodes[0] - 1 + lengthOfSide; 21810038SAli.Saidi@ARM.com } else { 21910038SAli.Saidi@ARM.com nodes[1] = nodes[0] - 1; 22010038SAli.Saidi@ARM.com } 22111570SCurtis.Dunham@arm.com nodePairs.insertAtBottom(nodes); 22210038SAli.Saidi@ARM.com latencies.insertAtBottom(latency); 22310038SAli.Saidi@ARM.com bw_multis.insertAtBottom(bw_multiplier); 22410038SAli.Saidi@ARM.com 22511570SCurtis.Dunham@arm.com // right 22611570SCurtis.Dunham@arm.com if((nodes[0] + 1)%lengthOfSide == 0){ // determine right neighbor 22711570SCurtis.Dunham@arm.com nodes[1] = nodes[0] + 1 - lengthOfSide; 22811570SCurtis.Dunham@arm.com } else { 22910038SAli.Saidi@ARM.com nodes[1] = nodes[0] + 1; 23010038SAli.Saidi@ARM.com } 2318528SN/A nodePairs.insertAtBottom(nodes); 2328528SN/A latencies.insertAtBottom(latency); 2338528SN/A bw_multis.insertAtBottom(bw_multiplier); 2349988Snilay@cs.wisc.edu 23510038SAli.Saidi@ARM.com // top 2368528SN/A if(nodes[0] - lengthOfSide < 2*m_nodes){ // determine if node is on the top 2378528SN/A nodes[1] = nodes[0] - lengthOfSide + (lengthOfSide*lengthOfSide); 2388528SN/A } else { 2398528SN/A nodes[1] = nodes[0] - lengthOfSide; 2408528SN/A } 2419885Sstever@gmail.com nodePairs.insertAtBottom(nodes); 24211570SCurtis.Dunham@arm.com latencies.insertAtBottom(latency); 2439988Snilay@cs.wisc.edu bw_multis.insertAtBottom(bw_multiplier); 24410038SAli.Saidi@ARM.com 2459265SAli.Saidi@ARM.com // bottom 24611570SCurtis.Dunham@arm.com if(nodes[0] + lengthOfSide >= 2*m_nodes+numberOfTorusSwitches){ // determine if node is on the bottom 24711570SCurtis.Dunham@arm.com // sorin: bad bug if this is a > instead of a >= 24811570SCurtis.Dunham@arm.com nodes[1] = nodes[0] + lengthOfSide - (lengthOfSide*lengthOfSide); 24911570SCurtis.Dunham@arm.com } else { 2508528SN/A nodes[1] = nodes[0] + lengthOfSide; 25110451Snilay@cs.wisc.edu } 2528528SN/A nodePairs.insertAtBottom(nodes); 2538528SN/A latencies.insertAtBottom(latency); 25411103Snilay@cs.wisc.edu bw_multis.insertAtBottom(bw_multiplier); 2559885Sstever@gmail.com 25611680SCurtis.Dunham@arm.com } 25710451Snilay@cs.wisc.edu 2589885Sstever@gmail.com // add links 25911219Snilay@cs.wisc.edu ASSERT(nodePairs.size() == latencies.size() && latencies.size() == bw_multis.size()) 26011731Sjason@lowepower.com for (int k = 0; k < nodePairs.size(); k++) { 26111570SCurtis.Dunham@arm.com ASSERT(nodePairs[k].size() == 2); 26210636Snilay@cs.wisc.edu addLink(nodePairs[k][0], nodePairs[k][1], latencies[k], bw_multis[k]); 2639988Snilay@cs.wisc.edu } 26411014Sandreas.sandberg@arm.com 2658528SN/A} 26610451Snilay@cs.wisc.edu 26711570SCurtis.Dunham@arm.com// hierarchical switch topology 26811570SCurtis.Dunham@arm.comvoid Topology::makeHierarchicalSwitch(int fan_out_degree) 26911570SCurtis.Dunham@arm.com{ 27011570SCurtis.Dunham@arm.com // Make a row of switches with only one input. This extra row makes 2718528SN/A // sure the links out of the nodes have latency and limited 2728835SAli.Saidi@ARM.com // bandwidth. 27310451Snilay@cs.wisc.edu 27410036SAli.Saidi@ARM.com // number of inter-chip switches, i.e. the last row of switches 2758528SN/A Vector<SwitchID> last_level; 2768835SAli.Saidi@ARM.com for (int i=0; i<m_nodes; i++) { 27711731Sjason@lowepower.com SwitchID new_switch = newSwitchID(); // internal switch id # 2789885Sstever@gmail.com addLink(i, new_switch, NETWORK_LINK_LATENCY); 27910451Snilay@cs.wisc.edu last_level.insertAtBottom(new_switch); 2808528SN/A } 28111219Snilay@cs.wisc.edu 2828528SN/A // Create Hierarchical Switches 28310451Snilay@cs.wisc.edu 2848528SN/A // start from the bottom level and work up to root 2859885Sstever@gmail.com Vector<SwitchID> next_level; 2869885Sstever@gmail.com while(last_level.size() > 1) { 28710451Snilay@cs.wisc.edu for (int i=0; i<last_level.size(); i++) { 2889885Sstever@gmail.com if ((i % fan_out_degree) == 0) { 2899885Sstever@gmail.com next_level.insertAtBottom(newSwitchID()); 29011731Sjason@lowepower.com } 29111570SCurtis.Dunham@arm.com // Add this link to the last switch we created 2929988Snilay@cs.wisc.edu addLink(last_level[i], next_level[next_level.size()-1], NETWORK_LINK_LATENCY); 29311570SCurtis.Dunham@arm.com } 29411570SCurtis.Dunham@arm.com 29511570SCurtis.Dunham@arm.com // Make the current level the last level to get ready for next 29611570SCurtis.Dunham@arm.com // iteration 29710036SAli.Saidi@ARM.com last_level = next_level; 2989885Sstever@gmail.com next_level.clear(); 29911731Sjason@lowepower.com } 3009885Sstever@gmail.com 3018528SN/A SwitchID root_switch = last_level[0]; 3028528SN/A 3039988Snilay@cs.wisc.edu Vector<SwitchID> out_level; 3048528SN/A for (int i=0; i<m_nodes; i++) { 3059449SAli.Saidi@ARM.com out_level.insertAtBottom(m_nodes+i); 3069449SAli.Saidi@ARM.com } 30711219Snilay@cs.wisc.edu 3089988Snilay@cs.wisc.edu // Build the down network from the endpoints to the root 3099449SAli.Saidi@ARM.com while(out_level.size() != 1) { 31010038SAli.Saidi@ARM.com 31110038SAli.Saidi@ARM.com // A level of switches 31210038SAli.Saidi@ARM.com for (int i=0; i<out_level.size(); i++) { 31310038SAli.Saidi@ARM.com if ((i % fan_out_degree) == 0) { 31410038SAli.Saidi@ARM.com if (out_level.size() > fan_out_degree) { 31510038SAli.Saidi@ARM.com next_level.insertAtBottom(newSwitchID()); 31610038SAli.Saidi@ARM.com } else { 31710038SAli.Saidi@ARM.com next_level.insertAtBottom(root_switch); 3189449SAli.Saidi@ARM.com } 3199449SAli.Saidi@ARM.com } 3209449SAli.Saidi@ARM.com // Add this link to the last switch we created 3219449SAli.Saidi@ARM.com addLink(next_level[next_level.size()-1], out_level[i], NETWORK_LINK_LATENCY); 3229449SAli.Saidi@ARM.com } 3239449SAli.Saidi@ARM.com 32410038SAli.Saidi@ARM.com // Make the current level the last level to get ready for next 3259449SAli.Saidi@ARM.com // iteration 3269449SAli.Saidi@ARM.com out_level = next_level; 32710038SAli.Saidi@ARM.com next_level.clear(); 32810038SAli.Saidi@ARM.com } 32910513SAli.Saidi@ARM.com} 33010038SAli.Saidi@ARM.com 33110038SAli.Saidi@ARM.com// one internal node per chip, point to point links between chips 33210038SAli.Saidi@ARM.comvoid Topology::makePtToPt() 33310038SAli.Saidi@ARM.com{ 33410038SAli.Saidi@ARM.com Vector< Vector < SwitchID > > nodePairs; // node pairs extracted from the file 33510038SAli.Saidi@ARM.com Vector<int> latencies; // link latencies for each link extracted 33610038SAli.Saidi@ARM.com Vector<int> bw_multis; // bw multipliers for each link extracted 33710736Snilay@cs.wisc.edu 33810038SAli.Saidi@ARM.com Vector < SwitchID > nodes; 33910038SAli.Saidi@ARM.com nodes.setSize(2); 34010038SAli.Saidi@ARM.com 34110038SAli.Saidi@ARM.com // number of inter-chip switches 34210038SAli.Saidi@ARM.com int numberOfChipSwitches = m_nodes/MachineType_base_level(MachineType_NUM); 34310038SAli.Saidi@ARM.com // two switches per machine node grouping 34410038SAli.Saidi@ARM.com // one intra-chip switch and one inter-chip switch per chip 34510038SAli.Saidi@ARM.com for(int i=0; i<numberOfChipSwitches; i++){ 34610038SAli.Saidi@ARM.com SwitchID new_switch = newSwitchID(); 34710038SAli.Saidi@ARM.com new_switch = newSwitchID(); 34810038SAli.Saidi@ARM.com } 34910038SAli.Saidi@ARM.com 35010038SAli.Saidi@ARM.com makeSwitchesPerChip(nodePairs, latencies, bw_multis, numberOfChipSwitches); 35111570SCurtis.Dunham@arm.com 35210038SAli.Saidi@ARM.com // connect intra-chip switch to inter-chip switch 35310038SAli.Saidi@ARM.com for (int chip = 0; chip < RubyConfig::numberOfChips(); chip++) { 35410038SAli.Saidi@ARM.com 35511570SCurtis.Dunham@arm.com int latency = ON_CHIP_LINK_LATENCY; // internal link latency 35611570SCurtis.Dunham@arm.com int bw_multiplier = 10; // external link bw multiplier of the global bandwidth 35711570SCurtis.Dunham@arm.com 35811570SCurtis.Dunham@arm.com nodes[0] = chip+m_nodes*2; 35910038SAli.Saidi@ARM.com nodes[1] = chip+m_nodes*2+RubyConfig::numberOfChips(); 3609449SAli.Saidi@ARM.com 3618528SN/A // insert link 3628528SN/A nodePairs.insertAtBottom(nodes); 3638528SN/A latencies.insertAtBottom(latency); 3649988Snilay@cs.wisc.edu bw_multis.insertAtBottom(bw_multiplier); 36510038SAli.Saidi@ARM.com 3668528SN/A // opposite direction link 3678528SN/A Vector < SwitchID > otherDirectionNodes; 3688528SN/A otherDirectionNodes.setSize(2); 3698528SN/A otherDirectionNodes[0] = nodes[1]; 3708528SN/A otherDirectionNodes[1] = nodes[0]; 3719885Sstever@gmail.com nodePairs.insertAtBottom(otherDirectionNodes); 37211570SCurtis.Dunham@arm.com latencies.insertAtBottom(latency); 3739988Snilay@cs.wisc.edu bw_multis.insertAtBottom(bw_multiplier); 37410038SAli.Saidi@ARM.com } 3759265SAli.Saidi@ARM.com 37611570SCurtis.Dunham@arm.com // point-to-point network between chips 37711570SCurtis.Dunham@arm.com for (int chip = 0; chip < RubyConfig::numberOfChips(); chip++) { 37811570SCurtis.Dunham@arm.com for (int other_chip = chip+1; other_chip < RubyConfig::numberOfChips(); other_chip++) { 37911570SCurtis.Dunham@arm.com 3808528SN/A int latency = NETWORK_LINK_LATENCY; // external link latency 38110451Snilay@cs.wisc.edu int bw_multiplier = 1; // external link bw multiplier of the global bandwidth 38210451Snilay@cs.wisc.edu 38310451Snilay@cs.wisc.edu nodes[0] = chip+m_nodes*2+RubyConfig::numberOfChips(); 38411103Snilay@cs.wisc.edu nodes[1] = other_chip+m_nodes*2+RubyConfig::numberOfChips(); 38510451Snilay@cs.wisc.edu 38611680SCurtis.Dunham@arm.com // insert link 38710451Snilay@cs.wisc.edu nodePairs.insertAtBottom(nodes); 38810451Snilay@cs.wisc.edu latencies.insertAtBottom(latency); 38911219Snilay@cs.wisc.edu bw_multis.insertAtBottom(bw_multiplier); 39011731Sjason@lowepower.com 39111570SCurtis.Dunham@arm.com // opposite direction link 39210636Snilay@cs.wisc.edu Vector < SwitchID > otherDirectionNodes; 39310451Snilay@cs.wisc.edu otherDirectionNodes.setSize(2); 39411014Sandreas.sandberg@arm.com otherDirectionNodes[0] = nodes[1]; 39510451Snilay@cs.wisc.edu otherDirectionNodes[1] = nodes[0]; 39610451Snilay@cs.wisc.edu nodePairs.insertAtBottom(otherDirectionNodes); 39711570SCurtis.Dunham@arm.com latencies.insertAtBottom(latency); 39811570SCurtis.Dunham@arm.com bw_multis.insertAtBottom(bw_multiplier); 39911570SCurtis.Dunham@arm.com } 40011570SCurtis.Dunham@arm.com } 40110451Snilay@cs.wisc.edu 40210451Snilay@cs.wisc.edu // add links 40310451Snilay@cs.wisc.edu ASSERT(nodePairs.size() == latencies.size() && latencies.size() == bw_multis.size()) 40410451Snilay@cs.wisc.edu for (int k = 0; k < nodePairs.size(); k++) { 40510451Snilay@cs.wisc.edu ASSERT(nodePairs[k].size() == 2); 40610451Snilay@cs.wisc.edu addLink(nodePairs[k][0], nodePairs[k][1], latencies[k], bw_multis[k]); 40711731Sjason@lowepower.com } 40810451Snilay@cs.wisc.edu} 40910451Snilay@cs.wisc.edu 41010451Snilay@cs.wisc.edu// make a network as described by the networkFile 41111219Snilay@cs.wisc.eduvoid Topology::makeFileSpecified() 41210451Snilay@cs.wisc.edu{ 41310451Snilay@cs.wisc.edu 41410451Snilay@cs.wisc.edu Vector< Vector < SwitchID > > nodePairs; // node pairs extracted from the file 41510451Snilay@cs.wisc.edu Vector<int> latencies; // link latencies for each link extracted 41610451Snilay@cs.wisc.edu Vector<int> bw_multis; // bw multipliers for each link extracted 41710636Snilay@cs.wisc.edu Vector<int> weights; // link weights used to enfore e-cube deadlock free routing 41810451Snilay@cs.wisc.edu Vector< SwitchID > int_network_switches; // internal switches extracted from the file 41911570SCurtis.Dunham@arm.com Vector<bool> endpointConnectionExist; // used to ensure all endpoints are connected to the network 42010451Snilay@cs.wisc.edu 42110451Snilay@cs.wisc.edu endpointConnectionExist.setSize(m_nodes); 42210451Snilay@cs.wisc.edu 42310636Snilay@cs.wisc.edu // initialize endpoint check vector 42410636Snilay@cs.wisc.edu for (int k = 0; k < endpointConnectionExist.size(); k++) { 42510636Snilay@cs.wisc.edu endpointConnectionExist[k] = false; 42610636Snilay@cs.wisc.edu } 42710636Snilay@cs.wisc.edu 42810636Snilay@cs.wisc.edu string filename = "network/simple/Network_Files/"; 42910636Snilay@cs.wisc.edu filename = filename+g_CACHE_DESIGN 43011570SCurtis.Dunham@arm.com +"_Procs-"+int_to_string(RubyConfig::numberOfProcessors()) 43111570SCurtis.Dunham@arm.com +"_ProcsPerChip-"+int_to_string(RubyConfig::numberOfProcsPerChip()) 43211570SCurtis.Dunham@arm.com +"_L2Banks-"+int_to_string(RubyConfig::numberOfL2Cache()) 43311570SCurtis.Dunham@arm.com +"_Memories-"+int_to_string(RubyConfig::numberOfMemories()) 43410636Snilay@cs.wisc.edu +".txt"; 43510636Snilay@cs.wisc.edu 43610636Snilay@cs.wisc.edu if (g_SIMICS) { 43710636Snilay@cs.wisc.edu filename = "../../../ruby/"+filename; 43810451Snilay@cs.wisc.edu } 43910636Snilay@cs.wisc.edu ifstream networkFile( filename.c_str() , ios::in); 44010636Snilay@cs.wisc.edu if (!networkFile.is_open()) { 44110636Snilay@cs.wisc.edu cerr << "Error: Could not open network file: " << filename << endl; 44210636Snilay@cs.wisc.edu cerr << "Probably no network file exists for " << RubyConfig::numberOfProcessors() 44310451Snilay@cs.wisc.edu << " processors and " << RubyConfig::numberOfProcsPerChip() << " procs per chip " << endl; 44410451Snilay@cs.wisc.edu exit(1); 44510451Snilay@cs.wisc.edu } 44610451Snilay@cs.wisc.edu 44710451Snilay@cs.wisc.edu string line = ""; 44810451Snilay@cs.wisc.edu 44910451Snilay@cs.wisc.edu while (!networkFile.eof()) { 45011731Sjason@lowepower.com 45111570SCurtis.Dunham@arm.com Vector < SwitchID > nodes; 45210451Snilay@cs.wisc.edu nodes.setSize(2); 45311570SCurtis.Dunham@arm.com int latency = -1; // null latency 45411570SCurtis.Dunham@arm.com int weight = -1; // null weight 45511570SCurtis.Dunham@arm.com int bw_multiplier = DEFAULT_BW_MULTIPLIER; // default multiplier incase the network file doesn't define it 45611570SCurtis.Dunham@arm.com int i = 0; // node pair index 45710451Snilay@cs.wisc.edu int varsFound = 0; // number of varsFound on the line 45810451Snilay@cs.wisc.edu int internalNodes = 0; // used to determine if the link is between 2 internal nodes 45911731Sjason@lowepower.com std::getline(networkFile, line, '\n'); 46010451Snilay@cs.wisc.edu string varStr = string_split(line, ' '); 46110451Snilay@cs.wisc.edu 46210451Snilay@cs.wisc.edu // parse the current line in the file 46311219Snilay@cs.wisc.edu while (varStr != "") { 46410451Snilay@cs.wisc.edu string label = string_split(varStr, ':'); 46511570SCurtis.Dunham@arm.com 46610451Snilay@cs.wisc.edu // valid node labels 46710736Snilay@cs.wisc.edu if (label == "ext_node" || label == "int_node") { 46810736Snilay@cs.wisc.edu ASSERT(i < 2); // one link between 2 switches per line 46911570SCurtis.Dunham@arm.com varsFound++; 47011570SCurtis.Dunham@arm.com bool isNewIntSwitch = true; 47111570SCurtis.Dunham@arm.com if (label == "ext_node") { // input link to node 47211440SCurtis.Dunham@arm.com MachineType machine = string_to_MachineType(string_split(varStr, ':')); 47311570SCurtis.Dunham@arm.com string nodeStr = string_split(varStr, ':'); 47410736Snilay@cs.wisc.edu if (string_split(varStr, ':') == "bank") { 47511219Snilay@cs.wisc.edu nodes[i] = MachineType_base_number(machine) 47610736Snilay@cs.wisc.edu + atoi(nodeStr.c_str()) 47710451Snilay@cs.wisc.edu + atoi((string_split(varStr, ':')).c_str())*RubyConfig::numberOfChips(); 47810451Snilay@cs.wisc.edu } else { 47910451Snilay@cs.wisc.edu nodes[i] = MachineType_base_number(machine) 48010451Snilay@cs.wisc.edu + atoi(nodeStr.c_str()); 48110736Snilay@cs.wisc.edu } 4828528SN/A // in nodes should be numbered 0 to m_nodes-1 48311219Snilay@cs.wisc.edu ASSERT(nodes[i] >= 0 && nodes[i] < m_nodes); 48411219Snilay@cs.wisc.edu isNewIntSwitch = false; 48511219Snilay@cs.wisc.edu endpointConnectionExist[nodes[i]] = true; 48611219Snilay@cs.wisc.edu } 48711219Snilay@cs.wisc.edu if (label == "int_node") { // interior node 48811219Snilay@cs.wisc.edu nodes[i] = atoi((string_split(varStr, ':')).c_str())+m_nodes*2; 48911219Snilay@cs.wisc.edu // in nodes should be numbered >= m_nodes*2 4908528SN/A ASSERT(nodes[i] >= m_nodes*2); 4918528SN/A for (int k = 0; k < int_network_switches.size(); k++) { 4929988Snilay@cs.wisc.edu if (int_network_switches[k] == nodes[i]) { 4938528SN/A isNewIntSwitch = false; 4948528SN/A } 4958528SN/A } 49610451Snilay@cs.wisc.edu if (isNewIntSwitch) { // if internal switch 49710315Snilay@cs.wisc.edu m_number_of_switches++; 4988528SN/A int_network_switches.insertAtBottom(nodes[i]); 4999885Sstever@gmail.com } 5008528SN/A internalNodes++; 50111570SCurtis.Dunham@arm.com } 5028528SN/A i++; 5038528SN/A } else if (label == "link_latency") { 5048528SN/A latency = atoi((string_split(varStr, ':')).c_str()); 50510038SAli.Saidi@ARM.com varsFound++; 5068528SN/A } else if (label == "bw_multiplier") { // not necessary, defaults to DEFAULT_BW_MULTIPLIER 5079988Snilay@cs.wisc.edu bw_multiplier = atoi((string_split(varStr, ':')).c_str()); 5088528SN/A } else if (label == "link_weight") { // not necessary, defaults to link_latency 5098528SN/A weight = atoi((string_split(varStr, ':')).c_str()); 5108528SN/A } else if (label == "processors") { 5119449SAli.Saidi@ARM.com ASSERT(atoi((string_split(varStr, ':')).c_str()) == RubyConfig::numberOfProcessors()); 51210038SAli.Saidi@ARM.com } else if (label == "bw_unit") { 5138528SN/A ASSERT(atoi((string_split(varStr, ':')).c_str()) == g_endpoint_bandwidth); 5148528SN/A } else if (label == "procs_per_chip") { 5158528SN/A ASSERT(atoi((string_split(varStr, ':')).c_str()) == RubyConfig::numberOfProcsPerChip()); 5168528SN/A } else if (label == "L2banks") { 5178528SN/A ASSERT(atoi((string_split(varStr, ':')).c_str()) == RubyConfig::numberOfL2Cache()); 5188528SN/A } else if (label == "memories") { 51911570SCurtis.Dunham@arm.com ASSERT(atoi((string_split(varStr, ':')).c_str()) == RubyConfig::numberOfMemories()); 52011570SCurtis.Dunham@arm.com } else { 52111570SCurtis.Dunham@arm.com cerr << "Error: Unexpected Identifier: " << label << endl; 52211570SCurtis.Dunham@arm.com exit(1); 5238528SN/A } 5248528SN/A varStr = string_split(line, ' '); 5259885Sstever@gmail.com } 52610315Snilay@cs.wisc.edu if (varsFound == 3) { // all three necessary link variables where found so add the link 5279449SAli.Saidi@ARM.com nodePairs.insertAtBottom(nodes); 52811957Sgabeblack@google.com latencies.insertAtBottom(latency); 5298528SN/A if (weight != -1) { 5308528SN/A weights.insertAtBottom(weight); 5318835SAli.Saidi@ARM.com } else { 5328528SN/A weights.insertAtBottom(latency); 5338528SN/A } 5348528SN/A bw_multis.insertAtBottom(bw_multiplier); 5358528SN/A Vector < SwitchID > otherDirectionNodes; 53611103Snilay@cs.wisc.edu otherDirectionNodes.setSize(2); 5379885Sstever@gmail.com otherDirectionNodes[0] = nodes[1]; 53811680SCurtis.Dunham@arm.com if (internalNodes == 2) { // this is an internal link 53910451Snilay@cs.wisc.edu otherDirectionNodes[1] = nodes[0]; 5409885Sstever@gmail.com } else { 54111219Snilay@cs.wisc.edu otherDirectionNodes[1] = nodes[0]+m_nodes; 54211731Sjason@lowepower.com } 54311570SCurtis.Dunham@arm.com nodePairs.insertAtBottom(otherDirectionNodes); 54410636Snilay@cs.wisc.edu latencies.insertAtBottom(latency); 5459988Snilay@cs.wisc.edu if (weight != -1) { 54611014Sandreas.sandberg@arm.com weights.insertAtBottom(weight); 5478528SN/A } else { 54810451Snilay@cs.wisc.edu weights.insertAtBottom(latency); 54911570SCurtis.Dunham@arm.com } 55011570SCurtis.Dunham@arm.com bw_multis.insertAtBottom(bw_multiplier); 55111570SCurtis.Dunham@arm.com } else { 55211570SCurtis.Dunham@arm.com if (varsFound != 0) { // if this is not a valid link, then no vars should have been found 5538528SN/A cerr << "Error in line: " << line << endl; 5548835SAli.Saidi@ARM.com exit(1); 5559449SAli.Saidi@ARM.com } 55610036SAli.Saidi@ARM.com } 5578528SN/A } // end of file 5588835SAli.Saidi@ARM.com 55911731Sjason@lowepower.com // makes sure all enpoints are connected in the soon to be created network 5609885Sstever@gmail.com for (int k = 0; k < endpointConnectionExist.size(); k++) { 56110451Snilay@cs.wisc.edu if (endpointConnectionExist[k] == false) { 56210451Snilay@cs.wisc.edu cerr << "Error: Unconnected Endpoint: " << k << endl; 56311219Snilay@cs.wisc.edu exit(1); 5648528SN/A } 56510451Snilay@cs.wisc.edu } 5668528SN/A 5679885Sstever@gmail.com ASSERT(nodePairs.size() == latencies.size() && latencies.size() == bw_multis.size() && latencies.size() == weights.size()) 5689885Sstever@gmail.com for (int k = 0; k < nodePairs.size(); k++) { 56910451Snilay@cs.wisc.edu ASSERT(nodePairs[k].size() == 2); 5709885Sstever@gmail.com addLink(nodePairs[k][0], nodePairs[k][1], latencies[k], bw_multis[k], weights[k]); 5719885Sstever@gmail.com } 57211731Sjason@lowepower.com 57311570SCurtis.Dunham@arm.com networkFile.close(); 5749988Snilay@cs.wisc.edu} 57511570SCurtis.Dunham@arm.com 57611570SCurtis.Dunham@arm.comvoid Topology::createLinks(bool isReconfiguration) 57711570SCurtis.Dunham@arm.com{ 57811570SCurtis.Dunham@arm.com // Find maximum switchID 57910036SAli.Saidi@ARM.com 5809885Sstever@gmail.com SwitchID max_switch_id = 0; 58111731Sjason@lowepower.com for (int i=0; i<m_links_src_vector.size(); i++) { 5829885Sstever@gmail.com max_switch_id = max(max_switch_id, m_links_src_vector[i]); 58310038SAli.Saidi@ARM.com max_switch_id = max(max_switch_id, m_links_dest_vector[i]); 58410038SAli.Saidi@ARM.com } 58510038SAli.Saidi@ARM.com 58610038SAli.Saidi@ARM.com // Initialize weight vector 58710038SAli.Saidi@ARM.com Matrix topology_weights; 58810736Snilay@cs.wisc.edu Matrix topology_latency; 58910038SAli.Saidi@ARM.com Matrix topology_bw_multis; 59010038SAli.Saidi@ARM.com int num_switches = max_switch_id+1; 59110038SAli.Saidi@ARM.com topology_weights.setSize(num_switches); 59210038SAli.Saidi@ARM.com topology_latency.setSize(num_switches); 59310038SAli.Saidi@ARM.com topology_bw_multis.setSize(num_switches); 59410038SAli.Saidi@ARM.com m_component_latencies.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 59510038SAli.Saidi@ARM.com m_component_inter_switches.setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 59610038SAli.Saidi@ARM.com for(int i=0; i<topology_weights.size(); i++) { 59710038SAli.Saidi@ARM.com topology_weights[i].setSize(num_switches); 59810038SAli.Saidi@ARM.com topology_latency[i].setSize(num_switches); 59910038SAli.Saidi@ARM.com topology_bw_multis[i].setSize(num_switches); 60010038SAli.Saidi@ARM.com m_component_latencies[i].setSize(num_switches); 60110038SAli.Saidi@ARM.com m_component_inter_switches[i].setSize(num_switches); // FIXME setting the size of a member variable here is a HACK! 60211570SCurtis.Dunham@arm.com for(int j=0; j<topology_weights[i].size(); j++) { 60310038SAli.Saidi@ARM.com topology_weights[i][j] = INFINITE_LATENCY; 60410038SAli.Saidi@ARM.com topology_latency[i][j] = -1; // initialize to an invalid value 60510038SAli.Saidi@ARM.com topology_bw_multis[i][j] = -1; // initialize to an invalid value 60611570SCurtis.Dunham@arm.com m_component_latencies[i][j] = -1; // initialize to an invalid value 60711570SCurtis.Dunham@arm.com m_component_inter_switches[i][j] = 0; // initially assume direct connections / no intermediate switches between components 60811570SCurtis.Dunham@arm.com } 60911570SCurtis.Dunham@arm.com } 61010038SAli.Saidi@ARM.com 61110038SAli.Saidi@ARM.com // Set identity weights to zero 6128528SN/A for(int i=0; i<topology_weights.size(); i++) { 6138528SN/A topology_weights[i][i] = 0; 6148528SN/A } 6159988Snilay@cs.wisc.edu 61610038SAli.Saidi@ARM.com // Fill in the topology weights and bandwidth multipliers 6178528SN/A for (int i=0; i<m_links_src_vector.size(); i++) { 6188528SN/A topology_weights[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_weight_vector[i]; 6198528SN/A topology_latency[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; 6208528SN/A m_component_latencies[m_links_src_vector[i]][m_links_dest_vector[i]] = m_links_latency_vector[i]; // initialize to latency vector 6218528SN/A topology_bw_multis[m_links_src_vector[i]][m_links_dest_vector[i]] = m_bw_multiplier_vector[i]; 6229885Sstever@gmail.com } 62311570SCurtis.Dunham@arm.com 6249988Snilay@cs.wisc.edu // Walk topology and hookup the links 62510038SAli.Saidi@ARM.com Matrix dist = shortest_path(topology_weights, m_component_latencies, m_component_inter_switches); 6269265SAli.Saidi@ARM.com for(int i=0; i<topology_weights.size(); i++) { 62711570SCurtis.Dunham@arm.com for(int j=0; j<topology_weights[i].size(); j++) { 62811570SCurtis.Dunham@arm.com int weight = topology_weights[i][j]; 62911570SCurtis.Dunham@arm.com int bw_multiplier = topology_bw_multis[i][j]; 63011570SCurtis.Dunham@arm.com int latency = topology_latency[i][j]; 6318528SN/A if (weight > 0 && weight != INFINITE_LATENCY) { 63210451Snilay@cs.wisc.edu NetDest destination_set = shortest_path_to_node(i, j, topology_weights, dist); 6338528SN/A assert(latency != -1); 6348528SN/A makeLink(i, j, destination_set, latency, weight, bw_multiplier, isReconfiguration); 63511103Snilay@cs.wisc.edu } 6369885Sstever@gmail.com } 63711680SCurtis.Dunham@arm.com } 63810451Snilay@cs.wisc.edu} 6399885Sstever@gmail.com 64011219Snilay@cs.wisc.eduSwitchID Topology::newSwitchID() 64111731Sjason@lowepower.com{ 64211570SCurtis.Dunham@arm.com m_number_of_switches++; 64310636Snilay@cs.wisc.edu return m_number_of_switches-1+m_nodes+m_nodes; 6449988Snilay@cs.wisc.edu} 64511014Sandreas.sandberg@arm.com 6468528SN/Avoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency) 64710451Snilay@cs.wisc.edu{ 64811570SCurtis.Dunham@arm.com addLink(src, dest, link_latency, DEFAULT_BW_MULTIPLIER, link_latency); 64911570SCurtis.Dunham@arm.com} 65011570SCurtis.Dunham@arm.com 65111570SCurtis.Dunham@arm.comvoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier) 6528528SN/A{ 6538835SAli.Saidi@ARM.com addLink(src, dest, link_latency, bw_multiplier, link_latency); 65410451Snilay@cs.wisc.edu} 65510036SAli.Saidi@ARM.com 6568528SN/Avoid Topology::addLink(SwitchID src, SwitchID dest, int link_latency, int bw_multiplier, int link_weight) 6578835SAli.Saidi@ARM.com{ 65811731Sjason@lowepower.com ASSERT(src <= m_number_of_switches+m_nodes+m_nodes); 6599885Sstever@gmail.com ASSERT(dest <= m_number_of_switches+m_nodes+m_nodes); 66010451Snilay@cs.wisc.edu m_links_src_vector.insertAtBottom(src); 6618528SN/A m_links_dest_vector.insertAtBottom(dest); 66211219Snilay@cs.wisc.edu m_links_latency_vector.insertAtBottom(link_latency); 6638528SN/A m_links_weight_vector.insertAtBottom(link_weight); 66410451Snilay@cs.wisc.edu m_bw_multiplier_vector.insertAtBottom(bw_multiplier); 6658528SN/A} 6669885Sstever@gmail.com 6679885Sstever@gmail.comvoid Topology::makeLink(SwitchID src, SwitchID dest, const NetDest& routing_table_entry, int link_latency, int link_weight, int bw_multiplier, bool isReconfiguration) 66810451Snilay@cs.wisc.edu{ 6699885Sstever@gmail.com // Make sure we're not trying to connect two end-point nodes directly together 6709885Sstever@gmail.com assert((src >= 2*m_nodes) || (dest >= 2*m_nodes)); 67111731Sjason@lowepower.com 67211570SCurtis.Dunham@arm.com if (src < m_nodes) { 6739988Snilay@cs.wisc.edu m_network_ptr->makeInLink(src, dest-(2*m_nodes), routing_table_entry, link_latency, bw_multiplier, isReconfiguration); 67411570SCurtis.Dunham@arm.com } else if (dest < 2*m_nodes) { 67511570SCurtis.Dunham@arm.com assert(dest >= m_nodes); 67611570SCurtis.Dunham@arm.com NodeID node = dest-m_nodes; 67711570SCurtis.Dunham@arm.com m_network_ptr->makeOutLink(src-(2*m_nodes), node, routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 67810036SAli.Saidi@ARM.com } else { 6799885Sstever@gmail.com assert((src >= 2*m_nodes) && (dest >= 2*m_nodes)); 68011731Sjason@lowepower.com m_network_ptr->makeInternalLink(src-(2*m_nodes), dest-(2*m_nodes), routing_table_entry, link_latency, link_weight, bw_multiplier, isReconfiguration); 6819885Sstever@gmail.com } 6828528SN/A} 6838528SN/A 6849988Snilay@cs.wisc.eduvoid Topology::printConfig(ostream& out) const 6858528SN/A{ 6869449SAli.Saidi@ARM.com assert(m_component_latencies.size() > 0); 6879449SAli.Saidi@ARM.com 68811219Snilay@cs.wisc.edu out << "--- Begin Topology Print ---" << endl; 6899988Snilay@cs.wisc.edu out << endl; 6909449SAli.Saidi@ARM.com out << "Topology print ONLY indicates the _NETWORK_ latency between two machines" << endl; 69110038SAli.Saidi@ARM.com out << "It does NOT include the latency within the machines" << endl; 69210038SAli.Saidi@ARM.com out << endl; 69310038SAli.Saidi@ARM.com for (int m=0; m<MachineType_NUM; m++) { 69410038SAli.Saidi@ARM.com for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 69510038SAli.Saidi@ARM.com MachineID cur_mach = {(MachineType)m, i}; 69610038SAli.Saidi@ARM.com out << cur_mach << " Network Latencies" << endl; 69710038SAli.Saidi@ARM.com for (int n=0; n<MachineType_NUM; n++) { 69810038SAli.Saidi@ARM.com for (int j=0; j<MachineType_base_count((MachineType)n); j++) { 6999449SAli.Saidi@ARM.com MachineID dest_mach = {(MachineType)n, j}; 7009449SAli.Saidi@ARM.com if (cur_mach != dest_mach) { 7019449SAli.Saidi@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]; 7029449SAli.Saidi@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]; 7039449SAli.Saidi@ARM.com out << " " << cur_mach << " -> " << dest_mach << " net_lat: " 7049449SAli.Saidi@ARM.com << link_latency+intermediate_switches << endl; // NOTE switches are assumed to have single cycle latency 70510038SAli.Saidi@ARM.com } 7069449SAli.Saidi@ARM.com } 7079449SAli.Saidi@ARM.com } 70810038SAli.Saidi@ARM.com out << endl; 70910038SAli.Saidi@ARM.com } 71010513SAli.Saidi@ARM.com } 71110038SAli.Saidi@ARM.com 71210038SAli.Saidi@ARM.com out << "--- End Topology Print ---" << endl; 71310038SAli.Saidi@ARM.com} 71410038SAli.Saidi@ARM.com 71510038SAli.Saidi@ARM.com/**************************************************************************/ 71610038SAli.Saidi@ARM.com 71710038SAli.Saidi@ARM.com// The following all-pairs shortest path algorithm is based on the 71810736Snilay@cs.wisc.edu// discussion from Cormen et al., Chapter 26.1. 71910038SAli.Saidi@ARM.com 72010038SAli.Saidi@ARM.comstatic void extend_shortest_path(Matrix& current_dist, Matrix& latencies, Matrix& inter_switches) 72110038SAli.Saidi@ARM.com{ 72210038SAli.Saidi@ARM.com bool change = true; 72310038SAli.Saidi@ARM.com int nodes = current_dist.size(); 72410038SAli.Saidi@ARM.com 72510038SAli.Saidi@ARM.com while (change) { 72610038SAli.Saidi@ARM.com change = false; 72710038SAli.Saidi@ARM.com for (int i=0; i<nodes; i++) { 72810038SAli.Saidi@ARM.com for (int j=0; j<nodes; j++) { 72910038SAli.Saidi@ARM.com int minimum = current_dist[i][j]; 73010038SAli.Saidi@ARM.com int previous_minimum = minimum; 73110038SAli.Saidi@ARM.com int intermediate_switch = -1; 73211570SCurtis.Dunham@arm.com for (int k=0; k<nodes; k++) { 73310038SAli.Saidi@ARM.com minimum = min(minimum, current_dist[i][k] + current_dist[k][j]); 73410038SAli.Saidi@ARM.com if (previous_minimum != minimum) { 73510038SAli.Saidi@ARM.com intermediate_switch = k; 73611570SCurtis.Dunham@arm.com inter_switches[i][j] = inter_switches[i][k] + inter_switches[k][j] + 1; 73711570SCurtis.Dunham@arm.com } 73811570SCurtis.Dunham@arm.com previous_minimum = minimum; 73911570SCurtis.Dunham@arm.com } 74010038SAli.Saidi@ARM.com if (current_dist[i][j] != minimum) { 7419449SAli.Saidi@ARM.com change = true; 7428528SN/A current_dist[i][j] = minimum; 7438528SN/A assert(intermediate_switch >= 0); 7448528SN/A assert(intermediate_switch < latencies[i].size()); 7459988Snilay@cs.wisc.edu latencies[i][j] = latencies[i][intermediate_switch] + latencies[intermediate_switch][j]; 74610038SAli.Saidi@ARM.com } 7478528SN/A } 7488528SN/A } 7498528SN/A } 7508528SN/A} 7518528SN/A 7529885Sstever@gmail.comstatic Matrix shortest_path(const Matrix& weights, Matrix& latencies, Matrix& inter_switches) 75311570SCurtis.Dunham@arm.com{ 7549988Snilay@cs.wisc.edu Matrix dist = weights; 75510038SAli.Saidi@ARM.com extend_shortest_path(dist, latencies, inter_switches); 7569265SAli.Saidi@ARM.com return dist; 75711570SCurtis.Dunham@arm.com} 75811570SCurtis.Dunham@arm.com 75911570SCurtis.Dunham@arm.comstatic bool link_is_shortest_path_to_node(SwitchID src, SwitchID next, SwitchID final, 76011570SCurtis.Dunham@arm.com const Matrix& weights, const Matrix& dist) 7618528SN/A{ 76210451Snilay@cs.wisc.edu return (weights[src][next] + dist[next][final] == dist[src][final]); 76310451Snilay@cs.wisc.edu} 76410451Snilay@cs.wisc.edu 76511103Snilay@cs.wisc.edustatic NetDest shortest_path_to_node(SwitchID src, SwitchID next, 76610451Snilay@cs.wisc.edu const Matrix& weights, const Matrix& dist) 76711680SCurtis.Dunham@arm.com{ 76810451Snilay@cs.wisc.edu NetDest result; 76910451Snilay@cs.wisc.edu int d = 0; 77011219Snilay@cs.wisc.edu int machines; 77111731Sjason@lowepower.com int max_machines; 77211570SCurtis.Dunham@arm.com 77310636Snilay@cs.wisc.edu machines = MachineType_NUM; 77410451Snilay@cs.wisc.edu max_machines = MachineType_base_number(MachineType_NUM); 77511014Sandreas.sandberg@arm.com 77610451Snilay@cs.wisc.edu for (int m=0; m<machines; m++) { 77710451Snilay@cs.wisc.edu for (int i=0; i<MachineType_base_count((MachineType)m); i++) { 77811570SCurtis.Dunham@arm.com // we use "d+max_machines" below since the "destination" switches for the machines are numbered 77911570SCurtis.Dunham@arm.com // [MachineType_base_number(MachineType_NUM)...2*MachineType_base_number(MachineType_NUM)-1] 78011570SCurtis.Dunham@arm.com // for the component network 78111570SCurtis.Dunham@arm.com if (link_is_shortest_path_to_node(src, next, 78210451Snilay@cs.wisc.edu d+max_machines, 78310451Snilay@cs.wisc.edu weights, dist)) { 78410451Snilay@cs.wisc.edu MachineID mach = {(MachineType)m, i}; 78510451Snilay@cs.wisc.edu result.add(mach); 78610451Snilay@cs.wisc.edu } 78710451Snilay@cs.wisc.edu d++; 78811731Sjason@lowepower.com } 78910451Snilay@cs.wisc.edu } 79010451Snilay@cs.wisc.edu 79110451Snilay@cs.wisc.edu DEBUG_MSG(NETWORK_COMP, MedPrio, "returning shortest path"); 79211219Snilay@cs.wisc.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, (src-(2*max_machines))); 79310451Snilay@cs.wisc.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, (next-(2*max_machines))); 79410451Snilay@cs.wisc.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, src); 79510451Snilay@cs.wisc.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, next); 79610451Snilay@cs.wisc.edu DEBUG_EXPR(NETWORK_COMP, MedPrio, result); 79710451Snilay@cs.wisc.edu DEBUG_NEWLINE(NETWORK_COMP, MedPrio); 79810636Snilay@cs.wisc.edu 79910451Snilay@cs.wisc.edu return result; 80011570SCurtis.Dunham@arm.com} 80110451Snilay@cs.wisc.edu 80210451Snilay@cs.wisc.edu