diff options
| -rw-r--r-- | Chain.C | 24 | ||||
| -rw-r--r-- | Chain.h | 24 | ||||
| -rw-r--r-- | Experiment.C | 542 | ||||
| -rw-r--r-- | Experiment.h | 100 | ||||
| -rw-r--r-- | License.htm | 267 | ||||
| -rw-r--r-- | License.txt | 214 | ||||
| -rw-r--r-- | Lock.C | 45 | ||||
| -rw-r--r-- | Lock.h | 30 | ||||
| -rw-r--r-- | Main.C | 89 | ||||
| -rw-r--r-- | Main.h | 18 | ||||
| -rw-r--r-- | Makefile | 34 | ||||
| -rw-r--r-- | Output.C | 153 | ||||
| -rw-r--r-- | Output.h | 28 | ||||
| -rw-r--r-- | Run.C | 761 | ||||
| -rw-r--r-- | Run.h | 49 | ||||
| -rw-r--r-- | SpinBarrier.C | 48 | ||||
| -rw-r--r-- | SpinBarrier.h | 44 | ||||
| -rw-r--r-- | Thread.C | 86 | ||||
| -rw-r--r-- | Thread.h | 53 | ||||
| -rw-r--r-- | Timer.C | 175 | ||||
| -rw-r--r-- | Timer.h | 28 | ||||
| -rw-r--r-- | Types.C | 13 | ||||
| -rw-r--r-- | Types.h | 29 | ||||
| -rwxr-xr-x | pChase.sh | 39 | ||||
| -rwxr-xr-x | pChase64_NUMA | bin | 0 -> 47016 bytes | |||
| -rwxr-xr-x | pChase64_SMP | bin | 0 -> 46208 bytes | |||
| -rwxr-xr-x | run-pChase.sh | 5 |
27 files changed, 2898 insertions, 0 deletions
@@ -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 <stdio.h> + +#include "Chain.h" + +Chain::Chain() +: next(NULL) +{ +} + +Chain::~Chain() +{ +} @@ -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 <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#if defined(NUMA) +#include <numa.h> +#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 <stride> exclusive OR and mask + // reverse <stride> 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 <mask> exclusive OR and mask + // add <offset> addition and offset + // map <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 <options>\n", argv[0]); + printf("where <options> are selected from the following:\n"); + printf(" [-h|--help] # this message\n"); + printf(" [-l|--line] <number> # bytes per cache line (cache line size)\n"); + printf(" [-p|--page] <number> # bytes per page (page size)\n"); + printf(" [-c|--chain] <number> # bytes per chain (used to compute pages per chain)\n"); + printf(" [-r|--references] <number> # chains per thread (memory loading)\n"); + printf(" [-t|--threads] <number> # number of threads (concurrency and contention)\n"); + printf(" [-i|--iterations] <number> # iterations\n"); + printf(" [-e|--experiments] <number> # experiments\n"); + printf(" [-a|--access] <pattern> # memory access pattern\n"); + printf(" [-o|--output] <format> # output format\n"); + printf(" [-n|--numa] <placement> # numa placement\n"); + printf(" [-s|--strict] # fail rather than adjust options to sensible values\n"); + printf("\n"); + printf("<pattern> is selected from the following:\n"); + printf(" random # all chains are accessed randomly\n"); + printf(" forward <stride> # chains are in forward order with constant stride\n"); + printf(" reverse <stride> # chains are in reverse order with constant stride\n"); + printf("\n"); + printf("Note: <stride> is always a small positive integer.\n"); + printf("\n"); + printf("<format> 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("<placement> is selected from the following:\n"); + printf(" local # all chains are allocated locally\n"); + printf(" xor <mask> # exclusive OR and mask\n"); + printf(" add <offset> # addition and offset\n"); + printf(" map <map> # explicit mapping of threads and chains to domains\n"); + printf("\n"); + printf("<map> 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 @@ +<h1>Common Public License Version 1.0</h1> + +<tt> + +<p>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. </p> + + + +<p><b>1. DEFINITIONS </b></p> + +<p>"Contribution" means:</p> + +<blockquote> +<p>a) in the case of the initial Contributor, the initial code and documentation + distributed under this Agreement, and </p> +<p> +b) in the case of each subsequent Contributor:</p> +<p> +i) changes to the Program, and</p> +<p> +ii) additions to the Program;</p> + +<p>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.</p> +</blockquote> + + + +<p>"Contributor" means any person or entity that distributes the Program. </p> + + + +<p>"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.</p> + + + +<p>"Program" means the Contributions distributed in accordance with this + Agreement. </p> + + + +<p>"Recipient" means anyone who receives the Program under this Agreement, + including all Contributors. </p> + + + +<p><b>2. GRANT OF RIGHTS</b></p> + +<blockquote> +<p>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.</p> +<p> + +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.</p> + +<p>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.</p> + +<p>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.</p></blockquote> + + +<p><strong>3. REQUIREMENTS</strong> </p> + +<p>A Contributor may choose to distribute the Program in object code form under + its own license agreement, provided that: </p> + +<blockquote> +<p>a) it complies with the terms and conditions of this Agreement; and</p> + +<p> +b) its license agreement:</p> + +<p>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; +</p> +<p>ii) effectively excludes on behalf of all Contributors all liability for + damages, including direct, indirect, special, incidental and consequential + damages, such as lost profits; +</p> +<p>iii) states that any provisions which differ from this Agreement are offered + by that Contributor alone and not by any other party; and +</p> +<p>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. +</p></blockquote> + +<p> + +When the Program is made available in source code form:</p> + +<blockquote><p> + a) it must be made available under this Agreement; and</p> + <p> + b) a copy of this Agreement must be included with each copy of the Program. +</p></blockquote> + + +<p>Contributors may not remove or alter any copyright notices contained within + the Program.</p> + + + + + +<p>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. </p> + + +<p><strong>4. COMMERCIAL DISTRIBUTION</strong> </p> + +<p>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. +</p> + + +<p>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. +</p> + +<p><strong>5. NO WARRANTY</strong></p> + +<p> +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. + </p> + + +<p><strong> +6. DISCLAIMER OF LIABILITY </strong></p> + +<p>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. +</p> + +<p><strong>7. GENERAL</strong></p> + +<p>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. </p> + + + +<p>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.</p> + + + +<p>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. </p> + + + +<p>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. </p> + + + +<p>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.</p> + + +</tt> 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. + @@ -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 <stdio.h> +#include <pthread.h> + +#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) ); +} + @@ -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 <pthread.h> + +class Lock { +public: + Lock(); + ~Lock(); + void lock(); + int test(); + void unlock(); + +private: + pthread_mutex_t mutex; +}; + +#endif @@ -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 <stdio.h> + +#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; +} @@ -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 <stdio.h> +#include <stdlib.h> +#include <string.h> + +#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 @@ -0,0 +1,761 @@ +/******************************************************************************* + * Copyright (c) 2006 International Business Machines Corporation. * + * All rights reserved. This program and the accompanying materials * + * are made available under the terms of the Common Public License v1.0 * + * which accompanies this distribution, and is available at * + * http://www.opensource.org/licenses/cpl1.0.php * + * * + * Contributors: * + * Douglas M. pase - initial API and implementation * + *******************************************************************************/ + + +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> + +#if defined(NUMA) +#include <numa.h> +#endif + +#include "Run.h" + +#include "Chain.h" +#include "Timer.h" +#include "SpinBarrier.h" + + +static double min( double v1, double v2 ); + +Lock Run::global_mutex; +int64 Run::_ops_per_chain = 0; +double Run::_seconds = 1E9; + + +Run::Run() +: exp(NULL), bp(NULL) +{ +} + +Run::~Run() +{ +} + +void +Run::set( Experiment &e, SpinBarrier* sbp ) +{ + this->exp = &e; + this->bp = sbp; +} + +int +Run::run() +{ + // first allocate all memory for the chains, + // making sure it is allocated within the + // intended numa domains + Chain** chain_memory = new Chain* [ this->exp->chains_per_thread ]; + Chain** root = new Chain* [ this->exp->chains_per_thread ]; + +#if defined(NUMA) + // establish the node id where this thread + // will run. threads are mapped to nodes + // by the set-up code for Experiment. + int run_node_id = this->exp->thread_domain[this->thread_id()]; + numa_run_on_node(run_node_id); + + // establish the node id where this thread's + // memory will be allocated. + for (int i=0; i < this->exp->chains_per_thread; i++) { + int alloc_node_id = this->exp->chain_domain[this->thread_id()][i]; + nodemask_t alloc_mask; + nodemask_zero(&alloc_mask); + nodemask_set(&alloc_mask, alloc_node_id); + numa_set_membind(&alloc_mask); + + chain_memory[i] = new Chain[ this->exp->links_per_chain ]; + } +#else + for (int i=0; i < this->exp->chains_per_thread; i++) { + chain_memory[i] = new Chain[ this->exp->links_per_chain ]; + } +#endif + + for (int i=0; i < this->exp->chains_per_thread; i++) { + if (this->exp->access_pattern == Experiment::RANDOM) { + root[i] = random_mem_init( chain_memory[i] ); + } else if (0 < this->exp->stride) { + root[i] = forward_mem_init( chain_memory[i] ); + } else { + root[i] = reverse_mem_init( chain_memory[i] ); + } + } + + // barrier + for (int e=-1; e <= this->exp->experiments; e++) { + this->bp->barrier(); + + // start timer + double start = 0; + if (this->thread_id() == 0) start = Timer::seconds(); + this->bp->barrier(); + + // chase pointers + if (this->exp->chains_per_thread == 1) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + while (a != NULL) { + a = a->next; + } + this->mem_check( a ); + } + } else if (this->exp->chains_per_thread == 2) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + while (a != NULL) { + a = a->next; + b = b->next; + } + this->mem_check( a ); + this->mem_check( b ); + } + } else if (this->exp->chains_per_thread == 3) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + } + } else if (this->exp->chains_per_thread == 4) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + } + } else if (this->exp->chains_per_thread == 5) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + } + } else if (this->exp->chains_per_thread == 6) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + Chain* f = root[5]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + f = f->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + this->mem_check( f ); + } + } else if (this->exp->chains_per_thread == 7) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + Chain* f = root[5]; + Chain* g = root[6]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + f = f->next; + g = g->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + this->mem_check( f ); + this->mem_check( g ); + } + } else if (this->exp->chains_per_thread == 8) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + Chain* f = root[5]; + Chain* g = root[6]; + Chain* h = root[7]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + f = f->next; + g = g->next; + h = h->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + this->mem_check( f ); + this->mem_check( g ); + this->mem_check( h ); + } + } else if (this->exp->chains_per_thread == 9) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + Chain* f = root[5]; + Chain* g = root[6]; + Chain* h = root[7]; + Chain* j = root[8]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + f = f->next; + g = g->next; + h = h->next; + j = j->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + this->mem_check( f ); + this->mem_check( g ); + this->mem_check( h ); + this->mem_check( j ); + } + } else if (this->exp->chains_per_thread == 10) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + Chain* f = root[5]; + Chain* g = root[6]; + Chain* h = root[7]; + Chain* j = root[8]; + Chain* k = root[9]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + f = f->next; + g = g->next; + h = h->next; + j = j->next; + k = k->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + this->mem_check( f ); + this->mem_check( g ); + this->mem_check( h ); + this->mem_check( j ); + this->mem_check( k ); + } + } else if (this->exp->chains_per_thread == 11) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + Chain* f = root[5]; + Chain* g = root[6]; + Chain* h = root[7]; + Chain* j = root[8]; + Chain* k = root[9]; + Chain* l = root[10]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + f = f->next; + g = g->next; + h = h->next; + j = j->next; + k = k->next; + l = l->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + this->mem_check( f ); + this->mem_check( g ); + this->mem_check( h ); + this->mem_check( j ); + this->mem_check( k ); + this->mem_check( l ); + } + } else if (this->exp->chains_per_thread == 12) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + Chain* f = root[5]; + Chain* g = root[6]; + Chain* h = root[7]; + Chain* j = root[8]; + Chain* k = root[9]; + Chain* l = root[10]; + Chain* m = root[11]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + f = f->next; + g = g->next; + h = h->next; + j = j->next; + k = k->next; + l = l->next; + m = m->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + this->mem_check( f ); + this->mem_check( g ); + this->mem_check( h ); + this->mem_check( j ); + this->mem_check( k ); + this->mem_check( l ); + this->mem_check( m ); + } + } else if (this->exp->chains_per_thread == 13) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + Chain* f = root[5]; + Chain* g = root[6]; + Chain* h = root[7]; + Chain* j = root[8]; + Chain* k = root[9]; + Chain* l = root[10]; + Chain* m = root[11]; + Chain* n = root[12]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + f = f->next; + g = g->next; + h = h->next; + j = j->next; + k = k->next; + l = l->next; + m = m->next; + n = n->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + this->mem_check( f ); + this->mem_check( g ); + this->mem_check( h ); + this->mem_check( j ); + this->mem_check( k ); + this->mem_check( l ); + this->mem_check( m ); + this->mem_check( n ); + } + } else if (this->exp->chains_per_thread == 14) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + Chain* f = root[5]; + Chain* g = root[6]; + Chain* h = root[7]; + Chain* j = root[8]; + Chain* k = root[9]; + Chain* l = root[10]; + Chain* m = root[11]; + Chain* n = root[12]; + Chain* o = root[13]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + f = f->next; + g = g->next; + h = h->next; + j = j->next; + k = k->next; + l = l->next; + m = m->next; + n = n->next; + o = o->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + this->mem_check( f ); + this->mem_check( g ); + this->mem_check( h ); + this->mem_check( j ); + this->mem_check( k ); + this->mem_check( l ); + this->mem_check( m ); + this->mem_check( n ); + this->mem_check( o ); + } + } else if (this->exp->chains_per_thread == 15) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + Chain* f = root[5]; + Chain* g = root[6]; + Chain* h = root[7]; + Chain* j = root[8]; + Chain* k = root[9]; + Chain* l = root[10]; + Chain* m = root[11]; + Chain* n = root[12]; + Chain* o = root[13]; + Chain* p = root[14]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + f = f->next; + g = g->next; + h = h->next; + j = j->next; + k = k->next; + l = l->next; + m = m->next; + n = n->next; + o = o->next; + p = p->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + this->mem_check( f ); + this->mem_check( g ); + this->mem_check( h ); + this->mem_check( j ); + this->mem_check( k ); + this->mem_check( l ); + this->mem_check( m ); + this->mem_check( n ); + this->mem_check( o ); + this->mem_check( p ); + } + } else if (this->exp->chains_per_thread == 16) { + for (int i=0; i < this->exp->iterations; i++) { + Chain* a = root[0]; + Chain* b = root[1]; + Chain* c = root[2]; + Chain* d = root[3]; + Chain* e = root[4]; + Chain* f = root[5]; + Chain* g = root[6]; + Chain* h = root[7]; + Chain* j = root[8]; + Chain* k = root[9]; + Chain* l = root[10]; + Chain* m = root[11]; + Chain* n = root[12]; + Chain* o = root[13]; + Chain* p = root[14]; + Chain* q = root[15]; + while (a != NULL) { + a = a->next; + b = b->next; + c = c->next; + d = d->next; + e = e->next; + f = f->next; + g = g->next; + h = h->next; + j = j->next; + k = k->next; + l = l->next; + m = m->next; + n = n->next; + o = o->next; + p = p->next; + q = q->next; + } + this->mem_check( a ); + this->mem_check( b ); + this->mem_check( c ); + this->mem_check( d ); + this->mem_check( e ); + this->mem_check( f ); + this->mem_check( g ); + this->mem_check( h ); + this->mem_check( j ); + this->mem_check( k ); + this->mem_check( l ); + this->mem_check( m ); + this->mem_check( n ); + this->mem_check( o ); + this->mem_check( p ); + this->mem_check( q ); + } + } + // barrier + this->bp->barrier(); + + // stop timer + double stop = 0; + if (this->thread_id() == 0) stop = Timer::seconds(); + this->bp->barrier(); + + if (0 <= e) { + if (this->thread_id() == 0) { + double delta = stop - start; + if (0 < delta) { + Run::_seconds = min( Run::_seconds, delta ); + } + } + } + } + + this->bp->barrier(); + + + for (int i=0; i < this->exp->chains_per_thread; i++) { + if (chain_memory[i] != NULL) delete [] chain_memory[i]; + } + if (chain_memory != NULL) delete [] chain_memory; + + return 0; +} + +int dummy = 0; +void +Run::mem_check( Chain *m ) +{ + if (m == NULL) dummy += 1; +} + +static double +min( double v1, double v2 ) +{ + if (v2 < v1) return v2; + return v1; +} + + // exclude 2 and mersienne primes, i.e., + // primes of the form 2**n - 1, e.g., + // 3, 7, 31, 127 +static const int prime_table[] = { 5, 11, 13, 17, 19, 23, 37, 41, 43, 47, + 53, 61, 71, 73, 79, 83, 89, 97, 101, 103, 109, 113, 131, 137, 139, 149, + 151, 157, 163, }; +static const int prime_table_size = sizeof prime_table / sizeof prime_table[0]; + +Chain* +Run::random_mem_init( Chain *mem ) +{ + // initialize pointers -- + // choose a page at random, then use + // one pointer from each cache line + // within the page. all pages and + // cache lines are chosen at random. + Chain* root = NULL; + Chain* prev = NULL; + int link_within_line = 0; + int64 local_ops_per_chain = 0; + + // we must set a lock because random() + // is not thread safe + Run::global_mutex.lock(); + setstate(this->exp->random_state[this->thread_id()]); + int page_factor = prime_table[ random() % prime_table_size ]; + int page_offset = random() % this->exp->pages_per_chain; + Run::global_mutex.unlock(); + + // loop through the pages + for (int i=0; i < this->exp->pages_per_chain; i++) { + int page = (page_factor * i + page_offset) % this->exp->pages_per_chain; + Run::global_mutex.lock(); + setstate(this->exp->random_state[this->thread_id()]); + int line_factor = prime_table[ random() % prime_table_size ]; + int line_offset = random() % this->exp->lines_per_page; + Run::global_mutex.unlock(); + + // loop through the lines within a page + for (int j=0; j < this->exp->lines_per_page; j++) { + int line_within_page = (line_factor * j + line_offset) % this->exp->lines_per_page; + int link = page * this->exp->links_per_page + line_within_page * this->exp->links_per_line + link_within_line; + + if (root == NULL) { +// printf("root = %d(%d)[0x%x].\n", page, line_within_page, mem+link); + prev = root = mem + link; + local_ops_per_chain += 1; + } else { +// printf("0x%x = %d(%d)[0x%x].\n", prev, page, line_within_page, mem+link); + prev->next = mem + link; + prev = prev->next; + local_ops_per_chain += 1; + } + } + } + + Run::global_mutex.lock(); + Run::_ops_per_chain = local_ops_per_chain; + Run::global_mutex.unlock(); + + return root; +} + +Chain* +Run::forward_mem_init( Chain *mem ) +{ + Chain* root = NULL; + Chain* prev = NULL; + int link_within_line = 0; + int64 local_ops_per_chain = 0; + + for (int i=0; i < this->exp->lines_per_chain; i += this->exp->stride) { + int link = i * this->exp->links_per_line + link_within_line; + if (root == NULL) { +// printf("root = %d(%d)[0x%x].\n", page, line_within_page, mem+link); + prev = root = mem + link; + local_ops_per_chain += 1; + } else { +// printf("0x%x = %d(%d)[0x%x].\n", prev, page, line_within_page, mem+link); + prev->next = mem + link; + prev = prev->next; + local_ops_per_chain += 1; + } + } + + Run::global_mutex.lock(); + Run::_ops_per_chain = local_ops_per_chain; + Run::global_mutex.unlock(); + + return root; +} + +Chain* +Run::reverse_mem_init( Chain *mem ) +{ + Chain* root = NULL; + Chain* prev = NULL; + int link_within_line = 0; + int64 local_ops_per_chain = 0; + + int stride = -this->exp->stride; + int last; + for (int i=0; i < this->exp->lines_per_chain; i += stride) { + last = i; + } + + for (int i=last; 0 <= i; i -= stride) { + int link = i * this->exp->links_per_line + link_within_line; + if (root == NULL) { +// printf("root = %d(%d)[0x%x].\n", page, line_within_page, mem+link); + prev = root = mem + link; + local_ops_per_chain += 1; + } else { +// printf("0x%x = %d(%d)[0x%x].\n", prev, page, line_within_page, mem+link); + prev->next = mem + link; + prev = prev->next; + local_ops_per_chain += 1; + } + } + + Run::global_mutex.lock(); + Run::_ops_per_chain = local_ops_per_chain; + Run::global_mutex.unlock(); + + return root; +} @@ -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 <stdio.h>
+#include <pthread.h>
+
+#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 <pthread.h>
+
+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 <stdio.h> +#include <pthread.h> +#include <unistd.h> + +#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 <pthread.h> + +#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 @@ -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 <stdio.h> +#include <sys/time.h> + +#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; +} @@ -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 @@ -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" @@ -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 Binary files differnew file mode 100755 index 0000000..7086a99 --- /dev/null +++ b/pChase64_NUMA diff --git a/pChase64_SMP b/pChase64_SMP Binary files differnew file mode 100755 index 0000000..d61d2d9 --- /dev/null +++ b/pChase64_SMP 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 |