Presentation
P systems simulations on massively parallel architectures
Author/s | 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 Ujaldón, Manuel |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Publication Date | 2010 |
Deposit Date | 2018-02-06 |
Published in |
|
ISBN/ISSN | 978-84-693-6141-2 |
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 ... 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. |
Project ID. | 00001/CS/2007
TIN2009–13192 CSD2006- 00046 P06-TIC-02109 P08–TIC-04200 |
Citation | 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. (2010). P systems simulations on massively parallel architectures. En WPABA 2010: Third International Workshop on Parallel Architectures and Bioinspired Algorithms (17-26), Vienna, Austria: Universidad Complutense de Madrid. |
Files | Size | Format | View | Description |
---|---|---|---|---|
f8989dbc50b9ed3047da2267d3215d ... | 643.8Kb | [PDF] | View/ | |