From fb9ae8907327f93cbeed6ffef914435a4e2ec651 Mon Sep 17 00:00:00 2001 From: Doug Pase Date: Mon, 22 Jan 2007 00:00:00 +0000 Subject: Initial commit. --- Chain.C | 24 ++ Chain.h | 24 ++ Experiment.C | 542 +++++++++++++++++++++++++++++++++++++++++ Experiment.h | 100 ++++++++ License.htm | 267 ++++++++++++++++++++ License.txt | 214 +++++++++++++++++ Lock.C | 45 ++++ Lock.h | 30 +++ Main.C | 89 +++++++ Main.h | 18 ++ Makefile | 34 +++ Output.C | 153 ++++++++++++ Output.h | 28 +++ Run.C | 761 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Run.h | 49 ++++ SpinBarrier.C | 48 ++++ SpinBarrier.h | 44 ++++ Thread.C | 86 +++++++ Thread.h | 53 ++++ Timer.C | 175 ++++++++++++++ Timer.h | 28 +++ Types.C | 13 + Types.h | 29 +++ pChase.sh | 39 +++ pChase64_NUMA | Bin 0 -> 47016 bytes pChase64_SMP | Bin 0 -> 46208 bytes run-pChase.sh | 5 + 27 files changed, 2898 insertions(+) create mode 100644 Chain.C create mode 100644 Chain.h create mode 100644 Experiment.C create mode 100644 Experiment.h create mode 100644 License.htm create mode 100644 License.txt create mode 100644 Lock.C create mode 100644 Lock.h create mode 100644 Main.C create mode 100644 Main.h create mode 100644 Makefile create mode 100644 Output.C create mode 100644 Output.h create mode 100644 Run.C create mode 100644 Run.h create mode 100644 SpinBarrier.C create mode 100644 SpinBarrier.h create mode 100644 Thread.C create mode 100644 Thread.h create mode 100644 Timer.C create mode 100644 Timer.h create mode 100644 Types.C create mode 100644 Types.h create mode 100755 pChase.sh create mode 100755 pChase64_NUMA create mode 100755 pChase64_SMP create mode 100755 run-pChase.sh diff --git a/Chain.C b/Chain.C new file mode 100644 index 0000000..d010878 --- /dev/null +++ b/Chain.C @@ -0,0 +1,24 @@ +/******************************************************************************* + * 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 + +#include "Chain.h" + +Chain::Chain() +: next(NULL) +{ +} + +Chain::~Chain() +{ +} diff --git a/Chain.h b/Chain.h new file mode 100644 index 0000000..cf1a51b --- /dev/null +++ b/Chain.h @@ -0,0 +1,24 @@ +/******************************************************************************* + * 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 * + *******************************************************************************/ + + +#if !defined(Chain_h) +#define Chain_h + +class Chain { +public: + Chain(); + ~Chain(); + Chain* next; +private: +}; + +#endif diff --git a/Experiment.C b/Experiment.C new file mode 100644 index 0000000..07f18a4 --- /dev/null +++ b/Experiment.C @@ -0,0 +1,542 @@ +/******************************************************************************* + * 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 +#include +#include +#include + +#if defined(NUMA) +#include +#endif + +#include "Experiment.h" + +Experiment::Experiment() : + strict (0), + pointer_size (DEFAULT_POINTER_SIZE), + bytes_per_line (DEFAULT_BYTES_PER_LINE), + links_per_line (DEFAULT_LINKS_PER_LINE), + bytes_per_page (DEFAULT_BYTES_PER_PAGE), + lines_per_page (DEFAULT_LINES_PER_PAGE), + links_per_page (DEFAULT_LINKS_PER_PAGE), + bytes_per_chain (DEFAULT_BYTES_PER_CHAIN), + lines_per_chain (DEFAULT_LINES_PER_CHAIN), + links_per_chain (DEFAULT_LINKS_PER_CHAIN), + pages_per_chain (DEFAULT_PAGES_PER_CHAIN), + chains_per_thread(DEFAULT_CHAINS_PER_THREAD), + bytes_per_thread (DEFAULT_BYTES_PER_THREAD), + num_threads (DEFAULT_THREADS), + bytes_per_test (DEFAULT_BYTES_PER_TEST), + iterations (DEFAULT_ITERATIONS), + experiments (DEFAULT_EXPERIMENTS), + output_mode (TABLE), + access_pattern (RANDOM), + stride (1), + numa_placement (LOCAL), + offset_or_mask (0), + placement_map (NULL), + thread_domain (NULL), + chain_domain (NULL), + numa_max_domain (0), + num_numa_domains (1) +{ +} + +Experiment::~Experiment() +{ +} + + // interface: + // + // -l or --line bytes per cache line (line size) + // -p or --page bytes per page (page size) + // -c or --chain bytes per chain (used to compute pages per chain) + // -r or --references chains per thread (memory loading) + // -t or --threads number of threads (concurrency and contention) + // -i or --iters iterations + // -e or --experiments experiments + // -a or --access memory access pattern + // random random access pattern + // forward exclusive OR and mask + // reverse addition and offset + // -o or --output output mode + // hdr header only + // csv csv only + // both header + csv + // table human-readable table of values + // -n or --numa numa placement + // local local allocation of all chains + // xor exclusive OR and mask + // add addition and offset + // map explicit mapping of threads and chains to domains + +int +Experiment::parse_args(int argc, char* argv[]) +{ + int error = 0; + for (int i=1; i < argc; i++) { + if (strcasecmp(argv[i], "-s") == 0 || strcasecmp(argv[i], "--strict") == 0) { + this->strict = 1; + } else if (strcasecmp(argv[i], "-l") == 0 || strcasecmp(argv[i], "--line") == 0) { + i++; + if (i == argc) { error = 1; break; } + this->bytes_per_line = Experiment::parse_number(argv[i]); + if (this->bytes_per_line == 0) { error = 1; break; } + } else if (strcasecmp(argv[i], "-p") == 0 || strcasecmp(argv[i], "--page") == 0) { + i++; + if (i == argc) { error = 1; break; } + this->bytes_per_page = Experiment::parse_number(argv[i]); + if (this->bytes_per_page == 0) { error = 1; break; } + } else if (strcasecmp(argv[i], "-c") == 0 || strcasecmp(argv[i], "--chain") == 0) { + i++; + if (i == argc) { error = 1; break; } + this->bytes_per_chain = Experiment::parse_number(argv[i]); + if (this->bytes_per_chain == 0) { error = 1; break; } + } else if (strcasecmp(argv[i], "-r") == 0 || strcasecmp(argv[i], "--references") == 0) { + i++; + if (i == argc) { error = 1; break; } + this->chains_per_thread = Experiment::parse_number(argv[i]); + if (this->chains_per_thread == 0) { error = 1; break; } + } else if (strcasecmp(argv[i], "-t") == 0 || strcasecmp(argv[i], "--threads") == 0) { + i++; + if (i == argc) { error = 1; break; } + this->num_threads = Experiment::parse_number(argv[i]); + if (this->num_threads == 0) { error = 1; break; } + } else if (strcasecmp(argv[i], "-i") == 0 || strcasecmp(argv[i], "--iterations") == 0) { + i++; + if (i == argc) { error = 1; break; } + this->iterations = Experiment::parse_number(argv[i]); + if (this->iterations == 0) { error = 1; break; } + } else if (strcasecmp(argv[i], "-e") == 0 || strcasecmp(argv[i], "--experiments") == 0) { + i++; + if (i == argc) { error = 1; break; } + this->experiments = Experiment::parse_number(argv[i]); + if (this->experiments == 0) { error = 1; break; } + } else if (strcasecmp(argv[i], "-a") == 0 || strcasecmp(argv[i], "--access") == 0) { + i++; + if (i == argc) { error = 1; break; } + if (strcasecmp(argv[i], "random") == 0) { + this->access_pattern = RANDOM; + } else if (strcasecmp(argv[i], "forward") == 0) { + this->access_pattern = STRIDED; + i++; + if (i == argc) { error = 1; break; } + this->stride = Experiment::parse_number(argv[i]); + if (this->stride == 0) { error = 1; break; } + } else if (strcasecmp(argv[i], "reverse") == 0) { + this->access_pattern = STRIDED; + i++; + if (i == argc) { error = 1; break; } + this->stride = - Experiment::parse_number(argv[i]); + if (this->stride == 0) { error = 1; break; } + } else { + error = 1; + break; + } + } else if (strcasecmp(argv[i], "-o") == 0 || strcasecmp(argv[i], "--output") == 0) { + i++; + if (i == argc) { error = 1; break; } + if (strcasecmp(argv[i], "table") == 0) { + this->output_mode = TABLE; + } else if (strcasecmp(argv[i], "csv") == 0) { + this->output_mode = CSV; + } else if (strcasecmp(argv[i], "both") == 0) { + this->output_mode = BOTH; + } else if (strcasecmp(argv[i], "hdr") == 0) { + this->output_mode = HEADER; + } else if (strcasecmp(argv[i], "header") == 0) { + this->output_mode = HEADER; + } else { + error = 1; + break; + } + } else if (strcasecmp(argv[i], "-n") == 0 || strcasecmp(argv[i], "--numa") == 0) { + i++; + if (i == argc) { error = 1; break; } + if (strcasecmp(argv[i], "local") == 0) { + this->numa_placement = LOCAL; + } else if (strcasecmp(argv[i], "xor") == 0) { + this->numa_placement = XOR; + i++; + if (i == argc) { error = 1; break; } + this->offset_or_mask = Experiment::parse_number(argv[i]); + } else if (strcasecmp(argv[i], "add") == 0) { + this->numa_placement = ADD; + i++; + if (i == argc) { error = 1; break; } + this->offset_or_mask = Experiment::parse_number(argv[i]); + } else if (strcasecmp(argv[i], "map") == 0) { + this->numa_placement = MAP; + i++; + if (i == argc) { error = 1; break; } + this->placement_map = argv[i]; + } else { + error = 1; + break; + } + } else { + error = 1; + break; + } + } + + + // if we've hit an error, print a message and quit + if (error) { + printf("usage: %s \n", argv[0]); + printf("where are selected from the following:\n"); + printf(" [-h|--help] # this message\n"); + printf(" [-l|--line] # bytes per cache line (cache line size)\n"); + printf(" [-p|--page] # bytes per page (page size)\n"); + printf(" [-c|--chain] # bytes per chain (used to compute pages per chain)\n"); + printf(" [-r|--references] # chains per thread (memory loading)\n"); + printf(" [-t|--threads] # number of threads (concurrency and contention)\n"); + printf(" [-i|--iterations] # iterations\n"); + printf(" [-e|--experiments] # experiments\n"); + printf(" [-a|--access] # memory access pattern\n"); + printf(" [-o|--output] # output format\n"); + printf(" [-n|--numa] # numa placement\n"); + printf(" [-s|--strict] # fail rather than adjust options to sensible values\n"); + printf("\n"); + printf(" is selected from the following:\n"); + printf(" random # all chains are accessed randomly\n"); + printf(" forward # chains are in forward order with constant stride\n"); + printf(" reverse # chains are in reverse order with constant stride\n"); + printf("\n"); + printf("Note: is always a small positive integer.\n"); + printf("\n"); + printf(" is selected from the following:\n"); + printf(" hdr # csv header only\n"); + printf(" csv # results in csv format only\n"); + printf(" both # header and results in csv format\n"); + printf(" table # human-readable table of values\n"); + printf("\n"); + printf(" is selected from the following:\n"); + printf(" local # all chains are allocated locally\n"); + printf(" xor # exclusive OR and mask\n"); + printf(" add # addition and offset\n"); + printf(" map # explicit mapping of threads and chains to domains\n"); + printf("\n"); + printf(" has the form \"t1:c11,c12,...,c1m;t2:c21,...,c2m;...;tn:cn1,...,cnm\"\n"); + printf("where t[i] is the NUMA domain where the ith thread is run,\n"); + printf("and c[i][j] is the NUMA domain where the jth chain in the ith thread is allocated.\n"); + printf("(The values t[i] and c[i][j] must all be zero or small positive integers.)\n"); + printf("\n"); + printf("Note: for maps, each thread must have the same number of chains,\n"); + printf("maps override the -t or --threads specification,\n"); + printf("NUMA domains are whole numbers in the range of 0..N, and\n"); + printf("thread or chain domains that exceed the maximum NUMA domain\n"); + printf("are wrapped around using a MOD function.\n"); + printf("\n"); + printf("To determine the number of NUMA domains currently available\n"); + printf("on your system, use a command such as \"numastat\".\n"); + printf("\n"); + printf("Final note: strict is not yet implemented, and\n"); + printf("maps do not gracefully handle ill-formed map specifications.\n"); + + return 1; + } + + + // STRICT -- fail if specifications are inconsistent + + // compute lines per page and lines per chain + // based on input and defaults. + // we round up page and chain sizes when needed. + this->lines_per_page = (this->bytes_per_page+this->bytes_per_line-1) / this->bytes_per_line; + this->bytes_per_page = this->bytes_per_line * this->lines_per_page; + this->pages_per_chain = (this->bytes_per_chain+this->bytes_per_page-1) / this->bytes_per_page; + this->bytes_per_chain = this->bytes_per_page * this->pages_per_chain; + this->bytes_per_thread = this->bytes_per_chain * this->chains_per_thread; + this->bytes_per_test = this->bytes_per_thread * this->num_threads; + this->links_per_line = this->bytes_per_line / pointer_size; + this->links_per_page = this->lines_per_page * this->links_per_line; + this->lines_per_chain = this->lines_per_page * this->pages_per_chain; + this->links_per_chain = this->lines_per_chain * this->links_per_line; + + + // allocate the chain roots for all threads + // and compute the chain locations + // (the chains themselves are initialized by the threads) + switch (this->numa_placement) { + case LOCAL : + case XOR : + case ADD : + this->thread_domain = new int32 [ this->num_threads ]; + this->chain_domain = new int32*[ this->num_threads ]; + this->random_state = new char* [ this->num_threads ]; + + for (int i=0; i < this->num_threads; i++) { + this->chain_domain[i] = new int32 [ this->chains_per_thread ]; + + const int state_size = 256; + this->random_state[i] = new char[state_size]; + initstate((unsigned int) i, (char *) this->random_state[i], (size_t) state_size); + } + break; + } + + +#if defined(NUMA) + this->numa_max_domain = numa_max_node(); + this->num_numa_domains = this->numa_max_domain + 1; +#endif + + + switch (this->numa_placement) { + case LOCAL : + default: + this->alloc_local(); + break; + case XOR : + this->alloc_xor(); + break; + case ADD : + this->alloc_add(); + break; + case MAP : + this->alloc_map(); + break; + } + + return 0; +} + + +int64 +Experiment::parse_number( const char* s ) +{ + int64 result = 0; + + int len = strlen( s ); + for (int i=0; i < len; i++) { + if ( '0' <= s[i] && s[i] <= '9' ) { + result = result * 10 + s[i] - '0'; + } else if (s[i] == 'k' || s[i] == 'K') { + result = result << 10; + break; + } else if (s[i] == 'm' || s[i] == 'M') { + result = result << 20; + break; + } else if (s[i] == 'g' || s[i] == 'G') { + result = result << 30; + break; + } else if (s[i] == 't' || s[i] == 'T') { + result = result << 40; + break; + } else { + break; + } + } + + return result; +} + +void +Experiment::alloc_local() +{ + for (int i=0; i < this->num_threads; i++) { + this->thread_domain[i] = i % this->num_numa_domains; + for (int j=0; j < this->chains_per_thread; j++) { + this->chain_domain[i][j] = this->thread_domain[i]; + } + } +} + +void +Experiment::alloc_xor() +{ + for (int i=0; i < this->num_threads; i++) { + this->thread_domain[i] = i % this->num_numa_domains; + for (int j=0; j < this->chains_per_thread; j++) { + this->chain_domain[i][j] = (this->thread_domain[i] ^ this->offset_or_mask) % this->num_numa_domains; + } + } +} + +void +Experiment::alloc_add() +{ + for (int i=0; i < this->num_threads; i++) { + this->thread_domain[i] = i % this->num_numa_domains; + for (int j=0; j < this->chains_per_thread; j++) { + this->chain_domain[i][j] = (this->thread_domain[i] + this->offset_or_mask) % this->num_numa_domains; + } + } +} + + // DOES NOT HANDLE ILL-FORMED SPECIFICATIONS +void +Experiment::alloc_map() +{ + // STRICT -- fail if specifications are inconsistent + + // maps look like "t1:c11,c12,...,c1m;t2:c21,...,c2m;...;tn:cn1,...,cnm" + // where t[i] is the thread domain of the ith thread, + // and c[i][j] is the chain domain of the jth chain in the ith thread + + // count the thread descriptors by counting ";" up to EOS + int threads = 1; + char *p = this->placement_map; + while (*p != '\0') { + if (*p == ';') threads += 1; + p++; + } + int thread_domain[ threads ]; + + // count the chain descriptors by counting "," up to ";" or EOS + int chains = 1; + p = this->placement_map; + while (*p != '\0') { + if (*p == ';') break; + if (*p == ',') chains += 1; + p++; + } + int chain_domain [ threads ][ chains ]; + + int t=0, c=0; + p = this->placement_map; + while (*p != '\0') { + // everything up to ":" is the thread domain + int i = 0; + char buf[64]; + while (*p != '\0') { + if (*p == ':') { p++; break; } + buf[i] = *p; + i++; + p++; + } + buf[i] = '\0'; + thread_domain[t] = Experiment::parse_number(buf); + + // search for one or several ',' + c = 0; + while (*p != '\0' && *p != ';') { + int i = 0; + while (*p != '\0' && *p != ';') { + if (*p == ',') { p++; break; } + buf[i] = *p; + i++; + p++; + } + buf[i] = '\0'; + chain_domain[t][c] = Experiment::parse_number(buf); + c++; + } + + if (*p == '\0') break; + if (*p == ';') p++; + t++; + } + + + this->num_threads = threads; + this->chains_per_thread = chains; + + this->thread_domain = new int32 [ this->num_threads ]; + this->chain_domain = new int32*[ this->num_threads ]; + this->random_state = new char* [ this->num_threads ]; + + for (int i=0; i < this->num_threads; i++) { + this->thread_domain[i] = thread_domain[i] % this->num_numa_domains; + + const int state_size = 256; + this->random_state[i] = new char[state_size]; + initstate((unsigned int) i, (char *) this->random_state[i], (size_t) state_size); + + this->chain_domain[i] = new int32 [ this->chains_per_thread ]; + for (int j=0; j < this->chains_per_thread; j++) { + this->chain_domain[i][j] = chain_domain[i][j] % this->num_numa_domains; + } + } + + this->bytes_per_thread = this->bytes_per_chain * this->chains_per_thread; + this->bytes_per_test = this->bytes_per_thread * this->num_threads; +} + +#include "Chain.h" + +void +Experiment::print() +{ + printf("strict = %d\n", strict); + printf("pointer_size = %d\n", pointer_size); + printf("sizeof(Chain) = %d\n", sizeof(Chain)); + printf("sizeof(Chain *) = %d\n", sizeof(Chain *)); + printf("bytes_per_line = %d\n", bytes_per_line); + printf("links_per_line = %d\n", links_per_line); + printf("bytes_per_page = %d\n", bytes_per_page); + printf("lines_per_page = %d\n", lines_per_page); + printf("links_per_page = %d\n", links_per_page); + printf("bytes_per_chain = %d\n", bytes_per_chain); + printf("lines_per_chain = %d\n", lines_per_chain); + printf("links_per_chain = %d\n", links_per_chain); + printf("pages_per_chain = %d\n", pages_per_chain); + printf("chains_per_thread = %d\n", chains_per_thread); + printf("bytes_per_thread = %d\n", bytes_per_thread); + printf("num_threads = %d\n", num_threads); + printf("bytes_per_test = %d\n", bytes_per_test); + printf("iterations = %d\n", iterations); + printf("experiments = %d\n", experiments); + printf("access_pattern = %d\n", access_pattern); + printf("stride = %d\n", stride); + printf("output_mode = %d\n", output_mode); + printf("numa_placement = %d\n", numa_placement); + printf("offset_or_mask = %d\n", offset_or_mask); + printf("numa_max_domain = %d\n", numa_max_domain); + printf("num_numa_domains = %d\n", num_numa_domains); + + for (int i=0; i < this->num_threads; i++) { + printf("%d: ", this->thread_domain[i]); + for (int j=0; j < this->chains_per_thread; j++) { + printf("%d,", this->chain_domain[i][j]); + } + printf("\n"); + } + + fflush(stdout); +} + +const char* +Experiment::access() +{ + char* result = NULL; + + if (this->access_pattern == RANDOM) { + result = "random"; + } else if (this->access_pattern == STRIDED && 0 < this->stride) { + result = "forward"; + } else if (this->access_pattern == STRIDED && this->stride < 0) { + result = "reverse"; + } + + return result; +} + +const char* +Experiment::placement() +{ + char* result = NULL; + + if (this->numa_placement == LOCAL) { + result = "local"; + } else if (this->numa_placement == XOR) { + result = "xor"; + } else if (this->numa_placement == ADD) { + result = "add"; + } else if (this->numa_placement == MAP) { + result = "map"; + } + + return result; +} diff --git a/Experiment.h b/Experiment.h new file mode 100644 index 0000000..ae1be1e --- /dev/null +++ b/Experiment.h @@ -0,0 +1,100 @@ +/******************************************************************************* + * 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 * + *******************************************************************************/ + + +#if !defined(Experiment_h) +#define Experiment_h + +#include "Chain.h" +#include "Types.h" + +class Experiment { +public: + Experiment(); + ~Experiment(); + + int parse_args(int argc, char* argv[]); + int64 parse_number( const char* s ); + + const char* placement(); + const char* access(); + + // fundamental parameters + int64 pointer_size; // number of bytes in a pointer + int64 bytes_per_line; // working set cache line size (bytes) + int64 links_per_line; // working set cache line size (links) + int64 bytes_per_page; // working set page size (in bytes) + int64 lines_per_page; // working set page size (in lines) + int64 links_per_page; // working set page size (in links) + int64 bytes_per_chain; // working set chain size (bytes) + int64 lines_per_chain; // working set chain size (lines) + int64 links_per_chain; // working set chain size (links) + int64 pages_per_chain; // working set chain size (pages) + int64 bytes_per_thread; // thread working set size (bytes) + int64 chains_per_thread; // memory loading per thread + int64 num_threads; // number of threads in the experiment + int64 bytes_per_test; // test working set size (bytes) + + int64 iterations; // number of iterations per experiment + int64 experiments; // number of experiments per test + + enum { CSV, BOTH, HEADER, TABLE } + output_mode; // results output mode + + enum { RANDOM, STRIDED } + access_pattern; // memory access pattern + int64 stride; + + enum { LOCAL, XOR, ADD, MAP } + numa_placement; // memory allocation mode + int64 offset_or_mask; + char* placement_map; + + // maps threads and chains to numa domains + int32* thread_domain; // thread_domain[thread] + int32** chain_domain; // chain_domain[thread][chain] + int32 numa_max_domain; // highest numa domain id + int32 num_numa_domains; // number of numa domains + + char** random_state; // random state for each thread + + int strict; // strictly adhere to user input, or fail + + const static int32 DEFAULT_POINTER_SIZE = sizeof(Chain); + const static int32 DEFAULT_BYTES_PER_LINE = 64; + const static int32 DEFAULT_LINKS_PER_LINE = DEFAULT_BYTES_PER_LINE / DEFAULT_POINTER_SIZE; + const static int32 DEFAULT_BYTES_PER_PAGE = 4096; + const static int32 DEFAULT_LINES_PER_PAGE = DEFAULT_BYTES_PER_PAGE / DEFAULT_BYTES_PER_LINE; + const static int32 DEFAULT_LINKS_PER_PAGE = DEFAULT_LINES_PER_PAGE * DEFAULT_LINKS_PER_LINE; + const static int32 DEFAULT_PAGES_PER_CHAIN = 4096; + const static int32 DEFAULT_BYTES_PER_CHAIN = DEFAULT_BYTES_PER_PAGE * DEFAULT_PAGES_PER_CHAIN; + const static int32 DEFAULT_LINES_PER_CHAIN = DEFAULT_LINES_PER_PAGE * DEFAULT_PAGES_PER_CHAIN; + const static int32 DEFAULT_LINKS_PER_CHAIN = DEFAULT_LINES_PER_CHAIN * DEFAULT_BYTES_PER_LINE / DEFAULT_POINTER_SIZE; + const static int32 DEFAULT_CHAINS_PER_THREAD = 1; + const static int32 DEFAULT_BYTES_PER_THREAD = DEFAULT_BYTES_PER_CHAIN * DEFAULT_CHAINS_PER_THREAD; + const static int32 DEFAULT_THREADS = 1; + const static int32 DEFAULT_BYTES_PER_TEST = DEFAULT_BYTES_PER_THREAD * DEFAULT_THREADS; + const static int32 DEFAULT_ITERATIONS = 1; + const static int32 DEFAULT_EXPERIMENTS = 1; + + const static int32 DEFAULT_OUTPUT_MODE = 1; + + void alloc_local(); + void alloc_xor(); + void alloc_add(); + void alloc_map(); + + void print(); + +private: +}; + +#endif diff --git a/License.htm b/License.htm new file mode 100644 index 0000000..8beaf6a --- /dev/null +++ b/License.htm @@ -0,0 +1,267 @@ +

