On the Simulations of Evolution-Communication P Systems with Energy without Antiport Rules for GPUs

On the Simulations of Evolution-Communication P Systems with Energy without Antiport Rules for GPUs Richelle Ann B. Juayong1, Francis George C. Cabarle1, Henry N. Adorna1, Miguel A. Mart´ınez–del–Amor2 1Algorithms & Complexity Lab Department of Computer Science University of the Philippines Diliman Diliman 1101 Quezon City, Philippines E-mail: [email protected],[email protected],[email protected] 2Research 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] Summary. In this report, we present our initial proposal on simulating computations on a restricted variant of Evolution-Communication P system with energy (ECPe system) which will then be implemented in Graphics Processing Units (GPUs). This ECPe systems variant prohibits the use of antiport rules for communication. Several possible levels of parallelizations for simulating ECPe systems computations on GPUs are emphasized. Our work is based on a localized matrix representation for the mentioned variant given in a previous literature. Our proposal employs a methodology for forward computing also discussed in the said literature. Key words: Membrane computing, Parallel computing, GPU computing 1 Introduction Evolution-Communication P systems with energy (ECPe systems) [1] is a variant of P systems introduced in 2009 to initiate a framework for communication complexity. It originates from Evolution-Communication P (ECP) systems [10], a hybrid of two well-investigated variants, Transition P systems [9] and P systems with Symport and Antiport rules [11]. The difference between ECPe and ECP systems is the presence of a special object called ‘energy’ in the former, which can be produced through evolution rules and consumed in communication rules. One 268 R.A.B. Juayong et al. crucial restriction for ECPe systems includes the use of energy for each communication rule. Thus, no object can be communicated without using some ‘quanta’ of energy. Moreover, upon being delivered to a receiving region, the energy used in a communication does not pass through any membrane. In this manner, it is said that the energy used in the process of communication is being ’lost’. Several recent works have introduced the concept of representing certain P system variants and their computations as matrices and vector-matrix operations, respectively. In particular, variants known as Spiking Neural P (SNP) systems and their matrix representations were introduced in [5] whereas matrix representations for ECPe systems were given in [6]. Aside from creating a ‘convenient’ and relatively compact way of describing the systems and their computations, the matrix representations add additional ease to their simulation and implementation in parallel hardware. Vector and matrix operations are highly parallelizable and can be efficiently implemented in parallel hardware, including Graphics Processing Units (GPUs). GPUs are massively parallel hardware not like current generation CPUs. Using their respective matrix representations, SNP systems have been successfully implemented in GPUs in [2] and more recently in [3]. The intention of this current work is to continue such trend i.e. to provide our methodology on how to implement ECPe systems computations (using the vector-matrix representations) on parallel hardware, in particular GPUs. 2 Evolution-Communication P Systems with Energy 2.1 Formal Definition of ECPe systems Before we proceed, we note that the readers are assumed to be familiar with the fundamentals of formal language theory and membrane computing [9]. A relatively new variant of Evolution-Communication P systems [10] has been introduced in [1] to evaluate communication that is dependent on some energy produced from evolution rules. A special object eis introduced to the system to represent a quantum of energy. We use the definition for EC P system with energy (ECPe system) from [1]. Definition 1. An EC P system with energy is a construct of the form Π= (O, e, µ, w1, . . . , wm, R1, R0 1, . . . , Rm, R0 m, iout) where: (i) mpertains to the total number of membranes; (ii) Ois the alphabet of objects; (iii) µis the membrane structure which can be denoted by a set of paired square brackets with labels. We say that membrane iis the parent membrane of a membrane j, denoted parent(j), if the paired square brackets representing On the Simulations of ECPe Systems with Energy for GPUs 269 membrane jis located inside the paired square brackets representing membrane i, i.e. [i. . . [j]j]i. Reversely, we say that membrane jis a child membrane of membrane i, denoted j∈children(i) where children(i) refers to the set of membranes contained in membrane i. The relation of parent and child membrane becomes more apparent when we represent the membrane structure as a tree. Since order does not matter in our model, there can be multiple trees (isomorphic with respect to children of a node), each corresponding to the same membrane structure representation. (iv) w1, . . . , wmare strings over O∗where widenotes the multiset of object present in the region bounded by membrane i. (v) R1, . . . , Rmare sets of evolution rules, each associated with a region delimited by a membrane in µ; •An evolution rule is of the form a→vwhere a∈O,v∈(O∪ {e})∗. In the event that this type of rule is applied, the object atransforms into a multiset of objects vin the next time step. Through evolution rules, object ecan be produced, but eshould never be in the initial configuration and object eis not allowed to evolve. (vi) R0 1, . . . , R0 mare sets of communication rules, each associated with a membrane in µ; A communication rule can either be a symport or an antiport rule: •A symport rule can be of the form (aei, in) or (aei, out), where a∈O, i≥1. By using this rule, icopy of eobjects are consumed to transport object ainside (denoted by in) or outside (denoted by out) the membrane where the rule is defined. To consume copies of object emeans that upon completion of the transportation of object a, the occurrences of eare lost, they do not pass from a region to another one. •An antiport rule is of the form (aei, out;bej, in) where a, b ∈Oand i, j ≥1. By using this rule, we know that there exists an object ain the region immediately outside the membrane where the rule is declared, and an object binside the region bounded by the membrane. In the application of this rule, object aand object bare swapped using iand jcopies of object ein the different regions, respectively. As in symport rules, the copies of object eare lost after the application. We say that a communication rule has a sending and receiving region. For a rule r∈R0 iassociated with an in label, its receiving region is region i and its sending region is the parent(i). On the other hand, the sending and receiving regions are reversed for a rule r∈R0 iassociated with an out label. For an antiport rule r∈R0 i, region iand parent(i) are both sending and receiving region. Also, note that no communication can be applied without the utilization of object e. (vii) iout ∈ {0,1, . . . , m}is the output membrane. If iout = 0, this means that the environment shall be the placeholder of the output. Rules are applied in a nondeterministic, maximally parallel manner. Nondeterminism, in this case, has the following meaning: when there are more than two evolution rules that can be applied to an object, the system will randomly choose 270 R.A.B. Juayong et al. the rule to be applied for each copy of the object. The system assumes a universal clock for simultaneous processing of membranes; all applicable rules have to be applied to all possible objects at the same time. The behavior of maximally parallel application of rule requires that all object that can evolve (or be transferred) should evolve (or be transferred). Note that there is a one-to-one mapping between region and membrane, however, strictly, region refers to the area delimited by a membrane. A configuration at any time i, denoted by Ci, is the state of the system; it consists of the membrane structure and the multiset of objects within each membrane. A transition from Cito Ci+1 through nondeterministic and maximally parallel manner of rule application can be denoted as Ci⇒Ci+1. A series of transition is said to be a computation and can be denoted as Ci⇒∗Cjwhere i < j. Computation succeeds when the system halts; this occurs when the system reaches a configuration wherein none of the rules can be applied. This configuration is called a halting configuration. If there is no halting configuration—that is, if the system does not halt—computation fails, because the system did not produce any output. Output can either be in the form of objects sent outside the skin, the outermost membrane, or objects sent into an output membrane. We let N(Π) be the set of numbers generated by a given ECPe system Π. 2.2 An Example To show how ECPe system works, we shall give an example of an ECPe system with two membranes adapted from [1]: Π= ({a, #}, e, [1[2]2]1, a2#, λ, {r11 :a→aa, r12 :a→ee},∅, {r21 : # →#},{r0 21 : (ae, in), r0 22 : (#e, in)},2) Fig. 1. Graphical representation of an ECPe system Πwhere N(Π) = {2(n+ 1)|n≥0} from [1]. On the Simulations of ECPe Systems with Energy for GPUs 271 A graphical illustration of Πis shown in Figure 1. Its output is N(Π) = {2(n+ 1)|n≥0}. The computation to generate this proceeds as follows: Initially, we can use either rule r11 or r12 in order to consume the copies of object ain membrane 1. At any time, we can use both r11 and r12 to evolve copies of object a. For every copy of a, we produce either two copies of object eor another two copies of object a, therefore, we are always assured that multiplicity of object ain region 1 is even, as well as the multiplicity of object e. Note that upon introduction of object ein the system, it should immediately be used (in the next step) to transport copies of object ain region 2, otherwise, it will be used to transport the trap symbol # in region 2 using rule r0 22 leading the system to a never ending computation due to rule r21. For a computation to halt, rule r0 21 should be the last rule to be applied. Since copies of object etransporting copies of object ain region 2 is always even, we are assured that the multiplicity of objects (copies of object a) in region 2 is also even. The minimum value 2 is produced when we use both rule r11 and r12 in configuration C1. In the next step, we use two applications of rule r0 21. This will cause the system to halt. 2.3 Representation and Methodology for Forward Computing In this section, we relate how computations in ECPe systems without antiport rules can be performed in a localized manner. As will be shown, when we do not allow antiport rules, membranes can compute more independently. This representation has been used in [4] to answer the problem of computing backward and forward. We shall relate the methodology for the latter. By computing forward, the problem is to find the next configurations that can be yielded in one computational step given a current configuration. Let h∈ {0,1,2, . . . , m}where region 0 refers to the region located outside the skin, the outermost membrane. The following notations and definitions are adopted from [4] and used in the remaining parts of this section. •Let IO(r, h) be the set of objects in region hinvolved in a rule r. •Let TO(r, h) be the set of objects in region hthat trigger a rule r. •The set of rules IR(h) = Rh∪R0 h∪(Sh0∈children(h)R0 h0) represents the set of rules that directly influences the content of region hat any time of a computation. An object αin region hat any time i≥0 may either be produced by an evolution rule, transported from neighboring region to region h(or vice versa), or simply carried over. In the first scenario, it is by definition that the rule that produced object αmust be in Rh. A neighboring region may either be a region delimited by parent(h) or regions delimited by membranes in children(h). In the first case, the rules for communication are in R0 hwhile in the second case, the rules for communication must be in one of R0 h0where h0∈children(h). •The set PO(h) = {α|αappeared in wh} ∪ (Sr∈IR(h)IO(r, h)) represents the set of objects (including special object e) that may possibly occur in region h at any time of a computation. Originally, the objects that surely exist in the region are the elements present in wh. In order to create a copy of an object 272 R.A.B. Juayong et al. α, object αmust either be produced or transported in region hthrough rules in IR(h). •The set TR(h) = {r|T O(r, h)6=∅} corresponds to the set of rules that contribute to the decrease of objects in region h. In order to activate rules belonging to such set, there must be a trigger object that may either be consumed or be used for transportation In order to represent configuration and rule application in terms of vectors, and represent effect of a rule in each region using a matrix, the concept of total order must be utilized. We note that for all the vector (and matrix) representation constructed in the remaining parts of this section, there is a need to define a total order hp1, p2, ...i(so that piis considered the ith element in a defined set) over the elements involved in the column for vectors (rows and columns for matrices). As can be observed, this is used so that elements are uniquely identified by their positions in the order to where they belong to and to assure that the position of elements are correct during the vector-matrix operation. Definition 2. Configuration Vector for each Region h A configuration vector Ci,h is a vector whose length is |PO(h)|. The vector Ci,h(α) refers to the multiplicity of object αin region hat configuration Ci. Definition 3. Application Vector for each Region h An application vector ai,h is a vector whose length is |R(h)|. The vector ai,h(r) refers to the number of application of rule rspecifically in region hduring the transition Ci−1⇒Ci. Definition 4. Transition Matrix for each Region h A transition matrix MΠECP e ,h is a matrix whose dimension is |R(h)|×|PO(h)|. The matrix MΠECP e ,h(r, α)returns the number of consumed or produced object α in region hupon single application of rule r. The consumed objects have negative values while the produced objects are positive. If object αin region his not used in rule r, then its value is zero. Given application vector ai,h representing a maximal set of rule applications applied in a configuration Ci−1to achieve configuration Ci, the paper [4] showed that a transition Ci−1→Cican be represented by performing Ci,h =Ci−1,h +ai,h.MΠ,h (1) for each region hprovided that if hand h0are the sender and receiver regions corresponding to a communication rule r0∈IR(h)∩IR(h0), then ai,h(r0) = ai,h0(r0). Illustrating Localized Computation To illustrate localized computation, we represent a possible transition C0⇒C1 by showing the effect of applying rule r11 and rule r12 once on the initial configuration of the example presented in Section 2.2. Since P O(0) = IR(0) = ∅, the participation of the environment is not needed in any part of the computation. On the Simulations of ECPe Systems with Energy for GPUs 273 For Region 1 At the onset, we can impose a total order ha, #, eiover P O(1) and total order hr11, r12, r0 21, r0 22iover IR(1). The initial configuration will be represented by the configuration vector C0,1where C0,1=210 and the representation for single application of both rules r11 and r12 will be given by application vector a1,1where a1,1=1100 Applying Equation (1) with the transition matrix MΠECP e ,1containing the values shown below: MΠECP e ,1=    100 −1 0 2 −1 0 −1 0−1−1     will yield the configuration vector C1,1 C1,1=212 which means that in the next configuration, there will be two copies of both object aand the special object eand a single copy of the trap symbol # in region 1. For Region 2 For region 2, we impose total order ha, #iover P O(2) and total order hr21, r0 21, r0 22i over IR(2). Since initially, no objects are present in region 2 and the rules involved in the transition C0⇒C1are not in IR(2), the configuration vector C0,2and the application vector a1,2will all contain zero values. We now show the transition matrix MΠECP e ,2 MΠECP e ,2=  0 0 1 0 0 1   Since application vector a1,2is a zero vector, the configuration vector C1,2remains also a zero vector. Notice that all the declared communication rules influence the multiplicity of objects in both region 1 and region 2. However, region 1 contains negative values because it acts as a sending region while region 2 have non-negative values since it acts as a receiving region. Also, matrix MΠECP e ,2shows that the special object ecan never reach region 2. Forward Computing in ECPe systems without Antiport Rules Shown below is a methodology for forward computing shown in [4]. 274 R.A.B. Juayong et al. 1. Categorize all possible objects in P O(h)for all region h. First, all α∈PO(h) are categorized for a certain region h. These categories are: •Category 1: Evolution Trigger Object αis an evolution trigger if there exists r∈Rhsuch that TO(r, h) = {α}. •Category 2: Communication Trigger Only Object αbelongs in this category if there does not exist r∈Rhsuch that TO(r, h) = {α}but there exists r0∈IR(h) such that α∈T O(r0, h). •Category 3: Not a Trigger Object αis neither in Category 1 nor in Category 2. 2. Construct identity rules for objects in Category 2 and 3 for all region h. For each α∈P O(h) that falls under one of Category 2 and Category 3, an identity rule α→αis added. All these rules shall be contained in a set labelled Radd,h. Also, a list of α0∈PO(h)− {e}that fall under Category 2 is maintained, the list shall be labelled Listcat2and sorted Listcat2in increasing order of energy requirement for transport. 3. Construct Trigger Matrix TMΠECP e,h for all region h The defined rules represented in the rows of TMΠECP e,h are the rules that contribute to the decrease of multiplicity of objects in region h. These rules are represented in the set T R(h). The additional rules from Radd,h are represented in the rows as well. The set of objects represented in the columns of T MΠECP e,h is PO(h). Therefore, T MΠECP e ,h has dimensions |T R(h)∪Radd,h|×|PO(h)|. TMΠECP e ,h(r, α) returns the multiplicity of αin region hneeded to activate a single application of rule r. 4. Set the dimension of the vector of unknowns (also called extended application vector) a0 i,h for all region h The length of a0 i,h is |TR(h)∪Radd,h|. 5. Solve system of linear equation Find all solutions to the equation a0 i,h.T MΠECP e ,h =Ci−1,h (2) Since elements of vector a0 i,h pertain to number of application of rules, these elements must be natural numbers. The value a0 i,h(r) can be interpreted as either the number of application of each rule r∈T R(h) or how many object αis unevolved or unmoved (if (r:α→α)∈Radd,h). Note that T R(h) and Radd,h are disjoint sets. On the Simulations of ECPe Systems with Energy for GPUs 275 6. Filter solutions in Step 5 For each region h, if Listcat26=∅, scan the sorted Listcat2and find out the first object, labelled αcat2,min, falling under Category 2 whose corresponding identity rule application is non-zero, i.e. a0 i,h(αcat2,min →αcat2,min)>0. Since Listcat2is sorted increasingly according to transport energy requirement, the object αcat2,min has the minimum energy required for communication. Let its corresponding energy be labelled energy(αcat2,min). Solutions are filtered in step 5 by adding, for each region hwith a non-empty Listcat2, the inequality below: a0 i,h(e→e)< energy(αcat2,min) (3) 7. Finding ai,h Upon finding values for a0 i,h in all region h, all identity rules r0∈Radd,h are omitted. The values of an application vector ai,h are filled through the equation ai,h(r) = a0 i,h(r), r ∈Rh(4) For every communication rule r∈IR(r, h0)∩IR(r, h00), ai,h0(r) = ai,h00 (r) = a0 i,h00 (r) (5) where region h00 is the sending region of communication rule r. An Illustration We illustrate how we can compute forward in ECPe systems without antiport by using the ECPe system given in Section 2.2. We maintain the total orders ha, #, ei over elements of P O(1), ha, #iover elements of P O(2), hr11, r12, Add11, Add12i over elements of ER(1)∪Radd,1and hr21, r0 21, r0 22, Add21iover elements of ER(2)∪ Radd,2. Thus, our vectors are: Ci−1,1=212Ci−1,2=1 0  Step 1 For region 1, object abelong to Category 1, object # and special object ebelong to Category 2 while no objects belong to Category 3. On the other hand, objects # and ain region 2 belong to Category 1 and Category 3, resp. Step 2 The additional identity rules per region are given below. Radd,1={Add11 : # →#, Add12 :e→e} Radd,2={Add21 :a→a} Since only object # is in category 2, Listcat2for region 1 is composed of only a single element #. 282 R.A.B. Juayong et al. Fig. 3. (a) Common transistor allocation of CPUs and GPUs (b) Computing unit hierarchy of GPUs, from [12]. The first level is highly parallelizable since vector-matrix multiplication and vector addition are highly data independent. Each thread can multiply a vector to one column of the matrix, thus performing ai,h ·MΠ,h. Each thread sums the products then adds these to another vector, performing the addition of Ci−1,h. For the second level, if there are qnumber of ai,h’s and hence qnumber of next configurations, then qblocks will perform Equation (1) qtimes. Because of the physical limitations of current NVIDIA GPUs, no more than 1024 threads per block are allowed for Fermi architecture GPUs so that at most matrices of at most 1024 columns can be simulated in a block. In Fermi GPUs, the maximum number of allowable thread blocks in a grid is 65535 (See Table 1) so q is currently upper bounded by this value. Another simulation consideration, aside from the computing units (threads, thread blocks) is the relatively more limited memory of current GPUs compared to CPUs. In this case, storing all qnumber of application vectors (each of which are of length |R(h)|) and the qnumber of next configurations (each of which are of length |PO(h)|) resulting from those application vectors must fit into the GPU’s global memory. On Generating Object Solutions Given an examined energy solution, we check each object condition where each variable corresponding to a communication rule have already been determined (via On the Simulations of ECPe Systems with Energy for GPUs 283 the examined energy solution) and the value at the right-hand side of a communicated object has already been updated. As can observed, this problem is reduced to an integer partition problem where, given an object equation α1+α2+...+αk=n, we need to find vector containing αi∈N’s, i.e. (α1, α2, ...., αk). To generate solutions for non-energy object equation, we first obtain a lexicographic order of partition for the value n. In [13], given X= (x1, x2, ..., xk0) and Y= (y1, y2, ..., yk00 ), Xprecedes Ylexicographically if and only if for some j≥1, xi≥yiwhen i < j, and xjprecedes yj. As an example, partitions of 5 in lexicographic order are: 11111,2111,311,221,311,32,41,5. Each resulting partition will be padded with zeroes accordingly so that the partition can be represented in a k-dimensional vector. Each partition will be assigned to a thread. Each thread will be responsible for the generation of distinct permutation of the k-dimensional vector representing the partition. The union of solutions generated by each partition corresponds to the set of object solutions for a certain examined object. Since the filtering step of the forward methodology, as explained in Section 2.4, can be done per object condition, this step can also be performed within the current threads. The idea of parallelization in Section 3 may also be used for generating energy solutions of the form c1α1+c2α2+... +ckαk=n, where a lexicographic order on the partitions of nis first accomplished. Again, each resulting partition will then be padded with zeroes accordingly. Upon assigning each partition to a thread, and generating distinct permutation of a partition, each vector representating a permutation can be equated with the vector (c1α1, c2α2, ..., ckαk), afterwhich the corresponding value for the α0 iscan be obtained. 4 Conclusions and future work In this report, we were able to describe a sequential implementation of a forward computing methodology for ECPe systems without antiport rules. We also were able to show how we extend this sequential work to employ GPUs for parallelizing some key areas in the implementation procedures. We were also able to show our proposed ideas for parallelizing other parts of the code. As future work, we would like to implement our proposed ideas for parallelization and test the efficiency of the resulting implementation. Moreover, we hope to improve these ideas to better capitalize the parallelizability of vector-matrix representations of the computations on GPUs. As part of our future works, we also would like to extend the methodology for forward computing to apply to a general ECPe systems where antiport rules are allowed. The difficulty in allowing such communication rules are influenced by the implication that a region can be both a sender and receiver region. Thus, antiport rules need to maintain relationship between adjacent regions at crucial parts of the forward computing methodology. The more tricky part is the action done when considering objects that are unmoved due to antiport rule. The antiport rule increases the number of possible cases dictating why a category 2 object can remain in a certain region. 284 R.A.B. Juayong et al. 5 Acknowledgments R.B. Juayong and F.G.C. Cabarle are partially supported by the DOST-ERDT scholarship program. H. Adorna is funded by the DOST-ERDT research grant and the Alexan professorial chair of the UP Diliman Department of Computer Science, University of the Philippines Diliman. M.A. Mart´ınez–del–Amor is supported by “Proyecto de Excelencia con Investigador de Reconocida Val´ıa” of the “Junta de Andaluc´ıa” under grant P08-TIC04200, and by the project TIN2009–13192 of the “Ministerio de Ciencia e Innovaci´on” of Spain, both co-financed by FEDER funds. References 1. H. Adorna, Gh. P˘aun, M. P´erez-Jim´enez : On Communication Complexity in Evolution-Communication P systems, Romanian Journal of Information Science and Technology, Vol. 13 No. 2 pp. 113-130, 2010 2. F.G.C. Cabarle, H. Adorna, M.A. Mart´ınez-del-Amor: A Spiking Neural P system simulator based on CUDA, M. Gheorghe et al. (Eds.), 12th Int’l Conference on Membrane Computing 2011, revised and selected papers, LNCS vol. 7184, pp. 87103. Springer-Verlag, 2012. 3. F.G.C. Cabarle, H. Adorna, M.A. Mart´ınez-del-Amor, M.J. P´erez-Jim´enez: Improving GPU Simulations of Spiking Neural P Systems, (to appear) Romanian Journal of Information Science and Technology, 2012. 4. R.A. Juayong, H. Adorna: Computing on Evolution-Communication P systems with Energy Using Symport Only, Workshop on Computation: Theory and Practice 2011 (WCTP 2011), UP Diliman NISMED auditorium. 5. X. Zeng, H. Adorna, M. A. Mart´ınez-del-Amor, L. Pan, M. P´erez-Jim´enez : Matrix Representation of Spiking Neural P Systems, Membrane Computing: Lecture Notes in Computer Science, Volume 6501/2011, 377-391, 2011 6. R.A. Juayong, H. Adorna: A Matrix Representation for Computations in Evolution-Communication P Systems with Energy, Proc. of Philippine Computing Science Congress, Naga, Camarines Sur, Philippines, March 3-4, 2011 7. Kirk D., Hwu W., Programming Massively Parallel Processors: A Hands On Approach, 1st ed. MA, USA, Morgan Kaufmann, 2010. 8. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez: Computing Backwards with P systems, W MC10, Curtea de Arge¸s, Romania, (2009), 282-295. 9. Gh. P˘aun: Introduction to Membrane Computing. In: Gabriel Ciobanu, Mario J. P´erez-Jim´enez and Gheorghe P˘aun, eds: Applications of Membrane Computing, Natural Computing Series. Springer, pp.142. (2006) 10. M. Cavaliere: Evolution-communication P systems. Membrane Computing. Proc. WMC 2002, Curtea de Arge¸s (Gh. P˘aun et al., eds.), LNCS 2597, Springer, Berlin, 134-145. (2003) 11. A. P˘aun, Gh. P˘aun: The power of communication: P systems with symport/antiport. New Generation Computing, 20, 3, 295-306, (2002) 12. NVIDIA corporation,“NVIDIA CUDA C programming guide”, version 3.2, CA, USA, 2010. 13. A. Zoghbi, I. Stojmenovi´c: Fast algorithms for generating integer partitions, International Journal of Computer Mathematics, Vol. 70, No. 2., pp. 319-332, (1998) On the Simulations of ECPe Systems with Energy for GPUs 285 Appendix A: On File Formats for Implementation of ECPe system in C Fig. 4. Format for file trans file.txt for the sequential implementation of ECPe system in C. Shown in Figure 4 above is the format for input file trans file.txt. This file contains the information required to find a succeeding configuration given a current one. First, the number of regions must be specified. If there will be a case where the environment will be needed during the computation, the value of this parameter must be the number of membranes incremented by one in order to account for the environment. The membrane structure is represented by paired square brackets as typical representation of a membrane structure. Note that for either a closed or open square bracket, the symbol must be followed by a numeral to indicate the label of the membrane. For the initial configuration, there is a need to follow a total order as discussed in Section 2.3. Therefore, the initial configuration is simply a initial configuration vector where each cell contains the number of copies of a certain object at the start of the computation. The separator for the cells will be the space symbol. The expected transition matrix has dimensions following the previously specified number of rules involving a specific region and the number of possible objects that may enter the region. The rows will be separated by newline, whereas, the columns are separated by spaces. A rule type can either be an evolution rule in 286 R.A.B. Juayong et al. which case the symbol to type will be ’e’, whereas a communication rule can have one of symbol ’s’ and ’r’. The symbol ’s’ represents that the communication rule uses the specific region as a sender, while the symbol ’r’ uses the specific region as a receiver. Fig. 5. Format for file forwComp file.txt for the sequential implementation of ECPe system in C. Figure 5, on the other hand, illustrates the format for the input file forwComp file.txt. This file contains the information required to find all valid application vectors from a given configuration vector. First, a trigger matrix needs to be indicated. Again, there is a need to impose a total order over the rules. In this case, there will be a specific setup for the rules in the trigger matrix wherein, it is required that evolution rules must be specified first before the communication rules. After the existing rules associated with the region, the identity rule for energy (e) should proceed after. The identity rules for the other category 2 objects will follow after the energy’s identity rule. After indicating the trigger matrix, there is a need to define the range of the communication rules in the specified region. To indicate this: On the Simulations of ECPe Systems with Energy for GPUs 287 Fig. 6. Input files for the example given in Section 2.2 <position of starting communication rule>-<position of last communication rule> where the positions will be based on the imposed total order. The total order will also be used in the next set of input which entails specifying the minimal energy requirement needed to transport each category 2 object. Since they only be enumerated in a single line, the separator of energy per object will be the space symbol. Following after this will be the enumeration of the details needed in the receiving region for each communication rule. To indicate this: <position of receiving region> <position of partner rule in receiving region> where this specifications per communication rule will be separated by newlines. Note that only a single space symbol separates the position of the receiving region with the position of the corresponding rule in the receiving region. In case no communication rules exist in the trigger matrix, there is no need to fill up this part. Moreover, the range of communication rules will be 0-0 and the value of the succeeding line will be 0. Shown in Figure 6 are the input files for the example given in Section 2.2 whose total order for involved rules and possible objects follows the order given in Section 2.3 except that we swap the position of the last and second 288 R.A.B. Juayong et al. Fig. 7. Sample output files for the example given in Section 2.2 On the Simulations of ECPe Systems with Energy for GPUs 289 to the last identity rule in the first region to follow the required format for total order on rules involved in the corresponding trigger matrix. For the output, there will be two files, namely conf.txt and conf index.txt, that shall represent an ECPe systems configuration tree of computations. The former consists a list of configurations (not yet necesarily unique) where each system configuration is separated by a newline. The system configuration is composed of configuration vectors local to each region that are juxtaposed together. The elements of the vectors are separated by an individual space whereas dollar sign ($) separates each local configurations. The initial configuration will be the first configuration in the file. The output file conf index.txt stores the indices of the configurations in file conf.txt in order to remember the association between configurations. Given an index in this file, the configuration associated with the index is the configuration in conf.txt which has the same line position as the line of the index. For example, the initial configuration is located at the first line in the file conf.txt, its corresponding first line in conf index.txt is the index 1. Since we can represent computation as a tree, the initial configuration with index 1 is the root node configuration of the tree. To determine the configurations that sprung from the initial configuration i.e. the children of the root node, the indices must have the prefix ’1 ’. The parent configuration which generates a configuration can be tracked by removing the last underscore in the index associated with the configuration, along with the number that appears after the said underscore. A path from the initial configuration to any configuration Ccan be traced by retrieving the associated configuration starting from index 1 (which, as mentioned, represents the initial configuration) to the configuration Cfollowing the precedence imposed by the indices. Shown in Figure 7 are the output files for the example given in Section 2.2 whose total order for objects follows the order given in Section 2.3 and where the maximum number of configurations to examine is set to 10.