text: // $Id$
  
  /*
   Copyright (c) 2007-2015, 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.
  */
  
  ////////////////////////////////////////////////////////////////////////
  //
  // FatTree
  //
  //       Each level of the hierarchical indirect Network has
  //       k^(n-1) Routers. The Routers are organized such that 
  //       each node has k descendents, and each parent is
  //       replicated k  times.
  //      most routers has 2K ports, excep the top level has only K
  ////////////////////////////////////////////////////////////////////////
  //
  // RCS Information:
  //  $Author: jbalfour $
  //  $Date: 2007/06/26 22:50:48 $
  //  $Id$
  // 
  ////////////////////////////////////////////////////////////////////////
  
  
  #include "booksim.hpp"
  #include <vector>
  #include <sstream>
  #include <cmath>
  
  #include "fattree.hpp"
  #include "misc_utils.hpp"
  
  
   //#define FATTREE_DEBUG
  
  FatTree::FatTree( const Configuration& config,const string & name )
    : Network( config ,name)
  {
    
  
    _ComputeSize( config );
    _Alloc( config );
    _BuildNet( config );
  
  }
  
  void FatTree::_ComputeSize( const Configuration& config )
  {
  
    _k = config.GetInt( "k" );
    _n = config.GetInt( "n" );
     
    gK = _k; gN = _n;
    
    _nodes = powi( _k, _n );
  
    //levels * routers_per_level
    _size = _n * powi( _k , _n - 1 );
  
    //(channels per level = k*routers_per_level* up/down) * (levels-1)
    _channels = (2*_k * powi( _k , _n-1 ))*(_n-1); 
    
  
  }
  
  
  void FatTree::RegisterRoutingFunctions() {
  
  }
  
  void FatTree::_BuildNet( const Configuration& config )
  {
   cout << "Fat Tree" << endl;
    cout << " k = " << _k << " levels = " << _n << endl;
    cout << " each switch - total radix =  "<< 2*_k << endl;
    cout << " # of switches = "<<  _size << endl;
    cout << " # of channels = "<<  _channels << endl;
    cout << " # of nodes ( size of network ) = " << _nodes << endl;
  
  
    // Number of router positions at each depth of the network
    const int nPos = powi( _k, _n-1);
  
    //
    // Allocate Routers
    //
    ostringstream name;
    int level, pos, id, degree, port;
    for ( level = 0 ; level < _n ; ++level ) {
      for ( pos = 0 ; pos < nPos ; ++pos ) {
        
        if ( level == 0 ) //top routers is zero
  	degree = _k;
        else
  	degree = 2 * _k;
  
        id = level * nPos + pos;
  
        name.str("");
        name << "router_level" << level << "_" << pos;
        Router * r = Router::NewRouter( config, this, name.str( ), id,
  				      degree, degree );
        _Router( level, pos ) = r;
        _timed_modules.push_back(r);
      }
    }
  
    //
    // Connect Channels to Routers
    //
  
    //
    // Router Connection Rule: Output Ports <gK Move DOWN Network
    //                         Output Ports >=gK Move UP Network
    //                         Input Ports <gK from DOWN Network
    //                         Input Ports >=gK  from up Network
  
    // Connecting  Injection & Ejection Channels  
    for ( pos = 0 ; pos < nPos ; ++pos ) {
      for(int index = 0; index<_k; index++){
        int link = pos*_k + index;
        _Router( _n-1, pos)->AddInputChannel( _inject[link],
  					    _inject_cred[link]);
        _Router( _n-1, pos)->AddOutputChannel( _eject[link],
  					     _eject_cred[link]);
        _inject[link]->SetLatency( 1 );
        _inject_cred[link]->SetLatency( 1 );
        _eject[link]->SetLatency( 1 );
        _eject_cred[link]->SetLatency( 1 );
      }
    }
  
  #ifdef FATTREE_DEBUG
    cout<<"\nAssigning output\n";
  #endif
  
    //channels are numbered sequentially from an output channel perspective
    int chan_per_direction = (_k * powi( _k , _n-1 )); //up or down
    int chan_per_level = 2*(_k * powi( _k , _n-1 )); //up+down
  
    //connect all down output channels
    //level n-1's down channel are injection channels
    for (level = 0; level<_n-1; level++){
      for ( pos = 0; pos < nPos; ++pos ) {
        for ( port = 0; port < _k; ++port ) {
  	int link = (level*chan_per_level) + pos*_k + port;
  	_Router(level, pos)->AddOutputChannel( _chan[link],
  						_chan_cred[link] );
  	_chan[link]->SetLatency( 1 );
  	_chan_cred[link]->SetLatency( 1 ); 
  #ifdef FATTREE_DEBUG
  	cout<<_Router(level, pos)->Name()<<" "
  	    <<"down output "<<port<<" "
  	    <<"channel_id "<<link<<endl;
  #endif
  
        }
      }
    }
    //connect all up output channels
    //level 0 has no up chnanels
    for (level = 1; level<_n; level++){
      for ( pos = 0; pos < nPos; ++pos ) {
        for ( port = 0; port < _k; ++port ) {
  	int link = (level*chan_per_level - chan_per_direction) + pos*_k + port ;
  	_Router(level, pos)->AddOutputChannel( _chan[link],
  						_chan_cred[link] );
  	_chan[link]->SetLatency( 1 );
  	_chan_cred[link]->SetLatency( 1 ); 
  #ifdef FATTREE_DEBUG
  	cout<<_Router(level, pos)->Name()<<" "
  	    <<"up output "<<port<<" "
  	    <<"channel_id "<<link<<endl;
  #endif
        }
      }
    }
  
  #ifdef FATTREE_DEBUG
    cout<<"\nAssigning Input\n";
  #endif
  
    //connect all down input channels
    for (level = 0; level<_n-1; level++){
      //input channel are numbered interleavely, the interleaev depends on level
      int routers_per_neighborhood = powi(_k,_n-1-(level)); 
      int routers_per_branch = powi(_k,_n-1-(level+1)); 
      int level_offset = routers_per_neighborhood*_k;
      for ( pos = 0; pos < nPos; ++pos ) {
        int neighborhood = pos/routers_per_neighborhood;
        int neighborhood_pos = pos%routers_per_neighborhood;
        for ( port = 0; port < _k; ++port ) {
  	int link = 
  	  ((level+1)*chan_per_level - chan_per_direction)  //which levellevel
  	  +neighborhood*level_offset   //region in level
  	  +port*routers_per_branch*gK  //sub region in region
  	  +(neighborhood_pos)%routers_per_branch*gK  //router in subregion
  	  +(neighborhood_pos)/routers_per_branch; //port on router
  
  	_Router(level, pos)->AddInputChannel( _chan[link],
  					      _chan_cred[link] );
  #ifdef FATTREE_DEBUG
  	cout<<_Router(level, pos)->Name()<<" "
  	    <<"down input "<<port<<" "
  	    <<"channel_id "<<link<<endl;
  #endif
        }
      }
    }
  
  
   //connect all up input channels
    for (level = 1; level<_n; level++){
      //input channel are numbered interleavely, the interleaev depends on level
      int routers_per_neighborhood = powi(_k,_n-1-(level-1)); 
      int routers_per_branch = powi(_k,_n-1-(level)); 
      int level_offset = routers_per_neighborhood*_k;
      for ( pos = 0; pos < nPos; ++pos ) {
        int neighborhood = pos/routers_per_neighborhood;
        int neighborhood_pos = pos%routers_per_neighborhood;
        for ( port = 0; port < _k; ++port ) {
  	int link = 
  	  ((level-1)*chan_per_level) //which levellevel
  	  +neighborhood*level_offset   //region in level
  	  +port*routers_per_branch*gK  //sub region in region
  	  +(neighborhood_pos)%routers_per_branch*gK //router in subregion
  	  +(neighborhood_pos)/routers_per_branch; //port on router
  
  	_Router(level, pos)->AddInputChannel( _chan[link],
  					      _chan_cred[link] );
  #ifdef FATTREE_DEBUG
  	cout<<_Router(level, pos)->Name()<<" "
  	    <<"up input "<<port<<" "
  	    <<"channel_id "<<link<<endl;
  #endif
        }
      }
    }
  #ifdef FATTREE_DEBUG
    cout<<"\nChannel assigned\n";
  #endif
  }
  
  Router*& FatTree::_Router( int depth, int pos ) 
  {
    assert( depth < _n && pos < powi( _k, _n-1) );
    return _routers[depth * powi( _k, _n-1) + pos];
  }
  