1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
#include "booksim.hpp"
#include <vector>
#include <sstream>
#include "fly.hpp"
#include "misc_utils.hpp"
//#define DEBUG_FLY
KNFly::KNFly( const Configuration &config ) :
Network( config )
{
_ComputeSize( config );
_Alloc( );
_BuildNet( config );
}
void KNFly::_ComputeSize( const Configuration &config )
{
_k = config.GetInt( "k" );
_n = config.GetInt( "n" );
gK = _k; gN = _n;
_sources = powi( _k, _n );
_dests = powi( _k, _n );
// n stages of k^(n-1) k x k switches
_size = _n*powi( _k, _n-1 );
// n-1 sets of wiring between the stages
_channels = (_n-1)*_sources;
}
void KNFly::_BuildNet( const Configuration &config )
{
ostringstream router_name;
int per_stage = powi( _k, _n-1 );
int node = 0;
int c;
for ( int stage = 0; stage < _n; ++stage ) {
for ( int addr = 0; addr < per_stage; ++addr ) {
router_name << "router_" << stage << "_" << addr;
_routers[node] = Router::NewRouter( config, this, router_name.str( ),
node, _k, _k );
router_name.seekp( 0, ios::beg );
#ifdef DEBUG_FLY
cout << "connecting node " << node << " to:" << endl;
#endif
for ( int port = 0; port < _k; ++port ) {
// Input connections
if ( stage == 0 ) {
c = addr*_k + port;
_routers[node]->AddInputChannel( &_inject[c], &_inject_cred[c] );
#ifdef DEBUG_FLY
cout << " injection channel " << c << endl;
#endif
} else {
c = _InChannel( stage, addr, port );
_routers[node]->AddInputChannel( &_chan[c], &_chan_cred[c] );
#ifdef DEBUG_FLY
cout << " input channel " << c << endl;
#endif
}
// Output connections
if ( stage == _n - 1 ) {
c = addr*_k + port;
_routers[node]->AddOutputChannel( &_eject[c], &_eject_cred[c] );
#ifdef DEBUG_FLY
cout << " ejection channel " << c << endl;
#endif
} else {
c = _OutChannel( stage, addr, port );
_routers[node]->AddOutputChannel( &_chan[c], &_chan_cred[c] );
#ifdef DEBUG_FLY
cout << " output channel " << c << endl;
#endif
}
}
++node;
}
}
}
int KNFly::_OutChannel( int stage, int addr, int port ) const
{
return stage*_sources + addr*_k + port;
}
int KNFly::_InChannel( int stage, int addr, int port ) const
{
int in_addr;
int in_port;
// Channels are between {node,port}
// { d_{n-1} ... d_{n-stage} ... d_0 } and
// { d_{n-1} ... d_0 ... d_{n-stage} }
int shift = powi( _k, _n-stage-1 );
int last_digit = port;
int zero_digit = ( addr / shift ) % _k;
// swap zero and last digit to get first node's address
in_addr = addr - zero_digit*shift + last_digit*shift;
in_port = zero_digit;
return(stage-1)*_sources + in_addr*_k + in_port;
}
int KNFly::GetN( ) const
{
return _n;
}
int KNFly::GetK( ) const
{
return _k;
}
double KNFly::Capacity( ) const
{
return 1.0;
}
|
