Team members
Assignment1
What is Bitonic sorting algorithm?
Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of O( n log^2( n )) comparators and have a delay of O( log^2( n )) , where n is the number of items to be sorted.(https://en.wikipedia.org/wiki/Bitonic_sorter)
(https://www.geeksforgeeks.org/bitonic-sort/)
Analysis and Profiling
The bitonic sorting algorithm is devised for the input length n being a power of 2. To check the noticeable time gap, we put 2^15, 2^20, 2^25.
void bitonicSort(int* array, int N){
int i,j,k;
for (k=2;k<=N;k=2*k) {
for (j=k>>1;j>0;j=j>>1) {
for (i=0;i<N;i++) {
int ixj=i^j;
if ((ixj)>i) {
if ((i&k)==0 && array[i]>array[ixj]){
int temp=array[i];
array[i]=array[ixj];
array[ixj]=temp;
}
if ((i&k)!=0 && array[i]<array[ixj]){
int temp=array[i];
array[i]=array[ixj];
array[ixj]=temp;
}
}
}
}
}
}Flat profile
The size of array:2^16(65536)
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
100.00 0.07 0.07 1 70.00 70.00 bitonicSort(int*, int)
0.00 0.07 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z11bitonicSortPii
0.00 0.07 0.00 1 0.00 0.00 generateRandom(int*, int)
0.00 0.07 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)The size of array:2^20(1048576)
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
98.94 1.87 1.87 1 1.87 1.87 bitonicSort(int*, int)
1.06 1.89 0.02 1 0.02 0.02 generateRandom(int*, int)
0.00 1.89 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z11bitonicSortPii
0.00 1.89 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)The size of array:2^24(16777216)
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
99.53 41.98 41.98 1 41.98 41.98 bitonicSort(int*, int)
0.47 42.18 0.20 1 0.20 0.20 generateRandom(int*, int)
0.00 42.18 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z11bitonicSortPii
0.00 42.18 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)Assignment2
First, array is unsorted array.
second box is stage 1, and orange boxes are sorted in ascending order and green boxes are sorted in descending order. Third box is stage 2 and it has 2 rounds. In first round, there are 2 orange and green boxes that contains 4 elements. in this case, index 0 and 2 and 1 and 3 will be compared and sorted in ascending if orange box and in descending if green box. then in round 2, index 0 and 1 , 2 and 3 ... will be compared and sorted. Third box and Fourth box are same.
