summaryrefslogtreecommitdiff
path: root/src/intersim2/networks/fattree.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/intersim2/networks/fattree.cpp')
-rw-r--r--src/intersim2/networks/fattree.cpp270
1 files changed, 270 insertions, 0 deletions
diff --git a/src/intersim2/networks/fattree.cpp b/src/intersim2/networks/fattree.cpp
new file mode 100644
index 0000000..81cd2b1
--- /dev/null
+++ b/src/intersim2/networks/fattree.cpp
@@ -0,0 +1,270 @@
+// $Id: fattree.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.
+*/
+
+////////////////////////////////////////////////////////////////////////
+//
+// 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: fattree.cpp 5188 2012-08-30 00:31:31Z dub $
+//
+////////////////////////////////////////////////////////////////////////
+
+
+#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( );
+ _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];
+}
generated by cgit v1.3 (git 2.53.0) at 2026-07-11 01:20:38 +0000