Common Public License Version 1.0

+ + + +

THE ACCOMPANYING PROGRAM IS PROVIDED UNDER THE TERMS OF THIS COMMON PUBLIC + LICENSE ("AGREEMENT"). ANY USE, REPRODUCTION OR DISTRIBUTION OF THE PROGRAM + CONSTITUTES RECIPIENT'S ACCEPTANCE OF THIS AGREEMENT.

+ + + +

1. DEFINITIONS

+ +

"Contribution" means:

+ +
+

a) in the case of the initial Contributor, the initial code and documentation + distributed under this Agreement, and

+

+b) in the case of each subsequent Contributor:

+

+i) changes to the Program, and

+

+ii) additions to the Program;

+ +

where such changes and/or additions to the Program originate from and are + distributed by that particular Contributor. A Contribution 'originates' from a + Contributor if it was added to the Program by such Contributor itself or anyone + acting on such Contributor's behalf. Contributions do not include additions to + the Program which: (i) are separate modules of software distributed in + conjunction with the Program under their own license agreement, and (ii) are + not derivative works of the Program.

+
+ + + +

"Contributor" means any person or entity that distributes the Program.

+ + + +

"Licensed Patents " mean patent claims licensable by a Contributor which are + necessarily infringed by the use or sale of its Contribution alone or when + combined with the Program.

