I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
A GPU-based MPG solver


The GPUMPG package contains a GPU-based implementations of several algorithms for solving mean-payoff games.

To use the tool, you need the corresponding OpenCL drivers for your device:

The tool can be invoked by executing mpgsolver FILE, with FILE being a mean-payoff game. Several options can be specified, list them by executing mpgsolver --help. The benchmark results can be re-evaluated by running the Bash script bench/run_benchmarks.sh, with the options in bench/config adjusted to your system.

Source code, benchmarks and results

Compiling instructions

You need, in addition to one of the OpenCL toolkits given above:

  • A C++ compiler. Compilation was tested with g++ 6.1 and the Visual Studio 2015 compiler (msvc-14.0)
  • CMake
  • Boost in the version 1.61 or higher. Extract boost to some location and set the environment variable BOOST_ROOT to that location. You also need to build the static boost libraries with the following commands in the boost folder (adjust toolset if you use another compiler):
    • .\boostrap
    • .\b2 -j8 variant=release toolset=msvc-14.0 address-model=64 link=static threading=multi

Then the build script build_windows.bat builds the project on Windows using Visual Studio 2015 in a 64-bit build. Other builds can be specified by editing the file or invoking CMake by hand.