From 69f2911e04ffb1b19eef1fafb8c040af271f656e Mon Sep 17 00:00:00 2001
From: Tor Aamodt <aamodt@ece.ubc.ca>
Date: Thu, 15 Jul 2010 18:09:46 -0800
Subject: creating branch for adding support for CUDA 3.x and Fermi

[git-p4: depot-paths = "//depot/gpgpu_sim_research/fermi/distribution/": change = 6829]
---
 src/intersim/maxsize.cpp | 181 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 181 insertions(+)
 create mode 100644 src/intersim/maxsize.cpp

(limited to 'src/intersim/maxsize.cpp')

diff --git a/src/intersim/maxsize.cpp b/src/intersim/maxsize.cpp
new file mode 100644
index 0000000..3d1349a
--- /dev/null
+++ b/src/intersim/maxsize.cpp
@@ -0,0 +1,181 @@
+#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( const Configuration &config,
+                            Module *parent, const string& name,
+                            int inputs, int outputs ) :
+DenseAllocator( config, parent, name, inputs, outputs )
+{
+   _from = new int [_outputs];
+   _s    = new int [_inputs];
+   _ns   = new int [_inputs];
+}
+
+MaxSizeMatch::~MaxSizeMatch( )
+{
+   delete [] _from;
+   delete [] _s;
+   delete [] _ns;
+}
+
+void MaxSizeMatch::Allocate( )
+{
+   // clear matching
+   for ( int i = 0; i < _inputs; ++i ) {
+      _inmatch[i] = -1;
+   }
+   for ( int j = 0; j < _outputs; ++j ) {
+      _outmatch[j] = -1;
+   }
+
+   // augment as many times as possible 
+   // (this is an O(N^3) maximum-size matching algorithm)
+   while ( _ShortestAugmenting( ) );
+}
+
+
+bool MaxSizeMatch::_ShortestAugmenting( )
+{
+   int i, j, jn;
+   int slen, nslen;
+   int *t;
+
+   slen = 0;
+   for ( i = 0; i < _inputs; ++i ) {
+      if ( _inmatch[i] == -1 ) { // start with unmatched left nodes
+         _s[slen] = i;
+         slen++;
+      }
+      _from[i] = -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
+      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;
+}
-- 
cgit v1.3