56
edits
Changes
→Assignment 1
code website: https://www.geeksforgeeks.org/selection-sort/
==== Bitonic Sort ====
Bitonic Sort is a classic parallel algorithm for sorting.
'''Source Code'''
<pre>
void bitonic_sort(int *data, int N)
{
int i, j, k;
int temp;
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 && data[i] > data[ixj]) {
temp = data[i];
data[i] = data[ixj];
data[ixj] = temp;
}
if ((i&k) != 0 && data[i] < data[ixj]) {
temp = data[i];
data[i] = data[ixj];
data[ixj] = temp;
}
}
}
}
}
}
</pre>
'''gprof results'''
Tested the Bitonic sort with three different array size: 4194304, 16777216, and 67108864.
<pre>
// Array Size 2^22 = 4194304
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls Ts/call Ts/call name
100.00 4.20 4.20 bitonic_sort(int*, int)
0.00 4.20 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z12bitonic_sortPii
</pre>
<pre>
// Array Size 2^24 = 16777216
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls Ts/call Ts/call name
100.00 19.84 19.84 bitonic_sort(int*, int)
0.00 19.84 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z12bitonic_sortPii
</pre>
<pre>
// Array Size 2^26 = 67108864
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls Ts/call Ts/call name
100.00 88.26 88.26 bitonic_sort(int*, int)
0.00 88.26 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z12bitonic_sortPii
</pre>
'''Result in chart diagram'''
[[File:HVBitonicSort.png]]
'''Reference'''
https://www.geeksforgeeks.org/bitonic-sort/
=== Assignment 2 ===
=== Assignment 3 ===
