Concurrent Algorithms

Setup/Install

Install General Dependencies

sudo apt-get install -y build-essential libgtest-dev librange-v3-dev libyaml-cpp-dev libeigen3-dev libtbb-dev libboost-thread-dev

Install Argparse

git clone https://github.com/morrisfranken/argparse.git
cd argparse
mkdir build && cd build
cmake ..
make -j8
sudo make install

Install Magic Enum

mkdir magic_enum && cd magic_enum
wget https://github.com/Neargye/magic_enum/releases/download/v0.9.6/magic_enum-v0.9.6.tar.gz
tar -xzvf magic_enum-v0.9.6.tar.gz && rm magic_enum-v0.9.6.tar.gz
mkdir build && cd build
cmake .. -DMAGIC_ENUM_OPT_BUILD_TESTS=OFF
make -j8
sudo make install

Install Python Dependencies

Developed with python=3.12

pip install -r requirements.txt

Run Program

sudo make main

This will build the file ./bin/main and run it. The file will increment a shared counter 100 times, and each thread will output the indices that it incremented. sudo is required to set the priorities and avoid interruption (you can still interrupt on a non-real-time kernel).

Run Experiments

sudo make run EXPERIMENT=$experiment_name FLAGS="$flags" DESCRIPTION="optional description"

All experiments have the argument -c or --num-cpus to specify the number of CPUs to use. For more options, set flags=--help. This will create directories with the following structure:

.
├── logs
│   ├── EXPERIMENT
│   │   ├── YYYYMMDDHHMMSSNNNNNNNNN
│   │   │   ├── config.yaml  # experiment configuration
│   │   │   ├── description.txt  # contents of DESCRIPTION variable
│   │   │   ├── flags  # copy of FLAGS variable
│   │   │   ├── git  # parent commit hash
│   │   │   └── log.tsv  # log with output of all runs

The full list of experiments is available in ./include/experiment/experiments.hpp as ExperimentTag:

• arraysum: comparison of array sum ordering patterns
• benchmarksorting: benchmarking sorting algorithm implementations
• blocklistsize: comparison of block sizes for blocklist and comparison to STL libraries
• find: comparison of block sizes for finding the first needle in a haystack
• findall: comparison of memory reservation patterns for finding all needles in a haystack
• findany: comparison of checking strategies for finding a needle in a haystack
• lockspeed: benchmarking different lock implementations
• mapchunksize: comparison of chunk sizes for map algorithms
• matrixblocktransposeorder: comparison of different row/column orderings when transposing a matrix
• matrixtransposeblocksize: comparison of different block sizes and orderings when transposing a matrix
• matrixtransposeiterator: comparison of different methods for iterating over a matrix during transposition
• matrixtransposeorder: comparison of order for iterating over rows and columns when transposing a matrix
• matrixtransposeparallelsplit: comparison of different ways to split up a matrix for parallelisation
• matrixtransposevariants: benchmarking different implementations of matrix transpose
• mergesortmemorycomparison: comparison of different memory management strategies for mergesort
• mergesortrecursion: comparison of data structures for managing recursion when performing mergesort
• mrswspeed: benchmarking different MRSW lock implementations
• parallelmergesort: benchmarking parallel mergesort algorithms
• pingpongmergesortbenchmark: benchmarking ping-pong mergesort against default implementation
• privatequeuesize: comparison of private queue sizes for chunked map algorithm
• quicksortminsize: comparison of minimum sizes for parallelisation of the quicksort algorithm
• quicksortrecursion: comparison of data structures for managing recursion when performing quicksort
• reducebenchmark: benchmarking reduce algorithm implementations
• reduceblocksize: comparison of block sizes for the reduce algorithm

Advanced Usage

It is also possible to run experiments directly from the experiment binary. First, build the experiment binary:

make ./bin/experiment

Then run

sudo ./bin/experiment EXPERIMENT_NAME DIRECTORY [FLAGS]...

This means all the outputs will have root as the owner, so you will manually have to change the permissions. The permissions will be updated automatically if run via the Makefile.

Scripts

The main scripts are ./scripts/merge.py and ./scripts/visualize.py. All other files are utilities or test files.

Merging Experiments

Some experiments require separate runs (for example, running an experiment on different numbers of CPUs) and will therefore be stored in separate folders. ./scripts/merge.py allows you to merge these results into a single directory.

