// ************************************************************************** // // // // 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 // // // // ************************************************************************** // // OddEvenSort is similar to BubbleSort, but lends itself better to parallel // // implementation as shown below. The algorithm works as follows: Each // // iteration consists of an oddStep and an evenStep. In oddStep, the algorithm// // checks the pairs (1,2);(3,4);(5,6);... for swaps, and in the evenStep, it // // checks the pairs (0,1);(2,3);(4,5);... for swaps. It is easily seen that // // the array is sorted if there was neither a swap in the oddStep nor in the // // evenStep. // // The algorithm can be easily parallelized in that all the swaps checked and // // done in the oddStep and the evenStep, respectively, are done in parallel. // // This way, N processors are required to sort a list of size N with N steps. // // To determine the loop bounds for oddStep and evenStep, consider the cases // // (1) aSize=2N (with N:=aSize/2): // // oddStep: (1,2);(3,4);(5,6);...;(2N-3,2N-2) // // evenStep: (0,1);(2,3);(4,5);...;(2N-2,2N-1) // // and we have (aSize-3)/2 = (2N-3)/2 = N-2 // // and (aSize-2)/2 = (2N-2)/2 = N-1 // // (2) aSize=2N+1 (with N:=aSize/2): // // oddStep: (1,2);(3,4);(5,6);...;(2N-1,2N) // // evenStep: (0,1);(2,3);(4,5);...;(2N-2,2N-1) // // and we have (aSize-3)/2 = (2N-2)/2 = N-1 // // and (aSize-2)/2 = (2N-1)/2 = N-1 // // ************************************************************************** // macro aSize = 16; macro iSize = 64; module OddEvenSort([aSize]int{iSize} ?a,b, event !ready) { bool sorted; for(i=0..(aSize-1)) b[i] = a[i]; sorted = false; while(!sorted) { next(sorted) = true; oddStep: pause; for(i=0..(aSize-3)/2){ if(b[2*i+1]>b[2*i+2]) { next(b[2*i+2]) = b[2*i+1]; next(b[2*i+1]) = b[2*i+2]; next(sorted) = false; } } evenStep: pause; for(i=0..(aSize-2)/2){ if(b[2*i]>b[2*i+1]) { next(b[2*i]) = b[2*i+1]; next(b[2*i+1]) = b[2*i]; next(sorted) = false; } } checkSorted: pause; } emit(ready); } drivenby Test01 { for(i=0..aSize-1) a[i] = i; dw: await(ready); for(i=0..aSize-1) assert(b[i] == i); } drivenby Test02 { for(i=0..aSize-1) a[i] = aSize-1-i; dw: await(ready); for(i=0..aSize-1) assert(b[i] == i); } drivenby Test03 { for(i=0..aSize-1) a[i] = ((i%2==0)?i:((aSize%2==0)?aSize-i:aSize-1-i)); dw: await(ready); for(i=0..aSize-1) assert(b[i] == i); }