Enhancing the simulation of P systems for the SAT problem on GPUs

Abstract

GPUs constitute nowadays a solid alternative for high performance computing, and the advent of CUDA/OpenCL allow programmers a friendly model to accelerate a broad range of applications. The way GPUs exploit parallelism differ from multi-core CPUs, which raises new challenges to take advantage of its tremendous computing power. In this respect, P systems or Membrane Systems provide a high-level computational modeling framework that combines the structure and dynamic aspects of biological systems while being inherently parallel and nondeterministic. In this work, we implement on GPUs the simulation for a solution provided by Membrane Computing to solve the Satisfiability (SAT) problem. The overall speed up reaches 100x versus a sequential CPU, with an additional 16x due to CUDA optimizations. A promising scalability is also proven on more sophisticated GPU clusters and/or demanding problem sizes.