Simulating a Family of Tissue P Systems Solving SAT on the GPU

Simulating a Family of Tissue P Systems Solving SAT on the GPU Miguel A. Mart´ınez-del-Amor, Jes´us P´erez-Carrasco, Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Seville Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: [email protected], [email protected], [email protected] Summary. In order to provide efficient software tools to deal with large membrane systems, high-throughput simulators are required. Parallel computing platforms are good candidates, since they are capable of partially implementing the inherently parallel nature of the model. In this concern, today GPUs (Graphics Processing Unit) are considered as highly parallel processors, and they are being consolidated as accelerators for scientific applications. In fact, previous attempts to design P systems simulators on GPUs have shown that a parallel architecture is better suited in performance than traditional single CPUs. In 2010, a GPU-based simulator was introduced for a family of P systems with active membranes solving SAT in linear time. This is the starting point of this paper, which presents a new GPU simulator for another polynomial-time solution to SAT by means of tissue P systems with cell division, trading space for time. The aim of this simulator is to further study which ingredients of different P systems models are well suited to be managed by the GPU. Keywords: Membrane Computing, tissue P systems, SAT, GPU Computing 1 Introduction Membrane Computing [15] is a recent branch of Natural Computing, which defines massively parallel and non-deterministic computing devices abstracted from living eukaryotic cells. These devices are called membrane systems, or simply, P systems (named after its creator, Gheorghe P˘aun) [12]. Today, researchers have only one method to work with P systems, which is the usage of simulators running on conventional electronic computers. However, these simulators are normally unfit for very large P systems models. The main reason is that they are not throughputoriented, so they consume large amounts of time and memory resources on a computer. Therefore, the necessity of efficient simulators arises [15]. 202 M.A. Mart´ınez-del-Amor, J. P´erez-Carrasco, M.J. P´erez-Jim´enez In the last years, the trend has been oriented to implement P systems parallelism on parallel platforms, such as accelerators (special parallel devices). In fact, the advent of the accelerators in High Performance Computing offers fresh avenues for developing new and efficient simulators [2]. One of the most important accelerators nowadays is the GPU (Graphics Processing Unit). It is the core of graphics cards and, thanks to the fast growth of video and game market, typically contains hundreds of slight processors. Their evolution has also led to a new programming model based on data parallelism. This permits to use GPUs for general purpose applications (GPGPU or GPU computing) [8]. So far, many GPU-based simulators have been developed for several P systems models: active membranes [2], PDP systems [9], Spiking Neural P systems [1], among others. These simulators are flexible for the corresponding P system model, supporting a wide variety of P systems. However, this feature causes a negative effect on performance [10]. An alternative line was initiated in 2010 with the introduction of a specific (ad-hoc) simulator for a P system based efficient solution to SAT by using GPUs [3, 4]. The solution is based on P systems with active membranes, and the simulator achieves speedups of up to 90x, compared to the CPU counterpart. The obtained results lead to a new open question, related with the efficiency of P system simulators: fixed a problem (e.g. SAT), which is the fastest P system based solution simulated on the GPU? In order to answer this question, we first need to analyze which elements of P systems are better suited to be handled by the GPU. In fact, this can help to define new methods to design more efficient simulators. In this paper, we consider another efficient solution to SAT based on tissue P systems with cell division. A simulator based on GPUs for this solution is presented. We provide an analysis of performance of the new simulator, together with a performance comparison between the cell-like and the tissue-like simulators. The paper is structured as follows: Section 2 introduces the model of tissue P systems with cell division and the solution to SAT; Section 3 surveys the typical GPU architecture and the peculiarities of GPU computing; Section 4 depicts the design of the new simulator; Section 5 provides the performance analysis of the developed simulator and the mentioned comparisons; and finally, Section 6 ends the paper with conclusions and open research lines. 2 Tissue-like P systems In this paper, we work on computational devices inspired by the cell inter– communication in tissues, and adding the ingredient of cell division rules. Cell division is an elegant process that enables organisms to grow and reproduce by means of the production of two daughter cells from a single parent cell. Tissue P systems with cell division are inspired by the cell-like model of P systems with active membranes [13]. In these models, the cells are not polarized; cells obtained by division have the same labels as the original cell, and if a cell is Simulating a Family of Tissue P Systems Solving SAT on the GPU 203 divided, its interaction with other cells or with the environment is locked during the division process. First, we recall some preliminaries. An alphabet Γis a non–empty set whose elements are called symbols. A multiset mover an alphabet Γis a pair m= (Γ, f) where fis a mapping from Γinto N. If m= (Γ, f) is a multiset then its support is defined as supp(m) = {x∈Γ|f(x)>0}. A multiset is finite if its support is a finite set. If supp(m) = {a1, . . . , ak}then the multiset mwill be denoted as m=af(a1) 1. . . af(ak) k(here the order is irrelevant), and we say that f(a1) + · · · +f(ak) is the cardinal of m, denoted by |m|. The empty multiset is denoted by λ. Let m1= (Γ, f1) and m2= (Γ, f2) multisets over Γ. The union of m1and m2, denoted by m1+m2, is the multiset (Γ, g), where g=f1+f2, that is, g(x) = f1(x)+f2(x) for each x∈Γ. The relative complement of m2in m1, denoted by m1\m2is the multiset (Γ, g), where g(x) = f1(x)−f2(x) if f1(x)≥f2(x) and g(x) = 0 otherwise. Definition 1. A tissue P system with cell division of degree q≥1is a tuple Π= (Γ, Σ, E,M1,...,Mq,R, iin, iout), where: 1. Γ, Σ and Eare finite alphabets such that Σ(Γand E ⊆ Γ. 2. Γhas two distinguished objects yes and no, and {yes,no}∩E=∅. 3. M1,...,Mqare finite multisets over Γ\Σ. 4. At least one copy of objects yes and no are present in some initial multisets M1, . . . , Mq, but none of them are present in E. 5. Ris a finite set of rules of the following forms: (a) Communication rules:(i, u/v, j), for i, j ∈ {0,1,2, . . . , q}, i 6=j,u, v finite multisets over Γ, and |u+v| 6= 0; (b) Division rules:[a]i→[b]i[c]i, where i∈ {1,2, . . . , q},i6=iout and a, b, c ∈Γ. 6. iin ∈ {1,2, . . . , q}, and iout ∈ {0,1, . . . , q}. Atissue P system with cell division Π= (Γ, Σ, E,M1,...,Mq,R, iin, iout) of degree q≥1 can be viewed as a set of qcells, labeled by 1, . . . , q, with an environment labeled by 0 such that: (a) M1,...,Mqare finite multisets over Γ representing the objects (elements in Γ) initially placed in the qcells of the system; (b) Eis the set of objects located initially in the environment of the system, all of them appearing in an arbitrary number of copies; and (c) iin represents the input cell, and iout ∈ {0,1, . . . , q}represents the region (a distinguished cell when iout ∈ {1, . . . , q}, or the environment when iout = 0) which will encode the output of the system. When applying a rule (i, u/v, j), the objects of the multiset uare sent from region ito region jand, simultaneously, the objects of multiset vare sent from region jto region i. When applying a division rule [a]i→[b]i[c]i, under the influence of object a, the cell with label iis divided into two cells with the same label. In the first copy, object ais replaced by object b, and in the second one, 204 M.A. Mart´ınez-del-Amor, J. P´erez-Carrasco, M.J. P´erez-Jim´enez object ais replaced by object c; all the other objects are replicated and copies of them are placed in the two new cells. The output cell iout cannot be divided. The rules of a tissue P system with cell division are applied in a nondeterministic maximally parallel manner. At each step, all the cells which can evolve must evolve in a maximally parallel way (at each step, we apply a multiset of rules which is maximal, no further rule can be added), with the following important remark: if a cell divides, only the division rule is applied to that cell at that step; the objects inside that cell do not evolve by means of communication rules. Aconfiguration at any instant of Πis described by all multisets of objects over Γassociated with all the cells present in the system, and the multiset of objects over Γ\E associated with the environment at that moment. Given a finite multiset mover Σ, the initial configuration with input mis (M1,...,Miin +m, . . . , Mq;∅). A configuration is a halting configuration if no rule of the system is applicable to it. We say that configuration C1yields configuration C2in one transition step if we can pass from C1to C2by applying the rules from Rfollowing the previous remarks. A computation of Πis a sequence of configurations such that: (a) the first term of the sequence is an initial configuration of the system; (b) each remaining term of the sequence is obtained from the previous one by applying the rules of the system in a maximally parallel manner with the restrictions previously mentioned; and (c) if the sequence is finite (called halting computation), then the last term of the sequence is a halting configuration. A tissue P system with cell division is a recognizer system if all computations halt, and if Cis a computation of Π, then either object yes or object no (but not both) must have been released into the environment, and only at the last step of the computation. We say that Cis an accepting (respectively, rejecting) computation if object yes (respectively, object no) appears in the environment associated with the corresponding halting configuration of C. 2.1 An efficient solution to SAT by means of tissue P systems with cell division This section presents an efficient solution to the SAT problem by means of family of recognizer tissue P systems with cell division (see [14] for details). For each pair of natural numbers m, n ∈N, we will consider the recognizer tissue P system with cellular division Π(hm, ni)=(Γ, Σ, µ, M1,M2, R, 2) of degree 2, defined as follows: •The input alphabet is Σ={xi,j, xi,j : 1 ≤i≤n, 1≤j≤m} •The working alphabet is Γ=Σ∪ {ai, ti, fi|1≤i≤n}∪{ri|1≤i≤m} ∪ ∪ {Ti, Fi|1≤i≤n}∪{Ti,j, Fi,j |1≤i≤n, 1≤j≤m+ 1} ∪ ∪ {bi|1≤i≤2n+m+ 1}∪{ci|1≤i≤n+ 1} ∪ ∪ {di|1≤i≤2n+ 2m+nm + 1}∪ ∪ {ei|1≤i≤2n+ 2m+nm + 3} ∪ {f, g, yes,no} Simulating a Family of Tissue P Systems Solving SAT on the GPU 205 •The environment alphabet is E=Γ− {yes,no}. •The set of labels is {1,2}. •The initial multisets associated with the cells are M1={yes,no, b1, c1, d1, e1} and M2={f, g, a1, a2, . . . , an}. •The input cell is the one labeled by 2, and the output region is the environment. •The set Ris formed by the following rules: 1. Division rule: (a) [ ai]2→[Ti]2[Fi]2, for i= 1,2, . . . , n. 2. Communication rules: (b) (1, bi/b2 i+1,0),for i= 1, . . . , n. (c) (1, ci/c2 i+1,0),for i= 1, . . . , n. (d) (1, di/d2 i+1,0),for i= 1, . . . , n. (e) (1, ei/ei+1,0),for i= 1,...,2n+ 2m+nm + 2. (f) (1, bn+1cn+1/f, 2). (g) (1, dn+1/g, 2). (h∗) (1, f2/f, 0). (h) (2, cn+1Ti/cn+1 Ti,1,0),for i= 1, . . . , n. (i) (2, cn+1Fi/cn+1 Fi,1,0),for i= 1, . . . , n. (j) (2, Ti,j/tiTi,j+1,0),for i= 1, . . . , n and j= 1, . . . , m. (k) (2, Fi,j/fiFi,j+1,0),for i= 1, . . . , n and j= 1, . . . , m. (l) (2, bi/bi+1,0). (m) (2, di/di+1,0), for i=n+ 1,...,2n+m. (n) (2, b2n+m+1 tixi,j/b2n+m+1 rj,0). (o) (2, b2n+m+1 fixi,j/b2n+m+1 rj,0),for 1 ≤i≤nand 1 ≤j≤m. (p) (2, di/di+1,0), for i= 2n+m+ 1,...,2n+m+nm. (q) (2, d2n+m+nm+jrj/d2n+m+nm+j+1,0), for j= 1, . . . , m. (r) (2, d2n+2m+nm+1/f yes,1). (s) (2,yes/λ, 0). (t) (1, e2n+2m+nm+3 fno/λ, 0). Let ϕ=C1∧ · ·· ∧ Cmbe a propositional formula in CNF1such that the set of variables of the formula is V ar(ϕ) = {x1, . . . , xn}, and consists of mclauses Cj=yj,1∨· · ·∨yj,kj, 1 ≤i≤m, where yj,j0∈ {xi,¬xi: 1 ≤i≤n}are the literals of ϕ. Without loss of generality, we can assume that the formula is in simplified expression. Next, we consider a polynomial encoding (cod, s) of the SAT problem in the family Π={Π(t)|t∈IN}. The function cod associates to the previously described propositional formula ϕ, that is an instance of SAT with parameters n(number of variables) and m(number of clauses), the following multiset of objects 1Conjunctive Normal Form 206 M.A. Mart´ınez-del-Amor, J. P´erez-Carrasco, M.J. P´erez-Jim´enez cod(ϕ) = m [ i=1 {xi,j :xi∈Cj}∪{xi,j :¬xi∈Cj} In this case, object xi,j represents that variable xibelongs to clause Cj. The size function, s, is defined as follows s(ϕ) = hm, ni=(m+n)·(m+n+1) 2+m. The system of the family Πto process the instance ϕwill be the tissue P system Π(s(ϕ)) with input multiset cod(ϕ). The execution of the system Π(s(ϕ)) with input cod(ϕ) is structured in six phases: •Valuations generation phase: in this phase all the possible relevant truth valuations are generated for the set of variables of the formula {x1, . . . , xn}. It is implemented by using division rules (a), whereby each object xiproduces two new cells, one having the object Ti, that codifies the true value of the variable xi, y and the other having the object Ti, that codifies the false value of the variable xi. Thus, 2ncells are obtained in ncomputation steps. These cells are labeled by 2, and each one codifies each possible truth valuation of the set of variables {x1, . . . , xn}. Meanwhile, the objects f, g are replicated in each created cell. This phase spends ncomputation steps. •Counters generation phase: simultaneously, and using the rules (b),(c), (d) and (e), the counters bi, ci, di, eiof the cell labeled by 1, are evolving such that in each computation step the number of objects in each one are doubling. Thereby, through this process and after nsteps, we get 2ncopies of the objects bn+1, cn+1, and dn+1. Objects b0swill be used to check which clauses are satisfied for each truth valuation. Objects c0sare used to obtain a sufficient number of copies of ti, fi(namely, m). Objects d0swill be used to check if there is at least one valuation satisfying all clauses. Finally, objects e0swill be used to produced, in its case, the object no at the end of the computation. •Checking preparation phase: this phase aims at preparing the system for checking clauses. For this, at step n+ 1 of the computation, and by the application of the rules (f) and (g), the counters bn+1, cn+1, dn+1 of the cell 1 is exchanged for the objects fand gof the 2ncells 2. Thus, after this step, each cell labeled by two has a copy of the objects bn+1, cn+1, dn+1, while the cell 1 has 2 copies of the objects fand g. Subsequently, the presence of an object cn+1 in each one of the 2ncells labeled by 2 allows to generate the objects Ti,1and Fi,1. By the application of rules (j) and (k), these objects allows the emergence of mcopies of tiand mcopies of fi, according to the values of truth or falsity that a cell 2 assigns to a variable xi. This process spends n+msteps since there is only one object cn+1 in each cell 2 and, moreover, for each i= 1, . . . , n, the rules (j) and (k) are applied exactly mconsecutively times. Simultaneously, in the first steps of this process, the application of the rule (h∗) makes the cell labeled by 1 to appear only one copy of the object yes. Simultaneously in this phase, the counters bi, diand eiare evolving by the applications of the corresponding rules. Simulating a Family of Tissue P Systems Solving SAT on the GPU 207 •Checking clauses phase: in this phase, the clauses that are true for every truth valuation are determined, and encoded by a cell labeled by 2. This phase starts at the computation step (n+1)+(n+m) + 1 = 2n+m+ 2. Using the rules (n) and (o), the true clauses are checked for each valuation encoded by a cell., so that the appearance of an object rjin a cell 2 means that the corresponding valuation makes true the clause Cj. Bearing in mind that a single copy of the object b2n+m+1 is in each cell, the phase takes nm computation steps. Thus, the configuration C2n+m+nm+1 is characterized by the following: – It contains exactly 2ncells labeled by 2. Each one contains the object d2n+m+nm+1, and copies of objects rjfor each clause Cjmade true by the encoded valuation in the cell. – It contains a unique cell labeled by 1, containing a copy of objects yes,no, f, g and the counter e2n+m+nm+2. This phase consumes mcomputation steps. •Formula checking phase: in this phase it is determined if there exists any valuation making true the mclauses of the formula. For this, the rules of type (q) are used, analyzing in an ordered way (first the clause C1, after that clause C2, and so on) if the clauses of the formula are being satisfied by the represented valuation in the corresponding cell labeled by 2. For example, from counter d2n+m+nm+1 appearing in every cell 2, the appearance of the object r1 (the valuation makes true clause C1) permits to generate in that cell the object d2n+m+nm+2. This object, in turn, permits to evolve object d2n+m+nm+3 if in that cell appears the object r2. In this manner, a valuation represented by a cell labeled by 2 makes true the formula ϕif and only if the object d2n+m+nm+m+1 appears in the content of that cell in the configuration C2n+m+nm+m+1. •Output phase: in this phase the system will provide the corresponding output, depending on the analysis in the formula checking phase. If the formula ϕis satisfiable, then there is some cell in the configuration C2n+m+nm+m+1 that contains an object d2n+m+nm+m+1. In this case, the application of rule (r) sends an object fand the object yes to the cell 1. The object yes therefore disappears from cell 1, and consequently, rule (t) can not be applied. In the next computation step, the application of the rule (s) produces an object yes in the environment (for the first time during the whole computation) and the process ends. If the formula ϕis not satisfiable, then there no exist any cell in the configuration C2n+m+nm+m+1 containing an object d2n+m+nm+m+1. In this case, the rule (r) is not applicable, and in the next computation step, the counter eievolves, providing an object e2n+m+nm+m+3 in the cell 1. This object permits the application of rule (t), since the objects no and fremains in the cell 1. In this way, the object no is sent in the next computation step, and the computation finalizes. It can be easily proved that the family Π={Π(hm, ni) : n, m ∈N}, defined above, is polynomially uniform by deterministic Turing machines. For this, it is enough to keep in mind that the systems of the family have benn defined through 208 M.A. Mart´ınez-del-Amor, J. P´erez-Carrasco, M.J. P´erez-Jim´enez recursive expressions, and the amount of resources needed to describe the system Π(hm, ni) is quadratic in max{m, n}. Indeed: 1. Size of the alphabet: 6nm + 12n+ 7m+ 12 ∈Θ(nm). 2. Number of initial cells: 2 ∈Θ(1). 3. Number of initial objects: n+ 8 ∈Θ(n). 4. Number of rules: 4nm + 10n+ 3m+ 16 ∈Θ(nm). 5. Upper limit of rule length: 5 ∈Θ(1) 3 GPU computing The GPU (Graphics Processor Unit) is a specialized chip designed to manipulate computer graphics efficiently. In fact, it is an essential part of most current computers. Their highly parallel structure is based on hundreds of simple computing cores, making them more effective than common CPUs for processing large blocks of data in parallel [8]. Thus, the GPU is being consolidated as a device suitable for High Performance Computing, as it was foreseen by Elster [5] and other authors [8]. 3.1 CUDA programming model In 2007, NVIDIA announced CUDA (Compute Unified Device Architecture) [17], a programming model totally abstracted from the hardware of the GPU. Based on C, the programmer only has to think on threads and arrays, together with some performance aspects. This easy way to build large applications has led to a rapidly evolution of GPU computing [11]. As a result, CUDA has been successfully utilized for developing P systems simulators [1, 2, 3, 4, 9]. CUDA provides an heterogeneous computing system, consisting of a host (the CPU) and several devices (GPUs) [7]. The idea is to execute on device program sections with large amount of data parallelism. These sections are written in separated C functions called kernel. Each kernel is executed on the GPU by a grid of threads. As shown in Figure 1, threads are grouped in blocks. Threads belonging to the same block are easily synchronized by barrier operations (when a thread reaches the barrier, wait for the rest to continue). The memory model is also an aspect to consider in the CUDA programming model. This memory hierarchy is explicitly and manually managed. The global memory is the largest (but slowest) in the GPU. It is accessed by the host, and also by any thread, as it is the communication channel between the host and the device. The smallest (but fastest) memory is the shared memory. It is local to each block, but the content is volatile through kernels calls, and the CPU cannot read it. Finally, there is a variety of atomic operations to update single data elements in any memory in a concurrently and synchronously way. An efficient way to structure an algorithm in CUDA is by maximizing the usage of the memory hierarchy, as follows: Simulating a Family of Tissue P Systems Solving SAT on the GPU 209 Fig. 1: Overview of CUDA programming model. 1. The threads of each block read its corresponding data portion from global memory to shared memory (which is inevitable because the host only can put the data in global memory). 2. Threads work with the data directly on shared memory. 3. Threads copy these data back to global memory (so the host can retrieve the result). 3.2 A modern GPU architecture The GPU used in our work is the NVIDIA Tesla C1060. We use this model since it was used in our previous work, and the aim is to compare results. The Tesla C1060 is based on a scalable processor array which has 240 SPs (streamingprocessor) cores organized as 30 SMs (streaming multiprocessor) and 4 GB of off-chip GDDR3 memory called device memory. The applications start at the host side which communicates with the device side through a bus, which is a PCI Express x16 bus standard. The SM is the processing unit and an unified graphics and computing multiprocessor. Every SM contains the following units: eight SPs arithmetic cores, one double precision unit, an instruction cache, a read only constant cache, 16- Kbyte on-chip read/write shared memory, a set of 16384 32-bit registers, and access to the off-chip memory (device/local memory). The SM also has two SFUs that execute more complex floating point operations such as reciprocal square root, 216 M.A. Mart´ınez-del-Amor, J. P´erez-Carrasco, M.J. P´erez-Jim´enez 2 4 8 16 32 64 128 256 0,1 1 10 100 Sequential simulator Parallel simulator Objects per membrane Miliseconds Fig. 3: Simulation performance for tsp-sat-seq and tsp-sat-gpu: Test 1 (2048 membranes) 64 128 256 512 1K 2K 4K 8K 16K 32K 64K 128K 256K 512K 1M 2M 0,1 1 10 100 1000 10000 100000 Sequential simulator Parallel simulator Membranes Miliseconds Fig. 4: Simulation performance for tsp-sat-seq and tsp-sat-gpu: Test 2 (256 Objects/Membrane) management. However, for very large systems, the speedup is as large as only considering kernels. The maximum speedup is given for 4 M cells, up to 10x. 5.2 Cell-like vs tissue-like Next, we compare the two simulators developed for the two solutions to SAT using P systems with active membranes (let call it am-sat-gpu) and tissue P systems with cell division (tsp-sat-gpu). Here we study which model is better suited to be simulated on the GPU. Simulating a Family of Tissue P Systems Solving SAT on the GPU 217 64 128 256 512 1K 2K 4K 8K 16K 32K 64K 128K 256K 512K 1M 2M 4M 0 2 4 6 8 10 12 Number of membranes Speedup Fig. 5: Speedup achieved running test (256 Objects/Cell) for tsp-sat-gpu and tspsat-seq. GPU data management is also considered. First of all, we should analyze the differences between them to better understand the different behaviors. We highlight the following: •Computational steps: given m, n ∈N, representing the number of clauses and variables respectively, the cell-like P systems take 5n+ 2m+ 3 steps, and the tissue P systems require 2n+ 2m+nm + 1. Thus, the computation of the tissue-like solution is longer (in number of steps), if m > 3 + 2 n≃3. •Phases: am-sat-gpu is based on 4 phases (implemented in 3 kernels), whereas tsp-sat-gpu uses 5 phases (implemented in 4 kernels). •Memory requirements: each membrane in am-sat-gpu is represented by a number of 32-bit integers equals to |cod(ϕ)|, but the tissue-like simulators use for them 2n+ 4 + |cod(ϕ)|. Thus, tsp-sat-gpu uses, in total, (2n+ 4)2nbytes more. Figure 6 compares both solutions using Test 2. It can be observed that the kernels of am-sat-gpu outperforms tsp-sat-gpu, even using optimizations for the last one. This improvement implies a speedup of 2.9x. However, if we take into account the data management in the GPU, we can see that the behavior of them is almost similar. The simulator am-sat-gpu runs just a bit faster, but for 2 M membranes, the speedup is almost 2x. This makes us to think that the data implementation of am-sat-gpu can be improved, since it requires an inferior amount of data. Recall that am-sat-gpu has not any GPU oriented enhancements, as in tsp-sat-gpu. We finish this comparison by reporting their corresponding maximum speedup with their sequential counterparts, which is of 63x and 10x for the cell-like and tissue-like simulators, respectively. Therefore, using the GPU for the cell-like solutions allows to get better performance gain. 218 M.A. Mart´ınez-del-Amor, J. P´erez-Carrasco, M.J. P´erez-Jim´enez 64 128 256 512 1K 2K 4K 8K 16K 32K 64K 128K 256K 512K 1M 2M 0 0,5 1 1,5 2 2,5 3 3,5 Speedup (w/ data) Speedup (w/o data) Number of membranes Speedup Fig. 6: Achieved speedup for both tsp-sat-gpu and am-sat-gpu simulators, considering (w/ data) or not considering (w/o data) the time for data management. 5.3 Characterizing the simulation on the GPU Next, we characterize the simulations carried out in this work. From the comparison of the simulators for the cell-like and the tissue-like solutions, we have observed that the cell-like simulations are better carried out by the GPU. Thus, we have identified two properties that have helped to improve the performance of these GPU simulators: •Charges: the model of P systems with active membranes associates charges to the membranes. They can be used to store information over the computation as well. If they are considered (and effectively used) for a given solution (e.g. to encode the truth assignment for SAT), less memory would be required (remind that the tissue-like simulator requires 2n(2n+ 4) bytes more). In fact, the information encoded by charges can save objects that may or not may appear simultaneously in membranes, what saves also memory, and so, the number of threads to launch, working with much less objects. •Rules with no cooperation: the model of P systems with active membranes defines rules with no cooperation, that is, the number of objects appearing in their left-hand sides is always 1. This property helps threads to be assigned to each rule, what also means to work with each object in parallel. Rules permitting cooperation (as in tissue P systems) require to take care of which objects are accessed by rules (and threads). It would be also interesting to study each type of rule (i.e., division, communication for tissue-like, and division, dissolution, send-in, send-out and evolution for cell-like) separately. Recall that a more flexible and general simulator for active membranes [2], the constraints of send-in, send-out, division and dissolution rules have to be considered for each membrane, what degrades parallelism on the GPU (it implies using local locks). However, in the model of tissue P systems these restrictions are not presented. A flexible simulator for tissue models can be implemented in a future Simulating a Family of Tissue P Systems Solving SAT on the GPU 219 to study what is better: usage of charges but restricting types of rules, or not using charges (i.e. more objects per membrane) and more (but less restrictive) parallel rules. 6 Conclusions In this paper we have presented a recent result on the parallel simulation with GPUs of an efficient solution to SAT by tissue P systems with cell division. The CUDA simulator design is similar to the one used in the previous simulator for a solution based on P systems with active membranes. 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. Experiments show that the CUDA simulator outperforms the sequential one by 10x. It can be seen that solving the same problem (SAT) under different P system variants leads to different speedups on the GPU (up to 2.9x for the celllike simulator against the tissue-like). Indeed, we show that the usage of charges can help to save space devoted to objects, and rules without cooperation to increase thread parallelism. Future work will be focused on developing new GPU-based simulators for other P systems models, and on improving the existing ones. In addition, further research can be carried out concerning the parallel simulation of particular P systems features, identifying which of them can be easily combined and efficiently simulated by the GPU. In this way, novel approximations for parallel simulators development can be performed also at the P systems area. An approach is to define a P system model combining all the good features for GPU simulators (let call it GP systems, or GPU oriented P systems). Then, the creation of a GPU based simulator for GP systems would be straightforward, considering the corresponding GPU oriented optimizations. However, it would be important to define a translation protocol from other P systems models to GP systems. Acknowledgments The authors acknowledge the support of “Proyecto de Excelencia con Investigador de Reconocida Val´ıa” of the “Junta de Andaluc´ıa” under grant P08-TIC04200, and the support of the project TIN2012-37434 of the “Ministerio de Econom´ıa y Competitividad” of Spain, both co-financed by FEDER funds. References 1. F. Cabarle, H. Adorna, M.A. Mart´ınez-del-Amor, M.J. P´erez-Jim´enez. Improving GPU Simulations of Spiking Neural P Systems, Romanian Journal of Information Science and Technology,15, 1 (2012), 5–20. 220 M.A. Mart´ınez-del-Amor, J. P´erez-Carrasco, M.J. P´erez-Jim´enez 2. J.M. Cecilia, J.M. Garc´ıa, G.D. Guerrero, M.A. Mart´ınez-del-Amor, I. P´erez- Hurtado, M.J. P´erez-Jim´enez. Simulation of P systems with Active Membranes on CUDA, Briefings in Bioinformatics,11, 3 (2010), 313–322. 3. J.M. Cecilia, J.M. Garc´ıa, G.D. Guerrero, M.A. Mart´ınez-del-Amor, I. P´erez- Hurtado, M.J. P´erez-Jim´enez. Simulating a P system based efficient solution to SAT by using GPUs, Journal of Logic and Algebraic Programming,79, 6 (2010), 317–325. 4. J.M. Cecilia, J.M. Garc´ıa, G.D. Guerrero, M.A. Mart´ınez-del-Amor, M.J. P´erez- Jim´enez, M. Ujald´on. The GPU on the simulation of cellular computing models, Soft Computing,16, 2 (2012), 231–246. 5. A. C. Elster. High-performance computing: Past, present and future, LNCS, 2367 (2002), 433–444. 6. M. Garc´ıa-Quismondo, R. Guti´errez-Escudero, I. P´erez-Hurtado, M.J. P´erez- Jim´enez, Agust´ın Riscos-N´u˜nez. An overview of P-Lingua 2.0, LNCS,5957 (2010), 264–288. 7. D. Kirk, W. Hwu. Programming Massively Parallel Processors: A Hands On Approach, MA (USA), 2010. 8. M. Harris. Mapping computational concepts to GPUs, ACM SIGGRAPH 2005 Courses, NY (USA), 2005. 9. M.A. Mart´ınez-del-Amor, I. P´erez-Hurtado, A. Gastalver-Rubio, A.C. Elster, M.J. P´erez-Jim´enez. Population Dynamics P systems on CUDA, LNCS,7605 (2012), 247-266. 10. V. Nguyen, D. Kearney, G. Gioiosa. Balancing performance, flexibility, and scalability in a parallel computing platform for Membrane Computing applications, LNCS,4860 (2007), 385-413. 11. J.D. Owens, M. Houston, D. Luebke, S. Green, J.E. Stone, J.C. Phillips. GPU Computing, Proceedings of the IEEE,96, 5 (2008), 879-899. 12. G. P˘aun. Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143, and TUCS Report No 208. 13. G. P˘aun. Attacking NP-complete problems, In Unconventional Models of Computation, UMC’2K, 2000, 94-115. 14. G. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez. Tissue P System with cell division. International Journal of Computers, Communications &Control,3, 3 (2008), 295- 303. 15. G. P˘aun, G. Rozenberg, A. Salomaa (eds.). The Oxford Handbook of Membrane Computing, Oxford University Press, 2010. 16. M. Qasem. WinSAT website, 2009,http://www.mqasem.net/sat/winsat. 17. Official NVIDIA CUDA website.http://www.nvidia.com/cuda 18. The PMCGPU project website.http://sourceforge.net/p/pmcgpu