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]

1 files changed, 1331 insertions, 0 deletions

diff --git a/src/intersim2/networks/flatfly_onchip.cpp b/src/intersim2/networks/flatfly_onchip.cpp
new file mode 100644
index 0000000..fd17c1a
--- /dev/null
+++ b/src/intersim2/networks/flatfly_onchip.cpp
@@ -0,0 +1,1331 @@
+// $Id: flatfly_onchip.cpp 5188 2012-08-30 00:31:31Z dub $
+
+/*
+ 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.
+
+ 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.
+*/
+
+//Flattened butterfly simulator
+//Created by John Kim
+//
+//Updated 11/6/2007 by Ted Jiang, now scales 
+//with any n such that N = K^3, k is a power of 2
+//however, the change restrict it to a 2D FBfly
+//
+//updated sometimes in december by Ted Jiang, now works for updat to 4
+//dimension. 
+//
+//Updated 2/4/08 by Ted Jiang disabling partial networks
+//change concentrations
+//
+//More update 3/31/08 to correctly assign the nodes to the routers
+//UGAL now has added a "mapping" to account for this new assignment
+//of the nodes to the routers
+//
+//Updated by mihelog   27 Aug to add progressive choice of intermediate destination.
+//Also, half of the total vcs are used for non-minimal routing, others for minimal (for UGAL and valiant).
+
+
+#include "booksim.hpp"
+#include <vector>
+#include <sstream>
+#include <limits>
+#include <cmath>
+#include "flatfly_onchip.hpp"
+#include "random_utils.hpp"
+#include "misc_utils.hpp"
+#include "globals.hpp"
+
+
+
+//#define DEBUG_FLATFLY
+
+static int _xcount;
+static int _ycount;
+static int _xrouter;
+static int _yrouter;
+
+FlatFlyOnChip::FlatFlyOnChip( const Configuration &config, const string & name ) :
+  Network( config, name )
+{
+
+  _ComputeSize( config );
+  _Alloc( );
+  _BuildNet( config );
+}
+
+void FlatFlyOnChip::_ComputeSize( const Configuration &config )
+{
+  _k = config.GetInt( "k" );	// # of routers per dimension
+  _n = config.GetInt( "n" );	// dimension
+  _c = config.GetInt( "c" );    //concentration, may be different from k
+  _r = _c + (_k-1)*_n ;		// total radix of the switch  ( # of inputs/outputs)
+
+  //how many routers in the x or y direction
+  _xcount = config.GetInt("x");
+  _ycount = config.GetInt("y");
+  assert(_xcount == _ycount);
+  //configuration of hohw many clients in X and Y per router
+  _xrouter = config.GetInt("xr");
+  _yrouter = config.GetInt("yr");
+  assert(_xrouter == _yrouter);
+  gK = _k; 
+  gN = _n;
+  gC = _c;
+  
+  assert(_c == _xrouter*_yrouter);
+
+  _nodes = powi( _k, _n )*_c;   //network size
+
+  _num_of_switch = _nodes / _c;
+  _channels = _num_of_switch * (_r - _c); 
+  _size = _num_of_switch;
+
+}
+
+void FlatFlyOnChip::_BuildNet( const Configuration &config )
+{
+  int _output;
+
+  ostringstream router_name;
+
+  
+  if(gTrace){
+
+    cout<<"Setup Finished Router"<<endl;
+    
+  }
+
+  //latency type, noc or conventional network
+  bool use_noc_latency;
+  use_noc_latency = (config.GetInt("use_noc_latency")==1);
+  
+  cout << " Flat Bufferfly " << endl;
+  cout << " k = " << _k << " n = " << _n << " c = "<<_c<< endl;
+  cout << " each switch - total radix =  "<< _r << endl;
+  cout << " # of switches = "<<  _num_of_switch << endl;
+  cout << " # of channels = "<<  _channels << endl;
+  cout << " # of nodes ( size of network ) = " << _nodes << endl;
+
+  for ( int node = 0; node < _num_of_switch; ++node ) {
+
+    router_name << "router";
+    router_name << "_" <<  node ;
+
+    _routers[node] = Router::NewRouter( config, this, router_name.str( ), 
+					node, _r, _r );
+    _timed_modules.push_back(_routers[node]);
+
+
+#ifdef DEBUG_FLATFLY
+    cout << " ======== router node : " << node << " ======== " << " router_" << router_name.str() << " router node # : " << node << endl;
+#endif
+
+    router_name.str("");
+
+    //******************************************************************
+    // add inject/eject channels connected to the processor nodes
+    //******************************************************************
+    
+    //as accurately model the length of these channels as possible
+    int yleng = -_yrouter/2;
+    int xleng = -_xrouter/2;
+    bool yodd = _yrouter%2==1;
+    bool xodd = _xrouter%2==1;
+    
+    int y_index = node/(_xcount);
+    int x_index = node%(_xcount);
+    //estimating distance from client to router
+    for (int y = 0; y < _yrouter ; y++) {
+      for (int x = 0; x < _xrouter ; x++) {
+	//Zero is a naughty number
+	if(yleng == 0 && !yodd){
+	  yleng++;
+	}
+	if(xleng == 0 && !xodd){
+	  xleng++;
+	}
+	int ileng = 1;   //at least 1 away
+	//measure distance in the y direction
+	if(abs(yleng)>1){
+	  ileng+=(abs(yleng)-1);
+	}
+	//measure distance in the x direction
+	if(abs(xleng)>1){
+	  ileng+=(abs(xleng)-1);
+	}
+	//increment for the next client, add Y, if full, reset y add x
+	yleng++;
+	if(yleng>_yrouter/2){
+	  yleng= -_yrouter/2;
+	  xleng++;
+	}
+	//adopted from the CMESH, the first node has 0,1,8,9 (as an example)
+	int link = (_xcount * _xrouter) * (_yrouter * y_index + y) + (_xrouter * x_index + x) ;
+
+	if(use_noc_latency){
+	  _inject[link]->SetLatency(ileng);
+	  _inject_cred[link]->SetLatency(ileng);
+	  _eject[link] ->SetLatency(ileng);
+	  _eject_cred[link]->SetLatency(ileng);
+	} else {
+	  _inject[link]->SetLatency(1);
+	  _inject_cred[link]->SetLatency(1);
+	  _eject[link] ->SetLatency(1);
+	  _eject_cred[link]->SetLatency(1);
+	}
+	_routers[node]->AddInputChannel( _inject[link], _inject_cred[link] );
+	
+#ifdef DEBUG_FLATFLY
+	cout << "  Adding injection channel " << link << endl;
+#endif
+	
+	_routers[node]->AddOutputChannel( _eject[link], _eject_cred[link] );
+#ifdef DEBUG_FLATFLY
+	cout << "  Adding ejection channel " << link << endl;
+#endif
+      }
+    }
+  }
+  //******************************************************************
+  // add output inter-router channels
+  //******************************************************************
+
+  //for every router, in every dimension
+  for ( int node = 0; node < _num_of_switch; ++node ) {
+    for ( int dim = 0; dim < _n; ++dim ) {
+
+      //locate itself in every dimension
+      int xcurr = node%_k;
+      int ycurr = (int)(node/_k);
+      int curr3 = node%(_k*_k);
+      int curr4 = (int)(node/(_k*_k));
+      int curr5 = (int)(node/(_k*_k*_k));//mmm didn't mean to be racist
+      int curr6 = (node%(_k*_k*_k));//mmm didn't mean to be racist
+
+      //for every other router in the dimension
+      for ( int cnt = 0; cnt < (_k ); ++cnt ) {	
+	int other=0; //the other router that we are trying to connect
+	int offset = 0; //silly ness when node< other or when node>other
+	//if xdimension
+	if(dim == 0){
+	  other = ycurr * _k +cnt;
+	} else if (dim ==1){
+	  other = cnt * _k + xcurr;
+	  if(_n==3){
+	    other+= curr4*_k*_k;
+	  } 
+	  if(_n==4){
+	    curr4=((int)(node/(_k*_k)))%_k;
+	    other+= curr4*_k*_k+curr5*_k*_k*_k;
+	  }
+	}else if (dim ==2){
+	  other = cnt*_k*_k + curr3;
+	  if(_n==4){
+	    other+= curr5*_k*_k*_k;
+	  }
+	}else if (dim ==3){
+	  other = cnt*_k*_k*_k+curr6;
+	}
+	assert(dim < 4);
+	if(other == node){
+#ifdef DEBUG_FLATFLY
+	  cout << "ignore channel : " << _output << " to node " << node <<" and "<<other<<endl;
+#endif
+	  continue;
+	}
+	//calculate channel length
+	int length = 0;
+	int oned = abs((node%_xcount)-(other%_xcount));
+	int twod = abs(node/_xcount-other/_xcount);
+	length = _xrouter*oned + _yrouter *twod;
+	//oh the node<other silly ness
+	if(node<other){
+	  offset = -1;
+	}
+	//node, dimension, router within dimension. Good luck understanding this
+	_output = (_k-1) * _n  * node + (_k-1) * dim  + cnt+offset;
+	
+	
+#ifdef DEBUG_FLATFLY
+	cout << "Adding channel : " << _output << " to node " << node <<" and "<<other<<" with length "<<length<<endl;
+#endif
+	if(use_noc_latency){
+	  _chan[_output]->SetLatency(length);
+	  _chan_cred[_output]->SetLatency(length);
+	} else {
+	  _chan[_output]->SetLatency(1);
+	  _chan_cred[_output]->SetLatency(1);
+	}
+	_routers[node]->AddOutputChannel( _chan[_output], _chan_cred[_output] );
+	
+	_routers[other]->AddInputChannel( _chan[_output], _chan_cred[_output]);
+	
+	if(gTrace){
+	  cout<<"Link "<<_output<<" "<<node<<" "<<other<<" "<<length<<endl;
+	}
+	
+      }
+    }
+  }
+  if(gTrace){
+    cout<<"Setup Finished Link"<<endl;
+  }
+}
+
+
+int FlatFlyOnChip::GetN( ) const
+{
+  return _n;
+}
+
+int FlatFlyOnChip::GetK( ) const
+{
+  return _k;
+}
+
+void FlatFlyOnChip::InsertRandomFaults( const Configuration &config )
+{
+
+}
+
+double FlatFlyOnChip::Capacity( ) const
+{
+  return (double)_k / 8.0;
+}
+
+
+void FlatFlyOnChip::RegisterRoutingFunctions(){
+
+  
+  gRoutingFunctionMap["ran_min_flatfly"] = &min_flatfly;
+  gRoutingFunctionMap["adaptive_xyyx_flatfly"] = &adaptive_xyyx_flatfly;
+  gRoutingFunctionMap["xyyx_flatfly"] = &xyyx_flatfly;
+  gRoutingFunctionMap["valiant_flatfly"] = &valiant_flatfly;
+  gRoutingFunctionMap["ugal_flatfly"] = &ugal_flatfly_onchip;
+  gRoutingFunctionMap["ugal_pni_flatfly"] = &ugal_pni_flatfly_onchip;
+  gRoutingFunctionMap["ugal_xyyx_flatfly"] = &ugal_xyyx_flatfly_onchip;
+
+}
+
+//The initial XY or YX minimal routing direction is chosen adaptively
+void adaptive_xyyx_flatfly( const Router *r, const Flit *f, int in_channel, 
+		  OutputSet *outputs, bool inject )
+{ 
+  // ( Traffic Class , Routing Order ) -> Virtual Channel Range
+  int vcBegin = 0, vcEnd = gNumVCs-1;
+  if ( f->type == Flit::READ_REQUEST ) {
+    vcBegin = gReadReqBeginVC;
+    vcEnd = gReadReqEndVC;
+  } else if ( f->type == Flit::WRITE_REQUEST ) {
+    vcBegin = gWriteReqBeginVC;
+    vcEnd = gWriteReqEndVC;
+  } else if ( f->type ==  Flit::READ_REPLY ) {
+    vcBegin = gReadReplyBeginVC;
+    vcEnd = gReadReplyEndVC;
+  } else if ( f->type ==  Flit::WRITE_REPLY ) {
+    vcBegin = gWriteReplyBeginVC;
+    vcEnd = gWriteReplyEndVC;
+  }
+  assert(((f->vc >= vcBegin) && (f->vc <= vcEnd)) || (inject && (f->vc < 0)));
+
+  int out_port;
+
+  if(inject) {
+
+    out_port = -1;
+
+  } else {
+
+    int dest = flatfly_transformation(f->dest);
+    int targetr = (int)(dest/gC);
+
+    if(targetr==r->GetID()){ //if we are at the final router, yay, output to client
+      out_port = dest % gC;
+
+    } else {
+   
+      //each class must have at least 2 vcs assigned or else xy_yx will deadlock
+      int const available_vcs = (vcEnd - vcBegin + 1) / 2;
+      assert(available_vcs > 0);
+
+      int out_port_xy =  flatfly_outport(dest, r->GetID());
+      int out_port_yx =  flatfly_outport_yx(dest, r->GetID());
+
+      // Route order (XY or YX) determined when packet is injected
+      //  into the network, adaptively
+      bool x_then_y;
+      if(in_channel < gC){
+	int credit_xy = r->GetUsedCredit(out_port_xy);
+	int credit_yx = r->GetUsedCredit(out_port_yx);
+	if(credit_xy > credit_yx) {
+	  x_then_y = false;
+	} else if(credit_xy < credit_yx) {
+	  x_then_y = true;
+	} else {
+	  x_then_y = (RandomInt(1) > 0);
+	}
+      } else {
+	x_then_y =  (f->vc < (vcBegin + available_vcs));
+      }
+      
+      if(x_then_y) {
+	out_port = out_port_xy;
+	vcEnd -= available_vcs;
+      } else {
+	out_port = out_port_yx;
+	vcBegin += available_vcs;
+      }
+    }
+
+  }
+
+  outputs->Clear( );
+
+  outputs->AddRange( out_port , vcBegin, vcEnd );
+}
+
+//The initial XY or YX minimal routing direction is chosen randomly
+void xyyx_flatfly( const Router *r, const Flit *f, int in_channel, 
+		  OutputSet *outputs, bool inject )
+{ 
+  // ( Traffic Class , Routing Order ) -> Virtual Channel Range
+  int vcBegin = 0, vcEnd = gNumVCs-1;
+  if ( f->type == Flit::READ_REQUEST ) {
+    vcBegin = gReadReqBeginVC;
+    vcEnd = gReadReqEndVC;
+  } else if ( f->type == Flit::WRITE_REQUEST ) {
+    vcBegin = gWriteReqBeginVC;
+    vcEnd = gWriteReqEndVC;
+  } else if ( f->type ==  Flit::READ_REPLY ) {
+    vcBegin = gReadReplyBeginVC;
+    vcEnd = gReadReplyEndVC;
+  } else if ( f->type ==  Flit::WRITE_REPLY ) {
+    vcBegin = gWriteReplyBeginVC;
+    vcEnd = gWriteReplyEndVC;
+  }
+  assert(((f->vc >= vcBegin) && (f->vc <= vcEnd)) || (inject && (f->vc < 0)));
+
+  int out_port;
+
+  if(inject) {
+
+    out_port = -1;
+
+  } else {
+
+    int dest = flatfly_transformation(f->dest);
+    int targetr = (int)(dest/gC);
+
+    if(targetr==r->GetID()){ //if we are at the final router, yay, output to client
+      out_port = dest % gC;
+
+    } else {
+   
+      //each class must have at least 2 vcs assigned or else xy_yx will deadlock
+      int const available_vcs = (vcEnd - vcBegin + 1) / 2;
+      assert(available_vcs > 0);
+
+      // randomly select dimension order at first hop
+      bool x_then_y = ((in_channel < gC) ?
+		       (RandomInt(1) > 0) : 
+		       (f->vc < (vcBegin + available_vcs)));
+
+      if(x_then_y) {
+	out_port = flatfly_outport(dest, r->GetID());
+	vcEnd -= available_vcs;
+      } else {
+	out_port = flatfly_outport_yx(dest, r->GetID());
+	vcBegin += available_vcs;
+      }
+    }
+
+  }
+
+  outputs->Clear( );
+
+  outputs->AddRange( out_port , vcBegin, vcEnd );
+}
+
+int flatfly_outport_yx(int dest, int rID) {
+  int dest_rID = (int) (dest / gC);
+  int _dim   = gN;
+  int output = -1, dID, sID;
+  
+  if(dest_rID==rID){
+    return dest % gC;
+  }
+
+  for (int d=_dim-1;d >= 0; d--) {
+    int power = powi(gK,d);
+    dID = int(dest_rID / power);
+    sID = int(rID / power);
+    if ( dID != sID ) {
+      output = gC + ((gK-1)*d) - 1;
+      if (dID > sID) {
+	output += dID;
+      } else {
+	output += dID + 1;
+      }
+      return output;
+    }
+    dest_rID = (int) (dest_rID %power);
+    rID      = (int) (rID %power);
+  }
+  if (output == -1) {
+    cout << " ERROR ---- FLATFLY_OUTPORT function : output not found yx" << endl;
+    exit(-1);
+  }
+  return -1;
+}
+
+void valiant_flatfly( const Router *r, const Flit *f, int in_channel, 
+		  OutputSet *outputs, bool inject )
+{
+  // ( Traffic Class , Routing Order ) -> Virtual Channel Range
+  int vcBegin = 0, vcEnd = gNumVCs-1;
+  if ( f->type == Flit::READ_REQUEST ) {
+    vcBegin = gReadReqBeginVC;
+    vcEnd = gReadReqEndVC;
+  } else if ( f->type == Flit::WRITE_REQUEST ) {
+    vcBegin = gWriteReqBeginVC;
+    vcEnd = gWriteReqEndVC;
+  } else if ( f->type ==  Flit::READ_REPLY ) {
+    vcBegin = gReadReplyBeginVC;
+    vcEnd = gReadReplyEndVC;
+  } else if ( f->type ==  Flit::WRITE_REPLY ) {
+    vcBegin = gWriteReplyBeginVC;
+    vcEnd = gWriteReplyEndVC;
+  }
+  assert(((f->vc >= vcBegin) && (f->vc <= vcEnd)) || (inject && (f->vc < 0)));
+
+  int out_port;
+
+  if(inject) {
+
+    out_port = -1;
+
+  } else {
+
+    if ( in_channel < gC ){
+      f->ph = 0;
+      f->intm = RandomInt( powi( gK, gN )*gC-1);
+    }
+
+    int intm = flatfly_transformation(f->intm);
+    int dest = flatfly_transformation(f->dest);
+
+    if((int)(intm/gC) == r->GetID() || (int)(dest/gC)== r->GetID()){
+      f->ph = 1;
+    }
+
+    if(f->ph == 0) {
+      out_port = flatfly_outport(intm, r->GetID());
+    } else {
+      assert(f->ph == 1);
+      out_port = flatfly_outport(dest, r->GetID());
+    }
+
+    if((int)(dest/gC) != r->GetID()) {
+
+      //each class must have at least 2 vcs assigned or else valiant valiant will deadlock
+      int const available_vcs = (vcEnd - vcBegin + 1) / 2;
+      assert(available_vcs > 0);
+
+      if(f->ph == 0) {
+	vcEnd -= available_vcs;
+      } else {
+	// If routing to final destination use the second half of the VCs.
+	assert(f->ph == 1);
+	vcBegin += available_vcs;
+      }
+    }
+
+  }
+
+  outputs->Clear( );
+
+  outputs->AddRange( out_port , vcBegin, vcEnd );
+}
+
+void min_flatfly( const Router *r, const Flit *f, int in_channel, 
+		  OutputSet *outputs, bool inject )
+{
+  // ( Traffic Class , Routing Order ) -> Virtual Channel Range
+  int vcBegin = 0, vcEnd = gNumVCs-1;
+  if ( f->type == Flit::READ_REQUEST ) {
+    vcBegin = gReadReqBeginVC;
+    vcEnd = gReadReqEndVC;
+  } else if ( f->type == Flit::WRITE_REQUEST ) {
+    vcBegin = gWriteReqBeginVC;
+    vcEnd = gWriteReqEndVC;
+  } else if ( f->type ==  Flit::READ_REPLY ) {
+    vcBegin = gReadReplyBeginVC;
+    vcEnd = gReadReplyEndVC;
+  } else if ( f->type ==  Flit::WRITE_REPLY ) {
+    vcBegin = gWriteReplyBeginVC;
+    vcEnd = gWriteReplyEndVC;
+  }
+  assert(((f->vc >= vcBegin) && (f->vc <= vcEnd)) || (inject && (f->vc < 0)));
+
+  int out_port;
+
+  if(inject) {
+
+    out_port = -1;
+
+  } else {
+
+    int dest  = flatfly_transformation(f->dest);
+    int targetr= (int)(dest/gC);
+    //int xdest = ((int)(dest/gC)) % gK;
+    //int xcurr = ((r->GetID())) % gK;
+
+    //int ydest = ((int)(dest/gC)) / gK;
+    //int ycurr = ((r->GetID())) / gK;
+
+    if(targetr==r->GetID()){ //if we are at the final router, yay, output to client
+      out_port = dest % gC;
+    } else{ //else select a dimension at random
+      out_port = flatfly_outport(dest, r->GetID());
+    }
+
+  }
+
+  outputs->Clear( );
+
+  outputs->AddRange( out_port , vcBegin, vcEnd );
+}
+
+//=============================================================^M
+// route UGAL in the flattened butterfly
+//=============================================================^M
+
+
+//same as ugal except uses xyyx routing
+void ugal_xyyx_flatfly_onchip( const Router *r, const Flit *f, int in_channel,
+			  OutputSet *outputs, bool inject )
+{
+  // ( Traffic Class , Routing Order ) -> Virtual Channel Range
+  int vcBegin = 0, vcEnd = gNumVCs-1;
+  if ( f->type == Flit::READ_REQUEST ) {
+    vcBegin = gReadReqBeginVC;
+    vcEnd = gReadReqEndVC;
+  } else if ( f->type == Flit::WRITE_REQUEST ) {
+    vcBegin = gWriteReqBeginVC;
+    vcEnd = gWriteReqEndVC;
+  } else if ( f->type ==  Flit::READ_REPLY ) {
+    vcBegin = gReadReplyBeginVC;
+    vcEnd = gReadReplyEndVC;
+  } else if ( f->type ==  Flit::WRITE_REPLY ) {
+    vcBegin = gWriteReplyBeginVC;
+    vcEnd = gWriteReplyEndVC;
+  }
+  assert(((f->vc >= vcBegin) && (f->vc <= vcEnd)) || (inject && (f->vc < 0)));
+
+  int out_port;
+
+  if(inject) {
+
+    out_port = -1;
+
+  } else {
+
+    int dest  = flatfly_transformation(f->dest);
+
+    int rID =  r->GetID();
+    int _concentration = gC;
+    int found;
+    int debug = 0;
+    int tmp_out_port, _ran_intm;
+    int _min_hop, _nonmin_hop, _min_queucnt, _nonmin_queucnt;
+    int threshold = 2;
+
+
+    if ( in_channel < gC ){
+      if(gTrace){
+	cout<<"New Flit "<<f->src<<endl;
+      }
+      f->ph   = 0;
+    }
+
+    if(gTrace){
+      int load = 0;
+      cout<<"Router "<<rID<<endl;
+      cout<<"Input Channel "<<in_channel<<endl;
+      //need to modify router to report the buffere depth
+      load +=r->GetBufferOccupancy(in_channel);
+      cout<<"Rload "<<load<<endl;
+    }
+
+    if (debug){
+      cout << " FLIT ID: " << f->id << " Router: " << rID << " routing from src : " << f->src <<  " to dest : " << dest << " f->ph: " <<f->ph << " intm: " << f->intm <<  endl;
+    }
+    // f->ph == 0  ==> make initial global adaptive decision
+    // f->ph == 1  ==> route nonminimaly to random intermediate node
+    // f->ph == 2  ==> route minimally to destination
+
+    found = 0;
+
+    if (f->ph == 1){
+      dest = f->intm;
+    }
+
+    if (dest >= rID*_concentration && dest < (rID+1)*_concentration) {
+      if (f->ph == 1) {
+	f->ph = 2;
+	dest = flatfly_transformation(f->dest);
+	if (debug)   cout << "      done routing to intermediate ";
+      }
+      else  {
+	found = 1;
+	out_port = dest % gC;
+	if (debug)   cout << "      final routing to destination ";
+      }
+    }
+
+    if (!found) {
+
+      int const xy_available_vcs = (vcEnd - vcBegin + 1) / 2;
+      assert(xy_available_vcs > 0);
+
+      // randomly select dimension order at first hop
+      bool x_then_y = ((in_channel < gC) ?
+		       (RandomInt(1) > 0) : 
+		       (f->vc < (vcBegin + xy_available_vcs)));
+
+      if (f->ph == 0) {
+	//find the min port and min distance
+	_min_hop = find_distance(flatfly_transformation(f->src),dest);
+	if(x_then_y){
+	  tmp_out_port =  flatfly_outport(dest, rID);
+	} else {
+	  tmp_out_port =  flatfly_outport_yx(dest, rID);
+	}
+	if (f->watch){
+	  cout << " MIN tmp_out_port: " << tmp_out_port;
+	}
+	//sum over all vcs of that port
+	_min_queucnt =   r->GetUsedCredit(tmp_out_port);
+
+	//find the nonmin router, nonmin port, nonmin count
+	_ran_intm = find_ran_intm(flatfly_transformation(f->src), dest);
+	_nonmin_hop = find_distance(flatfly_transformation(f->src),_ran_intm) +    find_distance(_ran_intm, dest);
+	if(x_then_y){
+	  tmp_out_port =  flatfly_outport(_ran_intm, rID);
+	} else {
+	  tmp_out_port =  flatfly_outport_yx(_ran_intm, rID);
+	}
+
+	if (f->watch){
+	  cout << " NONMIN tmp_out_port: " << tmp_out_port << endl;
+	}
+	if (_ran_intm >= rID*_concentration && _ran_intm < (rID+1)*_concentration) {
+	  _nonmin_queucnt = numeric_limits<int>::max();
+	} else  {
+	  _nonmin_queucnt =   r->GetUsedCredit(tmp_out_port);
+	}
+
+	if (debug){
+	  cout << " _min_hop " << _min_hop << " _min_queucnt: " <<_min_queucnt << " _nonmin_hop: " << _nonmin_hop << " _nonmin_queucnt :" << _nonmin_queucnt <<  endl;
+	}
+
+	if (_min_hop * _min_queucnt   <= _nonmin_hop * _nonmin_queucnt +threshold) {
+
+	  if (debug) cout << " Route MINIMALLY " << endl;
+	  f->ph = 2;
+	} else {
+	  // route non-minimally
+	  if (debug)  { cout << " Route NONMINIMALLY int node: " <<_ran_intm << endl; }
+	  f->ph = 1;
+	  f->intm = _ran_intm;
+	  dest = f->intm;
+	  if (dest >= rID*_concentration && dest < (rID+1)*_concentration) {
+	    f->ph = 2;
+	    dest = flatfly_transformation(f->dest);
+	  }
+	}
+      }
+
+      //dest here should be == intm if ph==1, or dest == dest if ph == 2
+      if(x_then_y){
+	out_port =  flatfly_outport(dest, rID);
+	if(out_port >= gC) {
+	  vcEnd -= xy_available_vcs;
+	}
+      } else {
+	out_port =  flatfly_outport_yx(dest, rID);
+	if(out_port >= gC) {
+	  vcBegin += xy_available_vcs;
+	}
+      }
+
+      // if we haven't reached our destination, restrict VCs appropriately to avoid routing deadlock
+      if(out_port >= gC) {
+
+	int const ph_available_vcs = xy_available_vcs / 2;
+	assert(ph_available_vcs > 0);
+
+	if(f->ph == 1) {
+	  vcEnd -= ph_available_vcs;
+	} else {
+	  assert(f->ph == 2);
+	  vcBegin += ph_available_vcs;
+	}
+      }
+
+      found = 1;
+    }
+
+    if (!found) {
+      cout << " ERROR: output not found in routing. " << endl;
+      cout << *f; exit (-1);
+    }
+
+    if (out_port >= gN*(gK-1) + gC)  {
+      cout << " ERROR: output port too big! " << endl;
+      cout << " OUTPUT select: " << out_port << endl;
+      cout << " router radix: " <<  gN*(gK-1) + gK << endl;
+      exit (-1);
+    }
+
+    if (debug) cout << "        through output port : " << out_port << endl;
+    if(gTrace){cout<<"Outport "<<out_port<<endl;cout<<"Stop Mark"<<endl;}
+
+  }
+
+  outputs->Clear( );
+
+  outputs->AddRange( out_port , vcBegin, vcEnd );
+}
+
+
+
+//ugal now uses modified comparison, modefied getcredit
+void ugal_flatfly_onchip( const Router *r, const Flit *f, int in_channel,
+			  OutputSet *outputs, bool inject )
+{
+  // ( Traffic Class , Routing Order ) -> Virtual Channel Range
+  int vcBegin = 0, vcEnd = gNumVCs-1;
+  if ( f->type == Flit::READ_REQUEST ) {
+    vcBegin = gReadReqBeginVC;
+    vcEnd = gReadReqEndVC;
+  } else if ( f->type == Flit::WRITE_REQUEST ) {
+    vcBegin = gWriteReqBeginVC;
+    vcEnd = gWriteReqEndVC;
+  } else if ( f->type ==  Flit::READ_REPLY ) {
+    vcBegin = gReadReplyBeginVC;
+    vcEnd = gReadReplyEndVC;
+  } else if ( f->type ==  Flit::WRITE_REPLY ) {
+    vcBegin = gWriteReplyBeginVC;
+    vcEnd = gWriteReplyEndVC;
+  }
+  assert(((f->vc >= vcBegin) && (f->vc <= vcEnd)) || (inject && (f->vc < 0)));
+
+  int out_port;
+
+  if(inject) {
+
+    out_port = -1;
+
+  } else {
+
+    int dest  = flatfly_transformation(f->dest);
+
+    int rID =  r->GetID();
+    int _concentration = gC;
+    int found;
+    int debug = 0;
+    int tmp_out_port, _ran_intm;
+    int _min_hop, _nonmin_hop, _min_queucnt, _nonmin_queucnt;
+    int threshold = 2;
+
+    if ( in_channel < gC ){
+      if(gTrace){
+	cout<<"New Flit "<<f->src<<endl;
+      }
+      f->ph   = 0;
+    }
+
+    if(gTrace){
+      int load = 0;
+      cout<<"Router "<<rID<<endl;
+      cout<<"Input Channel "<<in_channel<<endl;
+      //need to modify router to report the buffere depth
+      load +=r->GetBufferOccupancy(in_channel);
+      cout<<"Rload "<<load<<endl;
+    }
+
+    if (debug){
+      cout << " FLIT ID: " << f->id << " Router: " << rID << " routing from src : " << f->src <<  " to dest : " << dest << " f->ph: " <<f->ph << " intm: " << f->intm <<  endl;
+    }
+    // f->ph == 0  ==> make initial global adaptive decision
+    // f->ph == 1  ==> route nonminimaly to random intermediate node
+    // f->ph == 2  ==> route minimally to destination
+
+    found = 0;
+
+    if (f->ph == 1){
+      dest = f->intm;
+    }
+
+
+    if (dest >= rID*_concentration && dest < (rID+1)*_concentration) {
+
+      if (f->ph == 1) {
+	f->ph = 2;
+	dest = flatfly_transformation(f->dest);
+	if (debug)   cout << "      done routing to intermediate ";
+      }
+      else  {
+	found = 1;
+	out_port = dest % gC;
+	if (debug)   cout << "      final routing to destination ";
+      }
+    }
+
+    if (!found) {
+
+      if (f->ph == 0) {
+	_min_hop = find_distance(flatfly_transformation(f->src),dest);
+	_ran_intm = find_ran_intm(flatfly_transformation(f->src), dest);
+	tmp_out_port =  flatfly_outport(dest, rID);
+	if (f->watch){
+	  *gWatchOut << GetSimTime() << " | " << r->FullName() << " | "
+		     << " MIN tmp_out_port: " << tmp_out_port;
+	}
+
+	_min_queucnt =   r->GetUsedCredit(tmp_out_port);
+
+	_nonmin_hop = find_distance(flatfly_transformation(f->src),_ran_intm) +    find_distance(_ran_intm, dest);
+	tmp_out_port =  flatfly_outport(_ran_intm, rID);
+
+	if (f->watch){
+	  *gWatchOut << GetSimTime() << " | " << r->FullName() << " | "
+		     << " NONMIN tmp_out_port: " << tmp_out_port << endl;
+	}
+	if (_ran_intm >= rID*_concentration && _ran_intm < (rID+1)*_concentration) {
+	  _nonmin_queucnt = numeric_limits<int>::max();
+	} else  {
+	  _nonmin_queucnt =   r->GetUsedCredit(tmp_out_port);
+	}
+
+	if (debug){
+	  cout << " _min_hop " << _min_hop << " _min_queucnt: " <<_min_queucnt << " _nonmin_hop: " << _nonmin_hop << " _nonmin_queucnt :" << _nonmin_queucnt <<  endl;
+	}
+
+	if (_min_hop * _min_queucnt   <= _nonmin_hop * _nonmin_queucnt +threshold) {
+
+	  if (debug) cout << " Route MINIMALLY " << endl;
+	  f->ph = 2;
+	} else {
+	  // route non-minimally
+	  if (debug)  { cout << " Route NONMINIMALLY int node: " <<_ran_intm << endl; }
+	  f->ph = 1;
+	  f->intm = _ran_intm;
+	  dest = f->intm;
+	  if (dest >= rID*_concentration && dest < (rID+1)*_concentration) {
+	    f->ph = 2;
+	    dest = flatfly_transformation(f->dest);
+	  }
+	}
+      }
+
+      // find minimal correct dimension to route through
+      out_port =  flatfly_outport(dest, rID);
+
+      // if we haven't reached our destination, restrict VCs appropriately to avoid routing deadlock
+      if(out_port >= gC) {
+	int const available_vcs = (vcEnd - vcBegin + 1) / 2;
+	assert(available_vcs > 0);
+	if(f->ph == 1) {
+	  vcEnd -= available_vcs;
+	} else {
+	  assert(f->ph == 2);
+	  vcBegin += available_vcs;
+	}
+      }
+
+      found = 1;
+    }
+
+    if (!found) {
+      cout << " ERROR: output not found in routing. " << endl;
+      cout << *f; exit (-1);
+    }
+
+    if (out_port >= gN*(gK-1) + gC)  {
+      cout << " ERROR: output port too big! " << endl;
+      cout << " OUTPUT select: " << out_port << endl;
+      cout << " router radix: " <<  gN*(gK-1) + gK << endl;
+      exit (-1);
+    }
+
+    if (debug) cout << "        through output port : " << out_port << endl;
+    if(gTrace) {
+      cout<<"Outport "<<out_port<<endl;
+      cout<<"Stop Mark"<<endl;
+    }
+  }
+
+  outputs->Clear( );
+
+  outputs->AddRange( out_port , vcBegin, vcEnd );
+}
+
+
+// partially non-interfering (i.e., packets ordered by hash of destination) UGAL
+void ugal_pni_flatfly_onchip( const Router *r, const Flit *f, int in_channel,
+			      OutputSet *outputs, bool inject )
+{
+  // ( Traffic Class , Routing Order ) -> Virtual Channel Range
+  int vcBegin = 0, vcEnd = gNumVCs-1;
+  if ( f->type == Flit::READ_REQUEST ) {
+    vcBegin = gReadReqBeginVC;
+    vcEnd = gReadReqEndVC;
+  } else if ( f->type == Flit::WRITE_REQUEST ) {
+    vcBegin = gWriteReqBeginVC;
+    vcEnd = gWriteReqEndVC;
+  } else if ( f->type ==  Flit::READ_REPLY ) {
+    vcBegin = gReadReplyBeginVC;
+    vcEnd = gReadReplyEndVC;
+  } else if ( f->type ==  Flit::WRITE_REPLY ) {
+    vcBegin = gWriteReplyBeginVC;
+    vcEnd = gWriteReplyEndVC;
+  }
+  assert(((f->vc >= vcBegin) && (f->vc <= vcEnd)) || (inject && (f->vc < 0)));
+
+  int out_port;
+
+  if(inject) {
+    
+    out_port = -1;
+
+  } else {
+
+    int dest  = flatfly_transformation(f->dest);
+
+    int rID =  r->GetID();
+    int _concentration = gC;
+    int found;
+    int debug = 0;
+    int tmp_out_port, _ran_intm;
+    int _min_hop, _nonmin_hop, _min_queucnt, _nonmin_queucnt;
+    int threshold = 2;
+
+    if ( in_channel < gC ){
+      if(gTrace){
+	cout<<"New Flit "<<f->src<<endl;
+      }
+      f->ph   = 0;
+    }
+
+    if(gTrace){
+      int load = 0;
+      cout<<"Router "<<rID<<endl;
+      cout<<"Input Channel "<<in_channel<<endl;
+      //need to modify router to report the buffere depth
+      load +=r->GetBufferOccupancy(in_channel);
+      cout<<"Rload "<<load<<endl;
+    }
+
+    if (debug){
+      cout << " FLIT ID: " << f->id << " Router: " << rID << " routing from src : " << f->src <<  " to dest : " << dest << " f->ph: " <<f->ph << " intm: " << f->intm <<  endl;
+    }
+    // f->ph == 0  ==> make initial global adaptive decision
+    // f->ph == 1  ==> route nonminimaly to random intermediate node
+    // f->ph == 2  ==> route minimally to destination
+
+    found = 0;
+
+    if (f->ph == 1){
+      dest = f->intm;
+    }
+
+
+    if (dest >= rID*_concentration && dest < (rID+1)*_concentration) {
+
+      if (f->ph == 1) {
+	f->ph = 2;
+	dest = flatfly_transformation(f->dest);
+	if (debug)   cout << "      done routing to intermediate ";
+      }
+      else  {
+	found = 1;
+	out_port = dest % gC;
+	if (debug)   cout << "      final routing to destination ";
+      }
+    }
+
+    if (!found) {
+
+      if (f->ph == 0) {
+	_min_hop = find_distance(flatfly_transformation(f->src),dest);
+	_ran_intm = find_ran_intm(flatfly_transformation(f->src), dest);
+	tmp_out_port =  flatfly_outport(dest, rID);
+	if (f->watch){
+	  *gWatchOut << GetSimTime() << " | " << r->FullName() << " | "
+		     << " MIN tmp_out_port: " << tmp_out_port;
+	}
+
+	_min_queucnt =   r->GetUsedCredit(tmp_out_port);
+
+	_nonmin_hop = find_distance(flatfly_transformation(f->src),_ran_intm) +    find_distance(_ran_intm, dest);
+	tmp_out_port =  flatfly_outport(_ran_intm, rID);
+
+	if (f->watch){
+	  *gWatchOut << GetSimTime() << " | " << r->FullName() << " | "
+		     << " NONMIN tmp_out_port: " << tmp_out_port << endl;
+	}
+	if (_ran_intm >= rID*_concentration && _ran_intm < (rID+1)*_concentration) {
+	  _nonmin_queucnt = numeric_limits<int>::max();
+	} else  {
+	  _nonmin_queucnt =   r->GetUsedCredit(tmp_out_port);
+	}
+
+	if (debug){
+	  cout << " _min_hop " << _min_hop << " _min_queucnt: " <<_min_queucnt << " _nonmin_hop: " << _nonmin_hop << " _nonmin_queucnt :" << _nonmin_queucnt <<  endl;
+	}
+
+	if (_min_hop * _min_queucnt   <= _nonmin_hop * _nonmin_queucnt +threshold) {
+
+	  if (debug) cout << " Route MINIMALLY " << endl;
+	  f->ph = 2;
+	} else {
+	  // route non-minimally
+	  if (debug)  { cout << " Route NONMINIMALLY int node: " <<_ran_intm << endl; }
+	  f->ph = 1;
+	  f->intm = _ran_intm;
+	  dest = f->intm;
+	  if (dest >= rID*_concentration && dest < (rID+1)*_concentration) {
+	    f->ph = 2;
+	    dest = flatfly_transformation(f->dest);
+	  }
+	}
+      }
+
+      // find minimal correct dimension to route through
+      out_port =  flatfly_outport(dest, rID);
+
+      // if we haven't reached our destination, restrict VCs appropriately to avoid routing deadlock
+      if(out_port >= gC) {
+	int const available_vcs = (vcEnd - vcBegin + 1) / 2;
+	assert(available_vcs > 0);
+	if(f->ph == 1) {
+	  vcEnd -= available_vcs;
+	} else {
+	  assert(f->ph == 2);
+	  vcBegin += available_vcs;
+	}
+      }
+
+      found = 1;
+    }
+
+    if (!found) {
+      cout << " ERROR: output not found in routing. " << endl;
+      cout << *f; exit (-1);
+    }
+
+    if (out_port >= gN*(gK-1) + gC)  {
+      cout << " ERROR: output port too big! " << endl;
+      cout << " OUTPUT select: " << out_port << endl;
+      cout << " router radix: " <<  gN*(gK-1) + gK << endl;
+      exit (-1);
+    }
+
+    if (debug) cout << "        through output port : " << out_port << endl;
+    if(gTrace) {
+      cout<<"Outport "<<out_port<<endl;
+      cout<<"Stop Mark"<<endl;
+    }
+  }
+
+  if(inject || (out_port >= gC)) {
+
+    // NOTE: for "proper" flattened butterfly configurations (i.e., ones 
+    // derived from flattening an actual butterfly), gK and gC are the same!
+    assert(gK == gC);
+
+    assert(inject ? (f->ph == -1) : (f->ph == 1 || f->ph == 2));
+
+    int next_coord = flatfly_transformation(f->dest);
+    if(inject) {
+      next_coord /= gC;
+      next_coord %= gK;
+    } else {
+      int next_dim = (out_port - gC) / (gK - 1) + 1;
+      if(next_dim == gN) {
+	next_coord %= gC;
+      } else {
+	next_coord /= gC;
+	for(int d = 0; d < next_dim; ++d) {
+	  next_coord /= gK;
+	}
+	next_coord %= gK;
+      }
+    }
+    assert(next_coord >= 0 && next_coord < gK);
+    int vcs_per_dest = (vcEnd - vcBegin + 1) / gK;
+    assert(vcs_per_dest > 0);
+    vcBegin += next_coord * vcs_per_dest;
+    vcEnd = vcBegin + vcs_per_dest - 1;
+  }
+
+  outputs->Clear( );
+
+  outputs->AddRange( out_port , vcBegin, vcEnd );
+}
+
+
+//=============================================================^M
+// UGAL : calculate distance (hop cnt)  between src and destination
+//=============================================================^M
+int find_distance (int src, int dest) {
+  int dist = 0;
+  int _dim   = gN;
+  int _dim_size;
+  
+  int src_tmp= (int) src / gC;
+  int dest_tmp = (int) dest / gC;
+  int src_id, dest_id;
+  
+  //  cout << " HOP CNT between  src: " << src << " dest: " << dest;
+  for (int d=0;d < _dim; d++) {
+    _dim_size = powi(gK, d )*gC;
+    //if ((int)(src / _dim_size) !=  (int)(dest / _dim_size))
+    //   dist++;
+    src_id = src_tmp % gK;
+    dest_id = dest_tmp % gK;
+    if (src_id !=  dest_id)
+      dist++;
+    src_tmp = (int) (src_tmp / gK);
+    dest_tmp = (int) (dest_tmp / gK);
+  }
+  
+  //  cout << " : " << dist << endl;
+  
+  return dist;
+}
+
+//=============================================================^M
+// UGAL : find random node for load balancing
+//=============================================================^M
+int find_ran_intm (int src, int dest) {
+  int _dim   = gN;
+  int _dim_size;
+  int _ran_dest = 0;
+  int debug = 0;
+  
+  if (debug) 
+    cout << " INTM node for  src: " << src << " dest: " <<dest << endl;
+  
+  src = (int) (src / gC);
+  dest = (int) (dest / gC);
+  
+  _ran_dest = RandomInt(gC - 1);
+  if (debug) cout << " ............ _ran_dest : " << _ran_dest << endl;
+  for (int d=0;d < _dim; d++) {
+    
+    _dim_size = powi(gK, d)*gC;
+    if ((src % gK) ==  (dest % gK)) {
+      _ran_dest += (src % gK) * _dim_size;
+      if (debug) 
+	cout << "    share same dimension : " << d << " int node : " << _ran_dest << " src ID : " << src % gK << endl;
+    } else {
+      // src and dest are in the same dimension "d" + 1
+      // ==> thus generate a random destination within
+      _ran_dest += RandomInt(gK - 1) * _dim_size;
+      if (debug) 
+	cout << "    different  dimension : " << d << " int node : " << _ran_dest << " _dim_size: " << _dim_size << endl;
+    }
+    src = (int) (src / gK);
+    dest = (int) (dest / gK);
+  }
+  
+  if (debug) cout << " intermediate destination NODE: " << _ran_dest << endl;
+  return _ran_dest;
+}
+
+
+
+//=============================================================
+// UGAL : calculated minimum distance output port for flatfly
+// given the dimension and destination
+//=============================================================
+// starting from DIM 0 (x first)
+int flatfly_outport(int dest, int rID) {
+  int dest_rID = (int) (dest / gC);
+  int _dim   = gN;
+  int output = -1, dID, sID;
+  
+  if(dest_rID==rID){
+    return dest % gC;
+  }
+
+
+  for (int d=0;d < _dim; d++) {
+    dID = (dest_rID % gK);
+    sID = (rID % gK);
+    if ( dID != sID ) {
+      output = gC + ((gK-1)*d) - 1;
+      if (dID > sID) {
+
+	output += dID;
+      } else {
+	output += dID + 1;
+      }
+      
+      return output;
+    }
+    dest_rID = (int) (dest_rID / gK);
+    rID      = (int) (rID / gK);
+  }
+  if (output == -1) {
+    cout << " ERROR ---- FLATFLY_OUTPORT function : output not found " << endl;
+    exit(-1);
+  }
+  return -1;
+}
+
+int flatfly_transformation(int dest){
+  //the magic of destination transformation
+
+  //destination transformation, translate how the nodes are actually arranged
+  //to the easier way of routing
+  //this transformation only support 64 nodes
+
+  //cout<<"ORiginal destination "<<dest<<endl;
+  //router in the x direction = find which column, and then mod by cY to find 
+  //which horizontal router
+  int horizontal = (dest%(_xcount*_xrouter))/(_xrouter);
+  int horizontal_rem = (dest%(_xcount*_xrouter))%(_xrouter);
+  //router in the y direction = find which row, and then divided by cX to find 
+  //vertical router
+  int vertical = (dest/(_xcount*_xrouter))/(_yrouter);
+  int vertical_rem = (dest/(_xcount*_xrouter))%(_yrouter);
+  //transform the destination to as if node0 was 0,1,2,3 and so forth
+  dest = (vertical*_xcount + horizontal)*gC+_xrouter*vertical_rem+horizontal_rem;
+  //cout<<"Transformed destination "<<dest<<endl<<endl;
+  return dest;
+}