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
2 n) on a serial computer but runs only O(log 2 n) in
parallel.[2]
Algorithm:
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 5th
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.
