// ************************************************************************** // // // // eses eses // // eses eses // // eses eseses esesese eses Embedded Systems Group // // ese ese ese ese ese // // ese eseseses eseseses ese Department of Computer Science // // eses eses ese eses // // eses eseses eseseses eses University of Kaiserslautern // // eses eses // // // // ************************************************************************** // // ShearSort is parallel sorting algorithm that is performed on a MxN array. // // The sorted sequence will finally be mapped to the array in a snake-like // // row major indexing scheme, as eg. // // // // 01 02 03 04 // // 08 07 06 05 // // 09 10 11 12 // // 16 15 14 13 // // // // The algorithm is due to [Scherson & Sen, 1989], and works by performing // // a loop of column sorts and row sorts until the array is sorted. The // // version below makes use of selection sort to for the column and row // // sorting phases which is not that efficient. // // ************************************************************************** // macro N = 4; macro M = 4; macro I = 64; module ShearOddEvenSort([M*N]int{I} ?a,[M][N]int{I}b, event ready) { bool swapped,colsorted,rowsorted,firstRound; // gather the input row-wise in the matrix for(i=0..(M-1)) for(j=0..(N-1)) b[i][j] = a[i*N+j]; firstRound = true; weak abort loop { // column-wise sorting by OddEvenSort colsorted = false; while(!colsorted) { next(colsorted) = true; colOddStep: pause; for(j=0..(N-1)) { for(i=0..(M-3)/2){ if(b[2*i+1][j]>b[2*i+2][j]) { next(b[2*i+2][j]) = b[2*i+1][j]; next(b[2*i+1][j]) = b[2*i+2][j]; next(colsorted) = false; next(swapped) = true; } } } colEvenStep: pause; for(j=0..(N-1)) { for(i=0..(M-2)/2){ if(b[2*i][j]>b[2*i+1][j]) { next(b[2*i][j]) = b[2*i+1][j]; next(b[2*i+1][j]) = b[2*i][j]; next(colsorted) = false; next(swapped) = true; } } } next(rowsorted) = false; colCheckSorted: pause; } if(!swapped&!firstRound) emit(ready); else next(swapped) = false; // row-wise sorting by OddEvenSort while(!rowsorted) { next(rowsorted) = true; rowOddStep: pause; for(i=0..(M-1)) do || { for(j=0..(N-3)/2){ if((i%2==0?b[i][2*j+1]>b[i][2*j+2]:b[i][2*j+1]<b[i][2*j+2])) { next(b[i][2*j+2]) = b[i][2*j+1]; next(b[i][2*j+1]) = b[i][2*j+2]; next(rowsorted) = false; next(swapped) = true; } } } rowEvenStep: pause; for(i=0..(M-1)) do || { for(j=0..(N-2)/2){ if((i%2==0?b[i][2*j]>b[i][2*j+1]:b[i][2*j]<b[i][2*j+1])) { next(b[i][2*j]) = b[i][2*j+1]; next(b[i][2*j+1]) = b[i][2*j]; next(rowsorted) = false; next(swapped) = true; } } } next(colsorted) = false; rowCheckSorted: pause; } if(!swapped&!firstRound) emit(ready); else next(swapped) = false; firstRound = false; } when(ready); } drivenby Test01 { // generate already sorted sequence for(i=0..M*N-1) a[i] = i; dw: await(ready); // check that rows are sorted in snake-like order for(i=0..M-1) if(i%2==0) assert(forall(p=1..N-1) (b[i][p-1]<=b[i][p])); else assert(forall(p=1..N-1) (b[i][p-1]>=b[i][p])); // and check that the first and last column are sorted assert(forall(p=1..M-1) (b[p-1][0]<=b[p][0])); assert(forall(p=1..M-1) (b[p-1][N-1]<=b[p][N-1])); } drivenby Test02 { // generate reversed sorted sequence for(i=0..M*N-1) a[i] = M*N-1-i; dw: await(ready); // check that rows are sorted in snake-like order for(i=0..M-1) if(i%2==0) assert(forall(p=1..N-1) (b[i][p-1]<=b[i][p])); else assert(forall(p=1..N-1) (b[i][p-1]>=b[i][p])); // and check that the first and last column are sorted assert(forall(p=1..M-1) (b[p-1][0]<=b[p][0])); assert(forall(p=1..M-1) (b[p-1][N-1]<=b[p][N-1])); } drivenby Test03 { for(i=0..M*N-1) a[i] = ((i%2==0)?i:((M*N%2==0)?M*N-i:M*N-1-i)); dw: await(ready); // check that rows are sorted in snake-like order for(i=0..M-1) if(i%2==0) assert(forall(p=1..N-1) (b[i][p-1]<=b[i][p])); else assert(forall(p=1..N-1) (b[i][p-1]>=b[i][p])); // and check that the first and last column are sorted assert(forall(p=1..M-1) (b[p-1][0]<=b[p][0])); assert(forall(p=1..M-1) (b[p-1][N-1]<=b[p][N-1])); }