2.4. Sorting

A number of different SIMD algorithms exist for the problem of sorting. The `odd-even transposition sort' (OETS) is presented here as a representative, which can be understood as a parallel version of bubble-sort. OETS sorts n data elements with n PEs in n steps. Figure 17 shows the progression of the parallel algorithm. Every PE holds one of the numbers to be sorted. During processing, the algorithm differentiates between odd and even steps. In odd steps, all of the PEs with odd identification numbers compare their element values with that of their right neighbor (PEs: 1-2, 3-4, 5-6, etc.) and carry out a data exchange if the value of their own element is larger than that the one of their neighbor. In the even steps, all of the PEs with even identification numbers carry out an analogous comparison and, if necessary, a data exchange with their right neighbor (PEs: 2-3, 4-5, 6-7, etc.). After n iterations, the list is sorted. The right part of Figure 17 visualizes the algorithm, with each line in the image representing the current state of the list of PEs, while the time is progressing from top to bottom. Each pixel in a line is represented by a gray value according to its data value (low values are dark, high values are bright). In the beginning (top line), the gray values (data values) are unsorted, while they become slowly disentangled during progression of the algorithm, until the bottom line contains the gray values in perfect order. The movement of individual cells to the left or right reminds of bubble-sort.

Figure 17 Example of odd-even transposition sorting

In the Parallaxis program, first the variable lhs determines whether a PE is in the role of the left or the right partner of a comparison. This role changes for each loop iteration. During each pass, the PEs get the data values of their left and right neighbor in l and r, respectively. The partner on the left-hand side uses the right neighbor's value for comparison, while the partner on the right-hand side uses the value of its left neighbor. The complicated comparison `lhs = (comp<val)' is true for the left PE partner when the right comparison value is greater than its own value; it is also true for the right PE partner, if the left comparison value is smaller than its own value. So a single key comparison is sufficient for all PEs to find out where swapping of data values are required. By applying a more complex compound topology, the program could be optimized further, such that only a single data exchange operation would be required for each pass through the loop.

MODULE sort;  (* Odd-Even Transposition Sorting *) 
CONST n = 10; 
CONFIGURATION list [1..n]; 
CONNECTION left : list[i] <-> list [i-1] :right;
VAR step    : INTEGER; 
    a       : ARRAY[1..n] OF INTEGER; 
    val,comp: list OF INTEGER; 
    lhs     : list OF BOOLEAN; 


BEGIN 
  WriteString('Enter 10 values: ');
  FOR step:=1 TO n DO ReadInt(a[step]) END; 
  LOAD(val,a); 
  lhs := ODD(ID(list));  (* PE is left-hand-side of comparison *) 
  FOR step:=1 TO n DO 
    IF lhs THEN comp := RECEIVE.left(val) 
           ELSE comp := RECEIVE.right(val) 
    END; 
    IF lhs = (comp<val) THEN val:=comp END;(* lhs & (comp< val) *) 
    lhs := NOT lhs;                     (* or rhs & (comp>=val) *) 
  END;                              
  STORE(val,a); 
  FOR step:=1 TO n DO WriteInt(a[step],10); WriteLn END; 
END sort.
Figure 18 shows the runtiof the OETS sorting algorithm for sorting of 1000 numbers. The PE load curve shows a continuous high processor utilization.

active PEs
time in program steps

Figure 18 Processor utilization of the sorting algorithm

[ Previous Page | Table of Contents | Next Page ]