benchmarks initial commit

1 files changed, 341 insertions, 0 deletions

diff --git a/benchmarks/towers/towers_main.c b/benchmarks/towers/towers_main.c
new file mode 100644
index 0000000..36526a2
--- /dev/null
+++ b/benchmarks/towers/towers_main.c
@@ -0,0 +1,341 @@
+//**************************************************************************
+// Towers of Hanoi benchmark
+//--------------------------------------------------------------------------
+//
+// Towers of Hanoi is a classic puzzle problem. The game consists of
+// three pegs and a set of discs. Each disc is a different size, and
+// initially all of the discs are on the left most peg with the smallest
+// disc on top and the largest disc on the bottom. The goal is to move all
+// of the discs onto the right most peg. The catch is that you are only
+// allowed to move one disc at a time and you can never place a larger
+// disc on top of a smaller disc.
+//
+// This implementation starts with NUM_DISC discs and uses a recursive
+// algorithm to sovel the puzzle.  The smips-gcc toolchain does not support
+// system calls so printf's can only be used on a host system, not on the
+// smips processor simulator itself. You should not change anything except
+// the HOST_DEBUG and PREALLOCATE macros for your timing run.
+
+//--------------------------------------------------------------------------
+// Macros
+
+// Set HOST_DEBUG to 1 if you are going to compile this for a host
+// machine (ie Athena/Linux) for debug purposes and set HOST_DEBUG
+// to 0 if you are compiling with the smips-gcc toolchain.
+
+#ifndef HOST_DEBUG
+#define HOST_DEBUG 0
+#endif
+
+// Set PREALLOCATE to 1 if you want to preallocate the benchmark
+// function before starting stats. If you have instruction/data
+// caches and you don't want to count the overhead of misses, then
+// you will need to use preallocation.
+
+#ifndef PREALLOCATE
+#define PREALLOCATE 0
+#endif
+
+// Set SET_STATS to 1 if you want to carve out the piece that actually
+// does the computation.
+
+#ifndef SET_STATS
+#define SET_STATS 0
+#endif
+
+// This is the number of discs in the puzzle.
+
+#define NUM_DISCS  7
+
+//--------------------------------------------------------------------------
+// Helper functions
+
+void finishTest( int toHostValue )
+{
+#if HOST_DEBUG
+  if ( toHostValue == 1 )
+    printf( "*** PASSED ***\n" );
+  else
+    printf( "*** FAILED *** (tohost = %d)\n", toHostValue );
+  exit(0);
+#else
+  asm( "mtpcr %0, cr30" : : "r" (toHostValue) );
+  while ( 1 ) { }
+#endif
+}
+
+void setStats( int enable )
+{
+#if ( !HOST_DEBUG && SET_STATS )
+  asm( "mtpcr %0, cr10" : : "r" (enable) );
+#endif
+}
+
+//--------------------------------------------------------------------------
+// List data structure and functions
+
+struct Node
+{
+  int val;
+  struct Node* next;
+};
+
+struct List
+{
+  int size;
+  struct Node* head;
+};
+
+struct List g_nodeFreeList;
+struct Node g_nodePool[NUM_DISCS];
+
+int list_getSize( struct List* list )
+{
+  return list->size;
+}
+
+void list_init( struct List* list )
+{
+  list->size = 0;
+  list->head = 0;
+}
+
+void list_push( struct List* list, int val )
+{
+  struct Node* newNode;
+
+  // Pop the next free node off the free list
+  newNode = g_nodeFreeList.head;
+  g_nodeFreeList.head = g_nodeFreeList.head->next;
+
+  // Push the new node onto the given list
+  newNode->next = list->head;
+  list->head = newNode;
+
+  // Assign the value
+  list->head->val = val;
+
+  // Increment size
+  list->size++;
+
+}
+
+int list_pop( struct List* list )
+{
+  struct Node* freedNode;
+  int val;
+
+  // Get the value from the->head of given list
+  val = list->head->val;
+
+  // Pop the head node off the given list
+  freedNode = list->head;
+  list->head = list->head->next;
+
+  // Push the freed node onto the free list
+  freedNode->next = g_nodeFreeList.head;
+  g_nodeFreeList.head = freedNode;
+
+  // Decrement size
+  list->size--;
+
+  return val;
+}
+
+void list_clear( struct List* list )
+{
+  while ( list_getSize(list) > 0 )
+    list_pop(list);
+}
+
+//--------------------------------------------------------------------------
+// Tower data structure and functions
+
+struct Towers
+{
+  int numDiscs;
+  int numMoves;
+  struct List pegA;
+  struct List pegB;
+  struct List pegC;
+};
+
+void towers_init( struct Towers* this, int n )
+{
+  int i;
+
+  this->numDiscs = n;
+  this->numMoves = 0;
+
+  list_init( &(this->pegA) );
+  list_init( &(this->pegB) );
+  list_init( &(this->pegC) );
+
+  for ( i = 0; i < n; i++ )
+    list_push( &(this->pegA), n-i );
+
+}
+
+void towers_clear( struct Towers* this )
+{
+
+  list_clear( &(this->pegA) );
+  list_clear( &(this->pegB) );
+  list_clear( &(this->pegC) );
+
+  towers_init( this, this->numDiscs );
+
+}
+
+#if HOST_DEBUG
+void towers_print( struct Towers* this )
+{
+  struct Node* ptr;
+  int i, numElements;
+
+  printf( "  pegA: " );
+  for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegA))); i++ )
+    printf( ". " );
+  for ( ptr = this->pegA.head; ptr != 0; ptr = ptr->next )
+    printf( "%d ", ptr->val );
+
+  printf( "  pegB: " );
+  for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegB))); i++ )
+    printf( ". " );
+  for ( ptr = this->pegB.head; ptr != 0; ptr = ptr->next )
+    printf( "%d ", ptr->val );
+
+  printf( "  pegC: " );
+  for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegC))); i++ )
+    printf( ". " );
+  for ( ptr = this->pegC.head; ptr != 0; ptr = ptr->next )
+    printf( "%d ", ptr->val );
+
+  printf( "\n" );
+}
+#endif
+
+void towers_solve_h( struct Towers* this, int n,
+                     struct List* startPeg,
+                     struct List* tempPeg,
+                     struct List* destPeg )
+{
+  int val;
+
+  if ( n == 1 ) {
+#if HOST_DEBUG
+    towers_print(this);
+#endif
+    val = list_pop(startPeg);
+    list_push(destPeg,val);
+    this->numMoves++;
+  }
+  else {
+    towers_solve_h( this, n-1, startPeg, destPeg,  tempPeg );
+    towers_solve_h( this, 1,   startPeg, tempPeg,  destPeg );
+    towers_solve_h( this, n-1, tempPeg,  startPeg, destPeg );
+  }
+
+}
+
+void towers_solve( struct Towers* this )
+{
+  towers_solve_h( this, this->numDiscs, &(this->pegA), &(this->pegB), &(this->pegC) );
+}
+
+int towers_verify( struct Towers* this )
+{
+  struct Node* ptr;
+  int numDiscs = 0;
+
+  if ( list_getSize(&this->pegA) != 0 ) {
+#if HOST_DEBUG
+    printf( "ERROR: Peg A is not empty!\n" );
+#endif
+    return 2;
+  }
+
+  if ( list_getSize(&this->pegB) != 0 ) {
+#if HOST_DEBUG
+    printf( "ERROR: Peg B is not empty!\n" );
+#endif
+    return 3;
+  }
+
+  if ( list_getSize(&this->pegC) != this->numDiscs ) {
+#if HOST_DEBUG
+    printf( " ERROR: Expected %d discs but found only %d discs!\n", \
+            this->numDiscs, list_getSize(&this->pegC) );
+#endif
+    return 4;
+  }
+
+  for ( ptr = this->pegC.head; ptr != 0; ptr = ptr->next ) {
+    numDiscs++;
+    if ( ptr->val != numDiscs ) {
+#if HOST_DEBUG
+      printf( " ERROR: Expecting disc %d on peg C but found disc %d instead!\n", \
+              numDiscs, ptr->val );
+#endif
+      return 5;
+    }
+  }
+
+  if ( this->numMoves != ((1 << this->numDiscs) - 1) ) {
+#if HOST_DEBUG
+    printf( " ERROR: Expecting %d num moves but found %d instead!\n", \
+            ((1 << this->numDiscs) - 1), this->numMoves );
+#endif
+    return 6;
+  }
+
+  return 1;
+}
+
+//--------------------------------------------------------------------------
+// Main
+
+int main( int argc, char* argv[] )
+{
+  struct Towers towers;
+  int i;
+
+  // Initialize free list
+
+  list_init( &g_nodeFreeList );
+  g_nodeFreeList.head = &(g_nodePool[0]);
+  g_nodeFreeList.size = NUM_DISCS;
+  g_nodePool[NUM_DISCS-1].next = 0;
+  g_nodePool[NUM_DISCS-1].val = 99;
+  for ( i = 0; i < (NUM_DISCS-1); i++ ) {
+    g_nodePool[i].next = &(g_nodePool[i+1]);
+    g_nodePool[i].val = i;
+  }
+
+  towers_init( &towers, NUM_DISCS );
+
+  // If needed we preallocate everything in the caches
+
+#if PREALLOCATE
+  towers_solve( &towers );
+#endif
+
+  // Solve it
+
+  towers_clear( &towers );
+  setStats(1);
+  towers_solve( &towers );
+  setStats(0);
+
+  // Print out the results
+
+#if HOST_DEBUG
+  towers_print( &towers );
+#endif
+
+  // Check the results
+
+  finishTest( towers_verify( &towers ) );
+
+}
+