P systems simulations on massively parallel architectures

Abstract

Membrane Computing is an emergent research area studying the behaviour of living cells to de ne bio-inspired computing devices, also called P systems. Such devices provide polynomial time solutions to NP-complete problems by trading time for space. The e cient simulation of P systems poses challenges in three di erent aspects: an intrinsic massively parallelism of P systems, an exponential computational workspace, and a non-intensive oating point nature. In this paper, we analyze the simulation of a family of recognizer P systems with active membranes that solves the Satis ability (SAT) problem in linear time on three di erent architectures: a shared memory system, a distributed memory system, and a set of Graphics Processing Units (GPUs). For an e cient handling of the exponential workspace created by the P systems computation, we enable di erent data policies on those architectures to increase memory bandwidth and exploit data locality through tiling. Parallelism inherent to the target P system is also managed on each architecture to demonstrate that GPUs o er a valid alternative for high-performance computing at a considerably lower cost: Considering the largest problem size we were able to run on the three parallel platforms involving four processors, execution times were 20049.70 ms. using OpenMP on the shared memory multiprocessor, 4954.03 ms. using MPI on the distributed memory multiprocessor and 565.56 ms. using CUDA in our four GPUs, which results in speed factors of 35.44x and 8.75x, respectively.