+ + + +

"Program" means the Contributions distributed in accordance with this + Agreement.

+ + + +

"Recipient" means anyone who receives the Program under this Agreement, + including all Contributors.

+ + + +

2. GRANT OF RIGHTS

+ +
+

a) Subject to the terms of this Agreement, each Contributor hereby grants + Recipient a non-exclusive, worldwide, royalty-free copyright license to + reproduce, prepare derivative works of, publicly display, publicly perform, + distribute and sublicense the Contribution of such Contributor, if any, and + such derivative works, in source code and object code form.

+

+ +b) Subject to the terms of this Agreement, each Contributor hereby grants + Recipient a non-exclusive, worldwide, royalty-free patent license under + Licensed Patents to make, use, sell, offer to sell, import and otherwise + transfer the Contribution of such Contributor, if any, in source code and + object code form. This patent license shall apply to the combination of the + Contribution and the Program if, at the time the Contribution is added by the + Contributor, such addition of the Contribution causes such combination to be + covered by the Licensed Patents. The patent license shall not apply to any + other combinations which include the Contribution. No hardware per se is + licensed hereunder.

+ +

c) Recipient understands that although each Contributor grants the licenses + to its Contributions set forth herein, no assurances are provided by any + Contributor that the Program does not infringe the patent or other intellectual + property rights of any other entity. Each Contributor disclaims any liability + to Recipient for claims brought by any other entity based on infringement of + intellectual property rights or otherwise. As a condition to exercising the + rights and licenses granted hereunder, each Recipient hereby assumes sole + responsibility to secure any other intellectual property rights needed, if any. + For example, if a third party patent license is required to allow Recipient to + distribute the Program, it is Recipient's responsibility to acquire that + license before distributing the Program.

