A New Methodology for Software-Simulation of Membrane Systems Using a Multi-Thread Programming Model

Graphical Abstract A new methodology for software-simulation of membrane systems using a multi-thread programming model Daniel Cascado-Caballero, Fernando Diaz-del-Rio, Daniel Cagigas-Mu˜niz, David Orellana-Mart´ın, Ignacio P´erez-Hurtado This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed Highlights A new methodology for software-simulation of membrane systems using a multi-thread programming model Daniel Cascado-Caballero, Fernando Diaz-del-Rio, Daniel Cagigas-Mu˜niz, David Orellana-Mart´ın, Ignacio P´erez-Hurtado •A new generic methodology for membrane simulation is presented, which takes advantage of the current processor parallelism, thus enhancing those software computational frameworks that rely on sequential algorithms, are problem-specific or are not scalable enough to implement large P systems. •Our simulation methodology can implement generic P systems and can be used for other types of discrete-time simulation. •Examples of P systems have been simulated and their performance improvements have been obtained, according to the number of threads used in the simulation. This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed A new methodology for software-simulation of membrane systems using a multi-thread programming model Daniel Cascado-Caballeroa,∗, Fernando Diaz-del-Rioa, Daniel Cagigas-Mu˜niza, David Orellana-Mart´ınb, Ignacio P´erez-Hurtadob aDepartment of Computer Architecture and Technology, Universidad de Sevilla, Seville, Spain bResearch Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Seville, Spain Abstract The evolution of simulation and implementation of P systems has been intense since the theoretical model of computation was created. In the field of software simulation of P systems, the proposals made so far have taken advantage mainly of the parallelism of GPUs, but not of the parallelism of existing multi-core processors. This paper proposes a methodology for simulating P systems using a multi-threaded methodological approach in a multi-core processor. This proposal has been implemented and tested using a simulator programmed in C#, and its correct operation has been tested for confluent and non-confluent systems. The experimental results confirm that the simulator scales well with the number of hardware threads of a multiprocessor. The results obtained suggest that the methodology is valid and that it is worth testing it with more complex systems to find the limits of the methodology. Keywords: Unconventional computing, parallelism, multi-threading, membrane computing, P systems ∗Corresponding author Email addresses: [email protected] (Daniel Cascado-Caballero), [email protected] (Fernando Diaz-del-Rio), [email protected] (Daniel Cagigas-Mu˜niz), [email protected] (David Orellana-Mart´ın), [email protected] (Ignacio P´erez-Hurtado) Preprint submitted to Simulation Modelling Practice and Theory January 24, 2024 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed 1. Introduction Since the conception of the membrane computing paradigm in 1998 [1], simulation has been conceived as a way to assist in the design and to verify the operation and usefulness of these models of computation. This computing paradigm is based on the imitation of cellular chemical processes and on the existence of membranes that delimit the scope of action of these chemical processes. Thus, each membrane processes the chemical elements in its environment to stay alive, containing a set of rewriting rules by which it achieves the goal of staying alive. By default, there is no established order to execute the membrane rules since the chemical elements associate and react nondeterministically as they appear in the membrane. However, a membrane system (hereafter P system) can be designed so that, given a set of elements, there is only one set of rules to be executed at any given time. Likewise, this type of system can be confluent (always arriving at the same solution if starting from the same set of initial elements) or non-confluent (each time it is executed, the system generates a possible solution from a set of solutions), regardless of whether the rules are executed randomly or in a given order. This view of the membrane as a set of rules to be executed can be used to view each membrane as a program running on a processor, and thus parallel processing could easily be thought of if several membranes coexist in the system to be described. This could be called coarse-grained parallelism. Although many of the implementations of P system simulators have avoided parallelism by running on a single processor, there are some implementations using Message Passing Interface (MPI) [2][3]. They have attempted to exploit multiprocessing to increase performance in what could be considered coarsegrained parallelism. However, one could also think of fine-grained parallelism. Chemical elements can then be seen as independent units of computation (threads) that join others to form new ones according to the set of rules in which each element may be involved. Several different classes of membrane systems have been introduced since its conception. The three most studied types are cell-like P systems [1], whose structure is a tree-like graph, tissue-like P systems [4], whose directed graph structure is intrinsically defined by their rules, and neural-like P systems [5], which resemble the functioning of neurons in the human brain. In addition to these membrane systems, other types have been well studied in the literature, such as PDP systems [6], widely used for modeling purposes, P colonies [7], recreating an environment where agents interact with each other and with 2 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed the environment, and dP systems [8], having the ability to solve problems in a distributed way, among others. This paper presents a methodology for the implementation of a P system simulator with fine-grained massive parallelism, making use of the multiprocessing characteristics of current processors, capable of executing several threads at the same time and being able to make efficient use of it by sharing memory among the threads. Multiprocessing is possible in today’s processors because within each processor there are code execution units that allow different programs to be executed in parallel. The programmer or operating system manages the execution of these programs (or threads), deciding when and on which processor they are executed. The programmer has to establish in a clear way how the different threads are synchronized to produce a coherent result and also has to establish the appropriate synchronization objects, such as semaphores, barriers, or locks, to prevent the same data from being accessed by more than one thread at a time. The proposal of this paper is about how to deploy the abstract entities of a P system model into threads and synchronization objects to ensure the correct execution of the P system. The goal in developing this proposal is not only to take advantage of multitasking in current computation systems, but to make P system emulation advantageous in cases where size or design requires large amounts of computational or storage resources. Therefore, we hope that this is a first approach to scalable P system execution. For the reasons mentioned above, we consider that the methodology for implementing a multi-threaded simulator for P systems is a task worth describing and sharing with the scientific community. In this study, we give a description of this methodology and show the results on several P systems obtained with a multi-threaded implementation framework. The article is organized as follows. Section 2 shows related work, Section 3 gives a simple description of the P systems discussed in this paper, Section 4 describes the implementation methodology for multi-threaded P system simulators, Section 5 shows the results obtained from an implementation of the above methodology, Section 6 analyses these results, Section 7 shows future work and Section 8, conclusions. 2. Related work The theoretical development of membrane computing models has been very intense since the beginning of the first model. However, the simulation 3 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed of membrane computing models has not always evolved in the same way. In [9] there is a complete summary of all hardware emulations/implementations of membrane systems. These systems are classified into three main types: simulations on Field-Programmable Gate Arrays (FPGAs) [10, 11], custom hardware [12], and simulations using Graphics Processing Units (GPUs) [13, 14, 15]. The latter can be considered a hybrid hardware/software approach, as the model is programmed in software but simulated on specialized hardware to achieve higher acceleration and performance. These hardware simulators have limitations in terms of the types of P system they can simulate, scalability, and, partly, also ease of use by non-experts. In this sense, software simulators offer more flexibility. From the point of view of software simulations or simulations, implementations have been made since the early beginnings of membrane computing. For example, in [2] a simulation is performed using a cluster of computers. This implementation, although innovative, is costly to deploy in terms of hardware resources and does not take advantage of the potential of current multiprocessors. The P-Lingua programming language [16] designed for programming and modeling P systems also provides a simulator implemented in C++. However, this simulator is sequential (using a single multiprocessor core) and has dependencies on Linux operating system libraries that limit its portability. Previously, P-Lingua was included in the MeCoSim framework [17]. This simulator, which is a standard in the research community on membrane computing, is intended to serve as a universal simulation tool for membrane computing. It is implemented in Java (which facilitates its portability) and also provides a graphical and user-friendly interface. Along the same lines and more recently, the UPSimulator simulator has been developed. This software allows for the simulation of additional P systems, such as tissue-like P systems and neural-like P systems [18]. Like P-Lingua, this simulator offers its own P systems modeling language called UPLanguage. This simulator is also programmed in Java and provides a graphical interface. The main objective of all these software simulators is to assist in the design and verification of P systems. These simulators always apply fixed algorithms for the random allocation of elements (from a multiset) between the different rules of a P system. Being a sequential allocation, this type of sequential simulation departs from the intrinsically parallel philosophy of membrane computing. Performance or efficiency aspects of current multiprocessors are also not considered. These aspects are generally neglected or 4 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed dealt with in hardware implementations. Finally, in recent years, there has also been a growing interest in certain types of P systems such as Spiking Neural P systems. Simulators of this type of P systems are specified in [19], [20] and [21]. However, such simulators cannot be applied to any P system. Their application is oriented towards solving a certain type of problem. It is therefore necessary to continue researching into new types of simulator implementations or generalist P system simulators in order to: 1. Take advantage of the parallelism of modern multiprocessors to achieve a simulation closer to the membrane computing paradigm. 2. Achieve maximum use of the hardware resources of multiprocessors. 3. Facilitate their portability with the aim of studying their possible application in embedded and/or mobile systems. 3. P systems at a glance In this section, some basic concepts about P systems will be introduced. For a formal description of transition P systems, we refer the reader to [1]. For a comprehensive introduction to formal languages and membrane systems, we refer the reader to [22, 23]. Transition P systems are the first type of P systems introduced in the framework of Membrane Computing [1], inspired by the internal structure of living cells and the chemical reactions that occur within them. A transition P system can be seen as a set of membranes organized in a rooted-tree graph, where each labeled node represents a membrane, the relationship between the parent and child membranes is described naturally, and where the environment is the parent region of the outermost membrane (called the skin membrane). We use the term region or zone ito generally speak about the membrane iif it is the label of a membrane, and for the environment if i= 0. Each membrane will contain an initial multiset of objects that will evolve through the application of rewriting rules. Each rewriting rule of the form r≡[u→v]hcan be applied if there exists a multiset of objects u(usually called the left-hand side of the rule) in the region hat a certain moment. If such a rule is applied, then the multiset uwill be removed from that membrane, and the multiset of objects v(usually called the right-hand side of the rule) will be created within that membrane. Certain rules can have 5 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed priorities over other rules, creating the next additional restriction to the applicability of the rules. Let r1and r2be applicable rules in a certain membrane. If r1has priority over r2, then r2will not be applicable on such a membrane while r1is applicable. If two rules are applicable and they compete for any object, then the applied rule will be selected in a non-deterministic manner. In transition P systems, the multiset of applied rules in a computational step will be maximal; that is, after removing all objects from the left-hand side of the applied rules, there cannot exist a multiset of objects uthat fires a rule r. Otherwise, the rule rmust be applied. 4. Implementing multi-threaded simulators of P systems In this section, we will explain the basic principles of the implementation of the simulator, focusing on the description of the model and the way it works, to make it easier to understand what difficulties appear when implementing it in a multi-threaded platform. 4.1. Execution threads as a cornerstone As stated in the previous section, software-based P system simulations do not take advantage of multiprocessing capabilities of nowadays microprocessors. In this paper, we focus our attention on these capabilities to create a methodology to simulate P systems. ”A thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system” [24]. One thread is part of a process, an instance of a program that is executed by the operating system. A process shares with its threads all the resources (memory, handlers, instructions, etc.), being necessary to synchronize the access to common resources to ensure the correct management of them by the set of threads. In a multiprocessor machine, there are as many hardware threads of execution as parallel processing units or processors. These hardware threads are used by the operating system to implement software threads, which are managed by the operating system. Distinguishing between these two types of threads is fundamental, since only instructions executed on different hardware threads are truly executed in parallel. If several software threads want to be executed on the same hardware thread, they will be scheduled in a certain order by the operating system. 6 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed The way we think of applying multiprocessing to P systems is to distribute the P system rules in several workerthreads coordinated by a mainthread, which determines when the computational step that determines the production of new objects, the dissolution of the membrane, its mitosis, etc. occurs. All threads are contained in a process that instantiates a program (in our case, the simulator of the P system). In this regard, several methodologies arise to assign threads to the components of a P system model. One of them is to assign a thread to each rule of the P system, so that there would be at least as many threads as rules. Another possibility is to assign a thread to each P system object so that this thread is in charge of executing all the rules that allow this object to combine with others. Since this last methodology seems to be more in line with the philosophy of P systems, we are going to adopt it as a working assumption of this paper. We will comment on its advantages and disadvantages later on. In the following subsections, the entities needed to implement a complete P system under this operating principle will be defined. Let us start with the definition of an object. 4.2. Operating principle To explain the operating principle of the simulator, one can imagine a membrane with different molecules interacting with each other to create new ones. Each molecule has the ability to combine (or react) with others attending to certain rules specified by the designer of the P system. Let a, f →e and c, d →bbe the rules. Then, molecules aand fcan react with each other to create a new molecule e; also the reaction between molecules cand dwill create b. If there were an additional rule like a, m →x, the molecule acould react with for with m, but only one at a time. If there were no probability rates, awould have the same probability of reacting with one or the other, and there would be no way to determine which of the two molecules (for m) will react with a. Figure 1 describes the scenario in which the last rule is not applied because ahas reacted with f. Furthermore, the figure shows how reactions are defined for P systems: reactions do not occur continuously in time, but there are certain time barriers, called computational steps, where new molecules are produced and the new state of the P system is generated. From this point of view, a P system is a massively combinatorial system, where reactions occur probabilistically, depending on the rules that make each molecule react with others. Each molecule behaves according to the 7 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed •A state machine (see Figure 2) to implement the evolution of the rule state (see Subsection 4.4.1). Figure 2: State machine for a computation step to implement rule priorities. At the beginning of a computation step all rules start in the Active state. Only Executed and Active states allow rule execution. A simple example can clarify this. Let r1, r2, r3 be three rules that obey a unique partial priority scheme described as a priority chain:r1> r2> r3. This means that r1 does not have ancestors, r2 has r1, as its only ancestor, and r3 has r2 and r1 as ancestors. Let us suppose that all rules have enough objects to be executed only once, and that none rule execution result would produce objects that enable the execution of any other rule. At the beginning of one computation step, all rules are in active state. All worker threads must follow the state machine shown in Figure 2 when processing any rule. In the first computation step, r1 can be executed because it has no ancestors and has enough LH objects according to the previous hypothesis: then it passes to the state Executed. When executed, it consumes all objects and finishes its evolution by passing to the state Disabled. In parallel, rule r2 tries to execute, but since it depends on r1, whose state is Disabled or Executed, the state of r2 must become Waiting. Thus, r2 cannot be executed. The same circumstance applies to r3, which depends on the state of r2. Thus, in this computation step, only r1 is executed. Rule states are reset to the Active state at the end of the first computation step. In the second computation step, r1 cannot be executed because it had consumed all objects (by hypothesis) in the previous computation step, 14 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed so its state becomes Cancelled. Being the state of the only ancestor of r2 as Cancelled, it can now run. Then r2 passes to the Executed state and, afterwards, it consumes all its LH objects and ends in Disabled. As previously, r3 stays in Waiting state. If r2 reads the state of r1 before it changes to Cancelled, the state of r2 will remain as Active, because r2 has an Active ancestor. r2 will wait in the active state until it reads the new state of r! (Cancelled). In the third computation step, neither r1 nor r2 can be executed, and they go to canceled, granting permission for r3 to be executed for the first time. Finally, r3 is executed and passes to the Disabled state. Through this mechanism of priority chains, any generic rule priority scheme can be implemented. In our current multi-threaded simulator implementation, it is the user’s responsibility to prevent a set of rules from forming a cycle that may result in a deadlock (that is, a first rule has another as an ancestor, which, in turn, contains the first as an ancestor). 4.5. Worker threads On its own, a rule cannot be executed independently; rather, a rule serves as a guide to what an object can do when it is associated with others. If objects are considered living entities, each of them must possess a list of rules to determine which rules it should attempt to execute through associations with other objects. The act of observing and attempting to execute this list of rules bestows upon it the status of an active entity within the P system. The means of implementing the living condition of each object in a P system is through the association of a Worker thread. The worker thread contains a list of rules in which its associated object is on the left-hand side of every rule within the list. In this manner, the primary purpose of a working thread associated with an object is to execute all the rules contained in its list until each of them becomes non-executable. As shown in Algorithm 2, the working thread randomly selects one of its rules for execution. This selection relies on the presence of a random number generator, which is responsible for choosing a rule from the assigned list of rules for the thread. To ensure the randomness of the results, each thread is equipped with a unique random number generator. 4.6. Membrane The membrane serves as a container for objects, threads, and rules. Its primary responsibility is to coordinate the execution threads to ensure an 15 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed Algorithm 2: Execution loop for a working thread associated to object Obj Data: List of rules associated with object , Obj while membrane has not ordered finishing the thread do Wait for membrane’s barrier; repeat R←select a rule randomly from the list of rules; Check if Rcan be executed; if Ris executable then Prob ←random number between 0 and 100; Call Algorithm 1 to execute rule Rwith probability Prob; end until all the rules are not executable; Wait for membrane’s barrier; end orderly execution of the computation step. The computation step to be implemented by a membrane comprises three phases: a rule evolution phase, an element production phase, and, if necessary, a membrane dissolution control phase. Additionally, the membrane is tasked with initializing objects, threads, and rules, and constructing the P system in accordance with the designer’s specifications. Finally, the membrane must facilitate the monitoring of its status, startup, and shutdown. The fundamental attributes of the membrane are described below. •Identifier or name •Polarity of the membrane. •Permeability of the membrane. •List of objects contained in the membrane. •List of rules operated by objects contained in the membrane. •List of working threads associated with the objects contained in the membrane. •Main thread for synchronizing the operations of computation steps. 16 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed The first three attributes are utilized to facilitate the operations of object searching, importing, and exporting. Using these attributes, a rule can search for an object originating from a membrane with a specified identifier and polarity, managing to locate it or generate new objects within, depending on the permeability of the membrane where the object is situated. The subsequent lists are used to store objects, rules, and threads and are established through the membrane initialization process. During this process, the designer is required to follow the following steps: •Register the objects contained in the membrane and their initial multiplicities. •Register the rules that affect the above mentioned objects and their priority schemes (by creating the lists of predecessors of each rule). Each rule builds its list of elements from its left and right sides, yet associating them to the objects with which it operates (this is done by the execution of the rule). •Initialize the membrane. The initiation of the membrane involves filling the lists with objects and rules. Following this population, worker threads associated with the objects on the left side of the rules are created. A unique thread is designated for each object. For every thread, a list of applicable rules is constructed. Those rules have the reference object on the left side. This method of allocating threads to objects has significant implications for simulation performance, as will be elucidated in Section 5 Subsequently to these steps, the membrane registers its primary thread and synchronizes it with the worker threads. This synchronization ensures a coordinated execution of the computation step. The systematic approach aims to optimize the execution process and maintain consistency between computational operations. 4.6.1. Synchronization between the main and the worker threads Synchronization between the main thread and the worker threads is achieved through an execution barrier, with which both the main thread and the worker threads are associated. This arrangement necessitates that all threads wait until they concurrently reach this barrier. Consequently, the algorithm executed by the main thread is structured as follows: 17 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed Algorithm 3: Execution loop for a membrane’s main thread. Simplified version for unique membrane P systems while Not finish do Reactive all rules of the membrane; Wait at the barrier in common with the working threads; Resolve queued objects; Resolve dissolution; if Dissolution take place then finish ←true; end end As illustrated in Algorithm 3, there are two synchronization points that align with the two waits in Algorithm 2. Consequently, when the main thread reaches its first wait, the worker threads arrive at a corresponding juncture, initiating what is known as the evolution phase, during which they execute their rules. Simultaneously, the main thread proceeds to its next wait. The worker threads continue until no further rules are executable, at which point they arrive at the second synchronization point, where the main thread awaits them. Subsequently, the worker threads enter a holding pattern at the first wait, while the main thread performs the later stages of the computation step process. Therefore, the interval between the two waits in the main thread is utilized by the worker threads to execute the rule evolution phase. Figure 3 depicts the temporal progression between a worker thread and the main thread. In Figure 3, following the evolution phase, the process of resolving the queued objects takes place, transforming them into active objects (by adding their queued multiplicity to their active multiplicity). This phase also involves the resolution of the active multiplicities of special objects, such as those determining membrane permeability, dissolution, and polarity. Only after these resolutions are completed can the state of the membrane’s permeability and polarity, as well as the necessity for membrane dissolution, be evaluated for the subsequent computational step. The specifics of membrane dissolution will be addressed in a later section. 18 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed Figure 3: Time evolution of a working thread and a main thread. 4.6.2. Implementing multi-membrane P systems In order to be able to build multi-membrane P systems, the followings attributes must be added to the membrane: •ID or TAG. •Reference to the parent membrane. •List references to children’s membranes. •Synchronization barrier for membranes. The TAG attribute is utilized so that the rules can identify the membrane by its identifier, as elucidated in Section 4.4. References to parent and child membranes serve a similar purpose, granting rules the capability to examine adjacent membranes for objects. The synchronization barrier plays a critical role in synchronizing the various phases of each membrane’s main thread. Consequently, barriers must be strategically interspersed among the different phases of the main thread, as demonstrated in Algorithm 4. This ensures 19 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed that all evolution phases of the membranes are completed concurrently, followed by the resolution of queued objects. Additionally, monitoring events are initiated to allow the user to scrutinize the system’s status or halt its operation if necessary. Three distinct monitoring events can be registered with the main membrane of the P system during its initialization: the computation step event, the end-of-computation event, and the dissolution event. Each of these events is triggered on the basis of specific conditions that pertain to the main membrane. The Computation Step event is activated consistently at every computation step. The End of Computation event occurs when no rules are executed during the current computation step, which is determined when the queued multiplicities of all objects equal zero. Lastly, the dissolution event is triggered when the membrane is on the verge of dissolution. Algorithm 4: Execution loop for a membrane’s main thread. Complete version for multi-membrane P systems while Not finish do Reactive all rules of the membrane; Wait at the barrier in common with the working threads; Wait at the barrier in common with the working threads; Wait for Multi-membrane barrier; Resolve queued objects; Wait for Multi-membrane barrier; Trigger the monitoring events; Resolve dissolution; if Dissolution take place then finish ←true; end end The dissolution of the membrane is contingent on the multiplicity of the special dissolution object (if its multiplicity is greater than zero, the membrane must dissolve) and the membrane’s permeability, which in turn is influenced by the special object of permeability. Given that dissolution is dependent on the active values of these objects, it must be evaluated at the end of the queued object resolution phase. Consequently, each membrane within a P system determines whether it needs to dissolve, after which the 20 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed dissolution processes are executed. Membrane dissolution entails the transfer of its non-dissolving children and all of its objects, excluding special objects, with an active multiplicity greater than zero, to its parent membrane. Considering that the parent membrane may also undergo dissolution, the appropriate recipient for this transfer is identified as the first ancestor in the lineage chain that opts not to dissolve. 4.7. Starting the P system To initiate a P system in this simulation, it is necessary to first delineate all membranes that will be initially active and define their interrelationships. Subsequently, non-special objects with a multiplicity greater than zero, along with the rules, must be specified. Following the definition of rules and objects, the worker threads are established. These threads achieve synchronization with their respective membrane’s main thread by subscribing to its synchronization barrier. All main threads of the membranes register with the intermembrane synchronization barrier, which is affiliated with the main membrane of the P system. Additionally, the user program may register for the membrane monitoring event and implement a corresponding code routine. When all the threads of the P system are prepared, the system initiates them recursively: the main membrane activates its threads and then triggers the start of its children’s threads. With these steps completed, the system becomes operational. The user has the capability to monitor the system or halt it by enforcing termination through the activation of the ’end’ attribute of the main membrane. 5. Experimenting and comparative In this section, the methodology will be evaluated using two very different P systems already defined in [11]: a confluent and a non-confluent system. The P system described in Algorithm 5 generates the first NFibonacci numbers and will be used to check if the methodology can correctly simulate a confluent P system correctly composed by one membrane. The working alphabet is ai: 1 ≤i≤N,ai,0: 1 ≤i≤N+ 1 and ai,1: 2 ≤i≤N+ 2. In total, 3N+ 3 different objects, if we count the object λ.The system halts when there are no rules that can be selected for execution. This happens exactly after the N+ 1 steps of the computation. When the system stops, the output of the system is given by the multiplicities 21 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed of objects ai: 1 ≤i≤N, and such multiplicities represent the first N Fibonacci numbers, i.e., a1= 1, a2= 1, a3= 2, a4= 3, a5= 5, etc. Objects ai,0: 1 ≤i≤N+ 1 and ai,1: 2 ≤i≤N+ 2 are used for intermediate computations in non-final configuration steps. There are four pattern of rules as enumerated in the P system described in Algorithm 5. The rule patterns r1and r2produce the Fibonacci numbers. The rule patterns r3and r4are used to erase residual objects aN+1,1and aN+2,0in the final configuration. In this particular system, a thread is generated for each object ai,0and ai,1, totaling 2N+2 threads. Each thread solely focuses on observing a single rule. Furthermore, an extra thread is created to serve as the main thread for the membrane. Since each rule requires only one object to be activated and no two rules share the same object on the left side, there is no competition for objects. Consequently, there is no element of randomness, and the rules can only be triggered in one specific manner. Algorithm 5: P system definition for a Fibonacci series generator. Initial membrane structure: []1; Initial multiset for membrane labeled 1: a1,1, a2,0; r1≡[ai,1→ai, ai+2,0]1: 1 ≤i≤N; r2≡[ai+1,0→ai+1,1, ai+2,0]1: 1 ≤i≤N; r3≡[aN+1,1→λ]1; r4≡[aN+2,0→λ]1; Algorithm 6 presents the P system, which generates a random nondirected graph (also known as a random graph generator, or RNDG) with N nodes using a non-deterministic approach (i.e., it is non-confluent). The purpose of this system is to test the implementation of a non-confluent P system by ensuring that all possible outcomes (i.e., all nondirected graphs) can be reached. The working alphabet is ai: 1 ≤i≤N,e∗ i,j :i<j≤N, 1≤i≤Nand ei,j :i < j ≤N, 1≤i≤n. Objects ai: 1 ≤i≤Nrepresent nodes in the graph. The objects ei,j :i<j≤N, 1≤i≤Nrepresent the edges in the graph. Objects e∗ i,j :i<j≤N, 1≤i≤Nare used for intermediate calculus and represent all possible edges in the graph. The system halts when there are no rules that can be selected for execution. There are two patterns of rules r1and r2competing for the same objects ai, aj, e∗ i,j :i<j≤N, 1≤i≤N. For each combination, only one rule pat- 22 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed tern (r1or r2) is selected in a non-deterministic manner. Both rule patterns consume the corresponding possible edge e∗ i,j, but only the first rule pattern produces an edge ei,j in the graph. Thus, in the final configuration there would not be objects e∗ i,j and there would be an arbitrary set of objects ei,j. In this case (N2−N)/2+N+1 threads will be created, one thread for each object ai: 1 ≤i≤N, and one for each object e∗ i,j :i<j≤N, 1≤i≤N, and one more thread as the main thread of the membrane. Threads belonging to aiobjects observe 2(N−1) rules, half of the pattern r1and the other half of the pattern r2. The thread associated with objects e∗ i,j is subject to observing only two rules, one for each pattern. In this scenario, these rules must contend with others to gather three objects each. The outcome of these competitions is contingent on the order of execution of the object thread and the random-rule selection process within the thread. Consequently, the final configuration of this P-system varies with each simulation iteration. Additionally, the number of computation steps needed to yield a solution depends on the sequence in which rules are executed and whether they contend for objects already claimed by other rules. This competition may result in rules being blocked from execution in the active computation step, forcing them to attempt execution again in the subsequent step. Algorithm 6: P system definition for a Random Graph Generator (RNDG). Initial membrane structure: []1 Initial multiset for membrane labeled 1: ai: 1 ≤i≤N e∗ i,j :i<j≤N, 1≤i≤N r1≡[ai, aj, e∗ i,j →ai, aj, ei,j]1:i<j≤N, 1≤i≤N; r2≡[ai, aj, e∗ i,j →ai, aj]1:i<j≤N, 1≤i≤N; In order to obtain results, a C# implementation of the methodology was developed to create a simulator for P systems. The simulator is a CLI (Command Line Interface) program that enables users to choose the P system to be simulated, its parameters, and various options for defining the simulator’s output. It also allows for basic interaction, such as obtaining the system’s status at any given moment by pressing a key or forcibly stopping the simulation. As mentioned in Section 2, the selection order of rules for each thread must be different to ensure randomness, as each thread has a unique 23 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed Figure 6: Average execution times (in seconds) vs # threads for the manual mode. to multi-membrane systems, provided the number of membranes remains consistent throughout the simulation. Investigating the behavior and performance of simulations in such multi-membrane P systems would be a valuable direction for future research. Upon verifying the accurate functioning of multi-membrane simulations, it becomes crucial to augment the methodology with necessary features for simulating systems that display a dynamic count of membranes. This enhancement requires the integration of operations such as cloning, mitosis, and membrane division. Broadening the scope of the methodology to include these elements is essential to evaluate its effectiveness in simulating systems characterized by exponential membrane growth, as illustrated in the case of the zebra mussel simulation model [25]. The next objective involves attaining optimal simulation performance coupled with code portability across various hardware types, including embedded systems. The initial prototype of the proposed model, developed using the C# language and the .NET platform, is inherently aligned with the Windows operating system (although Mono is a compatible framework in the Linux operating system). This alignment may inherently restrict the portability and efficiency of current implementation on various hardware and 30 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed software platforms. An alternative approach entails porting the implementation of the proposed model to the C/C++ language, utilizing the standard POSIX threading library. The C programming language is demonstrably faster than C# in a majority of instances, as evidenced by [26]. This efficiency extends to energy consumption, with C / C++ also shows the potential to utilize less than half of the memory resources of a computer compared to C#. However, a significant drawback of employing C/C++ language and POSIX threads lies in their increased complexity. In reference [27], a preliminary prototype is presented detailing the implementation of a transition P system utilizing C and POSIX threads. This implementation will serve as a foundational framework for subsequent developments. In fact, transition P systems are generally characterized by the absence of probabilistic elements in their formulation. Nevertheless, the integration of these elements into the simulator presents opportunities for future experiments with Population Dynamics P (PDP) systems. Simulations of this nature are typically resource-intensive, rendering the simulator an instrumental tool for evaluating its efficacy in managing complex scenarios that incorporate probabilistic components. In summary, future endeavors can be delineated into three distinct phases. First, the model outlined in this study will be ported to the C/C++ programming language and POSIX threads. Second, performance evaluations will be conducted in both high-performance computing (HPC) and embedded systems. Third, the results of these evaluations will be juxtaposed with the performance metrics of P system simulations executed on GPUs, as detailed in [28]. 8. Conclusions This paper meticulously outlines a methodology for implementing simulators of single-membrane transition P systems, leveraging the parallelism inherent in contemporary processors. To evaluate the efficacy of this methodology, a simulator has been developed that is capable of performing simulations of a P-system. This simulator is equipped to display both the results of the simulated P system and the key performance statistics. Employing this simulation interface, a series of execution batches have been conducted to assess the proper functioning and performance of two systems: one confluent and the other non-confluent. The use of the confluent 31 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed system facilitated the verification of accurate execution in a P system that yields deterministic outcomes. Similarly, the application of the non-confluent system enabled the confirmation that the simulation can encompass all feasible results. In terms of harnessing parallelism in the simulation, simulations of nonconfluent P systems have conclusively demonstrated that parallel processing can be effectively utilized to decrease execution time. However, this benefit depends on the precise calibration of the maximum number of execution threads to match the number of physical processors in the system that execute the simulation. Notably, as the number of execution threads is determined by the count of P-system objects, the implementation of an excessive number of threads (surpassing the processor count) might result in performance reduction due to the concurrent utilization of processors by multiple hardware threads. Consequently, the aforementioned results suggest that this simulation methodology could be particularly beneficial for large P systems, especially in environments where a significant number of processors are available. Acknowledgments This work is part of the project SANEVEC TED2021-130825B-I00, funded by the Ministerio de Ciencia e Innovaci´on (MCIN), Agencia Estatal de Investigaci´on (AEI) of Spain, MCIN/AEI/10.13039/501100011033, and by the European Union NextGenerationEU/PRTR. D. Orellana-Mart´ın acknowledges Contrataci´on de Personal Investigador Doctor. (Convocatoria 2019) 43 Contratos Capital Humano L´ınea 2. Paidi 2020, supported by the European Social Fund and Junta de Andaluc´ıa. Declaration of generative AI and AI-assisted technologies in the writing process During the preparation of this work, the author(s) used ChatGPT 4.0 in order to improve the readability and correctness of the text. After using this tool, the author(s) reviewed and edited the content as needed and take(s) full responsibility for the content of the publication. No new or original text or content has been generated through the use of artificial intelligence. 32 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed References [1] G. P˘aun, Computing with membranes, Journal of Computer and System Sciences 61 (1) (2000) 108–143. doi:https://doi.org/10.1006/jcss.1999.1693. [2] G. Ciobanu, G. Wenyuan, P Systems Running on a Cluster of Computers, in: C. Mart´ın-Vide, G. Mauri, G. P˘aun, G. Rozenberg, A. Salomaa (Eds.), Membrane Computing, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 123–139. [3] O. Andrei, G. Ciobanu, D. Lucanu, A rewriting logic framework for operational semantics of membrane systems, Theoretical Computer Science 373 (3) (2007) 163–181, structural Operational Semantics. doi:https://doi.org/10.1016/j.tcs.2006.12.016. URL https://www.sciencedirect.com/science/article/pii/S0304397506009029 [4] C. Mart´ın-Vide, Gh. P˘aun, J. Pazos, A. Rodr´ıguez-Pat´on, Tissue P systems, Theoretical Computer Science 296 (2) (2003) 295–326, Machines, Computations and Universality. [5] M. Ionescu, G. P˘aun, T. Yokomori, Spiking neural P systems, Fundamenta informaticae 71 (2-3) (2006) 279–308. [6] M. A. Colomer, A. Margalida, M. J. P´erez-Jim´enez, Population dynamics P System (PDP) models: A standardized protocol for describing and applying novel bio-inspired computing tools, PLOS ONE 8 (4) (2013) 1–13. doi:10.1371/journal.pone.0060698. [7] L. Ciencialov´a, E. Csuhaj-Varj´u, L. Cienciala, P. Sos´ık, P colonies, Journal of Membrane Computing 1 (3) (2019) 178–197. doi:10.1007/s41965- 019-00019-w. [8] H. N. Adorna, L. Pan, B. Song, On distributed solution to SAT by membrane computing, Int. J. Comput. Commun. Control 13 (3) (2018) 303–320. doi:10.15837/ijccc.2018.3.3217. [9] G. Zhang, Z. Shang, S. Verlan, M. A. Mart´ınez-del Amor, C. Yuan, L. Valencia-Cabrera, M. J. P´erez-Jim´enez, An Overview of Hardware Implementation of Membrane Computing Models, ACM Comput. Surv. 53 (4) (aug 2020). doi:10.1145/3402456. 33 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed [10] G. Zhang, M. J. P´erez-Jim´enez, A. Riscos-N´u˜nez, S. Verlan, S. Konur, T. Hinze, M. Gheorghe, P Systems Implementation on FPGA, Springer Singapore, 2021, Ch. 7, pp. 217–243. doi:10.1007/978-981-16-1566-5 7. [11] D. Cascado-Caballero, F. D. del Rio, D. Cagigas-Mu˜niz, A. Rios- Navarro, J.-L. Guisado-Lizar, I. P´erez-Hurtado, A. R.-N. nez, MAREX: A general purpose hardware architecture for membrane computing, Information Sciences 584 (2022) 360–386. doi:https://doi.org/10.1016/j.ins.2021.10.064. [12] A. Guti´errez, L. Fern´andez, F. Arroyo, V. J. Mart´ınez, Design of a Hardware Architecture Based on Microcontrollers for the Implementation of Membrane Systems, in: V. Negru, D. Petcu, D. Zaharie, A. Abraham, B. Buchberger, A. Cicortas, D. Gorgan, J. Quinqueton (Eds.), 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2006), 26-29 September 2006, Timisoara, Romania, IEEE Computer Society, 2006, pp. 350–353. doi:10.1109/SYNASC.2006.29. [13] M. A. Martinez-del Amor, M. Garcia-Quismondo, L. F. Macias-Ramos, L. Valencia-Cabrera, A. Riscos-N´u˜nez, M. J. Perez-Jimenez, Simulating P systems on GPU devices: a survey, Fundamenta Informaticae 136 (3) (2015) 269–284. [14] M. ´ A. Mart´ınez-del Amor, D. Orellana-Mart´ın, I. P´erez-Hurtado, L. Valencia-Cabrera, A. Riscos-N´u˜nez, M. J. P´erez-Jim´enez, Design of Specific P Systems Simulators on GPUs, in: T. Hinze, G. Rozenberg, A. Salomaa, C. Zandron (Eds.), Membrane Computing, Springer International Publishing, Cham, 2019, pp. 202–207. [15] A. Maroosi, R. C. Muniyandi, E. Sundararajan, A. M. Zin, Parallel and distributed computing models on a graphics processing unit to accelerate simulation of membrane systems, Simulation Modelling Practice and Theory 47 (2014) 60–78. doi:https://doi.org/10.1016/j.simpat.2014.05.005. URL https://www.sciencedirect.com/science/article/pii/S1569190X14000756 [16] I. P´erez-Hurtado, D. Orellana-Mart´ın, G. Zhang, M. J. P´erez-Jim´enez, P-lingua in two steps: flexibility and efficiency, Journal of Membrane Computing 1 (2) (2019) 93–102. doi:10.1007/S41965-019-00014-1. 34 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed [17] I. P´erez-Hurtado, L. Valencia-Cabrera, M. P´erez-Jim´enez, M. Colomer, A. Riscos-N´u˜nez, MeCoSim: A general purpose software tool for simulating biological phenomena by means of P systems, in: Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010, 2010, pp. 637 – 643. doi:10.1109/BICTA.2010.5645199. [18] P. Guo, C. Quan, L. Ye, UPSimulator: A General P System Simulator, Know.-Based Syst. 170 (C) (2019) 20–25. doi:10.1016/j.knosys.2019.01.013. [19] R. Lefticaru, M. Gheorghe, S. Konur, I. Niculescu, H. Adorna, Spiking Neural P Systems Simulation and Verification, in: 18th International Conference on High Performance Computing & Simulation (HPCS 2020), IEEE, 2021, pp. 22–27. [20] A. D. C. Fernandez, R. M. Fresco, F. G. C. Cabarle, R. T. A. de la Cruz, I. H. Macababayao, K. J. Ballesteros, H. N. Adorna, Snapse: A Visual Tool for Spiking Neural P Systems, Processes 9 (1) (2021). doi:10.3390/pr9010072. [21] A. Dupaya, A. Galano, F. Cabarle, R. T. de la Cruz, K. Ballesteros, P. Lazo, A web-based visual simulator for spiking neural P systems, Journal of Membrane Computing 4 (2022) 1–20. doi:10.1007/s41965- 022-00092-8. [22] G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Springer-Verlag, Berlin, Heidelberg, 1997. [23] Gh. P˘aun, G. Rozenberg, A. Salomaa, The Oxford Handbook of Membrane Computing, Oxford University Press, Inc., USA, 2010. [24] L. Lamport, How to make a multiprocessor computer that correctly executes multiprocess programs, IEEE Transactions on Computers C- 28 (9) (1979) 690–691. doi:10.1109/TC.1979.1675439. [25] M. Cardona, M. A. Colomer, A. Margalida, A. Palau, I. P´erez-Hurtado, M. J. P´erez-Jim´enez, D. Sanuy, A computational modeling for real ecosystems based on P systems, Natural Computing 10 (2011) 39–53. doi:10.1007/s11047-010-9191-3. 35 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed [26] R. Pereira, M. Couto, F. Ribeiro, R. Rua, J. Cunha, J. P. Fernandes, J. Saraiva, Ranking programming languages by energy efficiency, Science of Computer Programming 205 (2021) 102609. doi:https://doi.org/10.1016/j.scico.2021.102609. [27] D. Cagigas-Mu˜niz, P-systems github (2022). URL https://github.com/dcagigas/P-Systems.git [28] M. A. Mart´ınez-del Amor, M. Garc´ıa-Quismondo, L. F. Mac´ıas-Ramos, L. Valencia-Cabrera, A. Riscos-N´u˜nez, M. J. P´erez-Jim´enez, Simulating P Systems on GPU Devices: A Survey, Fundam. Inf. 136 (3) (2015) 269–284. 36 This preprint research paper has not been peer reviewed. Electronic copy available at: https://ssrn.com/abstract=4706826 Preprint not peer reviewed