Handling Non-determinism in Spiking Neural P Systems : Algorithms and Simulations

• Autorzy: Carandang Jym Paul , Cabarle Francis George C. , Adorna Henry Natividad , Hernandez Nestine Hope S. , Martínez-del-Amor Miguel Ángel

Identyfikatory

DOI

10.3233/FI-2019-1759

• Języki publikacji: EN

Abstrakty

EN

Spiking Neural P system is a computing model inspired on how the neurons in a living being are interconnected and exchange information. As a model in embrane computing, it is a non-deterministic and massively-parallel system. The latter makes GPU a good candidate for accelerating the simulation of these models. A matrix representation for systems with and without delay have been previously designed, and algorithms for simulating them with deterministic systems was also developed. So far, non-determinism has been problematic for the design of parallel simulators. In this work, an algorithm for simulating non-deterministic spiking neural P system with delays is presented. In order to study how the simulations get accelerated on a GPU, this algorithm was implemented in CUDA and used to simulate non-uniform and uniform solutions to the Subset Sum problem as a case study. The analysis is completed with a comparison of time and space resources in the GPU of such simulations.

Słowa kluczowe

EN

CUDA; GPU; matrix representation; membrane computing; spiking neural P systems; subset sum

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 164, nr 2-3
• Strony: 139--155
• Opis fizyczny: Bibliogr. 32 poz., rys., tab., wykr.

Twórcy

autor

Carandang Jym Paul

• Algorithms and Complexity, Department of Computer Science, University of the Philippines Diliman, Philippines

autor

Cabarle Francis George C.

• Algorithms and Complexity, Department of Computer Science, University of the Philippines Diliman, Philippines

autor

Adorna Henry Natividad

• Algorithms and Complexity, Department of Computer Science, University of the Philippines Diliman, Philippines

autor

Hernandez Nestine Hope S.

• Algorithms and Complexity, Department of Computer Science, University of the Philippines Diliman, Philippines

autor

Martínez-del-Amor Miguel Ángel

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Spain

Bibliografia

