Simulating the Bitonic Sort on a 2D-mesh with P Systems

Simulating the Bitonic Sort on a 2D-mesh with P Systems Rodica Ceterchi1, Mario J. P´erez-Jim´enez2, Alexandru Ioan Tomescu1 1Faculty of Mathematics and Computer Science, University of Bucharest Academiei 14, RO-010014, Bucharest, Romania 2Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected], [email protected], [email protected] Summary. This paper gives a version of the parallel bitonic sorting algorithm of Batcher, which can sort Nelements in time O(log2N). When applying it to the 2D mesh architecture, two indexing functions are considered, row-major and shuffled rowmajor. Some properties are proved for the later, together with a correctness proof of the proposed algorithm. Two simulations with P systems are proposed and discussed. The first one uses dynamic communication graphs and follows the guidelines of the mesh version of the algorithm. The second simulation requires only symbol rewriting rules in one membrane. 1 Introduction P systems, introduced in [19], are powerful computational models, with nondeterministic as well as parallel features. Deterministic P systems can be also considered, and the power of their parallel features compared against the power of other computational models which enjoy parallelism. Along this line we refer to previous work, which relates P systems with parallel networks of processors, functioning according to the SIMD paradigm (Single Instruction Multiple Data machines), in [8], [9], for shuffle-exchange networks, and in [6] for 2D mesh networks. The comparison was approached by designing P systems which simulate the functioning of a specific architecture, when solving a specific problem. In [7] the general features of this type of approach were abstracted, giving a “blueprint” for the design of a class of deterministic P sytems, with dynamic communication graphs, which simulate a given parallel architecture, functioning to implement a given algorithm. Among the choices to be made for the problem to solve, the static sorting imposes itself, being a central theme in computer science. Although it is well known that comparison-based sorting algorithms require at least O(Nlog N) comparisons 206 R. Ceterchi, M.J. P´erez-Jim´enez, A.I. Tomescu to sort Nitems, performing many comparisons in parallel can reduce the sorting time. This paper analyses the bitonic sorting algorithm, one of the fastest parallel sorting algorithms where the sequence of comparisons is not data-dependent. The bitonic sorting network was discovered by Batcher [3], who also discovered the network for odd-even sort. These were the first networks capable of sorting Nelements in time O(log2N). Stone [24] maps the bitonic sort onto a perfect-shuffle interconnection network, sorting Nelements by using Nprocessors in time O(log2N). Siegel [23] shows that bitonic sort can also be performed on the hypercube in time O(log2N). The shuffled row-major indexing formulation of bitonic sort on a mesh-connected computer is presented by Thompson and Kung [25]. They also show how the odd-even merge sort can be used with snakelike row-major indexing. Nassimi and Sahni [16] present a row-major indexed bitonic sort formulation for a mesh with the same performance as shuffled row-major indexing. Static sorting algorithms have been developped and proposed also in the P systems area. Among the first approaches, made independently, we mention [2] and [4], [5]. The problem of sorting with P systems occupies Chapter 8, [1], of the monograph [10]. We analyze in this paper a version of the bitonic sorting algorithm of Batcher, and its implementation on the 2D mesh architecture. Section 2 introduces the mesh topology and the model of computation. In 2.2 we begin the formal study of indexing functions, and we stress their importance for the passing to a network architecture. (Some similar work has been done in [12] and [13], but we develop our own formalism.) In 2.3 we present the algorithm, and the main result, Theorem 1, whose Corrolary is the correctness proof of the algorithm. Other results in this subsection, like Lemma 3, and the Remarks, are subsequently used to prove assertions about the algorithm, and, in Section 3, about the simulations with P systems. Section 3 is devoted to the presentation of two different simulations of the algorithm with P systems. The first simulation uses dynamic communication graphs, as in [7]. A generative approach to the sequence of graphs used to communicate values between the membranes is a novel feature. The second simulation, uses only one membrane, and symbol rewriting rules. 2 Preliminaries: The bitonic sort on the 2D-mesh 2.1 Model of Computation The presentation of the bitonic sort on the 2D-mesh architecture is made here based mainly on the paper [25]. It is the same algorithm as in [21], but with more emphasis on the routings necessary to compare elements situated at greater distances on the mesh. Also, some restrictions imposed in [25], will be eliminated, or re-examined, since they were dictated by their explicit connection to the ILLIAC IV-type parallel computer. In general, our references to parallel machines/architectures will be at the level of generalization to be found for instance Simulating the Bitonic Sort on a 2D-mesh with P Systems 207 in [21]. We also found it useful to formalize properly some aspects related to the indexing function. Let us assume as in [25] that we have a parallel computer with N=n×n identical processors, disposed in a 2D-mesh structure. A processor is connected to all of its four vertical or horizontal neighbors, except for the processors situated on the perimeter, which have at most two or three neighbors, as no “wrap-around connections“ are permitted. Another assumption is that it is a SIMD (Single Instruction Multiple Data) machine. During each time unit, a single instruction is executed by a set of processors. In what follows, only two processor registers and two instructions are needed. For inter-processor data moves, we will use a routing instruction which copies the value of a register to a register of a neighbor processor. The second instruction is the internal comparison between the values of the two registers of a processor. We define tRthe time for one-unit distance routing step, and tCthe time required for one comparison step. Concurrent data movement is allowed, as long as it is in the same direction; also any number of parallel comparisons can be made simultaneously. 2.2 The sorting problem and indexing functions We assume to have an indexing function on the processors that is a one-to-one mapping from {0,1, . . . , n −1} × {0,1, . . . , n −1}onto {0,1, . . . , N −1}and that initially Nintegers are loaded in the Nprocessors. Therefore the sorting problem is defined as moving the jth smallest element to the processor indexed by j, for all j∈ {0,1, . . . N −1}. Let I:{0,1, . . . , n −1} × {0,1, . . . , n −1} −→ {0,1, . . . , N −1}denote an indexing function. Two indexing schemes are the following: (i) Row-major indexing. This is illustrated in Figure 1, and we denote it by I= RM. (ii) Shuffled row-major indexing. This is illustrated in Figure 2, and we denote it by I=sRM. In order not to make the notation cumbersome, we let the same letter, say i, stand for an integer in {0,1, . . . , n −1}, and for its binary representation as a string. For n= 2k, as the case will be, iwill be a binary string of length k. Whenever necessary, we complete with zeroes (obviously, to the left) to obtain strings of the same length. (When we refer to bits of such a string, we count from 1 to n, starting from right to left, such that the “first” bit will be that of the least significant digit, and so forth. However, when we write such a string, we will write it with bits numbered from right to left.) Consider the following definitions: Definition 1. The row-major indexing function RM is defined by RM(i, j) = ij, where in the right hand-side we have denoted by ij the string concatenation of the 208 R. Ceterchi, M.J. P´erez-Jim´enez, A.I. Tomescu 0000 00001 10010 20011 3 0100 40101 50110 60111 7 1000 81001 91010 10 1011 11 1100 12 1101 13 1110 14 1111 15 00 01 10 11 00 01 10 11 Fig. 1. Row-major indexing scheme for a 4 ×4 mesh binary representations of the integers iand j, after they have been brought to the same length. More precisely, for every k, we have the bijections RMk:{0,1, . . . , 2k−1}×{0,1, . . . , 2k−1} −→ {0,1, . . . , 22k−1}, defined by RMk(i1i2···ik, j1j2· · · jk) = i1i2···ikj1j2· · · jk. Let sh (from ’shuffle’) stand generically for the family of bit-shuffle functions shk:{0,1, . . . , 22k−1} −→ {0,1,...,22k−1}, defined by shk(i1i2· · · ikj1j2· · · jk) = i1j1i2j2···ikjk. This is a bijection, with the obvious inverse ushk(i1j1i2j2· · · ikjk) = i1i2· · · ikj1j2· · · jk, where ush comes from ’un-shuffle’. In the following we will drop the index k whenever it is clear from the context. Definition 2. The shuffled row-major indexing function sRM is defined by sRM(i, j) = sh(ij), where in the right hand-side we have denoted by ij the string concatenation of the binary representations of the integers iand j, after they have been brought to the same length, and sh is the appropriate bit-shuffle function. More precisely, for every k, we have the bijections sRMk:{0,1, . . . , 2k−1}×{0,1, . . . , 2k−1} −→ {0,1, . . . , 22k−1}, defined by sRMk(i1i2· · · ik, j1j2· · · jk) = shk(i1i2· · · ikj1j2· · · jk) = =i1j1i2j2· · · ikjk. Simulating the Bitonic Sort on a 2D-mesh with P Systems 209 0000 00001 10100 40101 5 0010 20011 30110 60111 7 1000 81001 91100 12 1101 13 1010 10 1011 11 1110 14 1111 15 00 01 10 11 00 01 10 11 Fig. 2. Shuffled row-major indexing scheme for a 4 ×4 mesh Lemma 1. For every i, j1, j2∈ {0,1, . . . , 2k−1}with j1< j2, we have that sRM(i, j1)< sRM(i, j2). Analogously, for every i1, i2, j ∈ {0,1, . . . , 2k−1}with i1< i2, we have that sRM(i1, j)< sRM(i2, j). Proof. The proof is immediate, from the definition of sRM.¤ Let us consider the following general definition: Definition 3. We call indexing function on the 2k×2kmesh a bijection Ik:{0,1, . . . , 2k−1}×{0,1, . . . , 2k−1} −→ {0,1,...,22k−1}. The problem of sorting on a 2k×2kmesh is obviously related to an indexing function I: given a family of values (Pij)ij, to sort them means to sort the corresponding ’linear’ family (PI(i,j))I(i,j), i.e., to find the permutation σkof {0,1,...,22k−1}such that (PσI(i,j))σI(i,j)is ascending (or descending). Furthermore, when designing or implementing sorting algorithms on the 2D mesh, through an indexing function Ithey will be translated into algorithms for sorting a linear set, (PI(i,j))I(i,j). But, the linear version of the algorithm, for sorting say an array hP0, . . . , P22k−1i, has to be such that its translation into 2D- mesh operations be admissible. By this last word we mean to obey certain rules for the functioning of the 2D mesh as a network of processors. One such rule is the possibility of a processor to communicate only with its neighbours. Other rules may involve simultaneous communication with neighbours: a processor may communicate with two neighbours simultaneously, provided they are on the same line or column, and that, if the same register is involved, the old value is read and communicated while the new value is written. Still further rules may involve the parallel functioning of the network: communications in parallel may be allowed only if either only lines or only columns are involved at one parallel step. The above mentioned restrictions can be formulated in a formal manner, leading to a notion of good indexing function, but this is beyond the scope of this 210 R. Ceterchi, M.J. P´erez-Jim´enez, A.I. Tomescu paper. Let us just say for now, that, if the linear version of the algorithm performs a comparison between Prand Ps, then PI−1(r)and PI−1(s)must be neighbours in the 2D mesh topology. Since the linear version of the algorithm is also parallel, whole pairs of families must be mapped by I−1into adjacent families, and the last ones are naturally the adjacent lines or columns of the mesh. This justifies to a certain degree results present in this paper such as Lemma 3. The choice of the indexing function Ik=sRMkprovides the connection between the bitonic sorting algorithm as presented in [21] and the bitonic sorting network of [14] and Figure 3. Let us also note that both RMk−1and sRMk−1are easy to compute. For a linear index r=i1i2···ikj1j2· · · jk, RMk−1(r) = RMk−1(i1i2· · · ikj1j2· · · jk) = = (i1i2· · · ik, j1j2· · · jk) = (rdiv 2k, r mod 2k), and similarly for sRMk−1. 2.3 The bitonic sorting algorithm In Batcher’s bitonic sorting network [3] of order n, the input is a bitonic sequence aof n/2 increasing elements followed by n/2 decreasing elements. These two sequences are merged by first applying n/2 comparators to a0and an/2,a1 and a(n/2)+1, ... an/2and an−1. This first-phase partitions the elements into two bitonic sequences of n/2 smaller elements and of n/2 larger elements. These two bitonic sequences are further sorted by applying two bitonic merging networks of size n/2 to each sequence. A bitonic sorting network for 16 elements appears in Figure 3. Lemma 2. [3] Given a bitonic sequence ha1, a2, . . . , a2nithe following hold. 1. d=hmin{ai, an+i}n i=1i=hmin{a1, an+1},min{a2, an+2}, . . . , min{an, a2n}i is bitonic. 2. e=hmax{ai, an+i}n i=1i=hmax{a1, an+1},max{a2, an+2}, . . . , max{an, a2n}i is bitonic. 3. max(d)< min(e). By an abuse of notations, we shall refer to a sequence of processors as the sequence of integers stored in one designated register Aof the processors at a certain moment. Similarly, we shall use min /max{Pi, Pj}meaning min /max{Pi[A], Pj[A]}and refer to such operations as a comparison and interchange of values between processors Piand Pj. We shall give a generic algorithm for Batcher’s bitonic sorter on an array hP0, . . . , P22k−1iof processors, independent of the indexing function used. The algorithm (as illustrated in Figure 3 for k= 2) will consist of 2kstages, numbered from 1 to 2k. After each Stage i, the sequence hP2ij, . . . , P2ij+2i−1iwith Simulating the Bitonic Sort on a 2D-mesh with P Systems 211 Stage 1 Stage 2 Stage 3 Stage 4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Fig. 3. A bitonic sorting network of size 16 0≤j≤2k−i−1 will be an ascending sequence for all jeven, and a descending sequence, for all jodd. Input: an array hP0, . . . , P22k−1iof processors Output: the sequence hP0, . . . , P22k−1iis ascending Stage(i) for t←idownto 1do // compare processors with indices differing on bit t forall j←0to 22k−t−1in parallel do if 2tjdiv 2iis even then order = ascending else order = descending Merge(2tj, 2tj+ 2t−1, order) end Bitonic-Sort for i←1to 2kdo Stage(i) end Algorithm 1: Bitonic sort on an array of 22kprocessors Given a bitonic sequence of processors hP1, P2, . . . , P2ni, by Merge(1,2n, ascending) we mean an operation which yields the sequence: 212 R. Ceterchi, M.J. P´erez-Jim´enez, A.I. Tomescu hmin{P1, Pn+1},min{P2, Pn+2}, . . . , min{Pn, P2n}, max{P1, Pn+1},max{P2, Pn+2},...,max{Pn, P2n}i. Analogously, a call to Merge(1,2n, descending) produces hmax{P1, Pn+1},max{P2, Pn+2}, . . . , max{Pn, P2n}, min{P1, Pn+1},min{P2, Pn+2}, . . . , min{Pn, P2n}i. Theorem 1. After each Stage i, the sequence hP2ij, . . . , P2ij+2i−1i,0≤j≤2k−i− 1will be an ascending sequence for all jeven, and a descending sequence, for all jodd. Proof. We shall reason by induction on i. For the base case i= 1 it is immediate that the statement holds. Now let the statement be true for iand show that is it also true for i+ 1. First, t=i+ 1 and 0 ≤j≤2k−i−1−1. The sequence Sfor the i+ 1 case can be written as S=hP2i+1j, . . . , P2i+1j+2i−1i= hP2i2j, . . . , P2i2j+2i−1, P2i(2j+1), . . . , P2i(2j+1)+2i−1i. From the induction hypothesis, we have that the sub-sequence S1=hP2i2j, . . . , P2i2j+2i−1i is ascending as 2jis even for any j, and that S2=hP2i(2j+1), . . . , P2i(2j+1)+2i−1i is descending as 2j+1 is odd for any j. Therefore, the whole sequence Sis bitonic. At this point we apply the Merge operation on S, and get S0=S0 1S0 2. By Lemma 2 we have that S0 1and S0 2are both bitonic. Moreover, when doing an ascending merge, max(S0 1)<min(S0 2) and when doing a descending merge, min(S0 1)>max(S0 2). This ensures that the two sequences are relatively ordered and can be sorted independently in parallel. For 1 ≤t < i + 1 the Merge operations are the same as in a merging network. We note that for all 2i+1j≤l < 2i+1(j+ 1), ldiv 2i+1 =jand therefore all subsequent Merge operations for t < i + 1 on these processors will have the same order as when t=i+ 1. ¤ Corollary 1. Given a sequence hP0, . . . , P22k−1iof processors, Algorithm 1 is correct. Proof. The proof is immediate by Theorem 1. At Stage kwe have j= 0 and hence the sequence hP0, . . . , P22k−1iis ascending. ¤ Simulating the Bitonic Sort on a 2D-mesh with P Systems 213 Lemma 3. Given a 2k×2k2D-mesh indexed with the function sRM and using Algorithm 1, for any two processors x= 2tj+land y= 2tj+l+ 2t−1, with 0≤l≤2t−1−1,1≤t≤i, and 0≤j≤2k−t−1, which compare and interchange values inside a call of the form Merge (2tj, 2tj+2t−1, order), the following hold: (i) the binary representations of xand ydiffer only on bit t; (ii)if tis even then xand yreside on the same vertical line of the mesh; if t is odd they are on the same horizontal line; (iii)the distance on the mesh between xand yis 2dt/2e−1; (iv)all processors situated on the same line between xand yare involved in the same Merge operation (i.e., have indices between 2tjand 2tj+ 2t−1). Proof. (i) Since x= 2tj+land l≤2t−1−1, we have that lcontributes to bits 1 to t−1 and that 2tjcontributes to bits t+ 1 to 2k. Therefore bit tof xis 0. Similarly, since y=x+2t−1, bit tof yis 1, and all other bits are the same as those of x. (ii) We apply the ’un-shuffle’ function to xand yand get ush(x) = i1j1and ush(y) = i2j2. By the definition of sRM we have that the iis the row index, while jis the column index. From i) we have that xand ydiffer on bit t, and hence the following two cases hold: tis even and i16=i2,j1=j2, or tis odd and i1=i2, j16=j2. In the first case xand yare on the same column, and in the latter, they are on the same row. (iii) Using the notations above, let us assume that tis even and i16=i2, j1=j2. If xand ydiffer on bit t, then i1and i2will differ on bit t/2, and therefore |i1−i2|= 2t/2−1. From ii)xand yare on the same line of the mesh and the distance between them is |i1−i2|= 2t/2−1. Similarly, when tis odd and i1=i2, j16=j2, we have that j1and j2differ on bit dt/2e. As before, the distance between xand yis 2dt/2e−1. (iv) Consider again the case teven and i16=i2,j1=j2. We have to show that for all numbers iwith i1≤i≤i2, we have 2tj≤sRM(i, j1)≤2tj+ 2t−1. But since i1≤i≤i2, form Lemma 1, we have that x≤sRM(i, j1)≤y, which concludes our proof as 2tj≤xand y≤2tj+ 2t−1. Analogously for todd. ¤ 2.4 Applying the bitonic sorting algorithm to the 2D-mesh Thompson and Kung [25], and Orcutt [18] showed that Batcher’s bitonic sorting algorithm can be applied to sorting on a mesh-connected parallel computer, once the indexing function is chosen. In [25] it is noted that a necessary condition for optimality is that a comparison-interchange on the jth bit be no more expensive than the (j+ 1)th bit, for all j. From (iii) of Lemma 3 we have that the “shuffled row-major” indexing scheme satisfies such condition, and leads to a complexity of (14(n−1) −8 log n)tR+ (2 log2n+ log n)tC. The algorithm for a 4 ×4 is illustrated below and in Figure 4, where by “well ordered” we reffer to the corresponding comparison directions from Figure 3. 220 R. Ceterchi, M.J. P´erez-Jim´enez, A.I. Tomescu In the case of a route(Px[B], Py[B]), only one communication graph is needed. The reason for not having supplementary rewritings is that such routings are done in parallel. The value from Px[B] is routed to Py[B] in parallel with the routing of Py[B] to a Bregister of a neighbor processors. Hence the number of symbols b in membrane yis the desired one Px[B]. [G, rules],such that (rBB) G⊆Gtotal,(x, y)∈E(G), rules((x, y)) = {(b, out)}. Consider now an internal comparison operation in processor Px,compare(Px, order) which places max(Px[A], Px[B]) in register Bif the order is ascending, or in register Aif the order is descending. This can be formalised as: [Id0, rules],such that Id0⊆Id, (x, x)∈E(Id0),(C) rules((x, x)) = ({ab →ab, a →b, b →b},if order is ascending, {ab →ab, a →a, b →a},if order is descending. For all s= 0,2dt/2e−1−1 denote with Gt s(sub-graphs of Gtotal) the communication graphs which simulate all parallel routing operations when comparing of bit t, in Algorithm 1. From the above considerations and the steps illustrated in Algorithm 3, we introduce the following algorithms: Algorithm 4 to generate the edges of a communication graph, and Algorithm 5 to generate sub-graphs of the Id where comparisons are to be performed: Input: integers k, t Output: communication graphs Gt s, for all s= 0,2dt/2e−1 set all E(Gt s)← ∅ for j←0to 22k−t−1do // for every Merge operation for l←0to 2t−dt/2e−1do // for every line in the Merge operation for s←0to 2dt/2e−1−1do // for each communication graph node = sRM(sRM−1 row(2tj) + l, sRM−1 col (2tj) + s) for q←1to 2dt/2e−1do // add the 2dt/2e−1edges E(Gt s)←E(Gt s)∪{(node, nextt(node))} node = nextt(node) Algorithm 4: Generating all communication graphs Gt sto compare on bit t Simulating the Bitonic Sort on a 2D-mesh with P Systems 221 Input: integers k, t Output: internal processing graphs Idt set all E(Idt)← ∅ for j←0to 22k−t−1do // for every Merge operation for l←0to 2t−dt/2e−1do // for every line in the Merge operation node = sRM(sRM−1 row(2tj) + l, sRM−1 col (2tj) + 2dt/2e−1) for q←1to 2dt/2e−1do E(Idt)←E(Idt)∪ {(node,node)} node = nextt(node) Algorithm 5: Generating internal processing graphs Idtto compare on bit t Let us denote with Gµthe sequence of graphs simulating the algoritm. Then Gµcan be obtained also algoritmically, using Algorithm 6: set Gµ←λ for i←1to 2kdo // compare interchange on bit t for t←idownto 1do // route to the second half for s←0to 2dt/2e−1−1do Gµ←Gµ·Gt s // compare internally Gµ←Gµ·Idt //route back to the first half for s←2dt/2e−1−1downto 0do Gµ←Gµ·Gt s Algorithm 6: Generating the sequence of graphs Gµfor simulating the bitonic sorting algoritm on the 2k×2k2D mesh where by λwe denote the empty sequence, and by “·” we denote the concatenation of two sequences. The above algorithms could be easily modified to produce a the finite sequence Rµof pairs [graph, rules] which simulates Algorithm 1. Keeping in mind the way routing and comparison operations are transformed into communication and rewriting rules of a P system (rAB, rBA, rBB, C), every time when adding an edge (x, y) to a graph G(subgraph of Gtotal or Id), the appropriate image rules((x, y)) should be specified. 222 R. Ceterchi, M.J. P´erez-Jim´enez, A.I. Tomescu 3.2 Bitonic sorting in one membrane We propose here a simulation of the bitonic sorting, which uses only one membrane. We will use (cooperative) symbol rewriting rules. The cooperation will be ’minimal’, i.e., of degree two, since we follow closely the algorithm, and thus the whole process is based on comparators. Consider an alphabet with 22ksymbols, V={v0, v1,· · · v22k−1}. We will call it the primary alphabet. We will consider also auxiliary alphabets, which we will specify in the sequel, in order to achieve sorting by rewritings. We want to sort in ascending order the sequence of distinct integers hx0, x1,· · · x22k−1i, codified over Vas the multiset w=v0x0v1x1···v22k−1x22k −1. We want to design a P system which, by rewritings acting in a maximal parallel manner and competing for objects, produces, from the initial configuration w, the configuration wf=v0σ(x0)v1σ(x1)· · · v22k−1σ(x22k −1), where σis the permutation which yeilds the total order, i.e., such that σ(x0)< σ(x1)<· · · < σ(x22k−1). Consider the alphabet Vas ordered, by the natural order given by the indices, and let v=v0v1· · · v22k−1be the alphabet word (see [1]), i.e., the word obtained by concatenating the letters of Vin their natural order. We call extended alphabet words over V, all words in V∗in which all the letters appear in their natural order. Note that both wand wf, the initial and the final configuration of our P system, are extended alphabet words. Actually, all the intermediate configurations over V will be of this type. Let Mj(u) denote the multiplicity of letter vjin a word u∈V∗. Then w=v0x0v1x1· · · v22k−1x22k −1=v0M0(w)···v22k−1M22k −1(w). Consider first the case n= 2 (k= 0). We have 2 integers codified over {v0, v1} as an extended alphabet word. Consider the auxiliary alphabets • {a, b}, for writing sources of a comparator • {c+, d+}, for writing targets of a ⊕-comparator • {c−, d−}, for writing targets of a ª-comparator Consider the rules: C⊕={v0→a, v1→b}∪{ab →c+d+, a →d+, b →d+}∪{c+→v0, d+→v1}. Simulating the Bitonic Sort on a 2D-mesh with P Systems 223 The first group rewrites all v0s to as and v1s to bs, the second group performs the comparison and produces the ascending order, and the last group rewrites back into the original alphabet. We have the sequence of configurations v0x0v1x1→ax0bx1→c+min(x0,x1)d+max(x0,x1)→v0min(x0,x1)v1max(x0,x1). Similarly, the rules: Cª={v0→a, v1→b} ∪ {ab →c−d−, a →c−, b →c−}∪{c−→v0, d−→v1}, achieve a descending comparator, generating the sequence of configurations v0x0v1x1→ax0bx1→c−max(x0,x1)d−min(x0,x1)→v0max(x0,x1)v1min(x0,x1). Lemma 4. On a two-letter alphabet, starting from an initial configuration w= v0x0v1x1, by applying rules in C⊕we obtain wfsuch that (Mi(wf))iis ascending, and by applying rules in Cªwe obtain wfsuch that (Mi(wf))iis descending. ¤ Note that rules C⊕simulate a Merge(0,1,+), and CªaMerge(0,1,−). We now want to simulate a whole family of merge operations done in parallel. We take 2 auxiliary alphabets, S+and S−to codify sources of + or −comparators, and another pair, T+and T−, to codify outputs (targets) of + or − comparators. We label them in a bijective correspondence with V. S+={s0+,· · · s+ 22k−1}, T+={t0+,· · · t+ 22k−1}, and similarly for −. (For the time being, only 4 copies of the initial alphabet. We will probably need 4 different copies for every stage, in order to keep them independent.) At Stage (1) we have to simulate Merge(2j, 2j+ 1, order), for all 0 ≤j≤ 22k−1−1, where order = + for all jeven, and order =−for all jodd. This is equivalent to: •Rewrite all symbols of Vinto start symbols for appropriate comparators, using the sets of rules {v2j→s2j+, v2j+1 →s2j+1+|0≤j≤22k−1−1 , j even}∪ ∪{v2j→s2j−, v2j+1 →s2j+1−|0≤j≤22k−1−1 , j odd}. •Apply in parallel the rewritings of symbols which correspond to the simulations of the comparators: {s2j+s2j+1+→t2j+t2j+1+, s2j+→t2j+1+, s2j+1+→t2j+1+| 0≤j≤22k−1−1 , j even}[ ∪{s2j−s2j+1−→t2j+t2j+1−, s2j−→t2j−, s2j+1−→t2j−| 0≤j≤22k−1−1 , j odd}. 224 R. Ceterchi, M.J. P´erez-Jim´enez, A.I. Tomescu •Rewrite back all symbols of T’s into V. {v2j←t2j+, v2j+1 ←t2j+1+|0≤j≤22k−1−1 , j even}∪ ∪{v2j←t2j−, v2j+1 ←t2j+1−|0≤j≤22k−1−1 , j odd}. The general scheme is as follows: Input: an extended alphabet word wover V Output: the extended alphabet word wfover V, such that hMi(wf)iiis ascending Sim-Stage(i) for t←idownto 1do Take 4 extra copies of the start and the terminal alphabets, S+ t,S− t, T+ t,T+ t, different for each value of t. For t’s smaller than iwe can re-use the alphabets of previous stages. forall j←0to 22k−t−1in parallel do if 2tjdiv 2iis even then order = ascending else order = descending // Simulate the calls Merge(2tj, 2tj+ 2t−1, order) (WF) Rewrite all symbols in Vwith the appropriate symbol in S+ t∪S− t. (C) Apply the rewritings which simulate the appropriate comparators. (WB) Rewrite back all symbols in T+ t∪T− tto symbols of V. end Sim-Bitonic-Sort for i←1to 2kdo Sim-Stage(i) end Algorithm 7: Simulating bitonic sort on an alphabet of 22kletters V The calls to Merge(2tj, 2tj+ 2t−1, order) are equivalent to parallel calls to Merge(x, y, order), where xand yare like in Lemma 3. The same result ensures us that, both the rewritings which feed the comparators, and the rewritings which implement the comparators can be done in parallel. For Merge(x, y, order =−), we use {sx−sy−→tx−ty−, sx−→tx−, sy−→tx−}. We propose the following sets of rules for simulating iteration tat Sim- Stage(i): (WF)Rewritings to S’s, with ∗=(+,if 2tjdiv 2iis even, −,if 2tjdiv 2iis odd, {vx→sx∗∈St∗|x∈[2tj, 2tj+ 2t−1),0≤j≤22k−t+1 −1}. Simulating the Bitonic Sort on a 2D-mesh with P Systems 225 (C)Rewritings which simulate the comparators, for appropriate pairs of indices: {sx+sy+→tx+ty+, sx+→ty+, sy+→ty+| x∈[2tj, 2tj+ 2t−1), y =x+ 2t−1,0≤j≤22k−t−1}, {sx−sy−→ty−tx−, sx−→tx−, sy−→tx−| x∈[2tj, 2tj+ 2t−1), y =x+ 2t−1,0≤j≤22k−t−1}. (WB)Rewritings from T’s: {vx←tx∗∈Tt∗|x∈[2tj, 2tj+ 2t−1),0≤j≤22k−t+1 −1}. 4 Conclusions and open problems We have presented a bitonic sorting algorithm which can be implemented on a 2D mesh of processors. The dependence between its performance and the choice of the indexing function still remains to be fully explored. However, we believe that we have proved some results which explain the choice of sRM as a “good” indexing function. We have not yet found in the literature a formal proof of the correctness of bitonic sorting, an equivalent, or an analogue of our Theorem 1. Much work remains to be done concerning the proposed simulations with P systems. The first simulation, derived in a “straightforward” manner from the functioning of the algorithm on the mesh, is inspired from work in [6], [8], [9], and [7], where the general framework was abstracted. It introduces a generative approach to the sequence of communication graphs, a feature to be explored in subsequent work. The second one is at the opposite pole: it requires no routings of values at all, just an appropriate codification of the symbols. It is in this area that other versions of the algorithm could be implemented, independent of the topology of a given structure, and the parallel features of the P systems can be compared against those of other computational devices. References 1. A. Alhazov, D. Sburlan, Static Sorting P Systems, Chapter 8 in Applications of Membrane Computing, G. Ciobanu, Gh. P˘aun, M.J. P´erez Jim´enez (Eds.), Springer 2006 2. J.J. Arulanandham, Implementing Bead–Sort with P Systems, Unconventional Models of Computation 2002 (C.S. Calude, M.J. Dinneen, F. Peper, Eds.), Lecture Notes in Computer Science 2509, Springer, 2002, 115–125. 3. K. Batcher, Sorting Networks and their Applications, Proc. of the AFIPS Spring Joint Computing Conf., Vol.32, 1968, pp. 307-314 4. R. Ceterchi, C. Mart´ın–Vide, Dynamic P Systems, Membrane Computing International Workshop, WMC-CdeA 2002, Curtea de Arge¸s, Romania, August 2002, Revised Papers (Gh. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron Eds.), LNCS 2597, Springer, Berln, 2003, 146-186 226 R. Ceterchi, M.J. P´erez-Jim´enez, A.I. Tomescu 5. R. Ceterchi, C. Mart´ın–Vide, P Systems with Communication for Static Sorting: GRLMC Report 26 (M. Cavaliere, C. Mart´ın–Vide, Gh. P˘aun, eds.), Rovira i Virgili University, Tarragona, 2003 6. R. Ceterchi, M.J. P´erez Jim´enez, On two-dimensional mesh networks and their simulation with P systems, LNCS 3365, 2005, 259–277 7. R. Ceterchi, M.J. P´erez Jim´enez, On simulating a class of parallel architectures, Intern. J. Found. Computer Sci., 17 (1), 2006, 91–110 8. R. Ceterchi, M.J. P´erez Jim´enez, Simulating Shuffle–Exchange Networks with P Systems, Proceedings of the Second Brainstorming Week on Membrane Computing, (Gh. P˘aun, A. Riscos, F. Sancho and A. Romero Eds.), Report RGNC 01/04, 2004, 117-129 9. R. Ceterchi, M.J. P´erez Jim´enez, A Perfect Shuffle Algorithm for Reduction Processes and its Simulation with P Systems, Proc. Inter. Conf. on Computers and Communications ICCC 2004 (I. Dzitac, T. Maghiar, C. Popescu Eds.), Baile Felix Spa - Oradea, Romania, Editura Univ. Oradea, 2004, 92-97 10. G. Ciobanu, Gh. P˘aun, M.J. P´erez Jim´enez (Eds.), Applications of Membrane Computing, Springer 2006 11. P.F. Corbett, I.D. Scherson, Sorting in Mesh Connected Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, Vol. 3, No. 5, 1992, 626 – 632 12. M. Dowd, Y. Perl, L. Rudolph, M. Saks, The periodic balanced sorting network, Journal of the ACM, 36, 4 (1989), 738–757 13. Y. Han, Y. Igarashi, M. Truszczynski, Indexing functions and time lower bounds for sorting on a mesh-connected computer, Discrete Applied Math., 36, 2 (1992), 141–152 14. D.E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, Reading, Mass., 1973 15. C. Layer, H.-J. Pfleiderer, A Reconfigurable Recurrent Bitonic Sorting Network for Concurrently Accessible Data, LNCS 3203, 2004, 648–657 16. D. Nassimi, S. Sahni, Bitonic sort on a mesh connected parallel computer, IEEE Transactions on Computers, C28(1), January 1979 17. D. Nassimi, S. Sahni, An Optimal Routing Algorithm for Mesh-Connected Parallel Computers, Journal of the ACM, Vol. 27, No. 1, January 1980, pp. 6-29 18. S.E. Orcutt, Computer Organization and algorithms for very high speed computations, Ph.D. Th., Stanford U.,Stanford, Calif., 1974, Chap. 2, pp. 20-23 19. Gh. P˘aun, Computing with Membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108–143 20. Gh. P˘aun, Membrane Computing. An Introduction, Springer-Verlag, Berlin, 2002 21. M.J. Quinn, Parallel Computing. Theory and Practice,, McGraw–Hill Series in Computer Science, 1994 22. K. Sado, Y. Igarashi, Some parallel sorts on a mesh-connected processor array and their time efficiency, J. Parallel and Distributed Computing, Vol. 3, No. 3, 1986, 398 – 410 23. H.J. Siegel, The universality of various types of SIMD machine interconnection networks, Proc. 4th Annual Symposium on Computer Architecture, 23–25, 1977 24. H.S. Stone, Parallel processing with the perfect shuffle, IEEE Transactions on Computers, C-20(2), 153–161, 1971 25. C.D. Thompson, H.T. Kung, Sorting on a mesh-connected parallel computer, Communications of the ACM, 20, 4 (1977), 263–271 26. The membrane computing web page: http://psystems.disco.unimib.it