Instruction systolic array (ISA)

Sorting

 up

Odd-even transposition sort

In two-dimensional sorting algorithms, the standard operations are sorting rows and columns with odd-even transposition sort. In Figure 1, an odd and an even step of odd-even transposition sort are shown. The arrows indicate a comparison-exchange operation that is performed by two adjacent processors. In order to sort a row of length n, there are n steps necessary.

Figure 1: Odd and even step of odd-even transposition sort
Figure 1: Odd and even step of odd-even transposition sort

On the ISA a comparison-exchange operation can be realized by the following instructions executed in two horizontally adjacent processors

C:=min(C, CE)       C:=max(C, CW)

The instructions must be executed simultaneously. Each of the processors compares the contents of its own communication register with the contents of its neighbour's communication register. CE is the communication register of the eastern neighbour, CW is the communication register of the western neighbour. The result of the comparison is written into the communication register.

Figure 2 shows an ISA program that performs two steps of odd-even transposition sort in the first row of the processor array. Each step of odd-even transposition sort requires two instructions.

Enable Java to see an animation of this figure
Two steps of odd-even transposition sort  in the first row
Figure 2: Two steps of odd-even transposition sort in the first row

In the programming language Laisa, an odd and an even step of odd-even transposition sort are expressed in the following way.

procedure row_odd_step(n : integer; s : selector);
{ performs an odd step of odd-even transposition sort
  in the rows specified by selector s }
begin(n)
    < max C, CW, C; s; 0(01)*0 >;
    < min C, CE, C; s; 0(10)*0 >;
end;

procedure row_even_step(n : integer; s : selector);
{ performs an even step of odd-even transposition sort
  in the rows specified by selector s }
begin(n)
    < max C, CW, C; s; (01)* >;
    < min C, CE, C; s; (10)* >;
end;

Programs for sorting a row and a column, respectively, are given in the following.

procedure row_oets_steps(n : integer; k : integer; s : selector);
{ applies k steps of odd-even transposition sort
  to the rows specified by selector s }
begin(n)
    repeat k/2 times 
    begin
        row_odd_step(n, s);
        row_even_step(n, s);
    end
end;

procedure col_oets_steps(n : integer; k : integer; s : selector);
{ applies k steps of odd-even transposition sort
  to the columns specified by selector s }
begin(n)
    mirror(row_oets_steps(n, k, s));
end;

procedure row_sort(n : integer; s : selector);
{ sorts a row with odd-even transposition sort }
begin(n)
    row_oets_steps(n, n, s);
end;

procedure col_sort(n : integer; s : selector);
{ sorts a column with odd-even transposition sort }
begin(n)
    col_oets_steps(n, n, s);
end;

Implementation of comparison-exchange

Actually, the standard instruction set of the ISA does not include a min- and a max-instruction. This is the case because operands are processed bit-serially with the least significant bit first, but a min- and a max-instruction would require the most significant bit first.

Therefore, a comparison-exchange is implemented by a subtraction followed by a conditional exchange. This requires four instead of two instructions.

procedure row_odd_step(n : integer; s : selector);
{ performs an odd step of odd-even transposition sort
  in the rows specified by selector s }
begin(n)
    < sub C, CW, 0; s; 0(01)*0 >;
    < sub CE, C, 0; s; 0(10)*0 >;
    < ifn CW, C, C; s; 0(01)*0 >;
    < ifn CE, C, C; s; 0(10)*0 >;
end;

According to the column selector bits, the first two and the second two instructions are performed simultaneously in adjacent processors. If the two values in the adjacent processors are in the wrong order, the results of the subtractions of the first two instructions are negative. This means that the N-flags are set in these processors, the results are ignored. In the subsequent two instructions, the values are exchanged if the N-flags are set.

Two-dimensional sorting algorithm

In order to sort the whole array, we use the sorting algorithm 4-way mergesort [Schi 87].

This algorithm requires sorting of some rows from right to left. This can be achieved with the same instructions that are used for sorting from left to right if the corresponding values are inverted before and after sorting. The following procedure inverts the contents of the communication register in the rows specified by selector s.

procedure row_invert(n : integer, s : selector);
{ inverts the contents of the communication register
  in the rows specified by selector s } 
begin(n)
    < sub 0, C, C; s; 1* >;    { C:=0-C }
end;

The algorithm recursively merges subarrays of size n/2 × n/2. The subarrays have to be roughly sorted in the sense that each value is already in its proper row (but not necessarily at its proper position within this row).

procedure merge(n : integer);
{ merges four roughly sorted n/2xn/2 arrays
  to a roughly sorted nxn array}
begin(n)
    row_invert(n, [1..n/2]);
    row_sort(n, 1*);
    row_invert(n, [1..n/2]);

    col_sort(n, 1*);

    row_invert(n, (01)*); 
    row_sort(n, 1*);
    row_invert(n, (01)*); 

    col_oets_steps(n, n/2, 1*);
end;

procedure roughsort(n : integer);
{ roughly sorts an nxn array }
begin(n)
    replicate(roughsort(n/2), 2, 2);
    merge(n);
end;

procedure sort(n : integer);
{ sorts an nxn array }
begin(n)
    roughsort(n);
    row_sort(n, 1*);
end;

 

Next:   [Processor architecture]  [References]  or   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 09.12.2004   Updated: 20.06.2018
Valid HTML 4.01 Transitional