1 files changed, 207 insertions, 0 deletions
diff --git a/src/intersim/selalloc.cpp b/src/intersim/selalloc.cpp
new file mode 100644
index 0000000..53d31fe
--- /dev/null
+++ b/src/intersim/selalloc.cpp
@@ -0,0 +1,207 @@
+#include "booksim.hpp"
+#include <iostream>
+
+#include "selalloc.hpp"
+#include "random_utils.hpp"
+
+//#define DEBUG_SELALLOC
+
+SelAlloc::SelAlloc( const Configuration &config,
+                    Module *parent, const string& name,
+                    int inputs, int outputs ) :
+SparseAllocator( config, parent, name, inputs, outputs )
+{
+   _iter = config.GetInt( "alloc_iters" );
+
+   _grants = new int [_outputs];
+   _gptrs  = new int [_outputs];
+   _aptrs  = new int [_inputs];
+
+   for ( int i = 0; i < _inputs; ++i ) {
+      _aptrs[i] = 0;
+   }
+   for ( int j = 0; j < _outputs; ++j ) {
+      _gptrs[j] = 0;
+   }
+}
+
+SelAlloc::~SelAlloc( )
+{
+   delete [] _grants;
+   delete [] _aptrs;
+   delete [] _gptrs;
+}
+
+void SelAlloc::Allocate( )
+{
+   int input;
+   int output;
+
+   int input_offset;
+   int output_offset;
+
+   list<sRequest>::iterator p;
+   list<int>::iterator outer_iter;
+   bool wrapped;
+
+   int max_index;
+   int max_pri;
+
+   _ClearMatching( );
+
+   for ( int i = 0; i < _outputs; ++i ) {
+      _grants[i] = -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->port < input_offset ) ) {
+            p++;
+         }
+
+         max_index = -1;
+         max_pri   = 0;
+
+         wrapped = false;
+         while ( (!wrapped) || ( p->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->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->out_pri > max_pri ) || ( max_index == -1 ) ) ) {
+               max_pri   = p->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->port < output_offset ) ) {
+            p++;
+         }
+
+         max_index = -1;
+         max_pri   = 0;
+
+         wrapped = false;
+         while ( (!wrapped) || ( p->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->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->in_pri > max_pri ) || ( max_index == -1 ) ) ) {
+               max_pri   = p->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 
+}