+ +

d) Each Contributor represents that to its knowledge it has sufficient + copyright rights in its Contribution, if any, to grant the copyright license + set forth in this Agreement.

+ + +

3. REQUIREMENTS

+ +

A Contributor may choose to distribute the Program in object code form under + its own license agreement, provided that:

+ +
+

a) it complies with the terms and conditions of this Agreement; and

+ +

+b) its license agreement:

+ +

i) effectively disclaims on behalf of all Contributors all warranties and + conditions, express and implied, including warranties or conditions of title + and non-infringement, and implied warranties or conditions of merchantability + and fitness for a particular purpose; +

+

ii) effectively excludes on behalf of all Contributors all liability for + damages, including direct, indirect, special, incidental and consequential + damages, such as lost profits; +

+

iii) states that any provisions which differ from this Agreement are offered + by that Contributor alone and not by any other party; and +

+

iv) states that source code for the Program is available from such + Contributor, and informs licensees how to obtain it in a reasonable manner on + or through a medium customarily used for software exchange. +

+ +

+ +When the Program is made available in source code form:

+ +

+ a) it must be made available under this Agreement; and

+

+ b) a copy of this Agreement must be included with each copy of the Program. +

+ + +

Contributors may not remove or alter any copyright notices contained within + the Program.

+ + + + + +

Each Contributor must identify itself as the originator of its Contribution, + if any, in a manner that reasonably allows subsequent Recipients to identify + the originator of the Contribution.

+ + +

4. COMMERCIAL DISTRIBUTION

+ +

Commercial distributors of software may accept certain responsibilities with + respect to end users, business partners and the like. While this license is + intended to facilitate the commercial use of the Program, the Contributor who + includes the Program in a commercial product offering should do so in a manner + which does not create potential liability for other Contributors. Therefore, if + a Contributor includes the Program in a commercial product offering, such + Contributor ("Commercial Contributor") hereby agrees to defend and indemnify + every other Contributor ("Indemnified Contributor") against any losses, damages + and costs (collectively "Losses") arising from claims, lawsuits and other legal + actions brought by a third party against the Indemnified Contributor to the + extent caused by the acts or omissions of such Commercial Contributor in + connection with its distribution of the Program in a commercial product + offering. The obligations in this section do not apply to any claims or Losses + relating to any actual or alleged intellectual property infringement. In order + to qualify, an Indemnified Contributor must: a) promptly notify the Commercial + Contributor in writing of such claim, and b) allow the Commercial Contributor + to control, and cooperate with the Commercial Contributor in, the defense and + any related settlement negotiations. The Indemnified Contributor may + participate in any such claim at its own expense. +

+ + +

For example, a Contributor might include the Program in a commercial product + offering, Product X. That Contributor is then a Commercial Contributor. If that + Commercial Contributor then makes performance claims, or offers warranties + related to Product X, those performance claims and warranties are such + Commercial Contributor's responsibility alone. Under this section, the + Commercial Contributor would have to defend claims against the other + Contributors related to those performance claims and warranties, and if a court + requires any other Contributor to pay any damages as a result, the Commercial + Contributor must pay those damages. +

+ +

5. NO WARRANTY

+ +

+EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, THE PROGRAM IS PROVIDED ON AN + "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, EITHER EXPRESS OR + IMPLIED INCLUDING, WITHOUT LIMITATION, ANY WARRANTIES OR CONDITIONS OF TITLE, + NON-INFRINGEMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Each + Recipient is solely responsible for determining the appropriateness of using + and distributing the Program and assumes all risks associated with its exercise + of rights under this Agreement, including but not limited to the risks and + costs of program errors, compliance with applicable laws, damage to or loss of + data, programs or equipment, and unavailability or interruption of operations. +

+ + +

+6. DISCLAIMER OF LIABILITY

+ +

EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, NEITHER RECIPIENT NOR ANY + CONTRIBUTORS SHALL HAVE ANY LIABILITY FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING WITHOUT LIMITATION LOST + PROFITS), 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 OR DISTRIBUTION OF THE PROGRAM OR THE EXERCISE OF ANY RIGHTS + GRANTED HEREUNDER, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. +

+ +

7. GENERAL

+ +

If any provision of this Agreement is invalid or unenforceable under + applicable law, it shall not affect the validity or enforceability of the + remainder of the terms of this Agreement, and without further action by the + parties hereto, such provision shall be reformed to the minimum extent + necessary to make such provision valid and enforceable.

+ + + +

If Recipient institutes patent litigation against a Contributor with respect + to a patent applicable to software (including a cross-claim or counterclaim in + a lawsuit), then any patent licenses granted by that Contributor to such + Recipient under this Agreement shall terminate as of the date such litigation + is filed. In addition, if Recipient institutes patent litigation against any + entity (including a cross-claim or counterclaim in a lawsuit) alleging that the + Program itself (excluding combinations of the Program with other software or + hardware) infringes such Recipient's patent(s), then such Recipient's rights + granted under Section 2(b) shall terminate as of the date such litigation is + filed.

