AMP PriorityQueue

From Pheet
Jump to: navigation, search

Contents

Interface

Your own priority queue implementation should adhere to the following interface:

// Replace Classname with the name of your Queue/Stack
template <class Pheet, typename TT>
class Classname {
public:
  Classname();
  ~Classname();

  void push(TT const& item);
  bool try_pop(TT& item);
  bool try_peek(TT& item);

  size_t size(); // Does not have to be exact, but needs to be > 0 if not empty

  static void print_name() {
    // Should also print some relevant configuration parameters if applicable
    std::cout << "Classname"; 
    // Also print name of Mutex used, in case you use locks
  }
};

Optionally, comparison based priority queues should have a third template parameter class Comparator = std::less<TT>. Due to limitations of C++ with regard to optional template parameters, such implementations cannot be plugged in directly into the benchmark. This can be worked around using a template alias as follows:

template <class Pheet, typename TT>
using ClassnameX = Classname<Pheet, TT>;

The template alias ClassnameX will provide an alias where there exists no third, optional, template parameter, thus making the compiler happy.

Add to stress test benchmark

Edit the file test/ds_stress/DsStressTests.cpp. Add an include directive to include your newly created data structure.

Add your own implementation to the run_test method by adding this line:

this->stress_test<PheetS2,
    YourImplementation,
    LinearDsTest>();

You can also comment out any tests there that you are not interested in.

Running the benchmark

Switch to the stress test benchmark by editing test/settings.h, and setting the macro ACTIVE_TEST to test/test_variants/ds.h. You can change the exact configuration of the test inside ds.h.

The compiler (default: g++), include and library paths can be set in the file settings.mk. To compile, enter the following on the command line:

make test
bin/pheet_test

The output of the benchmarks is in a tab-separated text-format, where each line of data is preceded with a line of headers and can be piped into a file. The output can be converted to a better to process format (csv with one row of headers at the beginning of the file) using the perl-script csvheet in the Pheet main directory.

Header dependencies are not tracked by the Pheet makefile right now, so if you change your lock implementation you might need to run make clean before your changes are applied on a recompile.

Configuration of benchmark and interpretation of results

You can change the configuration of the benchmark by editing test/test_variants/ds.h.

The following line allows to change the number of CPUs used for the experiments. It is recommended to run the tests with different numbers of processors to see scalability trends.

const procs_t ds_stress_test_cpus[] = {1, 2, 4, 8};

So far, Pheet only contains throughput tests. These tests count the number of successful push/pop/peek operations by all threads within one second. To give some intuition on fairness we also store the minimum and maximum number per type of operation by a single thread. Other types of tests (most importantly a test for correctness) will be added in the future.

const int ds_stress_test_types[] = {0};

We allow to explicitly set the random seeds used for the experiments, which adds some determinism to the experiments and thus reproducibility and better comparability between data structure implementations. We also use the random seeds to configure the number of repetitions of the experiments (each random seed is one repetition). For your final measurement, to get statistically significant results, you should run each experiment more than once. (As a rule of thumb, 20 experiments should suffice, unless your results exhibit high variance).

const unsigned int ds_stress_test_seed_first = 0;
const unsigned int ds_stress_test_seed_last = 0;

For the experiments all threads share a single instance of your data structure. Before the start of the experiment this data structure is pre-filled with a configurable amount of data.

const unsigned int ds_stress_test_prefill[] = {10000, 1000000};

The pattern by which the data structure is accessed is also configurable. So far we support the following patterns, with more being added in the future: 0: Each thread will perform a push or a pop at each iteration with equal probability. 1: Each thread is assigned a role and will either push or pop data all the time.

const unsigned int ds_stress_test_linear_dist[] = {0, 1};
Personal tools
Namespaces

Variants
Actions
Navigation
Tools