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 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