+ + + +

All Recipient's rights under this Agreement shall terminate if it fails to + comply with any of the material terms or conditions of this Agreement and does + not cure such failure in a reasonable period of time after becoming aware of + such noncompliance. If all Recipient's rights under this Agreement terminate, + Recipient agrees to cease use and distribution of the Program as soon as + reasonably practicable. However, Recipient's obligations under this Agreement + and any licenses granted by Recipient relating to the Program shall continue + and survive.

+ + + +

Everyone is permitted to copy and distribute copies of this Agreement, but in + order to avoid inconsistency the Agreement is copyrighted and may only be + modified in the following manner. The Agreement Steward reserves the right to + publish new versions (including revisions) of this Agreement from time to time. + No one other than the Agreement Steward has the right to modify this Agreement. + IBM is the initial Agreement Steward. IBM may assign the responsibility to + serve as the Agreement Steward to a suitable separate entity. Each new version + of the Agreement will be given a distinguishing version number. The Program + (including Contributions) may always be distributed subject to the version of + the Agreement under which it was received. In addition, after a new version of + the Agreement is published, Contributor may elect to distribute the Program + (including its Contributions) under the new version. Except as expressly stated + in Sections 2(a) and 2(b) above, Recipient receives no rights or licenses to + the intellectual property of any Contributor under this Agreement, whether + expressly, by implication, estoppel or otherwise. All rights in the Program not + expressly granted under this Agreement are reserved.

+ + + +

This Agreement is governed by the laws of the State of New York and the + intellectual property laws of the United States of America. No party to this + Agreement will bring a legal action under this Agreement more than one year + after the cause of action arose. Each party waives its rights to a jury trial + in any resulting litigation.

