Bitonic Sort in Go

0. Context

This semester I’m enrolled in CSE6220: Into to HPC class, where Prof. Vuduc tries to make sure we have a lot of fun (and learn some HPC stuff along the way).

For the first assignment, we were expected to turn a simple program into equally simple program but one that can execute some of its instructions in parallel. The program is bitonic sorter written in C, and all we had to do was to inject a single OpenMP instruction. After running the resultant code on Tech’s DeepThought cluster, I got puzzled with the question: how hard will it be to implement the very same bitonic sorter in Go?

Turned out, it was trivial to do!

So, this post is a quick summary of the work done. Please note that implemented sorter is primitive at best:

• it runs on a single machine (with multiple cores), no distribution to separate nodes
• it sorts only integers (easy to fix, but requires some typing..nobody mention generics here!)

1. Prerequisites

If you wonder what Bitonic Sort is, you definitely wonder what Sorting Networks are all about.

Here are some links to get you up to speed in no time:

• Sorting Networks A really nice intro to parallel programming (it is a part of CS344 on Udacity)
• Bitonic sort Amazing explanation of Bitonic Sort from Fachhochschule Flensburg.

For our purposes it is enough to understand that a sorting network is a special kind of sorting algorithm, where the sequence of comparisons is not data-dependent.

Sounds like a good case for parallel execution, right?

2. Implementation

You know what is really nice about Bitonic Sort? Not only it can perform really well, it is really easy to implement.

Here is the full code:

 1package bitonic
 2
 3const (
 4        SORT_ASC  bool = true
 5        SORT_DESC bool = false
 6)
 7
 8var lst []int
 9
10func Sort(input []int, dir bool) {
11        lst = input
12        sentinel := make(chan int)
13        go bitonicSort(0, len(lst), dir, sentinel)
14        <-sentinel
15}
16
17func bitonicSort(lo int, n int, dir bool, sentinel chan int) {
18        if n > 1 {
19                m := n / 2
20                c1 := make(chan int)
21                c2 := make(chan int)
22                go bitonicSort(lo, m, SORT_ASC, c1)
23                go bitonicSort(lo+m, m, SORT_DESC, c2)
24                <-c1
25                <-c2
26                bitonicMerge(lo, n, dir, sentinel)
27        } else {
28                sentinel <- 1
29        }
30}
31
32func bitonicMerge(lo int, n int, dir bool, sentinel chan int) {
33        if n > 1 {
34                m := n / 2
35                for i := lo; i < lo+m; i++ {
36                        compareAndSwap(i, i+m, dir)
37                }
38                c1 := make(chan int)
39                c2 := make(chan int)
40                go bitonicMerge(lo, m, dir, c1)
41                go bitonicMerge(lo+m, m, dir, c2)
42                <-c1
43                <-c2
44        }
45
46        sentinel <- 1
47}
48
49func compareAndSwap(i int, j int, dir bool) {
50        if dir == (lst[i] > lst[j]) {
51                lst[i], lst[j] = lst[j], lst[i]
52        }
53}

3. Analysis (kind of)

You can do your own experiments by forking farazdagi/bitonic repo.

Here is what I did:

• tried to run on a single core, on 4 cores, and on 8 cores
• every test got three runs, average time was taken
• the very same code was run every time i.e. even in case of a single core run, I used exactly the same concurrent program.

Here is a what I got:

Notes:

• as you see elapsed time to sort $2^{14}$ items on a single processor quickly goes up. Our parallel execution on multiple processors can handle the load easily.
• $2^{20} = 1.048.576$ and it takes ~$14$ seconds to sort those 1M records on 8-core machine. Pretty impressive.
• on second figure, when we compare 4 and 8 cores, difference is not that striking. I guess our parallel execution becomes dominated by memory accesses (sorting is in shared memory).

4. Summary and Take-Aways

1. Go is truly amazing language and I will definitely experiment with its concurrency model more (as we proceed with CSE6220). So, you should probably expect more posts similar to this one.
2. If you got interested in Bitonic sort, here is a list of awesomeness:

• Bitonic sorting network for n not a power of 2
• Sorting in Parallel
• Parallel Recursion: Batcher’s Bitonic Sort
• Bitonic Sort

Don’t forget to fork the repo. You can also follow me on Twitter.

Have a nice day and happy hacking!