// ************************************************************************** // // // // 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. // // ************************************************************************** // [16] nat b; function exp(nat x, nat y):nat{ nat h1,i; h1 = 1; if(x!=0){ for(i=1..y){ h1 = h1*x; } } return h1; } function PeriodicBalancedSortNet([16]nat a): nat{ nat i,l,d, l1, h, n; nat aSize,x,y, p; aSize = 16; //gather the inputs for(i=0..aSize-1){ b[i]=a[i]; } for(l=0..3){ // 3 = log2 16 for(d=0..3){ l1 = exp(2,(4-d)); n = aSize/l1; for(p=0..n-1){ for(i=0..l1/2-1){ x = p*l1+i; y = (p+1)*l1-1-i; if(b[x]>b[y]){ h = b[x]; b[x]=b[y]; //swap b[y]= h; } } } } } return 1; } thread test1{ nat t; [16]nat a; nat i; bool test1_passed; for(i=0..15){ a[i]=i+1; } a[5]=9; a[8]=6; a[10]=7; a[6]=11; test1_passed = true; t = PeriodicBalancedSortNet(a); for(i=0..15){ if((b[i]==(i+1)) & (test1_passed != false)){ test1_passed = true; }else{ test1_passed = false; } } } thread test2{ nat t; [16]nat a; nat i; bool test2_passed; for(i=0..15){ a[i]=i+1; } test2_passed = true; t = PeriodicBalancedSortNet(a); for(i=0..15){ if((b[i]==(i+1)) & (test2_passed != false)){ test2_passed = true; }else{ test2_passed = false; } } } thread test3{ nat t; [16]nat a; nat i; bool test3_passed; for(i=0..15){ a[i]=16-i; } test3_passed = true; t = PeriodicBalancedSortNet(a); for(i=0..15){ if((b[i]==(i+1)) & (test3_passed != false)){ test3_passed = true; }else{ test3_passed = false; } } }