Path: utzoo!attcan!uunet!lll-winken!ames!mailrus!cwjcc!gatech!hubcap!Math From: KOLOUTSAKIS%grcrvax1.bitnet@RELAY.CS.NET (Math Dept U of Crete Greece Michalis Kolountzakis) Newsgroups: comp.parallel Subject: Sorting on NxN Mesh. Message-ID: <4196@hubcap.UUCP> Date: 25 Jan 89 13:20:14 GMT Sender: fpst@hubcap.UUCP Lines: 144 Approved: parallel@hubcap.clemson.edu [ I found this on comp.theory. Thought it might interest the group. -- steve ] I would appreciate any suggestions, references or solutions for the following problem: We have a SIMD, 4-connected, NxN Mesh Connected Computer (MCC) and the following algorithm for sorting on it. The algorithm is an extension of the so called "odd-even transposition sorting" (OETS) algorithm for a sequence of N processors: P <--> P <--> P <--> ... <--> P 0 1 2 N-1 OETS works by coupling all processors and performing a compare-and- then-possibly-swap operation on every pair of processors. In even time moments the set P={0,...,N-1} is partitioned in {(0,1), (2,3), ..., (2i,2i+1), ...} and in odd time moments P is parti- tioned in {(1,2), (3,4), ..., (2i-1,2i) ,...} (P and P are not always 0 N-1 in some pair). It is almost obvious that OETS is a sorting algorithm for the sequence of processors but it takes some time to prove that it is linear in N. So, in OETS, each prossesor compares its contents, first with its left neighbour and then with its right neighbour and so on. In two dimensions the most reasonable extension of OETS would be to couple each processor first with its upper neighbour, then with its lower, its left and finally irs right neighbour and perform a compare- and-then-possibly-swap operation. More precisely in time T the NxN grid G={(i,j): i, j in P /* i for rows */} is partitioned in { <(2i-1,j), (2i, j)> for all i, j } when T mod 4 = 0 { <(2i,j), (2i+1,j)> for all i, j} when T mod 4 = 1 { <(i,2j-1), (i,2j)> for all i, j} when T mod 4 = 2 and { <(i,2j), (i,2j+1)> for all i, j} when T mod 4 = 3, and all these pairs of processors compare their contents and possibly swap them. It is obvious again that it is a sorting algorithm but what is its time complexity? Is it linear ? is the question. I suspect it is not, because if it were no other sorting alg. for the NxN mesh should have been invented; this seems far simpler than any other I have seen. But I do not have a bad example for this alg. Do you? Thanks in advance Michalis Kolountzakis, Mathematics Dept, Univ. of Crete, Greece e-mail: koloutsa@grcrvax1.bitnet ------------------------------------------------------------------------ Date: Tue, 24 Jan 89 21:28 O From: Michalis Kolountzakis(Math Dept U of Crete Greece) Subject: More on sorting on the NxN mesh To: theorynt@ndsuvm1 On the problem I have just mailed to the list (Sorting on the Mesh Connected Computer) I have not given the desirable order on the Mesh for which the algorithm I have described is supposed to work. I cannot expect this order to be any one for which "local order" does not imply "global order", e.g. it cannot be the row-major (lexicographic) order. If we want big elements to go up and left, then the following configuration of values 4 2 3 1 for a 2x2 Mesh is not ordered (2 and 3 should be swapped) but it is locally consistent with the row-major order (that is, every element in the Mesh is consistent with its neighbours.) An order for the Mesh which is good for our purposes is the "snake-like" order for which such a configuration cannot exist and so we can prove that the proposed algorithm is indeed a sorting algorithm. Michalis Kolountzakis, Math. Dept, Univ. of Crete, Greece I would appreciate any suggestions, references or solutions for the following problem: We have a SIMD, 4-connected, NxN Mesh Connected Computer (MCC) and the following algorithm for sorting on it. The algorithm is an extension of the so called "odd-even transposition sorting" (OETS) algorithm for a sequence of N processors: P <--> P <--> P <--> ... <--> P 0 1 2 N-1 OETS works by coupling all processors and performing a compare-and- then-possibly-swap operation on every pair of processors. In even time moments the set P={0,...,N-1} is partitioned in {(0,1), (2,3), ..., (2i,2i+1), ...} and in odd time moments P is parti- tioned in {(1,2), (3,4), ..., (2i-1,2i) ,...} (P and P are not always 0 N-1 in some pair). It is almost obvious that OETS is a sorting algorithm for the sequence of processors but it takes some time to prove that it is linear in N. So, in OETS, each prossesor compares its contents, first with its left neighbour and then with its right neighbour and so on. In two dimensions the most reasonable extension of OETS would be to couple each processor first with its upper neighbour, then with its lower, its left and finally irs right neighbour and perform a compare- and-then-possibly-swap operation. More precisely in time T the NxN grid G={(i,j): i, j in P /* i for rows */} is partitioned in { <(2i-1,j), (2i, j)> for all i, j } when T mod 4 = 0 { <(2i,j), (2i+1,j)> for all i, j} when T mod 4 = 1 { <(i,2j-1), (i,2j)> for all i, j} when T mod 4 = 2 and { <(i,2j), (i,2j+1)> for all i, j} when T mod 4 = 3, and all these pairs of processors compare their contents and possibly swap them. It is obvious again that it is a sorting algorithm but what is its time complexity? Is it linear ? is the question. I suspect it is not, because if it were no other sorting alg. for the NxN mesh should have been invented; this seems far simpler than any other I have seen. But I do not have a bad example for this alg. Do you? Thanks in advance Michalis Kolountzakis, Mathematics Dept, Univ. of Crete, Greece e-mail: koloutsa@grcrvax1.bitnet ------------------------------------------------------------------------ Date: Tue, 24 Jan 89 21:28 O From: Michalis Kolountzakis(Math Dept U of Crete Greece) Subject: More on sorting on the NxN mesh To: theorynt@ndsuvm1 On the problem I have just mailed to the list (Sorting on the Mesh Connected Computer) I have not given the desirable order on the Mesh for which the algorithm I have described is supposed to work. I cannot expect this order to be any one for which "local order" does not imply "global order", e.g. it cannot be the row-major (lexicographic) order. If we want big elements to go up and left, then the following configuration of values 4 2 3 1 for a 2x2 Mesh is not ordered (2 and 3 should be swapped) but it is locally consistent with the row-major order (that is, every element in the Mesh is consistent with its neighbours.) An order for the Mesh which is good for our purposes is the "snake-like" order for which such a configuration cannot exist and so we can prove that the proposed algorithm is indeed a sorting algorithm. Michalis Kolountzakis, Math. Dept, Univ. of Crete, Greece