K2

Team members

• Youngmin Kim
• Kwangsoo Jin

---

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)

The process of bitonic algorithm

(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 number of elements in array:2^15(32768)

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
100.00      0.02     0.02        1    20.00    20.00  bitonicSort(int*, int)
  0.00      0.02     0.00        1     0.00     0.00  _GLOBAL__sub_I__Z11bitonicSortPii
  0.00      0.02     0.00        1     0.00     0.00  generateRandom(int*, int)
  0.00      0.02     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)

The number of elements in 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.95      1.89     1.89        1     1.89     1.89  bitonicSort(int*, int)
  1.05      1.91     0.02        1     0.02     0.02  generateRandom(int*, int)
  0.00      1.91     0.00        1     0.00     0.00  _GLOBAL__sub_I__Z11bitonicSortPii
  0.00      1.91     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)

The number of elements in array:2^25(33554432)

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 99.46     91.66    91.66        1    91.66    91.66  bitonicSort(int*, int)
  0.54     92.16     0.50        1     0.50     0.50  generateRandom(int*, int)
  0.00     92.16     0.00        1     0.00     0.00  _GLOBAL__sub_I__Z11bitonicSortPii
  0.00     92.16     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)