+ + + diff --git a/License.txt b/License.txt new file mode 100644 index 0000000..8af18e5 --- /dev/null +++ b/License.txt @@ -0,0 +1,214 @@ +Common Public License Version 1.0 + +THE ACCOMPANYING PROGRAM IS PROVIDED UNDER THE TERMS OF THIS COMMON PUBLIC +LICENSE ("AGREEMENT"). ANY USE, REPRODUCTION OR DISTRIBUTION OF THE PROGRAM +CONSTITUTES RECIPIENT'S ACCEPTANCE OF THIS AGREEMENT. + +1. DEFINITIONS + +"Contribution" means: + + a) in the case of the initial Contributor, the initial code and +documentation distributed under this Agreement, and + + b) in the case of each subsequent Contributor: + + i) changes to the Program, and + + ii) additions to the Program; + + where such changes and/or additions to the Program originate from and are +distributed by that particular Contributor. A Contribution 'originates' from a +Contributor if it was added to the Program by such Contributor itself or anyone +acting on such Contributor's behalf. Contributions do not include additions to +the Program which: (i) are separate modules of software distributed in +conjunction with the Program under their own license agreement, and (ii) are not +derivative works of the Program. + +"Contributor" means any person or entity that distributes the Program. + +"Licensed Patents " mean patent claims licensable by a Contributor which are +necessarily infringed by the use or sale of its Contribution alone or when +combined with the Program. + +"Program" means the Contributions distributed in accordance with this Agreement. + +"Recipient" means anyone who receives the Program under this Agreement, +including all Contributors. + +2. GRANT OF RIGHTS + + a) Subject to the terms of this Agreement, each Contributor hereby grants +Recipient a non-exclusive, worldwide, royalty-free copyright license to +reproduce, prepare derivative works of, publicly display, publicly perform, +distribute and sublicense the Contribution of such Contributor, if any, and such +derivative works, in source code and object code form. + + b) Subject to the terms of this Agreement, each Contributor hereby grants +Recipient a non-exclusive, worldwide, royalty-free patent license under Licensed +Patents to make, use, sell, offer to sell, import and otherwise transfer the +Contribution of such Contributor, if any, in source code and object code form. +This patent license shall apply to the combination of the Contribution and the +Program if, at the time the Contribution is added by the Contributor, such +addition of the Contribution causes such combination to be covered by the +Licensed Patents. The patent license shall not apply to any other combinations +which include the Contribution. No hardware per se is licensed hereunder. + + c) Recipient understands that although each Contributor grants the licenses +to its Contributions set forth herein, no assurances are provided by any +Contributor that the Program does not infringe the patent or other intellectual +property rights of any other entity. Each Contributor disclaims any liability to +Recipient for claims brought by any other entity based on infringement of +intellectual property rights or otherwise. As a condition to exercising the +rights and licenses granted hereunder, each Recipient hereby assumes sole +responsibility to secure any other intellectual property rights needed, if any. +For example, if a third party patent license is required to allow Recipient to +distribute the Program, it is Recipient's responsibility to acquire that license +before distributing the Program. + + d) Each Contributor represents that to its knowledge it has sufficient +copyright rights in its Contribution, if any, to grant the copyright license set +forth in this Agreement. + +3. REQUIREMENTS + +A Contributor may choose to distribute the Program in object code form under its +own license agreement, provided that: + + a) it complies with the terms and conditions of this Agreement; and + + b) its license agreement: + + i) effectively disclaims on behalf of all Contributors all warranties and +conditions, express and implied, including warranties or conditions of title and +non-infringement, and implied warranties or conditions of merchantability and +fitness for a particular purpose; + + ii) effectively excludes on behalf of all Contributors all liability for +damages, including direct, indirect, special, incidental and consequential +damages, such as lost profits; + + iii) states that any provisions which differ from this Agreement are offered +by that Contributor alone and not by any other party; and + + iv) states that source code for the Program is available from such +Contributor, and informs licensees how to obtain it in a reasonable manner on or +through a medium customarily used for software exchange. + +When the Program is made available in source code form: + + a) it must be made available under this Agreement; and + + b) a copy of this Agreement must be included with each copy of the Program. + +Contributors may not remove or alter any copyright notices contained within the +Program. + +Each Contributor must identify itself as the originator of its Contribution, if +any, in a manner that reasonably allows subsequent Recipients to identify the +originator of the Contribution. + +4. COMMERCIAL DISTRIBUTION + +Commercial distributors of software may accept certain responsibilities with +respect to end users, business partners and the like. While this license is +intended to facilitate the commercial use of the Program, the Contributor who +includes the Program in a commercial product offering should do so in a manner +which does not create potential liability for other Contributors. Therefore, if +a Contributor includes the Program in a commercial product offering, such +Contributor ("Commercial Contributor") hereby agrees to defend and indemnify +every other Contributor ("Indemnified Contributor") against any losses, damages +and costs (collectively "Losses") arising from claims, lawsuits and other legal +actions brought by a third party against the Indemnified Contributor to the +extent caused by the acts or omissions of such Commercial Contributor in +connection with its distribution of the Program in a commercial product +offering. The obligations in this section do not apply to any claims or Losses +relating to any actual or alleged intellectual property infringement. In order +to qualify, an Indemnified Contributor must: a) promptly notify the Commercial +Contributor in writing of such claim, and b) allow the Commercial Contributor to +control, and cooperate with the Commercial Contributor in, the defense and any +related settlement negotiations. The Indemnified Contributor may participate in +any such claim at its own expense. + +For example, a Contributor might include the Program in a commercial product +offering, Product X. That Contributor is then a Commercial Contributor. If that +Commercial Contributor then makes performance claims, or offers warranties +related to Product X, those performance claims and warranties are such +Commercial Contributor's responsibility alone. Under this section, the +Commercial Contributor would have to defend claims against the other +Contributors related to those performance claims and warranties, and if a court +requires any other Contributor to pay any damages as a result, the Commercial +Contributor must pay those damages. + +5. NO WARRANTY + +EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, THE PROGRAM IS PROVIDED ON AN +"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, EITHER EXPRESS OR +IMPLIED INCLUDING, WITHOUT LIMITATION, ANY WARRANTIES OR CONDITIONS OF TITLE, +NON-INFRINGEMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Each +Recipient is solely responsible for determining the appropriateness of using and +distributing the Program and assumes all risks associated with its exercise of +rights under this Agreement, including but not limited to the risks and costs of +program errors, compliance with applicable laws, damage to or loss of data, +programs or equipment, and unavailability or interruption of operations. + +6. DISCLAIMER OF LIABILITY + +EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, NEITHER RECIPIENT NOR ANY +CONTRIBUTORS SHALL HAVE ANY LIABILITY FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING WITHOUT LIMITATION LOST +PROFITS), 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 OR DISTRIBUTION OF THE PROGRAM OR THE EXERCISE OF ANY RIGHTS +GRANTED HEREUNDER, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. + +7. GENERAL + +If any provision of this Agreement is invalid or unenforceable under applicable +law, it shall not affect the validity or enforceability of the remainder of the +terms of this Agreement, and without further action by the parties hereto, such +provision shall be reformed to the minimum extent necessary to make such +provision valid and enforceable. + +If Recipient institutes patent litigation against a Contributor with respect to +a patent applicable to software (including a cross-claim or counterclaim in a +lawsuit), then any patent licenses granted by that Contributor to such Recipient +under this Agreement shall terminate as of the date such litigation is filed. In +addition, if Recipient institutes patent litigation against any entity +(including a cross-claim or counterclaim in a lawsuit) alleging that the Program +itself (excluding combinations of the Program with other software or hardware) +infringes such Recipient's patent(s), then such Recipient's rights granted under +Section 2(b) shall terminate as of the date such litigation is filed. + +All Recipient's rights under this Agreement shall terminate if it fails to +comply with any of the material terms or conditions of this Agreement and does +not cure such failure in a reasonable period of time after becoming aware of +such noncompliance. If all Recipient's rights under this Agreement terminate, +Recipient agrees to cease use and distribution of the Program as soon as +reasonably practicable. However, Recipient's obligations under this Agreement +and any licenses granted by Recipient relating to the Program shall continue and +survive. + +Everyone is permitted to copy and distribute copies of this Agreement, but in +order to avoid inconsistency the Agreement is copyrighted and may only be +modified in the following manner. The Agreement Steward reserves the right to +publish new versions (including revisions) of this Agreement from time to time. +No one other than the Agreement Steward has the right to modify this Agreement. +IBM is the initial Agreement Steward. IBM may assign the responsibility to serve +as the Agreement Steward to a suitable separate entity. Each new version of the +Agreement will be given a distinguishing version number. The Program (including +Contributions) may always be distributed subject to the version of the Agreement +under which it was received. In addition, after a new version of the Agreement +is published, Contributor may elect to distribute the Program (including its +Contributions) under the new version. Except as expressly stated in Sections +2(a) and 2(b) above, Recipient receives no rights or licenses to the +intellectual property of any Contributor under this Agreement, whether +expressly, by implication, estoppel or otherwise. All rights in the Program not +expressly granted under this Agreement are reserved. + +This Agreement is governed by the laws of the State of New York and the +intellectual property laws of the United States of America. No party to this +Agreement will bring a legal action under this Agreement more than one year +after the cause of action arose. Each party waives its rights to a jury trial in +any resulting litigation. + diff --git a/Lock.C b/Lock.C new file mode 100644 index 0000000..8b59c3b --- /dev/null +++ b/Lock.C @@ -0,0 +1,45 @@ +/******************************************************************************* + * 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 +#include + +#include "Lock.h" + +Lock::Lock() +{ + pthread_mutex_init( &(this->mutex), NULL ); +} + +Lock::~Lock() +{ + pthread_mutex_destroy( &(this->mutex) ); +} + +void +Lock::lock() +{ + pthread_mutex_lock( &(this->mutex) ); +} + +int +Lock::test() +{ + pthread_mutex_trylock( &(this->mutex) ); +} + +void +Lock::unlock() +{ + pthread_mutex_unlock( &(this->mutex) ); +} + diff --git a/Lock.h b/Lock.h new file mode 100644 index 0000000..a820bef --- /dev/null +++ b/Lock.h @@ -0,0 +1,30 @@ +/******************************************************************************* + * 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 * + *******************************************************************************/ + + +#if !defined(Lock_h) +#define Lock_h + +#include + +class Lock { +public: + Lock(); + ~Lock(); + void lock(); + int test(); + void unlock(); + +private: + pthread_mutex_t mutex; +}; + +#endif diff --git a/Main.C b/Main.C new file mode 100644 index 0000000..ffd31d0 --- /dev/null +++ b/Main.C @@ -0,0 +1,89 @@ +/******************************************************************************* + * 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 + +#include "Main.h" + +#include "Run.h" +#include "Timer.h" +#include "Types.h" +#include "Output.h" +#include "Experiment.h" + + // This program allocates and accesses + // a number of blocks of memory, one or more + // for each thread that executes. Blocks + // are divided into sub-blocks called + // pages, and pages are divided into + // sub-blocks called cache lines. + // + // All pages are collected into a list. + // Pages are selected for the list in + // a particular order. Each cache line + // within the page is similarly gathered + // into a list in a particular order. + // In both cases the order may be random + // or linear. + // + // A root pointer points to the first + // cache line. A pointer in the cache + // line points to the next cache line, + // which contains a pointer to the cache + // line after that, and so on. This + // forms a pointer chain that touches all + // cache lines within the first page, + // then all cache lines within the second + // page, and so on until all pages are + // covered. The last pointer contains + // NULL, terminating the chain. + // + // Depending on compile-time options, + // pointers may be 32-bit or 64-bit + // pointers. + +int verbose = 0; + +int +main( int argc, char* argv[] ) +{ + Timer::calibrate(10000); + double clk_res = Timer::resolution(); + + Experiment e; + if (e.parse_args(argc, argv)) { + return 0; + } + +#if defined(UNDEFINED) + e.print(); + if (argv != NULL) return 0; +#endif + + SpinBarrier sb( e.num_threads ); + Run r[ e.num_threads ]; + for (int i=0; i < e.num_threads; i++) { + r[i].set( e, &sb ); + r[i].start(); + } + + for (int i=0; i < e.num_threads; i++) { + r[i].wait(); + } + + int64 ops = Run::ops_per_chain(); + double secs = Run::seconds(); + + Output::print(e, ops, secs, clk_res); + + return 0; +} diff --git a/Main.h b/Main.h new file mode 100644 index 0000000..98afdeb --- /dev/null +++ b/Main.h @@ -0,0 +1,18 @@ +/******************************************************************************* + * 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 * + *******************************************************************************/ + + +#if !defined(Main_h) +#define Main_h + +extern int verbose; + +#endif diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..dd8854f --- /dev/null +++ b/Makefile @@ -0,0 +1,34 @@ +SRC = Main.C Chain.C Experiment.C Lock.C Output.C Run.C SpinBarrier.C Timer.C Thread.C Types.C + +# +# BIT = { 32 | 64 } +# MODE = { NUMA | SMP } +# +BIT = 64 +# MODE = NUMA +MODE = SMP +# LIB = -lpthread -lnuma +LIB = -lpthread + +HDR = $(SRC:.C=.h) +OBJ = $(SRC:.C=.o) +EXE = pChase$(BIT)_$(MODE) + +RM = /bin/rm +MV = /bin/mv + +CXXFLAGS= -O3 -m$(BIT) -D$(MODE) + +.C.o: + $(CXX) -c $(CXXFLAGS) $< + +$(EXE): $(OBJ) + $(CXX) -o $(EXE) $(CXXFLAGS) $(OBJ) $(LIB) + +$(OBJ): $(HDR) + +rmexe: + $(RM) -rf $(EXE) + +rmobj: + $(RM) -rf $(OBJ) diff --git a/Output.C b/Output.C new file mode 100644 index 0000000..98071ee --- /dev/null +++ b/Output.C @@ -0,0 +1,153 @@ +/******************************************************************************* + * 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 +#include +#include + +#include "Output.h" + +#include "Types.h" +#include "Experiment.h" + + +void +Output::print( Experiment &e, int64 ops, double secs, double ck_res ) +{ + if (e.output_mode == Experiment::CSV) { + Output::csv(e, ops, secs, ck_res); + } else if (e.output_mode == Experiment::BOTH) { + Output::header(e, ops, secs, ck_res); + Output::csv(e, ops, secs, ck_res); + } else if (e.output_mode == Experiment::HEADER) { + Output::header(e, ops, secs, ck_res); + } else { + Output::table(e, ops, secs, ck_res); + } +} + +void +Output::header( Experiment &e, int64 ops, double secs, double ck_res ) +{ + printf("pointer size (bytes),"); + printf("cache line size (bytes),"); + printf("page size (bytes),"); + printf("chain size (bytes),"); + printf("thread size (bytes),"); + printf("test size (bytes),"); + printf("chains per thread,"); + printf("number of threads,"); + printf("iterations,"); + printf("experiments,"); + printf("access pattern,"); + printf("stride,"); + printf("numa placement,"); + printf("offset or mask,"); + printf("numa domains,"); + printf("domain map,"); + printf("operations per chain,"); + printf("total operations,"); + printf("elapsed time (seconds),"); + printf("elapsed time (timer ticks),"); + printf("clock resolution (ns),", ck_res * 1E9); + printf("memory latency (ns),"); + printf("memory bandwidth (MB/s)\n"); + + fflush(stdout); +} + +void +Output::csv( Experiment &e, int64 ops, double secs, double ck_res ) +{ + printf("%d,", e.pointer_size); + printf("%d,", e.bytes_per_line); + printf("%d,", e.bytes_per_page); + printf("%d,", e.bytes_per_chain); + printf("%d,", e.bytes_per_thread); + printf("%d,", e.bytes_per_test); + printf("%d,", e.chains_per_thread); + printf("%d,", e.num_threads); + printf("%d,", e.iterations); + printf("%d,", e.experiments); + printf("%s,", e.access()); + printf("%d,", e.stride); + printf("%s,", e.placement()); + printf("%d,", e.offset_or_mask); + printf("%d,", e.num_numa_domains); + printf("\""); + printf("%d:", e.thread_domain[0]); + printf("%d", e.chain_domain[0][0]); + for (int j=1; j < e.chains_per_thread; j++) { + printf(",%d", e.chain_domain[0][j]); + } + for (int i=1; i < e.num_threads; i++) { + printf(";%d:", e.thread_domain[i]); + printf("%d", e.chain_domain[i][0]); + for (int j=1; j < e.chains_per_thread; j++) { + printf(",%d", e.chain_domain[i][j]); + } + } + printf("\","); + printf("%d,", ops); + printf("%d,", ops * e.chains_per_thread * e.num_threads); + printf("%.3f,", secs); + printf("%.0f,", secs/ck_res); + printf("%.2f,", ck_res * 1E9); + printf("%.2f,", (secs / (ops * e.iterations)) * 1E9); + printf("%.3f\n", ((ops * e.iterations * e.chains_per_thread * e.num_threads * e.bytes_per_line) / secs) * 1E-6); + + fflush(stdout); +} + +void +Output::table( Experiment &e, int64 ops, double secs, double ck_res ) +{ + printf("pointer size = %d (bytes)\n", e.pointer_size); + printf("cache line size = %d (bytes)\n", e.bytes_per_line); + printf("page size = %d (bytes)\n", e.bytes_per_page); + printf("chain size = %d (bytes)\n", e.bytes_per_chain); + printf("thread size = %d (bytes)\n", e.bytes_per_thread); + printf("test size = %d (bytes)\n", e.bytes_per_test); + printf("chains per thread = %d\n", e.chains_per_thread); + printf("number of threads = %d\n", e.num_threads); + printf("iterations = %d\n", e.iterations); + printf("experiments = %d\n", e.experiments); + printf("access pattern = %s\n", e.access()); + printf("stride = %d\n", e.stride); + printf("numa placement = %s\n", e.placement()); + printf("offset or mask = %d\n", e.offset_or_mask); + printf("numa domains = %d\n", e.num_numa_domains); + printf("domain map = "); + printf("\""); + printf("%d:", e.thread_domain[0]); + printf("%d", e.chain_domain[0][0]); + for (int j=1; j < e.chains_per_thread; j++) { + printf(",%d", e.chain_domain[0][j]); + } + for (int i=1; i < e.num_threads; i++) { + printf(";%d:", e.thread_domain[i]); + printf("%d", e.chain_domain[i][0]); + for (int j=1; j < e.chains_per_thread; j++) { + printf(",%d", e.chain_domain[i][j]); + } + } + printf("\"\n"); + printf("operations per chain = %d\n", ops); + printf("total operations = %d\n", ops * e.chains_per_thread * e.num_threads); + printf("elapsed time = %.3f (seconds)\n", secs); + printf("elapsed time = %.0f (timer ticks)\n", secs/ck_res); + printf("clock resolution = %.2f (ns)\n", ck_res * 1E9); + printf("memory latency = %.2f (ns)\n", (secs / (ops * e.iterations)) * 1E9); + printf("memory bandwidth = %.3f (MB/s)\n", ((ops * e.iterations * e.chains_per_thread * e.num_threads * e.bytes_per_line) / secs) * 1E-6); + + fflush(stdout); +} diff --git a/Output.h b/Output.h new file mode 100644 index 0000000..9216988 --- /dev/null +++ b/Output.h @@ -0,0 +1,28 @@ +/******************************************************************************* + * 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 * + *******************************************************************************/ + + +#if !defined(Output_h) +#define Output_h + +#include "Types.h" +#include "Experiment.h" + +class Output { +public: + static void print ( Experiment &e, int64 ops, double secs, double ck_res ); + static void header( Experiment &e, int64 ops, double secs, double ck_res ); + static void csv ( Experiment &e, int64 ops, double secs, double ck_res ); + static void table ( Experiment &e, int64 ops, double secs, double ck_res ); +private: +}; + +#endif 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 +#include +#include + +#if defined(NUMA) +#include +#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; +} diff --git a/Run.h b/Run.h new file mode 100644 index 0000000..57a83bc --- /dev/null +++ b/Run.h @@ -0,0 +1,49 @@ +/******************************************************************************* + * 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 * + *******************************************************************************/ + + +#if !defined(Run_h) +#define Run_h + +#include "Thread.h" + +#include "Lock.h" +#include "Chain.h" +#include "Types.h" +#include "Experiment.h" +#include "SpinBarrier.h" + +class Run: public Thread { +public: + Run(); + ~Run(); + int run(); + void set( Experiment &e, SpinBarrier* sbp ); + + static int64 ops_per_chain() { return _ops_per_chain; } + static double seconds() { return _seconds; } + +private: + Experiment* exp; // experiment data + SpinBarrier* bp; // spin barrier used by all threads + + void mem_check( Chain *m ); + Chain* random_mem_init( Chain *m ); + Chain* forward_mem_init( Chain *m ); + Chain* reverse_mem_init( Chain *m ); + + static Lock global_mutex; // global lock + static int64 _ops_per_chain; // total number of operations per chain + static double _seconds; // total number of seconds +}; + + +#endif diff --git a/SpinBarrier.C b/SpinBarrier.C new file mode 100644 index 0000000..c150245 --- /dev/null +++ b/SpinBarrier.C @@ -0,0 +1,48 @@ +/******************************************************************************* + * 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 * + *******************************************************************************/ + + +/****************************************************************************** + * * + * SpinBarrier * + * * + * Author: Douglas M. Pase * + * * + * Date: September 21, 2000 * + * Translated to C++, June 19, 2005 * + * * + * void barrier() * + * * + ******************************************************************************/ +#include +#include + +#include "SpinBarrier.h" + + // create a new barrier +SpinBarrier::SpinBarrier(int participants) +: limit( participants ) +{ + pthread_barrier_init( &barrier_obj, NULL, this->limit ); +} + + // destroy an old barrier +SpinBarrier::~SpinBarrier() +{ +} + + // enter the barrier and wait. everyone leaves + // when the last participant enters the barrier. +void +SpinBarrier::barrier() +{ + pthread_barrier_wait( &this->barrier_obj ); +} diff --git a/SpinBarrier.h b/SpinBarrier.h new file mode 100644 index 0000000..27cb28d --- /dev/null +++ b/SpinBarrier.h @@ -0,0 +1,44 @@ +/******************************************************************************* + * 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 * + *******************************************************************************/ + + +/****************************************************************************** + * * + * SpinBarrier * + * * + * Author: Douglas M. Pase * + * * + * Date: September 21, 2000 * + * Translated to C++, June 19, 2005 * + * Rewritten August 13,2005 * + * * + * void barrier() * + * * + ******************************************************************************/ + +#if !defined( SpinBarrier_h ) +#define SpinBarrier_h + +#include + +class SpinBarrier { +public: + SpinBarrier(int participants); + ~SpinBarrier(); + + void barrier(); + +private: + int limit; // number of barrier participants + pthread_barrier_t barrier_obj; +}; + +#endif diff --git a/Thread.C b/Thread.C new file mode 100644 index 0000000..18bfefd --- /dev/null +++ b/Thread.C @@ -0,0 +1,86 @@ +/******************************************************************************* + * 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 +#include +#include + +#include "Thread.h" + +#include "Lock.h" + +Lock Thread::_global_lock; +int Thread::count = 0; + +Thread::Thread() +{ + Thread::global_lock(); + this->id = Thread::count; + Thread::count += 1; + Thread::global_unlock(); +} + +Thread::~Thread() +{ +} + +int +Thread::start() +{ + return pthread_create(&this->thread, NULL, Thread::start_routine, this); +} + +void* +Thread::start_routine(void* p) +{ + ((Thread*)p)->run(); + + return NULL; +} + +void +Thread::exit() +{ + pthread_exit(NULL); +} + +int +Thread::wait() +{ + pthread_join(this->thread, NULL); + + return 0; +} + +void +Thread::lock() +{ + this->object_lock.lock(); +} + +void +Thread::unlock() +{ + this->object_lock.unlock(); +} + +void +Thread::global_lock() +{ + Thread::_global_lock.lock(); +} + +void +Thread::global_unlock() +{ + Thread::_global_lock.unlock(); +} diff --git a/Thread.h b/Thread.h new file mode 100644 index 0000000..ddba894 --- /dev/null +++ b/Thread.h @@ -0,0 +1,53 @@ +/******************************************************************************* + * 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 * + *******************************************************************************/ + + +#if !defined(Thread_h) +#define Thread_h + +#include + +#include "Lock.h" + +class Thread { +public: + Thread(); + ~Thread(); + + virtual int run() = 0; + + int start(); + int wait(); + int thread_count() { return Thread::count; } + int thread_id() { return id; } + + static void exit(); + +protected: + void lock(); + void unlock(); + static void global_lock(); + static void global_unlock(); + +private: + static void* start_routine(void *); + static Lock _global_lock; + + Lock object_lock; + + pthread_t thread; + + static int count; + int id; + int lock_obj; +}; + +#endif diff --git a/Timer.C b/Timer.C new file mode 100644 index 0000000..d450867 --- /dev/null +++ b/Timer.C @@ -0,0 +1,175 @@ +/******************************************************************************* + * 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 +#include + +#include "Timer.h" + +#include "Types.h" + +static int64 read_rtc(); +static void calibrate_rtc(int n); +static double wall_seconds(); + +static int wall_ticks = -1; +static int rtc_ticks = -1; +static double wall_elapsed = -1; +static int64 rtc_elapsed = -1; +static double time_factor = -1; + +#if !defined(RTC) && !defined(GTOD) +#define RTC +#endif + +#if defined(RTC) + +double +Timer::seconds() +{ + return (double) read_rtc() * time_factor; +} + +int64 +Timer::ticks() +{ + // See pg. 406 of the AMD x86-64 Architecture + // Programmer's Manual, Volume 2, System Programming + unsigned int eax=0, edx=0; + + __asm__ __volatile__( + "rdtsc ;" + "movl %%eax,%0;" + "movl %%edx,%1;" + "" + : "=r"(eax), "=r"(edx) + : + : "%eax", "%edx" + ); + + return ((int64) edx << 32) | (int64) eax; +} + +static int64 +read_rtc() +{ + // See pg. 406 of the AMD x86-64 Architecture + // Programmer's Manual, Volume 2, System Programming + unsigned int eax=0, edx=0; + + __asm__ __volatile__( + "rdtsc ;" + "movl %%eax,%0;" + "movl %%edx,%1;" + "" + : "=r"(eax), "=r"(edx) + : + : "%eax", "%edx" + ); + + return ((int64) edx << 32) | (int64) eax; +} + +void +Timer::calibrate() +{ + Timer::calibrate(1000); +} + +void +Timer::calibrate(int n) +{ + wall_ticks = n; + + double wall_start,wall_finish,t; + t = wall_seconds(); + while (t == (wall_start=wall_seconds())) { + ; + } + int64 rtc_start = read_rtc(); + for (int i=0; i < wall_ticks; i++) { + t = wall_seconds(); + while (t == (wall_finish=wall_seconds())) { + ; + } + } + int64 rtc_finish = read_rtc(); + + wall_elapsed = wall_finish - wall_start; + rtc_elapsed = rtc_finish - rtc_start; + time_factor = wall_elapsed / (double) rtc_elapsed; +} + +static double +wall_seconds() +{ + struct timeval t; + gettimeofday(&t, NULL); + + return (double) t.tv_sec + (double) t.tv_usec * 1E-6; +} + +#else + +double +Timer::seconds() +{ + struct timeval t; + gettimeofday(&t, NULL); + + return (double) t.tv_sec + (double) t.tv_usec * 1E-6; +} + +int64 +Timer::ticks() +{ + struct timeval t; + gettimeofday(&t, NULL); + + return 1000000 * (int64) t.tv_sec + (int64) t.tv_usec; +} + +void +Timer::calibrate() +{ +} + +void +Timer::calibrate(int n) +{ +} + +#endif + +static double +min( double v1, double v2 ) +{ + if (v2 < v1) return v2; + return v1; +} + +double +Timer::resolution() +{ + double a,b,c=1E9; + for (int i=0; i < 10; i++) { + a = Timer::seconds(); + while (a == (b=Timer::seconds())) + ; + a = Timer::seconds(); + while (a == (b=Timer::seconds())) + ; + c = min(b - a, c); + } + + return c; +} diff --git a/Timer.h b/Timer.h new file mode 100644 index 0000000..164af1d --- /dev/null +++ b/Timer.h @@ -0,0 +1,28 @@ +/******************************************************************************* + * 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 * + *******************************************************************************/ + + +#if !defined(Timer_h) +#define Timer_h + +#include "Types.h" + +class Timer { +public: + static double seconds(); + static double resolution(); + static int64 ticks(); + static void calibrate(); + static void calibrate(int n); +private: +}; + +#endif diff --git a/Types.C b/Types.C new file mode 100644 index 0000000..d1ba66f --- /dev/null +++ b/Types.C @@ -0,0 +1,13 @@ +/******************************************************************************* + * 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 "Types.h" diff --git a/Types.h b/Types.h new file mode 100644 index 0000000..294b9ce --- /dev/null +++ b/Types.h @@ -0,0 +1,29 @@ +/******************************************************************************* + * 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 * + *******************************************************************************/ + + +#if !defined(Types_h) +#define Types_h + +typedef long long int64; +typedef int int32; +typedef short int16; +typedef char int8; + +typedef unsigned long long uint64; +typedef unsigned int uint32; +typedef unsigned short uint16; +typedef unsigned char uint8; + +typedef double float64; +typedef float float32; + +#endif diff --git a/pChase.sh b/pChase.sh new file mode 100755 index 0000000..5065d28 --- /dev/null +++ b/pChase.sh @@ -0,0 +1,39 @@ +#!/bin/bash + +pgm=./pChase64_NUMA + +b=(8k 16k 24k 32k 48k 64k 96k 128k 192k 256k 384k 512k 768k 1m 1536k 2m 3m 4m 6m 8m 12m 16m ) +s=(2m 2m 1536k 1m 96k 64k 48k 32k 24k 16k 12k 8k 6k 1k 768 512 384 256 192 128 96 64 ) +c=5 + +date +uname -a +echo +$pgm -o hdr +for page in 4k 8k 16k +do + for threads in 1 2 + do + for refs in 1 2 4 + do + for offset in 0 1 + do + for access in random "forward 1" + do + for ((i=0; $i < ${#s[*]}; i++)) + do + for ((j=0; $j < $c; j++)) + do + $pgm -p $page -t $threads -r $refs -n add $offset -a $access -c ${b[$i]} -i ${s[$i]} -o csv + done + done + done + done + done + done +done +echo +cat /proc/cpuinfo +cat /proc/meminfo +date + diff --git a/pChase64_NUMA b/pChase64_NUMA new file mode 100755 index 0000000..7086a99 Binary files /dev/null and b/pChase64_NUMA differ diff --git a/pChase64_SMP b/pChase64_SMP new file mode 100755 index 0000000..d61d2d9 Binary files /dev/null and b/pChase64_SMP differ diff --git a/run-pChase.sh b/run-pChase.sh new file mode 100755 index 0000000..cc88801 --- /dev/null +++ b/run-pChase.sh @@ -0,0 +1,5 @@ +#!/bin/bash + +dt=`date "+%Y-%m-%d-%H%M"` + +./pChase.sh | tee pc-${dt}.csv -- cgit v1.2.3