Sorting Omega Networks Simulated with P Systems: Optimal Data Layouts

Sorting Omega Networks Simulated with P Systems: Optimal Data Layouts 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 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mails: [email protected], [email protected], [email protected] Summary. The paper introduces some sorting networks and their simulation with P systems, in which each processor/membrane can hold more than one piece of data, and perform operations on them internally. Several data layouts are discussed in this context, and an optimal one is proposed, together with its implementation as a P system with dynamic communication graphs. 1 Introduction Paper [9] proposed two models to sort a sequence of Nnumbers, based on the bitonic sorting network. The first one consisted of Nmembranes, each storing two numbers; one number was an element of the sequence, and the other one was an auxiliary register used to route values. A number xwas codified as the number of appearances of a symbol ain each membrane. Moreover, the membranes were disposed on a 2D-mesh, where only communication between neighbor membranes on the mesh are permitted. This model, using a variant of P Systems, called P systems with dynamic communication graphs, (see [8]), follows closely the implementation of the bitonic sort on the 2D-mesh. The second model consisted of only one membrane, where all the Nnumbers were encoded as occurrences of Ndifferent symbols. Restrictions on communication were no longer imposed, as if the underlying communication graph were the complete graph. In this paper we introduce a model in between the two. First of all, observe that the first model has the advantage of a codifying alphabet of fixed size, while the second has the advantage of a small communication overhead. The model we put forth in this paper captures these two benefits. Each membrane holds a fixed number of values, and each of the membranes can communicate with any other. 80 R. Ceterchi et al. Additionally, in order to minimize the communication between membranes, we use a periodic remap of values to membranes, according to the steps of the omega network. The problem of mapping values to processors has been previously addressed in the context of parallel sorting algorithms. The bitonic sorting network, which can sort Nkeys in time O(log2N), is probably one of the most well-known parallel sorting algorithms. However, modern architectures differ greatly from the theoretical models under which such good results were obtained. As coarse-grained processors can store internally more than one value, the following problem arises: how to map Nkeys to Pprocessors (N > P), such that inter-processor communication is minimized. In the bitonic sorting algorithm, and for N≥P2, the solution given in [13, 14] consisted in alternating a blocked layout with a cyclic layout, performing thus the minimal number of remaps. This paper gives an optimal mapping strategy for the bitonic sort for any N > P, and then applies this result to P Systems. The paper is organized as follows. Section 2 presents preliminaries on bitonic sorting networks and defines omega networks. Section 3 approaches the problem of mapping Nkeys among Pprocessors, each processor manipulating n=N/P keys, such that overall communication is minimized. Optimal data layouts for the omega network are proposed along the lines of [20], and some essential results are proved about them. Section 4 discusses about internal processing in one processor, and how we model it in our implementation with P systems. Section 5 introduces the P system which simulates the omega network with optimal data layouts, and the algorithms which generate the sequence of dynamic communication graphs of this model. Complexity issues are addressed at the end of Sections 3 and 5. 2 Preliminaries on Bitonic Sorting Networks and Omega Networks A bitonic sequence is a concatenation of two monotonic sequences, one ascending, and the other one descending, or a sequence such that a cyclic shift of its elements would put them in such a form. The key components of a bitonic network are the bitonic splitters and the bitonic mergers. The splitter of size Ntakes as input a bitonic sequence of length Nand partitions it in two bitonic sequences of equal length, such that all the elements in the first sequence are smaller than (or greater than) all the elements in the second sequence. A bitonic merger of size Nconsists of a splitter of size N and of two mergers of size N/2, of opposite direction. It accepts as input a bitonic sequence and sorts it in ascending or descending order (direction). As any sequence of two numbers is bitonic, the sorting network uses bitonic mergers of increasing size and alternating direction to construct bitonic sequences of increasing length. The last such merger, of size N, renders the whole sequence of Nnumbers sorted. Sorting Omega Networks Simulated with P Systems 81 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Fig. 1. A bitonic sorting network of size N= 8. The network can be partitioned in three stages, each containing bitonic mergers of size 2, 4, and 8, respectively. 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 a b c=min(a,b) d=max(a,b) a b c=max(a,b) d=min(a,b) a b c=(1-s)a+sb d=sa+(1-s)b (a) Increasing comparator 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 a b c=min(a,b) d=max(a,b) a b c=max(a,b) d=min(a,b) a b c=(1-s)a+sb d=sa+(1-s)b (b) Decreasing comparator Fig. 2. Network devices Following [15] it is customary to represent a network as an ordered set of Nlines (wires) connected by a set of compare-exchange devices (comparators, for brevity). A comparator has two input terminals, aand b, and produces two output terminals cand d. If the comparator is increasing, Fig. 2(a), then c= min(a, b) and d= max(a, b), while if the comparator is decreasing, Fig. 2(b), c= max(a, b) and d= min(a, b). A bitonic sorting network for N= 8 is represented in Fig. 1. We introduce some more notations regarding the serial and parallel connections of networks T1and T2, of size N. Their serial connection, T1T2, is a network in which the i-th output terminal of T1is connected to the i-th input terminal of T2. The parallel connection, T1◦T2, is the union of T1and T2, with terminal iof T1 becoming terminal iof T1◦T2, and terminal iof T2becoming terminal i+Nof T1◦T2(i= 0, . . . , N −1). Definition 1 (Omega network, Fig. 3(d)). Let Dk,k≥1be a one-step network of N= 2klines with a device between the pair of lines (i, i +N/2), for i= 0 . . . N/2−1. Then the omega network OMkis recursively defined as OMk=Dk(OMk−1◦OMk−1). In [6] the striking similarity between the bitonic merger (Fig. 3(a), 3(b)) and the balanced merger (Fig. 3(c)) is investigated. Although prior research [11] showed that there is no permutation of lines to transform the bitonic merger into a balanced merger, a framework is developed under which it is shown that the two 82 R. Ceterchi et al. 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 a b c=min(a,b) d=max(a,b) a b c=max(a,b) d=min(a,b) a b c=(1-s)a+sb d=sa+(1-s)b 0 1 2 3 4 5 6 7 0 1 3 2 6 7 5 4 (a) The bitonic merger - classical representation 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 a b c=min(a,b) d=max(a,b) a b c=max(a,b) d=min(a,b) a b c=(1-s)a+sb d=sa+(1-s)b 0 1 2 3 4 5 6 7 0 1 3 2 6 7 5 4 (b) The bitonic merger - after a permutation of lines 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 a b c=min(a,b) d=max(a,b) a b c=max(a,b) d=min(a,b) a b c=(1-s)a+sb d=sa+(1-s)b 0 1 2 3 4 5 6 7 0 1 3 2 6 7 5 4 0 1 2 3 4 5 6 7 (c) The balanced merger 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 a b c=min(a,b) d=max(a,b) a b c=max(a,b) d=min(a,b) a b c=(1-s)a+sb d=sa+(1-s)b 0 1 2 3 4 5 6 0 1 3 2 6 7 5 4 0 1 2 3 4 5 6 7 D3OM2 OM2 (d) The omega network OM3 Fig. 3. The bitonic merger, the balanced merger, and the omega network of size 8 mergers are isomorphic graphs, also isomorphic to the graph of the omega network (Fig. 3(d)). As a serial connection of log Nidentical networks in the class of omega networks forms a sorting network [6], in what follows we will concentrate mainly on the omega network. 3 How They Communicate A sorting network is a fine-grained theoretical model, containing exactly one input key on each wire. Additionally, comparators require communication between wires, Sorting Omega Networks Simulated with P Systems 83 which can sometimes be more time consuming than the comparison operation itself [1, 3, 10, 16]. When redesigning parallel sorting algorithms for coarse-grained PRAM, one has to pay particular attention to both communication and computation. Given Nkeys and Pprocessors (N > P), we have to map n=N/P keys to each processor, such that overall communication is minimized. Ionescu and Schauser [13, 14] investigated this problem for the bitonic sorting algorithm. As initially suggested in [10], they proposed a smart periodical switch between a blocked layout and a cyclic layout. They observed that in each stage of the sorting algorithm, the last log nsteps can be performed locally under a blocked layout, while under the cyclic layout the first log nsteps are local. A necessary condition for the two layouts to span enough depth to cover an entire stage of the network is N≥P2. In addition, the two layouts are particular to the sorting network being implemented. We shall see, for example, that the balanced merger [11, 12], which, as the bitonic merger, belongs to the class of omega networks, also admits data layouts optimizing overall communication. An approach from the opposite side was put forth by Lee and Batcher [17]. They used a parity strategy for a shared-memory model with N= 2Pto store even-parity keys in local memory, while only odd-parity keys were recirculated. This decreased by a factor of 2 the number of shared memory references. The main contribution of this paper is a general scheme to map Nvalues to P processors, for any N > P and for any sorting network with the topology of the omega network. Our idea captures the essence from the alternating smart layout of [14], and makes it generally applicable, even when N < P2. The number of data layouts is no longer two, but it depends on the granularity of the processors. 3.1 Optimal Data Layouts for the Omega Network In the following, without explicitly mentioning it, we assume we have to sort N= 2kkeys using Pprocessors, N > P, each processor holding n=N/P keys. Any number i∈ {0, . . . , 2k−1}has a bit representation i=a1a2· · · ak,a1being the most significant bit, and akthe least significant one. To simplify notation, we say that a sequence of bits aj· · · ai, where i, j ∈ {1, . . . , k}and j > i, stands for the void sequence. The number of parallel steps of OMkis k, and step tof the omega network OMkcontains devices linking lines whose bit representations differ of bit t, with 1 ≤t≤k. For any t∈ {1, . . . , k}, consider the function bct:{0,1, . . . , 2k−1} −→ {0,1, . . . , 2k−1}, the bit complement of the t-th bit, defined by bct(a1a2· · · at· · · ak) = a1a2· · · ¯at· · · ak. The function bctis injective and idempotent. First, we give a formal definition of a data layout. Definition 2 (Data layout). A data layout of Nvalues to Pprocessors is a function D:{0, . . . , N −1} → {0, . . . , P −1}. We introduce the following data layouts, as suggested in [10, 14]. 84 R. Ceterchi et al. 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 (a) An omega network on size 32. Lines marked with same shape are assigned to the same processor in one data layout. 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 0 0 0 0 0 = 0 1 0 0 0 0 = 16 0 1 0 0 0 = 8 1 1 0 0 0 = 24 0 0 0 0 0 = 0 0 0 1 0 0 = 4 0 0 0 1 0 = 2 0 0 1 1 0 = 6 0 0 0 0 0 = 0 0 0 0 1 0 = 2 0 0 0 0 1 = 1 0 0 0 1 1 = 3 (b) Keys mapped to processor 0 in each of the three data layouts Fig. 4. Three data layouts for the omega network OM5. Definition 3 (Blocked layout). A blocked layout for mapping Nkeys on P processors is a function Db:{0, . . . , N −1} → {0, . . . , P −1}, such that Db(i) = bi/nc, where n=N/P. Definition 4 (Cyclic layout). A cyclic layout for mapping Nkeys on Pprocessors is a function Dc:{0, . . . , N −1}→{0, . . . , P −1}, such that Dc(i) = imod P. We note that Definition 5 in [13], and the definition for the cyclic layout indicated in Section 2.1 of [14] are incorrect, since if we map the i-th key to the imod nprocessor, where n=N/P, we have that n≤P, which implies N≤P2, which clearly is not the case considered. In a blocked layout, the first log N−log nsteps require remote communication, while the last log nsteps are local. In a cyclic layout, the situation is reversed: the first log N−log nsteps are local, while the last log nsteps are remote. The idea Sorting Omega Networks Simulated with P Systems 85 proposed in [14] when mapping N≥P2values in the bitonic sort is to periodically switch between the two layouts, such that all steps are local. Moreover, as the stages in a bitonic sort have increasing size, the author proposes an improved “smart” remap such that a layout spans through multiple stages of the algorithm, achieving a total of log P+ 1 remaps. Our paper better highlights the reasoning behind these remaps, in the case of the bitonic sort. Consider the omega network OMk, and consider we choose to map key 0 to processor 0. If each processor can hold 2mvalues, which other keys are mapped to processor 0? As we can see, at step 1 we have a device linking line 0 with line 0 + 2k−1. At step 2 we have a device linking line 0 with line 2k−2, and a device linking line 2k−1and line 2k−1+ 2k−2. We also note that in step 1 lines 2k−2and 2k−1+ 2k−2were also linked with a device. We continue until step m, where we identify 2mlines linked by 2m−1devices. It would be natural to map these lines to processor 0, as all comparisons at step mare local. However, one more problem remains: all comparisons at stages 0 through m−1 are also local? As we shall see, the answer is yes. The following lemma is straightforward from the definition of OMk. Lemma 1. At each step 1≤t≤kof OMk, and for any 0≤i < 2k, line iis linked by a device only with line bct(i). Lemma 2. In OMk, for any 0≤i < 2k−m,1≤m≤kand 0≤t≤k−m, in steps t+1, . . . , t+mthere is no device linking lines in the set Pt,m i={a1a2· · · ak| a1· · · atat+m+1 · · · ak=i, where a1· · · akis a bit representation}with lines from {0, . . . , 2k−1} \ Pt,m i. Proof. Suppose there are 1 ≤r≤m,l∈Pt,m iand l0/∈Pt,m isuch that at step t+rthere is a device linking land l0. From Lemma 1 we have that l0=bct+r(l), which implies l0∈Pt,m i, a contradiction. We can therefore derive the data layouts for the omega network. Suppose we have N= 2k,n= 2m, and P= 2k−m. We first assign to each processor Piall values in the set P0,m i, for 0 ≤i≤P−1. By Lemma 2 we have that the first log n=msteps are entirely local. After msteps, we remap to each processor Pi all the values in the set Pm,m i, and perform the next mstages locally, and so on. We can now give the definition of our proposed data layout. Definition 5. Given N= 2kkeys and P= 2k−mprocessors, which can store n= 2mvalues, m≥1, the sequence of optimal data layouts consists of dlog N/ log ne= dk/medata layouts. In each data layout Ds,0≤s≤ dk/me − 1, values in the set Psm,m iare mapped to processor Pi, for all 0≤i≤2k−m. More formally, for any 0≤u < 2ksuch that u∈Psm,m i, we have Ds(u) = i. The following is a consequence of Lemma 1 of [14]. Lemma 3. The maximum number of successive steps of the omega network that can be executed locally, under any data layout is log n, where n=N/P. 86 R. Ceterchi et al. Membrane 001 1 = 0 0 0 0 1 9 = 0 1 0 0 1 17 = 1 0 0 0 1 25 = 1 1 0 0 1 Membrane 010 2 = 0 0 0 1 0 10 = 0 1 0 1 0 18 = 1 0 0 1 0 26 = 1 1 0 1 0 Membrane 011 3 = 0 0 0 1 1 11 = 0 1 0 1 1 19 = 1 0 0 1 1 27 = 1 1 0 1 1 Membrane 100 4 = 0 0 1 0 0 12 = 0 1 1 0 0 20 = 1 0 1 0 0 28 = 1 1 1 0 0 Membrane 101 5 = 0 0 1 0 1 13 = 0 1 1 0 1 21 = 1 0 1 0 1 29 = 1 1 1 0 1 Membrane 110 6 = 0 0 1 1 0 14 = 0 1 1 1 0 22 = 1 0 1 1 0 30 = 1 1 1 1 0 Membrane 111 7 = 0 0 1 1 1 15 = 0 1 1 1 1 23 = 1 0 1 1 1 31 = 1 1 1 1 1 Membrane 000 0 = 0 0 0 0 0 8 = 0 1 0 0 0 16 = 1 0 0 0 0 24 = 1 1 0 0 0 Membrane 000 0 = 0 0 0 0 0 2 = 0 0 0 1 0 4 = 0 0 1 0 0 6 = 0 0 1 1 0 Membrane 001 1 = 0 0 0 0 1 3 = 0 0 0 1 1 5 = 0 0 1 0 1 7 = 0 0 1 1 1 Membrane 010 8 = 0 1 0 0 0 10 = 0 1 0 1 0 12 = 0 1 1 0 0 14 = 0 1 1 1 0 Membrane 011 9 = 0 1 0 0 1 11 = 0 1 0 1 1 13 = 0 1 1 0 1 15 = 0 1 1 1 1 Membrane 100 16 = 1 0 0 0 0 18 = 1 0 0 1 0 20 = 1 0 1 0 0 22 = 1 0 1 1 0 Membrane 101 17 = 1 0 0 0 1 19 = 1 0 0 1 1 21 = 1 0 1 0 1 23 = 1 0 1 1 1 Membrane 110 24 = 1 1 0 0 0 26 = 1 1 0 1 0 28 = 1 1 1 0 0 30 = 1 1 1 1 0 Membrane 111 25 = 1 1 0 0 1 27 = 1 1 0 1 1 29 = 1 1 1 0 1 31 = 1 1 1 1 1 Membrane 000 0 = 0 0 0 0 0 1 = 0 0 0 0 1 2 = 0 0 0 1 0 3 = 0 0 0 1 1 Membrane 001 4 = 0 0 1 0 0 5 = 0 0 1 0 1 6 = 0 0 1 1 0 7 = 0 0 1 1 1 Membrane 010 8 = 0 1 0 0 0 9 = 0 1 0 0 1 10 = 0 1 0 1 0 11 = 0 1 0 1 1 Membrane 011 12 = 0 1 1 0 0 13 = 0 1 1 0 1 14 = 0 1 1 1 0 15 = 0 1 1 1 1 Membrane 100 16 = 1 0 0 0 0 17 = 1 0 0 0 1 18 = 1 0 0 1 0 19 = 1 0 0 1 1 Membrane 101 20 = 1 0 1 0 0 21 = 1 0 1 0 1 22 = 1 0 1 1 0 23 = 1 0 1 1 1 Membrane 110 24 = 1 1 0 0 0 25 = 1 1 0 0 1 26 = 1 1 0 1 0 27 = 1 1 0 1 1 Membrane 111 28 = 1 1 1 0 0 29 = 1 1 1 0 1 30 = 1 1 1 1 0 31 = 1 1 1 1 1 Data layout 1 Data layout 2 Data layout 3 Fig. 5. The three data layouts for the omega network in Figure 4(a). Sorting Omega Networks Simulated with P Systems 87 In each data layout Ds, 0 ≤s≤ dk/me − 2, log n=msteps are local. For s=dk/me − 1, the last kmod msteps of the network are local. From Lemma 3 we have that the proposed data layouts for the omega network are optimal. In the case N≥P2, we notice that 2m > k, hence two data layouts are enough to cover the whole omega network. However, they do not coincide with Dbor Dc, as in the blocked layout, the last mstages are local, while in the cyclic layout, the first k−mstages are local. 3.2 Computation Complexity In each data layout, a processor holds nvalues and performs log nsteps locally, taking time O(nlog n). As we have dlog N/ log nedata layouts, we get an overall time complexity of the omega network of O(nlog N). From [6] we have that a serial connection of log Nomega networks of size Nis enough to sort a sequence of Nnumbers. Hence, the complexity to sort Nnumbers using Pprocessors, each holding n=N/P values, using our proposed data layouts, is O(nlog2N). This remark has a quite profound significance. In the fine-grained theoretical model we have n= 1, and its complexity is O(log2N). The complexity of the network using a more coarse-grained model depends linearly on the degree of parallelism of the model. At the opposite end, when n=Nand the entire sorting network is simulated locally, we have a complexity of O(Nlog2N), which is worse than O(Nlog N), the complexity of most sequential sorting algorithms. It would be desirable to choose nsuch that this bound is not surpassed in the parallel model. We impose nlog2N≤Nlog N, which implies n≤N/ log N. An algorithm to find the minimum of a bitonic sequence of size nin time O(log n), was introduced in [14]. This gives a time complexity of each data layout of O(n). In the case of a network obtained from a serial connection of bitonic mergers, this observation gives an overall time complexity of O(n log nlog2N). 4 What Happens Inside One Processor/Membrane One processor (and the membrane which simulates it) will be capable of holding n=N/P = 2m, pieces of data. We label the data with indices in the set {0,1,· · · , n −1}. For any such index we consider its writing as a binary string of length m, for instance i=x1x2· · · xt· · · xm. Inside one processor, several comparisons are performed, in parallel, between the npieces of data, in the following manner: for every bit t, (starting with 1, the most significant bit, and ending with m) we compare and exchange if necessary (to obtain an increasing order) all pairs of values codified with aiand abct(i). More precisely, we have the following algorithm to be performed inside each processor/membrane: