Fast Hardware Implementations of Static P Systems

Computing and Informatics, Vol. 35, 2016, 687–718 FAST HARDWARE IMPLEMENTATIONS OF STATIC P SYSTEMS Juan Quiros ID2 Group, Department of Electronic Technology, University of Seville Avda. Reina Mercedes s/n, 41012, Sevilla, Spain e-mail: [email protected] Sergey Verlan LACL, D´epartement Informatique, Universit´e Paris Est 61, av. G´en´eral de Gaulle, 94010 Cr´eteil, France e-mail: [email protected] Julian Viejo, Alejandro Millan, Manuel J. Bellido ID2 Group, Department of Electronic Technology, University of Seville Avda. Reina Mercedes s/n, 41012, Sevilla, Spain e-mail: [email protected], [email protected], [email protected] Abstract. In this article we present a simulator of non-deterministic static P systems using Field Programmable Gate Array (FPGA) technology. Its major feature is a high performance, achieving a constant processing time for each transition. Our approach is based on representing all possible applications as words of some regular context-free language. Then, using formal power series it is possible to obtain the number of possibilities and select one of them following a uniform distribution, in a fair and non-deterministic way. According to these ideas, we yield an implementation whose results show an important speed-up, with a strong independence from the size of the P system. Keywords: Reconfigurable hardware, P systems, static P systems, FPGA, membrane computing, parallel implementations of membrane computing, simulator of 688 J. Quiros, S. Verlan, J. Viejo, A. Millan, M. J. Bellido membrane computing, hardware implementations of membrane computing, parallel implementations of static P systems, simulator of static P systems Mathematics Subject Classification 2010: 94-04, 68-04, 68U20 1 INTRODUCTION The beginning of the membrane computing goes back to the end of the nineties, when G. P˘aun introduced it [1]. This area gets its essence of living cells and, in consequence, the first models are defined as a hierarchical structure or a tree topology of compartments (membranes that delimits cells), which contains objects (chemicals), which evolves according to applicability rules (chemical reactions). Using this concept as a starting point, more variations, based on more biological processes which take place in living cells, have been detailed during following years (and it continues nowadays). One of the most relevant modifications was the introduction of the tissue P systems [2], in which the tree topology of the structure of membranes is substituted for a graph topology, where the structure is composed by cells, instead of tree nodes [3]. This work is based on the formal framework introduced in [4], in which a general class of multiset rewriting system, which contains P systems and tissue P systems, is designed. So, this section only describes, in a non-formal way, the most relevant aspects for the introduced work. For more details about P systems, we refer to the books [3, 5], and to [4] for specific information relative to the formal framework. A P system, Π, can be describe as a network of cells Π=(n, V, w, Inf, R),(1) where •nis the number of cells. •Vis the alphabet, which contains symbols for each object in the system. •wis a tuple (w1, . . . , wn), where wicorresponds to the multiset of objects (o∈V) contained in cell i. •Inf represents which symbols are provided by the environment. In this case, a cell can receive an infinite number of objects. Inf = (Inf1,...,Infn), where Infi⊆Vdetermines which elements of the alphabet are received by cell ifrom the environment. •Ris a finite set of rules, ri, with the form ri:X→Y;P, Q.X→Yare vectors of multisets, which can be written as ((x1,1),...,(xn, n)) →((y1,1),...,(yn, n)), meaning that objects in X, also called lhs(ri), left-hand-side of ri, are consumed by the evolving rule, whereas objects in Y, also called rhs(ri), right-hand-side of ri, are produced. Attending to Pand Q, they are also vectors of multisets, Fast Hardware Implementations of Static P Systems 689 called permitting and forbidding conditions, but in the form P= (p1, . . . , pn) and Q= (q1, . . . , qn). These last ones affect the applicability of the rule in the following way: a rule can be applied, or is applicable, if all elements in Pare contained by the cells and none of the elements in Qare contained by them. Obviously, it is necessary that there also exist all elements which are going to be consumed by the rule, i.e. all elements in X. For the design of the simulator, we have only considered static tissue-like P systems. According to above definition, a P system is static when its cells do not change along the computation. Moreover, in order to reduce complexity, we have removed the permitting and forbidding conditions from the original rule definition. As it is shown in Section 5, these elements can be added easily to the simulator. The computation of any P system starts with its initial configuration C0. A configuration describes the state of the system at a particular time. So, in the case of a static P system, the objects contained in each cell of the system are only required, because the structure does not change along the computation. In consequence, the computation begins with C0=wand, from this state, the system evolves to next configuration C1by means of application of rules, what is called a computation step, and continues until a halt condition is reached. We will not enter into details about halting conditions, they are discussed in the bibliography suggested above. However, the most typical conditions take place when the system reaches a configuration in which it is not possible to apply any rule, called total halting condition; or it is equal to previous configuration, i.e. although rules which can be applied exist, their application does not change the configuration, called adult halting condition. For our purpose, the most interesting aspect of P systems is the computation step, i.e., how they evolve from a configuration Ci, to the next one, Ci+1. This process is described below. 1. At the beginning of the step, the system has a configuration Ci. 2. Given Ci, there will be rules which can be applied, called as applicable rules, and others which cannot. According to some restrictions, called as derivation mode (δ), it is possible to define multisets of applicable rules. We define Appl(Π, Ci, δ) as the set of all multisets of applicable rules which verify the restrictions imposed by δ. We note that Appl is associated to a P system Π, a configuration Ciand a derivation mode δ. Hence, computing Appl(Π, Ci, δ) will be the first mini-step. As the reader can deduce, derivation modes play an important role in the semantic of the model. They can be seen as some restrictions which should be accomplished by a multiset of applicable rules, R, to be included in the Appl set. There are several types, and we refer again to bibliography for more details. Maximal parallelism, max, was the first derivation mode and the most used until now. In an informal way, it says that a multiset of applicable rules, R, can be included in Appl if, and only if it does not exist another rule, not included in R, and which can be applied; in other words, if we remove from the system 690 J. Quiros, S. Verlan, J. Viejo, A. Millan, M. J. Bellido all objects consumed by rules in R, there will not be enough resources so that another rule can be applied. Formally, maximal parallelism is defined as: Appl(Π, C, max) = {R0|R0∈Appl(Π, C) and @R00 ∈Appl(Π, C) such that R00 %R0}.(2) 3. Once the Appl(Π, C, δ) has been computed, an element Rmust be selected from it. The criteria which must be followed depends on the type of P system. An example is extracting an element following an equi-probable distribution, i.e., all elements have the same probability of being chosen. 4. Finally, the last mini-step is applying the selected R. It consists in, for each rule r: (X→Y;P, Q) in R, removing all objects contained in Xand adding all those ones contained in Y. After that, a new next configuration, Ci+1, is obtained. In this paper we detail basic ideas about simulation of non-deterministic P systems with a choice of the applicable set of rules following a uniform distribution. Our point of view is slightly different from other approaches, achieving a performance close to an ideal. Although it implies a loss of flexibility, reducing the range of input P systems, it is worth to note that the acceptance of a P system does not depend on its class, as it happens in other simulators, but on the complexity of the dependences of its rules, achieving a wide range of target P systems. In order to exemplify our approach, we present a hardware implementation using FPGA technology and based on our ideas, with a performance of around 2 ×107compu- tational steps per second, independently of the number of used rules or types of objects. This paper is organized as follows. Firstly, in Section 2 we describe previous implementations of P systems simulators, focusing on those ones using FPGA technology. Besides, we give a brief introduction to the theory of formal power series (Subsection 2.1), giving examples of the computation of generating series for different languages. In Section 3 we explain our method of pre-computation of all possible applications of rules (Subsection 3.1), and the general architecture of our simulator (Subsection 3.2). Section 4 gives an example of a FPGA implementation of a concrete P system using our ideas: firstly, we present the mathematical details concerning the example, secondly, Subsection 4.1 overviews the specific hardware design for the simulator and lastly, Subsection 4.2 presents the obtained results. Finally, in Section 5 we discuss about some improvements and future research tasks, and in Section 6 we summarize our conclusions. 2 PRELIMINARIES The problem of computer simulation of different variants of P systems arose at the very beginning of the area development. The first software simulators [6, 7] were quite inefficient, but they provided an important understanding of related Fast Hardware Implementations of Static P Systems 691 problems. Since most variants of P systems are by definition inherently parallel and non-deterministic, it is natural to use distributed or parallel architectures in order to achieve better performances [8, 9, 10]. Another fruitful idea is to use a specialized hardware for the simulation. This approach was taken in [11, 12] using FPGA reconfigurable hardware technology. The first implementation from [11] is based on region processors which have rules as instructions and multiplicity of objects as data. Although it has several limitations what limits its performance (parallelism across membranes only and a reduced extensibility and scalability), it demonstrates that P systems can be executed on FPGAs. In the other [12, 13, 14] two possible designs are detailed: rule-oriented and region-oriented systems. In the first one, each rule is considered as a basic processing unit and, in consequence, has a specific hardware core. As a result, the system achieves a maximum degree of parallelism, because of all rules are executed in parallel by specific hardware components. In the second case, the basic processing units are regions. Thus, communication between regions acquire more relevance: local rules are processed by the region processors and, after that, a communication process between regions takes place in order to update the multiplicity of objects. In both architectures, there is a control logic which synchronizes the operations of processing units and updating of registers what saves the configuration of the system. How registers are grouped and what is considered as a basic processing unit depends on the approach (rules or regions). An important point for a (parallel) computing platform for membrane computing is to achieve a good balance between performance, flexibility and scalability. This is especially important for hardware simulators because the high performance comes often at an important price of flexibility or scalability. The important drawback of FPGA simulators from [11, 12] is that they suppose that the evolution of a P system is deterministic, and thus these simulators will yield always the same result for the same initial configuration. However, the non-determinism in P systems plays an important role and its absence reduces drastically the classes of P systems that can be used with the above simulators. Furthermore, the simulators are based on the model detailed in the foundational article [1]. As a consequence, they have strong restrictions about topology, type of objects and rules of the P system. So, a more flexible simulator would be desirable. In that way, some theoretical results, as [4], can be a starting point in order to develop a simulator which covers most of the restrictions about topology, rules and objects, that is to get a more flexible one. 2.1 Context-Free Grammars as Generators of Formal Power Series We assume that the reader is familiar with some notions from the formal power series theory, especially related to the theory of formal languages. We suggest reading of [15] for more details on this topic. We denote by |w|the length of the word wor the cardinality of the multiset or set w. For our purposes we consider that a formal power series fis a mapping f:A∗→N, where Ais an alphabet and Nis the set of 692 J. Quiros, S. Verlan, J. Viejo, A. Millan, M. J. Bellido non-negative integers (in the general case a formal power series is a mapping from a free monoid to a semiring). This mapping is usually written as f=X w∈A∗ f(w)w. (3) It is known that a context-free grammar G= (N, T, S, P) can be seen as a set of equations xi=α1+· · · +αni, for each non-terminal xiof G, where αjare the right-hand sides of productions xi→αj, 1 ≤j≤ni. A solution of Gis a set of formal power series s1, . . . ,sk, such that the substitution of xiby siin above equations converts them to the identity, i.e., corresponding series are equal term by term. It is well known [16] that si=Pw∈A∗fi(w)w, where fi(w) is the number of distinct leftmost derivations of wstarting from xi. Under the mapping that sends any symbol from Ato the same symbol, say x, we obtain the generating series for a non-terminal xi: fi= ∞ X n=0 X |w|=n fi(w)xn.(4) Let fi(n) = P|w|=nfi(w). Then the above equation can be rewritten as: fi= ∞ X n=0 fi(n)xn.(5) Suppose that x1=S, where Sis the starting symbol of G. Then f1is called the generating series of G. If Gis unambiguous, then f1(n) gives the number of words of length nin G. We denote by [xn]fthe nth coefficient of f, i.e. [xn]f=f(n). Let φbe the morphism defined by φ(λ) = 1, φ(a) = x, ∀a∈T, (6) φ(xi) = fi, xi∈N. Let xi→vi1| · · · | vik be the set of productions associated to xi. Then fican be obtained as the solution of the following system of equations: fi= k X j=1 φ(vij).(7) For a regular grammar Gthe system (7) becomes linear. By considering a finite automaton A= (V, Q, q0, Qf, δ) equivalent to Gwe obtain that system (7) corresponds to the following system (recall that xis considered as a constant) Q=xMQ +F, (8) where: Fast Hardware Implementations of Static P Systems 693 •Q= [q1. . . qn]t,qi∈Q, 1 ≤i≤nis the vector containing all states. •F= [a0. . . an]t, is the final state characteristic vector, i.e., ai= 1 if qiis a final state and 0 otherwise. •Mis the transfer matrix of the automaton A, i.e. the incidence matrix of the graph represented by Awith negative values replaced by zero. We remark that in the case of a regular language it is also possible to count the number of words of length nby summing the columns corresponding to the final states of the nth power of the transfer matrix of the corresponding automaton: fi(n) = X qj∈Qf (Mn)i,j.(9) It is known that the generating series ffor a regular language is rational. That implies that there exists a finite recurrence f(n) = Pk j=1 ajf(n−j), k > 0, aj∈Z which holds for large n. Example 1. Considering the regular language LIrecognized by the following automaton q2 1 //q0 0?? 1//q1 0//q3 0// 1 ccq4 1  the final state characteristic vector Fof this automaton is defined by F= [0,1,0,1, 0]tand the transfer matrix Mby M=      01100 00010 01000 01001 01000       .(10) 694 J. Quiros, S. Verlan, J. Viejo, A. Millan, M. J. Bellido The corresponding system (8) of linear equations has the following solution: q0=x3+ 2x2+x 1−x2−x3, q1=x+ 1 1−x2−x3, q2=x2+x 1−x2−x3,(11) q3=x2+x+ 1 1−x2−x3, q4=x2+x 1−x2−x3. We can expand q0to obtain q0(n) (= [xn]q0), q0=x+ 2x2+ 2x3+ 3x4+ 4x5+ 5x6+ 7x7+ 9x8+. . . (12) The coefficients of the above series give the number of words of the corresponding length. For example, there are 9 words of length 8 in LI. It is not difficult to verify that the obtained coefficients [xn]qk, 0 ≤k≤4, of the corresponding power series are particular cases of the Padovan sequence qk(n) = qk(n−2) + qk(n−3), n > 3, with the following starting values: k qk(0) qk(1) qk(2) 0 1 1 2 1 1 1 1 2 0 1 1 3 1 1 2 4 0 1 1 3 DESIGN OF THE SIMULATOR 3.1 Formal Part As it was detailed in Section 1, there are several features of a static P system which define it: topology, type of objects, rules, derivation mode and how a multiset of rules is chosen from the Appl set. The formal framework lets us remove the topology, type of objects and rules from this list. Hence we must only worry about the application of the rules. In this section, we consider a (static) P system, Π, of any type evolving in any derivation mode, chosen a multiset of rules in a nondeterministic way. The main idea for the construction of a fast simulator is to avoid the computation of the set Appl(Π, C, δ) and to compute R, the multiset of rules to be applied directly. In this article we are interested in algorithms that permit to Fast Hardware Implementations of Static P Systems 695 perform this computation on FPGA in constant time. We remark that, in a digital FPGA circuit synchronized by a global clock signal, in one cycle of FPGA, it is possible to compute any function where implementation has a delay which does not exceed the period of the global clock signal. A pipeline using arithmetical operations and, in general, any combinatorial and sequential asynchronous subsystems, are usually included in this group. In order to simplify the problem we split it into two parts corresponding to the construction of the following recursive functions: NBVariants(Π, C, δ): gives the cardinality of the set Appl(Π, C, δ). Variant(n, Π, C, δ),where 1 ≤n≤NBVariants(Π, C, δ): gives the multiset of rules corresponding to the nth element of some initially fixed enumeration of Appl(Π, C, δ). It is clear that if each function is computed in constant time, then the multiset of rules to be applied can also be computed in a constant time. In the following, we will discuss methods for the construction of these two functions for different classes of P systems. We will need the notion of the rules’ dependence graph. This is a weighted bipartite graph where the first partition Ucontains a node labeled by afor each object aof Π, while the second partition Vcontains a node labeled by rfor each rule rof Π. There is an edge between a node r∈Vand a node a∈Ulabeled by a weight kif ak∈lhs(r) (and ak+1 6∈ lhs(r)). Example 2. Considering a P system Π1having two rules r1:ab →uand r2:bc → v. These rules have the following dependence graph: r1r2 a b c Let Na, Nband Ncbe the number of objects a,band cin a configuration C. We define N1= min(Na, Nb), N2= min(Nb, Nc),(13) N= min(N1, N2). Suppose that Π evolves in a maximally parallel derivation mode. Then the set Appl(Π, C, max) can be computed as follows: Appl(Π, C, max) = [ p+q=Nnrp+k1 1rq+k2 2o,(14) 702 J. Quiros, S. Verlan, J. Viejo, A. Millan, M. J. Bellido tion. Although other blocks (persistenceBlock partially) use unsigned integers in order to save hardware resources, this one operates with signed integers, because some objects can be consumed (negative number) or produced (positive number). controlBlock: It is required to provide communication and control logic. Control is implemented using a finite state machine, which requires five states, and it generates all control signals. This block contains the rest of the logic associated to halting conditions and its complexity depends on the type of P system. The most frequent conditions are executing a fixed number of transitions; when, given a configuration, the Appl set is empty; or when the configuration does not change, even when Appl is not empty. inoutBlock: Besides the previous cores, an additional block is required to provide communication with the computer. It is strictly linked to software which runs in the computer. We are developing a new software which is able to be connected to a wide range of simulators, using a serial port as a first approach. Although, it is not complete yet. In consequence, some debug cores are used to control execution and to get results. 4 EXAMPLE OF SIMULATOR CONSTRUCTION Once general architecture and the ideas (modelling of P Systems applying formal framework) and algorithms on which it is based have been presented in previous sections, we used the following example to illustrate the FPGA implementation for our ideas. We considered multiset rewriting rules working in set-maximal mode (smax). This mode corresponds to the maximally parallel execution of rules, but where the rules cannot be applied more than once. This mode can be formally defined as follows (where asyn is the asynchronous mode [4] and Ris the set of all rules): S1={R∈Appl(Π, C, asyn)| |R|rj≤1,1≤j≤ |R|}, Appl(Π, C, smax) = {R∈S1|there is no R0∈S1such that R0⊃R}.(21) We remark that smax mode corresponds to min1mode [4] with a specific partition of rules: the size of the partition is |R| and each partition pjcontains exactly one rule rj∈ R. Considering now a multiset rewriting system (corresponding to a P system with one membrane) evolving in smax mode. To simplify the construction we consider rules having a dependence graph in a form of chain without weights. Fast Hardware Implementations of Static P Systems 703 r1r2. . . rn a0a1a2an−1an Let Naibe the number of objects aiin configuration C. The number of variants of applications of a chain of rules r1, . . . , rkto the configuration Cin smax mode is denoted by NBV ([r1, . . . , rk], C), k > 0 . We remark that for a P system Π having the set of rules R,NBVariants(Π, C, smax) = NBV (R, C). It is possible to distinguish 3 cases with respect to the number of objects Nai, 0≤i≤n(considering that 0 ≤s≤i≤e≤n): •Nai= 0. Then the two surrounding rules (riand ri+1) are not applicable. In this case the parts of the chain at the left and right of aiare independent, so the number of variants is a product of corresponding variants: NBV (rs, . . . , re, C) = NBV (rs, . . . , ri−1, C)∗NBV (ri+2, . . . , re, C).(22) •Nai>1. As in the previous case the chain can be split into two parts because both rules riand ri+1 can be applied: NBV (rs, . . . , re, C) = NBV (rs, . . . , ri, C)∗NBV (ri+1, . . . , re, C).(23) •Nai= 1. In this case riand ri+1 are in conflict. Now let us concentrate on the last case. Without loss of generality we can suppose that Nai= 1, 0 ≤i≤n. We remark that the language of binary strings of length ncorresponding to the joint applicability vector of rules r1, . . . , rncoincides with the language LIfrom Example 1. Therefore the number of possibilities of application of such a chain of rules of length nis equal to NBV (r1, . . . , rn, C) = [xn]q0, i.e., q0(0) = 1, q0(1) −1, q0(2) = 2 and q0(n) = q0(n−2) + q0(n−3), n > 3. Hence, in order to compute NBVariants(Π, C, smax) we first split the chain into k > 0 parts of length njaccording to the multiplicities of objects and compute the NBV function for each part using the decomposition above. The function Variant for each part can be computed using Algorithm 1. The next section gives more details on the implementation of the above algorithms on FPGA. 4.1 Implementation Details Starting from general architecture, there are only two blocks which can be affected by the implementation of a new type of P system: controlBlock and assignBlock. The first modification is originated by the halting conditions, and its impact is reduced to controlBlock. In this case, the halting configuration is reached when the configuration of the system does not change, even the Appl set being not empty. 704 J. Quiros, S. Verlan, J. Viejo, A. Millan, M. J. Bellido Attending to assignBlock, the derivation mode of the P system changes the way in which P system evolves, being needed to modify it. These situations are explained in Section 3.2, so we will not give more details about it here. The implementation of assignBlock depends on the selected evolving mode, smax mode in this case. According to algorithms explained in previous sections, it has to perform the following steps: Algorithm 2. 1. The input chain is split into kparts as it is described in Section 4. 2. For each part: (a) The system computes NBVariants(Π, C, smax). For this purpose, algorithms detailed in 2.1 and 4 are used. (b) The value of n, which indicates which combination will be chosen (nth element), is obtained. It is worth to note that its domain is from 0 to NBVariants(Π, C, smax)−1, so, considering that the random number generator produces numbers in binary format, the following correction is sometimes needed in order to obtain it. i. A random number, rn, is generated by the random number generator, where 0≤width(rn)≤ dlg2(NBVariants(Π, C, smax))e. ii. If rn < NBVariants(Π, C, smax) then n=rn. Otherwise, n=rn +NBVariants(Π, C, smax). (c) Compute Variant(n, Π,smax), according to Algorithm 1. We note that the computation of NBVariants(Π, C, smax) uses a subset of operations needed to compute Variant(n, Π,smax), moreover, these operations can be done in parallel with the generation of the random number n, necessary to compute Variant(n, Π,smax). Hence, this stage can be performed in 2 clock cycles by dividing operations into two sets, called left and right propagation, respectively. As it is shown by Figure 2, left propagation is the first to be executed. In this sub-stage, steps 2.a and 2.b.i of Algorithm 2 are computed from the last rule to the first one. Right propagation, which is the compound of steps 2.b.ii and 2.c, is executed in opposite way in the next clock cycle. One advantage of this approach is that it is not necessary to divide, implicitly, the chain of rules in kparts, deleting a step of the algorithm which let us reduce the number of required cycles from three to two. This logic is implemented, explicitly, by signals prevIsDep and chainStateSignal. After this stage, all rules have a random multiplicity assigned. In consequence, the architecture of this block is divided into one sub-block per rule (Figure 2), which implements the operations required in order to obtain the number of applications of its associated rule (left and right propagation). The interconnections between these components are based on design keys and propagation concepts: a sub-block is only connected to blocks located on its right and left. Fast Hardware Implementations of Static P Systems 705 Nxr_i n r_i Nxr_i Nx r_i+1 … … UnitControl calcNx values_of_Automaton [NBVariants part (Π ,C , smax)] chainStateSignal [indChainDetector ] randomMask randomNumber combs_in [Variant part(n , Π, C , smax)] autState_in [state2visit ] prevIsDep [indChainInd ] RuleBlock r_i+1 AutSubBlock r_i+1 ControlSubBlock r_i+1 ndSubBlockr_i+1 … … RandomNumberGenerator n r_i n r_i+1 … … INIT chainStateSignal INIT randomMask UPDATE chainStateSignal UPDATE randomMask UPDATE values_of_automaton according to chainStateSignal and values generated by previous block Left Propagation SET AutState = AutState_in SET Combs = Combs_in SET AutState = Q0 INIT combs according to randomNumber Right Propagation Nr != 1 Nr == 1 prevIsDep == 1 prevIsDep != 1 Nr != 1 Nr == 1 SET IsDep = 1 SET IsDep = 0 SET Nr = Nr According to autState and combs SET combs_out According to autState and combs SET nextAutState According to autState and combs SET Nr RuleBlock r_i AutSubBlock r_i ControlSubBlock r_i ndSubBlock r_i debugSignalschangeSeedclk execute (1) (2) Figure 2. Details of sub-blocks which compound the assignRule block. Flow of information between sub-blocks in left and right propagation is shown at the top of the figure (1). Below it, the algorithm is detailed using UML notation (2). 706 J. Quiros, S. Verlan, J. Viejo, A. Millan, M. J. Bellido Because assignBlock is the most critical component in order to achieve the maximum performance of the simulator, all operations which are required to compute NBVariants(Π, C, smax) and Variant(n, Π,smax) are defined recursively and are pipelined for the sake of a powerful performance. Hence, each sub-block associated to the nth rule computes asynchronously the number of times which the associated rule will be applied, based on values obtained by previous block. It permits to execute all operations in only two cycles, one for left propagation and another for right propagation, in contrast to synchronous version, which requires, at least, ncycles, due to dependences between rules and, in consequence, between operations for computing Variant and NBVariants. 4.2 Experimental Results Experimental results are divided into two tests. In the first one, the accuracy of the results generated by the simulator has been proved. Right after, we have obtained some results about the limitations of the physical hardware (FPGA) regarding size of the P system, and the relation performance-area required by the simulator in the device. The P systems are the same in both tests, only modifying its size (number of rules and objects). All of them consider rules where dependence graph forms a chain, the difference being in the right-hand side. Using these four types of dependences between rules let us check the accuracy of the results, because their design makes their behaviour predictable. We consider four P systems with the alphabet O= {o0, . . . , oN},N > 0 and having the following rules (we consider index operations modulo N+ 1): •System 1 (circular) ri:(oi−1oi→oioi+1,1≤i<N−1, oN−1oN→o0o1, i =N. (24) •System 2 (2-circular) ri:oi−1oi→oi+1oi+2,1≤i≤N. (25) •System 3 (linear) ri:(oi−1oi→oioi+1,1≤i<N−1, oN−1oN→oNoN, i =N. (26) •System 4 (opposite), 1 ≤i≤N ri:(oi−1oi→oioi+1, i mod 2 = 0, oioi+1 →oioi−1,otherwise .(27) Fast Hardware Implementations of Static P Systems 707 The target circuit for executions was the Xilinx Virtex-7 XC7VX485T, although similar results have been obtained with a Xilinx Virtex-5 FXT70 FPGA. Regarding code generation and extraction of results, different P systems were generated by a Java software and this code was synthesised, placed and routed using Xilinx tools. Since the input/output interface has not been developed yet, Chip- Scope, a Xilinx debug tool has been used. This tool lets us, synchronously, change and capture the results, i.e. computation results and consumption of hardware resources, directly from the FPGA. In order to carry out accuracy tests, an initial multiplicity of all objects equal to one and values 10, 20 and 50 were considered for Nparameter for accuracy test. The P systems with these sizes are manageable enough to let us check this parameter of the simulator. Values 10, 30, 50, 70, 90, 110, 150 and 200 for Nparameter were considered in case of hardware test. These values are enough in order to give a general idea about the relationship between consumption of hardware resources by the simulator and the size of the P systems. Then, for each obtained system, 1 024 executions of 8 192 transitions have been carried out. Each execution differs from the others by the seed required by the random number generator in the initialization stage. In consequence, different values are obtained during the assignment stage, which results in different executions. As results of experiments, the following values are collected: the cardinality of objects in the last configuration, the seed of the random number generator (just for internal results) and the number of steps to reach the halting configuration, in case the system reached it. Table 1 gives some statistics concerning the experiments. For each P system (type, size), the table shows if the stop condition is reached and, in this case, the minimum and maximum number of required transitions to achieve it (column Halting). The third column shows how many different configurations have been reached by the system. This parameter indicates the grade in which the system evolves following an equiprobable distribution. As expected, linear and 2-circular systems reach a halting configuration, while in the other two cases it cannot, due to dependences among their rules. It can be seen that the simulation of non-determinism is done correctly – in some cases all resulting configurations are different. Figure 3 shows the maximal, the minimal and the mean value of the number of different objects. Due to size of the obtained graphs, we only show the case of 10 rules, the other cases present a similar picture. It can be seen that in the case of the linear system there is a high chance to have a big value for the last object and in the case of 2-circular systems the second and penultimate objects are never present. In the case of circular systems it is possible to see an equiprobable distribution of objects, while for the opposite systems even values have a higher multiplicity. It can be easily seen that the rules used should exhibit exactly this behavior. Concerning performance tests, they only differ in the Nparameter from values of the P systems. The Xilinx tools let user control the generation of final bitstream providing some parameters. In that way, three sets of parameters, with three implementation goals, have been used: one to maximize performance, another 708 J. Quiros, S. Verlan, J. Viejo, A. Millan, M. J. Bellido Type N Different final conf. Halting Y/N min max Circular 10 982 No – – 20 1 024 No – – 50 1 024 No – – 2-circular 10 161 Yes 5 89 20 818 Yes 11 197 50 1 024 Yes 57 609 Linear 10 204 Yes 7 17 20 944 Yes 14 29 50 1 024 Yes 50 65 Opposite 10 4 No – – 20 938 No – – 50 1 024 No – – Table 1. Statistics concerning the executions of example systems to minimize area and a balanced configuration. For each hardware design and set of parameters, values relative to performance (Table 2) and hardware resource consumption (Figure 4) were taken. In Table 2 and Figure 4 only the best results are shown: those ones achieved with performance configuration and area minimization, respectively. Table 2 shows hardware period in ns of the system without the debug logic and Figure 4 shows resource consumption using relative values of LUTs and Slices. The implementation achieves high performance, with frequencies higher than 100 MHz, i.e., it allows to simulate around 2 ×107computational steps per second. A runtime comparison between P-Lingua simulator and our hardware simulator is shown in Table 3. P-Lingua is a Java software framework developed by members of the Research Group on Natural Computing, at the University of Seville. In order to make the comparison, several opposite P systems, see Definition 27, with a number of rules between 10 and 200, have been chosen. These P systems have been converted to equivalent probabilistic P systems: they have an environment with a membrane, they follow the same dependences between rules as opposite P Systems and they have the same number of rules and objects. The computing platform for execution was an Intel Core i55220 at 3 GHz, with 8 GB of RAM. The comparison shows that hardware architecture is 5 600 times faster than P-Lingua implementation in the worst case, when a P system with 10 rules is used, and approx. 30 000 times faster than P-Lingua in the best case, when the P system has 200 rules. Attending to the hardware resource consumption, it only depends on the number of rules. This result is coherent with the fact that rules of all systems do not change Fast Hardware Implementations of Static P Systems 709 objA objB objC objD objE objF objG objH objI objJ objK 0 2 4 6 8 10 12 Max Min Mean a) objA objB objC objD objE objF objG objH objI objJ objK 0 1 2 3 4 5 6 7 8 9 10 Max Min Mean b) objA objB objC objD objE objF objG objH objI objJ objK 0 1 2 3 4 5 6 7 Max Min Mean c) the total number of objects and share the same dependence graph. While the period is stable, with a slightly linear increase, the resources grow exponentially, reducing the use of the simulator for really large problems, in terms of thousands of rules. Current implementation has problems for P systems with more than 1 000 rules. In this case, configurations composed of several devices can be developed to move this barrier. 710 J. Quiros, S. Verlan, J. Viejo, A. Millan, M. J. Bellido objA objB objC objD objE objF objG objH objI objJ objK 0 0,5 1 1,5 2 2,5 Max Min Mean d) Figure 3. Objects min/max/mean values for the experiments using 10 rules; a) Linear, b) 2-circular, c) Circular, d) Opposite Type \Size Circular 2-circular Linear Opposite 10 7.06 ns 5.63 ns 5.46 ns 7.85 ns 30 8.23 ns 8.55 ns 7.33 ns 6.99 ns 50 7.69 ns 6.71 ns 6.11 ns 6.03 ns 70 9.14 ns 7.33 ns 7.34 ns 6.87 ns 90 7.32 ns 6.38 ns 7.02 ns 7.89 ns 110 7.00 ns 7.84 ns 6.23 ns 8.30 ns 150 7.85 ns 7.42 ns 8.88 ns 7.40 ns 200 7.74 ns 8.42 ns 7.98 ns 8.35 ns Table 2. Period of hardware implementation for each combination (type, sizes) 5 DISCUSSION One of the major characteristics of the simulator is its speed, offering a constant time execution step (in terms of clock cycles). Its design is based on the method discussed Size Software Hardware 10 0.22 s 3.927 ×10−5s 30 0.326 s 3.495 ×10−5s 50 0.453 s 3.017 ×10−5s 70 0.542 s 3.435 ×10−5s 90 0.639 s 3.945 ×10−5s 110 0.742 s 4.151 ×10−5s 150 0.911 s 3.7×10−5s 200 1.245 s 4.174 ×10−5s Table 3. Runtime comparison between a software simulation using P-Lingua, and a hardware simulation using architecture Fast Hardware Implementations of Static P Systems 711 10 30 50 70 90 110 150 200 0 10 20 30 40 50 60 Circular 2-circular Linear Opposite Size of the P system (rules) LUTs (%) a) 10 30 50 70 90 110 150 200 0 2 4 6 8 10 12 Circular 2-circular Linear Opposite Size of the P system (rules) Slices (%) b) Figure 4. LUTs and Slices consumption of hardware implementation for each combination (type, sizes) in rules; a) LUTs, b) Slices in Section 3.1 where, although it is possible to design ad-hoc functions that describe the execution strategy of the rules, we concentrated on the cases where the multisets of rules that can be applied form a non-ambiguous context-free language. This fact allows to easily compute the generating function of the corresponding language and gives a simple algorithm for the enumeration strategy. In this work we have focused on P systems whose rules are restricted to dependence graphs which form chains. However, the class of P systems where the set Appl(Π, C, δ) corresponds to a non-ambiguous context-free language is quite big. For example, considering a set of rules forming a circular dependence graph for a system working in the smax mode. 718 J. Quiros, S. Verlan, J. Viejo, A. Millan, M. J. Bellido Manuel J. Bellido received his B.Sc. degree in 1987 and his Ph.D. degree in 1994 in physics from the University of Seville, Spain. He has been with the Electronics Technology Department at the same university since 1990 where he holds a post as Associate Professor. Currently he is the co-director of ID2 research group (http://www.dte.us.es/id2). He has contributed by tens of research works to international journals and conferences in the area of metastability, delay modelling and logic level simulation. Lately, his main interests are the embedded systems based on open systems. He also acted as scientific consultant for a number of international journals like IEEE Transactions on Circuits and Systems, Electronics Letters, etc. Currently he is also a member of the editorial board of the Journal of Low Power Electronics.