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/arbiters/arbiter.cpp | 111 +++++++++++++++++++++ src/intersim2/arbiters/arbiter.hpp | 86 ++++++++++++++++ src/intersim2/arbiters/matrix_arb.cpp | 121 ++++++++++++++++++++++ src/intersim2/arbiters/matrix_arb.hpp | 71 +++++++++++++ src/intersim2/arbiters/prio_arb.cpp | 160 ++++++++++++++++++++++++++++++ src/intersim2/arbiters/prio_arb.hpp | 68 +++++++++++++ src/intersim2/arbiters/roundrobin_arb.cpp | 80 +++++++++++++++ src/intersim2/arbiters/roundrobin_arb.hpp | 75 ++++++++++++++ src/intersim2/arbiters/tree_arb.cpp | 119 ++++++++++++++++++++++ src/intersim2/arbiters/tree_arb.hpp | 71 +++++++++++++ 10 files changed, 962 insertions(+) create mode 100644 src/intersim2/arbiters/arbiter.cpp create mode 100644 src/intersim2/arbiters/arbiter.hpp create mode 100644 src/intersim2/arbiters/matrix_arb.cpp create mode 100644 src/intersim2/arbiters/matrix_arb.hpp create mode 100644 src/intersim2/arbiters/prio_arb.cpp create mode 100644 src/intersim2/arbiters/prio_arb.hpp create mode 100644 src/intersim2/arbiters/roundrobin_arb.cpp create mode 100644 src/intersim2/arbiters/roundrobin_arb.hpp create mode 100644 src/intersim2/arbiters/tree_arb.cpp create mode 100644 src/intersim2/arbiters/tree_arb.hpp (limited to 'src/intersim2/arbiters') diff --git a/src/intersim2/arbiters/arbiter.cpp b/src/intersim2/arbiters/arbiter.cpp new file mode 100644 index 0000000..5b4b38f --- /dev/null +++ b/src/intersim2/arbiters/arbiter.cpp @@ -0,0 +1,111 @@ +// $Id: arbiter.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. +*/ + +// ---------------------------------------------------------------------- +// +// Arbiter: Base class for Matrix and Round Robin Arbiter +// +// ---------------------------------------------------------------------- + +#include "arbiter.hpp" +#include "roundrobin_arb.hpp" +#include "matrix_arb.hpp" +#include "tree_arb.hpp" + +#include +#include + +using namespace std ; + +Arbiter::Arbiter( Module *parent, const string &name, int size ) + : Module( parent, name ), + _size(size), _selected(-1), _highest_pri(numeric_limits::min()), + _best_input(-1), _num_reqs(0) +{ + _request.resize(size); + for ( int i = 0 ; i < size ; i++ ) + _request[i].valid = false ; +} + +void Arbiter::AddRequest( int input, int id, int pri ) +{ + assert( 0 <= input && input < _size ) ; + assert( !_request[input].valid ); + + _num_reqs++ ; + _request[input].valid = true ; + _request[input].id = id ; + _request[input].pri = pri ; +} + +int Arbiter::Arbitrate( int* id, int* pri ) +{ + if ( _selected != -1 ) { + if ( id ) + *id = _request[_selected].id ; + if ( pri ) + *pri = _request[_selected].pri ; + } + + assert((_selected >= 0) || (_num_reqs == 0)); + + return _selected ; +} + +void Arbiter::Clear() +{ + if(_num_reqs > 0) { + + // clear the request vector + for ( int i = 0; i < _size ; i++ ) + _request[i].valid = false ; + _num_reqs = 0 ; + _selected = -1; + } +} + +Arbiter *Arbiter::NewArbiter( Module *parent, const string& name, + const string &arb_type, int size) +{ + Arbiter *a = NULL; + if(arb_type == "round_robin") { + a = new RoundRobinArbiter( parent, name, size ); + } else if(arb_type == "matrix") { + a = new MatrixArbiter( parent, name, size ); + } else if(arb_type.substr(0, 5) == "tree(") { + size_t left = 4; + size_t middle = arb_type.find_first_of(','); + assert(middle != string::npos); + size_t right = arb_type.find_last_of(')'); + assert(right != string::npos); + string groups_str = arb_type.substr(left+1, middle-left-1); + int groups = atoi(groups_str.c_str()); + string sub_arb_type = arb_type.substr(middle+1, right-middle-1); + a = new TreeArbiter( parent, name, size, groups, sub_arb_type ); + } else assert(false); + return a; +} diff --git a/src/intersim2/arbiters/arbiter.hpp b/src/intersim2/arbiters/arbiter.hpp new file mode 100644 index 0000000..456bd8f --- /dev/null +++ b/src/intersim2/arbiters/arbiter.hpp @@ -0,0 +1,86 @@ +// $Id: arbiter.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. +*/ + +// ---------------------------------------------------------------------- +// +// Arbiter: Base class for Matrix and Round Robin Arbiter +// +// ---------------------------------------------------------------------- + +#ifndef _ARBITER_HPP_ +#define _ARBITER_HPP_ + +#include + +#include "module.hpp" + +class Arbiter : public Module { + +protected: + + typedef struct { + bool valid ; + int id ; + int pri ; + } entry_t ; + + vector _request ; + int _size ; + + int _selected ; + int _highest_pri; + int _best_input; + +public: + int _num_reqs ; + // Constructors + Arbiter( Module *parent, const string &name, int size ) ; + + // Print priority matrix to standard output + virtual void PrintState() const = 0 ; + + // Register request with arbiter + virtual void AddRequest( int input, int id, int pri ) ; + + // Update priority matrix based on last aribtration result + virtual void UpdateState() = 0 ; + + // Arbitrate amongst requests. Returns winning input and + // updates pointers to metadata when valid pointers are passed + virtual int Arbitrate( int* id = 0, int* pri = 0 ) ; + + virtual void Clear(); + + inline int LastWinner() const { + return _selected; + } + + static Arbiter *NewArbiter( Module *parent, const string &name, + const string &arb_type, int size ); +} ; + +#endif diff --git a/src/intersim2/arbiters/matrix_arb.cpp b/src/intersim2/arbiters/matrix_arb.cpp new file mode 100644 index 0000000..d087e19 --- /dev/null +++ b/src/intersim2/arbiters/matrix_arb.cpp @@ -0,0 +1,121 @@ +// $Id: matrix_arb.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. +*/ + +// ---------------------------------------------------------------------- +// +// Matrix: Matrix Arbiter +// +// ---------------------------------------------------------------------- + +#include "matrix_arb.hpp" +#include +using namespace std ; + +MatrixArbiter::MatrixArbiter( Module *parent, const string &name, int size ) + : Arbiter( parent, name, size ), _last_req(-1) { + _matrix.resize(size); + for ( int i = 0 ; i < size ; i++ ) { + _matrix[i].resize(size); + for ( int j = 0; j < i; j++ ) { + _matrix[i][j] = 1; + } + } +} + +void MatrixArbiter::PrintState() const { + cout << "Priority Matrix: " << endl ; + for ( int r = 0; r < _size ; r++ ) { + for ( int c = 0 ; c < _size ; c++ ) { + cout << _matrix[r][c] << " " ; + } + cout << endl ; + } + cout << endl ; +} + +void MatrixArbiter::UpdateState() { + // update priority matrix using last grant + if ( _selected > -1 ) { + for ( int i = 0; i < _size ; i++ ) { + if( _selected != i ) { + _matrix[_selected][i] = 0 ; + _matrix[i][_selected] = 1 ; + } + } + } +} + +void MatrixArbiter::AddRequest( int input, int id, int pri ) +{ + _last_req = input; + Arbiter::AddRequest(input, id, pri); +} + +int MatrixArbiter::Arbitrate( int* id, int* pri ) { + + // avoid running arbiter if it has not recevied at least two requests + // (in this case, requests and grants are identical) + if ( _num_reqs < 2 ) { + + _selected = _last_req ; + + } else { + + _selected = -1 ; + + for ( int input = 0 ; input < _size ; input++ ) { + if(_request[input].valid) { + + bool grant = true; + for ( int i = 0 ; i < _size ; i++ ) { + if ( _request[i].valid && + ( ( ( _request[i].pri == _request[input].pri ) && + _matrix[i][input]) || + ( _request[i].pri > _request[input].pri ) + ) ) { + grant = false ; + break ; + } + } + + if ( grant ) { + _selected = input ; + break ; + } + } + + } + } + + return Arbiter::Arbitrate(id, pri); +} + +void MatrixArbiter::Clear() +{ + _last_req = -1; + Arbiter::Clear(); +} diff --git a/src/intersim2/arbiters/matrix_arb.hpp b/src/intersim2/arbiters/matrix_arb.hpp new file mode 100644 index 0000000..53d3724 --- /dev/null +++ b/src/intersim2/arbiters/matrix_arb.hpp @@ -0,0 +1,71 @@ +// $Id: matrix_arb.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. +*/ + +// ---------------------------------------------------------------------- +// +// Matrix: Matrix Arbiter +// +// ---------------------------------------------------------------------- + +#ifndef _MATRIX_ARB_HPP_ +#define _MATRIX_ARB_HPP_ + +#include + +#include "arbiter.hpp" + +using namespace std; + +class MatrixArbiter : public Arbiter { + + // Priority matrix + vector > _matrix ; + + int _last_req ; + +public: + + // Constructors + MatrixArbiter( Module *parent, const string &name, int size ) ; + + // Print priority matrix to standard output + virtual void PrintState() const ; + + // Update priority matrix based on last aribtration result + virtual void UpdateState() ; + + // Arbitrate amongst requests. Returns winning input and + // updates pointers to metadata when valid pointers are passed + virtual int Arbitrate( int* id = 0, int* pri = 0) ; + + virtual void AddRequest( int input, int id, int pri ) ; + + virtual void Clear(); + +} ; + +#endif diff --git a/src/intersim2/arbiters/prio_arb.cpp b/src/intersim2/arbiters/prio_arb.cpp new file mode 100644 index 0000000..9de2bc2 --- /dev/null +++ b/src/intersim2/arbiters/prio_arb.cpp @@ -0,0 +1,160 @@ +// $Id: prio_arb.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 "prio_arb.hpp" + + +PriorityArbiter::PriorityArbiter( const Configuration &config, + Module *parent, const string& name, + int inputs ) +: Module( parent, name ), _rr_ptr(0), _inputs( inputs ) +{ + +} + +void PriorityArbiter::Clear( ) +{ + _requests.clear( ); +} + +void PriorityArbiter::AddRequest( int in, int label, int pri ) +{ + sRequest r; + list::iterator insert_point; + + r.in = in; r.label = label; r.pri = pri; + + insert_point = _requests.begin( ); + while( ( insert_point != _requests.end( ) ) && + ( insert_point->in < in ) ) { + insert_point++; + } + + bool del = false; + bool add = true; + + // For consistant behavior, delete the existing request + // if it is for the same input and has a higher + // priority + + if ( ( insert_point != _requests.end( ) ) && + ( insert_point->in == in ) ) { + if ( insert_point->pri < pri ) { + del = true; + } else { + add = false; + } + } + + if ( add ) { + _requests.insert( insert_point, r ); + } + + if ( del ) { + _requests.erase( insert_point ); + } +} + +void PriorityArbiter::RemoveRequest( int in, int label ) +{ + list::iterator erase_point; + + erase_point = _requests.begin( ); + while( ( erase_point != _requests.end( ) ) && + ( erase_point->in < in ) ) { + erase_point++; + } + + assert( erase_point != _requests.end( ) ); + _requests.erase( erase_point ); +} + +int PriorityArbiter::Match( ) const +{ + return _match; +} + +void PriorityArbiter::Arbitrate( ) +{ + list::iterator p; + + int max_index, max_pri; + bool wrapped; + + //MERGENOTE + //booksim does not have this if statement + //as far as I can tell they are identical in function + if ( _requests.begin( ) != _requests.end( ) ) { + // A round-robin arbiter between input requests + p = _requests.begin( ); + while( ( p != _requests.end( ) ) && + ( p->in < _rr_ptr ) ) { + p++; + } + + max_index = -1; + max_pri = 0; + + wrapped = false; + while( (!wrapped) || ( p->in < _rr_ptr ) ) { + if ( p == _requests.end( ) ) { + if ( wrapped ) { break; } + // p is valid here because empty lists + // are skipped (above) + p = _requests.begin( ); + wrapped = true; + } + + // check if request is the highest priority so far + if ( ( p->pri > max_pri ) || ( max_index == -1 ) ) { + max_pri = p->pri; + max_index = p->in; + } + + p++; + } + + _match = max_index; // -1 for no match + if ( _match != -1 ) { + _rr_ptr = ( _match + 1 ) % _inputs; + } + + } else { + _match = -1; + } +} + +//MERGENOTE +//added update function to priorityarbiter + +void PriorityArbiter::Update( ) +{ + _rr_ptr = ( _rr_ptr + 1 ) % _inputs; +} diff --git a/src/intersim2/arbiters/prio_arb.hpp b/src/intersim2/arbiters/prio_arb.hpp new file mode 100644 index 0000000..0f7b737 --- /dev/null +++ b/src/intersim2/arbiters/prio_arb.hpp @@ -0,0 +1,68 @@ +// $Id: prio_arb.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 _PRIO_ARB_HPP_ +#define _PRIO_ARB_HPP_ + +#include + +#include "module.hpp" +#include "config_utils.hpp" + +class PriorityArbiter : public Module { + int _rr_ptr; + +protected: + const int _inputs; + + struct sRequest { + int in; + int label; + int pri; + }; + + list _requests; + + int _match; + +public: + PriorityArbiter( const Configuration &config, + Module *parent, const string& name, + int inputs ); + + void Clear( ); + + void AddRequest( int in, int label = 0, int pri = 0 ); + void RemoveRequest( int in, int label = 0 ); + + int Match( ) const; + + void Arbitrate( ); + void Update( ); +}; + +#endif diff --git a/src/intersim2/arbiters/roundrobin_arb.cpp b/src/intersim2/arbiters/roundrobin_arb.cpp new file mode 100644 index 0000000..f338381 --- /dev/null +++ b/src/intersim2/arbiters/roundrobin_arb.cpp @@ -0,0 +1,80 @@ +// $Id: roundrobin_arb.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. +*/ + +// ---------------------------------------------------------------------- +// +// RoundRobin: RoundRobin Arbiter +// +// ---------------------------------------------------------------------- + +#include "roundrobin_arb.hpp" +#include +#include + +using namespace std ; + +RoundRobinArbiter::RoundRobinArbiter( Module *parent, const string &name, + int size ) + : Arbiter( parent, name, size ), _pointer( 0 ) { +} + +void RoundRobinArbiter::PrintState() const { + cout << "Round Robin Priority Pointer: " << endl ; + cout << " _pointer = " << _pointer << endl ; +} + +void RoundRobinArbiter::UpdateState() { + // update priority matrix using last grant + if ( _selected > -1 ) + _pointer = ( _selected + 1 ) % _size ; +} + +void RoundRobinArbiter::AddRequest( int input, int id, int pri ) +{ + if(!_request[input].valid || (_request[input].pri < pri)) { + if((_num_reqs == 0) || + Supersedes(input, pri, _best_input, _highest_pri, _pointer,_size )) { + _highest_pri = pri; + _best_input = input; + } + } + Arbiter::AddRequest(input, id, pri); +} + +int RoundRobinArbiter::Arbitrate( int* id, int* pri ) { + + _selected = _best_input; + + return Arbiter::Arbitrate(id, pri); +} + +void RoundRobinArbiter::Clear() +{ + _highest_pri = numeric_limits::min(); + _best_input = -1; + Arbiter::Clear(); +} diff --git a/src/intersim2/arbiters/roundrobin_arb.hpp b/src/intersim2/arbiters/roundrobin_arb.hpp new file mode 100644 index 0000000..8062270 --- /dev/null +++ b/src/intersim2/arbiters/roundrobin_arb.hpp @@ -0,0 +1,75 @@ +// $Id: roundrobin_arb.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. +*/ + +// ---------------------------------------------------------------------- +// +// RoundRobin: Round Robin Arbiter +// +// ---------------------------------------------------------------------- + +#ifndef _ROUNDROBIN_HPP_ +#define _ROUNDROBIN_HPP_ + +#include "arbiter.hpp" + +class RoundRobinArbiter : public Arbiter { + + // Priority pointer + int _pointer ; + +public: + + // Constructors + RoundRobinArbiter( Module *parent, const string &name, int size ) ; + + // Print priority matrix to standard output + virtual void PrintState() const ; + + // Update priority matrix based on last aribtration result + virtual void UpdateState() ; + + // Arbitrate amongst requests. Returns winning input and + // updates pointers to metadata when valid pointers are passed + virtual int Arbitrate( int* id = 0, int* pri = 0) ; + + virtual void AddRequest( int input, int id, int pri ) ; + + virtual void Clear(); + + static inline bool Supersedes(int input1, int pri1, int input2, int pri2, int offset, int size) + { + // in a round-robin scheme with the given number of positions and current + // offset, should a request at input1 with priority pri1 supersede a + // request at input2 with priority pri2? + return ((pri1 > pri2) || + ((pri1 == pri2) && + (((input1 - offset + size) % size) < ((input2 - offset + size) % size)))); + } + +} ; + +#endif diff --git a/src/intersim2/arbiters/tree_arb.cpp b/src/intersim2/arbiters/tree_arb.cpp new file mode 100644 index 0000000..11033dc --- /dev/null +++ b/src/intersim2/arbiters/tree_arb.cpp @@ -0,0 +1,119 @@ +// $Id: tree_arb.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. +*/ + +// ---------------------------------------------------------------------- +// +// TreeArbiter +// +// ---------------------------------------------------------------------- + +#include "tree_arb.hpp" +#include +#include + +using namespace std ; + +TreeArbiter::TreeArbiter( Module *parent, const string &name, + int size, int groups, const string & arb_type ) + : Arbiter( parent, name, size ) { + assert(size % groups == 0); + _group_arbiters.resize(groups); + _group_reqs.resize(groups, 0); + _group_size = size / groups; + for(int i = 0; i < groups; ++i) { + ostringstream group_arb_name; + group_arb_name << "group_arb" << i; + _group_arbiters[i] = Arbiter::NewArbiter(this, group_arb_name.str(), arb_type, _group_size); + } + _global_arbiter = Arbiter::NewArbiter(this, "global_arb", arb_type, groups); +} + +TreeArbiter::~TreeArbiter() { + for(int i = 0; i < (int)_group_arbiters.size(); ++i) { + delete _group_arbiters[i]; + } + delete _global_arbiter; +} + +void TreeArbiter::PrintState() const { + for(int i = 0; i < (int)_group_arbiters.size(); ++i) { + cout << "Group arbiter " << i << ":" << endl; + _group_arbiters[i]->PrintState(); + } + cout << "Global arbiter:" << endl; + _global_arbiter->PrintState(); +} + +void TreeArbiter::UpdateState() { + if(_selected > -1) { + int last_winner = _global_arbiter->LastWinner(); + assert(last_winner >= 0 && last_winner < (int)_group_arbiters.size()); + _group_arbiters[last_winner]->UpdateState(); + _global_arbiter->UpdateState(); + } +} + +void TreeArbiter::AddRequest( int input, int id, int pri ) +{ + Arbiter::AddRequest(input, id, pri); + int group_index = input / _group_size; + _group_arbiters[group_index]->AddRequest( input % _group_size, id, pri ); + ++_group_reqs[group_index]; +} + +int TreeArbiter::Arbitrate( int* id, int* pri ) { + if(!_num_reqs) { + return -1; + } + for(int i = 0; i < (int)_group_arbiters.size(); ++i) { + if(_group_reqs[i]) { + int group_id, group_pri; + _group_arbiters[i]->Arbitrate(&group_id, &group_pri); + _global_arbiter->AddRequest(i, group_id, group_pri); + } + } + int group = _global_arbiter->Arbitrate(NULL, NULL); + assert(group >= 0 && group < (int)_group_arbiters.size()); + int group_sel = _group_arbiters[group]->LastWinner(); + assert(group_sel >= 0 && group_sel < _group_size); + _selected = group * _group_size + group_sel; + assert(_selected >= 0 && _selected < _size); + return Arbiter::Arbitrate(id, pri); +} + +void TreeArbiter::Clear() +{ + if(!_num_reqs) { + return; + } + for(int i = 0; i < (int)_group_arbiters.size(); ++i) { + _group_arbiters[i]->Clear(); + _group_reqs[i] = 0; + } + _global_arbiter->Clear(); + Arbiter::Clear(); +} diff --git a/src/intersim2/arbiters/tree_arb.hpp b/src/intersim2/arbiters/tree_arb.hpp new file mode 100644 index 0000000..4350e56 --- /dev/null +++ b/src/intersim2/arbiters/tree_arb.hpp @@ -0,0 +1,71 @@ +// $Id: tree_arb.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. +*/ + +// ---------------------------------------------------------------------- +// +// TreeArbiter +// +// ---------------------------------------------------------------------- + +#ifndef _TREE_ARB_HPP_ +#define _TREE_ARB_HPP_ + +#include "arbiter.hpp" + +class TreeArbiter : public Arbiter { + + int _group_size ; + + vector _group_arbiters; + Arbiter * _global_arbiter; + + vector _group_reqs; + +public: + + // Constructors + TreeArbiter( Module *parent, const string &name, int size, int groups, const string & arb_type ) ; + + ~TreeArbiter(); + + // Print priority matrix to standard output + virtual void PrintState() const ; + + // Update priority matrix based on last aribtration result + virtual void UpdateState() ; + + // Arbitrate amongst requests. Returns winning input and + // updates pointers to metadata when valid pointers are passed + virtual int Arbitrate( int* id = 0, int* pri = 0) ; + + virtual void AddRequest( int input, int id, int pri ) ; + + virtual void Clear(); + +} ; + +#endif -- cgit v1.3