Ravie Chandren Muniyandi, Ali Maroosi. Enhancing the Simulation of Membrane System on the GPU for the N-Queens Problem[J]. Chinese Journal of Electronics, 2015, 24(4): 740-743. doi: 10.1049/cje.2015.10.012
Citation: Ravie Chandren Muniyandi, Ali Maroosi. Enhancing the Simulation of Membrane System on the GPU for the N-Queens Problem[J]. Chinese Journal of Electronics, 2015, 24(4): 740-743. doi: 10.1049/cje.2015.10.012

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

doi: 10.1049/cje.2015.10.012
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
  • 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.
  • loading
  • 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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (212) PDF downloads(619) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return