// ************************************************************************** // // // // 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 // // // // ************************************************************************** // // PeriodicBalanceSortNet implements the periodic balanced sorting network // // [DPRS89]. This sorting network has depth log(N)^2 and requires N*log(N)^2 // // comparators. It is therefore not very efficient; it simply consists of a // // sequence of log(N) blocks of the same kind, where each block consists of // // log(N) columns where each has N comparators in form of reversed half // // cleaners in the single partitions. // // ************************************************************************** // import SortNet16.Swap; macro aSize = 16; macro iSize = 64; module PeriodicBalancedSortNet([aSize]nat{iSize} ?a,b, event !ready) { // gather the inputs for(i=0..aSize-1) b[i] = a[i]; for(i=0..log(aSize)-1) { // step 1: (8 swaps) Swap(b[0],b[15]); Swap(b[1],b[14]); Swap(b[2],b[13]); Swap(b[3],b[12]); Swap(b[4],b[11]); Swap(b[5],b[10]); Swap(b[6],b[9]); Swap(b[7],b[8]); pause; // step 2: (8 swaps) Swap(b[0],b[7]); Swap(b[1],b[6]); Swap(b[2],b[5]); Swap(b[3],b[4]); Swap(b[8],b[15]); Swap(b[9],b[14]); Swap(b[10],b[13]); Swap(b[11],b[12]); pause; // step 3: (8 swaps) Swap(b[0],b[3]); Swap(b[1],b[2]); Swap(b[4],b[7]); Swap(b[5],b[6]); Swap(b[8],b[11]); Swap(b[9],b[10]); Swap(b[12],b[15]); Swap(b[13],b[14]); pause; // step 4: (8 swaps) Swap(b[0],b[1]); Swap(b[2],b[3]); Swap(b[4],b[5]); Swap(b[6],b[7]); Swap(b[8],b[9]); Swap(b[10],b[11]); Swap(b[12],b[13]); Swap(b[14],b[15]); 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); }