On Two-Dimensional Mesh Networks and Their Simulation with P Systems

On Two-Dimensional Mesh Networks and Their Simulation with P Systems Rodica Ceterchi1and Mario J. P´erez–Jim´enez2 1Faculty of Mathematics and Computer Science, University of Bucharest, Academiei 14, 010014 Bucharest, Romania [email protected] 2Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] Abstract. We analize in this paper the possibility of simulating the parallel architecture SIMD-MC2, also known as the two-dimensional mesh, with P systems with dynamic communication graphs. We illustrate this simulation for an algorithm which computes the sum of given integers. Next, we show how to extend the formalism to the reduction problem. 1 Introduction P systems are powerful computational devices, with a high degree of parallelism, whose functioning is inspired by biological processes at the level of the cells, and of their membranes ([6], [7]). Among these processes, communication plays an important role (see [5]). We have started in previous work ([2], and [3]) to analyze the possibility of simulating (classical) parallel architectures with P systems. A parallel machine consists of a large number of processors (each one having an arithmetic logic unit with registers and a private memory) able to solve problems in a cooperative way. The “cooperation” (sharing of data among processors) is accomplished via a specific communication network which characterizes the architecture. We have considered in [2], and [3], the case of the shuffle–exchange architecture. In the present paper we deal with a different type of architecture, the two-dimensional mesh, in which the processors are placed in the vertices of a 2D-lattice in the plane, and communication is possible only between adjacent processors. In the course of this study, a new type of P systems has emerged: P systems with dynamic communication graphs of specific types. They are in a way similar to tissue-like P systems, the connections between elementary membranes being described by graph structures, but they have a dynamic behavior: the underlying graph structures change in time. Moreover, rules, which are generally associated to regions inside membranes, are in this new version associated to underlying graphs. This new formalism covers both the simulation of internal processing, modelled by symbol rewriting rules, and the communication of data, modelled by symport/antiport rules. The paper is organized as follows. Section 2 describes briefly the 2D-mesh parallel architecture. In Section 3 we introduce the P systems with dynamic communication of 2D-mesh type, the tools with which we accomplish the desired simulation. Section 4 illustrates an application of the 2D-mesh architecture to an algorithm for computing the sum of a set of integers, and contains a proof of its correctness. In Section 5 we discuss several simulations of the sum algorithm with P systems with dynamic communication of 2D-mesh type. In the next two sections we give some indications on how to extend the formalism to solve a general reduction problem. 2 The 2D-Mesh Architecture Recall that a parallel machine consists of a large number of processors (each one having an arithmetic logic unit with registers and a private memory) able to solve problems in a cooperative way; that is, the machine is capable of executing several instructions in the same time unit. According to Flynn’s classification of computers (see [4]), a form of synchronous parallelism is called SIMD (Single–Instruction–Multiple–Data). A SIMD machine consists of a set of identical processors capable of simultaneously performing the same instruction issued by a central control unit, on different sets of data, and in a synchronous manner: each processor executing an instruction in parallel must be allowed to finish before the execution of the next instruction starts. Several different methods of connecting processors in a parallel computer have been proposed. Quinn [8], quoting Ullman [9], mentions six important processor organizations, among which the mesh network. In a mesh network the processors are arranged into a q-dimensional lattice, and communication is allowed only between neighboring nodes, hence interior nodes communicate with 2qother processors. A SIMD machine in which the processors may communicate with each other via a mesh-connected network of dimension qis called in [8] a SIMD-MCqmachine. We deal in this paper with SIMD-MC2machines, i.e., a set of processors working according to the SIMD paradigm, and able to communicate (share) data among them according to a two–dimensional lattice architecture, which we will call in the sequel the 2D-mesh architecture. In general, in a given parallel architecture, we say that two processors are adjacent if they are directly connected. The distance between a pair of processors in a given architecture is the smallest length of a path between the processors. The diameter of an architecture is defined as the largest distance between any processors in the network. The two–dimensional mesh architecture provides a network with a large number of communication links connected to each processor, permitting to reduce the diameter of the network. In general, we consider a two–dimensional mesh–connected parallel computer as a SIMD machine consisting of n×midentical processors, P11,...,P nm, placed in the nodes of a 2D-lattice, or, equivalently, arranged in a 2D array. Each processor has a local memory consisting of a number of registers, and it can perform a number of operations on data stored in these registers. The communication between processors (mainly transmission of values of local variables) can take place only according to the 2D-lattice structure of the underlying network. Thus the processor placed in row iand column j, is denoted by Pi,j, (or Pij) with 1 ≤i≤nand 1 ≤j≤m.IfPi,j is an interior node, i.e., i=1,j=1,i=n,j=m, then Pi,j has four neighbors: Pi−1,j and, Pi+1,j on the same column, j, and Pi,j−1,Pi,j+1 on the same row, i. The rows i= 1 and i=n are the boundary rows, and columns j= 1 and j=mare the boundary columns. The nodes at the intersection of a boundary row and a boundary column have each one precisely two neighbors, and the rest of the boundary nodes have three neighbors. 3 P Systems with Dynamic Communication Graphs of 2D-Mesh Type The model we develop here for the simulation of the 2D-mesh architecture is along the same general lines as the model proposed for the shuffle-exchange networks in [2] and [3], with some differences which arise inherently from the differences in the two parallel architectures in question. We have a SIMD-MC2machine, composed of n×mprocessors, denoted Pij, with 1 ≤i≤n,1≤j≤m, organized in a 2D-mesh architecture. To each processor Pij we will associate a membrane, which we will still denote Pij. Similarly to tissue-like P systems, we will have a collection of elementary membranes, connected by certain graphs, at certain moments of their evolution in time. The graphs we will consider will be sub-graphs of the total graph of the 2D-mesh network, also sub-graphs of the identity graph of the 2D-mesh network, as we will explain in the sequel. The contents of each processor Pij will be codified in its associated membrane with symbol objects. The alphabet of symbols used, V, will depend on the contents of the processors we are simulating (see the applications in the following sections). If each processor has to contain say rvariables with positive integer values, they can be in principle codified with an alphabet with rletters. In the case of the applications illustrated further, we will have to represent at most two integer variables. Their simulation with P systems will use accordingly an alphabet with two (or four) symbols. Basically, we have to model: –Patterns of specific internal processing in each processor: these will be modelled by symbol rewriting rules. –Patterns of communication between processors. Recall that in the 2D-mesh architecture the communication between processors takes place along edges which connect two neighboring processors. As we have done in general for parallel architectures, and, in particular, for the perfect–shuffle architecture in previous work (see [2], [3]), we will speak of the (underlying) communication graph associated to a given architecture: the vertices of the graph are the processors, and the edges (oriented or not) are the network connections characteristic of the architecture. In the case of the 2D- mesh, the underlying communication graph is composed of all edges between neighboring nodes. We will call it the total graph, and we distinguish between horizontal edges and vertical edges. We use the following notation: Gtotal =Gh∪Gv= n  i=1 Gi∗∪ m  j=1 G∗j, where Gi∗={((i, j),(i, j + 1)) |1≤j≤m−1},for all 1 ≤i≤n, G∗j={((i, j),(i+1,j)) |1≤i≤n−1},for all 1 ≤j≤m. Gi∗is the set of all horizontal edges on line i, with 1 ≤i≤n, and G∗jis the set of all vertical edges on column j, for 1 ≤j≤m. For every particular algorithm implemented on a 2D-mesh network of processors, not all edges of the communication graph are used simultaneously for transmitting values of local variables, as we will see in the illustrations which follow. For this reason we will speak of the total virtual communication graph, and of active sub-graphs of Gtotal, composed of sets of edges along which actual communication takes place, in parallel, at certain steps of a given algorithm. For modelling the internal processing steps, in order to have unity of notation, we will associate the rules to the identity graph: the set of vertices is composed of all processors/membranes, the set of edges is defined as Id ={((i, j),(i, j)) |1≤i≤n, 1≤j≤m}. If an internal processing occurs only in a subset of the processors/membranes, then we will consider the respective active sub-graphs of Id. For instance, if internal processing occurs only for processors/membranes on line i, we will associate it with the active sub-graph Idi∗={((i, j),(i, j)) |1≤j≤m}. Similarly, if an internal processing occurs only for processors/membranes on column j, we will associate it with the active sub-graph Id∗j={((i, j),(i, j)) |1≤i≤n}. The P systems which we consider in the sequel, for modelling the 2D-mesh architecture, similarly to those considered in [2] and [3], depart from the classical P systems in two respects: – The connections between individual membranes of a P system, µ, which was a tree-like structure of membranes (see [6]), and which in tissue-like P systems becomes a graph structure, is now, a sequence of graphs. – The rules of a P system, usually associated to membranes, will now be associated to communication graphs between membranes. (a) We simulate the internal computations performed by a subset of processors by the action of symbol or object rewriting rules, at work simultaneously inside the corresponding subset of membranes. We will associate such rules to the corresponding active subsets of Id. (b) We simulate the exchange of data performed by the processors with communication rules (symport/antiport rules) between membranes. The communication rules will be associated to the active sub-graphs of Gtotal. We will consider the edges to have an orientation which gives meaning to the in and out of the symport/antiport rules: out means travelling in the sense of the edge’s orientation, in means travelling in the opposite sense. Thus, rules suchas(a, out), (a, in) function along an oriented edge in the same way they would function if they were attached to the source vertex of the edge. As in [2] and [3] (with slight modifications), we will use pairs [graph, rules] to describe the evolution of a P system which simulates the behavior of a given algorithm, in the 2D-mesh architecture. For every particular architecture, its underlying network structure imposes restrictions on the set Graphs to which the first member of a pair [graph, rules] can belong. For the 2D-mesh architecture Graphs is either a subset of Gtotal,or a subset of Id. The set Rules, of all symbol/object rewriting rules which simulate internal computations performed by the individual processors, will depend on the particular algorithm, used to solve a particular problem, within the framework of a given architecture. We model deterministic algorithms, each iterative step of such an algorithm will be modelled by a finite sequence of pairs [graph, rules] (sometimes each pair simulating the effect of “an instruction”, but not necessarily). The entire execution of such an algorithm will be modelled by a sequence of pairs [graph, rules], denoted in the sequel by Rµ. A P system which simulates a particular algorithm in the 2D-mesh architecture will thus be a construct Π=(V,P11,···,P nm,R µ), where P11,···,P nm are elementary membranes, Vis an alphabet of symbols used to codify the contents of the membranes, and Rµis a finite sequence of pairs [graph, rules], such that: (i) if graph ⊂Id, then its rules are rewriting rules; (ii) if graph ⊂Gtotal, then its rules are communication rules. We will call such a system a P system with dynamic communication of 2D-mesh type. The P system starts in an initial configuration, with its elementary membranes P11,···,P nm simulating the initial configuration of the corresponding processors. Each application of an element [graph, rules]∈Rµto a configuration consists of considering the (active) graph graph and applying the rules rules associated to it: (i) if graph ⊂Id, the corresponding rewriting rules are applied in the membranes which are vertices of graph; (ii) if graph ⊂Gtotal, the corresponding symport/antiport rules are applied along the edges of graph. This leads to the next configuration. The final configuration is obtained after the application of the entire sequence Rµ. Note that the general presentation of a P system with dynamic communication graph which simulates a given (arbitrary) parallel architecture based on communication networks (denote it by X) is the same: it specifies an alphabet of symbols used to codify the contents of membranes, a finite set of elementary membranes, and, finally, a finite sequence Rµof pairs [graph, rules]. The specifics of each architecture Ximpose certain particular forms for the sets Graphs to which the first member of a pair [graph, rules] can belong, and for the pairing [graph, rules]. Further, the specifics of each architecture, and sometimes of an algorithm implemented on it, govern the structure of the entire sequence Rµ. Denote by Graphs(X) the active graphs associated to the architecture X. For X= perfect shuffle SIMD = PS-SIMD we have (see [2], [3]): Graphs(PS-SIMD)={Gs,G e,G Id}, and the conditions for pairs are: 1. (i) if graph =GId, then its rules are rewriting rules; 2. (ii) if graph ∈{Gs,G e}, i.e., graph is either of type shuffle or of type exchange, then its rules are communication rules. For X= 2D-mesh SIMD = SIMD-MC2we have: Graphs(SIMD-MC2)=P(Gtotal)∪P(Id), and the conditions for pairs are: 1. (i) if graph ⊂Id, then its rules are rewriting rules; 2. (ii) if graph ⊂Gtotal, then its rules are communication rules. As for the differences in the structure of the sequence Rµ, in the case of the perfect shuffle architecture Rµwas periodic, while in the case of the 2D-mesh architecture it is not necessarily so, as we will see in the example illustrated in the next section. 4 The Sum on the 2D-Mesh We compute the sum of ninteger numbers a11,a 12,...,a ll, where n=l2, using the 2D-Mesh architecture, each integer held in one processor. We have n=l2processors Pij (1 ≤i, j ≤l) that possess two local variables: xij (initialized by aij ) and tij (initialized by 0). The following procedure computes the sum a11 +a12 +···+all. procedure sum2D−MESH(a11,a 12,···,a ll) begin for all i, j where 1≤i, j ≤ldo xij ←aij;tij ←0 endfor for j←l−1downto 1 do for all iwhere 1≤i≤ldo tij ⇐xi(j+1) xij ←xij +tij endfor endfor for i←l−1downto 1 do ti1⇐xi+1,1 xi1←xi1+ti1 endfor end where tij ⇐xi(j+1) means that processor Pi,(j+1) links by the mesh with processor Pij and communicates the value of variable x, and processor Pij puts it in variable t. In order to prove the correctness of this algorithm we reformulate in detail what is happening in each processor throughout the execution. We denote by xr ij and tr ij the corresponding values of the local variables of processor Pij after step rof the execution. The above algorithm can now be reformulated in the following, more detailed, manner: procedure sum2D−MESH(a11,a 12,···,a ll) begin for all i, j where 1≤i, j ≤ldo x0 ij ←aij;t0 ij ←0 endfor for j←l−1downto 1 do for all iwhere 1≤i≤ldo tl−j ij ⇐xl−j−1 i(j+1) xl−j ij ←x0 ij +tl−j ij endfor endfor for i←l−1downto 1 do t2l−i−1 i1⇐x2l−i−2 i+1,1 x2l−i−1 i1←xl−1 i1+t2l−i−1 i1 endfor end Theorem 1. The formula θ(j)≡∀i(1 ≤i≤l−→ xl−1 ij = l  s=j ais)is an invariant of the loop “for j←l−1downto 1 do” of the procedure sum2D−MESH. Proof. By descendant induction on j. –For j=l−1 we have, for each isuch that 1 ≤i≤l: xl−1 i,l−1=x1 i,l−1=x0 i,l−1+t1 i,l−1 =x0 i,l−1+x0 i,l =ai,l−1+ai,l = l  s=l−1 ais –Let j>1 and suppose that the formula θ(j) is true. Let us prove that the formula θ(j−1) is also true. For each isuch that 1 ≤i≤lwe have: xl−(j−1) i,j−1=x0 i,j−1+tl−(j−1) i,j−1 =x0 i,j−1+xl−j i,j i.h. =ai,j−1+ l  s=j ais = l  s=j−1 ais  Theorem 2. The formula ϕ(i)≡x2l−i−1 i1= l  r=i l  s=j ars is an invariant of the loop “for i←l−1downto 1 do” of procedure sum2D−MESH. Proof. By descendant induction on i. –For i=l−1wehave: x2l−i−1 i,1=x2l−(l−1)−1 l−1,1=xl−1 l−1,1+t2l−(l−1)−1 l−1,1 =xl−1 l−1,1+xl−1 l,l = l  s=1 al−1,s + l  s=1 al,s = l  r=l−1 l  s=l−1 ars –Let i>1 and suppose that the formula ϕ(i) is true. Let us prove that the formula ϕ(i−1) is also true. For each isuch that 1 ≤i≤lwe have: x2l−(i−1)−1 i−1,1=xl−1 i−1,1+t2l−(i−1)−1 i−1,1 =xl−1 i−1,1+x2l−i−1 i,1 Th. 1+i.h. = l  s=1 ai−1,1+ l  r=i l  s=j ars = l  r=i−1 l  s=j ars  Corollary 1. At the end of the execution of procedure sum2D−MESH, the variable xof processor P11 contains the value of the sum a11 +···+all. Proof. At the end of execution the formula ϕ(1) is true; that is, it is verified that: x2l−1−1 11 = l  r=1 l  s=j ars =a11 +a12 +···+all. Recall that x2l−1−1 11 is the content of the processor P11 at the end of the execution.  Let us note that the above algorithm, although formulated for a square 2D- mesh, works in the same way on a rectangular mesh, of dimensions n×m, and only slight changes are necessary in the proofs of the corresponding correctness results. The following procedure computes the sum a11 +a12 +···+anm. procedure sum2D−MESH(a11,a 12,···,a nm) begin for all i, j where 1≤i≤n,1≤j≤mdo xij ←aij;tij ←0 endfor for j←m−1downto 1 do for all iwhere 1≤i≤ndo tij ⇐xi(j+1) xij ←xij +tij endfor endfor for i←n−1downto 1 do ti1⇐xi+1,1 xi1←xi1+ti1 endfor end Its running time, measured in number of iterative steps, is (n−1)+(m−1). in the parallel architecture, were modelled with “communication-only” rules in the P systems simulation (the case of Theorem 3). In the first two simulations, Theorem 3 and Theorem 4, there was no need to even represent the auxiliary variable t, a local memory essential for the functioning of the parallel algorithm. This implies that the notion of “communication” in P systems is stronger than the corresponding notion in classical parallel models, of course, at the cost of “local memory loss”. 6 The Reduction on the 2D-Mesh Architecture Let (A, ∗,0) be a commutative monoid, i.e., Ais a set, ∗is a binary associative and commutative operation over A, and 0 is the neutral element of ∗. Let a0,...,a k−1be elements of this set. The reduction (see [8], Section 2.3.1) is the process of computing a0∗···∗ak−1. The 2D-mesh architecture can be used to solve the reduction problem. Let us suppose that the total number of elements is k=(2m+1)×(2n+ 1). Consider k=(2m+1)×(2n+ 1) processors connected by a 2D-mesh network. The nodes of the network will be labelled by pairs (i, j) (or simply ij), with ithe row index, −m≤i≤m, and with jthe column index, −n≤j≤n. The set of elements to which we want to apply the reduction is {a(−m)(−n),...,a (−m)(n),...,a 00,...,a m(−n),...,a mn}. Processor Pij, with label ij,−m≤i≤m,−n≤j≤n, possesses two local variables: xij (initialized by aij) and tij (initialized by 0). The following procedure computes a(−m)(−n)∗···∗a(−m)(n)∗···∗a00 ∗···∗am(−n)∗···∗amn, and puts the result in processor P00: procedure reduction2D−MESH(a(−m)(−n),...,a 00,...,a mn) begin for all i, j where −m≤i≤m,−n≤j≤n,do xij ←aij;tij ←0 endfor for j←n−1downto 0 do for all iwhere −m≤i≤mdo tij ⇐xi(j+1) xij ←xij ∗tij endfor endfor for j←−n+1 to0do for all iwhere −m≤i≤mdo tij ⇐xi(j−1) xij ←xij ∗tij endfor endfor for i←m−1downto 0 do ti0⇐xi+1,0 xi0←xi0∗ti0 endfor for i←−m+1 to0do ti0⇐xi−1,0 xi0←xi0∗ti0 endfor end The second and fourth for loops are iterative steps, one responsible for performing the ∗operation on columns from nto 0, the other for performing the ∗ operation on rows from mto 0, similarly to the algorithm for sum in section 4. However, this algorithm has some improvement over the one in section 4. The third for loop is the “mirror image” of the second one: a sequence of iterative steps, performing the ∗operation on columns, this time from −nto 0. Note that the execution of iterative step jin the second loop can be done in parallel with the execution of iterative step −jof the third loop. Similarly, the fifth for loop is the “mirror image” of the fourth one: a sequence of iterative steps, performing the ∗operation on rows, this time from −mto 0. Note that the execution of iterative step iin the fourth loop can be done in parallel with the execution of iterative step −iof the fifth loop. This ensures that the running time of this algorithm, (if we apply the parallelism mentioned above), measured in iterative steps is (2m+2n)/2, i.e., this algorithm takes √k/2 steps, compared with √ksteps required by the previous algorithm for sum. The simulation which follows makes use of this enhanced parallelism. 7 Simulation of the Reduction In order to simulate the algorithm for reduction presented in section 6 with P systems with dynamic communication of 2D-mesh type, we have to work under the following supplementary assumptions: 1. The elements aij on which the operation ∗is performed can be codified inside each membrane Pij over a finite alphabet, say Vx; the alphabet will be used to codify all values of variable xij , both initial and intermediate; 2. Using the same codification, the values of local variables tij are codified inside each membrane Pij over a finite alphabet, say Vt; 3. Vxand Vtare in bijective correspondence: to each a∈Vxthere corresponds a symbol a∈Vt; 4. There exists a set of symbol rewriting rules on Vx∪Vt, denoted r∗, which simulates performing the operation xij ∗tij inside each membrane Pij; the value of the result xij ∗tij is codified over Vxas the new value of xij. Under these assumptions, the rest of the model follows the general lines of the models for sum in Section 5. Copying the value of xij into tij is done by the set of symbol rewriting rules {a−→ aa|a∈Vx}. Since the codifications for x’s and t’s are the same, the effect is the desired one. Transfer of values for t’s over the appropriate edges can be accomplished with the set of symport rules {(a, out)|a∈Vt}. Finally, the set r∗will compute xij ∗tij and put the result in xij. We construct now the sequences of pairs [graph, rules] which simulate the iterative steps of the reduction algorithm. To simplify the notation we write all i instead of −m≤i≤m. For each j=n,...,1 (the horizontal steps), we take Rhj=[Id∗j∪Id∗(−j),{a−→ aa|a∈Vx}], [{((i, j),(i, j −1)) |all i}∪{((i, −j),(i, −j+ 1)) |all i},{(a, out)|a∈Vt}], [Id∗(j−1) ∪Id∗(−j+1),r ∗]. For each i=m,...,1 (the vertical steps on column 0), we take Rvi=[Idi0∪Id(−i)0,{a−→ aa|a∈Vx}], [{((i, 0),(i−1,0))}∪{((−i, 0),(−i+1,0))},{(a, out)|a∈Vt}], [Idi0∪Id(−i)0,r ∗]. Let (A, ∗,0) be a commutative monoid, and consider the following set of elements of A: {a(−m)(−n),...,a (−m)(n),...,a 00,...,a m(−n),...,a mn}. Assume that every element of Acan be codified over an alphabet Vx, and that there exists a set of rewriting rules r∗which simulates performing operation ∗ on two elements of A, one codified over Vx, the other over Vt, and the result of the computation is again codified over Vx. Consider the P system with dynamic communication of 2D-mesh type Π∗=(Vx∪Vt,{Pij |−m≤i≤m, −n≤j≤n},R µ∗), where Rµ∗is the sequence of pairs [graph, rules]: Rµ∗=Rhn···Rhj···Rh1·Rvm···Rvi···Rv1, with Rhjand Rvias defined previously. Then, starting from an initial configuration in which each membrane Pij contains a codification of the value aij over Vx, for all −m≤i≤m,−n≤j≤n, the application of the sequence Rµ∗will lead to a final configuration in which P00 contains a codification of S∈A, where S=a(−m)(−n)∗···∗a(−m)(n)∗···∗a00 ∗···∗am(−n)∗···∗amn. 8 Conclusions We have analyzed in this paper the possibility of simulating the parallel architecture known as the 2D-mesh with a new version of P systems, P systems with dynamic communication graphs. In Section 3 a comparison is made between dynamic communication graphs of 2D-mesh type, introduced here, and dynamic communication graphs of shuffle– exchange type, introduced in previous work. We believe this illustrates the power of this new version of P systems as tools for formalizing other network architectures as well. We have illustrated the proposed simulation with the particular algorithm for computing the sum of a given set of integers. Discussing several possible simulations of the sum algorithm has given us the opportunity to compare “communication” as understood in P systems, and communication in classical parallel architectures. We have further presented an algorithm to solve the reduction problem implemented on a 2D-mesh, and discussed its simulation with P systems with dynamic communication graphs, simulation possible under some supplementary assumptions. References 1. R. Ceterchi, C. Mart´ın–Vide, P Systems with Communication for Static Sorting. In M. Cavaliere, C. Mart´ın–Vide and Gh. P˘aun (eds.), Proceedings of the Brainstorming Week on Membrane Computing, Report GRLMC 26/03, 2003, 101–117. 2. R. Ceterchi, M.J. P´erez–Jim´enez, Simulating Shuffle–Exchange Networks with P Systems. In Gh. P˘aun, A. Riscos–N´u˜nez, F. Sancho–Caparrini and A. Romero– Jim´enez (eds.), Proceedings of the Second Brainstorming Week on Membrane Computing, Report RGNC 01/04, 2004, 117–129. 3. R. Ceterchi, M.J. P´erez–Jim´enez, A Perfect Shuffle Algorithm for Reduction Processes and its Simulation with P Systems. In I. Dzitac, T. Maghiar, C. Popescu (eds.), Proceedings of the International Conference on Computers and Communications ICCC 2004, May 27-29, 2004, Baile Felix Spa – Oradea, Romania, Editura Univ. Oradea, 2004, 92–97. 4. M.J. Flynn, Very High-Speed Computing Systems, Proceedings of the IEEE 54, 12 (1966), 1901–1909. 5. A. P˘aun, Gh. P˘aun, The Power of Communication: P Systems with Symport/Antiport. New Generation Computers, 20, 3 (2002), 295–306. 6. Gh. P˘aun, Computing with Membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143, and Turku Center for CS-TUCS Report No. 208, 1998. 7. Gh. P˘aun, Membrane Computing. An Introduction, Springer-Verlag, Berlin, 2002. 8. M.J. Quinn, Parallel Computing. Theory and Practice, McGraw–Hill Series in Computer Science, 1994. 9. J.D. Ullman, Computational Aspects of VLSI, Computer Science Press, Rockville, MD, 1984.