// ************************************************************************** // // // // 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. // // ************************************************************************** // macro aSize = 16; macro iSize = 64; module PeriodicBalancedSortNet([aSize]int{iSize} ?a,b, event !ready) { // gather the inputs for(i=0..aSize-1) b[i] = a[i]; for(l=0..log(aSize)-1) { // for every block for(d=0..log(aSize)-1) { // for every column the block let(L = exp(2,log(aSize)-d)) // size of a partition let(n = aSize/L) // number of partitions for(p=0..n-1) { // for each partition p for(i=0..L/2-1) { let(x = p*L+i) let(y = (p+1)*L-1-i) if(b[x]>b[y]) { next(b[x]) = b[y]; next(b[y]) = b[x]; } } } w2: 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); }