Enhancing the Simulation of Membrane System on the GPU for the <em>N</em>-Queens Problem

Ravie Chandren Muniyandi; Ali Maroosi

doi:10.1049/cje.2015.10.012

Volume 24 Issue 4

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2015 > 24(4): 740-743

Ravie Chandren Muniyandi and Ali Maroosi, “Enhancing the Simulation of Membrane System on the GPU for the N-Queens Problem,” Chinese Journal of Electronics, vol. 24, no. 4, pp. 740-743, 2015, doi: 10.1049/cje.2015.10.012

Citation:

Ravie Chandren Muniyandi and Ali Maroosi, “Enhancing the Simulation of Membrane System on the GPU for the N-Queens Problem,” Chinese Journal of Electronics, vol. 24, no. 4, pp. 740-743, 2015, doi: 10.1049/cje.2015.10.012

Citation:

PDF( 497 KB)

Enhancing the Simulation of Membrane System on the GPU for the N-Queens Problem

doi: 10.1049/cje.2015.10.012

Research Center for Software Technology and Management (SOFTAM), Faculty of Information Science and Technology (FTSM), National University of Malaysia (UKM), Bangi 43600, Malaysiam

Funds: This work is supported by the Science Fund of the MOSTI-Ministry of Science, Technology and Innovation, Malaysia (No.01-01-02-SF1104).

Received Date: 2014-03-03
Rev Recd Date: 2014-10-01
Publish Date: 2015-10-10

Abstract

Abstract

Previous approaches using active membrane systems to solve the N-queens problem defined many membranes with just one rule inside them. This resulted in many communication rules utilised to communicate between membranes, which made communications between the cores and the threads a very time-consuming process. The proposed approach reduces unnecessary membranes and communication rules by defining two membranes with many objects and rules inside each membrane. With this structure, objects and rules can evolve concurrently in parallel, which makes the model suitable for implementation on a Graphics processing unit (GPU). The speedup using a GPU with global memory for N=10 is 10.6 times, but using tiling and shared memory, it is 33 times.
- Membrane computing,
- Graphics processing unit (GPU),
- N-queens problem,
- Parallel processing

FullText(HTML)

References(19)

References

G. Paun, "A quick introduction to membrane computing", Journal of Logic and Algebraic Programming, Vol.79, pp.291- 294, 2010.

G. Paun, "Tracing some open problems in membrane computing", Romanian Journal of Information Science and Technology, Vol.10, pp.303-314, 2007.

R. Muniyandi and M.Z. Abdullah, "Modeling hormone-induced calcium oscillations in liver cell with membrane computing", Romanian Journal of Information Science and Technology, Vol.15, pp.63-76, 2012.

R. Muniyandi, M.Z. Abdullah and J.W. Sanders, "Converting differential-equation models of biological systems to membrane computing", BioSystems, Vol.114, pp.219-226, 2013.

G. Paun, "Computing with membranes", Journal of Computer and System Sciences, Vol.61, No.1, pp.108-143, 2000.

L. Pan and M.J. Perez-Jimenez, "Computational complexity of tissue-like P systems", Journal of Complexity, Vol.26, No.3, pp.296-315, 2010.

L. Pan, G. Paun and M.J. Perez-Jimenez, "Spiking neural P systems with neuron division and budding", Science China Information Sciences, Vol.54, No.8, pp.1596-1607, 2011.

T.O. Ishdorj, A. Leporati, L. Pan, X. Zeng and X. Zhang, "Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources", Theoretical Computer Science, Vol.411, pp.2345-2358, 2010.

A. Maroosi and R.C. Muniyandi, "Membrane computing inspired genetic algorithm on multi-core processors", Journal of Computer Science, Vol.9, pp.264-270, 2013.

M. Ali and R.C. Muniyandi, "A hybrid membrane computing and honey bee mating algorithm as an intelligent algorithm for channel assignment problem", Eighth International Conference on Bio-Inspired Computing: Theories and Applications, Springer Berlin, Heidelberg, pp.1021-1028, 2013.

J. Bell and B. Stevens, "A survey of known results and research areas for N-queens", Journal of Discrete Mathematics, Vol.309, pp.131, 2009.

M.A. Gutierrez-Naranjo, M.A. Martinez-del-Amor, I. Perez- Hurtado and M.J. Perez-Jimenez, "Solving the N-queens puzzle with P systems", Seventh Brainstorming Week on Membrane Computing, Fenix Editora, Sevilla, Spain, Vol.1, pp.199-210, 2009.

M.A. Gutierrez-Naranjo and M.J. Perez-Jimenez, "Depth-first search with P systems", Lecture Notes in Computer Science, Vol.6501, pp.257-264, 2010.

M.A. Gutierrez-Naranjo and M.J. Perez-Jimenez, "Local search with P systems: A case study", International Journal of Natural Computing Research, Vol.2, pp.47-55, 2011.

G. Paun, Membrane Computing: An Introduction, Springer, Berlin, 2002.

S. Prestwich, "Combining the scalability of local search with the pruning techniques of systematic search", Annals of Operations Research, Vol.115, pp.51-72, 2002.

A. Maroosi, R.C. Muniyandi, E. Sundararajan and A.M. Zin, "Parallel and distributed computing models on a graphics processing unit to accelerate simulation of membrane systems", Simulation Modelling Practice and Theory, Vol.47, pp.60-78, 2014.

A. Maroosi, R.C. Muniyandi, "Enhancement of membrane computing model implementation on GPU by introducing matrix representation for balancing occupancy and reducing inter-block communications", Journal of Computational Science, Vol.5, No.6, pp.861-871, 2014.

NVIDIA Corporation, "NVIDIA CUDA C programming guide", Version 4.2, available at http://docs.nvidia.com/cuda/index.html, 2012.

Relative Articles

Supplements(0)

Cited By

Proportional views