usage: merge.py [-h] [--attributes [ATTRIBUTES ...]] [--repeated]
                directories [directories ...]

positional arguments:
  directories           Directories with logs to merge.

options:
  -h, --help            show this help message and exit
  --attributes [ATTRIBUTES ...]
                        Attributes to merge.
  --repeated            Allow repeated shared attributes.

For example, running

python scripts/merge.py logs/cpu-1 logs/cpu-2 logs/cpu-4 --attributes num_cpus

will generate ./logs/merge-cpu--1-2-4 containing all the log data with an extra column num_cpus, which is taken out of the config.yaml file. It will ensure that all other config attributes are the same in all log directories (for example, the compiler).
The --repeated option is useful when merging experiments that share the same merged attributes, for example, if their log.tsv files contain outputs generated with different seeds.

Visualizing Results

After running, ./scripts/visualize.py is useful for generating plots. It takes in a single directory, which contains the logs and config. You can then specify chart attributes - important ones are

positional arguments:
  directory

options:
  --chart-type {box,scatter,strip}, -t {box,scatter,strip}, --chart {box,scatter,strip}
  --x X, -x X
  --y Y, -y Y
  --color COLOR, -c COLOR

These arguments are fed directly into Plotly when plotting the chart. For example running

python scripts/visualize.py resources/demo-plot/ -t strip -x num_cpus -y duration -c algorithm

will generate a strip chart with num_cpus on the x-axis duration plotted on the y-axis and points will be colour-coded by the algorithm run (displayed in the legend). It will also print the filename (resources/demo-plot/plot.pdf), which you can then pipe into | xargs -t open to display the plot. The configuration is saved after each run, so you can regenerate the same plot with python visualize.py DIRECTORY without any options. You could then run:

python visualize.py resources/demo-plot --log-x

which would change the x-axis to have a log scale, and all other attributes would be the same.

For all options, run

python scripts/visualize.py --help

and see the Plotly documentation on the relevant chart to understand what the options mean.

Run Tests

The simplest way to run tests is

make test

It is also possible to run a specific test file (in the ./test directory). To do this, run

make test_name

where test_name is the filename of the test, excluding the extension. For example, to test the random library, run

make test_random

Utils Overview

Block List

A container that is similar to a linked list, containing wide nodes that can store multiple values. When each node has a size of 1, it is identical to a linked list. The wider nodes allow cache-friendly iteration, without the reallocation problems of std::vector.

Cache Utils

Read cache information about the current system (lines, associativity, size) and calculate collision probabilities for different numbers of items.

Compiler

A define'd constant containing a string with the compiler name and version.

CPU Info

A std::string containing information about the current CPU.

Cyclic Queue

Fixed-size cyclic queue implementation.

Generator

An interface for a function that can be repeatedly called and output different values. It also provides implementations of a generator:

• $f^i(x) = i$
• $i\cdot f_M^i(x) \equiv 1 \mod M$

Lock

Lock (mutex) interface with implementations and a multiple-readers single-writer lock. The implementations are:

• EntryLock uses an entry array to determine which threads are contending for the lock.
• MutexLock, which wraps the std::mutex.
• ExchangeLock uses an atomic to determine the holder.

Math Utils

Library containing implementations for:

• $x!$
• $m\lfloor \frac n m \rfloor$ (rounding down)
• $m\lceil \frac n m \rceil$ (rounding up)

Matrix

Variable-size matrix with cache-friendly storage and transposition.

Generator

An interface for a monoid with an identity, composition and an aggregate function. It also provides implementations of the monoids:

• $a \cdot b = max(a,b)$
• $a \cdot b = a + b$
• $a \cdot_M b = ab \mod M$
• $a \cdot b = \underline a \underline b$ (where $\underline a$ and $\underline b$ are matrices)

Random

Seeded random number generation library with the following functions:

• random value $\in {\text{true}, \text{false}}$
• random integer $\in [a, b)$
• random float $\in [0, 1]$
• random value sampled from $\mathcal N(0, 1)$
• random vector in $Ber(p)^n$
• random list of length $N$ with $m$ ones and $N-m$ zeros
• shuffle
• random permutation

Thread Manager

Utility for managing interface with OS threading at setup and tear-down.

Time

Timing a program and useful type aliases.

Types

Utility functions for common type operations.