From 7f49fe9feb174d34efc2a011bad79b38522a360b Mon Sep 17 00:00:00 2001 From: Dongdong Li Date: Thu, 8 Aug 2013 00:15:58 -0800 Subject: Intesim2 Integration Details: See Review 80001 https://gpgpu-sim-code-review.appspot.com/80001/ [git-p4: depot-paths = "//depot/gpgpu_sim_research/fermi/distribution/": change = 16747] --- src/intersim2/allocators/selalloc.cpp | 254 ++++++++++++++++++++++++++++++++++ 1 file changed, 254 insertions(+) create mode 100644 src/intersim2/allocators/selalloc.cpp (limited to 'src/intersim2/allocators/selalloc.cpp') diff --git a/src/intersim2/allocators/selalloc.cpp b/src/intersim2/allocators/selalloc.cpp new file mode 100644 index 0000000..df42143 --- /dev/null +++ b/src/intersim2/allocators/selalloc.cpp @@ -0,0 +1,254 @@ +// $Id: selalloc.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 + +#include "selalloc.hpp" +#include "random_utils.hpp" + +//#define DEBUG_SELALLOC + +SelAlloc::SelAlloc( Module *parent, const string& name, + int inputs, int outputs, int iters ) : + SparseAllocator( parent, name, inputs, outputs ) +{ + _iter = iters; + + _gptrs.resize(outputs, 0); + _aptrs.resize(inputs, 0); + _outmask.resize(outputs, 0); +} + +void SelAlloc::Allocate( ) +{ + int input; + int output; + + int input_offset; + int output_offset; + + map::iterator p; + set::iterator outer_iter; + bool wrapped; + + int max_index; + int max_pri; + + vector grants(_outputs, -1); + + for ( int iter = 0; iter < _iter; ++iter ) { + // Grant phase + + for( outer_iter = _out_occ.begin( ); + outer_iter != _out_occ.end( ); ++outer_iter ) { + output = *outer_iter; + + // Skip loop if there are no requests + // or the output is already matched or + // the output is masked + if ( ( _out_req[output].empty( ) ) || + ( _outmatch[output] != -1 ) || + ( _outmask[output] != 0 ) ) { + continue; + } + + // A round-robin arbiter between input requests + input_offset = _gptrs[output]; + + p = _out_req[output].begin( ); + while( ( p != _out_req[output].end( ) ) && + ( p->second.port < input_offset ) ) { + p++; + } + + max_index = -1; + max_pri = 0; + + wrapped = false; + while( (!wrapped) || + ( ( p != _out_req[output].end() ) && + ( p->second.port < input_offset ) ) ) { + if ( p == _out_req[output].end( ) ) { + if ( wrapped ) { break; } + // p is valid here because empty lists + // are skipped (above) + p = _out_req[output].begin( ); + wrapped = true; + } + + input = p->second.port; + + // we know the output is free (above) and + // if the input is free, check if request is the + // highest priority so far + if ( ( _inmatch[input] == -1 ) && + ( ( p->second.out_pri > max_pri ) || ( max_index == -1 ) ) ) { + max_pri = p->second.out_pri; + max_index = input; + } + + p++; + } + + if ( max_index != -1 ) { // grant + grants[output] = max_index; + } + } + +#ifdef DEBUG_SELALLOC + cout << "grants: "; + for ( int i = 0; i < _outputs; ++i ) { + cout << grants[i] << " "; + } + cout << endl; + + cout << "aptrs: "; + for ( int i = 0; i < _inputs; ++i ) { + cout << _aptrs[i] << " "; + } + cout << endl; +#endif + + // Accept phase + + for ( outer_iter = _in_occ.begin( ); + outer_iter != _in_occ.end( ); ++outer_iter ) { + input = *outer_iter; + + if ( _in_req[input].empty( ) ) { + continue; + } + + // A round-robin arbiter between output grants + output_offset = _aptrs[input]; + + p = _in_req[input].begin( ); + while( ( p != _in_req[input].end( ) ) && + ( p->second.port < output_offset ) ) { + p++; + } + + max_index = -1; + max_pri = 0; + + wrapped = false; + while( (!wrapped) || + ( ( p != _in_req[input].end() ) && + ( p->second.port < output_offset ) ) ) { + if ( p == _in_req[input].end( ) ) { + if ( wrapped ) { break; } + // p is valid here because empty lists + // are skipped (above) + p = _in_req[input].begin( ); + wrapped = true; + } + + output = p->second.port; + + // we know the output is free (above) and + // if the input is free, check if the highest + // priroity + if ( ( grants[output] == input ) && + ( !_out_req[output].empty( ) ) && + ( ( p->second.in_pri > max_pri ) || ( max_index == -1 ) ) ) { + max_pri = p->second.in_pri; + max_index = output; + } + + p++; + } + + if ( max_index != -1 ) { + // Accept + output = max_index; + + _inmatch[input] = output; + _outmatch[output] = input; + + // Only update pointers if accepted during the 1st iteration + if ( iter == 0 ) { + _gptrs[output] = ( input + 1 ) % _inputs; + _aptrs[input] = ( output + 1 ) % _outputs; + } + } + } + } + +#ifdef DEBUG_SELALLOC + cout << "input match: "; + for ( int i = 0; i < _inputs; ++i ) { + cout << _inmatch[i] << " "; + } + cout << endl; + + cout << "output match: "; + for ( int j = 0; j < _outputs; ++j ) { + cout << _outmatch[j] << " "; + } + cout << endl; +#endif +} + +void SelAlloc::MaskOutput( int out, int mask ) +{ + assert( ( out >= 0 ) && ( out < _outputs ) ); + _outmask[out] = mask; +} + +void SelAlloc::PrintRequests( ostream * os ) const +{ + map::const_iterator iter; + + if(!os) os = &cout; + + *os << "Input requests = [ "; + for ( int input = 0; input < _inputs; ++input ) { + *os << input << " -> [ "; + for ( iter = _in_req[input].begin( ); + iter != _in_req[input].end( ); iter++ ) { + *os << iter->second.port << " "; + } + *os << "] "; + } + *os << "], output requests = [ "; + for ( int output = 0; output < _outputs; ++output ) { + *os << output << " -> "; + if ( _outmask[output] == 0 ) { + *os << "[ "; + for ( iter = _out_req[output].begin( ); + iter != _out_req[output].end( ); iter++ ) { + *os << iter->second.port << " "; + } + *os << "] "; + } else { + *os << "masked "; + } + } + *os << "]." << endl; +} + -- cgit v1.3