This directory contains all the experiments relevant to the thesis:

Algorithmic Skeletons for Exact Combinatorial Search at Scale, B
Archibald.

The experiments rely on a custom job launcher to get around limitations
of the test cluster. The job launcher assumes full single user access to
all localities (via ssh).

Building YewPar
===============

A release version of YewPar, used in the thesis, can be found at: http://dx.doi.org/10.5281/zenodo.1316476

The correct dependencies of YewPar can be build using the following
environment script within the main YewPar directory.

``` {.nix}
with import (fetchTarball "https://github.com/NixOS/nixpkgs/archive/78a17f5765f24ae24ee87224dad16862451295d2.tar.gz") {};
let
stdenv = overrideCC pkgs.stdenv pkgs.gcc7;
boost = boost164;
newHPX = stdenv.mkDerivation rec {
  name = "hpx-new";
  src = fetchFromGitHub {
    owner = "STEllAR-GROUP";
    repo = "hpx";
    rev = "51d3d007e5e7d1bad5eccd587569cc267b061246";
    sha256 = "1bydsxsblgrqykw4rw50qmlbqn7q4msirfbcw3y9dv631svw34k5";
  };

  buildInputs = [ boost mpich2 hwloc gperftools];
  nativeBuildInputs = [ cmake pkgconfig python ];

  cmakeFlags = [
    "-DHPX_WITH_PARCELPORT_MPI=ON"
    "-DHPX_WITH_EXAMPLES=OFF"
    "-DHPX_WITH_TESTS=OFF"
    "-DMPI_LIBRARY=${mpich2}/lib/libmpi.so"
  ];

  enableParallelBuilding = true;

  meta = {
    description = "C++ standard library for concurrency and parallelism";
    homepage = https://github.com/STEllAR-GROUP/hpx;
    license = stdenv.lib.licenses.boost;
    platforms = [ "x86_64-linux" ]; # stdenv.lib.platforms.linux;
  };
};
in
stdenv.mkDerivation rec {
  name = "YewPar";
  version = "0.0.1";

  buildInputs = [ boost mpich2 newHPX gperftools hwloc ];
  nativeBuildInputs = [ cmake ];

  src =
    let
      inDir = path : dir : stdenv.lib.hasPrefix (toString dir) (toString path);
      filter = path : type : baseNameOf path == "CMakeLists.txt"
        || inDir path ./apps
        || inDir path ./lib;
    in builtins.filterSource filter ./.;

  enableParallelBuilding = true;
}
```

Commands to build YewPar for the experiments are as follows:

``` {.bash}
git clone git@github.com:BlairArchibald/YewPar.git
cp experiment-env.nix YewPar # Assuming the script above is called experiment-env.nix
cd YewPar
nix-shell experiment-env.nix # Possibly with -jN to get parallel builds if required
# Now in nix-shell
mkdir build
cd build
cmake -DCMAKE_INSTALL_PREFIX=$(pwd)/install -DCMAKE_BUILD_TYPE=Release -DYEWPAR_BUILD_BNB_APPS_MAXCLIQUE_NWORDS=14 -DYEWPAR_BUILD_BNB_APPS_KNAPSACK_NITEMS=220 -DYEWPAR_BUILD_APPS_SIP_NWORDS=128 ../
make install
# If successful we also build another version of maxclique for larget graphs. both maxclique-14 and maxclique-32 will be in $(pwd)/install/bin
cmake -DYEWPAR_BUILD_BNB_APPS_MAXCLIQUE_NWORDS=32 ../
make install
```

The job launcher can be downloaded automatically via stack, by having
the following `.yaml` file in the run directory of a job launch script.

``` {.yaml}
resolver: lts-9.13
packages:
  - location:
      git: git@github.com:BlairArchibald/HSLauncher.git
      commit: eca5f21b1abcc660315d5fd5cba1ae805a160e0b
```

Experiments
===========

Sub-directories each contain different experiments including run scripts
(usually in \<experimentdir\>/scripts/run/). If you only want to
recreate the data/plots of the thesis (without gathering new data) then
you can simply call \`make\` in the root experiment directory.

To run the experiments you will require a working Haskell implementation, and a
python + pandas installation for running the analyses.

Most of the instances (except for H49) can be found in the instances directory.

-   [Sequential Baselines](sequential-baselines/): Collects samples runs
    using the Sequential skeleton for all benchmark instances (except
    finite-geometry).
-   [CPP-comparison](maxclique-cpp-comparison/): Compares YewPar to a
    hand-written C++ Maximum Clique implementation from McCreesh.
-   [Incumbent Updates](incumbent-updates/): Records how often the
    incumbent is updated for a selection of maximum clique instances.
-   [Workpool Choice](workpool-choice/): Compares Depth-pool to Deque
    based scheduling.
-   [Depth-Bounded Depth Sweep](depth-tuning/): Investigates the
    performance of Depth-Bounded at different d~cutoff~ settings.
    Including work-stealing performance.
-   [Stack-Stealing](stack-stealing/): Investigates the performance of
    Stack-Stealing including chunking and work-stealing performance.
-   [Budget](budget-tuning/): Investigates the performance of Budget
    including work-stealing performance.
-   [Skeleton Comparison](skeleton-comparisons/): Compares the
    performance across the skeleton implementations.
-   [Scaling](larger-instances/): Investigates the skeletons at scale
    (i.e on up to 255 workers).
-   [H49](finite-geometry/H49/Makefile): Looks at the larger H(4,9)
    finite geometry instance at 255 workers.
-   [Ordered](ordered-skeleton/): Investigates the Ordered skeleton for
    both scale and repeatability