Abstract
Membrane Computing is a discipline aiming to abstract formal computing 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 massively 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 Satisfiability problem in linear time
on different instances of Graphics Processing 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 dynamic queues. Parallelism inherent to the target P system is also managed to demonstrate that GPUs offer a valid
alternative for high-performance computing 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.
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 massively 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 Satisfiability problem in linear time
on different instances of Graphics Processing 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 dynamic queues. Parallelism inherent to the target P system is also managed to demonstrate that GPUs offer a valid
alternative for high-performance computing 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.
- Content Type Journal Article
- Category Focus
- Pages 1-16
- DOI 10.1007/s00500-011-0716-1
- Authors
- José M. Cecilia, Computer Engineering and Technology Department, University of Murcia, 30100 Murcia, Spain
- José M. García, Computer Engineering and Technology Department, University of Murcia, 30100 Murcia, Spain
- Ginés D. Guerrero, Computer Engineering and Technology Department, University of Murcia, 30100 Murcia, Spain
- Miguel A. Martínez-del-Amor, Computer Science and Artificial Intelligence Department, University of Seville, 41012 Seville, Spain
- Mario J. Pérez-Jiménez, Computer Science and Artificial Intelligence Department, University of Seville, 41012 Seville, Spain
- Manuel Ujaldón, Computer Architecture Department, University of Malaga, 29071 Malaga, Spain
- Journal Soft Computing – A Fusion of Foundations, Methodologies and Applications
- Online ISSN 1433-7479
- Print ISSN 1432-7643