Parallel simulation of a family of tissue-like P systems with cell division solving SAT in linear time (TSPCUDASAT)

---

1. Description

A correlated project to PCUDASAT is TSPCUDASAT. Its objective is to simulate a family of tissue-like P systems with cell division solving SAT in linear time. The simulation algorithm is based, as in PCUDASAT, in the 5 stages of the computation of the P systems: Generation, Exchange, Synchronization, Check-in and Output.

The CUDA simulator design is similar to the one used in PCUDASAT. Each thread block is assigned to each cell labeled by 2. However, the number of objects to be placed inside each cell in the memory representation is increased. The simulator requires to store $2n+4+|cod(\phi)|$ objects per cell, being $n$ the number of variables in the CNF formula, and $|cod(\phi)|$ the size of the input multiset. That is, it requires $2n+4$ more objects per cell than the PCUDASAT simulators, but it does not need to store charges. Threads are used differently in each stage, maximizing their usage in each case.

Experiments show that the CUDA simulator outperforms the sequential one by 10x (for 256 objects and 4 M cells). It can be seen that solving the same problem (SAT) under different P system models leads to different speedups using CUDA. Indeed, we show that the usage of charges can help to save space devoted to objects.

---

2. Installation and Usage

2.1. Installation:

1. Install the CUDA SDK version 4.X.

2. Install the counterslib: extract the file counterslib.tar.gz inside the common folder of the CUDA SDK.

3. Copy the folder into the source folder of the CUDA SDK, and type "make".

2.2. Usage:

Type ./tsp -h to list the different options.

• A sequential simulation: ./tsp -m 2 -f file.cnf
• A parallel simulation on the GPU: ./tsp -m 4 -f file.cnf

---

3. Publications

3.1 Journals

• M.A. Martínez-del-Amor, J. Pérez-Carrasco, M.J. Pérez-Jiménez. Characterizing the parallel simulation of P systems on the GPU. International Journal of Unconventional Computing, 9, 5-6 (2013), 405-424.

3.2 Conference paper

• M.A. Martínez-del-Amor, J. Pérez-Carrasco, M.J. Pérez-Jiménez. Simulating a Family of Tissue P Systems Solving SAT on the GPU, 11th Brainstorming Week on Membrane Computing, BWMC13, Seville, Spain, February 2013, Proceedings (2013), pp. 201-220.

3.3 Ph.D. Thesis

• Miguel Á. Martínez-del-Amor. Accelerating Membrane Systems Simulators using High Performance Computing with GPU. May 2013, University of Seville. Advised by Mario J. Pérez-Jiménez and Ignacio Pérez-Hurtado.

3.4 Master Thesis

• Jesús Pérez-Carrasco. Aceleración de simulaciones de sistemas celulares en soluciones del problema SAT usando GPUs (Acceleration of cellular systems simulations on solutions to SAT problem using GPUs), June 2012, Dpt. Comput. Sci. & A.I. (University of Seville).

---

4. Downloads

Required Counterslib library

Read the howto.pdf (extract from Miguel A. Martínez-del-Amor's thesis) for futher information about the simulators. It is in the root folder of files of PMCGPU.

---

5. How to acknowledge

If you intend to create a branch of TSPCUDASAT, or use its produced results, please consider citing the following publication:

M.A. Martínez-del-Amor, J. Pérez-Carrasco, M.J. Pérez-Jiménez. Characterizing the parallel simulation of P systems on the GPU. International Journal of Unconventional Computing, 9, 5-6 (2013), 405-424.

---

6. Funding

This work has been supported by the "Proyecto de Excelencia con Investigador de Reconocida Valía" of the "Junta de Andalucía" under grant P08-TIC04200, and by the project TIN2009-13192 of the "Ministerio de Educación y Ciencia" of Spain, both co-financed by FEDER funds.