diff options
Diffstat (limited to 'src/intersim2/allocators')
20 files changed, 2391 insertions, 0 deletions
diff --git a/src/intersim2/allocators/allocator.cpp b/src/intersim2/allocators/allocator.cpp new file mode 100644 index 0000000..5940ac5 --- /dev/null +++ b/src/intersim2/allocators/allocator.cpp @@ -0,0 +1,481 @@ +// $Id: allocator.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 <iostream> +#include <sstream> +#include <cassert> +#include "allocator.hpp" + +///////////////////////////////////////////////////////////////////////// +//Allocator types +#include "maxsize.hpp" +#include "pim.hpp" +#include "islip.hpp" +#include "loa.hpp" +#include "wavefront.hpp" +#include "selalloc.hpp" +#include "separable_input_first.hpp" +#include "separable_output_first.hpp" +// +///////////////////////////////////////////////////////////////////////// + +//================================================== +// Allocator base class +//================================================== + +Allocator::Allocator( Module *parent, const string& name, + int inputs, int outputs ) : +Module( parent, name ), _inputs( inputs ), _outputs( outputs ), _dirty( false ) +{ + _inmatch.resize(_inputs, -1); + _outmatch.resize(_outputs, -1); +} + +void Allocator::Clear( ) +{ + if(_dirty) { + _inmatch.assign(_inputs, -1); + _outmatch.assign(_outputs, -1); + _dirty = false; + } +} + +void Allocator::AddRequest( int in, int out, int label, int in_pri, + int out_pri ) { + + assert( ( in >= 0 ) && ( in < _inputs ) ); + assert( ( out >= 0 ) && ( out < _outputs ) ); + assert( label >= 0 ); + _dirty = true; +} + +int Allocator::OutputAssigned( int in ) const +{ + assert( ( in >= 0 ) && ( in < _inputs ) ); + + return _inmatch[in]; +} + +int Allocator::InputAssigned( int out ) const +{ + assert( ( out >= 0 ) && ( out < _outputs ) ); + + return _outmatch[out]; +} + +void Allocator::PrintGrants( ostream * os ) const +{ + if(!os) os = &cout; + + *os << "Input grants = [ "; + for ( int input = 0; input < _inputs; ++input ) { + if(_inmatch[input] >= 0) { + *os << input << " -> " << _inmatch[input] << " "; + } + } + *os << "], output grants = [ "; + for ( int output = 0; output < _outputs; ++output ) { + if(_outmatch[output] >= 0) { + *os << output << " -> " << _outmatch[output] << " "; + } + } + *os << "]." << endl; +} + +//================================================== +// DenseAllocator +//================================================== + +DenseAllocator::DenseAllocator( Module *parent, const string& name, + int inputs, int outputs ) : + Allocator( parent, name, inputs, outputs ) +{ + _request.resize(_inputs); + + for ( int i = 0; i < _inputs; ++i ) { + _request[i].resize(_outputs); + for ( int j = 0; j < _outputs; ++j ) { + _request[i][j].label = -1; + } + } +} + +void DenseAllocator::Clear( ) +{ + for ( int i = 0; i < _inputs; ++i ) { + for ( int j = 0; j < _outputs; ++j ) { + _request[i][j].label = -1; + } + } + Allocator::Clear(); +} + +int DenseAllocator::ReadRequest( int in, int out ) const +{ + assert( ( in >= 0 ) && ( in < _inputs ) ); + assert( ( out >= 0 ) && ( out < _outputs ) ); + + return _request[in][out].label; +} + +bool DenseAllocator::ReadRequest( sRequest &req, int in, int out ) const +{ + assert( ( in >= 0 ) && ( in < _inputs ) ); + assert( ( out >= 0 ) && ( out < _outputs ) ); + + req = _request[in][out]; + + return ( req.label >= 0 ); +} + +void DenseAllocator::AddRequest( int in, int out, int label, + int in_pri, int out_pri ) +{ + Allocator::AddRequest(in, out, label, in_pri, out_pri); + assert( _request[in][out].label == -1 ); + + _request[in][out].label = label; + _request[in][out].in_pri = in_pri; + _request[in][out].out_pri = out_pri; +} + +void DenseAllocator::RemoveRequest( int in, int out, int label ) +{ + assert( ( in >= 0 ) && ( in < _inputs ) ); + assert( ( out >= 0 ) && ( out < _outputs ) ); + + _request[in][out].label = -1; +} + +bool DenseAllocator::InputHasRequests( int in ) const +{ + for(int out = 0; out < _outputs; ++out) { + if(_request[in][out].label >= 0) { + return true; + } + } + return false; +} + +bool DenseAllocator::OutputHasRequests( int out ) const +{ + for(int in = 0; in < _inputs; ++in) { + if(_request[in][out].label >= 0) { + return true; + } + } + return false; +} + +int DenseAllocator::NumInputRequests( int in ) const +{ + int result = 0; + for(int out = 0; out < _outputs; ++out) { + if(_request[in][out].label >= 0) { + ++result; + } + } + return result; +} + +int DenseAllocator::NumOutputRequests( int out ) const +{ + int result = 0; + for(int in = 0; in < _inputs; ++in) { + if(_request[in][out].label >= 0) { + ++result; + } + } + return result; +} + +void DenseAllocator::PrintRequests( ostream * os ) const +{ + if(!os) os = &cout; + + *os << "Input requests = [ "; + for ( int input = 0; input < _inputs; ++input ) { + bool print = false; + ostringstream ss; + for ( int output = 0; output < _outputs; ++output ) { + const sRequest & req = _request[input][output]; + if ( req.label >= 0 ) { + print = true; + ss << output << "@" << req.in_pri << " "; + } + } + if(print) { + *os << input << " -> [ " << ss.str() << "] "; + } + } + *os << "], output requests = [ "; + for ( int output = 0; output < _outputs; ++output ) { + bool print = false; + ostringstream ss; + for ( int input = 0; input < _inputs; ++input ) { + const sRequest & req = _request[input][output]; + if ( req.label >= 0 ) { + print = true; + ss << input << "@" << req.out_pri << " "; + } + } + if(print) { + *os << output << " -> [ " << ss.str() << "] "; + } + } + *os << "]." << endl; +} + +//================================================== +// SparseAllocator +//================================================== + +SparseAllocator::SparseAllocator( Module *parent, const string& name, + int inputs, int outputs ) : + Allocator( parent, name, inputs, outputs ) +{ + _in_req.resize(_inputs); + _out_req.resize(_outputs); +} + + +void SparseAllocator::Clear( ) +{ + for ( int i = 0; i < _inputs; ++i ) { + if(!_in_req[i].empty()) + _in_req[i].clear( ); + } + + for ( int j = 0; j < _outputs; ++j ) { + if(!_out_req[j].empty()) + _out_req[j].clear( ); + } + + _in_occ.clear( ); + _out_occ.clear( ); + + Allocator::Clear(); +} + +int SparseAllocator::ReadRequest( int in, int out ) const +{ + sRequest r; + + if ( ! ReadRequest( r, in, out ) ) { + r.label = -1; + } + + return r.label; +} + +bool SparseAllocator::ReadRequest( sRequest &req, int in, int out ) const +{ + bool found; + + assert( ( in >= 0 ) && ( in < _inputs ) ); + assert( ( out >= 0 ) && ( out < _outputs ) ); + + map<int, sRequest>::const_iterator match = _in_req[in].find(out); + if ( match != _in_req[in].end( ) ) { + req = match->second; + found = true; + } else { + found = false; + } + + return found; +} + +void SparseAllocator::AddRequest( int in, int out, int label, + int in_pri, int out_pri ) +{ + Allocator::AddRequest(in, out, label, in_pri, out_pri); + assert( _in_req[in].count(out) == 0 ); + assert( _out_req[out].count(in) == 0 ); + + // insert into occupied inputs set if + // input is currently empty + if ( _in_req[in].empty( ) ) { + _in_occ.insert(in); + } + + // similarly for the output + if ( _out_req[out].empty( ) ) { + _out_occ.insert(out); + } + + sRequest req; + req.port = out; + req.label = label; + req.in_pri = in_pri; + req.out_pri = out_pri; + + _in_req[in][out] = req; + + req.port = in; + + _out_req[out][in] = req; +} + +void SparseAllocator::RemoveRequest( int in, int out, int label ) +{ + assert( ( in >= 0 ) && ( in < _inputs ) ); + assert( ( out >= 0 ) && ( out < _outputs ) ); + + assert( _in_req[in].count( out ) > 0 ); + assert( _in_req[in][out].label == label ); + _in_req[in].erase( out ); + + // remove from occupied inputs list if + // input is now empty + if ( _in_req[in].empty( ) ) { + _in_occ.erase(in); + } + + // similarly for the output + assert( _out_req[out].count( in ) > 0 ); + assert( _out_req[out][in].label == label ); + _out_req[out].erase( in ); + + if ( _out_req[out].empty( ) ) { + _out_occ.erase(out); + } +} + +bool SparseAllocator::InputHasRequests( int in ) const +{ + return _in_occ.count(in) > 0; +} + +bool SparseAllocator::OutputHasRequests( int out ) const +{ + return _out_occ.count(out) > 0; +} + +int SparseAllocator::NumInputRequests( int in ) const +{ + return _in_occ.count(in); +} + +int SparseAllocator::NumOutputRequests( int out ) const +{ + return _out_occ.count(out); +} + +void SparseAllocator::PrintRequests( ostream * os ) const +{ + map<int, sRequest>::const_iterator iter; + + if(!os) os = &cout; + + *os << "Input requests = [ "; + for ( int input = 0; input < _inputs; ++input ) { + if(!_in_req[input].empty()) { + *os << input << " -> [ "; + for ( iter = _in_req[input].begin( ); + iter != _in_req[input].end( ); iter++ ) { + *os << iter->second.port << "@" << iter->second.in_pri << " "; + } + *os << "] "; + } + } + *os << "], output requests = [ "; + for ( int output = 0; output < _outputs; ++output ) { + if(!_out_req[output].empty()) { + *os << output << " -> "; + *os << "[ "; + for ( iter = _out_req[output].begin( ); + iter != _out_req[output].end( ); iter++ ) { + *os << iter->second.port << "@" << iter->second.out_pri << " "; + } + *os << "] "; + } + } + *os << "]." << endl; +} + +//================================================== +// Global allocator allocation function +//================================================== + +Allocator *Allocator::NewAllocator( Module *parent, const string& name, + const string &alloc_type, + int inputs, int outputs, + Configuration const * const config ) +{ + Allocator *a = 0; + + string alloc_name; + string param_str; + size_t left = alloc_type.find_first_of('('); + if(left == string::npos) { + alloc_name = alloc_type; + } else { + alloc_name = alloc_type.substr(0, left); + size_t right = alloc_type.find_last_of(')'); + if(right == string::npos) { + param_str = alloc_type.substr(left+1); + } else { + param_str = alloc_type.substr(left+1, right-left-1); + } + } + if ( alloc_name == "max_size" ) { + a = new MaxSizeMatch( parent, name, inputs, outputs ); + } else if ( alloc_name == "pim" ) { + int iters = param_str.empty() ? (config ? config->GetInt("alloc_iters") : 1) : atoi(param_str.c_str()); + a = new PIM( parent, name, inputs, outputs, iters ); + } else if ( alloc_name == "islip" ) { + int iters = param_str.empty() ? (config ? config->GetInt("alloc_iters") : 1) : atoi(param_str.c_str()); + a = new iSLIP_Sparse( parent, name, inputs, outputs, iters ); + } else if ( alloc_name == "loa" ) { + a = new LOA( parent, name, inputs, outputs ); + } else if ( alloc_name == "wavefront" ) { + a = new Wavefront( parent, name, inputs, outputs ); + } else if ( alloc_name == "rr_wavefront" ) { + a = new Wavefront( parent, name, inputs, outputs, true ); + } else if ( alloc_name == "select" ) { + int iters = param_str.empty() ? (config ? config->GetInt("alloc_iters") : 1) : atoi(param_str.c_str()); + a = new SelAlloc( parent, name, inputs, outputs, iters ); + } else if (alloc_name == "separable_input_first") { + string arb_type = param_str.empty() ? (config ? config->GetStr("arb_type") : "round_robin") : param_str; + a = new SeparableInputFirstAllocator( parent, name, inputs, outputs, + arb_type ); + } else if (alloc_name == "separable_output_first") { + string arb_type = param_str.empty() ? (config ? config->GetStr("arb_type") : "round_robin") : param_str; + a = new SeparableOutputFirstAllocator( parent, name, inputs, outputs, + arb_type ); + } + +//================================================== +// Insert new allocators here, add another else if +//================================================== + + + return a; +} + diff --git a/src/intersim2/allocators/allocator.hpp b/src/intersim2/allocators/allocator.hpp new file mode 100644 index 0000000..ea4441a --- /dev/null +++ b/src/intersim2/allocators/allocator.hpp @@ -0,0 +1,158 @@ +// $Id: allocator.hpp 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. +*/ + +#ifndef _ALLOCATOR_HPP_ +#define _ALLOCATOR_HPP_ + +#include <string> +#include <map> +#include <set> +#include <vector> + +#include "module.hpp" +#include "config_utils.hpp" + +class Allocator : public Module { +protected: + const int _inputs; + const int _outputs; + + bool _dirty; + + vector<int> _inmatch; + vector<int> _outmatch; + +public: + + struct sRequest { + int port; + int label; + int in_pri; + int out_pri; + }; + + Allocator( Module *parent, const string& name, + int inputs, int outputs ); + + virtual void Clear( ); + + virtual int ReadRequest( int in, int out ) const = 0; + virtual bool ReadRequest( sRequest &req, int in, int out ) const = 0; + + virtual void AddRequest( int in, int out, int label = 1, + int in_pri = 0, int out_pri = 0 ); + virtual void RemoveRequest( int in, int out, int label = 1 ) = 0; + + virtual void Allocate( ) = 0; + + int OutputAssigned( int in ) const; + int InputAssigned( int out ) const; + + virtual bool OutputHasRequests( int out ) const = 0; + virtual bool InputHasRequests( int in ) const = 0; + + virtual int NumOutputRequests( int out ) const = 0; + virtual int NumInputRequests( int in ) const = 0; + + virtual void PrintRequests( ostream * os = NULL ) const = 0; + void PrintGrants( ostream * os = NULL ) const; + + static Allocator *NewAllocator( Module *parent, const string& name, + const string &alloc_type, + int inputs, int outputs, + Configuration const * const config = NULL ); +}; + +//================================================== +// A dense allocator stores the entire request +// matrix. +//================================================== + +class DenseAllocator : public Allocator { +protected: + vector<vector<sRequest> > _request; + +public: + DenseAllocator( Module *parent, const string& name, + int inputs, int outputs ); + + void Clear( ); + + int ReadRequest( int in, int out ) const; + bool ReadRequest( sRequest &req, int in, int out ) const; + + void AddRequest( int in, int out, int label = 1, + int in_pri = 0, int out_pri = 0 ); + void RemoveRequest( int in, int out, int label = 1 ); + + bool OutputHasRequests( int out ) const; + bool InputHasRequests( int in ) const; + + int NumOutputRequests( int out ) const; + int NumInputRequests( int in ) const; + + void PrintRequests( ostream * os = NULL ) const; + +}; + +//================================================== +// A sparse allocator only stores the requests +// (allows for a more efficient implementation). +//================================================== + +class SparseAllocator : public Allocator { +protected: + set<int> _in_occ; + set<int> _out_occ; + + vector<map<int, sRequest> > _in_req; + vector<map<int, sRequest> > _out_req; + +public: + SparseAllocator( Module *parent, const string& name, + int inputs, int outputs ); + + void Clear( ); + + int ReadRequest( int in, int out ) const; + bool ReadRequest( sRequest &req, int in, int out ) const; + + void AddRequest( int in, int out, int label = 1, + int in_pri = 0, int out_pri = 0 ); + void RemoveRequest( int in, int out, int label = 1 ); + + bool OutputHasRequests( int out ) const; + bool InputHasRequests( int in ) const; + + int NumOutputRequests( int out ) const; + int NumInputRequests( int in ) const; + + void PrintRequests( ostream * os = NULL ) const; + +}; + +#endif diff --git a/src/intersim2/allocators/islip.cpp b/src/intersim2/allocators/islip.cpp new file mode 100644 index 0000000..ab8f53d --- /dev/null +++ b/src/intersim2/allocators/islip.cpp @@ -0,0 +1,183 @@ +// $Id: islip.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 <iostream> + +#include "islip.hpp" +#include "random_utils.hpp" + +//#define DEBUG_ISLIP + +iSLIP_Sparse::iSLIP_Sparse( Module *parent, const string& name, + int inputs, int outputs, int iters ) : + SparseAllocator( parent, name, inputs, outputs ), + _iSLIP_iter(iters) +{ + _gptrs.resize(_outputs, 0); + _aptrs.resize(_inputs, 0); +} + +void iSLIP_Sparse::Allocate( ) +{ + int input; + int output; + + int input_offset; + int output_offset; + + map<int, sRequest>::iterator p; + bool wrapped; + + for ( int iter = 0; iter < _iSLIP_iter; ++iter ) { + // Grant phase + + vector<int> grants(_outputs, -1); + + for ( output = 0; output < _outputs; ++output ) { + + // Skip loop if there are no requests + // or the output is already matched + if ( ( _out_req[output].empty( ) ) || + ( _outmatch[output] != -1 ) ) { + 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++; + } + + 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, grant request + if ( _inmatch[input] == -1 ) { + grants[output] = input; + break; + } + + p++; + } + } + +#ifdef DEBUG_ISLIP + 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 ( input = 0; input < _inputs; ++input ) { + + 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++; + } + + 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, grant request + if ( grants[output] == input ) { + // Accept + _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; + } + + break; + } + + p++; + } + } + } + +#ifdef DEBUG_ISLIP + 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 +} diff --git a/src/intersim2/allocators/islip.hpp b/src/intersim2/allocators/islip.hpp new file mode 100644 index 0000000..c0c5d2a --- /dev/null +++ b/src/intersim2/allocators/islip.hpp @@ -0,0 +1,48 @@ +// $Id: islip.hpp 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. +*/ + +#ifndef _ISLIP_HPP_ +#define _ISLIP_HPP_ + +#include <vector> + +#include "allocator.hpp" + +class iSLIP_Sparse : public SparseAllocator { + int _iSLIP_iter; + + vector<int> _gptrs; + vector<int> _aptrs; + +public: + iSLIP_Sparse( Module *parent, const string& name, + int inputs, int outputs, int iters ); + + void Allocate( ); +}; + +#endif diff --git a/src/intersim2/allocators/loa.cpp b/src/intersim2/allocators/loa.cpp new file mode 100644 index 0000000..c24bbe3 --- /dev/null +++ b/src/intersim2/allocators/loa.cpp @@ -0,0 +1,112 @@ +// $Id: loa.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 <iostream> + +#include "loa.hpp" +#include "random_utils.hpp" + +LOA::LOA( Module *parent, const string& name, + int inputs, int outputs ) : + DenseAllocator( parent, name, inputs, outputs ) +{ + _req.resize(inputs); + _counts.resize(outputs); + + _rptr.resize(inputs); + _gptr.resize(outputs); +} + +void LOA::Allocate( ) +{ + int input; + int output; + + int input_offset; + int output_offset; + + int lonely; + int lonely_cnt; + + // Count phase --- the number of requests + // per output is counted + + for ( int j = 0; j < _outputs; ++j ) { + _counts[j] = 0; + for ( int i = 0; i < _inputs; ++i ) { + _counts[j] += ( _request[i][j].label != -1 ) ? 1 : 0; + } + } + + // Request phase + for ( input = 0; input < _inputs; ++input ) { + + // Find the lonely output + output_offset = _rptr[input]; + lonely = -1; + lonely_cnt = _inputs + 1; + + for ( int o = 0; o < _outputs; ++o ) { + output = ( o + output_offset ) % _outputs; + + if ( ( _request[input][output].label != -1 ) && + ( _counts[output] < lonely_cnt ) ) { + lonely = output; + lonely_cnt = _counts[output]; + } + } + + // Request the lonely output (-1 for no request) + _req[input] = lonely; + } + + // Grant phase + for ( output = 0; output < _outputs; ++output ) { + input_offset = _gptr[output]; + + for ( int i = 0; i < _inputs; ++i ) { + input = ( i + input_offset ) % _inputs; + + if ( _req[input] == output ) { + // Grant! + + _inmatch[input] = output; + _outmatch[output] = input; + + _rptr[input] = ( _rptr[input] + 1 ) % _outputs; + _gptr[output] = ( _gptr[output] + 1 ) % _inputs; + + break; + } + } + } + + +} + + diff --git a/src/intersim2/allocators/loa.hpp b/src/intersim2/allocators/loa.hpp new file mode 100644 index 0000000..c119c31 --- /dev/null +++ b/src/intersim2/allocators/loa.hpp @@ -0,0 +1,49 @@ +// $Id: loa.hpp 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. +*/ + +#ifndef _LOA_HPP_ +#define _LOA_HPP_ + +#include <vector> + +#include "allocator.hpp" + +class LOA : public DenseAllocator { + vector<int> _counts; + vector<int> _req; + + vector<int> _rptr; + vector<int> _gptr; + +public: + LOA( Module *parent, const string& name, + int inputs, int outputs ); + + void Allocate( ); +}; + +#endif diff --git a/src/intersim2/allocators/maxsize.cpp b/src/intersim2/allocators/maxsize.cpp new file mode 100644 index 0000000..ce18dae --- /dev/null +++ b/src/intersim2/allocators/maxsize.cpp @@ -0,0 +1,210 @@ +// $Id: maxsize.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. + Neither the name of the Stanford University nor the names of its contributors + may be used to endorse or promote products derived from this software without + specific prior written permission. + + 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 <iostream> + +#include "maxsize.hpp" + +// shortest augmenting path: +// +// for all unmatched left nodes, +// push node onto work stack +// end +// +// for all j, +// from[j] = undefined +// end +// +// do, +// +// while( !stack.empty ), +// +// nl = stack.pop +// for each edge (nl,j), +// if ( ( lmatch[nl] != j ) && ( from[j] == undefined ) ), +// if ( rmatch[j] == undefined ), +// stop // augmenting path found +// else +// from[j] = nl +// newstack.push( rmatch[j] ) +// end +// end +// end +// end +// +// stack = newstack +// end +// + +//#define DEBUG_MAXSIZE +//#define PRINT_MATCHING + +MaxSizeMatch::MaxSizeMatch( Module *parent, const string& name, + int inputs, int outputs ) : + DenseAllocator( parent, name, inputs, outputs ) +{ + _from.resize(outputs); + _s = new int [inputs]; + _ns = new int [inputs]; + _prio = 0; +} + +MaxSizeMatch::~MaxSizeMatch( ) +{ + delete [] _s; + delete [] _ns; +} + +void MaxSizeMatch::Allocate( ) +{ + + // augment as many times as possible + // (this is an O(N^3) maximum-size matching algorithm) + while( _ShortestAugmenting( ) ); + + // next time, start at next input to ensure fairness + _prio = (_prio + 1) % _inputs; +} + + +bool MaxSizeMatch::_ShortestAugmenting( ) +{ + int i, j, jn; + int slen, nslen; + + // start with empty stack + slen = 0; + + // push all unassigned inputs to the stack + for ( i = 0; i < _inputs; ++i ) { + j = (i + _prio) % _inputs; + if ( _inmatch[j] == -1 ) { // start with unmatched left nodes + _s[slen++] = j; + } + } + + _from.assign(_inputs, -1); + + for ( int iter = 0; iter < _inputs; iter++ ) { + nslen = 0; + + for ( int e = 0; e < slen; ++e ) { + i = _s[e]; + + for ( j = 0; j < _outputs; ++j ) { + if ( ( _request[i][j].label != -1 ) && // edge (i,j) exists + ( _inmatch[i] != j ) && // (i,j) is not contained in the current matching + ( _from[j] == -1 ) ) { // no shorter path to j exists + + _from[j] = i; // how did we get to j? + +#ifdef DEBUG_MAXSIZE + cout << " got to " << j << " from " << i << endl; +#endif + if ( _outmatch[j] == -1 ) { // j is unmatched -- augmenting path found + goto found_augmenting; + } else { // j is matched + _ns[nslen] = _outmatch[j]; // add the destination of this edge to the leaf nodes + nslen++; + +#ifdef DEBUG_MAXSIZE + cout << " adding " << _outmatch[j] << endl; +#endif + } + } + } + } + + // no augmenting path found yet, swap stacks + int * t = _s; + _s = _ns; + _ns = t; + slen = nslen; + } + + return false; // no augmenting paths + + found_augmenting: + + // the augmenting path ends at node j on the right + +#ifdef DEBUG_MAXSIZE + cout << "Found path: " << j << "c <- "; +#endif + + i = _from[j]; + _outmatch[j] = i; + +#ifdef DEBUG_MAXSIZE + cout << i; +#endif + + while ( _inmatch[i] != -1 ) { // loop until the end of the path + jn = _inmatch[i]; // remove previous edge (i,jn) and add (i,j) + _inmatch[i] = j; + +#ifdef DEBUG_MAXSIZE + cout << " <- " << j << "c <- "; +#endif + + j = jn; // add edge from (jn,in) + i = _from[j]; + _outmatch[j] = i; + +#ifdef DEBUG_MAXSIZE + cout << i; +#endif + } + +#ifdef DEBUG_MAXSIZE + cout << endl; +#endif + + _inmatch[i] = j; + +#ifdef PRINT_MATCHING + cout << "left matching: "; + + for ( i = 0; i < _inputs; i++ ) { + cout << _inmatch[i] << " "; + } + cout << endl; + + cout << "right matching: "; + for ( i = 0; i < _outputs; i++ ) { + cout << _outmatch[i] << " "; + } + cout << endl; +#endif + + return true; +} diff --git a/src/intersim2/allocators/maxsize.hpp b/src/intersim2/allocators/maxsize.hpp new file mode 100644 index 0000000..3a1afe9 --- /dev/null +++ b/src/intersim2/allocators/maxsize.hpp @@ -0,0 +1,51 @@ +// $Id: maxsize.hpp 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. +*/ + +#ifndef _MAXSIZE_HPP_ +#define _MAXSIZE_HPP_ + +#include <vector> + +#include "allocator.hpp" + +class MaxSizeMatch : public DenseAllocator { + vector<int> _from; // array to hold breadth-first tree + int *_s; // stack of leaf nodes in tree + int *_ns; // next stack + int _prio; // priority pointer to ensure fairness + + bool _ShortestAugmenting( ); + +public: + MaxSizeMatch( Module *parent, const string& name, + int inputs, int ouputs ); + ~MaxSizeMatch( ); + + void Allocate( ); +}; + +#endif diff --git a/src/intersim2/allocators/pim.cpp b/src/intersim2/allocators/pim.cpp new file mode 100644 index 0000000..487a6d6 --- /dev/null +++ b/src/intersim2/allocators/pim.cpp @@ -0,0 +1,120 @@ +// $Id: pim.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 <iostream> + +#include "pim.hpp" +#include "random_utils.hpp" + +//#define DEBUG_PIM + +PIM::PIM( Module *parent, const string& name, + int inputs, int outputs, int iters ) : + DenseAllocator( parent, name, inputs, outputs ), + _PIM_iter(iters) +{ +} + +PIM::~PIM( ) +{ +} + +void PIM::Allocate( ) +{ + int input; + int output; + + int input_offset; + int output_offset; + + for ( int iter = 0; iter < _PIM_iter; ++iter ) { + // Grant phase --- outputs randomly choose + // between one of their requests + + vector<int> grants(_outputs, -1); + + for ( output = 0; output < _outputs; ++output ) { + + // A random arbiter between input requests + input_offset = RandomInt( _inputs - 1 ); + + for ( int i = 0; i < _inputs; ++i ) { + input = ( i + input_offset ) % _inputs; + + if ( ( _request[input][output].label != -1 ) && + ( _inmatch[input] == -1 ) && + ( _outmatch[output] == -1 ) ) { + + // Grant + grants[output] = input; + break; + } + } + } + + // Accept phase -- inputs randomly choose + // between input_speedup of their grants + + for ( input = 0; input < _inputs; ++input ) { + + // A random arbiter between output grants + output_offset = RandomInt( _outputs - 1 ); + + for ( int o = 0; o < _outputs; ++o ) { + output = ( o + output_offset ) % _outputs; + + if ( grants[output] == input ) { + + // Accept + _inmatch[input] = output; + _outmatch[output] = input; + + break; + } + } + } + } + +#ifdef DEBUG_PIM + if ( _outputs == 8 ) { + cout << "input match: " << endl; + for ( int i = 0; i < _inputs; ++i ) { + cout << " from " << i << " to " << _inmatch[i] << endl; + } + cout << endl; + } + + cout << "output match: "; + for ( int j = 0; j < _outputs; ++j ) { + cout << _outmatch[j] << " "; + } + cout << endl; +#endif +} + + diff --git a/src/intersim2/allocators/pim.hpp b/src/intersim2/allocators/pim.hpp new file mode 100644 index 0000000..e4d709b --- /dev/null +++ b/src/intersim2/allocators/pim.hpp @@ -0,0 +1,47 @@ +// $Id: pim.hpp 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. +*/ + +#ifndef _PIM_HPP_ +#define _PIM_HPP_ + +#include <vector> + +#include "allocator.hpp" + +class PIM : public DenseAllocator { + int _PIM_iter; + +public: + PIM( Module *parent, const string& name, + int inputs, int outputs, int iters ); + + ~PIM( ); + + void Allocate( ); +}; + +#endif 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 <iostream> + +#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<int, sRequest>::iterator p; + set<int>::iterator outer_iter; + bool wrapped; + + int max_index; + int max_pri; + + vector<int> 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<int, sRequest>::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; +} + diff --git a/src/intersim2/allocators/selalloc.hpp b/src/intersim2/allocators/selalloc.hpp new file mode 100644 index 0000000..9a0fe8c --- /dev/null +++ b/src/intersim2/allocators/selalloc.hpp @@ -0,0 +1,55 @@ +// $Id: selalloc.hpp 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. +*/ + +#ifndef _SELALLOC_HPP_ +#define _SELALLOC_HPP_ + +#include <vector> + +#include "allocator.hpp" + +class SelAlloc : public SparseAllocator { + int _iter; + + vector<int> _aptrs; + vector<int> _gptrs; + + vector<int> _outmask; + +public: + SelAlloc( Module *parent, const string& name, + int inputs, int outputs, int iters ); + + void Allocate( ); + + void MaskOutput( int out, int mask = 1 ); + + virtual void PrintRequests( ostream * os = NULL ) const; + +}; + +#endif diff --git a/src/intersim2/allocators/separable.cpp b/src/intersim2/allocators/separable.cpp new file mode 100644 index 0000000..dc15da6 --- /dev/null +++ b/src/intersim2/allocators/separable.cpp @@ -0,0 +1,86 @@ +// $Id: separable.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. +*/ + +// ---------------------------------------------------------------------- +// +// SeparableAllocator: Separable Allocator Base Class +// +// ---------------------------------------------------------------------- + +#include "separable.hpp" + +#include <sstream> + +#include "arbiter.hpp" + +SeparableAllocator::SeparableAllocator( Module* parent, const string& name, + int inputs, int outputs, + const string& arb_type ) + : SparseAllocator( parent, name, inputs, outputs ) +{ + + _input_arb.resize(inputs); + + for (int i = 0; i < inputs; ++i) { + ostringstream arb_name("arb_i"); + arb_name << i; + _input_arb[i] = Arbiter::NewArbiter(this, arb_name.str(), arb_type, outputs); + } + + _output_arb.resize(outputs); + + for (int i = 0; i < outputs; ++i) { + ostringstream arb_name("arb_o"); + arb_name << i; + _output_arb[i] = Arbiter::NewArbiter(this, arb_name.str( ), arb_type, inputs); + } + +} + +SeparableAllocator::~SeparableAllocator() { + + for (int i = 0; i < _inputs; ++i) { + delete _input_arb[i]; + } + + for (int i = 0; i < _outputs; ++i) { + delete _output_arb[i]; + } + +} + +void SeparableAllocator::Clear() { + for ( int i = 0 ; i < _inputs ; i++ ) { + if(_input_arb[i]-> _num_reqs) + _input_arb[i]->Clear(); + } + for ( int o = 0; o < _outputs; o++ ) { + if(_output_arb[o]->_num_reqs) + _output_arb[o]->Clear(); + } + SparseAllocator::Clear(); +} diff --git a/src/intersim2/allocators/separable.hpp b/src/intersim2/allocators/separable.hpp new file mode 100644 index 0000000..afd1efc --- /dev/null +++ b/src/intersim2/allocators/separable.hpp @@ -0,0 +1,61 @@ +// $Id: separable.hpp 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. +*/ + +// ---------------------------------------------------------------------- +// +// SeparableAllocator: Separable Allocator Base Class +// +// ---------------------------------------------------------------------- + +#ifndef _SEPARABLE_HPP_ +#define _SEPARABLE_HPP_ + +#include <vector> + +#include "allocator.hpp" + +class Arbiter; + +class SeparableAllocator : public SparseAllocator { + +protected: + + vector<Arbiter*> _input_arb ; + vector<Arbiter*> _output_arb ; + +public: + + SeparableAllocator( Module* parent, const string& name, int inputs, + int outputs, const string& arb_type ) ; + + virtual ~SeparableAllocator() ; + + virtual void Clear() ; + +} ; + +#endif diff --git a/src/intersim2/allocators/separable_input_first.cpp b/src/intersim2/allocators/separable_input_first.cpp new file mode 100644 index 0000000..3a682fa --- /dev/null +++ b/src/intersim2/allocators/separable_input_first.cpp @@ -0,0 +1,103 @@ +// $Id: separable_input_first.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. +*/ + +// ---------------------------------------------------------------------- +// +// SeparableInputFirstAllocator: Separable Input-First Allocator +// +// ---------------------------------------------------------------------- + +#include "separable_input_first.hpp" + +#include "booksim.hpp" +#include "arbiter.hpp" + +#include <vector> +#include <iostream> +#include <cstring> + +SeparableInputFirstAllocator:: +SeparableInputFirstAllocator( Module* parent, const string& name, int inputs, + int outputs, const string& arb_type ) + : SeparableAllocator( parent, name, inputs, outputs, arb_type ) +{} + +void SeparableInputFirstAllocator::Allocate() { + + set<int>::const_iterator port_iter = _in_occ.begin(); + while(port_iter != _in_occ.end()) { + + const int & input = *port_iter; + + // add requests to the input arbiter + + map<int, sRequest>::const_iterator req_iter = _in_req[input].begin(); + while(req_iter != _in_req[input].end()) { + + const sRequest & req = req_iter->second; + + _input_arb[input]->AddRequest(req.port, req.label, req.in_pri); + + ++req_iter; + } + + // Execute the input arbiters and propagate the grants to the + // output arbiters. + + int label = -1; + const int output = _input_arb[input]->Arbitrate(&label, NULL); + assert(output > -1); + + const sRequest & req = _out_req[output][input]; + assert((req.port == input) && (req.label == label)); + + _output_arb[output]->AddRequest(req.port, req.label, req.out_pri); + + ++port_iter; + } + + port_iter = _out_occ.begin(); + while(port_iter != _out_occ.end()) { + + const int & output = *port_iter; + + // Execute the output arbiters. + + const int input = _output_arb[output]->Arbitrate(NULL, NULL); + + if(input > -1) { + assert((_inmatch[input] == -1) && (_outmatch[output] == -1)); + + _inmatch[input] = output ; + _outmatch[output] = input ; + _input_arb[input]->UpdateState() ; + _output_arb[output]->UpdateState() ; + } + + ++port_iter; + } +} diff --git a/src/intersim2/allocators/separable_input_first.hpp b/src/intersim2/allocators/separable_input_first.hpp new file mode 100644 index 0000000..c9ded06 --- /dev/null +++ b/src/intersim2/allocators/separable_input_first.hpp @@ -0,0 +1,52 @@ +// $Id: separable_input_first.hpp 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. +*/ + +// ---------------------------------------------------------------------- +// +// SeparableInputFirstAllocator: Separable Input-First Allocator +// +// ---------------------------------------------------------------------- + +#ifndef _SEPARABLE_INPUT_FIRST_HPP_ +#define _SEPARABLE_INPUT_FIRST_HPP_ + +#include <set> + +#include "separable.hpp" + +class SeparableInputFirstAllocator : public SeparableAllocator { + +public: + + SeparableInputFirstAllocator( Module* parent, const string& name, int inputs, + int outputs, const string& arb_type ) ; + + virtual void Allocate() ; + +} ; + +#endif diff --git a/src/intersim2/allocators/separable_output_first.cpp b/src/intersim2/allocators/separable_output_first.cpp new file mode 100644 index 0000000..b72658f --- /dev/null +++ b/src/intersim2/allocators/separable_output_first.cpp @@ -0,0 +1,103 @@ +// $Id: separable_output_first.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. +*/ + +// ---------------------------------------------------------------------- +// +// SeparableOutputFirstAllocator: Separable Output-First Allocator +// +// ---------------------------------------------------------------------- + +#include "separable_output_first.hpp" + +#include "booksim.hpp" +#include "arbiter.hpp" + +#include <vector> +#include <iostream> +#include <cstring> + +SeparableOutputFirstAllocator:: +SeparableOutputFirstAllocator( Module* parent, const string& name, int inputs, + int outputs, const string& arb_type ) + : SeparableAllocator( parent, name, inputs, outputs, arb_type ) +{} + +void SeparableOutputFirstAllocator::Allocate() { + + set<int>::const_iterator port_iter = _out_occ.begin(); + while(port_iter != _out_occ.end()) { + + const int & output = *port_iter; + + // add requests to the output arbiter + + map<int, sRequest>::const_iterator req_iter = _out_req[output].begin(); + while(req_iter != _out_req[output].end()) { + + const sRequest & req = req_iter->second; + + _output_arb[output]->AddRequest(req.port, req.label, req.out_pri); + + ++req_iter; + } + + // Execute the output arbiter and propagate the grants to the + // input arbiters. + + int label = -1; + const int input = _output_arb[output]->Arbitrate(&label, NULL); + assert(input > -1); + + const sRequest & req = _in_req[input][output]; + assert((req.port == output) && (req.label == label)); + + _input_arb[input]->AddRequest(req.port, req.label, req.in_pri); + + ++port_iter; + } + + port_iter = _in_occ.begin(); + while(port_iter != _in_occ.end()) { + + const int & input = *port_iter; + + // Execute the input arbiters. + + const int output = _input_arb[input]->Arbitrate(NULL, NULL); + + if(output > -1) { + assert((_inmatch[input] == -1) && (_outmatch[output] == -1)); + + _inmatch[input] = output; + _outmatch[output] = input; + _input_arb[input]->UpdateState() ; + _output_arb[output]->UpdateState() ; + } + + ++port_iter; + } +} diff --git a/src/intersim2/allocators/separable_output_first.hpp b/src/intersim2/allocators/separable_output_first.hpp new file mode 100644 index 0000000..1103f0d --- /dev/null +++ b/src/intersim2/allocators/separable_output_first.hpp @@ -0,0 +1,50 @@ +// $Id: separable_output_first.hpp 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. +*/ + +// ---------------------------------------------------------------------- +// +// SeparableOutputFirstAllocator: Separable Output-First Allocator +// +// ---------------------------------------------------------------------- + +#ifndef _SEPARABLE_OUTPUT_FIRST_HPP_ +#define _SEPARABLE_OUTPUT_FIRST_HPP_ + +#include "separable.hpp" + +class SeparableOutputFirstAllocator : public SeparableAllocator { + +public: + + SeparableOutputFirstAllocator( Module* parent, const string& name, int inputs, + int outputs, const string& arb_type ) ; + + virtual void Allocate() ; + +} ; + +#endif diff --git a/src/intersim2/allocators/wavefront.cpp b/src/intersim2/allocators/wavefront.cpp new file mode 100644 index 0000000..39a4427 --- /dev/null +++ b/src/intersim2/allocators/wavefront.cpp @@ -0,0 +1,111 @@ +// $Id: wavefront.cpp 5262 2012-09-20 23:39:40Z 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. +*/ + +/*wavefront.cpp + * + *The wave front allocator + * + */ +#include "booksim.hpp" + +#include "wavefront.hpp" + +Wavefront::Wavefront( Module *parent, const string& name, + int inputs, int outputs, bool skip_diags ) : + DenseAllocator( parent, name, inputs, outputs ), + _last_in(-1), _last_out(-1), _skip_diags(skip_diags), + _square(max(inputs, outputs)), _pri(0), _num_requests(0) +{ +} + +void Wavefront::AddRequest( int in, int out, int label, + int in_pri, int out_pri ) +{ + DenseAllocator::AddRequest(in, out, label, in_pri, out_pri); + _num_requests++; + _last_in = in; + _last_out = out; + _priorities.insert(make_pair(out_pri, in_pri)); +} + +void Wavefront::Allocate( ) +{ + + int first_diag = -1; + + if(_num_requests == 0) + + // bypass allocator completely if there were no requests + return; + + if(_num_requests == 1) { + + // if we only had a single request, we can immediately grant it + _inmatch[_last_in] = _last_out; + _outmatch[_last_out] = _last_in; + first_diag = _last_in + _last_out; + + } else { + + // otherwise we have to loop through the diagonals of request matrix + + for(set<pair<int, int> >::const_reverse_iterator iter = + _priorities.rbegin(); + iter != _priorities.rend(); ++iter) { + + for ( int p = 0; p < _square; ++p ) { + for ( int output = 0; output < _square; ++output ) { + int input = ( ( _pri + p ) + ( _square - output ) ) % _square; + if ( ( input < _inputs ) && ( output < _outputs ) && + ( _inmatch[input] == -1 ) && ( _outmatch[output] == -1 ) && + ( _request[input][output].label != -1 ) && + ( _request[input][output].in_pri == iter->second ) && + ( _request[input][output].out_pri == iter->first ) ) { + // Grant! + _inmatch[input] = output; + _outmatch[output] = input; + if(first_diag < 0) { + first_diag = input + output; + } + } + } + } + } + } + + _num_requests = 0; + _last_in = -1; + _last_out = -1; + _priorities.clear(); + + assert(first_diag >= 0); + + // Round-robin the priority diagonal + _pri = ( ( _skip_diags ? first_diag : _pri ) + 1 ) % _square; +} + + diff --git a/src/intersim2/allocators/wavefront.hpp b/src/intersim2/allocators/wavefront.hpp new file mode 100644 index 0000000..0c36a36 --- /dev/null +++ b/src/intersim2/allocators/wavefront.hpp @@ -0,0 +1,57 @@ +// $Id: wavefront.hpp 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. +*/ + +#ifndef _WAVEFRONT_HPP_ +#define _WAVEFRONT_HPP_ + +#include <set> + +#include "allocator.hpp" + +class Wavefront : public DenseAllocator { + +private: + int _last_in; + int _last_out; + set<pair<int, int> > _priorities; + bool _skip_diags; + +protected: + int _square; + int _pri; + int _num_requests; + +public: + Wavefront( Module *parent, const string& name, + int inputs, int outputs, bool skip_diags = false ); + + virtual void AddRequest( int in, int out, int label = 1, + int in_pri = 0, int out_pri = 0 ); + virtual void Allocate( ); +}; + +#endif |