text: // $Id: tree4.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.
  */
  
  ////////////////////////////////////////////////////////////////////////
  //
  // Tree4: Network with 64 Terminal Nodes arranged in a tree topology
  //        with 4 routers at the root of the tree
  // 
  //  Level 0 :  4  8 x 8 Routers   (8 Descending Links per Router)
  //  Level 1 :  8  8 x 8 Routers   (4 Descending Links per Router)
  //  Level 2 : 16  6 x 6 Routers   (4 Descending Links per Router)
  //  Level 3 : 64  Terminal Nodes
  //
  ////////////////////////////////////////////////////////////////////////
  //
  // RCS Information:
  //  $Author: jbalfour $
  //  $Date: 2007/06/26 22:49:23 $
  //  $Id: tree4.cpp 5188 2012-08-30 00:31:31Z dub $
  // 
  ////////////////////////////////////////////////////////////////////////
  
  #include <vector>
  #include <sstream>
  #include <cmath>
  
  #include "intersim2/booksim.hpp"
  #include "intersim2/misc_utils.hpp"
  #include "tree4.hpp"
  
  Tree4::Tree4( const Configuration& config, const string & name )
  : ISNetwork ( config, name )
  {
    _ComputeSize( config );
    _Alloc( );
    _BuildNet( config );
  }
  
  void Tree4::_ComputeSize( const Configuration& config )
  {
    int h;
  
    _k = config.GetInt( "k" );
    assert(_k == 4);
    _n = config.GetInt( "n" );
    assert(_n == 3);
    
    gK = _k; gN = _n;
    
    _nodes = powi( _k, _n );
    
    _size = 0;
    for ( h = 0; h < _n; ++h ) 
      _size += (4 >> h) * powi( _k, h );
  
    _channels = 2                  // Two Channels per Connection
      * ( 2 * powi( _k, 1) )       // Number of Middle Routers
      * ( 2 * _k );                // Connectivity of Middle Routers
  }
  
  void Tree4::RegisterRoutingFunctions(){
  
  }
  
  void Tree4::_BuildNet( const Configuration& config )
  {
  
    //
    // Allocate Routers
    //
    ostringstream name;
    int h, pos, nPos, degree, id;
  
    for ( h = 0; h < _n; h++ ) {
      nPos = (4 >> h) * powi( _k, h );
      for ( pos = 0; pos < nPos; ++pos) {
        if ( h < _n-1 ) 
  	degree = 8;
        else
  	degree = 6;
        
        name.str("");
        name << "router_" << h << "_" << pos;
        id = h * powi( _k, _n-1 ) + pos;
        Router * r = Router::NewRouter( config, this, name.str( ),
  				      id, degree, degree );
        _Router( h, pos ) = r;
        _timed_modules.push_back(r);
      }
    }
  
    //
    // Connect Channels to Routers
    //
    int pp, pc;
    //
    // Connection Rule: Output Ports 0:3 Move DOWN Network
    //                  Output Ports 4:7 Move UP Network
    //
    
    // Injection & Ejection Channels
    nPos = powi( _k, _n - 1 );
    for ( pos = 0 ; pos < nPos ; ++pos ) {
      for ( int port = 0 ; port < _k ; ++port ) {
        
        _Router( _n-1, pos)->AddInputChannel( _inject[_k*pos+port],
  					    _inject_cred[_k*pos+port]);
        
  
        _inject[_k*pos+port]->SetLatency( 1 );
        _inject_cred[_k*pos+port]->SetLatency( 1 );
  
        _Router( _n-1, pos)->AddOutputChannel( _eject[_k*pos+port],
  					     _eject_cred[_k*pos+port]);
  
        _eject[_k*pos+port]->SetLatency( 1 );
        _eject_cred[_k*pos+port]->SetLatency( 1 );
  
      }
    }
  
    // Connections between h = 1 and h = 2 Levels
    int c = 0;
    nPos = 2 * powi( _k, 1 );
    for ( pos = 0; pos < nPos; ++pos ) {
      for ( int port = 0; port < _k; ++port ) {
  
        pp = pos;
        pc = _k * ( pos / 2 ) + port;
        
        // cout << "connecting (1,"<<pp<<") <-> (2,"<<pc<<")"<<endl;
  
        _Router( 1, pp)->AddOutputChannel( _chan[c], _chan_cred[c] );
        _Router( 2, pc)->AddInputChannel(  _chan[c], _chan_cred[c] );
  
        //_chan[c]->SetLatency( L );
        //_chan_cred[c]->SetLatency( L );
  
        _chan[c]->SetLatency( 1 );
        _chan_cred[c]->SetLatency( 1 );
  
        c++;
  
        _Router(1, pp)->AddInputChannel( _chan[c], _chan_cred[c] );
        _Router(2, pc)->AddOutputChannel( _chan[c], _chan_cred[c] );
        
        //_chan[c]->SetLatency( L );
        //_chan_cred[c]->SetLatency( L );
        _chan[c]->SetLatency( 1 );
        _chan_cred[c]->SetLatency( 1 );
  
        c++;
      }
    }
  
    // Connections between h = 0 and h = 1 Levels
    nPos = 4 * powi( _k, 0 );
    for ( pos  = 0; pos < nPos; ++pos ) {
      for ( int port = 0; port < 2 * _k; ++port ) {
        pp = pos;
        pc = port;
  
        // cout << "connecting (0,"<<pp<<") <-> (1,"<<pc<<")"<<endl;
  
        _Router(0, pp)->AddOutputChannel( _chan[c], _chan_cred[c] );
        _Router(1, pc)->AddInputChannel( _chan[c], _chan_cred[c] );
  
        //      _chan[c]->SetLatency( L );
        //_chan_cred[c]->SetLatency( L );
        _chan[c]->SetLatency( 1 );
        _chan_cred[c]->SetLatency( 1 );
  
        c++;
  
        _Router(0, pp)->AddInputChannel( _chan[c], _chan_cred[c] );
        _Router(1, pc)->AddOutputChannel( _chan[c], _chan_cred[c] );
  
        //  _chan[c]->SetLatency( L );
        // _chan_cred[c]->SetLatency( L );
        _chan[c]->SetLatency( 1 );
        _chan_cred[c]->SetLatency( 1 );
        c++;
      }
    }
  
    // cout << "Used " << c << " of " << _channels << " channels" << endl;
  
  }
    
  Router*& Tree4::_Router( int height, int pos )
  {
    assert( height < _n );
    assert( pos < (4 >> height) * powi( _k, height) );
  
    int i = 0;
    for ( int h = 0; h < height; ++h )
      i += (4 >> h) * powi( _k, h );
    return _routers[i+pos];
  
  }
    
  int Tree4::_WireLatency( int height1, int pos1, int height2, int pos2 )
  {
    int heightChild, heightParent, posChild, posParent;
  
    int L;
  
    if (height1 < height2) {
      heightChild  = height2;
      posChild     = pos2;
      heightParent = height1;
      posParent    = pos1;
    } else {
      heightChild  = height1;
      posChild     = pos1;
      heightParent = height2;
      posParent    = pos2;
    }
  
    int _length_d2_d1   = 2 ;
    int _length_d1_d0_0 = 2 ;
    int _length_d1_d0_1 = 2 ;
    int _length_d1_d0_2 = 6 ;
    int _length_d1_d0_3 = 6 ;
  
    assert( heightChild == heightParent+1 );
  
    // We must decrement the delays by one to account for how the 
    //  simulator interprets the specified delay (with 0 indicating one
    //  cycle of delay).
  
    if ( heightChild == 2 ) 
      L = _length_d2_d1;
    else {
         if ( posChild == 0 || posChild == 6 )
        switch ( posParent ) {
        case 0: L =_length_d1_d0_0; break;
        case 1: L =_length_d1_d0_1; break;
        case 2: L =_length_d1_d0_2; break;
        case 3: L =_length_d1_d0_3; break;
        }
      if ( posChild == 1 || posChild == 7 )
        switch ( posParent ) {
        case 0: L =_length_d1_d0_3; break;
        case 1: L =_length_d1_d0_2; break;
        case 2: L =_length_d1_d0_1; break;
        case 3: L =_length_d1_d0_0; break;
        }
      if ( posChild == 2 || posChild == 4 )
        switch ( posParent ) {
        case 0: L = _length_d1_d0_0; break;
        case 1: L = _length_d1_d0_1; break;
        case 2: L = _length_d1_d0_2; break;
        case 3: L = _length_d1_d0_3; break;
        }
      if ( posChild == 3|| posChild == 5 )
        switch ( posParent ) {
        case 0: L =_length_d1_d0_3; break;
        case 1: L =_length_d1_d0_2; break;
        case 2: L =_length_d1_d0_1; break;
        case 3: L =_length_d1_d0_0; break;
        }
    }
    return L;
  }
  