The GPU on the simulation of cellular computing models
|Author||Cecilia, José M.
García, José M.
Guerrero, Ginés D.
Martínez del Amor, Miguel Ángel
Pérez Jiménez, Mario de Jesús
|Department||Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial|
|Published in||Soft Computing, 16 (2), 231-246.|
|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 ...
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.
|Cite||Cecilia, J.M., García, J.M., Guerrero, G.D., Martínez del Amor, M.Á., Pérez Jiménez, M.d.J. y Ujaldón, M. (2012). The GPU on the simulation of cellular computing models. Soft Computing, 16 (2), 231-246.|