summaryrefslogtreecommitdiff
path: root/Run.C
diff options
context:
space:
mode:
authorDoug Pase <douglas@pase.us>2007-01-22 00:00:00 +0000
committerTim Besard <tim.besard@gmail.com>2011-10-27 16:18:30 +0200
commitfb9ae8907327f93cbeed6ffef914435a4e2ec651 (patch)
tree8432c40e2e646816a83caa83091a105ac08342f6 /Run.C
Initial commit.
Diffstat (limited to 'Run.C')
-rw-r--r--Run.C761
1 files changed, 761 insertions, 0 deletions
diff --git a/Run.C b/Run.C
new file mode 100644
index 0000000..bca6485
--- /dev/null
+++ b/Run.C
@@ -0,0 +1,761 @@
+/*******************************************************************************
+ * Copyright (c) 2006 International Business Machines Corporation. *
+ * All rights reserved. This program and the accompanying materials *
+ * are made available under the terms of the Common Public License v1.0 *
+ * which accompanies this distribution, and is available at *
+ * http://www.opensource.org/licenses/cpl1.0.php *
+ * *
+ * Contributors: *
+ * Douglas M. pase - initial API and implementation *
+ *******************************************************************************/
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#if defined(NUMA)
+#include <numa.h>
+#endif
+
+#include "Run.h"
+
+#include "Chain.h"
+#include "Timer.h"
+#include "SpinBarrier.h"
+
+
+static double min( double v1, double v2 );
+
+Lock Run::global_mutex;
+int64 Run::_ops_per_chain = 0;
+double Run::_seconds = 1E9;
+
+
+Run::Run()
+: exp(NULL), bp(NULL)
+{
+}
+
+Run::~Run()
+{
+}
+
+void
+Run::set( Experiment &e, SpinBarrier* sbp )
+{
+ this->exp = &e;
+ this->bp = sbp;
+}
+
+int
+Run::run()
+{
+ // first allocate all memory for the chains,
+ // making sure it is allocated within the
+ // intended numa domains
+ Chain** chain_memory = new Chain* [ this->exp->chains_per_thread ];
+ Chain** root = new Chain* [ this->exp->chains_per_thread ];
+
+#if defined(NUMA)
+ // establish the node id where this thread
+ // will run. threads are mapped to nodes
+ // by the set-up code for Experiment.
+ int run_node_id = this->exp->thread_domain[this->thread_id()];
+ numa_run_on_node(run_node_id);
+
+ // establish the node id where this thread's
+ // memory will be allocated.
+ for (int i=0; i < this->exp->chains_per_thread; i++) {
+ int alloc_node_id = this->exp->chain_domain[this->thread_id()][i];
+ nodemask_t alloc_mask;
+ nodemask_zero(&alloc_mask);
+ nodemask_set(&alloc_mask, alloc_node_id);
+ numa_set_membind(&alloc_mask);
+
+ chain_memory[i] = new Chain[ this->exp->links_per_chain ];
+ }
+#else
+ for (int i=0; i < this->exp->chains_per_thread; i++) {
+ chain_memory[i] = new Chain[ this->exp->links_per_chain ];
+ }
+#endif
+
+ for (int i=0; i < this->exp->chains_per_thread; i++) {
+ if (this->exp->access_pattern == Experiment::RANDOM) {
+ root[i] = random_mem_init( chain_memory[i] );
+ } else if (0 < this->exp->stride) {
+ root[i] = forward_mem_init( chain_memory[i] );
+ } else {
+ root[i] = reverse_mem_init( chain_memory[i] );
+ }
+ }
+
+ // barrier
+ for (int e=-1; e <= this->exp->experiments; e++) {
+ this->bp->barrier();
+
+ // start timer
+ double start = 0;
+ if (this->thread_id() == 0) start = Timer::seconds();
+ this->bp->barrier();
+
+ // chase pointers
+ if (this->exp->chains_per_thread == 1) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ while (a != NULL) {
+ a = a->next;
+ }
+ this->mem_check( a );
+ }
+ } else if (this->exp->chains_per_thread == 2) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ }
+ } else if (this->exp->chains_per_thread == 3) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ }
+ } else if (this->exp->chains_per_thread == 4) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ }
+ } else if (this->exp->chains_per_thread == 5) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ }
+ } else if (this->exp->chains_per_thread == 6) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ Chain* f = root[5];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ f = f->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ this->mem_check( f );
+ }
+ } else if (this->exp->chains_per_thread == 7) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ Chain* f = root[5];
+ Chain* g = root[6];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ f = f->next;
+ g = g->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ this->mem_check( f );
+ this->mem_check( g );
+ }
+ } else if (this->exp->chains_per_thread == 8) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ Chain* f = root[5];
+ Chain* g = root[6];
+ Chain* h = root[7];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ f = f->next;
+ g = g->next;
+ h = h->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ this->mem_check( f );
+ this->mem_check( g );
+ this->mem_check( h );
+ }
+ } else if (this->exp->chains_per_thread == 9) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ Chain* f = root[5];
+ Chain* g = root[6];
+ Chain* h = root[7];
+ Chain* j = root[8];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ f = f->next;
+ g = g->next;
+ h = h->next;
+ j = j->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ this->mem_check( f );
+ this->mem_check( g );
+ this->mem_check( h );
+ this->mem_check( j );
+ }
+ } else if (this->exp->chains_per_thread == 10) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ Chain* f = root[5];
+ Chain* g = root[6];
+ Chain* h = root[7];
+ Chain* j = root[8];
+ Chain* k = root[9];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ f = f->next;
+ g = g->next;
+ h = h->next;
+ j = j->next;
+ k = k->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ this->mem_check( f );
+ this->mem_check( g );
+ this->mem_check( h );
+ this->mem_check( j );
+ this->mem_check( k );
+ }
+ } else if (this->exp->chains_per_thread == 11) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ Chain* f = root[5];
+ Chain* g = root[6];
+ Chain* h = root[7];
+ Chain* j = root[8];
+ Chain* k = root[9];
+ Chain* l = root[10];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ f = f->next;
+ g = g->next;
+ h = h->next;
+ j = j->next;
+ k = k->next;
+ l = l->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ this->mem_check( f );
+ this->mem_check( g );
+ this->mem_check( h );
+ this->mem_check( j );
+ this->mem_check( k );
+ this->mem_check( l );
+ }
+ } else if (this->exp->chains_per_thread == 12) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ Chain* f = root[5];
+ Chain* g = root[6];
+ Chain* h = root[7];
+ Chain* j = root[8];
+ Chain* k = root[9];
+ Chain* l = root[10];
+ Chain* m = root[11];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ f = f->next;
+ g = g->next;
+ h = h->next;
+ j = j->next;
+ k = k->next;
+ l = l->next;
+ m = m->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ this->mem_check( f );
+ this->mem_check( g );
+ this->mem_check( h );
+ this->mem_check( j );
+ this->mem_check( k );
+ this->mem_check( l );
+ this->mem_check( m );
+ }
+ } else if (this->exp->chains_per_thread == 13) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ Chain* f = root[5];
+ Chain* g = root[6];
+ Chain* h = root[7];
+ Chain* j = root[8];
+ Chain* k = root[9];
+ Chain* l = root[10];
+ Chain* m = root[11];
+ Chain* n = root[12];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ f = f->next;
+ g = g->next;
+ h = h->next;
+ j = j->next;
+ k = k->next;
+ l = l->next;
+ m = m->next;
+ n = n->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ this->mem_check( f );
+ this->mem_check( g );
+ this->mem_check( h );
+ this->mem_check( j );
+ this->mem_check( k );
+ this->mem_check( l );
+ this->mem_check( m );
+ this->mem_check( n );
+ }
+ } else if (this->exp->chains_per_thread == 14) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ Chain* f = root[5];
+ Chain* g = root[6];
+ Chain* h = root[7];
+ Chain* j = root[8];
+ Chain* k = root[9];
+ Chain* l = root[10];
+ Chain* m = root[11];
+ Chain* n = root[12];
+ Chain* o = root[13];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ f = f->next;
+ g = g->next;
+ h = h->next;
+ j = j->next;
+ k = k->next;
+ l = l->next;
+ m = m->next;
+ n = n->next;
+ o = o->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ this->mem_check( f );
+ this->mem_check( g );
+ this->mem_check( h );
+ this->mem_check( j );
+ this->mem_check( k );
+ this->mem_check( l );
+ this->mem_check( m );
+ this->mem_check( n );
+ this->mem_check( o );
+ }
+ } else if (this->exp->chains_per_thread == 15) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ Chain* f = root[5];
+ Chain* g = root[6];
+ Chain* h = root[7];
+ Chain* j = root[8];
+ Chain* k = root[9];
+ Chain* l = root[10];
+ Chain* m = root[11];
+ Chain* n = root[12];
+ Chain* o = root[13];
+ Chain* p = root[14];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ f = f->next;
+ g = g->next;
+ h = h->next;
+ j = j->next;
+ k = k->next;
+ l = l->next;
+ m = m->next;
+ n = n->next;
+ o = o->next;
+ p = p->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ this->mem_check( f );
+ this->mem_check( g );
+ this->mem_check( h );
+ this->mem_check( j );
+ this->mem_check( k );
+ this->mem_check( l );
+ this->mem_check( m );
+ this->mem_check( n );
+ this->mem_check( o );
+ this->mem_check( p );
+ }
+ } else if (this->exp->chains_per_thread == 16) {
+ for (int i=0; i < this->exp->iterations; i++) {
+ Chain* a = root[0];
+ Chain* b = root[1];
+ Chain* c = root[2];
+ Chain* d = root[3];
+ Chain* e = root[4];
+ Chain* f = root[5];
+ Chain* g = root[6];
+ Chain* h = root[7];
+ Chain* j = root[8];
+ Chain* k = root[9];
+ Chain* l = root[10];
+ Chain* m = root[11];
+ Chain* n = root[12];
+ Chain* o = root[13];
+ Chain* p = root[14];
+ Chain* q = root[15];
+ while (a != NULL) {
+ a = a->next;
+ b = b->next;
+ c = c->next;
+ d = d->next;
+ e = e->next;
+ f = f->next;
+ g = g->next;
+ h = h->next;
+ j = j->next;
+ k = k->next;
+ l = l->next;
+ m = m->next;
+ n = n->next;
+ o = o->next;
+ p = p->next;
+ q = q->next;
+ }
+ this->mem_check( a );
+ this->mem_check( b );
+ this->mem_check( c );
+ this->mem_check( d );
+ this->mem_check( e );
+ this->mem_check( f );
+ this->mem_check( g );
+ this->mem_check( h );
+ this->mem_check( j );
+ this->mem_check( k );
+ this->mem_check( l );
+ this->mem_check( m );
+ this->mem_check( n );
+ this->mem_check( o );
+ this->mem_check( p );
+ this->mem_check( q );
+ }
+ }
+ // barrier
+ this->bp->barrier();
+
+ // stop timer
+ double stop = 0;
+ if (this->thread_id() == 0) stop = Timer::seconds();
+ this->bp->barrier();
+
+ if (0 <= e) {
+ if (this->thread_id() == 0) {
+ double delta = stop - start;
+ if (0 < delta) {
+ Run::_seconds = min( Run::_seconds, delta );
+ }
+ }
+ }
+ }
+
+ this->bp->barrier();
+
+
+ for (int i=0; i < this->exp->chains_per_thread; i++) {
+ if (chain_memory[i] != NULL) delete [] chain_memory[i];
+ }
+ if (chain_memory != NULL) delete [] chain_memory;
+
+ return 0;
+}
+
+int dummy = 0;
+void
+Run::mem_check( Chain *m )
+{
+ if (m == NULL) dummy += 1;
+}
+
+static double
+min( double v1, double v2 )
+{
+ if (v2 < v1) return v2;
+ return v1;
+}
+
+ // exclude 2 and mersienne primes, i.e.,
+ // primes of the form 2**n - 1, e.g.,
+ // 3, 7, 31, 127
+static const int prime_table[] = { 5, 11, 13, 17, 19, 23, 37, 41, 43, 47,
+ 53, 61, 71, 73, 79, 83, 89, 97, 101, 103, 109, 113, 131, 137, 139, 149,
+ 151, 157, 163, };
+static const int prime_table_size = sizeof prime_table / sizeof prime_table[0];
+
+Chain*
+Run::random_mem_init( Chain *mem )
+{
+ // initialize pointers --
+ // choose a page at random, then use
+ // one pointer from each cache line
+ // within the page. all pages and
+ // cache lines are chosen at random.
+ Chain* root = NULL;
+ Chain* prev = NULL;
+ int link_within_line = 0;
+ int64 local_ops_per_chain = 0;
+
+ // we must set a lock because random()
+ // is not thread safe
+ Run::global_mutex.lock();
+ setstate(this->exp->random_state[this->thread_id()]);
+ int page_factor = prime_table[ random() % prime_table_size ];
+ int page_offset = random() % this->exp->pages_per_chain;
+ Run::global_mutex.unlock();
+
+ // loop through the pages
+ for (int i=0; i < this->exp->pages_per_chain; i++) {
+ int page = (page_factor * i + page_offset) % this->exp->pages_per_chain;
+ Run::global_mutex.lock();
+ setstate(this->exp->random_state[this->thread_id()]);
+ int line_factor = prime_table[ random() % prime_table_size ];
+ int line_offset = random() % this->exp->lines_per_page;
+ Run::global_mutex.unlock();
+
+ // loop through the lines within a page
+ for (int j=0; j < this->exp->lines_per_page; j++) {
+ int line_within_page = (line_factor * j + line_offset) % this->exp->lines_per_page;
+ int link = page * this->exp->links_per_page + line_within_page * this->exp->links_per_line + link_within_line;
+
+ if (root == NULL) {
+// printf("root = %d(%d)[0x%x].\n", page, line_within_page, mem+link);
+ prev = root = mem + link;
+ local_ops_per_chain += 1;
+ } else {
+// printf("0x%x = %d(%d)[0x%x].\n", prev, page, line_within_page, mem+link);
+ prev->next = mem + link;
+ prev = prev->next;
+ local_ops_per_chain += 1;
+ }
+ }
+ }
+
+ Run::global_mutex.lock();
+ Run::_ops_per_chain = local_ops_per_chain;
+ Run::global_mutex.unlock();
+
+ return root;
+}
+
+Chain*
+Run::forward_mem_init( Chain *mem )
+{
+ Chain* root = NULL;
+ Chain* prev = NULL;
+ int link_within_line = 0;
+ int64 local_ops_per_chain = 0;
+
+ for (int i=0; i < this->exp->lines_per_chain; i += this->exp->stride) {
+ int link = i * this->exp->links_per_line + link_within_line;
+ if (root == NULL) {
+// printf("root = %d(%d)[0x%x].\n", page, line_within_page, mem+link);
+ prev = root = mem + link;
+ local_ops_per_chain += 1;
+ } else {
+// printf("0x%x = %d(%d)[0x%x].\n", prev, page, line_within_page, mem+link);
+ prev->next = mem + link;
+ prev = prev->next;
+ local_ops_per_chain += 1;
+ }
+ }
+
+ Run::global_mutex.lock();
+ Run::_ops_per_chain = local_ops_per_chain;
+ Run::global_mutex.unlock();
+
+ return root;
+}
+
+Chain*
+Run::reverse_mem_init( Chain *mem )
+{
+ Chain* root = NULL;
+ Chain* prev = NULL;
+ int link_within_line = 0;
+ int64 local_ops_per_chain = 0;
+
+ int stride = -this->exp->stride;
+ int last;
+ for (int i=0; i < this->exp->lines_per_chain; i += stride) {
+ last = i;
+ }
+
+ for (int i=last; 0 <= i; i -= stride) {
+ int link = i * this->exp->links_per_line + link_within_line;
+ if (root == NULL) {
+// printf("root = %d(%d)[0x%x].\n", page, line_within_page, mem+link);
+ prev = root = mem + link;
+ local_ops_per_chain += 1;
+ } else {
+// printf("0x%x = %d(%d)[0x%x].\n", prev, page, line_within_page, mem+link);
+ prev->next = mem + link;
+ prev = prev->next;
+ local_ops_per_chain += 1;
+ }
+ }
+
+ Run::global_mutex.lock();
+ Run::_ops_per_chain = local_ops_per_chain;
+ Run::global_mutex.unlock();
+
+ return root;
+}