bitonic sort on many cores

bitonic.go

//
// Parallel merge sort in Golang
//
// (c) C. Löndahl 2018
//

package bitonic

import "log"

var w []uint64
var numProc uint64
var n uint64

type Bitonic struct {
    numProc uint64
    table   *[]uint64
}

func New(table *[]uint64, numProc uint64) Bitonic {
    if !__is_power(len(*table)) {
        log.Fatal("Needs to be a power of two in size")
    }

    return Bitonic{
        numProc: numProc,
        table:   table,
    }
}

func (b *Bitonic) Sort() {
    w = *b.table
    numProc = b.numProc
    n = uint64(len(w))
    z := make(chan int, 1)
    __sort(0, n-1, z)
}

func __is_power(x int) bool {
    return ((x != 0) && (x&(x-1)) == 0)
}

func __lswap(i uint64, j uint64) {
    a := w[i]
    b := w[j]
    if a <= b {
        w[i] = a
        w[j] = b
    } else {
        w[i] = b
        w[j] = a
    }
}

func __shift_block_chunk(l uint64, h uint64, j uint64, m uint64, c chan int) {
    s := h - l + 1
    t := s / 2
    u := t / m
    for i := j * u; i < (j+1)*u; i++ {
        __lswap(l+i, l+i+t)
    }
    c <- 1
}

func __shift_block(l uint64, h uint64) {
    s := h - l + 1
    t := s / 2
    if n/s >= numProc {
        for i := uint64(0); i < t; i++ {
            __lswap(l+i, l+i+t)
        }
    } else {
        m := s * numProc / n
        c := make(chan int, m)
        for j := uint64(0); j < m; j++ {
            go __shift_block_chunk(l, h, j, m, c)
        }
        // Sync
        for i := uint64(0); i < m; i++ {
            <-c
        }
    }
}

func __symmetric_block_chunk(l uint64, h uint64, j uint64, m uint64, c chan int) {
    s := h - l + 1
    t := s / 2
    u := t / m
    for i := j * u; i < (j+1)*u; i++ {
        __lswap(l+i, h-i)
    }
    c <- 1
}

func __symmetric_block(l uint64, h uint64) {
    s := h - l + 1
    if n/s >= numProc {
        for i := uint64(0); i < s/2; i++ {
            __lswap(l+i, h-i)
        }
    } else {
        m := s * numProc / n
        c := make(chan int, m)
        for j := uint64(0); j < m; j++ {
            __symmetric_block_chunk(l, h, j, m, c)
        }
        // Sync
        for i := uint64(0); i < m; i++ {
            <-c
        }
    }
}

func __bitonic_seq(l uint64, h uint64) {
    if l == h {
        return
    }
    __shift_block(l, h)
    s := h - l + 1
    t := s / 2
    __bitonic_seq(l, l+t-1)
    __bitonic_seq(l+t, h)
}

func __bitonic(l, h uint64, d chan int) {
    if l == h {
        return
    }
    __shift_block(l, h)
    s := h - l + 1
    t := s / 2
    if n/s >= numProc {
        __bitonic_seq(l, l+t-1)
        __bitonic_seq(l+t, h)
    } else {
        c := make(chan int, 2)
        go __bitonic(l, l+t-1, c)
        go __bitonic(l+t, h, c)
        // Sync
        <-c
        <-c
    }
    d <- 1
}

func __merge(l uint64, h uint64) {
    __symmetric_block(l, h)
    s := h - l + 1
    t := s / 2
    if n/s >= numProc {
        __bitonic_seq(l, l+t-1)
        __bitonic_seq(l+t, h)
    } else {
        c := make(chan int, 2)
        go __bitonic(l, l+t-1, c)
        go __bitonic(l+t, h, c)
        <-c
        <-c
    }
}

func __sort_seq(l uint64, h uint64) {
    if l == h {
        return
    }
    s := h - l + 1
    t := s / 2
    __sort_seq(l, l+t-1)
    __sort_seq(l+t, h)
    __merge(l, h)
}

func __sort(l uint64, h uint64, d chan int) {
    if l == h {
        return
    }
    s := h - l + 1
    t := s / 2
    if n/s >= numProc {
        __sort_seq(l, l+t-1)
        __sort_seq(l+t, h)
    } else {
        c := make(chan int, 2)
        go __sort(l, l+t-1, c)
        go __sort(l+t, h, c)
        // Sync
        <-c
        <-c
    }
    __merge(l, h)
    d <- 1
}