Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
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/, 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.