Playing Parity Games on the Sony PlayStation 3
Parity games are a class of games played by two players on labelled graphs. They have important connections to logics, and also interesting complexity properties: it is strongly suspected that the decision problem for parity games is in P, however, it is only known that it is in the intersection of NP and co-NP.
The Sony PlayStation 3 contains one of the most advanced processors, IBM's "Cell", consisting of a PowerPC and eight other processors called Synergistic Processing Elements (SPEs). Development methodologies for efficient algorithms on the Cell architecture are however still in their infancy.
The aim of this project is to gain experience in the development of parity game algorithms for the Cell, and to report on the idiosyncrasies of the architecture. A PlayStation 3 will be available for experimentation.
Tasks
- Optimize a version of a multi-core parity game algorithm called "Small Progress Measures" which is poised for running on the Cell architecture.
Requirements
- Solid knowledge of C/C++, cross-compilation, etc.
Literature
- Hartmut Klauck. Algorithms for Parity Games, LNCS 2500, 2002.
- Freark van der Berg. Solving Parity Games on the Sony PlayStation 3, 13th TSC on IT, 2010.
- Jorne Kandziora. Playing Parity Games on the Sony PlayStation 3, 10th TSC on IT, 2009.
Notes
The IBM Cell Software Development Kit for Linux can be obtained from <http://www.ibm.com/developerworks/power/cell/downloads.html>, including a Cell simulator (in "Extras").
However, the installation is not a push-button process and the development process is set up for cross-compilation. If you are unable to get to the point of cross-compiling the example programs and running them in the simulator, this project is going to be tough.