From 7f49fe9feb174d34efc2a011bad79b38522a360b Mon Sep 17 00:00:00 2001 From: Dongdong Li Date: Thu, 8 Aug 2013 00:15:58 -0800 Subject: Intesim2 Integration Details: See Review 80001 https://gpgpu-sim-code-review.appspot.com/80001/ [git-p4: depot-paths = "//depot/gpgpu_sim_research/fermi/distribution/": change = 16747] --- src/intersim2/networks/dragonfly.cpp | 575 +++++++++++++++++++++++++++++++++++ 1 file changed, 575 insertions(+) create mode 100644 src/intersim2/networks/dragonfly.cpp (limited to 'src/intersim2/networks/dragonfly.cpp') diff --git a/src/intersim2/networks/dragonfly.cpp b/src/intersim2/networks/dragonfly.cpp new file mode 100644 index 0000000..b539cc6 --- /dev/null +++ b/src/intersim2/networks/dragonfly.cpp @@ -0,0 +1,575 @@ +/* + Copyright (c) 2007-2012, Trustees of The Leland Stanford Junior University + All rights reserved. + + Redistribution and use in source and binary forms, with or without modification, + are permitted provided that the following conditions are met: + + Redistributions of source code must retain the above copyright notice, this list + of conditions and the following disclaimer. + Redistributions in binary form must reproduce the above copyright notice, this + list of conditions and the following disclaimer in the documentation and/or + other materials provided with the distribution. + Neither the name of the Stanford University nor the names of its contributors + may be used to endorse or promote products derived from this software without + specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND + ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR + ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON + ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#include "booksim.hpp" +#include +#include + +#include "dragonfly.hpp" +#include "random_utils.hpp" +#include "misc_utils.hpp" +#include "globals.hpp" + +#define DRAGON_LATENCY + +int gP, gA, gG; + +//calculate the hop count between src and estination +int dragonflynew_hopcnt(int src, int dest) +{ + int hopcnt; + int dest_grp_ID, src_grp_ID; + int src_hopcnt, dest_hopcnt; + int src_intm, dest_intm; + int grp_output, dest_grp_output; + int grp_output_RID; + + int _grp_num_routers= gA; + int _grp_num_nodes =_grp_num_routers*gP; + + dest_grp_ID = int(dest/_grp_num_nodes); + src_grp_ID = int(src / _grp_num_nodes); + + //source and dest are in the same group, either 0-1 hop + if (dest_grp_ID == src_grp_ID) { + if ((int)(dest / gP) == (int)(src /gP)) + hopcnt = 0; + else + hopcnt = 1; + + } else { + //source and dest are in the same group + //find the number of hops in the source group + //find the number of hops in the dest group + if (src_grp_ID > dest_grp_ID) { + grp_output = dest_grp_ID; + dest_grp_output = src_grp_ID - 1; + } + else { + grp_output = dest_grp_ID - 1; + dest_grp_output = src_grp_ID; + } + grp_output_RID = ((int) (grp_output / (gP))) + src_grp_ID * _grp_num_routers; + src_intm = grp_output_RID * gP; + + grp_output_RID = ((int) (dest_grp_output / (gP))) + dest_grp_ID * _grp_num_routers; + dest_intm = grp_output_RID * gP; + + //hop count in source group + if ((int)( src_intm / gP) == (int)( src / gP ) ) + src_hopcnt = 0; + else + src_hopcnt = 1; + + //hop count in destination group + if ((int)( dest_intm / gP) == (int)( dest / gP ) ){ + dest_hopcnt = 0; + }else{ + dest_hopcnt = 1; + } + + //tally + hopcnt = src_hopcnt + 1 + dest_hopcnt; + } + + return hopcnt; +} + + +//packet output port based on the source, destination and current location +int dragonfly_port(int rID, int source, int dest){ + int _grp_num_routers= gA; + int _grp_num_nodes =_grp_num_routers*gP; + + int out_port = -1; + int grp_ID = int(rID / _grp_num_routers); + int dest_grp_ID = int(dest/_grp_num_nodes); + int grp_output=-1; + int grp_RID=-1; + int group_dest=-1; + + //which router within this group the packet needs to go to + if (dest_grp_ID == grp_ID) { + grp_RID = int(dest / gP); + } else { + if (grp_ID > dest_grp_ID) { + grp_output = dest_grp_ID; + } else { + grp_output = dest_grp_ID - 1; + } + grp_RID = int(grp_output /gP) + grp_ID * _grp_num_routers; + group_dest = grp_RID * gP; + } + + //At the last hop + if (dest >= rID*gP && dest < (rID+1)*gP) { + out_port = dest%gP; + } else if (grp_RID == rID) { + //At the optical link + out_port = gP + (gA-1) + grp_output %(gP); + } else { + //need to route within a group + assert(grp_RID!=-1); + + if (rID < grp_RID){ + out_port = (grp_RID % _grp_num_routers) - 1 + gP; + }else{ + out_port = (grp_RID % _grp_num_routers) + gP; + } + } + + assert(out_port!=-1); + return out_port; +} + + +DragonFlyNew::DragonFlyNew( const Configuration &config, const string & name ) : + Network( config, name ) +{ + + _ComputeSize( config ); + _Alloc( ); + _BuildNet( config ); +} + +void DragonFlyNew::_ComputeSize( const Configuration &config ) +{ + + // LIMITATION + // -- only one dimension between the group + // _n == # of dimensions within a group + // _p == # of processors within a router + // inter-group ports : _p + // terminal ports : _p + // intra-group ports : 2*_p - 1 + _p = config.GetInt( "k" ); // # of ports in each switch + _n = config.GetInt( "n" ); + + + assert(_n==1); + // dimension + + if (_n == 1) + _k = _p + _p + 2*_p - 1; + else + _k = _p + _p + 2*_p; + + + // FIX... + gK = _p; gN = _n; + + // with 1 dimension, total of 2p routers per group + // N = 2p * p * (2p^2 + 1) + // a = # of routers per group + // = 2p (if n = 1) + // = p^(n) (if n > 2) + // g = # of groups + // = a * p + 1 + // N = a * p * g; + + if (_n == 1) + _a = 2 * _p; + else + _a = powi(_p, _n); + + _g = _a * _p + 1; + _nodes = _a * _p * _g; + + _num_of_switch = _nodes / _p; + _channels = _num_of_switch * (_k - _p); + _size = _num_of_switch; + + + + gG = _g; + gP = _p; + gA = _a; + _grp_num_routers = gA; + _grp_num_nodes =_grp_num_routers*gP; + +} + +void DragonFlyNew::_BuildNet( const Configuration &config ) +{ + + int _output; + int _input; + int c; + int _dim_ID; + int _num_ports_per_switch; + int _dim_size; + + ostringstream router_name; + + + + cout << " Dragonfly " << endl; + cout << " p = " << _p << " n = " << _n << endl; + cout << " each switch - total radix = "<< _k << endl; + cout << " # of switches = "<< _num_of_switch << endl; + cout << " # of channels = "<< _channels << endl; + cout << " # of nodes ( size of network ) = " << _nodes << endl; + cout << " # of groups (_g) = " << _g << endl; + cout << " # of routers per group (_a) = " << _a << endl; + + for ( int node = 0; node < _num_of_switch; ++node ) { + // ID of the group + int grp_ID; + grp_ID = (int) (node/_a); + router_name << "router"; + + router_name << "_" << node ; + + _routers[node] = Router::NewRouter( config, this, router_name.str( ), + node, _k, _k ); + _timed_modules.push_back(_routers[node]); + + router_name.str(""); + + for ( int cnt = 0; cnt < _p; ++cnt ) { + c = _p * node + cnt; + _routers[node]->AddInputChannel( _inject[c], _inject_cred[c] ); + + } + + for ( int cnt = 0; cnt < _p; ++cnt ) { + c = _p * node + cnt; + _routers[node]->AddOutputChannel( _eject[c], _eject_cred[c] ); + + } + + // add OUPUT channels + // _k == # of processor per router + // need 2*_k routers --thus, + // 2_k-1 outputs channels within group + // _k-1 outputs for intra-group + + // + + if (_n > 1 ) { cout << " ERROR: n>1 dimension NOT supported yet... " << endl; exit(-1); } + + //******************************************** + // connect OUTPUT channels + //******************************************** + // add intra-group output channel + for ( int dim = 0; dim < _n; ++dim ) { + for ( int cnt = 0; cnt < (2*_p -1); ++cnt ) { + _output = (2*_p-1 + _p) * _n * node + (2*_p-1) * dim + cnt; + + _routers[node]->AddOutputChannel( _chan[_output], _chan_cred[_output] ); + +#ifdef DRAGON_LATENCY + _chan[_output]->SetLatency(10); + _chan_cred[_output]->SetLatency(10); +#endif + } + } + + // add inter-group output channel + + for ( int cnt = 0; cnt < _p; ++cnt ) { + _output = (2*_p-1 + _p) * node + (2*_p - 1) + cnt; + + // _chan[_output].global = true; + _routers[node]->AddOutputChannel( _chan[_output], _chan_cred[_output] ); +#ifdef DRAGON_LATENCY + _chan[_output]->SetLatency(100); + _chan_cred[_output]->SetLatency(100); +#endif + } + + + //******************************************** + // connect INPUT channels + //******************************************** + // # of non-local nodes + _num_ports_per_switch = (_k - _p); + + + // intra-group GROUP channels + for ( int dim = 0; dim < _n; ++dim ) { + + _dim_size = powi(_k,dim); + + _dim_ID = ((int) (node / ( powi(_p, dim)))); + + + + // NODE ID withing group + _dim_ID = node % _a; + + + + + for ( int cnt = 0; cnt < (2*_p-1); ++cnt ) { + + if ( cnt < _dim_ID) { + + _input = grp_ID * _num_ports_per_switch * _a - + (_dim_ID - cnt) * _num_ports_per_switch + + _dim_ID * _num_ports_per_switch + + (_dim_ID - 1); + } + else { + + _input = grp_ID * _num_ports_per_switch * _a + + _dim_ID * _num_ports_per_switch + + (cnt - _dim_ID + 1) * _num_ports_per_switch + + _dim_ID; + + } + + if (_input < 0) { + cout << " ERROR: _input less than zero " << endl; + exit(-1); + } + + + _routers[node]->AddInputChannel( _chan[_input], _chan_cred[_input] ); + } + } + + + // add INPUT channels -- "optical" channels connecting the groups + int _grp_num_routers; + int grp_output; + int grp_ID2; + + for ( int cnt = 0; cnt < _p; ++cnt ) { + // _dim_ID + grp_output = _dim_ID* _p + cnt; + + _grp_num_routers = powi(_k, _n-1); + grp_ID2 = (int) ((grp_ID - 1) / (_k - 1)); + + if ( grp_ID > grp_output) { + + _input = (grp_output) * _num_ports_per_switch * _a + // starting point of group + (_num_ports_per_switch - _p) * (int) ((grp_ID - 1) / _p) + // find the correct router within grp + (_num_ports_per_switch - _p) + // add offset within router + grp_ID - 1; + } else { + + _input = (grp_output + 1) * _num_ports_per_switch * _a + + (_num_ports_per_switch - _p) * (int) ((grp_ID) / _p) + // find the correct router within grp + (_num_ports_per_switch - _p) + + grp_ID; + } + + _routers[node]->AddInputChannel( _chan[_input], _chan_cred[_input] ); + } + + } + + cout<<"Done links"<Clear( ); + + if(inject) { + int inject_vc= RandomInt(gNumVCs-1); + outputs->AddRange(-1, inject_vc, inject_vc); + return; + } + + int _grp_num_routers= gA; + + int dest = f->dest; + int rID = r->GetID(); + + int grp_ID = int(rID / _grp_num_routers); + int debug = f->watch; + int out_port = -1; + int out_vc = 0; + int dest_grp_ID=-1; + + if ( in_channel < gP ) { + out_vc = 0; + f->ph = 0; + if (dest_grp_ID == grp_ID) { + f->ph = 1; + } + } + + + out_port = dragonfly_port(rID, f->src, dest); + + //optical dateline + if (out_port >=gP + (gA-1)) { + f->ph = 1; + } + + out_vc = f->ph; + if (debug) + *gWatchOut << GetSimTime() << " | " << r->FullName() << " | " + << " through output port : " << out_port + << " out vc: " << out_vc << endl; + outputs->AddRange( out_port, out_vc, out_vc ); +} + + +//Basic adaptive routign algorithm for the dragonfly +void ugal_dragonflynew( const Router *r, const Flit *f, int in_channel, + OutputSet *outputs, bool inject ) +{ + //need 3 VCs for deadlock freedom + + assert(gNumVCs==3); + outputs->Clear( ); + if(inject) { + int inject_vc= RandomInt(gNumVCs-1); + outputs->AddRange(-1, inject_vc, inject_vc); + return; + } + + //this constant biases the adaptive decision toward minimum routing + //negative value woudl biases it towards nonminimum routing + int adaptive_threshold = 30; + + int _grp_num_routers= gA; + int _grp_num_nodes =_grp_num_routers*gP; + int _network_size = gA * gP * gG; + + + int dest = f->dest; + int rID = r->GetID(); + int grp_ID = (int) (rID / _grp_num_routers); + int dest_grp_ID = int(dest/_grp_num_nodes); + + int debug = f->watch; + int out_port = -1; + int out_vc = 0; + int min_queue_size, min_hopcnt; + int nonmin_queue_size, nonmin_hopcnt; + int intm_grp_ID; + int intm_rID; + + if(debug){ + cout<<"At router "<ph = 2; + } else { + //select a random node + f->intm =RandomInt(_network_size - 1); + intm_grp_ID = (int)(f->intm/_grp_num_nodes); + if (debug){ + cout<<"Intermediate node "<intm<<" grp id "<ph = 1; + } else { + //congestion metrics using queue length, obtained by GetUsedCredit() + min_hopcnt = dragonflynew_hopcnt(f->src, f->dest); + min_router_output = dragonfly_port(rID, f->src, f->dest); + min_queue_size = max(r->GetUsedCredit(min_router_output), 0) ; + + + nonmin_hopcnt = dragonflynew_hopcnt(f->src, f->intm) + + dragonflynew_hopcnt(f->intm,f->dest); + nonmin_router_output = dragonfly_port(rID, f->src, f->intm); + nonmin_queue_size = max(r->GetUsedCredit(nonmin_router_output), 0); + + //congestion comparison, could use hopcnt instead of 1 and 2 + if ((1 * min_queue_size ) <= (2 * nonmin_queue_size)+adaptive_threshold ) { + if (debug) cout << " MINIMAL routing " << endl; + f->ph = 1; + } else { + f->ph = 0; + } + } + } + } + + //transition from nonminimal phase to minimal + if(f->ph==0){ + intm_rID= (int)(f->intm/gP); + if( rID == intm_rID){ + f->ph = 1; + } + } + + //port assignement based on the phase + if(f->ph == 0){ + out_port = dragonfly_port(rID, f->src, f->intm); + } else if(f->ph == 1){ + out_port = dragonfly_port(rID, f->src, f->dest); + } else if(f->ph == 2){ + out_port = dragonfly_port(rID, f->src, f->dest); + } else { + assert(false); + } + + //optical dateline + if (f->ph == 1 && out_port >=gP + (gA-1)) { + f->ph = 2; + } + + //vc assignemnt based on phase + out_vc = f->ph; + + outputs->AddRange( out_port, out_vc, out_vc ); +} -- cgit v1.3