Research Group on Natural Computing

Membrane Computing is a discipline aiming to abstract formal com-
puting models, called membrane systems or P systems, from the structure and
functioning of the living cells as well as from the cooperation of cells in tissues,
organs, and other higher order structures. This framework provides polynomial
time solutions to NP-complete problems by trading space for time, and whose
efficient simulation poses challenges in three different aspects: an intrinsic mas-
sively parallelism of P systems, an exponential computational workspace, and
a non-intensive floating point nature. In this paper, we analyze the simulation
of a family of recognizer P systems with active membranes that solves the Sat-
isfiability (SAT) problem in linear time on different instances of Graphics Pro-
cessing Units (GPUs). For an efficient handling of the exponential workspace
created by the P systems computation, we enable different data policies to
increase memory bandwidth and exploit data locality through tiling and dy-
namic queues. Parallelism inherent to the target P system is also managed to
demonstrate that GPUs offer a valid alternative for high-performance comput-
ing at a considerably lower cost. Furthermore, scalability is demonstrated on
the way to the largest problem size we were able to run, and considering the
new hardware generation from Nvidia, Fermi, for a total speed-up exceeding
four orders of magnitude when running our simulations on the Tesla S2050
server.