Simulation of Computing P Systems: A GPU Design for the Factorization Problem

Simulation of Computing P Systems: A GPU Design for the Factorization Problem Miguel Á. Martínez-del-Amor, David Orellana-Martín Ignacio Pérez-Hurtado, Luis Valencia-Cabrera Agustín Riscos-Núñez, Mario J. Pérez-Jiménez Research Group on Natural Computing Dept. Computer Science and Artificial Intelligence Universidad de Sevilla CMC19, 4-7 September 2018, Dresden (Germany) M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 1/37 Contents 1GPU computing fundamentals 2GPU simulators for P systems Structure of a GPU simulator State of the art Other P system models 3Concepts for specific simulators 4Future research lines M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 2/37 GPU computing fundamentals Outline 1GPU computing fundamentals 2GPU simulators for P systems Structure of a GPU simulator State of the art Other P system models 3Concepts for specific simulators 4Future research lines M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 3/37 GPU computing fundamentals GPU computing Graphics Processor Unit (GPU) Data-parallel computing model: SPMD programming model (Same Program for Multiple Data) Shared memory system New programming languages: CUDA, OpenCL, DirectCompute A GPU features thousand of cores M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 4/37 GPU computing fundamentals NVIDIA’s technology CUDA programming model1 Heterogeneous model: CPU (host) + GPU (device). All threads execute the same code (kernel) in parallel. Three-level hierarchy of threads (grid, blocks, threads). Memory hierarchy (global, shared within block). 1W.-M. Hwu, D. Kirk. Programming massively parallel processors, Morgan Kaufmann, 2010. M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 5/37 GPU computing fundamentals Why is the GPU interesting for simulating P systems? Desired properties: High level of parallelism (up to 4000 cores) Shared memory system (easily synchronized) Scalability and portability Known languages: C/C++, Python, Fortran... Cheap technology everywhere (cost and maintenance) Undesired properties: Best performance requires lot of research. Programming model imposes many restrictions M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 6/37 GPU simulators for P systems Structure of a GPU simulator Outline 1GPU computing fundamentals 2GPU simulators for P systems Structure of a GPU simulator State of the art Other P system models 3Concepts for specific simulators 4Future research lines M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 7/37 GPU simulators for P systems Structure of a GPU simulator GPU simulator workflow - Initialization (I) CPU (serial code) GPU (serial code) Read P system information: + P system model description + Initial configuration Allocate memory in GPU GPU memory P system info (rules, alphabet) P system configuration (incl. all possible membranes to be generated during computation) Copy P system information to GPU Copy P system initial config to GPU Auxiliary (rule selection) M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 8/37 GPU simulators for P systems Structure of a GPU simulator GPU simulator workflow - Simulation - Selection (II) CPU (serial code) GPU (serial code) Read P system information: + P system model description + Initial configuration Allocate memory in GPU Copy P system information to GPU Copy P system initial config to GPU Call to Selection Kernel(s) GPU grid GPU memory P system info P system configuration Auxiliary M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 9/37 GPU simulators for P systems State of the art Simulating models (“generic” approach) Performance analysis Two benchmarks (on a C1060 with 240 cores): A. Asimple test P system2 Max speedup: 5.8x B. An efficient solution to SAT Max speedup: 1.5x (n=18, 218 membranes) Density of objects per membrane: Reality WorstCase =#Objects AlphabetSize Test A: 100% Test B: ∼15% 2One division rule: [d]2→[d]2[d]2, Many evolution rules: [oi→oi]2,0≤i≤N M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 16/37 GPU simulators for P systems State of the art Simulating models (“generic” approach) Performance analysis Two benchmarks (on a C1060 with 240 cores): A. Asimple test P system2 Max speedup: 5.8x B. An efficient solution to SAT Max speedup: 1.5x (n=18, 218 membranes) Density of objects per membrane: Reality WorstCase =#Objects AlphabetSize Test A: 100% Test B: ∼15% 2One division rule: [d]2→[d]2[d]2, Many evolution rules: [oi→oi]2,0≤i≤N M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 16/37 GPU simulators for P systems State of the art Simulating models (“generic” approach) Foreseen performance by Sevilla Carpets: D. Orellana-Martín et al. Sevilla Carpets revisited: Enriching the Membrane Computing toolbox. Fundamenta Informaticae, 134 (2014), 153-166. The flatter the carpet, the higher the parallel degree in the system (and so, in the simulation). M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 17/37 GPU simulators for P systems State of the art Simulating models (“specific” approach) Cell-like solution to SAT P systems with active membranes A specific linear time solution to SAT, with exponential workspace Encoding: Objects: literals of the formula and auxiliary (counters, etc.) Membranes: truth assignments A 4-staged solution: 1Generation 2Synchronization 3Check out 4Output M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 18/37 GPU simulators for P systems State of the art Simulating models (“specific” approach) Cell-like solution to SAT - parallel design Membranes to Thread Blocks Objects in initial multiset to Threads:we have constrained the number of threads to the amount of different objects in the initial multiset. M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 19/37 GPU simulators for P systems State of the art Simulating models (“specific” approach) Tissue-like solution to SAT Tissue P systems with cell division Directed graph of cells. No polarization and cooperation (multisets in LHS) Communication (symport/antiport) and division rules. Active environment. A specific linear time solution to SAT, with exponential workspace Encoding: Objects: literals of the formula and auxiliary (counters, etc.) Cell: truth assignment A 5-staged solution: 1Generation 2Exchange 3Synchronization 4Checking 5Output M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 20/37 GPU simulators for P systems State of the art Simulating models (“specific” approach) Tissue-like solution to SAT Tissue P systems with cell division Directed graph of cells. No polarization and cooperation (multisets in LHS) Communication (symport/antiport) and division rules. Active environment. A specific linear time solution to SAT, with exponential workspace Encoding: Objects: literals of the formula and auxiliary (counters, etc.) Cell: truth assignment A 5-staged solution: 1Generation 2Exchange 3Synchronization 4Checking 5Output M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 20/37 GPU simulators for P systems State of the art Simulating models (“specific” approach) Tissue-like solution to SAT - parallel design Cells to Thread Blocks Objects in initial multiset, objects for truth assignation, and auxiliary objects to Threads: selection of rules is not direct given that there is cooperation. M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 21/37 GPU simulators for P systems State of the art Simulating models (“specific” approach) Performance analysis Cell-like approach: Max speedup: 63x (n=21) Tissue-like approach: Max speedup: 10x (n=21) Conclusion: Charges save space, and help to increase object density No-cooperation avoids synchronization issues Shallow P systems (no more than skin and elementary membranes) M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 22/37 GPU simulators for P systems State of the art Simulating models (“specific” approach) Performance analysis Cell-like approach: Max speedup: 63x (n=21) Tissue-like approach: Max speedup: 10x (n=21) Conclusion: Charges save space, and help to increase object density No-cooperation avoids synchronization issues Shallow P systems (no more than skin and elementary membranes) M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 22/37 Concepts for specific simulators Design of specific simulators Considerations: No need to do selection - execution (we know the rules) No need to do per-transition simulation (we can take short paths) No need to store rules in memory (we know the rules!!) Under control:we should be able to know, looking into the simulator, the state of the P system at every transition Common designs: Models are normally designed by staged computations Each one with different behaviour (generation, checking, ...) A kernel per stage M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 29/37 Concepts for specific simulators Design of specific simulators Considerations: No need to do selection - execution (we know the rules) No need to do per-transition simulation (we can take short paths) No need to store rules in memory (we know the rules!!) Under control:we should be able to know, looking into the simulator, the state of the P system at every transition Common designs: Models are normally designed by staged computations Each one with different behaviour (generation, checking, ...) A kernel per stage M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 29/37 Concepts for specific simulators Design of specific simulators Increasing density of objects: from sparse to dense representation a b c d e f o1 o2 o3 o4 o5 o6 o7 o8 a b c d e f oi Initial Multiset Objects acting as counters M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 30/37 Concepts for specific simulators Design of specific simulators Design decisions: Objects acting as counters, variable or in memory? Are we able to set an upper-bound of objects appearing in membranes? Minimal production helps!! Do we know the maximum amount of membranes? A kernel or several kernels per stage? Fusing kernels for simple stages? M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 31/37 Future research lines Outline 1GPU computing fundamentals 2GPU simulators for P systems Structure of a GPU simulator State of the art Other P system models 3Concepts for specific simulators 4Future research lines M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 32/37 Future research lines GPU-oriented P systems MABICAP: Bio-inspired machines over high performance platforms. Seeking P system models well-suited for GPU deployments. Selection of best ingredients, while keeping computing power and expressibility: Charges Minimal production Minimal (almost no-) cooperation Shallow structure (horizontal parallelism) Towards efficient simulation of Spiking Neural P systems (sparse representation) M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 33/37 Future research lines New GPU features Kernel compilation in runtime (customizable to the model) Cooperative Groups (for deeper P systems) Tensor cores (matrix representations for SNP systems) Dynamic Parallelism (to be seen...) Faster memory Cloud M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 34/37 Future research lines Coming Calls BICAS 2019:Biologically Inspired Parallel and Distributed Computing, Algorithms and Solutions Part of HPCS 2019 (a CORE B conference) Dublin (Ireland), July 15 – 19, 2019 Deadline: TBD (around March) Proceedings in IEEE Xplore Special issues in ISI journals (FGCS, CCPE, ...) http://hpcs2019.cisedu.info M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 35/37 Future research lines Coming Calls BWMC 2019:Brainstorming Week on Membrane Computing Sevilla (Spain) Dates: 5-8 February Announcements at RGNC website: http://www.gcn.us.es M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 36/37 Future research lines Thank you for your attention! Vielen Dank für Ihre Beachtung! The authors acknowledge support of the R&D project MABICAP TIN2017-89842-P and REDBIOCOM TIN2015-71562-REDT, funded by the Spanish government and EU FEDER funds. M.Á. Martínez-del-Amor et al. (RGNC) Simulation of Computing P Systems CMC19, Dresden (Germany) 37/37