• [1] Păun G. Membrane Computing: An Introduction. Springer Berlin Heidelberg; 2002. doi:10.1007/978-3-642-56196-2.
• [2] Ionescu M, Păun G, Yokomori T. Spiking Neural P Systems. Fundamenta Informaticae. 2006;71(2-3):279-308.
• [3] Ibarra OH, Woodworth S. Characterizing regular languages by spiking neural P systems. International Journal of Foundations of Computer Science. 2007;18(6):1247-1256. URL https://doi.org/10.1142/S0129054107005297.
• [4] Ibarra OH, Păun A, Rodrguez-Patón A. Sequential SNP systems based on min/max spike number. Theoretical Computer Science. 2009;410(30-32):2982-2991. URL https://doi.org/10.1016/j.tcs.2009.03.004.
• [5] Cavaliere M, Ibarra OH, Pun G, Egecioglu O, Ionescu M, Woodworth S. Asynchronous spiking neural P systems. Theoretical Computer Science. 2009;410(24-25):2352-2364. URL https://doi.org/10.1016/j.tcs.2009.02.031.
• [6] Leporati A, Zandron C, Ferretti C, Mauri G. Solving numerical NP-complete problems with spiking neural P systems. Lecture Notes in Computer Science. vol 4860 of LNCS, 2007 pp. 336-352. doi:10.1007/978-3-540-77312-2_21.
• [7] Leporati A, Mauri G, Zandron C, Păun G, Pérez-Jiménez MJ. Uniform solutions to SAT and Subset Sum by spiking neural P systems. Natural Computing. 2008 Jul; 8(4):681. doi:10.1007/s11047-008-9091-y.
• [8] Ishdorj TO, Leporati A, Pan L, Zeng X, Zhang X. Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources. Theoretical Computer Science. 2010;411(25):2345-2358. URL https://doi.org/10.1016/j.tcs.2010.01.019.
• [9] Pan L, Păun Gh. Spiking Neural P systems with Anti-Spikes. Int. J. Comput, Commun Control. 2009;4(3):273-282. URL https://doi.org/10.15837/ijccc.2009.3.2435.
• [10] Pan L, Păun G, Pérez-Jiménez MJ. Spiking neural P systems with neuron division and budding. Science China Info Sciences. 2011;54(8):1596-1607. doi:10.1007/s11432-011-4303-y.
• [11] Pan L, Wang J, Hoogeboom HJ. Spiking Neural P Systems with Astrocytes. Neural Computation. 2012;24(3):805-825. URL https://doi.org/10.1162/NECO_a_00238.
• [12] Song T, Pan L, Păun G. Spiking neural P systems with rules on synapses. Theoretical Computer Science. 2014;529:82-95. URL https://doi.org/10.1016/j.tcs.2014.01.001.
• [13] Cabarle FGC, Adorna HN, Pérez-Jiménez MJ, Song T. Spiking neural P systems with structural plasticity. Neural Computing and Applications. 2015;26(8):1905-1917. doi:10.1007/s00521-015-1857-4.
• [14] Song T, Pan L. Spiking neural P systems with request rules. Neurocomputing. 2016;193:193-200. URL https://doi.org/10.1016/j.neucom.2016.02.023.
• [15] Cabarle FGC, Adorna HN, Jiang M, Zeng X. Spiking neural P systems with scheduled synapses. IEEE Trans Nanobiosci. 2017;16(8):792-801. doi:10.1109/TNB.2017.2762580.
• [16] Wu T, Păun A, Zhang Z, Pan L. Spiking neural P systems with polarizations. IEEE Trans Neural Net Learning Sys. 2017.
• [17] Cabarle FGC, Adorna HN, Martínez-del-Amor MÁ , Pérez-Jiménez MJ. Improving GPU Simulations of Spiking Neural P Systems. Romanian Journal of Information Science and Technology. 2012;15(1):5-20. URL http://www.imt.ro/romjist/Volum15/Number15_1/cuprins15_1.htm.
• [18] Carandang JPA, Villaflores JMB, Cabarle FGC, Adorna HN, Martínez-del-Amor MÁ. CuSNP: Spiking Neural P Systems Simulators in CUDA. Romanian Journal of Information Science and Technology. 2017;20(1):57-70. URL http://2016.asiancmc.org/.
• [19] Carandang JPA, Villaflores JMB, Cabarle FGC, Adorna H, Martínez-del-Amor MÁ. CuSNP: Spiking Neural P Systems Simulators in CUDA. 5th Asian Conference on Membrane Computing. 2016.
• [20] Carandang JPA, Villaflores JMB, Cabarle FGC, Adorna H, Martínez-del-Amor MÁ. Improving simulations of Spiking Neural P Systems in NVIDIA CUDA GPUs: CuSNP. In: 14th Brainstorming Week on Membrane Computing. Seville, Spain: Fénix Editora; 2016. pp. 135-150. URL http://www.gcn.us.es/14bwmc_proceedings.
• [21] Carandang JPA, Villaflores JMB, Cabarle FGC, Adorna H, Martínez-del-Amor MÁ. CuSNP version 06.06.16; 2016. http://aclab.dcs.upd.edu.ph/productions/software/cusnp_v060616.
• [22] Nguyen V, Kearney D, Gioiosa G. An Algorithm for Non-deterministic Object Distribution in P Systems and Its Implementation in Hardware. In: Corne DW, Frisco P, Păun G, Rozenberg G, Salomaa A, editors. Membrane Computing. Berlin, Heidelberg: Springer Berlin Heidelberg; 2009. pp. 325-354. doi:10.1007/978-3-540-95885-7_24.
• [23] Martínez-Del-Amor, Miguel Ángel and Macías-Ramos, Luis Felipe and Valencia-Cabrera, Luis and Pérez-Jiménez, Mario J. Parallel Simulation of PDP Systems: Updates And Roadmaps. Natural Computing 2016; 15(4):565-573. doi:10.1007/s11047-016-9566-1.
• [24] Păun G. Membrane Computing: An Introduction. Springer-Verlag Berlin Heidelberg: Springer Berlin Heidelberg; 2002. doi:10.1007/978-3-642-56196-2.
• [25] Păun G, Rozenberg G, Salomaa A, editors. The Oxford Handbook of Membrane Computing. Oxford Univeristy Press; 2010. ISBN:0199556679, 9780199556670.
• [26] Ionescu M, Păun G, Yokomori T. Spiking Neural P Systems. Fundam Inf. 2006;71(2-3):279-308.
• [27] NVIDIA. CUDA C Programming Guide; 2015. Accessed: 2015-11-19. http://docs.nvidia.com/cuda/cuda-c-programming-guide.
• [28] Kirk DB, Hwu WmW. Programming Massively Parallel Processors: A Hands-on Approach. 2nd ed. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.; 2013. ISBN:9780123914187, 9780124159921.
• [29] Zeng X, Adorna H, Martínez-del-Amor MÁ, Pan L, Pérez-Jiménez MJ. In: Gheorghe M, Hinze T, Păun G, Rozenberg G, Salomaa A, editors. Matrix Representation of Spiking Neural P Systems. Berlin, Heidelberg: Springer Berlin Heidelberg; 2011. pp. 377-391. doi:10.1007/978-3-642-18123-8_29.
• [30] Cecilia JM, García JM, Guerrero GD, Martínez-del-Amor MÁ, Pérez-Hurtado I, Pérez-Jiménez MJ. Simulation of P systems with active membranes on CUDA. Briefings in Bioinformatics. 2010;11(3):313-322. doi:10.1093/bib/bbp064.
• [31] Martínez-del-Amor MÁ, García-Quismondo M, Macías-Ramos LF, Valencia-Cabrera L, Riscos-Núñez A, Pérez-Jiménez MJ. Simulating P Systems on GPU Devices: A Survey. Fundamenta Informaticae. 2015;136:269-284. doi:10.3233/FI-2015-1157.
• [32] Martínez-del-Amor MÁ, Orellana-Martín D, Cabarle FGC, Pérez-Jiménez MJ, Adorna HN. Sparse-matrix Representation of Spiking Neural P Systems for GPU. In: Proc. of 15th Brainstorming Week on Membrane Computing. Seville, Spain: Fénix Editora; 2017. pp. 161-170. URL http://www.gcn.us.es/15bwmc_proceedings.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).