Getting to know parallel programming

Parallel Programming was one of the interesting concepts I get to learn and try hands-on during my grad school in UPLB. The ability to do a task "shared" by multiple resources is surely handy when it comes to finishing large tasks in a limited amount of time. One of the things we had to do was sorting (descending or ascending) a set of random numbers by first creating a bitonic sort. It runs really fast and can be done using MPI, specifically, mpich2. Here's the content of the paper I did for the exercise:

 Bitonic Description:

Bitonic sorting is a divide-and-conquer strategy which utilizes a comparator network Bitonic sort to produce the bitonic sequence and the Bitonic merge to produce the sorted sequence.[1]

Elements are rearranged into a bitonic sequence first before finally producing the sorted sequence. A bitonic sequence is a sequence which monotonically increases then monotonically decreases.  The split of the input into these two bitonic sequences is called the bitonic split. Afterwhich, recursive bitonic splits in shorter sequences are done(bitonic merge)  until the subsequence is of size one. This will then produce the sorted sequence, monotonically increasing. [2] 

 The bitonic sort runs in O(n log ² n) on a serial computer but runs only O(log ² n) in parallel.[2]

Algorithm:

 1.       In the main function, the values to be sorted are stored in a one-dimensional array, arrayNum[]

2. Setup the MPI variables: process_rank, num_processes and call the necessary MPI functions:     MPI_Init(&argc, &argv);   MPI_Comm_size(MPI_COMM_WORLD, &num_processes); and     MPI_Comm_rank(MPI_COMM_WORLD, &process_rank);

3.  for i=0 to dimension size  {

   for j=i  to 0 {

      bit1 = get the (i+1)th bit of the process_rank  and do binary operation & with 1

      bit2 = get the jth bit of the process_rank  and do binary operation & with 1

      compare bit1 and bit2

         if bit and bit2 are equal

          call compare_exchange_min(…) and store returned value to retrieve

        else

          call compare_exchange_max(…) and store returned value to retrieve

  arrayNum[process_rank] = retrieve;   

    }

}

4.    print the value of the array to verify sorted values

          

      5.  In compare_exchange_min():

Exchange values with its partner process number by calling MPI_Send() then MPI_Receive

Sample Run with 16 input elements:

Input:

 arrayNum[16] = {95, 90, 3, 8,  9, 23, 18, 40, 12,  0, 60, 5, 10, 14, 20, 35};

The array elements are in bitonic sequence at 5^th iteration: 

Pass 5:  arrayNum[16] = {3, 8, 9, 18,  23, 40, 90, 95, 60,  35, 20,  14,  12, 10, 5, 0};

Output:

arrayNum[16] = {0, 3, 3, 8, 9, 23, 18, 40, 12,  0, 60,  5, 10, 14, 20, 35};

The actual code can be found in my github repo:                     https://github.com/ashlynkim/academe/blob/test/bitonic_sort.c

The figure below shows the process of the Bitonic Build followed by the Bitonic Merging using the test case used in the experiment.  The Bitonic Build will output the elements in bitonic sequence (increasing to decreasing values). The bitonic merge will output the sorted sequence (increasing values).

References:

[1] Lang, H.W. Bitonic Sort. http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm Last updated: 05/18/2010                         

[2] Grama, Ananth, Anshul Gupta, and George Karypis. Introduction to parallel computing: design and analysis of algorithms. Redwood City, CA: Benjamin/Cummings Publishing Company, 1994.