diff options
Diffstat (limited to 'src/intersim2/routers/chaos_router.cpp')
| -rw-r--r-- | src/intersim2/routers/chaos_router.cpp | 673 |
1 files changed, 673 insertions, 0 deletions
diff --git a/src/intersim2/routers/chaos_router.cpp b/src/intersim2/routers/chaos_router.cpp new file mode 100644 index 0000000..10c6277 --- /dev/null +++ b/src/intersim2/routers/chaos_router.cpp @@ -0,0 +1,673 @@ +// $Id: chaos_router.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. +*/ + +#include "booksim.hpp" +#include <string> +#include <sstream> +#include <iostream> +#include <cstdlib> + +#include "chaos_router.hpp" +#include "random_utils.hpp" +#include "globals.hpp" + +ChaosRouter::ChaosRouter( const Configuration& config, + Module *parent, const string & name, int id, + int inputs, int outputs ) + : Router( config, + parent, name, + id, + inputs, outputs ) +{ + int i; + + if ( inputs != outputs ) { + Error( "Chaos router must have equal number of input and output ports" ); + } + + _buffer_size = config.GetInt( "vc_buf_size" ); + assert(_buffer_size >= config.GetInt( "const_flits_per_packet" )); + + _multi_queue_size = config.GetInt( "multi_queue_size" ); + + _cur_channel = 0; + _read_stall = 0; + + // Routing + + string rf = config.GetStr("routing_function") + "_" + config.GetStr("topology"); + map<string, tRoutingFunction>::iterator rf_iter = gRoutingFunctionMap.find(rf); + if(rf_iter == gRoutingFunctionMap.end()) { + Error("Invalid routing function: " + rf); + } + _rf = rf_iter->second; + + _input_route.resize(_inputs); + + for ( i = 0; i < _inputs; ++i ) { + _input_route[i] = new OutputSet( ); + } + + _mq_route.resize(_multi_queue_size); + + for ( i = 0; i < _multi_queue_size; ++i ) { + _mq_route[i] = new OutputSet( ); + } + + // Alloc pipelines (to simulate processing/transmission delays) + + _crossbar_pipe = + new PipelineFIFO<Flit>( this, "crossbar_pipeline", _outputs, + _crossbar_delay ); + + // Input and output queues + + _input_frame.resize(_inputs); + _output_frame.resize(_outputs); + _multi_queue.resize(_multi_queue_size); + + _credit_queue.resize(_inputs); + + _input_state.resize(_inputs, empty); + _input_output_match.resize(_inputs, -1); + _input_mq_match.resize(_inputs, -1); + + _output_matched.resize(_outputs, false); + _next_queue_cnt.resize(_outputs, 0); + + _multi_match.resize(_multi_queue_size, -1); + _mq_age.resize(_multi_queue_size); + _mq_matched.resize(_multi_queue_size, false); + _multi_state.resize(_multi_queue_size, empty); + + for ( i = 0; i < _multi_queue_size; ++i ) { + _multi_state[i] = empty; + _multi_match[i] = -1; + _mq_matched[i] = false; + } +} + +ChaosRouter::~ChaosRouter( ) +{ + int i; + + delete _crossbar_pipe; + + for ( i = 0; i < _inputs; ++i ) { + delete _input_route[i]; + } + + for ( i = 0; i < _multi_queue_size; ++i ) { + delete _mq_route[i]; + } +} + +void ChaosRouter::ReadInputs( ) +{ + Flit *f; + Credit *c; + + for ( int input = 0; input < _inputs; ++input ) { + f = _input_channels[input]->Receive(); + + if ( f ) { + _input_frame[input].push( f ); + + if ( f->watch ) { + *gWatchOut << GetSimTime() << " | " << FullName() << " | " + << "Flit arriving at " << FullName() + << " on channel " << input << endl + << *f; + } + + switch( _input_state[input] ) { + case empty: + if ( f->head ) { + if ( f->tail ) { + _input_state[input] = full; + } else { + _input_state[input] = filling; + } + _rf( this, f, input, _input_route[input], false ); + } else { + cout << *f; + Error( "Empty buffer received non-head flit!" ); + } + break; + + case filling: + if ( f->tail ) { + _input_state[input] = full; + } else if ( f->head ) { + Error( "Input buffer received another head before previous tail!" ); + } + break; + + case full: + Error( "Received flit while full!" ); + break; + + case leaving: + if ( f->head ) { + _input_state[input] = shared; + + if ( f->tail ) { + Error( "Received single-flit packet in leaving state!" ); + } + } else { + cout << *f; + Error( "Received non-head flit while packet leaving!" ); + } + break; + + case cut_through: + if ( f->tail ) { + _input_state[input] = leaving; + } + if ( f->head ) { + cout << *f; + Error( "Received head flit in cut through buffer!" ); + } + break; + + case shared: + if ( f->head ) { + Error( "Shared buffer received another head!" ); + } else if ( f->tail ) { + cout << "Input " << input << endl; + cout << *f; + Error( "Shared buffer received another tail!" ); + } + break; + } + } + } + + // Process incoming credits + + for ( int output = 0; output < _outputs; ++output ) { + c = _output_credits[output]->Receive(); + + if ( c ) { + _next_queue_cnt[output]--; + + if ( _next_queue_cnt[output] < 0 ) { + Error( "Next queue count fell below zero!" ); + } + + c->Free(); + } + } +} + +void ChaosRouter::_InternalStep( ) +{ + _NextInterestingChannel( ); + _OutputAdvance( ); + + _crossbar_pipe->Advance( ); +} + +void ChaosRouter::WriteOutputs( ) +{ + _SendFlits( ); + _SendCredits( ); +} + +bool ChaosRouter::_IsInjectionChan( int chan ) const +{ + return ( chan == _inputs - 1 ); +} + +bool ChaosRouter::_IsEjectionChan( int chan ) const +{ + return ( chan == _outputs - 1 ); +} + +bool ChaosRouter::_InputReady( int input ) const +{ + bool ready = false; + + if ( ( _input_state[input] == filling ) || + ( _input_state[input] == full ) ) { + ready = true; + } + + return ready; +} + +bool ChaosRouter::_OutputFull( int out ) const +{ + return ( _output_frame[out].size( ) >= (size_t)_buffer_size ); +} + +bool ChaosRouter::_OutputAvail( int out ) const +{ + return ( ( !_output_matched[out] ) && ( _output_frame[out].empty( ) ) ); + //&& ( _next_queue_cnt[out] == 0 ) ); + //return ( ( !_output_matched[out] ) && !_OutputFull( out ) ); +} + +bool ChaosRouter::_MultiQueueFull( int mq ) const +{ + return ( _multi_queue[mq].size( ) >= (size_t)_buffer_size ); +} + +int ChaosRouter::_InputForOutput( int output ) const +{ + // return an input that prefers this output + + int input; + int offset = RandomInt( _inputs - 1 ); + bool match = false; + + for ( int i = 0; ( i < _inputs ) && ( !match ); ++i ) { + input = ( i + offset ) % _inputs; + + if ( _InputReady( input ) && + ( ! _input_route[input]->OutputEmpty( output ) ) ) { + match = true; + } + } + + return match ? input : -1; +} + +int ChaosRouter::_MultiQueueForOutput( int output ) const +{ + // return oldest multi queue that prefers the output, + // or if none prefer and the multi queue is full, + // return a random entry + + int mq_oldest = -1; + int mq_age; + + int m, r; + + bool isfull = true; + + for ( int i = 0; i < _multi_queue_size; ++i ) { + if ( ( _multi_match[i] == -1 ) && + ( ( _multi_state[i] == full ) || + ( _multi_state[i] == filling ) ) ) { + + if ( ( !_mq_route[i]->OutputEmpty( output ) ) && + ( ( mq_oldest == -1 ) || ( _mq_age[i] > mq_age ) ) ) { + mq_oldest = i; + mq_age = _mq_age[i]; + } + } + + // deroute only if all queues contain head flits ... + + if ( ( _multi_state[i] != full ) && + ( _multi_state[i] != filling ) && + ( _multi_state[i] != shared ) ) { + isfull = false; + } + } + + // Don't deroute MQs to the ejection channel + if ( ( mq_oldest == -1 ) && isfull && + ( !_IsEjectionChan( output ) ) ) { + r = RandomInt( _multi_queue_size - 1 ); + + // Find first routable multi-queue + for ( int i = 0; i < _multi_queue_size; ++i ) { + m = ( i + r ) % _multi_queue_size; + if ( ( _multi_state[m] == filling ) || + ( _multi_state[m] == full ) ) { + mq_oldest = m; + //cout << "DEROUTING at " << FullName() << endl; + break; + } + } + + if ( mq_oldest == -1 ) { + cout << "write stall" << endl; + } + } + + return mq_oldest; +} + +int ChaosRouter::_FindAvailMultiQueue( ) const +{ + // return any empty multi queue slot + + int avail = -1; + + for ( int i = 0; i < _multi_queue_size; ++i ) { + if ( ( !_MultiQueueFull( i ) ) && + ( !_mq_matched[i] ) ) { + avail = i; + break; + } + } + + return avail; +} + +void ChaosRouter::_NextInterestingChannel( ) +{ + bool interesting; + + int mq_index; + int in_index; + int mq_avail; + + int c; + + interesting = false; + mq_index = -1; + in_index = -1; + + // A channel is interesting if + // + // ( output frame available and + // ( ( a multiqueue packet wants output channel ) or + // ( an input packet wants output channel ) or + // ( the multiqueue is full ) ) ) + // or + // ( the packet at the input channel is stalled ) + + for ( c = 0; ( c < _inputs ) && ( !interesting ); ++c ) { + if ( _OutputAvail( _cur_channel ) ) { + mq_index = _MultiQueueForOutput( _cur_channel ); + in_index = _InputForOutput( _cur_channel ); + + if ( ( mq_index != -1 ) || ( in_index != -1 ) ) { + interesting = true; + } + } + + if ( _input_state[_cur_channel] == full ) { + interesting = true; + } + + if ( !interesting ) { + _cur_channel = ( _cur_channel + 1 ) % _inputs; + } + } + + if ( interesting ) { + //cout << _cur_channel << " is interesting at " << FullName() << endl; + + if ( mq_index != -1 ) { + //cout << "Match for multi-queue " << mq_index << " at " << FullName() + // << ", output matched = " << _output_matched[_cur_channel] << endl; + + _output_matched[_cur_channel] = true; + _multi_match[mq_index] = _cur_channel; + } else if ( in_index != -1 ) { + _output_matched[_cur_channel] = true; + _input_output_match[in_index] = _cur_channel; + + //cout << "Match for input " << in_index << " at " << FullName() << endl; + + if ( _input_state[in_index] == full ) { + _input_state[in_index] = leaving; + } else if ( _input_state[in_index] == filling ) { + _input_state[in_index] = cut_through; + } else { + Error( "Tried to route input through crossbar that was not full or filling!" ); + } + } + + // Any non-injection channel that is routable is + // directed to the multi-queue + if ( ( ( _input_state[_cur_channel] == filling ) || + ( _input_state[_cur_channel] == full ) ) && + ( !_IsInjectionChan( _cur_channel ) ) ) { + ++_read_stall; + } else { + // go to next channel for the next cycle + _cur_channel = ( _cur_channel + 1 ) % _inputs; + _read_stall = 0; + } + } + + if ( _read_stall > 0 ) { + mq_avail = _FindAvailMultiQueue( ); + + if ( mq_avail != -1 ) { + if ( _input_state[_cur_channel] == full ) { + _input_state[_cur_channel] = leaving; + } else if ( _input_state[_cur_channel] == filling ) { + _input_state[_cur_channel] = cut_through; + } else { + cout << "Input " << _cur_channel << " state = " + << _input_state[_cur_channel] << endl; + Error( "Tried to route input throught multi-queue that was not full or filling!" ); + } + + _input_mq_match[_cur_channel] = mq_avail; + _mq_matched[mq_avail] = true; + + // go to next channel for the next cycle + _cur_channel = ( _cur_channel + 1 ) % _inputs; + _read_stall = 0; + } else { + ++_read_stall; + //cout << "stalling at input " << _cur_channel << " (count = " << _read_stall << ")" << endl; + } + } +} + +void ChaosRouter::_OutputAdvance( ) +{ + Flit *f, *f2; + Credit *c; + bool advanced; + int mq; + + _crossbar_pipe->WriteAll( 0 ); + + for ( int i = 0; i < _inputs; ++i ) { + if ( ( ( _input_output_match[i] != -1 ) || + ( _input_mq_match[i] != -1 ) ) && + ( !_input_frame[i].empty( ) ) ) { + + advanced = false; + f = _input_frame[i].front( ); + + /*if ( ! ) { + + } else { + cout << "Input = " << i + << ", input_output_match = " << _input_output_match[i] + << ", input_mq_match = " << _input_mq_match[i] << endl; + Error( "Input queue empty, but matched!" ); + }*/ + + if ( _input_output_match[i] != -1 ) { + if ( f->tail ) { + _output_matched[_input_output_match[i]] = false; + } + + _crossbar_pipe->Write( f, _input_output_match[i] ); + + if ( f->watch ) { + *gWatchOut << GetSimTime() << " | " << FullName() << " | " + << "Flit traversing crossbar from input queue " + << i << " at " + << FullName() << endl + << *f; + } + + advanced = true; + + } else if ( !_MultiQueueFull( _input_mq_match[i] ) ) { + + mq = _input_mq_match[i]; + + if ( f->head ) { + _rf( this, f, i, _mq_route[mq], false ); + _mq_age[mq] = 0; + + if ( _multi_state[mq] == empty ) { + _multi_state[mq] = filling; + } else if ( _multi_state[mq] == leaving ) { + _multi_state[mq] = shared; + } else { + Error( "Multi-queue received head while not empty or leaving!" ); + } + } + + if ( f->tail ) { + _mq_matched[mq] = false; + + if ( _multi_state[mq] == filling ) { + _multi_state[mq] = full; + } else if ( _multi_state[mq] == cut_through ) { + _multi_state[mq] = leaving; + } else { + Error( "Multi-queue received tail while not filling or cutting-through!" ); + } + } + + _multi_queue[mq].push( f ); + + if ( f->watch ) { + *gWatchOut << GetSimTime() << " | " << FullName() << " | " + << "Flit stored in multiqueue at " + << FullName() << endl + << "State = " << _multi_state[mq] << endl + << *f; + } + + advanced = true; + } + + if ( advanced ) { + _input_frame[i].pop( ); + + if ( f->tail ) { // last in packet, update state + if ( _input_state[i] == leaving ) { + _input_state[i] = empty; + } else if ( _input_state[i] == shared ) { + _input_state[i] = filling; + f2 = _input_frame[i].front( ); + // update routes + _rf( this, f2, i, _input_route[i], false ); + } + + _input_output_match[i] = -1; + _input_mq_match[i] = -1; + } + + c = Credit::New( ); + c->vc.insert(0); + _credit_queue[i].push( c ); + } + } + } + + for ( int m = 0; m < _multi_queue_size; ++m ) { + if ( _multi_match[m] != -1 ) { + if ( !_multi_queue[m].empty( ) ) { + f = _multi_queue[m].front( ); + _multi_queue[m].pop( ); + } else { + cout << "State = " << _multi_state[m] << endl; + Error( "Multi queue empty, but matched!" ); + } + + _crossbar_pipe->Write( f, _multi_match[m] ); + + if ( f->watch ) { + *gWatchOut << GetSimTime() << " | " << FullName() << " | " + << "Flit traversing crossbar from multiqueue slot " + << m << " at " + << FullName() << endl + << *f; + } + + if ( f->head ) { + if ( _multi_state[m] == filling ) { + _multi_state[m] = cut_through; + } else if ( _multi_state[m] == full ) { + _multi_state[m] = leaving; + } else { + Error( "Multi-queue sent head while not filling or full!" ); + } + } + + if ( f->tail ) { + _output_matched[_multi_match[m]] = false; + _multi_match[m] = -1; + + if ( _multi_state[m] == shared ) { + _multi_state[m] = filling; + } else if ( _multi_state[m] == leaving ) { + _multi_state[m] = empty; + } else { + cout << "State = " << _multi_state[m] << endl; + cout << *f; + Error( "Multi-queue sent tail while not leaving or shared!" ); + } + } + } + + _mq_age[m]++; + } +} + + +void ChaosRouter::_SendFlits( ) +{ + for ( int output = 0; output < _outputs; ++output ) { + Flit *f = _crossbar_pipe->Read( output ); + + if ( f ) { + _output_frame[output].push( f ); + f->hops++; + } + + if ( ( _next_queue_cnt[output] < _buffer_size ) && + ( !_output_frame[output].empty( ) ) ) { + _output_channels[output]->Send( _output_frame[output].front( ) ); + _output_frame[output].pop( ); + ++_next_queue_cnt[output]; + } + } +} + +void ChaosRouter::_SendCredits( ) +{ + for ( int input = 0; input < _inputs; ++input ) { + if ( !_credit_queue[input].empty( ) ) { + Credit *c = _credit_queue[input].front( ); + _credit_queue[input].pop( ); + _input_credits[input]->Send( c ); + } + } +} + +void ChaosRouter::Display( ostream & os ) const +{ +} |