From 69f2911e04ffb1b19eef1fafb8c040af271f656e Mon Sep 17 00:00:00 2001 From: Tor Aamodt Date: Thu, 15 Jul 2010 18:09:46 -0800 Subject: creating branch for adding support for CUDA 3.x and Fermi [git-p4: depot-paths = "//depot/gpgpu_sim_research/fermi/distribution/": change = 6829] --- src/intersim/iq_router.cpp | 633 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 633 insertions(+) create mode 100644 src/intersim/iq_router.cpp (limited to 'src/intersim/iq_router.cpp') diff --git a/src/intersim/iq_router.cpp b/src/intersim/iq_router.cpp new file mode 100644 index 0000000..137c0bb --- /dev/null +++ b/src/intersim/iq_router.cpp @@ -0,0 +1,633 @@ +#include +#include +#include +#include +#include + +#include "iq_router.hpp" + +IQRouter::IQRouter( const Configuration& config, + Module *parent, string name, int id, + int inputs, int outputs ) +: Router( config, + parent, name, + id, + inputs, outputs ) +{ + string alloc_type; + ostringstream vc_name; + + _vcs = config.GetInt( "num_vcs" ); + _vc_size = config.GetInt( "vc_buf_size" ); + + _iq_time = 0; + + _output_extra_latency = config.GetInt( "output_extra_latency" ); + + // Routing + + _rf = GetRoutingFunction( config ); + + // Alloc VC's + + _vc = new VC * [_inputs]; + + for ( int i = 0; i < _inputs; ++i ) { + _vc[i] = new VC [_vcs]; + for( int j=0; j < _vcs; j++ ) + _vc[i][j].init( config, _outputs ); + + for ( int v = 0; v < _vcs; ++v ) { // Name the vc modules + vc_name << "vc_i" << i << "_v" << v; + _vc[i][v].SetName( this, vc_name.str( ) ); + vc_name.seekp( 0, ios::beg ); + } + } + + // Alloc next VCs' buffer state + + _next_vcs = new BufferState [_outputs]; + for( int j=0; j < _outputs; j++ ) { + _next_vcs[j].init( config ); + } + + for ( int o = 0; o < _outputs; ++o ) { + vc_name << "next_vc_o" << o; + _next_vcs[o].SetName( this, vc_name.str( ) ); + vc_name.seekp( 0, ios::beg ); + } + + // Alloc allocators + + config.GetStr( "vc_allocator", alloc_type ); + _vc_allocator = Allocator::NewAllocator( config, + this, "vc_allocator", + alloc_type, + _vcs*_inputs, 1, + _vcs*_outputs, 1 ); + + if ( !_vc_allocator ) { + cout << "ERROR: Unknown vc_allocator type " << alloc_type << endl; + exit(-1); + } + + config.GetStr( "sw_allocator", alloc_type ); + _sw_allocator = Allocator::NewAllocator( config, + this, "sw_allocator", + alloc_type, + _inputs*_input_speedup, _input_speedup, + _outputs*_output_speedup, _output_speedup ); + + if ( !_sw_allocator ) { + cout << "ERROR: Unknown sw_allocator type " << alloc_type << endl; + exit(-1); + } + + _sw_rr_offset = new int [_inputs*_input_speedup]; + for ( int i = 0; i < _inputs*_input_speedup; ++i ) { + _sw_rr_offset[i] = 0; + } + + // Alloc pipelines (to simulate processing/transmission delays) + + _crossbar_pipe = + new PipelineFIFO( this, "crossbar_pipeline", _outputs*_output_speedup, + _st_prepare_delay + _st_final_delay ); + + _credit_pipe = + new PipelineFIFO( this, "credit_pipeline", _inputs, + _credit_delay ); + + // Input and output queues + + _input_buffer = new queue [_inputs]; + _output_buffer = new queue > [_outputs]; + + _in_cred_buffer = new queue [_inputs]; + _out_cred_buffer = new queue [_outputs]; + + // Switch configuration (when held for multiple cycles) + + _hold_switch_for_packet = config.GetInt( "hold_switch_for_packet" ); + _switch_hold_in = new int [_inputs*_input_speedup]; + _switch_hold_out = new int [_outputs*_output_speedup]; + _switch_hold_vc = new int [_inputs*_input_speedup]; + + for ( int i = 0; i < _inputs*_input_speedup; ++i ) { + _switch_hold_in[i] = -1; + _switch_hold_vc[i] = -1; + } + + for ( int i = 0; i < _outputs*_output_speedup; ++i ) { + _switch_hold_out[i] = -1; + } +} + +IQRouter::~IQRouter( ) +{ + for ( int i = 0; i < _inputs; ++i ) { + delete [] _vc[i]; + } + + delete [] _vc; + delete [] _next_vcs; + + delete _vc_allocator; + delete _sw_allocator; + + delete [] _sw_rr_offset; + + delete _crossbar_pipe; + delete _credit_pipe; + + delete [] _input_buffer; + delete [] _output_buffer; + + delete [] _in_cred_buffer; + delete [] _out_cred_buffer; + + delete [] _switch_hold_in; + delete [] _switch_hold_vc; + delete [] _switch_hold_out; +} + +void IQRouter::ReadInputs( ) +{ + _ReceiveFlits( ); + _ReceiveCredits( ); +} + +void IQRouter::InternalStep( ) +{ + _InputQueuing( ); + _Route( ); + _VCAlloc( ); + _SWAlloc( ); + + for ( int input = 0; input < _inputs; ++input ) { + for ( int vc = 0; vc < _vcs; ++vc ) { + _vc[input][vc].AdvanceTime( ); + } + } + + _crossbar_pipe->Advance( ); + _credit_pipe->Advance( ); + ++_iq_time; + + _OutputQueuing( ); +} + +#include "interconnect_interface.h" +void IQRouter::WriteOutputs( ) +{ +// Flit *f; +// for ( int output = 0; output < _outputs; ++output ) { +// if ( !_output_buffer[output].empty( ) ) { + // f = _output_buffer[output].front( ); + // if ( out_buf_has_space (f->dest,f->data, f->head , f->tail) ){ + _SendFlits( ); + _SendCredits( ); + //} + //} + // } +} + +void IQRouter::_ReceiveFlits( ) +{ + Flit *f; + + for ( int input = 0; input < _inputs; ++input ) { + f = *((*_input_channels)[input]); + + if ( f ) { + _input_buffer[input].push( f ); + } + } +} + +void IQRouter::_ReceiveCredits( ) +{ + Credit *c; + + for ( int output = 0; output < _outputs; ++output ) { + c = *((*_output_credits)[output]); + + if ( c ) { + _out_cred_buffer[output].push( c ); + } + } +} + +void IQRouter::_InputQueuing( ) +{ + Flit *f; + Credit *c; + VC *cur_vc; + + for ( int input = 0; input < _inputs; ++input ) { + if ( !_input_buffer[input].empty( ) ) { + f = _input_buffer[input].front( ); + _input_buffer[input].pop( ); + + cur_vc = &_vc[input][f->vc]; + + if ( !cur_vc->AddFlit( f ) ) { + Error( "VC buffer overflow" ); + } + + if ( f->watch ) { + cout << "Received flit at " << _fullname << endl; + cout << *f; + } + } + } + + for ( int input = 0; input < _inputs; ++input ) { + for ( int vc = 0; vc < _vcs; ++vc ) { + + cur_vc = &_vc[input][vc]; + + if ( cur_vc->GetState( ) == VC::idle ) { + f = cur_vc->FrontFlit( ); + + if ( f ) { + if ( !f->head ) { + Error( "Received non-head flit at idle VC" ); + } + + cur_vc->Route( _rf, this, f, input ); + cur_vc->SetState( VC::routing ); + } + } + } + } + + for ( int output = 0; output < _outputs; ++output ) { + if ( !_out_cred_buffer[output].empty( ) ) { + c = _out_cred_buffer[output].front( ); + _out_cred_buffer[output].pop( ); + + _next_vcs[output].ProcessCredit( c ); + delete c; + } + } +} + +void IQRouter::_Route( ) +{ + VC *cur_vc; + + for ( int input = 0; input < _inputs; ++input ) { + for ( int vc = 0; vc < _vcs; ++vc ) { + + cur_vc = &_vc[input][vc]; + + if ( ( cur_vc->GetState( ) == VC::routing ) && + ( cur_vc->GetStateTime( ) >= _routing_delay ) ) { + + cur_vc->SetState( VC::vc_alloc ); + } + } + } +} + +void IQRouter::_AddVCRequests( VC* cur_vc, int input_index, bool watch ) +{ + const OutputSet *route_set; + BufferState *dest_vc; + int vc_cnt, out_vc; + int in_priority, out_priority; + + route_set = cur_vc->GetRouteSet( ); + out_priority = cur_vc->GetPriority( ); + + for ( int output = 0; output < _outputs; ++output ) { + vc_cnt = route_set->NumVCs( output ); + dest_vc = &_next_vcs[output]; + + for ( int vc_index = 0; vc_index < vc_cnt; ++vc_index ) { + out_vc = route_set->GetVC( output, vc_index, &in_priority ); + + if ( watch ) { + cout << " trying vc " << out_vc << " (out = " << output << ") ... "; + } + + // On the input input side, a VC might request several output + // VCs. These VCs can be prioritized by the routing function + // and this is reflected in "in_priority". On the output, + // if multiple VCs are requesting the same output VC, the priority + // of VCs is based on the actual packet priorities, which is + // reflected in "out_priority". + + if ( dest_vc->IsAvailableFor( out_vc ) ) { + _vc_allocator->AddRequest( input_index, output*_vcs + out_vc, 1, + in_priority, out_priority ); + if ( watch ) { + cout << "available" << endl; + } + } else if ( watch ) { + cout << "busy" << endl; + } + } + } +} + +void IQRouter::_VCAlloc( ) +{ + VC *cur_vc; + BufferState *dest_vc; + int input_and_vc; + int match_input; + int match_vc; + + Flit *f; + bool watched; + + _vc_allocator->Clear( ); + watched = false; + + for ( int input = 0; input < _inputs; ++input ) { + for ( int vc = 0; vc < _vcs; ++vc ) { + + cur_vc = &_vc[input][vc]; + + if ( ( cur_vc->GetState( ) == VC::vc_alloc ) && + ( cur_vc->GetStateTime( ) >= _vc_alloc_delay ) ) { + + f = cur_vc->FrontFlit( ); + if ( f->watch ) { + cout << "VC requesting allocation at " << _fullname << endl; + cout << " input_index = " << input*_vcs + vc << endl; + cout << *f; + watched = true; + } + + _AddVCRequests( cur_vc, input*_vcs + vc, f->watch ); + } + } + } + + /*if ( watched ) { + _vc_allocator->PrintRequests( ); + }*/ + + _vc_allocator->Allocate( ); + + // Winning flits get a VC + + for ( int output = 0; output < _outputs; ++output ) { + for ( int vc = 0; vc < _vcs; ++vc ) { + input_and_vc = _vc_allocator->InputAssigned( output*_vcs + vc ); + + if ( input_and_vc != -1 ) { + match_input = input_and_vc / _vcs; + match_vc = input_and_vc - match_input*_vcs; + + cur_vc = &_vc[match_input][match_vc]; + dest_vc = &_next_vcs[output]; + + cur_vc->SetState( VC::active ); + cur_vc->SetOutput( output, vc ); + dest_vc->TakeBuffer( vc ); + + f = cur_vc->FrontFlit( ); + + if ( f->watch ) { + cout << "Granted VC allocation at " << _fullname + << " (input index " << input_and_vc << " )" << endl; + cout << *f; + } + } + } + } +} + +void IQRouter::_SWAlloc( ) +{ + Flit *f; + Credit *c; + + VC *cur_vc; + BufferState *dest_vc; + + int input; + int output; + int vc; + + int expanded_input; + int expanded_output; + + _sw_allocator->Clear( ); + + for ( input = 0; input < _inputs; ++input ) { + for ( int s = 0; s < _input_speedup; ++s ) { + expanded_input = s*_inputs + input; + + // Arbitrate (round-robin) between multiple + // requesting VCs at the same input (handles + // the case when multiple VC's are requesting + // the same output port) + vc = _sw_rr_offset[ expanded_input ]; + + for ( int v = 0; v < _vcs; ++v ) { + + // This continue acounts for the interleaving of + // VCs when input speedup is used + if ( ( vc % _input_speedup ) != s ) { + vc = ( vc + 1 ) % _vcs; + continue; + } + + cur_vc = &_vc[input][vc]; + + if ( ( cur_vc->GetState( ) == VC::active ) && + ( !cur_vc->Empty( ) ) ) { + + dest_vc = &_next_vcs[cur_vc->GetOutputPort( )]; + + if ( !dest_vc->IsFullFor( cur_vc->GetOutputVC( ) ) ) { + + // When input_speedup > 1, the virtual channel buffers + // are interleaved to create multiple input ports to + // the switch. Similarily, the output ports are + // interleaved based on their originating input when + // output_speedup > 1. + + assert( expanded_input == (vc%_input_speedup)*_inputs + input ); + expanded_output = (input%_output_speedup)*_outputs + cur_vc->GetOutputPort( ); + + if ( ( _switch_hold_in[expanded_input] == -1 ) && + ( _switch_hold_out[expanded_output] == -1 ) ) { + + // We could have requested this same input-output pair in a previous + // iteration, only replace the previous request if the current + // request has a higher priority (this is default behavior of the + // allocators). Switch allocation priorities are strictly + // determined by the packet priorities. + + _sw_allocator->AddRequest( expanded_input, expanded_output, vc, + cur_vc->GetPriority( ), + cur_vc->GetPriority( ) ); + } + } + } + + vc = ( vc + 1 ) % _vcs; + } + } + } + + _sw_allocator->Allocate( ); + + // Winning flits cross the switch + + _crossbar_pipe->WriteAll( 0 ); + + for ( int input = 0; input < _inputs; ++input ) { + c = 0; + + for ( int s = 0; s < _input_speedup; ++s ) { + + expanded_input = s*_inputs + input; + + if ( _switch_hold_in[expanded_input] != -1 ) { + expanded_output = _switch_hold_in[expanded_input]; + vc = _switch_hold_vc[expanded_input]; + cur_vc = &_vc[input][vc]; + + if ( cur_vc->Empty( ) ) { // Cancel held match if VC is empty + expanded_output = -1; + } + } else { + expanded_output = _sw_allocator->OutputAssigned( expanded_input ); + } + + if ( expanded_output >= 0 ) { + output = expanded_output % _outputs; + + if ( _switch_hold_in[expanded_input] == -1 ) { + vc = _sw_allocator->ReadRequest( expanded_input, expanded_output ); + cur_vc = &_vc[input][vc]; + } + + if ( _hold_switch_for_packet ) { + _switch_hold_in[expanded_input] = expanded_output; + _switch_hold_vc[expanded_input] = vc; + _switch_hold_out[expanded_output] = expanded_input; + } + + assert( ( cur_vc->GetState( ) == VC::active ) && + ( !cur_vc->Empty( ) ) && + ( cur_vc->GetOutputPort( ) == ( expanded_output % _outputs ) ) ); + + dest_vc = &_next_vcs[cur_vc->GetOutputPort( )]; + + assert( !dest_vc->IsFullFor( cur_vc->GetOutputVC( ) ) ); + + // Forward flit to crossbar and send credit back + f = cur_vc->RemoveFlit( ); + + f->hops++; + + if ( f->watch ) { + cout << "Forwarding flit through crossbar at " << _fullname << ":" << endl; + cout << *f; + } + + if ( !c ) { + c = _NewCredit( _vcs ); + } + + c->vc[c->vc_cnt] = f->vc; + c->vc_cnt++; + + f->vc = cur_vc->GetOutputVC( ); + dest_vc->SendingFlit( f ); + + _crossbar_pipe->Write( f, expanded_output ); + + if ( f->tail ) { + cur_vc->SetState( VC::idle ); + + _switch_hold_in[expanded_input] = -1; + _switch_hold_vc[expanded_input] = -1; + _switch_hold_out[expanded_output] = -1; + } + + _sw_rr_offset[expanded_input] = ( f->vc + 1 ) % _vcs; + } + } + + _credit_pipe->Write( c, input ); + } +} + +void IQRouter::_OutputQueuing( ) +{ + Flit *f; + Credit *c; + int expanded_output; + + for ( int output = 0; output < _outputs; ++output ) { + for ( int t = 0; t < _output_speedup; ++t ) { + expanded_output = _outputs*t + output; + f = _crossbar_pipe->Read( expanded_output ); + + if ( f ) { + _output_buffer[output].push( make_pair(f,_iq_time) ); + } + } + } + + for ( int input = 0; input < _inputs; ++input ) { + c = _credit_pipe->Read( input ); + + if ( c ) { + _in_cred_buffer[input].push( c ); + } + } +} + +void IQRouter::_SendFlits( ) +{ + Flit *f; + + for ( int output = 0; output < _outputs; ++output ) { + + f = NULL; + + if ( !_output_buffer[output].empty( ) ) { + if ((_iq_time - _output_buffer[output].front().second) >= _output_extra_latency) { + f = _output_buffer[output].front( ).first; + _output_buffer[output].pop( ); + } + } + + *(*_output_channels)[output] = f; + } +} + +void IQRouter::_SendCredits( ) +{ + Credit *c; + + for ( int input = 0; input < _inputs; ++input ) { + if ( !_in_cred_buffer[input].empty( ) ) { + c = _in_cred_buffer[input].front( ); + _in_cred_buffer[input].pop( ); + } else { + c = 0; + } + + *(*_input_credits)[input] = c; + } +} + +void IQRouter::Display( ) const +{ + for ( int input = 0; input < _inputs; ++input ) { + for ( int v = 0; v < _vcs; ++v ) { + _vc[input][v].Display( ); + } + } +} -- cgit v1.3